Informes de la Construcción, Vol 71, No 556 (2019)

Método de construcción de dígrafos a partir de redes viales reales en mapas digitales con aplicaciones en la búsqueda de rutas óptimas


https://doi.org/10.3989/ic.65988

J. López Ortega
Universidad Autónoma Metropolitana, México
orcid https://orcid.org/0000-0002-2173-7146

J. López-Sauceda
Universidad Autónoma Metropolitana - Consejo Nacional de Ciencia y Tecnología CONACyT, México
orcid https://orcid.org/0000-0001-5174-6046

J. G. Carrillo
Universidad Autónoma Metropolitana - Consejo Nacional de Ciencia y Tecnología CONACyT, México
orcid https://orcid.org/0000-0002-4147-6764

J. Sandoval
Universidad Autónoma Metropolitana, México
orcid https://orcid.org/0000-0002-5578-4389

Resumen


Actualmente las redes viales en zonas urbanas sufren obstrucciones, ya sea por manifestaciones, embotellamientos, u otro tipo de bloqueo, causando el cierre momentáneo o permanente de vías o zonas de tránsito que obligan a conductores a establecer nuevas rutas. Una solución es la creación de rutas alternativas en mapas digitales a partir de dígrafos relacionados con las características de una red vial real, y la aplicación de algoritmos de optimización de rutas. En este trabajo se propone un método para construir dígrafos con una aplicación en la API de Google Maps en la extracción visual de elementos como vértices (intersecciones), aristas (calles) y flechas de sentido (dirección vial), lo que permite la aplicación del algoritmo de Dijkstra en busca de rutas alternativas.

Palabras clave


Dígrafo; red vial; API Google Maps; algoritmo Dijkstra; ruta alternativa

Texto completo:


HTML PDF XML

Referencias


(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




Copyright (c) 2019 Consejo Superior de Investigaciones Científicas (CSIC)

Licencia de Creative Commons
Esta obra está bajo una licencia de Creative Commons Reconocimiento 4.0 Internacional.


Contacte con la revista informes@ietcc.csic.es

Soporte técnico soporte.tecnico.revistas@csic.es