-
Notifications
You must be signed in to change notification settings - Fork 3
RoutingBibliography
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 MOA* algorithm with epsilon-dominance for path pruning and the Tung-Chew heuristic (a graph providing a lower bound on aggregate weight) 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!
-
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 -
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
-
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
-
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
-
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
- Schulz, Frank. Timetable Information and Shortest Paths. (2005, dissertation)
Excellent reference.
http://d-nb.info/1001586921/34
-
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
-
Wardman, Mark. Public Transport Values of Time. (2004)
http://eprints.whiterose.ac.uk/2062/1/ITS37_WP564_uploadable.pdf -
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
- Delling, Pajor, Werneck. Round-Based Public Transit Routing (2012)
This is a completely different approach to routing in public transit networks that does not use a graph. It is much simpler, more flexible and can even be faster.
http://research.microsoft.com/pubs/156567/raptor_alenex.pdf