Route planning with flexible edge restrictions
Authors:
Open Access
- 30 March 2012
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Journal of Experimental Algorithmics
- Vol. 17
Abstract
In this work, we explore a new type of flexible shortest-path query, in which the query can be dynamically parameterized to constrain the type of edges that may be included in the resulting shortest path (e.g., find the shortest path in a road network that avoids toll roads and low overpasses, respective of the specified vehicle height). We extend the hierarchical preprocessing technique known as Contraction Hierarchies to efficiently support such flexible queries. We also present several effective algorithmic optimizations for further improving the overall scalability and query times of this approach, including the addition of goal-directed search techniques, search space pruning techniques, and generalizing the constraints of the local search. Experiments are presented for both the North American and the European road networks, showcasing the general effectiveness and scalability of our proposed methodology to large-scale, real-world graphs.Keywords
Funding Information
- Division of Information and Intelligent Systems (IIS-0705916IIS-0803410)
This publication has 8 references indexed in Scilit:
- Graph indexing of road networks for shortest path queries with label restrictionsProceedings of the VLDB Endowment, 2010
- Combining hierarchical and goal-directed speed-up techniques for dijkstra's algorithmACM Journal of Experimental Algorithmics, 2010
- Engineering multilevel overlay graphs for shortest-path queriesACM Journal of Experimental Algorithmics, 2009
- Engineering Route Planning Algorithms2009
- Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks2008
- Highway Hierarchies Hasten Exact Shortest Path Queries2005
- A Formal Basis for the Heuristic Determination of Minimum Cost PathsIEEE Transactions on Systems Science and Cybernetics, 1968
- A note on two problems in connexion with graphsNumerische Mathematik, 1959