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

• 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

• 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

• 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

• 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 profile-query."
  http://www.ecompass-project.eu/sites/default/files/ECOMPASS-TR-021.pdf

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.

• Busby, Jeffrey R. “Accessibility-Based Transit Planning”. MA thesis. Massachusetts Institute of Technology, 2004. Web. [http://dspace.mit.edu/handle/1721.1/32414]

• Lei, T. L. and R. L. Church. “Mapping transit-based access: integrating GIS, routes and schedules.” International Journal of Geographical Information Science 24.2 (2010): 283–304. Web. [http://www.tandfonline.com/doi/pdf/10.1080/13658810902835404].

• McGurrin, Greczner. Performance Metrics: Calculating Accessibility Using Open Source Software and Open Data. (2010). Web. [http://amonline.trb.org/12jj6e/12jj6e/1] An approach for calculating accessibility via both transit and automobiles is presented. OTP is used for the transit portion.

• Tomer, Kneebone, Puentes, and Berube. Missed Opportunity: Transit and Jobs in Metropolitan America. (2011)
  Large-scale comparative public transit accessibility study.
  [http://www.brookings.edu/reports/2011/0512_jobs_and_transit.aspx]

• Huang, Ruihong. "Bridging GTFS and GIS for Computing Transit Level of Service," Association of American Geographers Annual Meeting. (2011)
  Presents data models and techniques to bridge GTFS data and GIS data and facilitate computation of various transit system level of service (TLOS) indicators for U.S. metropolitan areas.
  [http://meridian.aag.org/callforpapers/program/AbstractDetail.cfm?AbstractID=39742]

• Trozzi, Hosseinloo, Gentile2, and Bell. Dynamic Hyperpaths: The Stop Model. (2009)
  paper 1
  paper 2
  Effective frequencies of multiple frequency-based routes operating over common trunks. The passenger's position should be modeled as a superposition of positions along the various lines. Some work must be done here to present reasonable trips.