Julian Dibbelt
Skip Abstract Section
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.
- Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck. 2011. A hub-based labeling algorithm for shortest paths on road networks. In Proceedings of the 10th International Symposium on Experimental Algorithms (SEA’11) Lecture Notes in Computer Science, Vol. 6630. Springer, 230--241. Google Scholar
Digital Library
- Ittai Abraham, Amos Fiat, Andrew V. Goldberg, and Renato F. Werneck. 2010. Highway dimension, shortest paths, and provably efficient algorithms. In Proceedings of the 21st Annual ACM--SIAM Symposium on Discrete Algorithms (SODA’10). SIAM, 782--793. Google ScholarDigital Library
- Chris Barrett, Keith Bisset, Martin Holzer, Goran Konjevod, Madhav V. Marathe, and Dorothea Wagner. 2009. Engineering label-constrained shortest-path algorithms. In The Shortest Path Problem: Ninth DIMACS Implementation Challenge. DIMACS Book, Vol. 74. American Mathematical Society, 309--319.Google ScholarCross Ref
- Chris Barrett, Riko Jacob, and Madhav V. Marathe. 2000. Formal-language-constrained path problems. SIAM J. Comput. 30, 3 (2000), 809--837. Google ScholarDigital Library
- Hannah Bast. 2009. Car or public transport -- two worlds. In Efficient Algorithms. Lecture Notes in Computer Science, Vol. 5760. Springer, 355--367. Google ScholarDigital Library
- Hannah Bast, Erik Carlsson, Arno Eigenwillig, Robert Geisberger, Chris Harrelson, Veselin Raychev, and Fabien Viger. 2010. Fast routing in very large public transportation networks using transfer patterns. In Proceedings of the 18th Annual European Symposium on Algorithms (ESA’10) Lecture Notes in Computer Science, Vol. 6346. Springer, 290--301. Google ScholarDigital Library
- Holger Bast, Stefan Funke, Domagoj Matijevic, Peter Sanders, and Dominik Schultes. 2007. In transit to constant shortest-path queries in road networks. In Proceedings of the 9th Workshop on Algorithm Engineering and Experiments (ALENEX’07). SIAM, 46--59.Google ScholarCross Ref
- Gernot Veit Batz, Robert Geisberger, Sabine Neubauer, and Peter Sanders. 2010. Time-dependent contraction hierarchies and approximation. In Proceedings of the 9th International Symposium on Experimental Algorithms (SEA’10) Lecture Notes in Computer Science, Vol. 6049. Springer, 166--177. http://www.springerlink.com/content/u787292691813526/. Google ScholarDigital Library
- Reinhard Bauer, Daniel Delling, Peter Sanders, Dennis Schieferdecker, Dominik Schultes, and Dorothea Wagner. 2010. Combining hierarchical and goal-directed speed-up techniques for Dijkstra’s algorithm. ACM J. Exper. Algorithmics 15, 2.3 (January 2010), 1--31. Special Section devoted to WEA’08. Google ScholarDigital Library
- Annabell Berger, Daniel Delling, Andreas Gebhardt, and Matthias Müller--Hannemann. 2009. Accelerating time-dependent multi-criteria timetable information is harder than expected. In Proceedings of the 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS’09) (OpenAccess Series in Informatics (OASIcs)).Google Scholar
- Daniel Delling. 2009. Engineering and Augmenting Route Planning Algorithms. Ph.D. Dissertation. Universität Karlsruhe (TH), Fakultät für Informatik.Google Scholar
- Daniel Delling, Andrew V. Goldberg, Andreas Nowatzyk, and Renato F. Werneck. 2011a. PHAST: Hardware-accelerated shortest path trees. In Proceedings of the 25th International Parallel and Distributed Processing Symposium (IPDPS’11). IEEE Computer Society, 921--931. Google ScholarDigital Library
- Daniel Delling, Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck. 2011b. Customizable route planning. In Proceedings of the 10th International Symposium on Experimental Algorithms (SEA’11) (Lecture Notes in Computer Science), Vol. 6630. Springer, 376--387. Google ScholarDigital Library
- Daniel Delling, Martin Holzer, Kirill Müller, Frank Schulz, and Dorothea Wagner. 2009a. High-performance multi-level routing. In The Shortest Path Problem: 9th DIMACS Implementation Challenge. DIMACS Book, Vol. 74. American Mathematical Society, 73--92.Google ScholarCross Ref
- Daniel Delling, Bastian Katz, and Thomas Pajor. 2012. Parallel computation of best connections in public transportation networks. ACM J. Exper. Algorithmics 17, 4 (July 2012), 4.1--4.26. Google ScholarDigital Library
- Daniel Delling and Giacomo Nannicini. 2008. Bidirectional core-based routing in dynamic time-dependent road networks. In Proceedings of the 19th International Symposium on Algorithms and Computation (ISAAC’08) (Lecture Notes in Computer Science), Vol. 5369. Springer, 813--824. Google ScholarDigital Library
- Daniel Delling, Thomas Pajor, and Dorothea Wagner. 2009b. Accelerating multi-modal route planning by access-nodes. In Proceedings of the 17th Annual European Symposium on Algorithms (ESA’09) (Lecture Notes in Computer Science), Vol. 5757. Springer, 587--598.Google ScholarCross Ref
- Daniel Delling, Thomas Pajor, Dorothea Wagner, and Christos Zaroliagis. 2009c. Efficient route planning in flight networks. In Proceedings of the 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS’09) (OpenAccess Series in Informatics (OASIcs)).Google Scholar
- Daniel Delling, Peter Sanders, Dominik Schultes, and Dorothea Wagner. 2009d. Engineering route planning algorithms. In Algorithmics of Large and Complex Networks. Lecture Notes in Computer Science, Vol. 5515. Springer, 117--139. Google ScholarDigital Library
- Robert Geisberger. 2010. Contraction of timetable networks with realistic transfers. In Proceedings of the 9th International Symposium on Experimental Algorithms (SEA’10) (Lecture Notes in Computer Science), Vol. 6049. Springer, 71--82. Google ScholarDigital Library
- Robert Geisberger, Moritz Kobitzsch, and Peter Sanders. 2010. Route planning with flexible objective functions. In Proceedings of the 12th Workshop on Algorithm Engineering and Experiments (ALENEX’10). SIAM, 124--137.Google ScholarCross Ref
- Robert Geisberger, Peter Sanders, Dominik Schultes, and Daniel Delling. 2008. Contraction hierarchies: Faster and simpler hierarchical routing in road networks. In Proceedings of the 7th Workshop on Experimental Algorithms (WEA’08) (Lecture Notes in Computer Science), Vol. 5038. Springer, 319--333. Google ScholarDigital Library
- General Transit Feed. 2010. https://developers.google.com/transit/gtfs/. (2010).Google Scholar
- Andrew V. Goldberg. 2008. A practical shortest path algorithm with linear expected time. SIAM J. Comput. 37 (2008), 1637--1655. Google ScholarDigital Library
- Andrew V. Goldberg and Chris Harrelson. 2005. Computing the shortest path: A* search meets graph theory. In Proceedings of the 16th Annual ACM--SIAM Symposium on Discrete Algorithms (SODA’05). SIAM, 156--165. Google ScholarDigital Library
- Ronald J. Gutman. 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.Google Scholar
- HaCon - Ingenieurgesellschaft mbH. 1984. http://www.hacon.de. (1984).Google Scholar
- Peter E. Hart, Nils Nilsson, and Bertram Raphael. 1968. A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern. 4 (1968), 100--107.Google ScholarCross Ref
- Martin Holzer, Frank Schulz, and Dorothea Wagner. 2008. Engineering multilevel overlay graphs for shortest-path queries. ACM J. Exper. Algorithmics 13, 2.5 (December 2008), 1--26. Google ScholarDigital Library
- Dominik Kirchler, Leo Liberti, and Roberto Wolfler Calvo. 2012. A label correcting algorithm for the shortest path problem on a multi-modal route network. In Proceedings of the 11th International Symposium on Experimental Algorithms (SEA’12) (Lecture Notes in Computer Science), Vol. 7276. Springer. Google ScholarDigital Library
- Dominik Kirchler, Leo Liberti, Thomas Pajor, and Roberto Wolfler Calvo. 2011. UniALT for regular language constraint shortest paths on a multi-modal transportation network. In Proceedings of the 11th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS’11) (OpenAccess Series in Informatics (OASIcs)), Vol. 20. 64--75.Google Scholar
- Ulrich Lauther. 2004. An extremely fast, exact algorithm for finding shortest paths in static networks with geographical background. In Geoinformation und Mobilität - von der Forschung zur praktischen Anwendung. Vol. 22. IfGI prints, 219--230.Google Scholar
- Alberto O. Mendelzon and Peter T. Wood. 1995. Finding regular simple paths in graph databases. SIAM J. Comput. 24, 6 (1995), 1235--1258. Google ScholarDigital Library
- Metropolitan Transportation Authority of the State of New York. 1966. Retrieved from http://www.mta.info/.Google Scholar
- Thomas Pajor. 2009. Multi-Modal Route Planning. Master’s thesis. Universität Karlsruhe (TH). Retrieved from http://i11www.ira.uka.de/extra/publications/p-mmrp-09.pdf.Google Scholar
- PTV AG -- Planung Transport Verkehr. 1979. http://www.ptv.de. (1979).Google Scholar
- Evangelia Pyrga, Frank Schulz, Dorothea Wagner, and Christos Zaroliagis. 2008. Efficient models for timetable information in public transportation systems. ACM J. Exper. Algorithmics 12, 2.4 (2008), 1--39. Google ScholarDigital Library
- Michael Rice and Vassilis Tsotras. 2011. Graph indexing of road networks for shortest path queries with label restrictions. In Proceedings of the 37th International Conference on Very Large Databases (VLDB’11). 69--80. Google ScholarDigital Library
- Peter Sanders and Dominik Schultes. 2005. Highway hierarchies hasten exact shortest path queries. In Proceedings of the 13th Annual European Symposium on Algorithms (ESA’05) (Lecture Notes in Computer Science), Vol. 3669. Springer, 568--579. Google ScholarDigital Library
- Frank Schulz, Dorothea Wagner, and Karsten Weihe. 2000. Dijkstra’s algorithm on-line: An empirical case study from public railroad transport. ACM J. Exper. Algorithmics 5, 12 (2000), 1--23. Google ScholarDigital Library
- Dorothea Wagner, Thomas Willhalm, and Christos Zaroliagis. 2005. Geometric containers for efficient shortest-path computation. ACM J. Exper. Algorithmics 10, 1.3 (2005), 1--30. Google ScholarDigital Library
Index Terms
- User-Constrained Multimodal Route Planning
Recommendations
MultiModal Route Planning in Mobility as a Service
WI '19 Companion: IEEE/WIC/ACM International Conference on Web Intelligence - Companion VolumeMobility as a Service (MaaS) is a new approach for multimodal transportation in smart cities which refers to the seamless integration of various forms of transport services accessible through one single digital platform. In a MaaS environment there can ...
Anytime route planning with constrained devices
Urban mobility became a major challenge around the world, with frequent congestion and ever growing travel time. Albeit recent advances in the area of Intelligent Transportation Systems (ITS), it is still difficult to predict and manage the road ...
Multi-destination vehicular route planning with parking and traffic constraints
MobiQuitous '19: Proceedings of the 16th EAI International Conference on Mobile and Ubiquitous Systems: Computing, Networking and ServicesThis paper aims to provide an efficient solution for people in a city who drive their cars to visit several destinations, where they need to park for a while, but do not care about the visiting order. This instance of the multi-destination route ...
Comments