Zurück Vor

Detailergebnis zu DOK-Nr. 60001

Schnelle Kürzest-Weg-Suche in zeitlich variablen Verkehrsnetzen (Orig. engl.: Fast shortest path computation in time-dependent traffic networks)

Autoren	N. Lefebvre M. Balmer
Sachgebiete	5.0 Allgemeines (Verkehrsplanung, Raumordnung) 6.2 Verkehrsberechnungen, Verkehrsmodelle

Zürich: Institut für Verkehrsplanung und Transporttechnik (IVT), ETH Zürich, 2007, 27 S., 16 B, zahlr. Q (Working paper / Institut für Verkehrsplanung und Transporttechnik (IVT), ETH Zürich H. 439)

Die Kürzest-Weg-Suche zwischen einem Start- und einem Endknoten ist von essentieller Bedeutung für die Rechengeschwindigkeit von Verkehrsflusssimulationen. Inhalt dieser Untersuchung sind verschiedene Routing-Algorithmen und Beschleunigungsmethoden für die Kürzest-Weg-Suche in gerichteten Graphen, deren Attribute über den Tag variabel sind. Für die Untersuchung wurde das Programm MATSim-T (Multi-Agent Traffic Simulation Toolkit) genutzt. Es wurden Variationen des Dijkstra-Algorithmus und des A*-Algorithmus anhand verschiedener Schweizer Verkehrsnetze gegenübergestellt. Als schnellster Algorithmus hat sich der A*-Algorithmus mit heuristischer Schätzung erwiesen. Die Vorteile machen sich insbesondere auf kurzen Routen bemerkbar, auf welchen er 400-mal schneller als der Dijkstra-Algorithmus zum Ziel kommt. Mit zunehmender Länge der Routen nähert sich die Rechengeschwindigkeit beider Verfahren an.