Optimization in long distance public transportation

In recent years, the landscape of public transportation in Italy has undergone significant transformations due to new legislation shaping the market. Previously, bus companies received state concessions to cover specific routes, with earnings fixed rather than de pendent on passenger numbers. The removal of these concessions has increased market competitiveness and compelled companies to enhance efficiency. Not only the past but the future as well is impacting the market, with the imperative for efficiency stemming from the necessity to mitigate environmental impact and ensure business sustainability. Mathematical optimization offers a means for bus companies to realize significant sav ings, enhancing competitiveness and sustainability simultaneously. This thesis aims to achieve optimization by dynamically adjusting schedules based on daily demand. The problem at hand resembles a classical Vehicle Scheduling Problem but incorporates a pre-processing step merging trips post-vehicle scheduling to align with known passenger demand. Two models are presented and tested. The first is a bi-objective model aimed at minimizing both fleet size and passenger transfers. However, due to its complexity, this model struggles to terminate within acceptable timeframes for daily rescheduling with larger instances. Consequently, a heuristic derived from the first model is introduced as the second model. This heuristic decomposes the original bi-objective model into two separate models, each focusing on a single objective function. Testing on a real-world scenario demonstrates that both models achieve satisfactory solutions, yet the heuristic proves more efficient in terms of time, especially with larger instances.

Negli ultimi anni il settore dei trasporti in Italia ha subito diversi cambiamenti dovuti a nuove leggi che hanno trasformato il mercato. In passato, le compagnie di autolinee riceve vano concessioni statali per coprire certe tratte, con un guadagno fisso ed indipendenti dal numero di passeggieri trasportati. La rimozione di queste concessioni ha aumentato la con correnza nel mercato e imposto la necessità di una maggiore efficienza per le compagnie. Le ragioni dei cambiamenti del mercato però non risiedono soltanto nel passato, guardando al futuro anche la necessità di ridurre il proprio impatto sull’ambiente e garantire sosteni bilità aziendale spinge le aziende a ricercare maggiore efficienza. L’ottimizzazione matem atica offre alle aziende diversi strumenti per risparmiare sui costi operativi e migliorare la propria sostenibilità ecologica contemporaneamente. L’ obbiettivo di questa tesi è di raggiungere tale ottimizzazione andando a compiere una ripianificazione diaria delle tratte programmate tenendo in considerazione la domanda. Il problema è simile al classico “Ve hicle Scheduling Problem” ma introduce una fase di pre-processamento dei dati che punta a unificare le linee già pianificate quando la domanda lo permette. Due modelli sono presentati e testati. Il primo è un modello bi-obbiettivo che punta a ridurre contempo raneamente le dimensioni della flotta e il numero di cambi effettuati dai passeggeri. A causa della sua complessità questo modello, quando sottoposto ad istanze con numerose tratte, non termina in tempi ragionevoli per una ripianificazione diaria delle tratte. Per questo motivo il secondo modello presentato è un’euristica del primo. L’euristica divide il modello originale in due modelli, ognuno dei quali con la propria funzione obbiettivo. I test effettuati su dati provenienti da uno scenario reale mostrano che entrambi i modelli trovano soluzioni soddisfacenti anche se, con istanze più grandi, l’euristica risulta più ef ficace.