[MÚSICA] En el módulo anterior estudiamos el problema de asignación para caso donde los arcos de la red, que representa el sistema de transporte estudiado, no presenta congestión. Es decir, donde los tiempos de viaje son fijos y conocidos. En este módulo, estudiaremos qué sucede cuando los arcos sí presentan, en efecto, congestión. En particular, en el video de hoy, definiremos un caso particular de este problema, el problema de asignación estándar. Comencemos por recordar en qué consiste el problema de asignación. En esencia, el problema de asignación corresponde en determinar para una red conocida y una matriz de viajes dada qué rutas seguirán los usuarios para llegar a sus destinos. En el módulo anterior, estudiamos el problema de asignación para casos donde no existe congestión en la red. Es decir, donde los tiempos de viaje de los arcos son independientes del flujo que acarrean, es decir, son constantes. Tomemos para ilustrar este tipo de asignación la red estudiada en el capítulo anterior. Supongamos que sobre esta red, cuyos tiempos de viaje constantes se entregan sobre cada arco, deseamos asignar 10 unidades de flujo, desde el nodo A al nodo P, y 10 desde N a G. ¿Cuáles serán los flujos resultantes sobre la red? Para responder esta pregunta, necesitamos determinar para cada par origen-destino, con demanda por asignar, cuál es la ruta de costo mínimo que lo conecta. Esta ruta mínima puede ser obtenida utilizando el algoritmo de Dijkstra. En el módulo anterior, mostramos que la ruta mínima de A a P es la siguiente. El tiempo o costo de viaje de esta ruta es 151. La ruta mínima de ir de N a G, por su parte, es la siguiente, con un tiempo total de viaje de 127. Notemos que el arco F G, marcado en morado, pertenece a ambas rutas mínimas. Los flujos en arco resultantes tras asignar 10 unidades de flujo sobre cada ruta son los siguientes. Supongamos ahora que la red presenta congestión en sus arcos, es decir, que los tiempos de viaje son función del tiempo que circula por ellos. La relación entre el tiempo de viaje y el flujo en arco puede ser modelada utilizando funciones tipo VPR, como han sido introducidas en el primer módulo. Para mantener la simpleza del ejemplo, tenemos que el tiempo de viaje de cada arco puede ser modelado como un tiempo fijo de viaje, alfa, más un quinto del flujo F que circula por él, como se muestra en la ecuación. Calculemos cuáles son los tiempos de viaje de cada arco con el flujo de la asignación a ruta mínima que habíamos obtenido. Por ejemplo, para el arco A E, el tiempo fijo de viaje es 23, y le sumamos 10 sobre 5, es decir, 2, así obtenemos un tiempo de 25. Repetimos este procedimiento para cada arco, obteniendo nuevos tiempos de viaje sobre la red. Dado que los tiempos de viaje han cambiado, debemos recalcular los tiempos de cada ruta. Actualizamos estos valores. La asignación que habíamos calculado para el caso sin congestión predice, para esta red, que los viajes de A a P toman la ruta roja, tardando 165 minutos, y que los viajes de N a G, toman la ruta azul, demorando 139. Veremos con atención el gráfico. ¿Qué tan realista es esta asignación? En particular, los viajes que utilizan la ruta roja, ¿podrían encontrar una forma más rápida de hacer su viaje? Efectivamente. Los viajeros de la ruta roja podrían mejorar su tiempo de viaje de varias maneras. Por ejemplo, miremos esta ruta. El costo de ir de G a L por la ruta roja pasando por H es 54. El costo de ir de G a L por la ruta verde pasando por K es de 58. Por lo tanto, podemos usar la ruta verde de abajo para ir de A a P ahorrando una unidad de tiempo. Este ejemplo ilustra cómo empresas de congestión no basta asignar viajes de ruta mínima. Esto sucede porque al asignar los viajes, los costos de la ruta aumentan producto de la congestión, dando por lugar a que viajeros podrían encontrar mejores maneras de viajar invalidando la asignación calculada. ¿Cómo podemos entonces resolver el problema de asignación cuando los arcos presentan congestión? Para responder a esta pregunta, debemos primero definir qué condición debe satisfacer una asignación para representar, en forma razonable, la realidad. Pista del ejemplo anterior, ¿qué condición pudiéramos exigir a una asignación para predecir en forma razonable el comportamiento de los usuarios? Una asignación razonable debiese dejar satisfecho a cada uno de los viajeros de la red, sin generar incentivos para que deseen cambiar su elección. En palabras más sencillas, buscamos una solución donde ningún usuario puede cambiarse su ruta actual a una ruta de menor costo. Esta condición, que estudiaremos en detalle en la próxima clase, corresponde a la condición de equilibrio de tráfico del problema. En este módulo, nos concentramos en estudiar un tipo especial de problema de asignación con congestión, conocido como el problema de asignación estándar. Este es un problema de asignación con congestión cuyas funciones de costos son diagonales, es decir, donde el costo de tiempo o viaje en cada arco depende únicamente del flujo propio. El objetivo del problema de asignación estándar es encontrar una asignación que satisfaga las condiciones de equilibrio de tráfico, donde ningún usuario tenga un incentivo para cambiarse de ruta. En este video, introdujimos el problema de asignación con congestión. Por medio de un ejemplo, pudimos ver una primera dificultad de este problema, proveniente del hecho que la asignación a rutas mínimas deja de ser suficiente para modelar redes en presencia de congestión, dado que el aumento de costo producto de la congestión puede acarrear la aparición de atajos para romper el equilibrio buscado. Definimos además el problema de asignación estándar como el problema de asignación con congestión en que las funciones de costo son diagonales, es decir, dependen únicamente del propio flujo. Esto es todo por hoy. Nos vemos la próxima clase. [AUDIO_EN_BLANCO]
