Optimización convexa y métodos variacionales para estimar matrices origen destino - Chávez Hernández, María Victoria (Universidad Autónoma Metropolitana, 2019)
En este trabajo se incluye una revisión de los modelos y algoritmos más utilizados para estimar matrices de demanda o matrices origen destino (O-D) en redes de transporte público a partir de una pequeña cantidad de datos observados. Además, se proponen nuevos modelos y algoritmos para resolver este problema, los cuales mejoran los resultados y son más eficientes que los comúnmente utilizados hasta el momento por los ingenieros e investigadores del transporte. Considerando que no hay cambios bruscos de la demanda en el área geográfica de estudio, el objetivo de los modelos que aquí estudiamos es encontrar una nueva matriz O-D que sea lo más cercana posible a otra matriz O-D de referencia, la cual pudo haberse obtenido a partir de encuestas en los hogares o algún otro método. Esta nueva matriz O-D debe satisfacer dos condiciones más sus entradas deben ser no negativas y al llevar a cabo una asignación de tránsito con ella, se deben reproducir los datos observados. En la literatura (ver capítulo 1) se pueden encontrar modelos que de manera general consisten en minimizar la suma de un par de funciones que miden la distancia entre los valores de referencia y los estimados para la demanda y el flujo de pasajeros en algunos segmentos de la red. Una de las metodologías más estudiadas en la literatura es el método de (Spiess, 1990), en el cual se busca minimizar la distancia entre los volúmenes de tránsito (tráfico) observados y los que se obtienen después del método de asignación. Para resolver el problema, Spiess propuso un método de máximo descenso multiplicativo que preserva la estructura de una matriz conocida a priori y la no negatividad de las soluciones. En este trabajo se proponen dos nuevos modelos para resolver el problema, con base en un enfoque de control óptimo para resolver el problema inverso: un modelo de penalización (sección 3.2) y un modelo de Lagrangiano aumentado (sección 3.3). Estos modelos son inéditos dentro del ámbito de la investigación en transporte, y se construyeron tomando en cuenta la teoría de problemas inversos y de control en modelos descritos por ecuaciones diferenciales parciales. Ambos son modelos de optimización cuadrática, en donde se busca la matriz más cercana a una matriz obsoleta y que ajusta mediciones de flujo de pasajeros en un porcentaje pequeño de arcos de la red. Se utilizan algoritmos iterativos para resolver los problemas, los cuales demuestran ser más eficientes que los comúnmente utilizados en la investigación del transporte: un método de gradiente conjugado multiplicativo (para el modelo de penalización en la sección 3.2.2) y un método de ascenso dual y multiplicadores (para el modelo de Lagrangiano aumentado en la sección 3.3.1). Además, se demuestra que las soluciones del modelo penalizado convergen a la solución del modelo de Spiess, cuando el parámetro de penalización tiende a infinito (sección 3.2.1). Los resultados numéricos corroboran esta propiedad (sección 4.2). Cabe aclarar que en la literatura, el modelo de Spiess se considera uno de los más simples y eficientes, de hecho es utilizado ampliamente en el software comercial canadiense EMME, el cual es uno de los más exitosos y populares en el ambiente de transporte (capítulo 1, ecuaciones (1.2) y (1.3)). El modelo de penalización no solo generaliza el modelo de Spiess sino también es equivalente a los modelos de promedios pesados que tienen su base en la optimización cuadrática, pero con la ventaja de que los resultados teóricos permiten orientar el valor adecuado de los pesos, con base en su equivalencia con el parámetro de penalización (3.9). Al tener términos de penalización en ambos modelos y sus correspondientes algoritmos, es posible encontrar soluciones de manera estable ante perturbaciones o errores en los datos. Es decir son modelos de regularización que permiten resolver los problemas sub determinados, asociados al problema, sin amplificar el ruido o error en los datos o mediciones (ver el capítulo 4). Los dos modelos y sus correspondientes algoritmos son varias veces más rápidos que el modelo de Spiess y su algoritmo de descenso máximo multiplicativo; en particular, los resultados son más precisos cuando se utiliza el Lagrangiano aumentado para forzar la no negatividad de los coeficientes en la matriz O-D (tablas 4.2-4.8). Las propiedades anteriores permiten aplicar estas herramientas a la estimación de demanda en redes de transporte de gran tamaño. El tiempo de ejecución es del orden de segundos en una computadora personal de tamaño normal (Laptop); como se demuestra con los resultados para la red de la Zona Metropolitana del Valle de México, la cual incluye la Ciudad de México, los municipios conurbados del estado de México y un municipio del estado de Hidalgo (tabla 4.7). La utilización de supercómputo permitirá mejorar aun más los tiempos de ejecución. En la tabla 5.2, se puede ver que el modelo de Lagrangiano aumentado es el más completo, ya que aparte de ser más preciso y eficiente en redes de gran tamaño; puede ser generalizado para incluir otros aspectos a medir, como los volúmenes de transporte en segmentos de la red, los costos de viaje las producciones y atracciones en la demanda dentro de la red de transporte (ecuaciones (3.31) y (3.32), tabla 4.8). Los métodos aquí propuestos se probaron con dos redes: la red de tránsito de la ciudad de Winnipeg, que cuenta con 23716 pares O-D; y la red de tránsito de la Zona Metropolitana del Valle de México con más de 2 millones de pares O-D. En estos dos casos, consideramos una reducción del tamaño del problema (sección 3.4) extrayendo los coeficientes nulos en la matriz de referencia para reducir aun más el tiempo de cómputo.