research-article

Open access

Online Route Replanning for Scalable System-Optimal Route Planning

Authors:

Robert J. Fitzgerald,

Farnoush Banaei-KashaniAuthors Info & Claims

SIGSPATIAL '21: Proceedings of the 29th International Conference on Advances in Geographic Information Systems

Pages 588 - 591

https://doi.org/10.1145/3474717.3484262

Published: 04 November 2021 Publication History

PDF eReader

Abstract

Route planning in transportation networks is typically performed as a single optimization at trip departure. In this paper, we consider the impact of within-trip replanning on the performance of the overall network in a fully-algorithmic route selection scenario. An experimental study of three real road networks using synthetic demand demonstrates in over 200 trials the effects of replanning with respect to the replanning rate and the adoption rate of replanning. Overall network travel times are reduced by up to 48.49% from a baseline where all drivers are assigned a single route, demonstrating the profound effect of dynamic within-trip replanning. These observations are part of our work exploring a system-optimal route planning strategy that is robust to network size and conditions.

References

[1]

1964. Traffic assignment manual. US Department of Commerce, Washington, DC (1964).

Google Scholar

[2]

Hannah Bast, Daniel Delling, Andrew Goldberg, Matthias Müller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato F Werneck. 2016. Route planning in transportation networks. In Algorithm engineering. Springer, 19--80.

Google Scholar

[3]

Geoff Boeing. 2017. OSMnx: New methods for acquiring, constructing, analyzing, and visualizing complex street networks. Computers, Environment and Urban Systems 65 (2017), 126--139.

Crossref

Google Scholar

[4]

Edith Cohen, Eran Halperin, Haim Kaplan, and Uri Zwick. 2003. Reachability and distance queries via 2-hop labels. SIAM J. Comput. 32, 5 (2003), 1338--1355.

Digital Library

Google Scholar

[5]

Daniel Delling, Andrew V Goldberg, Andreas Nowatzyk, and Renato F Werneck. 2013. PHAST: Hardware-accelerated shortest path trees. J. Parallel and Distrib. Comput. 73, 7 (2013), 940--952.

Crossref

Google Scholar

[6]

Daniel Delling, Andrew V Goldberg, Thomas Pajor, and Renato F Werneck. 2011. Customizable route planning. In International Symposium on Experimental Algorithms. Springer, 376--387.

Crossref

Google Scholar

[7]

Edsger W Dijkstra et al. 1959. A note on two problems in connexion with graphs. Numerische mathematik 1, 1 (1959), 269--271.

Google Scholar

[8]

Robert J Fitzgerald and Farnoush Banaei-Kashani. 2019. Toward System-Optimal Route Guidance. In 2019 20th IEEE International Conference on Mobile Data Management (MDM). IEEE, 91--99.

Google Scholar

[9]

Robert Geisberger, Peter Sanders, Dominik Schultes, and Christian Vetter. 2012. Exact routing in large road networks using contraction hierarchies. Transportation Science 46, 3 (2012), 388--404.

Digital Library

Google Scholar

[10]

Andreas Horni, Kai Nagel, and Kay W Axhausen. 2016. The multi-agent transport simulation MATSim. Ubiquity Press London:.

Google Scholar

[11]

OpenStreetMap contributors. 2018. Planet dump retrieved from https://planet.osm.org. https://www.openstreetmap.org.

Google Scholar

Cited By

View all

Zhang SLuo ZYang LTeng FLi T(2024)A survey of route recommendations: Methods, applications, and opportunitiesInformation Fusion10.1016/j.inffus.2024.102413108(102413)Online publication date: Aug-2024
https://doi.org/10.1016/j.inffus.2024.102413
Fitzgerald RBanaei-Kashani F(2021)City-Scale System-Optimal Route Planning with Route Replanning2021 IEEE International Conference on Big Data (Big Data)10.1109/BigData52589.2021.9671357(322-327)Online publication date: 15-Dec-2021
https://doi.org/10.1109/BigData52589.2021.9671357

Index Terms

Online Route Replanning for Scalable System-Optimal Route Planning

Recommendations

Multi‐AGV route planning in automated warehouse system based on shortest‐time Q‐learning algorithm
Abstract
Route planning for automated guided vehicles (AGVs) is one of the key factors that affects work efficiency of automated storage and retrieval systems (AS/RSes). Route planning plays an important role in the operation of AGVs. Since the ...
Optimal Route Reflection Topology Design
LANC '18: Proceedings of the 10th Latin America Networking Conference

Autonomous Systems (ASes) exchange routing information about networks they can reach in the Internet, and the most widely extended way to connect them is by means of Border Gateway Protocol (BGP) sessions. ASes set up external BGP (eBGP) sessions ...
Designing optimal iBGP route-reflection topologies
NETWORKING'08: Proceedings of the 7th international IFIP-TC6 networking conference on AdHoc and sensor networks, wireless networks, next generation internet

The Border Gateway Protocol (BGP) is used today by all Autonomous Systems (AS) in the Internet. Inside each AS, iBGP sessions distribute the external routes among the routers. In large ASs, relying on a full-mesh of iBGP sessions between routers is not ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SIGSPATIAL '21: Proceedings of the 29th International Conference on Advances in Geographic Information Systems

November 2021

700 pages

ISBN:9781450386647

DOI:10.1145/3474717

This work is licensed under a Creative Commons Attribution International 4.0 License.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 November 2021

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Conference

SIGSPATIAL '21

Sponsor:

SIGSPATIAL

SIGSPATIAL '21: 29th International Conference on Advances in Geographic Information Systems

November 2 - 5, 2021

Beijing, China

Acceptance Rates

Overall Acceptance Rate 257 of 1,238 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
294
Total Downloads

Downloads (Last 12 months)85
Downloads (Last 6 weeks)13

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Zhang SLuo ZYang LTeng FLi T(2024)A survey of route recommendations: Methods, applications, and opportunitiesInformation Fusion10.1016/j.inffus.2024.102413108(102413)Online publication date: Aug-2024
https://doi.org/10.1016/j.inffus.2024.102413
Fitzgerald RBanaei-Kashani F(2021)City-Scale System-Optimal Route Planning with Route Replanning2021 IEEE International Conference on Big Data (Big Data)10.1109/BigData52589.2021.9671357(322-327)Online publication date: 15-Dec-2021
https://doi.org/10.1109/BigData52589.2021.9671357

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Index Terms

Recommendations

Multi‐AGV route planning in automated warehouse system based on shortest‐time Q‐learning algorithm

Optimal Route Reflection Topology Design

Designing optimal iBGP route-reflection topologies