Abstract

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.

Abstract

The transport of students presents important challenges in the case of the city of Bogota, where an important cluster of schools is located in one zone, but there is only one road connecting these schools to residential zones. Thus, traffic congestion is high, generating long travel times for students, high operational costs, and mobility problems. This paper studies the impacts of a cooperative strategy between logistics operators using a mixed integer programming mathematical model, to find the optimal design of school routes on a network with the topology that describes the aforementioned road system. Two strategies are compared: a mixed loads strategy, where students from different schools share buses; and a single load strategy, where students from different schools cannot share buses. The objective is to minimize the total operational costs while satisfying the schools’ time windows. Comparative results of the two models using exact and heuristic approaches are presented. Resumen El transporte de estudiantes tiene desafíos importantes en el caso de la ciudad de Bogotá, donde un grupo de escuelas se encuentra en una zona, pero sólo hay una carretera que las conecta con zonas residenciales. Por lo tanto, la congestión del tráfico es alta, generando largos tiempos de viaje, altos costos de operación y problemas de movilidad. Se estudia el impacto de una estrategia cooperativa entre operadores logísticos a través de modelos de programación de entera mixta, para encontrar el diseño óptimo de rutas escolares en una red con la topología que describe el mencionado sistema vial. Se comparan dos estrategias: Cargas mixtas y carga única, donde los estudiantes de diferentes escuelas comparten o no los autobuses disponibles. El objetivo es minimizar los costos totales de operación respetando las ventanas de tiempo de las escuelas. Se presentan los resultados comparativos de los modelos usando enfoques exactos y heurísticos. Document type: Article