Routing Bibliography

This is a list of articles, dissertations, and books that have inspired and informed both the existing OTP routing engine and some ongoing experiments.

OTP1 uses a single time-dependent (as opposed to time-expanded) graph that contains both street and transit networks. Walk-only and bicycle-only trips are generally planned using the A-star algorithm with a Euclidean heuristic. Walk+Transit or Bike+Transit trips are planned using A-star with the Tung-Chew heuristic (i.e. a graph grown backward from the destination providing a lower bound on aggregate weight) for queue ordering. For speed reasons we are performing single-variable generalized cost optimization, which is not ideal. We should be performing Pareto optimization on at least two variables (generalized cost and time).

OTP2 splits the search into three segments: access from the origin to transit stops, egress from transit stops to the destination, and transit service connecting the two. For the transit segment, OTP2 uses the Multi-criteria Range Raptor algorithm. For the access and egress searches it uses the same approach as OTP1. Both splitting the search into three parts and use of a table-scanning algorithm like Raptor improve OTP2's performance significantly while increasing result quality by producing true Pareto-optimal sets of results.

Algorithms used in OTP2 but not OTP1

Techniques used in or influencing OTP1 and OTP2

General Background

Path Search Speedup Techniques

Multi-objective Pareto Shortest Paths

Resource-constrained Routing

Contraction and Transfer Patterns

Timetable-based routing

ALT and Metric Embeddings

Calibration and Implementation Details

Post-Dijkstra Public Transit Routing