Optimización De Viajes

OPTIMIZACIÓN MULTIOBJETIVO DE RECORRIDOS Y FRECUENCIAS EN EL TRANSPORTE PÚBLICO URBANO COLECTIVO
Departamento de Investigación Operativa, Instituto de Computación, Facultad de Ingeniería, Universidad de La República, Uruguay RESUMEN Se estudia el problema del diseño óptimo de recorridos y frecuencias para el transporte público urbano colectivo (Transit Network Design Problem). Enfoquesanteriores han utilizado, en su mayoría, modelos de objetivo único y algoritmos aproximados (ávidos y genéticos) para su resolución. Este trabajo propone la utilización de un modelo de optimización multiobjetivo y de un algoritmo aproximado de resolución basado en la metaheurística GRASP (Greedy Randomized Adaptative Search Procedures), que son extensiones y mejoras del modelo y algoritmo ávido propuestopor Baaj y Mahmassani (1991). El caso de estudio de Mandl fue usado para realizar pruebas y comparar resultados. Ahora se considera la validación con un caso de estudio real de dimensiones manejables, en cuya construcción se está trabajando. La información referente a la demanda se obtendrá mediante una encuesta a bordo de los buses, realizada en colaboración con personal de la Municipalidad deRivera, Uruguay. ABSTRACT We study the optimal design of routes and frequencies for urban public transport (Transit Network Design Problem). Most previous approaches have used single-objective models and approximated algorithms (greedy and genetic algorithms mainly) to solve them. We propose a multiobjective optimization model based in the Baaj and Mahmassani (1991) model, and a GRASP (GreedyRandomized Adaptative Search Procedures) metaheuristic, which extends the greedy algorithm proposed by the same authors and improves some of its operations. The study case of Mandl was used to test the algorithm and to compare results. We are working with a real study case of manageable dimensions, the transit network of Rivera, Uruguay. The demand information will be obtained by making an on boardbus survey, in collaboration with the municipality staff.

Antonio Mauttone, María Urquhart

1. INTRODUCCIÓN El diseño de recorridos y frecuencias en sistemas de transporte público urbano colectivo es generalmente una tarea llevada a cabo por las entidades reguladoras (estado, municipalidad). La planificación a este nivel se realiza a menudo en base a la experiencia y sentido común de lostécnicos responsables, eventualmente con el apoyo de guías y estándares; razón por la cual es de interés contar con herramientas automatizadas de apoyo para la mejora de tal proceso y de sus resultados. En este contexto, se estudia el Transit Network Design Problem (TNDP), que consiste en encontrar un conjunto óptimo de recorridos y frecuencias, bajo restricciones de cubrimiento de demanda, nivelesde servicio y disponibilidad de flota. Los objetivos a optimizar involucran los intereses de los usuarios (minimizar tiempos de viaje y espera) y de los operadores (minimizar costos operativos, tamaño de flota); estos objetivos son contrapuestos, es decir, una mejora en uno se logra solamente con un detrimento en el otro. En la mayoría de los trabajos publicados (con la salvedad del de Ceder eIsraeli, 1998) el problema de optimización multiobjetivo TNDP es formulado mediante un modelo de objetivo único; los diferentes objetivos se combinan usando coeficientes, que cumplen con los siguientes dos propósitos: a) realizar la conversión entre las diferentes unidades, y b) reflejar la importancia relativa de los objetivos contrapuestos. La conversión entre diferentes unidades es resuelta,generalmente, mediante la aplicación de modelos de estimación de valores subjetivos del tiempo (Ortúzar y Willumsen, 1996). La ponderación a priori de los diferentes objetivos, en cambio, plantea un problema de difícil resolución, ya que requiere de
108

información adicional, generalmente consiste en una decisión tomada por el responsable de la toma de decisiones. Los algoritmos de resolución...