Problemas de flujo en redes: aplicación a redes de transporte urbano

Prof. Cristián Cortés


Resumen:

   En este curso se revisarán los modelos de flujo en redes que se basan en el problema genérico de flujo a costo mínimo, cuáles son el problema de transporte, los problemas de rutas mínimas, problema de flujo máximo, problema genérico convexo separable, entre los más conocidos. Se enseñarán técnicas de optimización ad-hoc en la resolución de la mayoría de estos problemas y se revisará en detalle los algoritmo de rutas mínimas en sus diversas versiones. Se introducirá el concepto de equilibrio en redes urbanas, y de que forma este problema puede finalmente plantearse como un problema de flujo en redes, pero con funciones de costo separable convexas. Se introducirá el algoritmo de solución para equilibrio con funciones de costo deterministas (tiempo de viaje en arcos) pero dependientes del flujo en los arcos. Este algoritmo es un método de combinaciones convexas, basado en encontrar dirección de descenso y tamaño del paso (algoritmo de Frank Wolfe) en cada iteración. El subproblema para encontrar la dirección de descenso en cada iteración resulta ser un problema de rutas mínimas. Los alumnos tendrán que implementar algunas versiones más simples de estos modelos (rutas mínimas y equilibrio) sobre redes reales estratégicas, correspondientes a la ciudad de Chicago, Estados Unidos.

Material