Part of the book series:Lecture Notes in Computer Science ((LNTCS,volume 7933))
Included in the following conference series:
2905Accesses
Abstract
We study the problem of finding multimodal journeys in transportation networks, including unrestricted walking, driving, cycling, and schedule-based public transportation. A natural solution to this problem is to use multicriteria search, but it tends to be slow and to produce too many journeys, several of which are of little value. We propose algorithms to compute a full Pareto set and then score the solutions in a postprocessing step using techniques from fuzzy logic, quickly identifying the most significant journeys. We also propose several (still multicriteria) heuristics to find similar journeys much faster, making the approach practical even for large metropolitan areas.
Partial support by DFG grant WA654/16-1 and EU grant 288094 (eCOMPASS).
This is a preview of subscription content,log in via an institution to check access.
Access this chapter
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 5719
- Price includes VAT (Japan)
- Softcover Book
- JPY 7149
- Price includes VAT (Japan)
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Barrett, C., Bisset, K., Holzer, M., Konjevod, G., Marathe, M.V., Wagner, D.: Engineering Label-Constrained Shortest-Path Algorithms. In: The Shortest Path Problem: 9th DIMACS Impl. Challenge. DIMACS, vol. 74, pp. 309–319. AMS (2009)
Bast, H.: Car or Public Transport – Two Worlds. In: Albers, S., Alt, H., Näher, S. (eds.) Efficient Algorithms. LNCS, vol. 5760, pp. 355–367. Springer, Heidelberg (2009)
Bast, H.: Next-Generation Route Planning: Multi-Modal, Real-Time, Personalized (2012) Talk given at ISMP
Bast, H., Carlsson, E., Eigenwillig, A., Geisberger, R., Harrelson, C., Raychev, V., Viger, F.: Fast Routing in Very Large Public Transportation Networks using Transfer Patterns. In: de Berg, M., Meyer, U. (eds.) ESA 2010, Part I. LNCS, vol. 6346, pp. 290–301. Springer, Heidelberg (2010)
Bauer, R., Delling, D., Wagner, D.: Experimental Study on Speed-Up Techniques for Timetable Information Systems. Networks 57(1), 38–52 (2011)
Bielli, M., Boulmakoul, A., Mouncif, H.: Object modeling and path computation for multimodal travel systems. EJOR 175(3), 1705–1730 (2006)
Corne, D., Deb, K., Fleming, P., Knowles, J.: The Good of the Many Outweighs the Good of the One: Evolutionary Multi-Objective Optimization. Connections 1(1), 9–13 (2003)
Delling, D., Dibbelt, J., Pajor, T., Wagner, D., Werneck, R.F.: Computing and Evaluating Multimodal Journeys. Technical Report 2012-20, Faculty of Informatics, Karlsruhe Institute of Technology (2012)
Delling, D., Goldberg, A.V., Pajor, T., Werneck, R.F.: Customizable Route Planning. In: Pardalos, P.M., Rebennack, S. (eds.) SEA 2011. LNCS, vol. 6630, pp. 376–387. Springer, Heidelberg (2011)
Delling, D., Pajor, T., Werneck, R.F.: Round-Based Public Transit Routing. In: ALENEX, pp. 130–140. SIAM (2012)
Delling, D., Sanders, P., Schultes, D., Wagner, D.: Engineering Route Planning Algorithms. In: Lerner, J., Wagner, D., Zweig, K.A. (eds.) Algorithmics. LNCS, vol. 5515, pp. 117–139. Springer, Heidelberg (2009)
Dibbelt, J., Pajor, T., Wagner, D.: User-Constrained Multi-Modal Route Planning. In: ALENEX, pp. 118–129. SIAM (2012)
Dijkstra, E.W.: A Note on Two Problems in Connexion with Graphs. Numerische Mathematik 1, 269–271 (1959)
Disser, Y., Müller–Hannemann, M., Schnee, M.: Multi-Criteria Shortest Paths in Time-Dependent Train Networks. In: McGeoch, C.C. (ed.) WEA 2008. LNCS, vol. 5038, pp. 347–361. Springer, Heidelberg (2008)
Ensor, A., Lillo, F.: Partial order approach to compute shortest paths in multimodal networks. Technical report (2011),http://arxiv.org/abs/1112.3366v1
Farina, M., Amato, P.: A Fuzzy Definition of “Optimality” for Many-Criteria Optimization Problems. IEEE Tr. Syst., Man, and Cyb. A 34(3), 315–326 (2004)
Geisberger, R., Sanders, P., Schultes, D., Vetter, C.: Exact Routing in Large Road Networks Using Contraction Hierarchies. Transp. Sci. 46(3), 388–404 (2012)
Müller-Hannemann, M., Schulz, F., Wagner, D., Zaroliagis, C.: Timetable Information: Models and Algorithms. In: Geraets, F., Kroon, L.G., Schoebel, A., Wagner, D., Zaroliagis, C.D. (eds.) Railway Optimization 2004. LNCS, vol. 4359, pp. 67–90. Springer, Heidelberg (2007)
Modesti, P., Sciomachen, A.: A Utility Measure for Finding Multiobjective Shortest Paths in Urban Multimodal Transportation Networks. EJOR 111(3), 495–508 (1998)
Zadeh, L.A.: Fuzzy Logic. IEEE Computer 21(4), 83–93 (1988)
Author information
Authors and Affiliations
Microsoft Research Silicon Valley, Mountain View, CA, 94043, USA
Daniel Delling & Renato F. Werneck
Karlsruhe Institute of Technology (KIT), 76128, Karlsruhe, Germany
Julian Dibbelt, Thomas Pajor & Dorothea Wagner
- Daniel Delling
You can also search for this author inPubMed Google Scholar
- Julian Dibbelt
You can also search for this author inPubMed Google Scholar
- Thomas Pajor
You can also search for this author inPubMed Google Scholar
- Dorothea Wagner
You can also search for this author inPubMed Google Scholar
- Renato F. Werneck
You can also search for this author inPubMed Google Scholar
Editor information
Editors and Affiliations
Institute for Systems Analysis and Computer Science (IASI), National Research Council (CNR), Viale Manzoni 30, 00185, Rome, Italy
Vincenzo Bonifaci
Department of Computer and Systems Science, Sapienza University of Rome, Via Ariosto 25, 00185, Rome, Italy
Camil Demetrescu & Alberto Marchetti-Spaccamela &
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Delling, D., Dibbelt, J., Pajor, T., Wagner, D., Werneck, R.F. (2013). Computing Multimodal Journeys in Practice. In: Bonifaci, V., Demetrescu, C., Marchetti-Spaccamela, A. (eds) Experimental Algorithms. SEA 2013. Lecture Notes in Computer Science, vol 7933. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38527-8_24
Download citation
Publisher Name:Springer, Berlin, Heidelberg
Print ISBN:978-3-642-38526-1
Online ISBN:978-3-642-38527-8
eBook Packages:Computer ScienceComputer Science (R0)
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative