Una red de transporte o red de transporte es una red o gráfico en un espacio geográfico que describe una infraestructura que permite y restringe el movimiento o el flujo. [1] Los ejemplos incluyen , entre otros , redes de carreteras , ferrocarriles , rutas aéreas , tuberías , acueductos y líneas eléctricas . La representación digital de estas redes y los métodos para su análisis es una parte fundamental del análisis espacial , los sistemas de información geográfica , los servicios públicos y la ingeniería del transporte.. El análisis de redes es una aplicación de las teorías y algoritmos de la teoría de grafos y es una forma de análisis de proximidad .
Historia
La aplicabilidad de la teoría de grafos a los fenómenos geográficos se reconoció como una fecha temprana. De hecho, muchos de los primeros problemas y teorías emprendidos por los teóricos de grafos se inspiraron en situaciones geográficas, como el problema de los Siete Puentes de Königsberg , que fue uno de los fundamentos originales de la teoría de grafos cuando fue resuelto por Leonhard Euler en 1736. [ 2]
En la década de 1970, la conexión fue restablecida por los primeros desarrolladores de sistemas de información geográfica , que la emplearon en las estructuras de datos topológicos de los polígonos (que no es de relevancia aquí) y el análisis de las redes de transporte. Los primeros trabajos, como Tinkler (1977), se centraron principalmente en redes esquemáticas simples, probablemente debido a la falta de volúmenes significativos de datos lineales y la complejidad computacional de muchos de los algoritmos. [3] La implementación completa de los algoritmos de análisis de redes en el software SIG no apareció hasta la década de 1990, [4] [5] pero en la actualidad se encuentran generalmente disponibles herramientas avanzadas.
Datos de red
El análisis de red requiere datos detallados que representen los elementos de la red y sus propiedades. [6] El núcleo de un conjunto de datos de red es una capa vectorial de polilíneas que representan las rutas de viaje, ya sean rutas geográficas precisas o diagramas esquemáticos, conocidos como bordes . Además, se necesita información sobre la topología de la red , que representa las conexiones entre las líneas, lo que permite modelar el transporte de una línea a otra. Normalmente, estos puntos de conexión, o nodos , se incluyen como un conjunto de datos adicional. [7]
Tanto a los bordes como a los nodos se les atribuyen propiedades relacionadas con el movimiento o flujo:
- Capacidad , mediciones de cualquier limitación en el volumen de flujo permitido, como el número de carriles en una carretera, el ancho de banda de telecomunicaciones o el diámetro de la tubería.
- Impedancia , mediciones de cualquier resistencia al flujo oa la velocidad del flujo, como un límite de velocidad o una dirección de giro prohibida en una intersección de calles.
- Costo acumulado a través del viaje individual a lo largo del borde o a través del nodo, tiempo comúnmente transcurrido, de acuerdo con el principio de fricción de la distancia . Por ejemplo, un nodo en una red de calles puede requerir una cantidad de tiempo diferente para hacer un giro a la izquierda o a la derecha en particular. Dichos costos pueden variar con el tiempo, como el patrón de tiempo de viaje a lo largo de una calle urbana dependiendo de los ciclos diurnos del volumen de tráfico.
- Volumen de flujo , medidas del movimiento real que se está produciendo. Pueden ser mediciones específicas codificadas en el tiempo recopiladas mediante redes de sensores , como contadores de tráfico , o tendencias generales durante un período de tiempo, como el tráfico diario medio anual (AADT).
Métodos de análisis
Se ha desarrollado una amplia gama de métodos, algoritmos y técnicas para resolver problemas y tareas relacionados con el flujo de la red. Algunos de estos son comunes a todos los tipos de redes de transporte, mientras que otros son específicos de dominios de aplicación particulares. [8] Muchos de estos algoritmos se implementan en software GIS comercial y de código abierto, como GRASS GIS y la extensión Network Analyst de Esri ArcGIS .
Enrutamiento óptimo
Una de las tareas más simples y comunes en una red es encontrar la ruta óptima que conecta dos puntos a lo largo de la red, con la definición óptima como minimizar alguna forma de costo, como la distancia, el gasto de energía o el tiempo. [9] Un ejemplo común es encontrar direcciones en una red de calles, una característica de casi cualquier aplicación de mapas de calles web como Google Maps . El método más popular para resolver esta tarea, implementado en la mayoría de los software de mapas y SIG, es el algoritmo de Dijkstra . [10]
Además del enrutamiento básico punto a punto, también son comunes los problemas de enrutamiento compuesto . El problema del vendedor ambulante pide el pedido y la ruta óptimos (menor distancia / costo) para llegar a varios destinos; es un problema NP-difícil, pero algo más fácil de resolver en el espacio de la red que en el espacio sin restricciones debido al conjunto de soluciones más pequeño. [11] El problema de enrutamiento de vehículos es una generalización de esto, permitiendo múltiples rutas simultáneas para llegar a los destinos. El problema de inspección de ruta o "cartero chino" pide la ruta óptima (menor distancia / costo) que atraviesa cada borde; una aplicación común es el enrutamiento de camiones de basura. Esto resulta ser un problema mucho más simple de resolver, con algoritmos de tiempo polinomial .
Análisis de ubicación
Esta clase de problemas tiene como objetivo encontrar la ubicación óptima para una o más instalaciones a lo largo de la red, con la definición óptima como minimizar el costo total o medio de viaje hacia (o desde) otro conjunto de puntos en la red. Un ejemplo común es determinar la ubicación de un almacén para minimizar los costos de envío a un conjunto de puntos de venta minorista, o la ubicación de un punto de venta minorista para minimizar el tiempo de viaje desde las residencias de sus clientes potenciales. En el espacio no restringido (coordenadas cartesianas), este es un problema NP-difícil que requiere soluciones heurísticas como el algoritmo de Lloyd , pero en un espacio de red se puede resolver de manera determinista. [12]
Las aplicaciones particulares a menudo agregan más restricciones al problema, como la ubicación de instalaciones preexistentes o competidoras, las capacidades de las instalaciones o el costo máximo.
Áreas de servicio
Un área de servicio de red es análoga a un búfer en un espacio sin restricciones, una descripción del área a la que se puede llegar desde un punto (generalmente una instalación de servicio) en menos de una distancia especificada u otro costo acumulado. [13] Por ejemplo, el área de servicio preferida para una estación de bomberos sería el conjunto de segmentos de calles a los que puede llegar en poco tiempo. Cuando hay varias instalaciones, cada borde se asignaría a la instalación más cercana, produciendo un resultado análogo a un diagrama de Voronoi . [14]
Análisis de fallas
Una aplicación común en las redes de servicios públicos es la identificación de posibles ubicaciones de fallas o roturas en la red (que a menudo está enterrada o es difícil de observar directamente), deducida de informes que se pueden ubicar fácilmente, como quejas de los clientes.
Ingeniería de transporte
El tráfico se ha estudiado ampliamente utilizando métodos de física estadística. [15] [16] [17] Recientemente se estudió una red de transporte real de Beijing usando un enfoque de red y teoría de percolación. La investigación mostró que se puede caracterizar la calidad del tráfico global en una ciudad en cada momento del día usando el umbral de percolación, ver Fig. 1. En artículos recientes, la teoría de la percolación se ha aplicado para estudiar la congestión del tráfico en una ciudad. La calidad del tráfico global en una ciudad en un momento dado es por un solo parámetro, el umbral crítico de filtración. El umbral crítico representa la velocidad por debajo de la cual se puede viajar en una gran fracción de la red de la ciudad. El método puede identificar cuellos de botella de tráfico repetitivo. [18] Los exponentes críticos que caracterizan la distribución del tamaño de los conglomerados del buen tráfico son similares a los de la teoría de la percolación. [19] También se encuentra que durante las horas pico la red de tráfico puede tener varios estados metaestables de diferentes tamaños de red y la alternativa entre estos estados. [20]
Recientemente, Zhang et al. (2007) realizaron un estudio empírico sobre la distribución del tamaño de los atascos de tráfico. [21] Encontraron una ley de potencia universal aproximada para la distribución del tamaño de los atascos.
Serok et al. Desarrollaron un método para identificar grupos funcionales de calles espacio-temporales que representan un flujo de tráfico fluido en una ciudad. [22] G. Li y col. [23] desarrolló un método para diseñar una red de transporte de dos capas óptima en una ciudad.
Patrones de flujo de tráfico
Yohei Shida et al. Han estudiado patrones de flujo de tráfico similares a ríos en áreas urbanas de grandes ciudades durante las horas pico y no pico. [24]
Ver también
- La paradoja de Braess
- Red de flujo
- Enrutamiento heurístico
- Red de transporte interplanetario
- Ciencia de la red
- Teoría de la filtración
- Red de calles
- Red ferroviaria
- Transporte multimodal
Referencias
- ^ Barthelemy, Marc (2010). "Redes espaciales". Informes de física . 499 (1–3): 1–101. arXiv : 1010.0302 . Código bibliográfico : 2011PhR ... 499 .... 1B . doi : 10.1016 / j.physrep.2010.11.002 . S2CID 4627021 .
- ^ Euler, Leonhard (1736). "Solutio problematis ad geometriam situs pertinente". Comentario. Acad. Sci. U. Petrop 8, 128–40.
- ^ Tinkler, KJ (1977). "Introducción a los métodos teóricos de gráficos en geografía" (PDF) . CATMOG (14).
- ^ Ahuja RK, Magnanti TL, Orlin JB (1993) Flujos de red: teoría, algoritmos y aplicaciones . Prentice Hall, Englewood Cliffs, Nueva Jersey, EE. UU.
- ^ Daskin MS (1995) Red y ubicación discreta: modelos, algoritmos y aplicaciones . Wiley, Nueva Jersey, EE. UU.
- ^ "¿Qué es un conjunto de datos de red?" . Documentación de ArcGIS Pro . Esri.
- ^ "Elementos de red" . Documentación de ArcGIS Pro . Esri . Consultado el 17 de marzo de 2021 .
- ^ deSmith, Michael J .; Goodchild, Michael F .; Longley, Paul A. (2021). "7.2.1 Descripción general: análisis de red y ubicación" . Análisis geoespacial: una guía completa de principios, técnicas y herramientas de software (sexta edición revisada).
- ^ Worboys, Michael; Duckham, Matt (2004). "5.7 Representación de redes y algoritmos". GIS: A Computing Perspective (2ª ed.). Prensa CRC. págs. 211–218.
- ^ Dijkstra, EW (1959). "Una nota sobre dos problemas relacionados con los gráficos" (PDF) . Numerische Mathematik . 1 : 269-271. doi : 10.1007 / BF01386390 . S2CID 123284777 .
- ^ "Comando v.net.salesman" . Manual de GRASS GIS . OSGEO . Consultado el 17 de marzo de 2021 .
- ^ deSmith, Michael J .; Goodchild, Michael F .; Longley, Paul A. (2021). "7.4.2 Problemas de p-mediana y p-centro más grandes" . Análisis geoespacial: una guía completa de principios, técnicas y herramientas de software (sexta edición revisada).
- ^ deSmith, Michael J .; Goodchild, Michael F .; Longley, Paul A. (2021). "7.4.3 Áreas de servicio" . Análisis geoespacial: una guía completa de principios, técnicas y herramientas de software (sexta edición revisada).
- ^ "Comando v.net.alloc" . Documentación de GRASS GIS . OSGEO . Consultado el 17 de marzo de 2021 .
- ^ Helbing, D (2001). "Tráfico y sistemas de muchas partículas autónomos relacionados". Reseñas de Física Moderna . 73 (4): 1067-1141. arXiv : cond-mat / 0012229 . Código Bibliográfico : 2001RvMP ... 73.1067H . doi : 10.1103 / RevModPhys.73.1067 . S2CID 119330488 .
- ^ S., Kerner, Boris (2004). La física del tráfico: características empíricas del patrón de autopistas, aplicaciones de ingeniería y teoría . Berlín, Heidelberg: Springer Berlin Heidelberg. ISBN 9783540409861. OCLC 840291446 .
- ^ Wolf, DE; Schreckenberg, M; Bachem, A (junio de 1996). Tráfico y flujo granular . Tráfico y flujo granular . CIENTÍFICO MUNDIAL. págs. 1–394. doi : 10.1142 / 9789814531276 . ISBN 9789810226350.
- ^ Li, Daqing; Fu, Bowen; Wang, Yunpeng; Lu, Guangquan; Berezin, Yehiel; Stanley, H. Eugene; Havlin, Shlomo (20 de enero de 2015). "Transición de filtración en red de tráfico dinámico con cuellos de botella críticos en evolución" . Actas de la Academia Nacional de Ciencias . 112 (3): 669–672. Código bibliográfico : 2015PNAS..112..669L . doi : 10.1073 / pnas.1419185112 . ISSN 0027-8424 . PMC 4311803 . PMID 25552558 .
- ^ Cambiar entre modos de filtración críticos en la dinámica del tráfico de la ciudad, G Zeng, D Li, S Guo, L Gao, Z Gao, HE Stanley, S Havlin, Proceedings of the National Academy of Sciences 116 (1), 23-28 (2019)
- ^ G. Zeng, J. Gao, L. Shekhtman, S. Guo, W. Lv, J. Wu, H. Liu, O. Levy, D. Li, ... (2020). "Múltiples estados de red metaestable en tráfico urbano" . Actas de la Academia Nacional de Ciencias . 117 (30): 17528-17534. doi : 10.1073 / pnas.1907493117 . PMC 7395445 . PMID 32661171 .CS1 maint: varios nombres: lista de autores ( enlace )
- ^ Resiliencia sin escala de atascos de tráfico reales, Limiao Zhang, Guanwen Zeng, Daqing Li, Hai-Jun Huang, H Eugene Stanley, Shlomo Havlin, Actas de la Academia Nacional de Ciencias 116 (18), 8673-8678 (2019)
- ^ Nimrod Serok, Orr Levy, Shlomo Havlin, Efrat Blumenfeld-Lieberthal (2019). "Revelando las interrelaciones entre la red de calles urbanas y sus flujos dinámicos de tráfico: Implicación urbanística". Publicaciones SAGE . 46 (7): 1362.CS1 maint: varios nombres: lista de autores ( enlace )
- ^ G. Li, SDS Reis, AA Moreira, S. Havlin, HE Stanley, JS Andrade Jr. (2010). "Hacia los principios de diseño de redes de transporte óptimas". Phys. Rev. Lett . 104 (1): 018701. arXiv : 0908.3869 . Código Bibliográfico : 2010PhRvL.104a8701L . doi : 10.1103 / PhysRevLett.104.018701 . PMID 20366398 . S2CID 119177807 .CS1 maint: varios nombres: lista de autores ( enlace )
- ^ Y. Shida, H. Takayasu, S. Havlin, M. Takayasu (2020). "Leyes de escala universal de patrones de flujo humano colectivo en regiones urbanas" . Informes científicos . 10 (1): 21405. doi : 10.1038 / s41598-020-77163-2 . PMC 7722863 . PMID 33293581 .CS1 maint: varios nombres: lista de autores ( enlace )