Real-time Traffic Assignment Using Engineered Customizable Contraction Hierarchies

doi:10.1145/3362693

Real-time Traffic Assignment Using Engineered Customizable Contraction Hierarchies

2019-12-10

0

PRE

AI

DOI：10.1145/3362693

原文链接

原文求助

摘要

En 中文

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.

Real-time Traffic Assignment Using Engineered Customizable Contraction Hierarchies

摘要

AI总结

期刊

机构

引用论文