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.
http://research.microsoft.com/pubs/156567/raptor_alenex.pdf
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.
https://epubs.siam.org/doi/pdf/10.1137/1.9781611975499.5

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.
http://www.mpi-inf.mpg.de/~bast/papers/car_or_public_transport.pdf
Delling, Daniel. Engineering and augmenting route planning algorithms. (2009, dissertation)
Overview, including time-dependent and Pareto shortest paths.
http://i11www.ira.uka.de/extra/publications/d-earpa-09.pdf
Delling, Sanders, Schultes, and Wagner. Engineering Route-Planning Algorithms. (2009)
Overview.
http://i11www.ira.uka.de/extra/publications/dssw-erpa-09.pdf

Path Search Speedup Techniques

Delling and Wagner. Time-Dependent Route Planning. (2009)
Overview.
http://i11www.iti.uni-karlsruhe.de/extra/publications/dw-tdrp-09.pdf
Delling and Wagner. Landmark-Based Routing in Dynamic Graphs. (2008)
http://i11www.ira.uka.de/extra/publications/dw-lbrdg-07.pdf
Bauer, Delling, Sanders, Schultes, and Wagner. Combining Hierarchical and Goal-Directed Speed-Up Techniques for Dijkstra’s Algorithm. (2008)
http://algo2.iti.kit.edu/download/bdsssw-chgds-10.pdf
Bauer and Delling. SHARC: Fast and Robust Unidirectional Routing. (2009)
SH ortcuts + ARC flags. Can be combined with ALT.
http://www.siam.org/proceedings/alenex/2008/alx08_02bauerr.pdf
Delling, Daniel. Time-Dependent SHARC-Routing. (2008)
http://i11www.iti.uni-karlsruhe.de/extra/publications/d-tdsr-09.pdf
Goldberg, Kaplan, and Werneck. Reach for A∗: Efficient Point-to-Point Shortest Path Algorithms. (2005)
http://avglab.com/andrew/pub/msr-tr-2005-132.pdf

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
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.97.8780&rep=rep1&type=pdf
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.
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.160.4715&rep=rep1&type=pdf
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.
http://www-desir.lip6.fr/publications/pub_1052_1_ECAI08.pdf
Tung and Chew. A multicriteria Pareto-optimal path algorithm. (1992)
Delling and Wagner. Pareto Paths with SHARC. (2009)
http://i11www.iti.uni-karlsruhe.de/extra/publications/dw-pps-09.pdf

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)
http://scidok.sulb.uni-saarland.de/volltexte/2004/251/pdf/MarkZiegelmann_ProfDrKurtMehlhorn.pdf

Contraction and Transfer Patterns

Geisberger, Robert. Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks. (2008, dissertation)
http://algo2.iti.kit.edu/documents/routeplanning/geisberger_dipl.pdf
Geisberger, Robert. Contraction of Timetable Networks with Realistic Tranfers (2010)
Introduces the "Station Model Graph".
http://algo2.iti.kit.edu/download/time_table_ch.pdf
Bast, Carlsson, Eigenwillig, Geisberger Harrelson, Raychev, and Viger. Fast Routing in Very Large Public Transportation Networks Using Transfer Patterns. (2010)
http://ad.informatik.uni-freiburg.de/files/transferpatterns.pdf/at_download/file

Timetable-based routing

Schulz, Frank. Timetable Information and Shortest Paths. (2005, dissertation)
Excellent reference.
http://d-nb.info/1001586921/34

ALT and Metric Embeddings

Goldberg and Werneck. Computing Point-to-Point Shortest Paths from External Memory. (2005)
Introduced the ALT algorithm.
http://www.cs.princeton.edu/courses/archive/spring06/cos423/Handouts/GW05.pdf
Linial, London, and Rabinovich. The Geometry of Graphs and Some of its Algorithmic Applications. (1995)
http://pdf.aminer.org/000/798/423/the_geometry_of_graphs_and_some_of_its_algorithmic_applications.pdf
Hjaltason and Samet. Contractive Embedding Methods for Similarity Searching in Metric Spaces. (2000)
http://www.cs.umd.edu/~hjs/pubs/metricpruning.pdf
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.
http://dcommon.bu.edu/xmlui/bitstream/handle/2144/1727/2009-004-shortest-distance-estimation.pdf

Calibration and Implementation Details

Wardman, Mark. Public Transport Values of Time. (2004)
http://eprints.whiterose.ac.uk/2062/1/ITS37_WP564_uploadable.pdf
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.
http://www.cs.utexas.edu/users/shaikat/papers/TR-07-54.pdf

Post-Dijkstra Public Transit Routing

Dibbelt, Pajor, Strasser, Wagner. Intriguingly Simple and Fast Transit Routing (2013).
Introduces the Connection Scan Algorithm (CSA).
http://www.ecompass-project.eu/sites/default/files/ECOMPASS-TR-021.pdf
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 proﬁle-query."
http://www.ecompass-project.eu/sites/default/files/ECOMPASS-TR-021.pdf