MUSE: Reiseroutenplanung inspiriert durch Multimodale Trennzeichen

11. Januar 2022
-
ALGOTEL 2020 - (französischsprachige Tagung zu algorithmischen Aspekten der Telekommunikation)
Anime FALEK
und Cristel Pelsser, Sébastien Julien, Fabrice Theoleyre
Partner-Labor:
Netzwerke
unter
Université de Strasbourg

In diesem Beitrag wird ein multimodaler Algorithmus für kürzeste Wege vorgestellt, der auf Graphenseparatoren basiert. Durch die Unterteilung des Netzes in Partitionen kann die Vorverarbeitung parallelisiert werden, was eine effiziente Berechnung des kürzesten Weges über verschiedene Verkehrsträger hinweg ermöglicht. Während der Abfragephase findet der Algorithmus schnell die kürzeste Route für jede beliebige Abfolge von Verkehrsträgern. Laufende Arbeiten konzentrieren sich auf die Skalierung des Ansatzes auf größere Graphen (Frankreich und Europa) und die Erforschung mehrstufiger Partitionen mit bidirektionaler Suche, um die Leistung weiter zu verbessern, sowie auf die Anpassung der Methode für dynamische Graphen mit zeitabhängigen Reisezeiten.

Mit der Entwicklung der Cloud boomt der Bereich der Algorithmen zur Berechnung kürzerer Wege. Einige Lösungen, die als multimodal bekannt sind, wurden entwickelt, um verschiedene Transportarten zu kombinieren, allerdings um den Preis einer erheblichen Erhöhung der Komplexität. Hier schlagen wir MUSE vor, einen Algorithmus, der auf Graphentrennern 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 Verkehrsträger unterteilt sind, so dass wir später jede Anfrage beantworten können. Anschließend berechnen wir alle kürzesten Routen auf dieser kleinen Anzahl von Zellen, wobei wir die Kennzeichnungen (Modi) der einzelnen Kanten berücksichtigen. Auf diese Weise können wir in der Online-Phase sehr schnell auf eine Anfrage antworten: Der Benutzer gibt die von ihm zugelassenen Modusfolgen an und verwendet die vorausberechneten kürzesten Routen.

Lesen Sie die vollständige Veröffentlichung
Anime FALEK
und Cristel Pelsser, Sébastien Julien, Fabrice Theoleyre
11. Januar 2022
-
ALGOTEL 2020 - (französischsprachige Tagung zu algorithmischen Aspekten der Telekommunikation)