Route Planning in Transportation Networks
| Autor: | Thomas Pajor, Daniel Delling, Hannah Bast, Andrew V. Goldberg, Peter Sanders, Matthias Müller-Hannemann, Renato F. Werneck, Dorothea Wagner |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Schedule
Range query (data structures) Operations research business.industry Computer science 0102 computer and information sciences 02 engineering and technology computer.software_genre 01 natural sciences Metropolitan area Variety (cybernetics) Contraction hierarchies 010201 computation theory & mathematics 020204 information systems Public transport 0202 electrical engineering electronic engineering information engineering Route planning software Train business computer Simulation |
| Zdroj: | Algorithm Engineering ISBN: 9783319494869 Algorithm Engineering |
| DOI: | 10.1007/978-3-319-49487-6_2 |
| Popis: | We survey recent advances in algorithms for route planning in transportation networks. For road networks, we show that one can compute driving directions in milliseconds or less even at continental scale. A variety of techniques provide different trade-offs between preprocessing effort, space requirements, and query time. Some algorithms can answer queries in a fraction of a microsecond, while others can deal efficiently with real-time traffic. Journey planning on public transportation systems, although conceptually similar, is a significantly harder problem due to its inherent time-dependent and multicriteria nature. Although exact algorithms are fast enough for interactive queries on metropolitan transit systems, dealing with continent-sized instances requires simplifications or heavy preprocessing. The multimodal route planning problem, which seeks journeys combining schedule-based transportation (buses, trains) with unrestricted modes (walking, driving), is even harder, relying on approximate solutions even for metropolitan inputs. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|