Red de transporte

Una red de transporte o red de transferencia es una red o gráfico en el espacio geográfico que describe una infraestructura que permite y restringe el movimiento o el flujo. Los ejemplos incluyen, entre otros, redes de carreteras, vías férreas, 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 de 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 fue reconocida como una fecha temprana. De hecho, muchos de los primeros problemas y teorías emprendidas 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.

En la década de 1970, la conexión fue restablecida por los primeros desarrolladores de sistemas de información geográfica, quienes la emplearon en las estructuras de datos topológicos de polígonos (que no es relevante aquí) y el análisis de 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. La implementación completa de los algoritmos de análisis de red en el software GIS no apareció hasta la década de 1990, pero hoy en día generalmente hay herramientas avanzadas disponibles.

Datos de red

El análisis de red requiere datos detallados que representen los elementos de la red y sus propiedades. 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, representando las conexiones entre las líneas, lo que permite modelar el transporte de una línea a otra. Por lo general, estos puntos de conexión, o nodos, se incluyen como un conjunto de datos adicional.

Tanto a las aristas 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 las telecomunicaciones o el diámetro de la tubería.
• Impedancia, medidas de cualquier resistencia al flujo o a 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, comúnmente tiempo 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 realizar un giro a la izquierda oa 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 caudal, medidas del movimiento real que se está produciendo. Pueden ser mediciones codificadas en el tiempo específicas recopiladas mediante redes de sensores, como contadores de tráfico, o tendencias generales durante un período de tiempo, como el tráfico diario promedio 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 relacionadas 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. Muchos de estos algoritmos se implementan en software GIS comercial y de código abierto, como GRASS GIS y la extensión Network Analyst para Esri ArcGIS.

Enrutamiento óptimo

Una de las tareas más sencillas y comunes en una red es encontrar la ruta óptima que conecta dos puntos a lo largo de la red, con lo óptimo definido como la minimización de algún tipo de costo, como la distancia, el gasto de energía o el tiempo. Un ejemplo común es encontrar direcciones en una red de calles, una característica de casi cualquier aplicación web de mapas de calles como Google Maps. El método más popular para resolver esta tarea, implementado en la mayoría de los SIG y software de mapeo, es el algoritmo de Dijkstra.

Además del enrutamiento básico punto a punto, también son comunes los problemas de enrutamiento compuesto. El problema del vendedor ambulante solicita 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. El problema de enrutamiento de vehículos es una generalización de esto, lo que permite múltiples rutas simultáneas para llegar a los destinos. El problema de la inspección de ruta o del "cartero chino" solicita la ruta óptima (menor distancia/costo) que atraviesa todos los bordes; una aplicación común es el enrutamiento de camiones de basura. Este 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 lo óptimo definido como minimizar el costo de viaje agregado o medio 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, o la ubicación de un punto de venta para minimizar el tiempo de viaje desde las residencias de sus clientes potenciales. En un espacio sin restricciones (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.

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 similar a un búfer en un espacio sin restricciones, una representación del área a la que se puede llegar desde un punto (típicamente una instalación de servicio) en menos de una distancia especificada u otro costo acumulado. 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.

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 interrupciones en la red (que a menudo están enterradas o son difíciles de observar directamente), deducidas de informes que pueden ubicarse fácilmente, como las quejas de los clientes.

Ingeniería de transporte

El tráfico se ha estudiado ampliamente utilizando métodos de física estadística.