Búsqueda tabú para determinar frecuencias en el transporte público

Abstract

En esta tesis se estudia el problema de determinación de frecuencias en el trasporte público utilizando un enfoque de optimización combinatoria. La determinación de frecuencias es llevada a cabo en las etapas de planificación estratégica y táctica de los sistemas de transporte público. El problema consiste en determinar el intervalo de tiempo entre pasadas de buses subsecuentes de cada línea, considerando su ruta y la demanda de viajes. Las frecuencias impactan tanto a los usuarios como operadores. A los usuarios en el tiempo de espera. A los operadores en el costo de operación, dado que principalmente su costo está determinado por el tamaño de la flota requerida. En este trabajo se consideran dos formulaciones para el problema: objetivo único y multiobjetivo. La formulación de objetivo único minimiza el tiempo total de viaje de los usuarios sujeto a una restricción en el tamaño de flota, mientras que la formulación multiobjetivo extiende la de objetivo único removiendo la restricción. Se proponen tres algoritmos para la resolución aproximada del problema basados en la metaheurística Búsqueda Tabú. Para la formulación de objetivo único los dos primeros algoritmos implementados producen una única solución, mientras que para la multiobjetivo el algoritmo produce un conjunto de soluciones no dominadas que representan diferentes compromisos entre los intereses de los usuarios y operadores. La propuesta es probada utilizando cuatro instancias reales del problema de diferentes dimensiones que varían entre una decena y una centena de líneas de transporte. Se compara contra resultados exactos cuando están disponibles. Se hace un estudio computacional exhaustivo para determinar el comportamiento de los algoritmos propuestos. Los resultados obtenidos muestran que la metodología propuesta es capaz de mejorar las soluciones actuales en términos de tiempo de viaje y tamaño de flota. Además, para el caso de la variante multiobjetivo el método propuesto presenta diferentes soluciones alternativas con respecto al conflicto de intereses de los usuarios y operadores.

In this thesis we study the transit frequency setting problem using a combinatorial optimization approach. Frequency setting takes place at the strategic and tactical planning stages of public transportation systems. The problem consists in determining the time interval between subsequent buses of each line, taking into account its route and trip demand. Frequencies impact overboth users (in the waiting time), and operators (their cost is mainly determinedby the size of the fleet required). In this work two formulations are considered for the problem: single-objective and multi-objective. The single-objective formulation minimizes the total travel time of users subject to a restriction on the fleet size, while the multi-objective formulation extends the single-objective formulation by removing the restriction. Three algorithms based on the Tabu Search metaheuristic are proposed to solve the problem approximately. For the single-objective formulation, the first two algorithms implemented produce a single solution, while for the multi-objective one the algorithm produces a set of non-dominated solutions that represent different compromises between the interests of users and operators. The proposal is tested using four real instances of the problem of different size, ranging from a dozen to one hundred transit lines. It is compared against exact results when they are available. A comprehensive computational study is done to determine the behavior of the proposed algorithms. The results obtained show that the proposed methodology is capable of improving current solutions in terms of travel time and fleet size. In addition, in the case of the multi-objective variant, the proposed method presents different alternative solutions with respect to the conflict of interests of users and operators.