research-article

Personalized route planning in road networks

Authors:

Sabine StorandtAuthors Info & Claims

SIGSPATIAL '15: Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems

Article No.: 45, Pages 1 - 10

https://doi.org/10.1145/2820783.2820830

Published: 03 November 2015 Publication History

Abstract

Computing shortest paths in road networks with millions of nodes and edges is challenging on its own. In the last few years, several preprocessing-based acceleration techniques have been developed to enable query answering orders of magnitudes faster than a plain Dijkstra computation. But most of these techniques work only if the metric which determines the optimal path is static or rarely changes. In contrast to that, we aim at answering personalized route planning queries. Here, every single query comes with a specification of its very own metric. This increases the combinatorial complexity of the problem significantly. We develop new preprocessing schemes that allow for real-time personalized route planning in huge road networks while keeping the memory footprint of the preprocessed data and subsequent queries small.

References

[1]

I. Abraham, D. Delling, A. V. Goldberg, and R. F. Werneck. Alternative routes in road networks. In Proceedings of the 9th international conference on Experimental Algorithms, SEA'10, pages 23--34, Berlin, Heidelberg, 2010. Springer-Verlag.

Digital Library

[2]

I. Abraham, D. Delling, A. V. Goldberg, and R. F. Werneck. A hub-based labeling algorithm for shortest paths in road networks. In Experimental Algorithms, pages 230--241. Springer, 2011.

Digital Library

[3]

H. Bast, S. Funke, P. Sanders, and D. Schultes. Fast routing in road networks with transit nodes. Science, 316(5824):566--566, 2007.

[4]

G. V. Batz, D. Delling, P. Sanders, and C. Vetter. Time-dependent contraction hierarchies. In ALENEX, volume 9. SIAM, 2009.

Digital Library

[5]

G. D'Angelo, D. Frigioni, and C. Vitale. Dynamic arc-flags in road networks. In Experimental Algorithms, pages 88--99. Springer, 2011.

Digital Library

[6]

D. Delling, A. V. Goldberg, T. Pajor, and R. F. Werneck. Customizable route planning. In Experimental Algorithms, pages 376--387. Springer, 2011.

Digital Library

[7]

D. Delling, M. Kobitzsch, and R. F. Werneck. Customizing driving directions with gpus. In Euro-Par 2014 Parallel Processing, pages 728--739. Springer, 2014.

[8]

D. Delling and R. F. Werneck. Faster customization of road networks. SEA, 13:30--42, 2013.

[9]

J. Dibbelt, B. Strasser, and D. Wagner. Customizable contraction hierarchies. In Experimental Algorithms - 13th International Symposium, SEA 2014, Copenhagen, Denmark, June 29 - July 1, 2014. Proceedings, pages 271--282, 2014.

Digital Library

[10]

J. Dibbelt, B. Strasser, and D. Wagner. Erratum: Customizable contraction hierarchies. In Experimental Algorithms - 13th International Symposium, SEA 2014, Copenhagen, Denmark, June 29 - July 1, 2014. Proceedings, 2014.

Digital Library

[11]

S. Funke, A. Nusser, and S. Storandt. On k-path covers and their applications. Proceedings of the VLDB Endowment, 7(10), 2014.

Digital Library

[12]

S. Funke and S. Storandt. Polynomial-time construction of contraction hierarchies for multi-criteria objectives. In Proceedings of the 15th Meeting on Algorithm Engineering and Experiments, ALENEX 2013, pages 41--54, 2013.

Digital Library

[13]

R. Geisberger, M. Kobitzsch, and P. Sanders. Route planning with flexible objective functions. In ALENEX'10, pages 124--137, 2010.

Digital Library

[14]

R. Geisberger, M. N. Rice, P. Sanders, and V. J. Tsotras. Route planning with flexible edge restrictions. J. Exp. Algorithmics, 17(1):1.2:1.1--1.2:1.20, Mar. 2012.

Digital Library

[15]

R. Geisberger, P. Sanders, D. Schultes, and C. Vetter. Exact routing in large road networks using contraction hierarchies. Transportation Science, 46(3):388--404, 2012.

Digital Library

[16]

A. V. Goldberg and C. Harrelson. Computing the shortest path: A search meets graph theory. In Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, SODA '05, pages 156--165, Philadelphia, PA, USA, 2005. Society for Industrial and Applied Mathematics.

Digital Library

[17]

The CGAL Project. CGAL User and Reference Manual. CGAL Editorial Board, 4.4 edition, 2014.

Cited By

Kurbanov TCuchý MVokřínek J(2023)Fast One-to-Many Multicriteria Shortest Path SearchIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2023.328206924:10(10410-10419)Online publication date: Oct-2023
https://doi.org/10.1109/TITS.2023.3282069
Gao LChen CChu FLiao CHuang HWang Y(2023)MOOP: An Efficient Utility-Rich Route Planning Framework Over Two-Fold Time-Dependent Road NetworksIEEE Transactions on Emerging Topics in Computational Intelligence10.1109/TETCI.2023.32419307:5(1554-1570)Online publication date: Oct-2023
https://doi.org/10.1109/TETCI.2023.3241930
Ju Svan Vliet PArenz OPeters J(2023)Digital Twin of a Driver-in-the-Loop Race Car Simulation With Contextual Reinforcement LearningIEEE Robotics and Automation Letters10.1109/LRA.2023.32796188:7(4107-4114)Online publication date: Jul-2023
https://doi.org/10.1109/LRA.2023.3279618
Show More Cited By

Index Terms

Personalized route planning in road networks

Recommendations

PARP: A Parallel Traffic Condition Driven Route Planning Model on Dynamic Road Networks
The problem of route planning on road network is essential to many Location-Based Services (LBSs). Road networks are dynamic in the sense that the weights of the edges in the corresponding graph constantly change over time, representing evolving traffic ...
Route Planning in Road Networks
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGSPATIAL '15: Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems

November 2015

646 pages

ISBN:9781450339674

DOI:10.1145/2820783

General Chairs:
Mohamed Ali
University of Washington, Tacoma
,
Yan Huang
University of North Texas
,
Program Chairs:
Michael Gertz
Heidelberg University, Germany
,
Matthias Renz
LMU Munich, Germany
,
Jagan Sankaranarayanan
NEC Labs

Copyright © 2015 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]

Sponsors

SIGSPATIAL: ACM Special Interest Group on Spatial Information

In-Cooperation

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 November 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SIGSPATIAL'15

Sponsor:

SIGSPATIAL

SIGSPATIAL'15: 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems

November 3 - 6, 2015

Washington, Seattle

Acceptance Rates

SIGSPATIAL '15 Paper Acceptance Rate 38 of 212 submissions, 18%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

22
Total Citations
View Citations
508
Total Downloads

Downloads (Last 12 months)63
Downloads (Last 6 weeks)6

Reflects downloads up to 16 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kurbanov TCuchý MVokřínek J(2023)Fast One-to-Many Multicriteria Shortest Path SearchIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2023.328206924:10(10410-10419)Online publication date: Oct-2023
https://doi.org/10.1109/TITS.2023.3282069
Gao LChen CChu FLiao CHuang HWang Y(2023)MOOP: An Efficient Utility-Rich Route Planning Framework Over Two-Fold Time-Dependent Road NetworksIEEE Transactions on Emerging Topics in Computational Intelligence10.1109/TETCI.2023.32419307:5(1554-1570)Online publication date: Oct-2023
https://doi.org/10.1109/TETCI.2023.3241930
Ju Svan Vliet PArenz OPeters J(2023)Digital Twin of a Driver-in-the-Loop Race Car Simulation With Contextual Reinforcement LearningIEEE Robotics and Automation Letters10.1109/LRA.2023.32796188:7(4107-4114)Online publication date: Jul-2023
https://doi.org/10.1109/LRA.2023.3279618
Fuest SShkedova OSester M(2023)Promoting favorable routes through visual communication: a design study for creating ‘Social’ route maps for the case of air pollutionInternational Journal of Cartography10.1080/23729333.2022.215978110:1(68-93)Online publication date: 15-Mar-2023
https://doi.org/10.1080/23729333.2022.2159781
Liu HLi YFu YMei HXiong H(2022)Polestar++: An Intelligent Routing Engine for National-Wide Public TransportationIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.3153711(1-1)Online publication date: 2022
https://doi.org/10.1109/TKDE.2022.3153711
Li PWang XGao HXu XIqbal MDahal K(2022)A Dynamic and Scalable User-Centric Route Planning Algorithm Based on Polychromatic Sets TheoryIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2021.308502623:3(2762-2772)Online publication date: Mar-2022
https://doi.org/10.1109/TITS.2021.3085026
Chen CGao LXie XWang Z(2022)Enjoy the most beautiful scene now: a memetic algorithm to solve two-fold time-dependent arc orienteering problemFrontiers of Computer Science: Selected Publications from Chinese Universities10.1007/s11704-019-8364-114:2(364-377)Online publication date: 11-Mar-2022
https://dl.acm.org/doi/10.1007/s11704-019-8364-1
Chen CGao LXie XFeng LWang Y(2021)2TD Path-Planner: Towards a More Realistic Path Planning System over Two-Fold Time-Dependent Road Networks [Application Notes]IEEE Computational Intelligence Magazine10.1109/MCI.2021.306187916:2(78-98)Online publication date: May-2021
https://doi.org/10.1109/MCI.2021.3061879
de Oliveira e Silva RCui GRahimi SWang X(2021)Personalized route recommendation through historical travel behavior analysisGeoInformatica10.1007/s10707-021-00453-y26:3(505-540)Online publication date: 10-Nov-2021
https://doi.org/10.1007/s10707-021-00453-y
Barth FFunke SJepsen TProissl C(2020)Scalable unsupervised multi-criteria trajectory segmentation and driving preference miningProceedings of the 9th ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data10.1145/3423336.3429348(1-10)Online publication date: 3-Nov-2020
https://dl.acm.org/doi/10.1145/3423336.3429348
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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents