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.

Currently, OTP 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. Currently 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) but will need to do some optimizations and check performance.

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

Analysis Bibliography

This is a list of articles about non-passenger-facing applications of multi-modal routing engines (including OTP) in urban planning, public policy, economics, geography etc.