Técnicas de solución para modelos integrados de optimización de transporte público : Modelos de programación lineal entera para la calendarización de viajes y enrutamiento de pasajeros.

Abstract

The timetabling problem is an essential part of public transportation planning. It involves setting the arrival and departure times at each station for each transportation unit in a way that minimizes the average travel time for passengers in the transportation system. Since travel times depend on the routes chosen by passengers within the system, some previous works have proposed an integrated approach to timetabling along with passenger routing. Solving these integrated models implies a computational challenge because of the number of variables that take part in the models. In this current work, two heuristics, known as UB and LB, are implemented. These heuristics were proposed in a previous study to obtain upper and lower bounds for the integrated timetabling and passenger routing model. The achievement of these heuristics is due to the simplification of the initial problem by reducing origin-destination pairs in two different ways, thereby creating two new integer linear programming problems of lower complexity. These implemented algorithms were first applied to simulated instances and then used on real-world instances known for their large size and difficulty in solving optimally. These instances were obtained online, and they are free to download. Finally, the quality of the implementation of one of the heuristics, to be specific the LB heuristic, was tested by comparing it with other available implementations. The number of variables and the value of the objective function were used for comparing the implementations over the same instances. The available implementations were obtained from open-access software known as LimTim.