MUSE: Reiseplanung inspiriert von multimodalen Separatoren

In diesem Artikel wird ein multimodaler Algorithmus für den kürzesten Pfad vorgestellt, der auf Graphtrennzeichen basiert. Durch die Aufteilung des Netzwerks in Partitionen kann die Vorverarbeitung parallelisiert werden, was effiziente Berechnungen des kürzesten Pfades über verschiedene Verkehrsträger hinweg ermöglicht. Während der Abfragephase ermittelt der Algorithmus schnell die kürzeste Route für eine bestimmte Abfolge von Verkehrsträgern. Die laufenden Arbeiten konzentrieren sich auf die Skalierung des Ansatzes auf größere Grafiken (Frankreich und Europa) und die Untersuchung mehrstufiger Partitionen mit bidirektionaler Suche, um die Leistung weiter zu verbessern, sowie auf die Anpassung der Methode für dynamische Grafiken mit zeitabhängigen Laufzeiten.

‍

Mit der Entwicklung der Cloud boomt das Gebiet der Algorithmen zur Berechnung kürzerer Pfade. Einige Lösungen, die als multimodal bezeichnet werden, sind darauf ausgelegt, verschiedene Verkehrsträger zu kombinieren, allerdings auf Kosten einer erheblichen Erhöhung der Komplexität. Hier schlagen wir MUSE vor, einen Algorithmus, der auf Graphtrennzeichen basiert, aber an den multimodalen Fall angepasst ist. In einer Vorverarbeitungsphase unterteilen wir den Graphen zunächst in unabhängige Partitionen (oder Zellen), die jeweils in Transportmodi unterteilt sind, sodass wir später jede Anfrage beantworten können. Anschließend berechnen wir alle kürzesten Routen für diese kleine Anzahl von Zellen im Voraus und berücksichtigen dabei die Beschriftungen (Modi) jeder Kante. Auf diese Weise können wir in der Online-Phase sehr schnell auf eine Anfrage antworten: Der Benutzer gibt an, welche Modussequenzen er zulässt, und verwendet die im Voraus berechneten kürzesten Routen.