Kürzeste-Wege-Findung
Beteiligte Mitarbeiter
Beschreibung
Das klassische Kürzeste-Wege-Problem, bei dem in einem Netzwerk ein kürzester (schnellster, etc.) Weg von einem Start- zu einem Zielknoten gesucht wird, ist zentraler Bestandteil vieler Algorithmen und liegt nicht zuletzt Anwendungen wie Routenplanern oder Fahrplanauskunftssystemen zugrunde.
In den letzten Jahren hat sich die Forschung auf das Finden von kürzesten Wegen in Straßengraphen konzentriert. Wir haben uns mit der Fragestellung beschäftigt, inwieweit Lösungsansätze für Straßengraphen auf Fahrplanauskunftsysteme übertragen werden können. Dabei haben wir festgestellt, dass Straßengraphen viele Gemeinsamkeiten zu Eisenbahngraphen haben. Allerdings gibt es auch deutliche Unterschiede, die das Finden von optimalen Routen deutlich schwieriger macht.
Für eine multimodale Variante dieses Problems, bei der einschränkende Bedingungen an kürzeste Wege formuliert werden können, wurde eine gemeinschaftlich mit Kollegen der Virginia Tech und der Arizona State University entwickelte Implementation verfeinert, um Beschleunigungskonzepte erweitert und in unterschiedlichen Szenarien unter Verwendung von Realdaten systematisch evaluiert.
Viele Techniken zur Beschleunigung von Kürzeste-Wege Anfragen basieren darauf fiktive Direktverbindungen in das zu durchsuchende Netzwerk einzufügen. In Kooperation mit der Universität L'Aquila wurde untersucht wie komplex es ist diese Direktverbindungen in optimaler Art und Weise einzufügen.