Permalink
Switch branches/tags
0.5.x 0.6.x 0.7.x 0.10.x 0.11.x 0.13.x 0.19-nysdot 1.0.x-pre-rebase 1.0.x 1320_patterns TStopLinking WeakHashMap abyrdCompaction add-lines add-transfers-to-rest-api alightProblemPoc analyst-propagation-earliestarrival analystOperator analystReverseOptimize analystReverseOptimize2 antilombok arlington batch-analyst-sh berlin-bike bike-safety-factor bikeParking brokerRedelivery byte-packing bytes car-rental-routing-master-pr car-rental-routing car-rental-trimet-dev-resolution cars client-router-selector cluster-mods cluster custom-search-timeout debugNewRaptor denoramlizepointset deploy-builds-to-s3 earliest-arrival-propagation edgeUnwrap elim-graphvertex export-transfers faster-profile-routing fix-bad-date-npe fix-elevation fix-jersey-annotation fix-patterns fixStopClusterBug flatten-profile-requests frequentize gbfs-hours gbfs geoidElevation geometry-creation-fix gh-pages graphvertex-refactor-alternate gtfswrite hackidf2030 histograms ib-heuristic-improvements incrementLevels index_freq isochrone-grid isochrone-simplification isochrones issue894 jersey_inject jsonConfig leaflet-backbone leaflet-ui leg-geometry lessInterfaces linbin logback longdistanceretry ltr-ride-type-refactor mapdb master maven-ssl maxHours maxInterlineDistanceConfigurable merge_modules mmri-rt mod-ped-routing modes new-graph nnMods nontransit-analyst nyc-fare-bug nyspeed obaa_abyrd obaa osm-linking osmLevelType osmLoader osmreaderfields park-ride-api pathparse point-feature-equality post-data profile-propagation profile-routing-distributions propagate-params public-command-line-parameters qualified-mode-analyst-fixes railHeuristicTuning raptor-new raptor realtimeStoptime refactorindicator remove-integer-indexes remove-opentraffic removeHardcodedArrayLengths removePathServices result-set-simplification rootbeer route-type-name routeList routeListB sameEdgeLinkFix scenarios serializable-routing-requests serialize-fst-mmap simpleOriginDestinationLinker simplify-tnc-response sptservice stable startMode startSpotWorkers stop-times-service-dates summing test-date-time-parameters-in-plan-request test-id-collisions testFeedIds thinRaptorWorkers threadedHeuristic timezone tnc-eta-refactor tnc-routing tnc-wav-routing traffic transfer-rules transit-data-api transportation-network-company-routing trimet-call trimet-dev updated-profile-routing use-triptimes-subsets-for-modeify vertexEdgeTypes vexFormat vizdebugger vreixo-master_realtime_trips_stoptimes_tametable walk-issues-with-tnc-and-vehicle-rental zmqUpdateStreamer
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
162 lines (108 sloc) 11.2 KB

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

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

Contraction and Transfer Patterns

Timetable-based routing

ALT and Metric Embeddings

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.