Skip to content

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

  • Delling, Pajor, Werneck. Round-Based Public Transit Routing (2012)
    This is a tabular approach to routing in public transit networks that does not use an ( explicit) graph. It is simpler and can outperform classic graph algorithms.

  • Delling, Dibbelt, and Pajor. Fast and Exact Public Transit Routing with Restricted Pareto Sets ( 2019)
    Describes the heuristic used in OTP2 to eliminate options early when they are known to become non-optimal before they reach the destination.

Techniques used in or influencing OTP1 and OTP2

General Background

  • Bast, Hannah. Car or public transport -- two worlds. (2009)
    Explains how car routing is different from schedule-based public transport routing.

  • 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)

Path Search Speedup Techniques

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

  • 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)

  • Goldberg, Kaplan, and Werneck. Reach for A∗: Efficient Point-to-Point Shortest Path Algorithms. (2005)

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)

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

  • 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.

  • Perny and Spanjaard. Near Admissible Algorithms for Multiobjective Search. (2009)
    Discusses relaxed Pareto dominance (Epsilon-dominance) and its use in Multi-objective A*. This a scheme for approximating the entire pareto-optimal solution set that allows time and space complexity polynomial in the number of nodes.

  • 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)

  • A.M. El-Geneidy, K.J. Krizek, M.J. Iacono. Predicting bicycle travel speeds along different facilities using GPS data: a proof of concept model. (2007)
    Proceedings of the 86th Annual Meeting of the Transportation Research Board, Compendium of Papers, TRB, Washington, D.C., USA ( CD-ROM)

  • 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.

Post-Dijkstra Public Transit Routing

  • Dibbelt, Pajor, Strasser, Wagner. Intriguingly Simple and Fast Transit Routing (2013).
    Introduces the Connection Scan Algorithm (CSA).

  • Delling, Katz, and Pajor. Parallel computation of best connections in public transportation networks (2012).
    "In this work, we present a novel algorithm for the one-to-all profile-search problem in public transportation networks. It answers the question for all fastest connections between a given station S and any other station at any time of the day in a single query... two interesting questions arise for time-dependent route planning: compute the best connection for a given departure time and the computation of all best connections during a given time interval (e. g., a whole day). The former is called a time-query, while the latter is called a profile-query."