En este video veremos como hacer asignación de viajes en redes con congestión y para ello estudiaremos la transformada de Beckmann y un problema de optimización que nos permite encontrar los flujos de equilibrio de usuarios, tanto como los óptimos de sistema a partir de una formulación matemática. Veamos, entonces, cómo resolver esto. ¿Cómo encontramos los flujos de equilibrio de usuarios en una red congestionada? Sabemos que el equilibrio de usuario es tal que para cada par origen destino las rutas utilizadas tienen igual costo medio, mientras que aquellas sin flujo tienen un costo igual o mayores. Voy a describir primero la notación y después vamos a ver cómo ocupamos esta condición para encontrar una formulación matemática que nos permita encontrar la solución. Vamos a considerar una red con N centroides y a arcos Vamos a asumir que un par ordenado w es un par origen destino. Vamos a tener todos los pares origen destino que conecten todos los viajes de nuestra red. W mayúscula va a ser ese conjunto de todos los pares origen destino que existen en los datos de nuestra red de transporte. P va a ser el conjunto de todas las rutas percibidas, que son las que podría utilizar un viajero para ir desde su origen a su destino. P sub w es el subconjunto de las rutas para, que unen el par w. T sub w es la demanda para un par w, que es un par origen destino. H sub p y f sub a son los flujos en la ruta p y flujo en la ruta a respectivamente. C sub a es el costo del viaje por el arco a. C sub P es el costo de viaje en la ruta P y f es el vector de flujo en los arcos. H, el vector de flujo en rutas. ¿Cuáles son las reflexiones que debe satisfacer un problema de equilibrio usuario? En primer lugar debemos satisfacer que la demanda, que es conocida en un dato, en este caso, este T w de acá, es un dato conocido para efectos de nuestro problema. Recuerden que estamos haciendo asignaciones de tráfico. Con, estamos buscando un equilibrio de tráfico, donde conocemos la demanda. Por lo tanto, este T sub w es un dato conocido y lo que vamos a exigir es que el flujo de la ruta, de todas las rutas que unen el par w, acá estoy sumando sobre todos los caminos que unen el par w, el flujo total de esas rutas tiene que ser igual al total de viaje y con eso aseguramos que satisfaga la demanda y vamos a tener tantas restricciones de esta como pares origen destino tengamos. En segundo lugar, debemos satisfacer y tener una relación entre el flujo de los arcos con los flujos de las rutas. Y el flujo en un arco A, para cualquier arco de la red, va a ser igual que la suma de todos los flujos de las rutas que usan ese arco y donde delta a p es un indicador que nos dice si el arco A es utilizado o no por la ruta P, pero delta a p toma valor 1 si a pertenece a p y 0 si no. Y, además, tenemos restricciones de una negatividad para los flujos en arco y flujos en ruta. Esas son las restricciones del problema. Para formular el problema de equilibrio de usuarios, Beckmann utilizó el siguiente análisis, dijo, si yo tengo un total de viajes q en cualquier par origen destino, el flujo de las rutas tiene que ser igual. Voy a explicarlo intuitivamente a partir de un ejemplo muy sencillo, como el que tenemos acá, al lado izquierdo de la pantalla. Tenemos Q viajes, que van desde este origen a este destino y tienen dos rutas para efectos del análisis, q 1 y q 2. La ruta 1 y la ruta 2 con flujos q 1 y q 2 respectivamente. Si tomamos ese total de viajes Q, lo podemos graficar acá. Ese total de viajes Q acá, es igual a todo esto que está acá y ese total de viajes Q lo tenemos que repartir entre estas dos rutas. Hay distintas maneras de repartirlo. Si yo, por ejemplo, pusiera q 1 flujo acá y q 2 acá vería, y estos son las funciones de costo de las rutas, costo de la ruta 1, este es el costo de la ruta 2. Veríamos que el costo de la ruta 1 sería este de acá y el costo de la ruta 2 sería acá. Se nos haría un equilibrio. En equilibrio, estas dos rutas tendrían que tener igual costo para que los usuarios no pudieran encontrar una alternativa mejor y mantuviesen la ruta que están utilizando ahora. Si tenemos una asignación distinta, por ejemplo esta, el costo de esta ruta va a ser mayor que esta otra. Y Beckmann lo que se dio cuenta, es que si el planteaba un problema de minimizar las áreas bajo las curvas, en este caso decía, ¿cuál es el área mínima de las curvas? Uno encuentra que el área mínima de las dos curvas se da justo cuando los costos son iguales, para este caso, si ambas rutas se utilizan. Si ambas rutas no se utilizan, tenemos una asignación cualquiera, como la misma que teníamos acá, nos daríamos cuenta que cualquier asignación que hagamos va a tener mayor área que la asignación de equilibrio donde el área va a ser minimizada, que es cuando todos los usuarios ocupan la ruta 1, por ejemplo. Y con este análisis, lo extendió. Se puede demostrar que hay una formulación matemática que corresponde a minimizar el área bajo las curvas de costos medios, sujeto a las restricciones que habíamos visto anteriormente que nos permite encontrar un equilibrio usuario y en ese caso, entonces, podemos plantear el problema de equilibrio usuario o el principio, o la asignación correspondiente al principio de comportamiento de Wardrop tipo 1, sería igual al minimizar la suma sobre todos los arcos de la red, de la función de costos medios de ese arco, de la integral entre 0 y f a. Esto corresponde al área bajo la curva de costos medios hasta el flujo de equilibrio que es el que estamos buscando, sujeto a las restricciones que habíamos incluido anteriormente. Tenemos las mismas restricciones, satisfacemos que el total de viajes sea igual a T sub w, que el flujo de los arcos corresponda al flujo de las rutas y restricciones de una negatividad. Con eso hemos formulado el problema de equilibrio de usuarios. Asociado a este problema, uno podría pensar en cómo minimizar el costo total del sistema o buscar la, la asignación que minimiza costo del sistema. Este óptimo de sistema con demanda fija se puede obtener minimizando el costo total. ¿Cuál sería el costo total? Tendríamos esta función objetiva acá, donde Z es igual al a la sumatoria para todos los arcos del costo de ese arco por el flujo de ese arco, y eso es lo que estarían pagando todos los usuarios de a red. Es fácil hacer esa demostración. Mostramos acá que esto se puede reescribir como la integral del diferencial del costo total del arco respecto a xdx. Este diferencial con la integral y los dx se cancelarían. Bien, llegamos a la misma función de acá, costo total del arco A. Ahora, si uno desarrolla esto, se puede dar cuenta que la derivada del costo total de un arco con respecto al flujo es igual al costo marginal de ese arco y, por lo tanto, el problema del óptimo sistema es equivalente a minimizar la suma sobre todos los arcos de las integrales los costos marginales en vez de las de costos medios. Por lo tanto el problema será minimizar esta nueva función objetiva sujeto a las mismas restricciones. ¿Cómo encontramos, entonces, el óptimo sistema? Bueno, podríamos ocupar un mismo paquete computacional, cambiando las funciones de costo medio, entregándoles, en este caso, funciones de costo marginal. En resumen, tenemos dos problemas matemáticos que pueden introducirse en paquetes computacionales de optimización y que nos van a entregar asignaciones de equilibrio de usuario o asignaciones correspondientes con el óptimo sistema. Otras heurísticas para encontrar una asignación eficiente, o métodos para resolver el problema anterior. Una es una asignación incremental. En este caso, yo divido la matriz en varias partes, todas iguales y voy asignando de a pedazos. Por ejemplo, podría entregar primero el 5% de la matriz, asignarlo a las rutas mínimas, recalcular los flujos de las rutas, con ese flujo ya asignado y volver a asignar otro 5% así, hasta completar el total de viajes. Con eso uno consigue soluciones bastante cercanas a el flujo de equilibrio de usuario. Otro método para resolver el problema anterior y el más utilizado actualmente, es el método de Frank Wolfe, que está implementado en una gran cantidad de paquetes computacionales Algunos softwares comerciales que permiten resolver equilibrio de usuario son Emme de, y ahí tenemos la página web. TransCad. En el caso de Chile es bastante común ocupar Estraus.
