Route Planning in Transportation Networks

By Hannah Bast, Daniel Delling, Andrew Vladislav Goldberg, Matthias Müller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, Renato F. Werneck. 2015

783 citations recorded by the source corpus.

We survey recent advances in algorithms for route planning in transportation networks. For road networks, we show that one can compute driving directions in milliseconds or less even at continental scale. A variety of techniques provide different trade-offs between preprocessing effort, space requirements, and query time. Some algorithms can answer queries in a fraction of a microsecond, while others can deal efficiently with real-time traffic. Journey planning on public transportation systems, although conceptually similar, is a significantly harder problem due to its inherent time-dependent and multicriteria nature. Although exact algorithms are fast enough for interactive queries on metropolitan transit systems, dealing with continent-sized instances requires simplifications or heavy preprocessing. The multimodal route planning problem, which seeks journeys combining schedule-based transportation (buses, trains) with unrestricted modes (walking, driving), is even harder, relying on approximate solutions even for metropolitan inputs.

Subfields: Geography, Planning and Development, Transportation, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Geography, Planning and Development

1. Luc Van Gool
2. Dengxin Dai
3. Simon Hecker

In Transportation

1. Ekim Yurtsever
2. Adrian Weller
3. Kazuya Takeda
4. Alexander Carballo
5. Szilárd Aradi
6. Jacob Lambert

In Signal Processing

1. Adrian Weller
2. Baofu Wu
3. Luc Van Gool
4. Kazuya Takeda
5. Roberto Cipolla
6. Dengxin Dai
7. Alexander Carballo
8. Sidi Lu

Citations in the corpus

• A Survey of Autonomous Driving: Common Practices and Emerging Technologies (2019, methodology): “HL is the fastest query time algorithm for route planning [244], in the expense of high storage usage.”
• A Survey of Motion Planning and Control Techniques for Self-Driving Urban Vehicles (2016, neutral): “4”
• Concrete Problems for Autonomous Vehicle Safety: Advantages of Bayesian Deep Learning (2017, background): “Several algorithms exist that are more suited to large networks than A* [Bast et al., 2016].”
• Survey of Deep Reinforcement Learning for Motion Planning of Autonomous Vehicles (2020, background): “A comprehensive study on the subject can be found in [4].”
• End-to-End Learning of Driving Models with Surround-View Cameras and Route Planners (2018, background): “Route planning has been extensively studied as well [52,53,54,55,56], mainly to compute the fastest, most fuel-efficient, or a customized trajectory to the destination through a road network.”
• Computing Systems for Autonomous Driving: State of the Art and Challenges (2020, background): “GPS navigation systems are known as global planners [135] to plan a feasible global route, but it does not guarantee safety.”
• Self-Driving Cars: A Survey (2019, methodology): “[BAS15] evaluated experimentally many of the”