Route planning in transportation networks – Bast et al.
Yesterday we looked at the CS problems behind startups using mobile workforces to build variations on the pick-up and delivery problem. Today I thought it would be fun to look at a related problem – journey planning. What’s the tech behind city navigation and journey planning apps?
Today’s choice is the exactly the kind of paper you would be delighted to find if you wanted to build such an app. An up-to-date (Jan 2014) comprehensive survey of algorithms and approaches, with details of space-time trade-offs and real world results.
The ultimate validation of several of the approaches described here is that they have found their way into systems that serve millions of users every day. Several authors of papers cited in this survey have worked in routing-related problems for companies like Apple, Esri, Google, MapBox, Microsoft, Nokia, PTV, TeleNav, TomTom, and Yandex.
So what’s the current state-of-the-art?
For road planning, one can compute driving directions in milliseconds or less even at continental scale. Journey planning on public transport systems, even though conceptually similar, is a significantly harder problem due to its inherent time-dependent and multicriteria nature. The multimodel 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.
The most basic technique is Dijkstra’s algorithm, which proceeds by maintaining a priority queue of vertices ordered by (tentative) distances from the starting vertex. In each iteration it scans a new unvisited node and updates the (tentative) distances. You wouldn’t use Dijkstra’s algorithm at scale today since it is dominated by other approaches, but it’s good to know as it serves as the reference to which many other approaches are compared. If you want to know the shortest journey between A and B (and not all shortest paths from A), then you can speed things up by searching forwards from A to B, and backwards from B to A and stopping when you find a vertex in common.
Things can also be speed up by pre-processing (trading time for space). The ALT algorithm (A*, Landmarks and Triangles, where A* is an improved version of Dijkstra) picks a set of landmarks ahead of time and precomputes distances between them.
Arc flags partitions the graph into cells and keeps flags indicating whether arcs lie on the shortest path to some vertex in cell i.
Arc flags currently have the fastest query times among purely goal-directed methods on road networks.
Hierarchical technques exploit the inherent hierarchy of road networks. Sufficiently long shortest paths eventually converge to a small arterial network of important roads, such as highways. Contraction Hierarchies exploit this hierarchy by using shortcuts that can be used by long-distance queries to skip over ‘unimportant’ vertices. Combinations of the individual techniques can lead to speed-ups of one to two orders of magnitude over Dijkstra’s algorithm.
Extensions to the base problem (find the length of the shortest path) deal with actually retrieving what that path is (sounds pretty fundamental to me!), computing several paths at once, and dealing with dynamic networks (delays, road closures etc.). Other variations consider time-based extensions such as travel times on segments varying with time of day.
Adding in public transport makes things more complicated:
A key difference to road networks is that public transit networks are inherently time-dependent, since certain segments of the network can only be traversed at specific, discrete points in time.
One approach to this is to ‘unroll’ the timetable into a space-time graph with vertices for every event in the timetable, and arcs in the direction of timeflow. The resulting graphs can get very large though. The time-dependent model adds functions to arcs:
…time dependencies are encoded by travel-time functions on the arcs, which map departure times to travel times.
As we all know from first-hand experience, trains, buses and other means of transport are often subject to delays in the real world. So relying on the timetable alone may not be sufficient for good results. Fermani et al. studied public transport in Rome and
…provide strong evidence that computing journeys according to the published timetable often fails to deliver optimal or even high-quality solutions.
You can add in real-time updates and/or stochastic information to make models more accurate.
The multi-model (public transport mixed with driving, walking etc.) problem is harder again! Algorithms must not only consider each mode of transport in isolation, but also optimize the choice and sequence of transportation modes in some integrated way.
A general approach to obtain a multimodal network is to first build an individual graph for each transportation mode, and then merge them into a single multimodal graph with link arcs added to enable modal transfers.
In their paper summary, the authors say:
These recent successes [in journey planning] do not mean that all problems in this area are solved. The ultimate goal, a worldwide multimodel journey planner, has not yet been reached… such a system must take into account real-time traffic and transit information, historic patterns, schedule constraints, and monetary costs. Moreover, all these elements should be combined in a personalized manner. Solving such a general problem efficiently seems beyond the reach of current algorithms. Given the recent pace of progress however, a solution may be closer than expected.
See the paper (link at the top) for references to all the algorithms discussed, and much more detail than I could get into in this post.