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

Autores/as

DOI:

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

Palabras clave:

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

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.

Descargas

Los datos de descargas todavía no están disponibles.

Citas

(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

Publicado

2019-12-30

Cómo citar

López Ortega, J., López-Sauceda, J., Carrillo, J. G., & Sandoval, J. (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. Informes De La Construcción, 71(556), e320. https://doi.org/10.3989/ic.65988

Número

Sección

Artículos