research-article

Alternative routes in road networks

Authors:

Daniel Delling,

Andrew V. Goldberg,

Renato F. WerneckAuthors Info & Claims

Journal of Experimental Algorithmics (JEA), Volume 18

Article No.: 1.3, Pages 1.1 - 1.17

https://doi.org/10.1145/2444016.2444019

Published: 19 April 2013 Publication History

Abstract

We study the problem of finding good alternative routes in road networks. We look for routes that are substantially different from the shortest path, have small stretch, and are locally optimal. We formally define the problem of finding alternative routes with a single via vertex, develop efficient algorithms for it, and evaluate them experimentally. Our algorithms are efficient enough for practical use and compare favorably with previous methods in both speed and solution quality.

References

[1]

Abraham, I., Delling, D., Goldberg, A. V., and Werneck, R. F. 2010a. Alternative routes in road networks. In Proceedings of the 9th International Symposium on Experimental Algorithms (SEA'10). Springer, 23--34.

Digital Library

[2]

Abraham, I., Fiat, A., Goldberg, A. V., and Werneck, R. F. 2010b. Highway dimension, shortest paths, and provably efficient algorithms. In Proceedings of the 21st Annual ACM--SIAM Symposium on Discrete Algorithms (SODA'10). 782--793.

Digital Library

[3]

Bader, R., Dees, J., Geisberger, R., and Sanders, P. 2011. Alternative route graphs in road networks. In Proceedings of the 1st International ICST Conference on Theory and Practice of Algorithms in (Computer) Systems (TAPAS'11). Springer, 21--32.

Digital Library

[4]

Cambridge Vehicle Information Technology Ltd. 2005. Choice routing. http://www.camvit.com.

[5]

Chen, Y., Bell, M. G. H., and Bogenberger, K. 2007. Reliable pretrip multipath planning and dynamic adaptation for a centralized road navigation system. IEEE Trans. Intell. Transp. Syst. 8, 1, 14--20.

Digital Library

[6]

Dantzig, G. B. 1962. Linear Programming and Extensions. Princeton University Press, Princeton, NJ.

[7]

Delling, D., Sanders, P., Schultes, D., and Wagner, D. 2009. Engineering route planning algorithms. In Algorithmics of Large and Complex Networks, J. Lerner, D. Wagner, and K. Zweig, Eds., Springer, 117--139.

Digital Library

[8]

Delling, D. and Wagner, D. 2009. Pareto paths with SHARC. In Proceedings of the 8th International Symposium on Experimental Algorithms (SEA'09). Springer, 125--136.

Digital Library

[9]

Demetrescu, C., Goldberg, A. V., and Johnson, D. S., Eds. 2006. Proceedings of the DIMACS Implementation Challenge: Shortest Paths.

[10]

Dijkstra, E. W. 1959. A note on two problems in connexion with graphs. Numerische Mathematik 1, 269--271.

Digital Library

[11]

Eppstein, D. 1994. Finding the k shortest paths. In Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science (FOCS'94). 154--165.

Digital Library

[12]

Geisberger, R., Kobitzsch, M., and Sanders, P. 2010. Route planning with flexible objective functions. In Proceedings of the 12th Workshop on Algorithm Engineering and Experiments (ALENEX'10). SIAM, 124--137.

[13]

Geisberger, R., Sanders, P., Schultes, D., and Delling, D. 2008. Contraction hierarchies: Faster and simpler hierarchical routing in road networks. In Proceedings of the 7th International Conference on Experimental Algorithms (WEA'08). Springer, 319--333.

Digital Library

[14]

Goldberg, A. V., Kaplan, H., and Werneck, R. F. 2009. Reach for A&ast;: Shortest path algorithms with preprocessing. In The Shortest Path Problem: Ninth DIMACS Implementation Challenge, C. Demetrescu, A. V. Goldberg, and D. S. Johnson, Eds., American Mathematical Society, 93--139.

[15]

Gutman, R. J. 2004. Reach-based routing: A new approach to shortest path algorithms optimized for road networks. In Proceedings of the 6th Workshop on Algorithm Engineering and Experiments (ALENEX'04). SIAM, 100--111.

[16]

Hansen, P. 1979. Bricriteria path problems. In Multiple Criteria Decision Making: Theory and Application, G. Fandel and T. Gal, Eds., Springer, 109--127.

[17]

Martins, E. Q. 1984. On a multicriteria shortest path problem. Euro. J. Oper. Res. 26, 3, 236--245.

[18]

Schultes, D. and Sanders, P. 2007. Dynamic highway-node routing. In Proceedings of the 6th Workshop on Experimental Algorithms (WEA'07). Springer, 66--79.

Digital Library

Cited By

Cornacchia GLemma LPappalardo L(2024)Alternative Routing based on Road PopularityProceedings of the 2nd ACM SIGSPATIAL Workshop on Sustainable Urban Mobility10.1145/3681779.3696836(14-17)Online publication date: 29-Oct-2024
https://dl.acm.org/doi/10.1145/3681779.3696836
Xu YLi LZhang MXu ZZhou X(2024)Global Optimal Travel Planning for Massive Travel Queries in Road NetworksIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.343940936:12(8377-8394)Online publication date: Dec-2024
https://doi.org/10.1109/TKDE.2024.3439409
Fahmin AShen BAamir Cheema MToosi AEunus Ali M(2024)Efficient Alternative Route Planning in Road NetworksIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2024.339617325:10(14220-14232)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1109/TITS.2024.3396173
Show More Cited By

Index Terms

Alternative routes in road networks
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory

Recommendations

Candidate Sets for Alternative Routes in Road Networks

We study the computation of good alternatives to the shortest path in road networks. Our approach is based on single via-node routing on top of contraction hierarchies and achieves superior quality and efficiency compared to previous methods. We present ...
Exact Routing in Large Road Networks Using Contraction Hierarchies

Contraction hierarchies are a simple approach for fast routing in road networks. Our algorithm calculates exact shortest paths and handles road networks of whole continents. During a preprocessing step, we exploit the inherent hierarchical structure of ...
Fast exact shortest path and distance queries on road networks with parametrized costs
SIGSPATIAL '15: Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems

We study a scenario for route planning in road networks, where the objective to be optimized may change between every shortest path query. Since this invalidates many of the known speedup techniques for road networks that are based on preprocessing of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Journal of Experimental Algorithmics

ACM Journal of Experimental Algorithmics Volume 18, Issue

2013

329 pages

ISSN:1084-6654

EISSN:1084-6654

DOI:10.1145/2444016

Issue’s Table of Contents

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 April 2013

Accepted: 01 September 2012

Revised: 01 June 2011

Received: 01 November 2010

Published in JEA Volume 18

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

56
Total Citations
View Citations
1,194
Total Downloads

Downloads (Last 12 months)62
Downloads (Last 6 weeks)3

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Cornacchia GLemma LPappalardo L(2024)Alternative Routing based on Road PopularityProceedings of the 2nd ACM SIGSPATIAL Workshop on Sustainable Urban Mobility10.1145/3681779.3696836(14-17)Online publication date: 29-Oct-2024
https://dl.acm.org/doi/10.1145/3681779.3696836
Xu YLi LZhang MXu ZZhou X(2024)Global Optimal Travel Planning for Massive Travel Queries in Road NetworksIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.343940936:12(8377-8394)Online publication date: Dec-2024
https://doi.org/10.1109/TKDE.2024.3439409
Fahmin AShen BAamir Cheema MToosi AEunus Ali M(2024)Efficient Alternative Route Planning in Road NetworksIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2024.339617325:10(14220-14232)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1109/TITS.2024.3396173
Amores DTanin EVasardani M(2024)Flexible Paths: A Path Planning Approach to Dynamic NavigationIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2023.334349025:6(4795-4808)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1109/TITS.2023.3343490
Zhao JLi LZhang MLuo ZZhao XZhou X(2024)A Just-In-Time Framework for Continuous Routing2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00350(4600-4613)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00350
Wang LWong RJensen C(2024)Congestion-Mitigating Spatiotemporal Routing in Road Networks2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00349(4586-4599)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00349
Cazor LWatling DDuncan LNielsen ORasmussen T(2024)A novel choice model combining utility maximization and the disjunctive decision rules, application to two case studiesJournal of Choice Modelling10.1016/j.jocm.2024.10051052(100510)Online publication date: Sep-2024
https://doi.org/10.1016/j.jocm.2024.100510
Lewis RCorcoran P(2024)Fast Algorithms for Computing Fixed-Length Round Trips in Real-World Street NetworksSN Computer Science10.1007/s42979-024-03223-35:7Online publication date: 9-Sep-2024
https://doi.org/10.1007/s42979-024-03223-3
Paricio-Garcia ALopez-Carmona M(2023)Application of Traffic Weighted Multi-Maps Based on Disjoint Routing Areas for Static Traffic AssignmentApplied Sciences10.3390/app13181007113:18(10071)Online publication date: 6-Sep-2023
https://doi.org/10.3390/app131810071
Böther MSchiller LFischbeck PMolitor LKrejca MFriedrich T(2023)Evolutionary Minimization of Traffic CongestionIEEE Transactions on Evolutionary Computation10.1109/TEVC.2022.322875027:6(1809-1821)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1109/TEVC.2022.3228750
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents