Demand-driven timetabling optimization for automated metro lines

With the recent growth of urban populations, efficiently managing transit systems has become a top priority to local authorities. The widespread adoption of automated transit systems, coupled with the increased availability of passenger demand-related information opens several avenues for innovatively managing transit systems. Indeed, the lack of drivers completely removes the need for personnel scheduling and rostering, which has traditionally been a very complex and delicate aspect of operating transit services. Thus, automated systems are allowed far more freedom in their control strategies. Such freedom can be leveraged to employ more flexible timetables, which can specifically be tailored to the passenger demand. In this thesis, we develop novel control strategies for an automated line aimed at exploiting their benefits, to achieve a fully demand-driven timetabling approach, and improve the passengers' service quality. In particular, we deviate from established methods in two significant ways. Firstly, we do not impose any structural constraints in the definition of the schedule of the trains. Instead, we let the model organically determine the structure of the timetable to match the demand and achieve optimal service quality. Secondly, we allow the use of short-turning in the schedule of the trains. By using short-turning trains are not required to serve the line from terminal to terminal. Instead, the trains may reverse their direction before reaching the terminal of the line, effectively performing a short cycle. By doing so, we can shape the timetable to fit the distribution of demand on the line and offer increased frequencies to high-demand stations and lower frequencies at low-demand stations. We introduce an alternative demand-driven control paradigm, called Direct Timetabling. According to this paradigm, the operators control the trains individually rather than imposing a predetermined structure for the entire timetable. Additionally, short-turning decisions are directly integrated into the optimization of the timetable. This allows far more flexibility in the control decisions of the line, which is used to adapt to variations of passenger demand and yield a better service. We formulate the problem of optimizing the schedule of a metro corridor with the direct timetabling paradigm through a mixed integer linear programming model with the objective of minimizing the passenger waiting time, and develop an efficient exact algorithm using cut generation. Our results show the effectiveness of the developed algorithm and the utility of the direct timetabling paradigm both on artificial instances and instances inspired from real-world lines. Afterwards, we consider a special case of direct timetabling, which can be more efficiently solved under mild assumptions on the structure of the train schedule. We present an alternative formulation for the problem and an efficient exact algorithm based on Benders decomposition, and show through extensive computational experiments the effectiveness of the developed decomposition. Lastly, we develop a direct timetabling strategy to handle the demand associated with a special event (e.g., a football match or a concert). In the developed strategy, we individually schedule the trains through short-turning to maximize the service quality serving the demand associated with one such event. We propose a mixed integer linear programming formulation for the problem, and an efficient heuristic based on Iterated Local Search, considering four possible objective functions representing different measures of service quality. Our results show that the developed strategy is able to significantly improve upon the regular timetable with respect to all measured objectives.

Con la recente crescita delle popolazioni urbane, la gestione efficiente dei sistemi di trasporto pubblico è diventata una priorità assoluta per le autorità locali. L'adozione diffusa di sistemi di guida autonoma, insieme alla maggiore disponibilità di dati realativi alla domanda di linea, offre diverse possibilità per la gestione innovativa dei mezzi di trasporto pubblico. Infatti, i sistemi automatizzati offrono significativamente più libertà nelle loro strategie di controllo, la quale può essere sfruttata per impiegare orari più flessibili, che possono essere specificamente adattati alla domanda dei passeggeri. In questa tesi, sviluppiamo nuove strategie di controllo per una linea metropolitana automatizzata, per ottenere un approccio alla programmazione degli orari completamente basato sulla domanda e migliorare la qualità del servizio per i passeggeri. In particolare, ci discostiamo dai metodi consolidati in due modi significativi. In primo luogo, non imponiamo alcun vincolo strutturale nella definizione dell'orario dei treni. Invece, lasciamo che il modello determini autonomamente la struttura dell'orario per soddisfare la domanda e raggiungere una qualità di servizio ottimale. In secondo luogo, permettiamo l'uso di manovre di inversione nella programmazione dei treni. Così facendo, i treni non sono tenuti a servire la linea da un terminale all'altro, invece, possono invertire la loro direzione prima di raggiungere il terminale della linea, accelerando la circolazione dei treni. In questo modo possiamo adattare l'orario distribuzione della domanda sulla linea e offrire maggiori frequenze alle stazioni ad alta domanda e minori frequenze alle stazioni a bassa domanda. Introduciamo un paradigma di controllo alternativo basato sulla domanda, chiamato Direct Timetabling. Secondo questo paradigma, i treni sono controllati indipendentemente l'uno dall'altro senza imporre una struttura predeterminata per l'intero orario. Inoltre, le decisioni di inversione sono direttamente integrate nella pianificazione degli orari. Questo permette una maggiore flessibilità nelle decisioni di controllo della linea, che può essere sfruttata per adattarsi alle variazioni della domanda dei passeggeri e produrre un servizio migliore. Formuliamo il problema dell'ottimizzazione dell'orario di una singola linea metropolitana con il paradigma del Direct Timetabling attraverso un modello di programmazione lineare intero misto con l'obiettivo di minimizzare il tempo di attesa dei passeggeri, e sviluppiamo un algoritmo esatto usando la generazione di tagli. I nostri risultati mostrano l'efficacia dell'algoritmo sviluppato e l'utilità del paradigma del Direct Timetabling sia su istanze artificiali che su istanze ispirate a linee reali. In seguito, consideriamo un caso speciale di Direct Timetabling, che può essere risolto in modo più efficiente sotto limitate assunzioni sulla struttura della programmazione dei treni. Presentiamo una formulazione alternativa per il problema e un efficiente algoritmo esatto basato sulla decomposizione di Benders, e mostriamo attraverso ampi esperimenti computazionali l'efficacia della decomposizione sviluppata. Infine, sviluppiamo una strategia di Direct Timetabling per gestire la domanda associata ad un evento (ad esempio, una partita di calcio o un concerto). Proponiamo una formulazione di programmazione lineare intera mista per il problema e un'euristica basata sull'Iterated Local Search, considerando quattro possibili funzioni obiettivo che rappresentano diverse misure della qualità del servizio. I nostri risultati mostrano che la strategia sviluppata è in grado di migliorare significativamente la qualità del servizio rispetto a tutti gli obiettivi misurati.