Method to construct graphs from real street networks in digital maps with applications in the search of optimal routes
DOI:
https://doi.org/10.3989/ic.65988Keywords:
Digraph, road network, Google Maps API, Dijkstra algorithm, alternative routeAbstract
In urban areas, street networks are exposed to road obstructions since some traffic obstacles such as street protest, and traffic congestion are frequent. According to this, drivers are forced to choose alternative routes. Building alternative routes on digital maps represents a solution to these road problems. We determine alternative routes associating graphs to characteristics of real road networks using a API and incorporating optimization algorithms. In this work we propose a method to construct a graph from a zone with traffic blockages considering the network features. With an optimization algorithm (Dijkstra) the alternative routes are defined using digital maps. In addition, a computer program was developed (using Google Maps API) as a tool to create the graph, which is composed of: vertices (intersections) and directional edges (driving direction). This graph is used to establish alternative routes represented as polylines in digital maps.
Downloads
References
(1) Gobierno de México (2016). Ley de movilidad del distrito federal, Título tercero, Capitulo XIV, Artículo 212 de la infraestructura para la movilidad y su uso. Gaceta oficial de la ciudad de México, CDMX, México.
(2) Instituto Nacional de Estadística y Geografía (INEGI) (2014). Red nacional de caminos, ISO 14825:2011 Intelligent transport systems. Recuperado de https://www.imt.mx/images/files/USIG/rnc/Documento_Tecnico.pdf
(3) Ardizzone, E. (2012, 25-29 de November). Extracting touristic information from online image collections, Conferencia. En Eighth International Conference on Signal Image Technology and Internet Based Systems (pp. 482-488). Nápoles, Italia: IEEE. https://doi.org/10.1109/SITIS.2012.77
(4) Recuero, A. (1994). Aplicaciones de la teoría de grafos: búsqueda de caminos en una red y análisis de su conectividad. Informes de la Construcción, 46(433): 33-45. https://doi.org/10.3989/ic.1994.v46.i433.1115
(5) Chen, Y., Shen, S., Chen, T., Yang, R. (2014). Path Optimization Study for Vehicles Evacuation Based on Dijkstra algorithm. Procedia Engineering, 71(2014): 159-165. https://doi.org/10.1016/j.proeng.2014.04.023
(6) Angel Restrepo, P.L, Marín, L.F. (2011). A computational method to obtaint optimal paths in road networks. Dyna, 78(167): 112-121.
(7) Nuñez, M. (2016, 1 de septiembre). Knowledge Tier Platform for Graph Mining in (Smart) Cities, Ponencia. En Symposium on Information Management and Big Data SIMBig (pp. 110-113). Perú.
(8) Zhan, F., Noon, C. (1998). Shortest path algorithms: An evaluation using real road networks. Transportation Science, 32(1): 65-73. https://doi.org/10.1287/trsc.32.1.65
(9) Eneh, A., Arinze, U. (2017). Comparative analysis and implementation of dijkstra's shortest path algorithm for emergency response and logistic planning. Nigerian Journal of Technology, 36(3): 876-888.
(10) Villalobos, A. (2006, 7-8 de septiembre). Grafos: herramienta informática para el aprendizaje y resolución de problemas reales de teoría de grafos, ponencia. En X Congreso de Ingeniería de Organización, Valencia, España. Asociación para el Desarrollo de la Ingeniería de Organización (ADINGOR)
(11) Abraham, I., Delling, D., Goldberg, A. (2013). Alternative routes in road networks. Journal of Experimental Algorithmics, 18(1): 1-17. https://doi.org/10.1145/2444016.2444019
(12) Peng, W. (2012). A Fast Algorithm to Find All-Pairs Shortest Paths in Complex Networks. Procedia Computer Science, 9: 557-566. https://doi.org/10.1016/j.procs.2012.04.060
(13) Restrepo, J., Sánchez, J. (2004). Aplicación de la teoría de grafos y el algoritmo de Dijkstra para determinar las distancias y las rutas más cortas en una ciudad. Scientia et technica, 10(26): 121-126.
(14) Nathaniel, O., Nsikan, A. (2017). Anapplication of Dijkstra's Algorithm to shortest route problem. IOSR Journal of Mathematics, 13(3): 20-32. https://doi.org/10.9790/5728-1301023238
Published
How to Cite
Issue
Section
License
Copyright (c) 2019 Consejo Superior de Investigaciones Científicas (CSIC)
This work is licensed under a Creative Commons Attribution 4.0 International License.
© CSIC. Manuscripts published in both the print and online versions of this journal are the property of the Consejo Superior de Investigaciones Científicas, and quoting this source is a requirement for any partial or full reproduction.
All contents of this electronic edition, except where otherwise noted, are distributed under a Creative Commons Attribution 4.0 International (CC BY 4.0) licence. You may read the basic information and the legal text of the licence. The indication of the CC BY 4.0 licence must be expressly stated in this way when necessary.
Self-archiving in repositories, personal webpages or similar, of any version other than the final version of the work produced by the publisher, is not allowed.
