Asignación de ruta

Este artículo trata sobre el modelado de transporte. Para redes de computadoras, consulte enrutamiento .

Una breve historia de la ingeniería de tráfico

La asignación de ruta , la elección de ruta o la asignación de tráfico se refieren a la selección de rutas (caminos alternativos llamados) entre orígenes y destinos en las redes de transporte . Es el cuarto paso en la convencional de transporte de pronóstico del modelo, después de la generación de viajes , distribución de viajes , y el modo de elección . El análisis de intercambio zonal de la distribución de viajes proporciona tablas de viaje de origen-destino. El análisis de elección de modo indica qué viajeros utilizarán qué modo. Para determinar las necesidades de las instalaciones y los costos y beneficios, necesitamos saber el número de viajeros en cada ruta y enlace de la red (una ruta es simplemente una cadena de enlaces entre un origen y un destino). Necesitamos asumir la asignación de tráfico (o viaje). Suponga que hay una red de carreteras y sistemas de tránsito y una adición propuesta. Primero queremos conocer el patrón actual de retraso del tráfico y luego qué sucedería si se hiciera la adición.

La Investigación de operaciones de Wikibook tiene una página sobre el tema: Problema de transporte y asignación

Enfoques generales

Técnicas de larga data

El problema de estimar cuántos usuarios hay en cada ruta es antiguo. Los planificadores empezaron a analizarlo detenidamente a medida que se empezaron a desarrollar autopistas y autovías . La autopista ofrecía un nivel de servicio superior al del sistema de calles local y desviaba el tráfico del sistema local. Al principio, la diversión era la técnica. Se utilizaron ratios de tiempo de viaje, atemperados por consideraciones de costes, comodidad y nivel de servicio .

Los investigadores del Estudio de transporte del área de Chicago (CATS) desarrollaron curvas de desvío para autopistas frente a calles locales. También hubo mucho trabajo en California, ya que California tuvo experiencias tempranas con la planificación de autopistas. Además del trabajo de tipo desvío, los CATS atacaron algunos problemas técnicos que surgen cuando se trabaja con redes complejas. Un resultado fue el algoritmo Bellman-Ford-Moore para encontrar las rutas más cortas en las redes.

El problema que no resolvió el enfoque de desvío fue la retroalimentación de la cantidad de tráfico en los enlaces y rutas. Si muchos vehículos intentan utilizar una instalación, la instalación se congestiona y aumenta el tiempo de viaje. A falta de alguna forma de considerar la retroalimentación, los primeros estudios de planificación (en realidad, la mayoría en el período 1960-1975) ignoraron la retroalimentación. Utilizaron el algoritmo de Moore para determinar las rutas más cortas y asignaron todo el tráfico a las rutas más cortas. Eso se llama asignación de todo o nada porque todo el tráfico de i a j se mueve a lo largo de una ruta o no.

La asignación de todo o nada o la ruta más corta no es trivial desde un punto de vista técnico-computacional. Cada zona de tráfico está conectada a n - 1 zonas, por lo que hay que considerar numerosas rutas. Además, en última instancia, estamos interesados ​​en el tráfico en los enlaces. Un enlace puede ser parte de varias rutas, y el tráfico a lo largo de las rutas debe sumarse enlace por enlace.

Se puede argumentar a favor del enfoque de todo o nada. Va de la siguiente manera: el estudio de planificación es para respaldar las inversiones para que haya un buen nivel de servicio disponible en todos los enlaces. Utilizando los tiempos de viaje asociados con el nivel de servicio planificado, los cálculos indican cómo fluirá el tráfico una vez que se hayan implementado las mejoras. Conociendo las cantidades de tráfico en los enlaces, se puede calcular la capacidad a suministrar para alcanzar el nivel de servicio deseado.

Procedimientos heurísticos

Para tener en cuenta el efecto de la carga de tráfico en los tiempos de viaje y los equilibrios del tráfico, se desarrollaron varios procedimientos de cálculo heurístico . Una heurística procede de forma incremental. El tráfico que se asignará se divide en partes (normalmente 4). Asigne la primera parte del tráfico. Calcule nuevos tiempos de viaje y asigne la siguiente parte del tráfico. El último paso se repite hasta que se asigna todo el tráfico. Los GATOS utilizaron una variación de esto; asignó fila por fila en la tabla OD.

La heurística incluida en la colección de programas informáticos de la FHWA procede de otra manera.

• 0. Empiece por cargar todo el tráfico utilizando un procedimiento de todo o nada.
• 1. Calcule los tiempos de viaje resultantes y reasigne el tráfico.
• 2. Ahora, comience a reasignar usando pesos. Calcule los tiempos de viaje ponderados en las dos cargas anteriores y utilícelos para la siguiente tarea. La última iteración obtiene un peso de 0,25 y la anterior obtiene un peso de 0,75.
• 3. Continuar.

Estos procedimientos parecen funcionar "bastante bien", pero no son exactos.

Algoritmo de Frank-Wolfe

Dafermos (1968) aplicó el algoritmo de Frank-Wolfe (1956, Florian 1976), que se puede utilizar para abordar el problema del equilibrio del tráfico. Suponga que estamos considerando una red de carreteras. Para cada enlace hay una función que indica la relación entre resistencia y volumen de tráfico. La Oficina de Carreteras Públicas (BPR) desarrolló una función de congestión de enlace (arco) (o retardo de volumen o rendimiento de enlace), que denominaremos S _a (v _a )

${\displaystyle S_{a}\left({v_{a}}\right)=t_{a}\left({1+0.15\left({\frac {v_{a}}{c_{a}}}\right)^{4}}\right)}$

• t _a = tiempo de viaje de flujo libre en el enlace a por unidad de tiempo
• v _a = volumen de tráfico en el enlace a por unidad de tiempo (algo más exacto: flujo que intenta utilizar el enlace a ).
• c _a = capacidad del enlace a por unidad de tiempo
• S _un (v _una ) es el tiempo promedio de viaje para un vehículo en el enlace de una

Hay otras funciones de congestión. El CATS ha utilizado durante mucho tiempo una función diferente de la utilizada por el BPR, pero parece haber poca diferencia entre los resultados cuando se comparan las funciones CATS y BPR.

Asignación de equilibrio

Para asignar tráfico a rutas y enlaces tenemos que tener reglas, y existen las conocidas condiciones de equilibrio de Wardrop . ^[1] La esencia de estos es que los viajeros se esforzarán por encontrar el camino más corto (menor resistencia) desde el origen hasta el destino, y el equilibrio de la red ocurre cuando ningún viajero puede reducir el esfuerzo de viaje cambiando a un nuevo camino. Estas se denominan condiciones óptimas para el usuario, ya que ningún usuario se beneficiará de cambiar las rutas de viaje una vez que el sistema esté en equilibrio.

El equilibrio óptimo del usuario se puede encontrar resolviendo el siguiente problema de programación no lineal

${\displaystyle \min \sum _{a}{\int _{0}^{v_{a}}{S_{a}\left(x\right)}}dx}$

sujeto a:

${\displaystyle v_{a}=\sum _{i}{\sum _{j}{\sum _{r}{\alpha _{ij}^{ar}x_{ij}^{r}}}}}$

${\displaystyle \sum _{r}{x_{ij}^{r}=T_{ij}}}$

${\displaystyle v_{a}\geq 0,\;x_{ij}^{r}\geq 0}$

donde es el número de vehículos en la ruta r desde el origen i hasta el destino j . Entonces, la restricción (2) dice que todos los viajes deben tener lugar - i = 1 ... n; j = 1 ... n${\displaystyle x_{ij}^{r}}$

${\displaystyle \alpha _{ij}^{ar}}$= 1 si el enlace a está en la ruta r de i a j; cero en caso contrario. Entonces, la restricción (1) suma el tráfico en cada enlace. Existe una restricción para cada enlace de la red. La restricción (3) asegura que no haya tráfico negativo.

Ejemplo

Un ejemplo de Eash, Janson y Boyce (1979) ilustrará la solución al problema del programa no lineal. Hay dos enlaces del nodo 1 al nodo 2, y hay una función de resistencia para cada enlace (consulte la Figura 1). Las áreas bajo las curvas de la Figura 2 corresponden a la integración de 0 a a en la ecuación 1, suman 220 674. Tenga en cuenta que la función para el enlace b se traza en la dirección inversa.

${\displaystyle S_{a}=15\left({1+0.15\left({\frac {v_{a}}{1000}}\right)^{4}}\right)}$

${\displaystyle S_{b}=20\left({1+0.15\left({\frac {v_{b}}{3000}}\right)^{4}}\right)}$

${\displaystyle v_{a}+v_{b}=8000}$

Figura 1: Red de dos rutas

Figura 2: Solución gráfica del problema de asignación de equilibrio

Figura 3: Asignación de vehículos que no satisfacen la condición de equilibrio

En el equilibrio, hay 2.152 vehículos en el enlace una y 5847 en el enlace b . El tiempo de viaje es el mismo en cada ruta: aproximadamente 63.

La Figura 3 ilustra una asignación de vehículos que no es consistente con la solución de equilibrio. Las curvas no se modifican. Pero con la nueva asignación de vehículos a las rutas, el área sombreada debe incluirse en la solución, por lo que la solución de la Figura 3 es más grande que la solución de la Figura 2 por el área del área sombreada.

Integrando opciones de viaje

El modelo de planificación del transporte urbano evolucionó como un conjunto de pasos a seguir y los modelos evolucionaron para su uso en cada paso. A veces, hubo pasos dentro de los pasos, como fue el caso de la primera declaración del modelo de Lowry . En algunos casos, se ha observado que los pasos se pueden integrar. De manera más general, los pasos se abstraen de las decisiones que pueden tomarse simultáneamente, y sería deseable replicarlo mejor en el análisis.

Los modelos de demanda desagregada se desarrollaron primero para tratar el problema de elección de modo. Ese problema supone que uno ha decidido hacer un viaje, a dónde irá ese viaje y a qué hora se realizará el viaje. Se han utilizado para tratar el contexto más amplio implícito. Por lo general, se desarrollará un modelo anidado, por ejemplo, comenzando con la probabilidad de que se realice un viaje, luego examinando la elección entre lugares y luego la elección del modo. El tiempo de viaje es un poco más difícil de tratar.

El modelo de entropía doblemente restringido de Wilson ha sido el punto de partida de los esfuerzos a nivel agregado. Ese modelo contiene la restricción

${\displaystyle t_{ij}c_{ij}=C}$

donde son los costos de viaje del enlace, se refiere al tráfico en un enlace y C es una restricción de recursos que se debe dimensionar al ajustar el modelo con datos. En lugar de usar esa forma de restricción, se puede usar la función de resistencia que aumenta monótonamente que se usa en la asignación de tráfico. El resultado determina los movimientos de zona a zona y asigna tráfico a las redes, y eso tiene mucho sentido por la forma en que uno imagina que funciona el sistema: el tráfico de zona a zona depende de la resistencia ocasionada por la congestión.${\displaystyle c_{ij}}$${\displaystyle t_{ij}}$

Alternativamente, la función de resistencia del enlace puede incluirse en la función objetivo (y la función de costo total eliminada de las restricciones).

Ha evolucionado un enfoque de elección desagregado generalizado, al igual que un enfoque agregado generalizado. La gran cuestión es la de las relaciones entre ellos. Cuando usamos un modelo macro, nos gustaría saber el comportamiento desagregado que representa. Si estamos haciendo un microanálisis, nos gustaría conocer las implicaciones agregadas del análisis.

Wilson deriva un modelo similar a la gravedad con parámetros ponderados que dicen algo sobre el atractivo de los orígenes y destinos. Sin demasiadas matemáticas, podemos escribir declaraciones de probabilidad de elección basadas en el atractivo, y estas toman una forma similar a algunas variedades de modelos de demanda desagregada.

Integrar la demanda de viajes con la asignación de rutas

Desde hace mucho tiempo se reconoce que la demanda de viajes está influenciada por la oferta de la red. El ejemplo de la apertura de un nuevo puente donde no había ninguno antes de inducir tráfico adicional se ha notado durante siglos. Se han realizado muchas investigaciones para desarrollar métodos que permitan al sistema de predicción dar cuenta directamente de este fenómeno. Evans (1974) publicó una tesis doctoral sobre una combinación matemáticamente rigurosa del modelo de distribución de la gravedad con el modelo de asignación de equilibrio. La primera cita de esta integración es el trabajo de Irwin y Von Cube, según lo relatado por Florian et al. (1975), quienes comentan sobre el trabajo de Evans:

"El trabajo de Evans se parece un poco a los algoritmos desarrollados por Irwin y Von Cube ['Capacity Restraint in Multi-Travel Mode Assignment Programs' HRB Bulletin 347 (1962)] para un estudio de transporte de Toronto . Su trabajo permite la retroalimentación entre asignaciones congestionadas y distribución de viajes, aunque aplican procedimientos secuenciales. A partir de una solución inicial del problema de distribución, los viajes interzonales se asignan a las rutas iniciales más cortas. Para iteraciones sucesivas, se calculan nuevas rutas más cortas y sus longitudes se utilizan como tiempos de acceso para la entrada el modelo de distribución. Los nuevos flujos interzonales se asignan luego en alguna proporción a las rutas ya encontradas. El procedimiento se detiene cuando los tiempos interzonales para iteraciones sucesivas son casi iguales ".

Florian y col. propuso un método algo diferente para resolver la asignación de distribución combinada, aplicando directamente el algoritmo de Frank-Wolfe. Boyce y col. (1988) resumen la investigación sobre problemas de equilibrio de redes, incluida la asignación con demanda elástica.

Discusión

Un problema de tres enlaces no se puede resolver gráficamente y la mayoría de los problemas de la red de transporte involucran una gran cantidad de nodos y enlaces. Eash et al., Por ejemplo, estudiaron la red de carreteras en el condado de DuPage, donde había alrededor de 30.000 enlaces unidireccionales y 9.500 nodos. Debido a que los problemas son grandes, se necesita un algoritmo para resolver el problema de asignación y se utiliza el algoritmo de Frank-Wolfe (con varias modificaciones modernas desde que se publicó por primera vez). Comience con una asignación de todo o nada y luego siga la regla desarrollada por Frank-Wolfe para iterar hacia el valor mínimo de la función objetivo. (El algoritmo aplica sucesivas soluciones factibles para lograr la convergencia a la solución óptima. Utiliza un procedimiento de búsqueda eficiente para mover el cálculo rápidamente hacia la solución óptima.) Los tiempos de viaje corresponden a las variables duales en este problema de programación.

Es interesante que el algoritmo de Frank-Wolfe estuviera disponible en 1956. Su aplicación se desarrolló en 1968, y pasaron casi otras dos décadas antes de que el primer algoritmo de asignación de equilibrio se integrara en el software de planificación de transporte de uso común ( Emme y Emme / 2 , desarrollado por Florian y otros en Montreal). No quisiéramos sacar ninguna conclusión general de la observación de la aplicación lenta, principalmente porque podemos encontrar contraejemplos sobre el ritmo y el patrón de desarrollo de la técnica. Por ejemplo, el método simplex para la solución de problemas de programación lineal se elaboró ​​y aplicó ampliamente antes del desarrollo de gran parte de la teoría de la programación.

El enunciado del problema y el algoritmo tienen aplicaciones generales en la ingeniería civil : hidráulica, estructuras y construcción. (Ver Hendrickson y Janson 1984).

Estudios empíricos de elección de ruta

Los modelos de asignación de rutas se basan, al menos en cierta medida, en estudios empíricos sobre cómo las personas eligen rutas en una red . Dichos estudios se centran generalmente en un modo particular y utilizan modelos de preferencia declarada o de preferencia revelada .

Bicicleta

Los ciclistas se han encontrado a preferir designados carriles para bicicletas y colinas escarpadas evitar. ^[2]

Transporte público

El transporte público se ha considerado durante mucho tiempo en el contexto de la asignación de rutas ^[3] y se han realizado muchos estudios sobre la elección de rutas de tránsito. Entre otros factores, los usuarios del transporte público intentan minimizar el tiempo total de viaje, el tiempo o la distancia a pie y la cantidad de transferencias. ^[4]

Ver también

• Elección de ruta (desambiguación)

Notas

1. Wardrop, JG (1952). Algunos aspectos teóricos de la investigación del tráfico rodado . Institución de Ingenieros Civiles. 1 . págs. 325–378.
2. Hood, Jeffrey; Sal, Elizabeth; Charlton, Billy (2011). "Un modelo de elección de ruta en bicicleta basado en GPS para San Francisco, California". Cartas de transporte . 3 (1): 63–75. doi : 10.3328 / TL.2011.03.01.63-75 .
3. Liu, Yulin; Bunker, Jonathan; Ferreira, Luis (2010). "Modelado de elección de ruta de los usuarios de tránsito en la asignación de tránsito: una revisión" (PDF) . Reseñas de transporte . 30 (6): 753–769. doi : 10.1080 / 01441641003744261 - a través de Taylor y Francis Online.
4. Janosikova, Ludmila; Slavik, Jiri; Kohani, Michal (2014). "Estimación de un modelo de elección de ruta para el transporte público urbano utilizando datos de tarjetas inteligentes". Planificación y tecnología del transporte . 37 (7): 638–648. doi : 10.1080 / 03081060.2014.935570 .

Referencias generales

• Dafermos, Stella. C. y FT Sparrow The Traffic Assignment Problem for a General Network. "J. of Res. Of the National Bureau of Standards, 73B, págs. 91-118. 1969.
• Florian, Michael ed., Métodos de equilibrio del tráfico, Springer-Verlag, 1976.
• Eash, Ronald, Bruce N. Janson y David Boyce Equilibrium Trip Assignment: Advantages and Implications for Practice, Transportation Research Record 728, págs. 1–8, 1979.
• Evans, Suzanne P.. "Derivación y análisis de algunos modelos para combinar distribución y asignación de viajes". Transportation Research, Vol 10, págs. 37–57 1976
• Hendrickson, CT y BN Janson, "Una formulación de flujo de red común para varios problemas de ingeniería civil" Sistemas de ingeniería civil 1 (4), págs. 195-203, 1984