User-Constrained Multimodal Route Planning
Authors:
Open Access
- 3 February 2015
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Journal of Experimental Algorithmics
- Vol. 19, 1-19
Abstract
In the multimodal route planning problem, we are given multiple transportation networks (e.g., pedestrian, road, public transit) and ask for a best integrated journey between two points. The main challenge is that a seemingly optimal journey may have changes between networks that do not reflect the user’s modal preferences. In fact, quickly computing reasonable multimodal routes remains a challenging problem: previous approaches either suffer from poor query performance or their available choices of modal preferences during query time is limited. In this work, we focus on computing exact multimodal journeys that can be restricted by specifying arbitrary modal sequences at query time. For example, a user can say whether he or she wants to only use public transit, prefers to also use a taxi or walking at the beginning or end of the journey, or has no restrictions at all. By carefully adapting node contraction, a common ingredient to many speedup techniques on road networks, we are able to compute point-to-point queries on a continental network combined of cars, railroads, and flights several orders of magnitude faster than Dijkstra’s algorithm. Thereby, we require little space overhead and obtain fast preprocessing times.Keywords
Funding Information
- DFG (WA 654/16-1)
- EU FP7/2007-2013 (DG INFSO.G4-ICT for Transport) (288094 (project eCOMPASS))
This publication has 24 references indexed in Scilit:
- Parallel computation of best connections in public transportation networksACM Journal of Experimental Algorithmics, 2012
- 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
- Efficient models for timetable information in public transportation systemsACM Journal of Experimental Algorithmics, 2008
- A Practical Shortest Path Algorithm with Linear Expected TimeSIAM Journal on Computing, 2008
- In Transit to Constant Time Shortest-Path Queries in Road Networks2007
- Geometric containers for efficient shortest-path computationACM Journal of Experimental Algorithmics, 2005
- Dijkstra's algorithm on-lineACM Journal of Experimental Algorithmics, 2000
- Formal-Language-Constrained Path ProblemsSIAM Journal on Computing, 2000
- Finding Regular Simple Paths in Graph DatabasesSIAM Journal on Computing, 1995