Models and algorithms for the optimal design of bus routes in public transportation systems

In this thesis we study models and algorithms for the optimal design of bus routes in urban public transportation systems. The problem known as TNDP (Transit Network Design Problem) consists in determining the number and itinerary of public transportation lines and their corresponding frequencies, in terms of a given infrastructure of streets and stops. The solutions should satisfy a given origin-destination demand and should take into account the interests of users and operators and a given set of physical, policy and budgetary constraints. We propose an explicit mixed integer linear programming formulation which incorporates the waiting time and the existence of multiple lines in the behavior of the passengers.Then, we discuss the impact in the structure of the model of adding transfer, infrastructure and bus capacity constraints. We apply the model (using a standard solver) to very small test cases as well as to a real one, related to a small-sized city comprising 13 bus lines. In order to deal with cases of larger sizes, we propose a greedy constructive algorithm that produces a set of routes that are convenient for both users and operators, taking into account constraints related to transfers. By using a real test case, we show that the proposed algorithm improves results from the state of the art.As a further extension, we represent the existence of the conflicting objectives of users and operators using a multi-objective combinatorial optimization model for the TNDP. This new model is solved by a metaheuristic that exploits the multi-objective nature of the problem in order to solve it eficiently. By using a benchmark test case and a real one, we show that the proposed algorithm improves results from the state of the art and produces solutions with characteristics comparable to the real one. Objective values of both constructive and metaheuristic algorithms are compared with values corresponding to reference solutions; for the first one we compare against optimal solutions obtained with the mathematical formulation, while for the second one we compare with the solution operating the public transportation system of the city corresponding to the real test case. Finally we discuss the relationships between the diferent contributions of this thesis and we comment several issues related to the application of the proposed methodologies to real cases. We also give some opinions and recommendations concerning future developments in this research field.En esta tesis se estudian modelos y algoritmos para el diseño óptimo de recorridos de buses en sistemas de transporte público urbano colectivo. El problema conocido como TNDP (Transit Network Design Problem) consiste en determinar el número y el itinerario de líneas de transporte público y sus correspondientes frecuencias, en términos de una infraestructura dada de calles y paradas. Las soluciones deben satisfacer una demanda origen-destino dada y deben tener en cuenta los intereses de los usuarios y de los operadores y un conjunto dado de restricciones físicas, políticas y de presupuesto. Se propone una formulación explícita de programación lineal entera mixta, que incorpora el tiempo de espera y la existencia de múltiples líneas en el comportamiento de los pasajeros. Seguidamente se discute el impacto en la estructura del modelo, al agregar restricciones de transbordos y de capacidad de la infraestructura y de los buses. El modelo se aplica (usando un solver estándar) a casos de prueba muy pequeños, así como a uno real relativo a una ciudad pequeña que consta de 13 líneas de buses. Con el propósito de atacar casos de mayor tamaño, se propone un algoritmo constructivo ávido que produce un conjunto de recorridos que son convenientes tanto para los usuarios como para los operadores, teniendo en cuenta restricciones de transbordos. Utilizando un caso de prueba real, se muestra que el algoritmo propuesto mejora resultados del estado del arte. Como una extensión del algoritmo constructivo, se representa la existencia de los objetivos en conflicto de usuarios y operadores usando un modelo de optimización combinatoria multi-objetivo para el TNDP.Este nuevo modelo se resuelve con una metaheurística que explota la naturaleza multi-objetivo del problema para resolverlo eficientemente. Utilizando un caso de prueba de referencia existente en la literatura y uno real, se muestra que el algoritmo propuesto mejora resultados del estado del arte y produce soluciones de características comparables a las del sistema real. Los valores objetivo del algoritmo constructivo y de la metaheurística se comparan con valores correspondientes a soluciones de referencia; en el primer caso se compara contra soluciones óptimas obtenidas con la formulación matemática, mientras que para el segundo se compara contra la solución que opera el sistema de transporte público de la ciudad correspondiente al caso de prueba real. Finalmente se discuten las relaciones entre las diferentes contribuciones de esta tesis y se comentan varias cuestiones relacionadas a la aplicación de las metodologías propuestas a casos reales. También se formulan algunas opiniones y recomendaciones en relación a futuros desarrollos de éste tópico de investigación