chapter

Car or Public Transport--Two Worlds

Author:

Hannah BastAuthors Info & Claims

Efficient Algorithms: Essays Dedicated to Kurt Mehlhorn on the Occasion of His 60th Birthday

September 2009

Pages 355 - 367

https://doi.org/10.1007/978-3-642-03456-5_24

Published: 01 September 2009 Publication History

Abstract

There are two kinds of people: those who travel by car, and those who use public transport. The topic of this article is to show that the algorithmic problem of computing the fastest way to get from A to B is also surprisingly different on road networks than on public transportation networks.

On road networks, even very large ones like that of the whole of Western Europe, the shortest path from a given source to a given target can be computed in just a few microseconds. Lots of interesting speed-up techniques have been developed to this end, and we will give an overview over the most important ones.

Public transportation networks can be modeled as graphs just like road networks, and most algorithms designed for road networks can be applied for public transportation networks as well. They just happen to perform not nearly as well, and to date we do not know how to route similarly fast on large public transportation networks as we can on large road networks.

The reasons for this are interesting and non-obvious, and it took us a long time to fully comprehend them. Once understood, they are relatively easy to explain, however, and that is what we want to do in this article. Oh, and by the way, happy birthday, Kurt!

Cited By

View all

Lin FHsieh H(2023)Exploiting Network Structure in Multi-criteria Distributed and Competitive Stationary-resource SearchingACM Transactions on Spatial Algorithms and Systems10.1145/35699379:4(1-33)Online publication date: 31-Dec-2023
https://dl.acm.org/doi/10.1145/3569937
Falek APelsser CJulien STheoleyre F(2022)MUSETransportation Science10.1287/trsc.2021.110456:2(436-459)Online publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1287/trsc.2021.1104
Lin FHsieh H(2022)Traveling Transporter Problem: Arranging a New Circular Route in a Public Transportation System Based on Heterogeneous Non-Monotonic Urban DataACM Transactions on Intelligent Systems and Technology10.1145/351003413:3(1-25)Online publication date: 3-Mar-2022
https://dl.acm.org/doi/10.1145/3510034
Show More Cited By

Recommendations

Do You Want Your Autonomous Car To Drive Like You?
HRI '17: Proceedings of the 2017 ACM/IEEE International Conference on Human-Robot Interaction

With progress in enabling autonomous cars to drive safely on the road, it is time to start asking how they should be driving. A common answer is that they should be adopting their users' driving style. This makes the assumption that users want their ...
Virtual Worlds: Virtual worlds, real exploits

As the popularity of virtual reality worlds grows, their potential security vulnerabilities are coming under increasing scrutiny. You are walking along a vast landscape littered occasionally with billboards, houses, and other small buildings. You hear ...
Operations Research in a Public Corporation

I am sure you have all heard quite a good deal about operations research in the military, in business, and in industry, and perhaps some about operations research in government. Tonight I would like to take a look at operations research in a somewhat ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Efficient Algorithms: Essays Dedicated to Kurt Mehlhorn on the Occasion of His 60th Birthday

September 2009

424 pages

ISBN:9783642034558

Editors:
Susanne Albers
Institut für Informatik, Universität Freiburg, Freiburg, Germany 79110
,
Helmut Alt
Institut für Informatik, Freie Universität Berlin, Berlin, Germany 14195
,
Stefan Näher
Fachbereich IV - Informatik, Universität Trier, Trier, Germany 54286

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 September 2009

Qualifiers

Chapter

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 26 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Lin FHsieh H(2023)Exploiting Network Structure in Multi-criteria Distributed and Competitive Stationary-resource SearchingACM Transactions on Spatial Algorithms and Systems10.1145/35699379:4(1-33)Online publication date: 31-Dec-2023
https://dl.acm.org/doi/10.1145/3569937
Falek APelsser CJulien STheoleyre F(2022)MUSETransportation Science10.1287/trsc.2021.110456:2(436-459)Online publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1287/trsc.2021.1104
Lin FHsieh H(2022)Traveling Transporter Problem: Arranging a New Circular Route in a Public Transportation System Based on Heterogeneous Non-Monotonic Urban DataACM Transactions on Intelligent Systems and Technology10.1145/351003413:3(1-25)Online publication date: 3-Mar-2022
https://dl.acm.org/doi/10.1145/3510034
Lin FHsieh H(2021)ConntransProceedings of the 29th International Conference on Advances in Geographic Information Systems10.1145/3474717.3483926(163-174)Online publication date: 2-Nov-2021
https://dl.acm.org/doi/10.1145/3474717.3483926
Lin FHsieh H(2021)A Joint Passenger Flow Inference and Path Recommender System for Deploying New Routes and Stations of Mass Transit TransportationACM Transactions on Knowledge Discovery from Data10.1145/345139316:1(1-36)Online publication date: 20-Jul-2021
https://dl.acm.org/doi/10.1145/3451393
Vo HMoshfeghi YOunis IMacdonald CJose JTriantafillou PLivingston MThakuriah P(2015)Enabling Smart Transit with Real-time Trip PlanningProceedings of the ACM First International Workshop on Understanding the City with Urban Informatics10.1145/2811271.2811272(13-18)Online publication date: 18-Oct-2015
https://dl.acm.org/doi/10.1145/2811271.2811272
Dibbelt JPajor TWagner D(2015)User-Constrained Multimodal Route PlanningACM Journal of Experimental Algorithmics10.1145/269988619(1-19)Online publication date: 3-Apr-2015
https://dl.acm.org/doi/10.1145/2699886
Sommer C(2014)Shortest-path queries in static networksACM Computing Surveys10.1145/253053146:4(1-31)Online publication date: 1-Mar-2014
https://dl.acm.org/doi/10.1145/2530531
Allulli LItaliano GSantaroni F(2014)Exploiting GPS Data in Public Transport Journey PlannersProceedings of the 13th International Symposium on Experimental Algorithms - Volume 850410.1007/978-3-319-07959-2_25(295-306)Online publication date: 29-Jun-2014
https://dl.acm.org/doi/10.1007/978-3-319-07959-2_25
Cuong T(2013)CrowdRouteProceedings of the Second ACM SIGSPATIAL International Workshop on Crowdsourced and Volunteered Geographic Information10.1145/2534732.2534738(9-14)Online publication date: 5-Nov-2013
https://dl.acm.org/doi/10.1145/2534732.2534738
Show More Cited By

View Options

View options

Login options

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

Abstract

Cited By

Recommendations

Do You Want Your Autonomous Car To Drive Like You?

Virtual Worlds: Virtual worlds, real exploits

Operations Research in a Public Corporation

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations