Real-time Traffic Assignment Using Engineered Customizable Contraction Hierarchies

Abstract

Given an urban road network and a set of origin-destination pairs, the traffic assignment problem asks for the traffic flow on each road segment. Common solution algorithms require a large number of shortest-path computations. In this article, we significantly accelerate the computation of flow patterns, enabling interactive transportation and urban planning applications. We achieve this by building a traffic assignment procedure upon customizable contraction hierarchies (CCH), revisiting and carefully engineering CCH customization and queries, and adapting CCH to compute batched point-to-point shortest paths. Although motivated by the traffic assignment problem, our optimizations apply to CCH in general. In contrast to previous work, our evaluation uses real-world production data for all parts of the input. On a metropolitan area encompassing about 2.7 million inhabitants, we decrease the flow-pattern computation for a typical 1-hour morning peak (a quarter million trips) from 90.9 to 14.1 seconds on one core and 2.4 seconds on a 16-core machine. This represents a speedup of 37 over the state of the art and more than three orders of magnitude over the Dijkstra-based baseline.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 28 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.