Abstract
We study the problem of computing isochrones in static and dynamic road networks, where the objective is to identify the boundary of the region in range from a given source within a certain amount of time. While there is a wide range of practical applications for this problem (e. g., urban planning, geomarketing, visualizing the cruising range of a vehicle), there has been little research on fast algorithms for large, realistic inputs, and existing approaches tend to compute more information than necessary. Our contribution is twofold: (1) We propose a more compact but sufficient definition of isochrones, based on which, (2) we provide several easy-to-parallelize, scalable algorithmic approaches for faster computation. By extensive experimental analysis, we demonstrate that our techniques enable fast isochrone computation within milliseconds even on continental networks, significantly faster than the state-of-the-art.
Supported by the EU FP7 under grant agreement no. 609026 (project MOVE-SMART).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Extension of CRP to isochrones is outlined in a patent (US Patent App. 13/649,114; http://www.google.com/patents/US20140107921), however, in a simpler than our intended scenario. Furthermore, the approach was neither implemented nor evaluated.
- 2.
Strictly speaking, isochrone implies time as a resource. While isoline or isocontour would be more precise, we have settled for the term most common in the literature.
References
Abraham, I., Delling, D., Fiat, A., Goldberg, A.V., Werneck, R.F.: HLDB: location-based services in databases. In: Proceedings of the 20th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems (GIS 2012), pp. 339–348. ACM Press, New York (2012)
Bast, H., Delling, D., Goldberg, A.V., Müller-Hannemann, M., Pajor, T., Sanders, P., Wagner, D., Werneck, R.F.: Route Planning in Transportation Networks. Technical report abs/1504.05140, ArXiv e-prints (2015)
Bauer, V., Gamper, J., Loperfido, R., Profanter, S., Putzer, S., Timko, I.: Computing isochrones in multi-modal, schedule-based transport networks. In: Proceedings of the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS 2008), pp. 78:1–78:2. ACM Press, New York (2008)
Baum, M., Bläsius, T., Gemsa, A., Rutter, I., Wegner, F.: Scalable Isocontour Visualization in Road Networks via Minimum-Link Paths. Technical report abs/1602.01777, ArXiv e-prints (2016)
Delling, D., Goldberg, A.V., Nowatzyk, A., Werneck, R.F.: PHAST: hardware-accelerated shortest path trees. J. Parallel Distrib. Comput. 73(7), 940–952 (2013)
Delling, D., Goldberg, A.V., Pajor, T., Werneck, R.F.: Customizable route planning. In: Pardalos, P.M., Rebennack, S. (eds.) SEA 2011. LNCS, vol. 6630, pp. 376–387. Springer, Heidelberg (2011)
Delling, D., Goldberg, A.V., Pajor, T., Werneck, R.F.: Customizable route planning in road networks. Transportation Science (2015)
Delling, D., Goldberg, A.V., Razenshteyn, I., Werneck, R.F.: Graph partitioning with natural cuts. In: Proceedings of the 25th International Parallel and Distributed Processing Symposium (IPDPS 2011), pp. 1135–1146. IEEE Computer Society (2011)
Delling, D., Goldberg, A.V., Werneck, R.F.: Faster batched shortest paths inroad networks. In: Proceedings of the 11th Workshop on Algorithmic Approachesfor Transportation Modeling, Optimization, and Systems (ATMOS 2011). OpenAccessSeries in Informatics, vol. 20, pp. 52–63. OASIcs (2011)
Delling, D., Holzer, M., Müller, K., Schulz, F., Wagner, D.: High-performance multi-level routing. In: The Shortest Path Problem: Ninth DIMACS Implementation Challenge, DIMACS Book, vol. 74, pp. 73–92. American Mathematical Society (2009)
Delling, D., Werneck, R.F.: Faster customization of road networks. In: Bonifaci, V., Demetrescu, C., Marchetti-Spaccamela, A. (eds.) SEA 2013. LNCS, vol. 7933, pp. 30–42. Springer, Heidelberg (2013)
Delling, D., Werneck, R.F.: Customizable point-of-interest queries in road networks. IEEE Trans. Knowl. Data Eng. 27(3), 686–698 (2015)
Demetrescu, C., Goldberg, A.V., Johnson, D.S. (eds.): The Shortest Path Problem: Ninth DIMACS Implementation Challenge, DIMACS Book, vol. 74. American Mathematical Society (2009)
Dibbelt, J., Strasser, B., Wagner, D.: Customizable contraction hierarchies. In: Gudmundsson, J., Katajainen, J. (eds.) SEA 2014. LNCS, vol. 8504, pp. 271–282. Springer, Heidelberg (2014)
Dibbelt, J., Strasser, B., Wagner, D.: Customizable contraction hierarchies. ACM J. Exp. Algorithmics 21(1), 108–122 (2016)
Dijkstra, E.W.: A note on two problems in connexion with graphs. Numer. Math. 1(1), 269–271 (1959)
Efentakis, A., Grivas, N., Lamprianidis, G., Magenschab, G., Pfoser, D.: Isochrones, traffic and DEMOgraphics. In: Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS 2013), pp. 548–551. ACM Press, New York (2013)
Efentakis, A., Pfoser, D.: GRASP. Extending graph separators for the single-source shortest-path problem. In: Schulz, A.S., Wagner, D. (eds.) ESA 2014. LNCS, vol. 8737, pp. 358–370. Springer, Heidelberg (2014)
Efentakis, A., Pfoser, D., Vassiliou, Y.: SALT. A unified framework for all shortest-path query variants on road networks. In: Bampis, E. (ed.) SEA 2015. LNCS, vol. 9125, pp. 298–311. Springer, Heidelberg (2015)
Efentakis, A., Theodorakis, D., Pfoser, D.: Crowdsourcing computing resources for shortest-path computation. In: Proceedings of the 20th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems (GIS 2012), pp. 434–437. ACM Press, New York (2012)
Erwig, M.: The graph voronoi diagram with applications. Networks 36(3), 156–163 (2000)
Foti, F., Waddell, P., Luxen, D.: A generalized computational framework for accessibility: from the pedestrian to the metropolitan scale. In: Proceedings of the 4th TRB Conference on Innovations in Travel Modeling. Transportation Research Board (2012)
Gamper, J., Böhlen, M., Cometti, W., Innerebner, M.: Defining isochrones in multimodal spatial networks. In: Proceedings of the 20th ACM International Conference on Information and Knowledge Management (CIKM 2011), pp. 2381–2384. ACM Press, New York (2011)
Gamper, J., Böhlen, M., Innerebner, M.: Scalable computation of isochrones with network expiration. In: Ailamaki, A., Bowers, S. (eds.) SSDBM 2012. LNCS, vol. 7338, pp. 526–543. Springer, Heidelberg (2012)
Geisberger, R.: Advanced Route Planning in Transportation Networks. Ph.D. thesis, Karlsruhe Institute of Technology (2011)
Geisberger, R., Luxen, D., Sanders, P., Neubauer, S., Volker, L.: Fast detour computation for ride sharing. In: Proceedings of the 10th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS 2010). OpenAccess Series in Informatics, vol. 14, pp. 88–99. OASIcs (2010)
Geisberger, R., Sanders, P., Schultes, D., Vetter, C.: Exact routing in large road networks using contraction hierarchies. Transp. Sci. 46(3), 388–404 (2012)
Grubwinkler, S., Brunner, T., Lienkamp, M.: Range prediction for EVs via crowd-sourcing. In: Proceedings of the 10th IEEE International Vehicle Power and Propulsion Conference (VPPC 2014), pp. 1–6. IEEE (2014)
Holzer, M., Schulz, F., Wagner, D.: Engineering multilevel overlay graphs for shortest-path queries. ACM J. Exp. Algorithmics 13, 1–26 (2008)
Innerebner, M., Böhlen, M., Gamper, J.: ISOGA: a system for geographical reachability analysis. In: Liang, S.H.L., Wang, X., Claramunt, C. (eds.) W2GIS 2013. LNCS, vol. 7820, pp. 180–189. Springer, Heidelberg (2013)
Jung, S., Pramanik, S.: An efficient path computation model for hierarchically structured topographical road maps. IEEE Trans. Knowl. Data Eng. 14(5), 1029–1046 (2002)
Knopp, S., Sanders, P., Schultes, D., Schulz, F., Wagner, D.: Computing many-to-many shortest paths using highway hierarchies. In: Proceedings of the 9th Workshop on Algorithm Engineering and Experiments (ALENEX 2007), pp. 36–45. SIAM (2007)
Marciuska, S., Gamper, J.: Determining objects within isochrones in spatial network databases. In: Catania, B., Ivanović, M., Thalheim, B. (eds.) ADBIS 2010. LNCS, vol. 6295, pp. 392–405. Springer, Heidelberg (2010)
Okabe, A., Satoh, T., Furuta, T., Suzuki, A., Okano, K.: Generalized network voronoi diagrams: concepts, computational methods, and applications. Int. J. Geogr. Inf. Sci. 22(9), 965–994 (2008)
O’Sullivan, D., Morrison, A., Shearer, J.: Using desktop GIS for the investigation of accessibility by public transport: an isochrone approach. Int. J. Geogr. Inf. Sci. 14(1), 85–104 (2000)
Pothen, A., Simon, H.D., Liou, K.P.: Partitioning sparse matrices with eigenvectors of graphs. SIAM J. Matrix Anal. Appl. 11, 430–452 (1990)
Sanders, P., Schulz, C.: Distributed evolutionary graph partitioning. In: Proceedings of the 14th Meeting on Algorithm Engineering and Experiments (ALENEX 2012), pp. 16–29. SIAM (2012)
Schulz, C.: High Quality Graph Partitioning. Ph.D. thesis, Karlsruhe Institute of Technology (2013)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Baum, M., Buchhold, V., Dibbelt, J., Wagner, D. (2016). Fast Exact Computation of Isochrones in Road Networks. In: Goldberg, A., Kulikov, A. (eds) Experimental Algorithms. SEA 2016. Lecture Notes in Computer Science(), vol 9685. Springer, Cham. https://doi.org/10.1007/978-3-319-38851-9_2
Download citation
DOI: https://doi.org/10.1007/978-3-319-38851-9_2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-38850-2
Online ISBN: 978-3-319-38851-9
eBook Packages: Computer ScienceComputer Science (R0)