Frequency optimization in public transportation with strict capacity constraints. A bilevel programming approach

Abstract

In this thesis, we consider the problem of frequency optimization in public transit systems based on buses. The objective of the problem is to determine the time interval between subsequent buses for a set of transportation lines. The solutions should satisfy a given origin-destination demand while considering the interests of users and operators in the context of constraints pertaining to infrastructure, budget, and service performance. To consider congestion on the transportation lines (that is, when the lines operate at the limit of their capacities in relation to the attracted demand), we extend an existing model by adding a constraint on bus capacities while respecting user choice on the lines that can drive users to their destinations. The resulting formulation is bilevel and is then transformed, by means of applying optimality conditions on the lower level, into a mixed integer linear programming formulation (MILP) that can be solved to optimality over small instances using state-of-the-art MILP techniques. To study the nature of the model, we analyze different variants of the proposed bilevel formulation. Furthermore, we compare solutions and evaluate their feasibility of being applied to real-world scenarios. In order to do that, we apply the model to a small test case and to a real one published in the literature. To provide a better level of service to the users of the system, we study the effects of adding to the proposed formulation a constraint on the maximum waiting times of the users allowed at the bus stops. We conclude that a bilevel approach should be considered whenever bus capacities are contemplated; thus, there is a need for models that incorporate the behavior of the users, the waiting times at the stops, and bus capacities. To the best of our knowledge, the simultaneous inclusion of all of the aforementioned aspects in a single mathematical programming formulation has not been studied. Moreover, by using a test case corresponding to an actual city, we explore some underlying issues that arise whenever bus capacities and different fleet sizes are considered. By studying measures such as line capacities and maximum waiting times, with the aid of visual inspection, problematic sectors of the line network can be quickly identified. This allows a more thorough discussion of the issues that could arise in real-life contexts and helps devise alternative solutions. Finally, we analyze the limit regarding the size of the instances that can be resolved by the proposed model.

En la presente tesis se considera el problema de optimización de frecuencias en sistemas de transporte público basados en ómnibus. El objetivo del problema es determinar el intervalo de tiempo entre pasadas de ómnibus consecutivos para un conjunto de líneas. Las soluciones deben satisfacer una demanda origen-destino dada y a su vez considerar el interés tanto de los usuarios como de los operadores, en un contexto de restricciones asociadas a la infraestructura subyacente, presupuesto y nivel de servicio ofrecido. A efectos de considerar eventos de congestión sobre las líneas de transporte (esto es, cuando las líneas operan al límite de su capacidad en relación a la demanda que atraen), se extiende un modelo existente agregando una restricción de capacidad en los ómnibus, utilizando un sub-modelo que asigna la demanda de forma de respetar la decisión de los usuarios en cuanto a la elección de las distintas líneas. La formulación obtenida de esta forma es binivel, y mediante una reformulación del segundo nivel usando las condiciones de optimalidad, es convertida a una formulación lineal entera mixta (MILP) que puede resolverse de forma óptima para instancias de pequeñas dimensiones utilizando técnicas del estado del arte empleadas para los MILP. Para estudiar el comportamiento del modelo propuesto se exploran diversas variantes de esta última formulación. Con el propósito de comparar distintas soluciones, y evaluar la factibilidad de implementarlas en escenarios reales, se aplica el modelo propuesto a un caso de pequeñas dimensiones, así como a un caso real que ha sido estudiado en otras publicaciones. A efectos de brindar un mejor nivel de servicio a los usuarios del sistema, se estudian los efectos de añadir a la formulación una restricción de tiempo de espera máximo de los usuarios en las paradas.

Se concluye que un enfoque binivel es necesario toda vez que se consideren capacidades en los ómnibus. Esto supone la necesidad de contar con modelos que incorporen tanto el comportamiento de los usuarios, como capacidades y el tiempo de espera en las paradas. La inclusión simultánea de todos estos aspectos en una formulación de programación matemática constituye una novedad en la literatura. A su vez, mediante un caso de estudio correspondiente a una ciudad real, se exploran algunas de las dificultades que surgen al tener en cuenta capacidades y distintos tamaños de flota. Gracias al estudio de distintas medidas, como las capacidades de las líneas, y tiempos máximos de espera en las paradas, con la ayuda de una inspección visual, es posible identificar los sectores más problemáticos de una red de transporte, permitiendo de esta forma una discusión detallada de los desafíos que pueden surgir en contextos reales de operación y contribuyendo de esta manera en el diseño de soluciones alternativas. Finalmente, se analiza el límite en cuanto al tamaño de instancias susceptibles de ser resueltas de forma exacta utilizando el modelo propuesto.