RoutingBibliography

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* algorithm with a Euclidean heuristic or contraction hierarchies. Walk+Transit or Bike+Transit trips are planned using a variant of the NAMOA* algorithm with the Tung-Chew (aggregate weight lower bound graph) heuristic for queue ordering. The alternate "weight table" heuristic is equivalent to a partially precomputed Tung-Chew heuristic with a table of shortcuts through the transit network. Core contraction hierarchies are also an option if edge weights are non-variable, but the recent addition of user-specified (bike) routing options interferes with contraction.

Please feel free to add references or summaries!

Path Search Speedup Techniques

• Delling, Daniel. Engineering and augmenting route planning algorithms. (2009, dissertation)
  Overview, including time-dependent and Pareto shortest paths.

• Delling, Sanders, Schultes, and Wagner. Engineering Route-Planning Algorithms. (2009)
  Overview.

• Delling and Wagner. Time-Dependent Route Planning. (2009)
  Overview.

• Delling and Wagner. Landmark-Based Routing in Dynamic Graphs. (2008)

• Bauer, Delling, Sanders, Schultes, and Wagner. Combining Hierarchical and Goal-Directed Speed-Up Techniques for Dijkstra’s Algorithm. (2008)

• Bauer and Delling. SHARC: Fast and Robust Unidirectional Routing. (2009)
  SH ortcuts + ARC flags. Can be combined with ALT.

• Delling, Daniel. Time-Dependent SHARC-Routing. (2008)

Multi-objective Pareto Shortest Paths

• Das and Dennis. Drawbacks of minimizing weighted sums of objectives for Pareto set generation in multicriteria optimization problems. (1997)

• Müller-Hannemann and Schnee. Finding All Attractive Train Connections by Multi-criteria Pareto Search. (2007)
  Deutsche Bahn information system. Does not account for on-street travel.

• Mandow & Pérez de la Cruz. A New Approach to Multiobjective A* Search. (2005)
  NAMOA*

• Mandow & Pérez de la Cruz. Multiobjective A* search with consistent heuristics. (2008)
  NAMOA*

• Machuca, Mandow and Pérez de la Cruz. Evaluation of Heuristic Functions for Bicriterion Shortest Path Problems. (2009)
  Evaluates heuristics from Tung & Chew (1992) versus lexicographical ordering of priority queue.

• Tung and Chew. A multicriteria Pareto-optimal path algorithm. (1992)

• Delling and Wagner. Pareto Paths with SHARC. (2009)

Resource-constrained Routing

• Dumitrescu & Boland. Improved Preprocessing, Labeling and Scaling Algorithms for the Weight-Constrained Shortest Path Problem. (2003)
  Comparison of scaling and label-setting methods.

• Ziegelmann, Mark. Constrained Shortest Paths and Related Problems. (2001, dissertation)

Contraction and Transfer Patterns

• Geisberger, Robert. Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks. (2008, dissertation)

• Geisberger, Robert. Contraction of Timetable Networks with Realistic Tranfers (2010)
  Introduces the "Station Model Graph".

• Bast, Carlsson, Eigenwillig, Geisberger Harrelson, Raychev, and Viger. Fast Routing in Very Large Public Transportation Networks Using Transfer Patterns. (2010)

Timetable-based routing

• Schulz, Frank. Timetable Information and Shortest Paths. (2005, dissertation)
  Excellent reference.

ALT and Metric Embeddings

• Goldberg and Werneck. Computing Point-to-Point Shortest Paths from External Memory. (2005)
  Introduced the ALT algorithm.

• Linial, London, and Rabinovich. The Geometry of Graphs and Some of its Algorithmic Applications. (1995)

• Hjaltason and Samet. Contractive Embedding Methods for Similarity Searching in Metric Spaces. (2000)

• Potamias, Bonchi, Castillo, and Gionis. Fast Shortest Path Distance Estimation in Large Networks. (2009)
  Briefly discusses the connection between landmark routing and more general research on metric embeddings.

Calibration and Implementation Details

• Wardman, Mark. Public Transport Values of Time. (2004)

• Chen, Chowdhury, Roche, Ramachandran, Tong. Priority Queues and Dijkstra’s Algorithm.
  Summary: Despite better theoretical complexity for Fibonacci heaps, it is often as good or better to use a binary heap as a priority queue when doing path searches.