Open access
Datum
2007Typ
- Working Paper
ETH Bibliographie
yes
Altmetrics
Abstract
In agent based traffic simulations which use systematic relaxation to reach a steady state of the scenario, the performance of the routing algorithm used for finding a path from a start node to an end node in the network is crucial for the overall performance. For example, a systematic relaxation process for a large scale scenario with about 7.5 million inhabitants (roughly the population of Switzerland) performing approximately three trips per day on average requires about 2.25 million route calculations, assuming that 10% of the trips are adapted per iteration. Expecting about 100 iterations to reach a stable state, 225 million routes have to be delivered in total. This paper focuses on routing algorithms and acceleration methods for point-to-point shortest path computations in directed graphs that are time-dependent, i.e. link weights vary during time. The work is done using MATSim-T (Multi-Agent Traffic Simulation Toolkit) which used for large-scale agent-based traffic simulations. The algorithms under investigation are both variations of Dijkstra’s algorithm and the A*-algorithm. Extensive performance tests are conducted on different traffic networks of Switzerland. The fastest algorithm is the A* algorithm with an enhanced heuristic estimate: While it is up to 400 times faster than Dijkstra’s original algorithm on short routes, the speed up compared to Dijkstra diminishes with the length of the route to be calculated. Mehr anzeigen
Persistenter Link
https://doi.org/10.3929/ethz-a-005437245Publikationsstatus
publishedZeitschrift / Serie
Arbeitsberichte Verkehrs- und RaumplanungBand
Verlag
ETH, Eidgenössische Technische Hochschule Zürich, IVT, Institut für Verkehrsplanung und TransportsystemeThema
SCHEDULING + TIMETABLING (OPERATIONS RESEARCH); VERKEHRSMODELLE + VERKEHRSSIMULATION (VERKEHR UND TRANSPORT); Shortest path problem; Multi-agent traffic simulation; TRANSPORT MODELS + TRAFFIC SIMULATION (TRANSPORTATION AND TRAFFIC); WEGPLANUNG + ZEITPLANUNG (OPERATIONS RESEARCH); Time-dependent networksOrganisationseinheit
02610 - Inst. f. Verkehrspl. u. Transportsyst. / Inst. Transport Planning and Systems03521 - Axhausen, Kay W. (emeritus) / Axhausen, Kay W. (emeritus)
02226 - NSL - Netzwerk Stadt und Landschaft / NSL - Network City and Landscape
02655 - Netzwerk Stadt u. Landschaft ARCH u BAUG / Network City and Landscape ARCH and BAUG
Anmerkungen
Online Publication Date 2007.ETH Bibliographie
yes
Altmetrics