License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2018.27
URN: urn:nbn:de:0030-drops-89623
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8962/
Buchhold, Valentin ;
Sanders, Peter ;
Wagner, Dorothea
Real-Time Traffic Assignment Using Fast Queries in Customizable Contraction Hierarchies
Abstract
Given an urban road network and a set of origin-destination (OD) pairs, the traffic assignment problem asks for the traffic flow on each road segment. A common solution employs a feasible-direction method, where the direction-finding step requires many shortest-path computations. In this paper, we significantly accelerate the computation of flow patterns, enabling interactive transportation and urban planning applications. We achieve this by revisiting and carefully engineering known speedup techniques for shortest paths, and combining them with customizable contraction hierarchies. In particular, our accelerated elimination tree search is more than an order of magnitude faster for local queries than the original algorithm, and our centralized search speeds up batched point-to-point shortest paths by a factor of up to 6. These optimizations are independent of traffic assignment and can be generally used for (batched) point-to-point queries. In contrast to prior work, our evaluation uses real-world data for all parts of the problem. On a metropolitan area encompassing more than 2.7 million inhabitants, we reduce the flow-pattern computation for a typical two-hour morning peak from 76.5 to 10.5 seconds on one core, and 4.3 seconds on four cores. This represents a speedup of 18 over the state of the art, and three orders of magnitude over the Dijkstra-based baseline.
BibTeX - Entry
@InProceedings{buchhold_et_al:LIPIcs:2018:8962,
author = {Valentin Buchhold and Peter Sanders and Dorothea Wagner},
title = {{Real-Time Traffic Assignment Using Fast Queries in Customizable Contraction Hierarchies}},
booktitle = {17th International Symposium on Experimental Algorithms (SEA 2018)},
pages = {27:1--27:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-070-5},
ISSN = {1868-8969},
year = {2018},
volume = {103},
editor = {Gianlorenzo D'Angelo},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8962},
URN = {urn:nbn:de:0030-drops-89623},
doi = {10.4230/LIPIcs.SEA.2018.27},
annote = {Keywords: traffic assignment, equilibrium flow pattern, customizable contraction hierarchies, batched shortest paths}
}
|
Keywords: |
|
traffic assignment, equilibrium flow pattern, customizable contraction hierarchies, batched shortest paths |
|
Collection: |
|
17th International Symposium on Experimental Algorithms (SEA 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
19.06.2018 |
