In many algorithms for traffic assignment, the most time-consuming step is shortest path search between all O–D pairs. Almost unnoticed by the transport modeling community, there has been an enormous amount of research on acceleration techniques for the shortest path problem in road networks in the past decade. These techniques usually divide the problem into a relatively expensive preprocessing phase and a significantly accelerated search phase. In this paper, the recently developed customizable contraction hierarchies are used for both shortest path search and network loading in the bi-conjugate Frank–Wolfe algorithm. For the largest test network, this approach achieves a speedup by a factor of 42 compared with a straightforward implementation of Dijkstra’s algorithm.
Accelerating Traffic Assignment with Customizable Contraction Hierarchies
Transportation Research Record: Journal of the Transportation Research Board
Transportation Research Record: Journal of the Transportation Research Board ; 2674 , 1 ; 188-196
2020-01-01
Article (Journal)
Electronic Resource
English
Real-Time Traffic Assignment Using Fast Queries in Customizable Contraction Hierarchies
DataCite | 2018
|Time-Dependent Route Planning with Contraction Hierarchies
DataCite | 2014
|