Técnicas de solución para modelos integrados de optimización de transporte público : programación lineal entera para la planificación de líneas con enrutamiento integrado de pasajeros en la optimización de sistemas de transportación pública.

Abstract

The models that integrate the phases of line planning and passenger routing aim to establish the lines to be operated in a public transportation system along with their frequencies, in such a way that they cover the entire transport demand while minimizing operating costs and ensuring a certain level of service, reflected in the average passenger travel time from it's origin station to it's destiny.

Although there are theoretical ways to model an integrated problem using integer linear programming, in practice, it isn't useful to use these models because them to be enormous and become unsolvable within a reasonable time frame.

The work focuses on the study of two heuristics, built on ideas proposed in Scholl's doctoral thesis, to find feasible solutions for an integer linear programming model that integrates the line planning phase with the passenger routing phase.

The first heuristic starts with the entire line pool, and in each iteration, it eliminates the least useful line. Three different criteria were taken into account to determine the utility of a line in each iteration. On the other hand, the second heuristic starts with an empty set of lines, and in each iteration, it must decide which line to enter and with what frequency.

Both heuristics were computationally implemented using the Python API of the Gurobi solver and tested on four instances obtained from the OpenLinTim project, two instances were simulated dataset and the other two were instances of real cities. The results of the computational experiments and the conclusions obtained were reported.