A column generation algorithm for the multi-depot crew scheduling problem

The goal on solving the Multi-Depot Crew Scheduling Problem (MDCSP) is to find a set of duties for the bus drivers that satisfies all the trips of a given timetable at the minimum cost. In this thesis we modeled a real MDCSP as a Set Partitioning Problem with side-constraints and we implemented a column generation scheme to heuristically solve it. The side constraints mainly model the different types of duties and the association between duties and depots ruled by laws and organizational choices that cannot be changed. The pricing problem consisted of finding a Resource Constrained Shortest Path (RCSP) on a Directed Acyclic Graph (DAG) and has been solved with a Branch and Bound scheme with Lagrangian relaxation. The DAG modeled the compatibilities between the trips and, giving appropriate weights on the arcs, the operative cost on them. In a Column Generation (CG) scheme an important role is played by the initialization phase in which a set duties have to be nested in the MDCSP model in order to get an initial feasible solution. Three ways to initialize the problem has been investigated and pros and cons of each of them are presented in the thesis. The topological ordering is a characteristic of the DAG and is widely explained in this work and used in the algorithm developed. The success of a CG relies mostly in the way the pricing problem is solved so many performance improvement techniques have been implemented in order to make the algorithm faster, more efficient and able to find better solution during the pricing phase. The algorithm has been developed following a scalable structure able to insert in it more pricing algorithms. In this way if a more performing algorithm will be implemented or a more suitable algorithm for a particular version of the MDCSP can be used the software structure can easily host the new procedure. Many tests have been performed on small, medium and big real instances and a comparison of the results obtained have been presented on the last chapter of the thesis. The computational results obtained expressed the goodness of the algorithm in terms of solution quality and computational time. It was able to solve big instances in a reasonable amount of time and small instances in less than a second.

Risolvere il Multi-Depot Crew Scheduling Problem (MDCSP) significa trovare un insieme di turni per gli autisti degli autobus che soddisfino tutte le corse di una data tabella oraria minimizzando una data funzione di costo. In questa tesi sono formulate istanze reali per la turnazione del personale come problemi di Set Partitioning con vincoli aggiuntivi ed è stato implementato uno schema di generazione di colonne per risolverlo euristicamente. I vincoli aggiuntivi modellano principalmente le diverse tipologie di turno e le associazioni tra i turni e i depositi che sono regolate da scelte interne delle aziende e che non possono essere modificate. Il problema di pricing consiste nel trovare un cammino minimo con vincoli di risorsa su un grafo diretto aciclico ed è stato risolto con l’implementazione di uno schema di Branch and Bound con rilassamento lagrangiano. Il grafo diretto aciclico modella le compatibilità tra le corse e, dando pesi appropriati agli archi, i costi operativi per la loro esecuzione in sequenza. In uno schema di generazione di colonne un ruolo importante è ricoperto dalla fase di inizializzazione del problema e nel MDCSP un insieme di turni deve essere inserito nel modello di Set Partitioning per ottenere una soluzione ammissibile iniziale. In questa tesi sono stati studiati e proposti tre modi per inizializzare e il problema con un’analisi dei pro e dei contro. L’ordinamento topologico è una caratteristica di un grafo diretto aciclico ed è ampiamente spiegata in questa tesi e usata nello sviluppo dell’algoritmo. Il successo di uno schema di generazione di colonne dipende molto dal modo con cui è risolto il problema di pricing. Per migliorare quindi le prestazione globali dell’algoritmo molte tecniche per l’incremento delle performance sono state implementate aumentando la velocità d’esecuzione, l’efficienza e a qualità delle soluzioni trovate. L’algoritmo è stato sviluppato con un struttura scalabile in modo tale da poter aggiungere ulteriori algoritmi di pricing. In questo modo se si riuscisse a implementare un algoritmo di pricing più performante o un algoritmo più efficiente fosse necessario per una particolare versione del MDCSP questa può essere tranquillamente aggiunta e utilizzata nell’attuale struttura dell’algoritmo. Molti test sono stati eseguiti su piccole medie e grandi istanze e un’analisi dei risultati ottenuti sono stati presentati nell’ultimo capitolo della tesi. I risultati computazionali ottenuti esprimono la bontà dell’algoritmo rispetto alla qualità delle soluzioni e ai tempi d’esecuzione. L’algoritmo è stato in grado di risolvere in tempi ragionevoli istanze grandi e in meno di un secondo le istanze piccole.