Bast, Hannah; Carlsson, Erik; Eigenwillig, Arno; Geisberger, Robert; Harrelson, Chris; Raychev, Veselin; Viger, Fabien Fast routing in very large public transportation networks using transfer patterns. (English) Zbl 1287.90013 de Berg, Mark (ed.) et al., Algorithms – ESA 2010. 18th annual European symposium, Liverpool, UK, September 6–8, 2010. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-15774-5/pbk). Lecture Notes in Computer Science 6346, 290-301 (2010). Summary: We show how to route on very large public transportation networks (up to half a billion arcs) with average query times of a few milliseconds. We take into account many realistic features like: traffic days, walking between stations, queries between geographic locations instead of a source and a target station, and multi-criteria cost functions. Our algorithm is based on two key observations: (1) many shortest paths share the same transfer pattern, i.e., the sequence of stations where a change of vehicle occurs; (2) direct connections without change of vehicle can be looked up quickly. We precompute the respective data; in practice, this can be done in time linear in the network size, at the expense of a small fraction of non-optimal results. We have accelerated public transportation routing on Google Maps with a system based on our ideas. We report experimental results for three data sets of various kinds and sizes.For the entire collection see [Zbl 1194.68069]. Cited in 6 Documents MSC: 90B10 Deterministic network models in operations research 90B06 Transportation, logistics and supply chain management PDFBibTeX XMLCite \textit{H. Bast} et al., Lect. Notes Comput. Sci. 6346, 290--301 (2010; Zbl 1287.90013) Full Text: DOI