Sesión Análisis Numérico y Optimización

Diciembre 14, 11:20 ~ 11:40

Estimación de la matriz OD utilizando el algoritmo de Dial

Corrales, Lucas

El proceso de planificación del tráfico urbano supone una secuencia de numerosos pasos, entre ellos, la recolección de información relevante. Para tomar decisiones respecto del sistema de transporte es necesario conocer el patrón de viajes sobre la red, es decir, el número de viajes que se realizan entre cada par origen-destino (OD). Estas cantidades son guardadas en lo se conoce como matriz OD. Obtener esta información puede ser muy costoso si se realiza a través de encuestas o métodos similares de recolección de datos. Sin embargo, si tenemos alguna información disponible, como el flujo observado en algunos arcos de la red o una matriz origen-destino vieja, es posible diseñar un problema de optimización cuya solución resuelva el problema de ajuste de demanda (PAD). El modelo del PAD puede variar dependiendo de las características del sistema de transporte considerado. En primer lugar, debemos elegir entre una red congestionada o descongestionada y el problema de asignación de tráfico que gobierna a los usuarios de la red (asignación todo o nada, equilibrio del usuario determinístico, asignación estocástica, etc.). En segundo lugar, la información disponible para estimar la demanda puede conducir a diferentes funciones objetivos, al igual que el método estadístico elegido. Respecto de redes congestionadas, el primer modelo del PAD que se encuentra en la literatura es el trabajo de Nguyen en el año 1977. En los trabajos de Spiess, Cheen y Florian, Yang, Sasaki, Iida, y Asakura, Codina y Barceló y Lundgren y Peterson se utilizan diferentes enfoques para aproximar el gradiente de la función objetivo. En el trabajo de Walpen, Mancinelli y Lotito (WML) es presentada una heurística en cuyo esquema es necesario resolver dos problemas de asignacin de tráfico, tanto para calcular la dirección de descenso como para chequear la factibilidad de la nueva aproximación durante una búsqueda lineal. El presente trabajo busca mejorar el rendimiento de la herustíca propuesta por WML utilizando un algoritmo basado en el origen para resolver los problemas de asignación. El primer enfoque utilizado para la resolución del problema de asignación de tráfico fue la minimización de una función convexa sujeta a restricciones lineales a través de la adaptación del algoritmo de Frank Wolf. La implementación de este algoritmo es sencilla y además utiliza poca memoria. Sin embargo el algoritmo no tiene una buena convergencia cuando se le exige un nivel de precisión aceptable. En los últimos 25 años han sido publicados varios algoritmos que buscan mejorar la precisión en la resolución del problema de asignación. En 1992 Larsson y Patriksson presentaron un algoritmo llamado disaggregate simplicial decomposition (DSD) basado en rutas, que es el útilizado en el trabajo de WML. Jayakrishnan et al. (1994) también presentaron un nuevo algoritmo basado en rutas, sin embargo este tipo de algoritmos requiere de una gran cantidad de memoria para el almacenamiento de las rutas, lo que resulta un problema para redes reales. Para mejorar este aspecto es que fueron creados una nueva generación de algoritmos basados en el origen, en los que se utiliza un enfoque de rutas pero estas no se almacenan lo que los vuelve precisos pero sin demasiados costos de memoria. Entre estos algoritmos podemos mencionar el OBA de Bar-Gera publicado en 2002 y el algoritmo B de Dial publicado en el 2006. En este trabajo vamos a utilizar el algoritmo B de Dial.

Autores: Corrales, Lucas / LOTITO, Pablo Andrés.