Asignación de ruta

La asignación de rutas , la elección de rutas o la asignación de tráfico se refiere a la selección de rutas (también llamadas caminos) entre orígenes y destinos en redes de transporte . Es el cuarto paso en el modelo convencional de pronóstico de transporte , después de la generación de viajes , la distribución de viajes y la elección del modo . El análisis de intercambio zonal de la distribución de viajes proporciona tablas de viajes origen-destino. El análisis de elección del modo indica qué viajeros utilizarán qué modo . Para determinar las necesidades de infraestructura, los costos y los 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 realizar la asignación de tráfico (o de viajes). Supongamos que hay una red de autopistas y sistemas de transporte público y una adición propuesta. Primero queremos saber el patrón actual de retraso del tráfico y luego qué sucedería si se hiciera la adición.

Enfoques generales

Técnicas de larga data

El problema de estimar cuántos usuarios hay en cada ruta es antiguo. Los planificadores comenzaron a analizarlo detenidamente cuando se empezaron a desarrollar las autopistas y las vías rápidas. La autopista ofrecía un nivel de servicio superior al del sistema de calles local y desviaba el tráfico de este último. Al principio, la técnica empleada era la desviación. Se utilizaban índices de tiempo de viaje, teniendo en cuenta los costos, la comodidad y el nivel de servicio .

Los investigadores del Estudio de Transporte del Área de Chicago (CATS, por sus siglas en inglés) desarrollaron curvas de desviación para autopistas en comparación con calles locales. También se realizó un trabajo importante en California, ya que este estado contaba con experiencia previa en la planificación de autopistas. Además del trabajo relacionado con las curvas de desviación, el CATS abordó algunos problemas técnicos que surgen al trabajar con redes complejas. Uno de los resultados fue el algoritmo Bellman-Ford-Moore para encontrar las rutas más cortas en redes.

El problema que no abordó 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 usar una vía, esta se congestiona y el tiempo de viaje aumenta. Al no existir una forma de considerar esta retroalimentación, los primeros estudios de planificación (de hecho, la mayoría entre 1960 y 1975) la ignoraron. Utilizaron el algoritmo de Moore para determinar las rutas más cortas y asignaron todo el tráfico a dichas rutas. Esto se conoce como asignación de todo o nada, ya que o todo el tráfico de i a j se mueve a lo largo de una ruta o no lo hace.

La asignación de ruta única o de 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 existen numerosas rutas a considerar. Además, en última instancia, nos interesa el tráfico en los enlaces. Un enlace puede formar 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. Funciona así: el estudio de planificación tiene como objetivo respaldar las inversiones para garantizar un buen nivel de servicio en todas las vías. Utilizando los tiempos de viaje asociados al nivel de servicio previsto, los cálculos indican cómo fluirá el tráfico una vez implementadas las mejoras. Conociendo el volumen de tráfico en cada vía, se puede calcular la capacidad necesaria 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 de tráfico, se desarrollaron varios procedimientos de cálculo heurísticos . Una heurística procede de forma incremental. El tráfico que se va a asignar se divide en partes (normalmente 4). Se asigna la primera parte del tráfico. Se calculan nuevos tiempos de viaje y se asigna la siguiente parte del tráfico. El último paso se repite hasta que se haya asignado todo el tráfico. El sistema CATS utilizó una variación de este método; asignaba fila por fila en la tabla origen-destino.

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

0. Comience cargando todo el tráfico mediante un procedimiento de todo o nada.
1. Calcular los tiempos de viaje resultantes y reasignar el tráfico.
2. Ahora, comience a reasignar usando ponderaciones. Calcule los tiempos de viaje ponderados en las dos cargas anteriores y utilícelos para la siguiente asignación. La última iteración recibe una ponderación de 0,25 y la anterior, una 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 puede utilizarse para abordar el problema del equilibrio del tráfico. Supongamos que estamos considerando una red de carreteras. Para cada enlace hay una función que establece la relación entre la resistencia y el volumen de tráfico. La Oficina de Carreteras Públicas (BPR) desarrolló una función de congestión de enlace (arco) (o volumen-retraso, o rendimiento del enlace), que denominaremos S _a (v _a ).

$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 en flujo libre en el enlace a por unidad de tiempo
v _a = volumen de tráfico en el enlace a por unidad de tiempo (de forma algo más precisa: flujo que intenta utilizar el enlace a ).
c _a = capacidad del enlace a por unidad de tiempo
S _a (v _a ) es el tiempo medio de viaje de un vehículo en el enlace a

Existen otras funciones de congestión. El sistema CATS lleva tiempo utilizando una función diferente a la que usa el BPR, pero parece haber poca diferencia entre los resultados cuando se comparan las funciones de CATS y BPR.

Asignación de equilibrio

Para asignar tráfico a rutas y enlaces, necesitamos reglas, y existen las conocidas condiciones de equilibrio de Wardrop . ^{[ 1 ]} La esencia de estas condiciones radica en que los viajeros se esforzarán por encontrar la ruta más corta (de menor resistencia) desde el origen hasta el destino, y el equilibrio de la red se produce cuando ningún viajero puede disminuir el esfuerzo de viaje cambiando a una nueva ruta. Estas se denominan condiciones óptimas para el usuario, ya que ningún usuario obtendrá beneficio al cambiar de ruta 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.

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

sujeto a:

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

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

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

dónde $x_{ij}^{r}$ es el número de vehículos en la ruta r desde el origen i hasta el destino j . Por lo tanto, la restricción (2) dice que todo el viaje debe tener lugar: i = 1 ... n; j = 1 ... n

$\alpha _{ij}^{ar}$ = 1 si el enlace a está en la ruta r de i a j ; cero en caso contrario. Por lo tanto, la restricción (1) suma el tráfico en cada enlace. Hay una restricción para cada enlace en 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 de programación no lineal. Hay dos enlaces del nodo 1 al nodo 2, y existe una función de resistencia para cada enlace (véase la Figura 1). Las áreas bajo las curvas en la Figura 2 corresponden a la integración de 0 a a en la ecuación 1, y su suma es 220 674. Nótese que la función para el enlace b se representa en sentido inverso.

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

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

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

Figura 1: Red de dos rutas

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

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

En equilibrio hay 2152 vehículos en el enlace a 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 coincide con la solución de equilibrio. Las curvas permanecen sin cambios. Sin embargo, 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 mayor que la de la Figura 2 en la cantidad del área sombreada.

Integrar las opciones de viaje

El modelo de planificación del transporte urbano evolucionó como una serie de pasos a seguir, y se desarrollaron modelos para cada paso. En ocasiones, existían pasos anidados, como en el primer enunciado del modelo de Lowry . En algunos casos, se ha observado que los pasos pueden integrarse. En términos generales, los pasos abstraen las decisiones que pueden tomarse simultáneamente, y sería deseable replicar mejor esta abstracción en el análisis.

Los modelos de demanda desagregada se desarrollaron inicialmente para abordar el problema de la elección del modo de transporte. Este problema presupone que se ha decidido realizar un viaje, cuál será el destino y a qué hora se realizará. Estos modelos se han utilizado para tratar el contexto más amplio implícito. Normalmente, se desarrolla un modelo anidado, por ejemplo, comenzando con la probabilidad de realizar un viaje, luego examinando la elección entre destinos y, finalmente, la elección del modo de transporte. 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 para los esfuerzos a nivel agregado. Ese modelo contiene la restricción

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

donde el $c_{ij}$ son los costos de viaje del enlace, $t_{ij}$ Se refiere al tráfico en un enlace, y C es una restricción de recursos que debe dimensionarse al ajustar el modelo con datos. En lugar de usar esa forma de restricción, se puede usar la función de resistencia monótonamente creciente utilizada en la asignación de tráfico. El resultado determina los movimientos entre zonas y asigna el tráfico a las redes, lo cual tiene mucho sentido según cómo se imagina que funciona el sistema: el tráfico entre zonas depende de la resistencia ocasionada por la congestión.

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

Se ha desarrollado un enfoque generalizado de elección desagregada, al igual que un enfoque generalizado agregado. La gran incógnita reside en la relación entre ambos. Al utilizar un modelo macro, nos interesa conocer el comportamiento desagregado que representa. Si realizamos un análisis micro, nos interesa conocer las implicaciones agregadas del mismo.

Wilson desarrolla un modelo similar a la gravedad con parámetros ponderados que indican el atractivo de los orígenes y destinos. Sin recurrir a cálculos matemáticos complejos, podemos formular afirmaciones sobre la probabilidad de elección basadas en el atractivo, las cuales adoptan una forma similar a la de algunos modelos de demanda desagregada.

Integración de la demanda de viajes con la asignación de rutas.

Desde hace 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 antes no existía ninguno, que genera un aumento del tráfico, se ha observado durante siglos. Se han realizado numerosas investigaciones para desarrollar métodos que permitan al sistema de pronóstico tener en cuenta directamente este fenómeno. Evans (1974) publicó una tesis doctoral sobre una combinación matemáticamente rigurosa del modelo de distribución de 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 el trabajo de Evans:

El trabajo de Evans se asemeja en cierto modo 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 en Toronto . Su trabajo permite la retroalimentación entre la asignación de tráfico congestionado y la distribución de viajes, aunque aplican procedimientos secuenciales. Partiendo de una solución inicial del problema de distribución, los viajes interzonales se asignan a las rutas iniciales más cortas. En iteraciones sucesivas, se calculan nuevas rutas más cortas y sus longitudes se utilizan como tiempos de acceso para introducirlas en el modelo de distribución. Los nuevos flujos interzonales se asignan entonces, en cierta proporción, a las rutas ya encontradas. El procedimiento se detiene cuando los tiempos interzonales de iteraciones sucesivas son prácticamente iguales.

Florian et al. propusieron un método algo diferente para resolver la asignación de distribución combinada, aplicando directamente el algoritmo de Frank-Wolfe. Boyce et al. (1988) resumen la investigación sobre problemas de equilibrio de redes, incluyendo 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 redes de transporte involucran una gran cantidad de nodos y enlaces. Eash et al., por ejemplo, estudiaron la red vial del condado de DuPage, que tenía aproximadamente 30 000 enlaces unidireccionales y 9500 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 su primera publicación). Se comienza con una asignación de todo o nada, y luego se sigue la regla desarrollada por Frank-Wolfe para iterar hacia el valor mínimo de la función objetivo. (El algoritmo aplica soluciones factibles sucesivas 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.

Resulta interesante que el algoritmo de Frank-Wolfe estuviera disponible en 1956. Su aplicación se desarrolló en 1968, y transcurrieron casi dos décadas más 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 , desarrollados por Florian y otros en Montreal). No conviene extraer conclusiones generales de la observación sobre la lenta aplicación, principalmente porque podemos encontrar contraejemplos sobre el ritmo y el patrón de desarrollo de las técnicas. Por ejemplo, el método simplex para la solución de problemas de programación lineal se desarrolló 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. (Véase Hendrickson y Janson, 1984).

Estudios empíricos sobre la 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 . Estos estudios suelen centrarse en un modo de transporte específico y utilizan modelos de preferencia declarada o de preferencia revelada .

Bicicleta

Se ha observado que los ciclistas prefieren los carriles bici designados y evitan las cuestas empinadas. ^{[ 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 numerosos estudios sobre la elección de rutas de transporte. Entre otros factores, los usuarios del transporte público intentan minimizar el tiempo total de viaje, el tiempo o la distancia a pie y el número de transbordos. ^{[ 4 ]}

Véase también

Elección de ruta (desambiguación)

Notas

↑ Wardrop, JG (1952). Algunos aspectos teóricos de la investigación del tráfico rodado . Institution of Civil Engineers. Vol. 1. pp. 325– 378.
↑ Hood, Jeffrey; Sall, Elizabeth; Charlton, Billy (2011). "Un modelo de elección de ruta en bicicleta basado en GPS para San Francisco, California". Transportation Letters . 3 (1): 63– 75. doi : 10.3328/TL.2011.03.01.63-75 .
↑ Liu, Yulin; Bunker, Jonathan; Ferreira, Luis (2010). "Modelado de elección de ruta de los usuarios del transporte público en la asignación de transporte público: una revisión" (PDF) . Transport Reviews . 30 (6): 753–769 . doi : 10.1080/01441641003744261 – vía Taylor and Francis Online.
↑ 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". Transportation Planning and Technology . 37 (7): 638– 648. doi : 10.1080/03081060.2014.935570 .

Referencias generales

Dafermos, Stella C. y FT Sparrow El problema de asignación de tráfico para una red general." J. of Res. of the National Bureau of Standards, 73B, pp. 91-118. 1969.
Florian, Michael (ed.), Métodos de equilibrio de tráfico, Springer-Verlag, 1976.
Eash, Ronald, Bruce N. Janson y David Boyce, Asignación de viajes de equilibrio: ventajas e implicaciones para la práctica, Transportation Research Record 728, págs. 1–8, 1979.
Evans, Suzanne P. «Derivación y análisis de algunos modelos para combinar la distribución y asignación de viajes». Transportation Research, vol. 10, págs. 37-57, 1976.
Hendrickson, CT y BN Janson, "Una formulación común de flujo de red para varios problemas de ingeniería civil", Civil Engineering Systems 1(4), pp. 195–203, 1984

[1] Wardrop, JG (1952). Algunos aspectos teóricos de la investigación del tráfico rodado . Institution of Civil Engineers. Vol. 1. pp. 325– 378.

[2] Hood, Jeffrey; Sall, Elizabeth; Charlton, Billy (2011). "Un modelo de elección de ruta en bicicleta basado en GPS para San Francisco, California". Transportation Letters . 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 del transporte público en la asignación de transporte público: una revisión" (PDF) . Transport Reviews . 30 (6): 753–769 . doi : 10.1080/01441641003744261 – vía Taylor and 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". Transportation Planning and Technology . 37 (7): 638– 648. doi : 10.1080/03081060.2014.935570 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]