La asignación de ruta , elección de ruta o asignación de tráfico se refiere a la selección de rutas (también llamadas rutas) entre orígenes y destinos en las redes de transporte . Es el cuarto paso en el modelo de pronóstico de transporte convencional , después de la generación de viajes , la distribución de viajes y la elección de 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 de modo indica qué viajeros utilizarán qué modo . Para determinar las necesidades de 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 realizar una asignación de tráfico (o viaje). Supongamos que hay una red de carreteras y sistemas de tránsito y una ampliación propuesta. Primero queremos saber el patrón actual de retrasos en el tráfico y luego qué pasaría si se hiciera la adición.
El problema de estimar cuántos usuarios hay en cada ruta viene de lejos. Los planificadores empezaron a analizarlo detenidamente a medida que se empezaron a desarrollar autopistas y autopistas. La autopista ofrecía un nivel de servicio superior al 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, atenuados por consideraciones de costos, comodidad y nivel de servicio .
Los investigadores del Estudio de Transporte del Área de Chicago (CATS) desarrollaron curvas de desvío para autopistas versus calles locales. También hubo mucho trabajo en California, ya que California tuvo experiencias tempranas con la planificación de autopistas. Además de trabajos de tipo desvío, el CATS abordó algunos problemas técnicos que surgen cuando se trabaja con redes complejas. Uno de los resultados fue el algoritmo Bellman-Ford-Moore para encontrar caminos más cortos en redes.
El problema que el enfoque de desvío no resolvió fue la retroalimentación de la cantidad de tráfico en enlaces y rutas. Si muchos vehículos intentan utilizar una instalación, ésta se congestiona y el tiempo de viaje aumenta. A falta de alguna forma de considerar la retroalimentación, los primeros estudios de planificación (de hecho, 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. Esto 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 del todo o nada o del camino más corto 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 numerosos caminos a considerar. Además, en última instancia, nos interesa el tráfico de enlaces. Un enlace puede ser parte de varios caminos y el tráfico a lo largo de los caminos debe sumarse enlace por enlace.
Se puede argumentar a favor del enfoque de todo o nada. Dice así: El estudio de planificación pretende apoyar 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.
Para tener en cuenta el efecto de la carga de tráfico sobre los tiempos de viaje y los equilibrios de tráfico, se desarrollaron varios procedimientos de cálculo heurístico . Una heurística avanza de forma incremental. El tráfico a 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 CATS 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.
Estos procedimientos parecen funcionar "bastante bien", pero no son exactos.
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 existe 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 (o retardo de volumen o rendimiento del enlace) del enlace (arco), que denominaremos S a (v a )
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 del CATS y del BPR.
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 esto es que los viajeros se esforzarán por encontrar el camino más corto (de menor resistencia) desde el origen al destino, y el equilibrio de la red ocurre cuando ningún viajero puede disminuir el esfuerzo de viaje cambiando a un nuevo camino. Estas se denominan condiciones óptimas para el usuario, ya que ningún usuario se beneficiará al 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
sujeto a:
¿Dónde está el número de vehículos en el camino r desde el origen i hasta el destino j ? Entonces, la restricción (2) dice que todos los viajes deben realizarse – i = 1 ... n; j = 1 ... norte
= 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) garantiza que no haya tráfico negativo.
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 (ver 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, suman 220,674. Tenga en cuenta que la función para el enlace b se traza en dirección inversa.
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: alrededor de 63.
La Figura 3 ilustra una asignación de vehículos que no es consistente con la solución de equilibrio. Las curvas no cambian. 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 mayor que la solución de la Figura 2 en el área del área sombreada.
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 había pasos dentro de pasos, como fue el caso de la primera afirmación del modelo de Lowry . En algunos casos, se ha observado que se pueden integrar pasos. En términos más generales, los pasos se abstraen de decisiones que pueden tomarse simultáneamente, y sería deseable replicar mejor eso en el análisis.
Los modelos de demanda desagregada se desarrollaron por primera vez para tratar el problema de la elección del 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. Normalmente, se desarrollará un modelo anidado, empezando por la probabilidad de realizar un viaje, examinando luego la elección entre lugares y luego la elección del modo. La época del viaje es un poco más difícil de tratar.
El modelo de entropía doblemente restringida de Wilson ha sido el punto de partida de los esfuerzos a nivel agregado. Ese modelo contiene la restricción.
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 debe dimensionarse al ajustar el modelo con datos. En lugar de utilizar esa forma de restricción, se puede utilizar la función de resistencia monótonamente creciente utilizada 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 desde la forma en que uno imaginaría que funciona el sistema: el tráfico de zona a zona 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 costo total eliminarse de las restricciones).
Ha evolucionado un enfoque de elección desagregada generalizada, al igual que un enfoque agregado generalizado. La gran cuestión es la de las relaciones entre ellos. Cuando utilizamos 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 éstas toman una forma similar a algunas variedades de modelos de demanda desagregada.
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 había ninguno, lo que induce tráfico adicional, se ha observado durante siglos. Se han realizado muchas investigaciones para desarrollar métodos que permitan que el sistema de pronóstico tenga 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, relatado por Florian et al. (1975), quienes comentan 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 cierta proporción a las rutas ya encontradas. El procedimiento se detiene cuando los tiempos interzonales para las iteraciones sucesivas son casi iguales.
Florián 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, incluida la asignación con demanda elástica.
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 de carreteras del 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 su primera publicación). 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 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.
Es interesante que el algoritmo de Frank-Wolfe estuvo 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 fuera integrado en el software de planificación de transporte de uso común (Emme y Emme/2, desarrollado por Florian y otros en Montreal). No queremos sacar ninguna conclusión general a partir de la observación de la aplicación lenta, principalmente porque podemos encontrar ejemplos contrarios 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 planteamiento del problema y el algoritmo tienen aplicaciones generales en toda la ingeniería civil : hidráulica, estructuras y construcción. (Ver Hendrickson y Janson 1984).
Los modelos de asignación de rutas se basan, al menos hasta cierto punto, en estudios empíricos sobre cómo las personas eligen rutas en una red . Estos estudios generalmente se centran en un modo particular y utilizan modelos de preferencia declarada o de preferencia revelada .
Se ha descubierto que los ciclistas prefieren los carriles designados para bicicletas y evitan las colinas empinadas. [2]
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 caminada y el número de transbordos. [4]
