El algoritmo de Dijkstra permite calcular de forma eficiente el camino m·s corto desde un nodo fuente a todos los demás, en un grafo con arcos ponderados. En términos generales, para cada nodo destino, la solución del problema es un camino desde la fuente.
El modelado del comportamiento de pasajeros en una red de transporte público (representada como un grafo con arcos ponderados) introduce el concepto de hipercamino más corto. En este caso, la solución del problema es un camino que se divide en nodos que representan paradas por las que pasan varias líneas que sirven para llegar al destino (donde la división es proporcional a las frecuencias de las líneas). El problema de encontrar el hipercamino más corto sobre un grafo ponderado y con frecuencias, tiene un algoritmo tipo Dijkstra que lo resuelve de forma eficiente (tiempo polinomial en el tamaño del grafo).
Este concepto lo aplicamos al problema de optimización de frecuencias en sistemas de transporte público. Dado un trazado fijo de recorridos (líneas que determinan el grafo) y un conjunto de demandas (pares origen-destino), se busca encontrar la frecuencia óptima de cada lÌnea (inverso del tiempo de pasada de buses en cada línea). El objetivo es minimizar el tiempo total de viaje de los pasajeros (cuyo componente de espera es inversamente proporcional a las frecuencias) sujeto a una restricción de tamaño de flota disponible (que es directamente proporcional a las frecuencias).
En este trabajo proponemos una formulación de programación matemática de naturaleza lineal entera, que permite resolver el problema de forma óptima para ciudades pequeñas. Para ciudades medianas y grandes proponemos una heurística basada en Tabu Search, que utiliza un algoritmo tipo Dijkstra para calcular los hipercaminos más cortos que modelan el comportamiento de los pasajeros frente a los diferentes valores de frecuencias.
Las metodologÌas propuestas se prueban con un caso benchmark de la literatura, con un caso de estudio relativo a la ciudad de Rivera y con datos de la ciudad de Montevideo.
Trabajo en co-autoría con Héctor Martínez y María E. Urquhart.