Transfers in massive transportation systems under fixed and variable route schemes

Abstract

In this thesis we present modelling contributions for performing transfer operations in fixed and flexible route transit systems to achieve good solutions in real size instances associated with both problems. In the case of fixed route services, the specific problem addressed in the specialized literature is denoted the Bus Synchronization Timetabling Problem (BST). In the case of flexible route services, our focus is in the Pickup and Delivery Problem with Transfers (PDP-T). In Chapter 1, we propose an exact method to address the Pickup and Delivery Problem with Transfers (PDP-T). Exact methods in the PDP-T literature were only employed for solving small instances with large computational times due to the complexity of the problem.In this thesis, we developed cutting-edge solution methods to PDP-T based on Column Generation. We propose a new methodology to solve the problem including precedence, route synchronization and capacity constraints, involving several kinds of columns. To the best of our knowledge, this research is innovative and pioneer in addressing the problem under a column based methodology. We improve the algorithm performance applying a branch and price strategy achieving optimality in instances from 5 requests previously using only a column generation framework, up to 30 requests under a B&P framework. In Chapter 2, we study the Bus Synchronization Timetabling Problem (BST) including bus dwelling times motivated by the night shift of transit system operating in SantiagoChile. Instead of following timetables, in the operation the dispatching of trips when there are high frequencies it is not necessary to publish timetables, since the waiting times are low (frequency based methods). This approach works well enough during the day operation when demand and frequencies are high. However, during the operation at night, when demand is low and there are a reduced number of services operating with lower frequencies, this type of policy may result in longer waiting times (not only to take the service, but also to transfer at bus stops) and a bad service quality for passengers. To address these inefficiencies, the authorities has defined that all of their night services will operate according to fixed and coordinated timetables. For this, we propose a mixed integer programming model to define the specific timetables and the duration of the vehicle dwelling periods, analyzing the model performance under a set of different real size instances.

En este documento, se presentan contribuciones al estado del arte en el modelamiento matemático de sistemas de transporte de bienes y pasajeros tanto en ruta flexible como ruta variable incorporando operaciones de transferencia, ya sea de carga o pasajeros, alcanzando soluciones de calidad en instancias de tamaño real. En la literatura especializada, los sistemas de servicios de rutas fijas y rutas variables, incluyendo transferencias son conocidos como: Bus Synchronization Timetabling Problem (BST) y Pickup and Delivery Problem with Transfers (PDP-T), respectivamente. En el capítulo 1 de este documento, se aborda el Pickup and Delivery Problem with Transfers (PDP-T) a través de un método exacto. Los métodos exactos en la literatura de PDP-T han sido empleados para solucionar instancias pequeñas con grandes tiempos de cómputo debido a su complejidad en las formulaciones agregando esta característica. En esta tesis, desarrollamos métodos de solución tipo cutting-edge (corte de aristas del poliedro matemático que describe el problema) al PDP-T: basado en generación de columnas. Se propone una nueva metodología para solucionar este tipo de problemas incluyendo restricciones de precedencia, sincronización de rutas y capacidad de vehículos; adicionalmente el problema involucra diferentes tipos de columnas. Según lo que se ha investigado, este trabajo es innovador y precursor en aplicar este enfoque metodológico a este problema específico. El desempeño del algoritmo fue mejorado aplicando diferentes estrategias Branch-and-Price. Esta implementación logró pasar de solucionar 5 solicitudes de servicios en el trabajo preliminar que solo empleaba generación de columnas hasta alcanzar soluciones óptimas en instancias de 30 solicitudes de servicio. En el capítulo 2 de este documento, se estudia el Bus Synchronization Timetabling Problem (BST) incluyendo tiempos de espera de los vehículos en los paraderos, motivado por la operación nocturna del sistema de buses en Santiago de Chile. En la operación actual, en lugar de regirse a programaciones, el despacho de vehículos se decide en tiempo real de acuerdo con la flota disponible y otras condiciones. Este enfoque funciona adecuadamente durante la operación diurna, cuando la demanda y las frecuencias son altas. Sin embargo, durante la operación de la noche, cuando la demanda es baja y hay un número reducido de servicios operando con frecuencias más bajas, este tipo de política puede resultar en tiempos de espera largos (no solo para abordar la línea de servicio, sino también para transferirse de vehículo) deteriorando la calidad de servicio para los usuarios. Para manejar estas ineficiencias, autoridades definieron que todas sus líneas de servicios nocturnas operarán con programaciones de servicio fijas y coordinadas. Para ello, se propone un modelo de programación lineal mixta con el objetivo de definir programaciones de servicios específicas y los tiempos de espera de los vehículos en los paraderos definidos para tal efecto, analizando el desempeño del modelo bajo un conjunto de diferentes instancias de tamaño real.