- Working Paper
Rights / licenseIn Copyright - Non-Commercial Use Permitted
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 Show more
Journal / seriesArbeitsberichte Verkehrs- und Raumplanung
PublisherETH, Eidgenössische Technische Hochschule Zürich, IVT, Institut für Verkehrsplanung und Transportsysteme
SubjectSCHEDULING + 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 networks
Organisational unit02610 - Institut für Verkehrsplanung und Transportsysteme (IVT) / Institute for Transport Planning and Systems (IVT)
03521 - Axhausen, Kay W.
NotesOnline Publication Date 2007.
MoreShow all metadata