Allocazione dinamica e pianificazione delle risorse nella gestione di una autostazione

The assignment of buses arriving to available gates is a major issue during the daily operations in a bus station. Such a problem is known in literature as Gate Assignment Problem and consists, given the daily bus schedule, in determining the best feasible assignment of the buses to the gates based on certain preference criteria. In order for a solution to be feasible at least two constraints have to be satisfied: each bus must be assigned to one and only one platform and two buses whose time intervals of platform occupation overlap cannot be assigned to the same platform. Problems similar to gate assignment in bus stations arise in the management of airports, train stations, ports, freight villages and so on. There are also strong similarities with the register assignment problem in Digital Signal Processors. In the bus station case, manager may require that the bus-platform assignment plan occupies the minimum number of platforms during the planning horizon. For this problem we propose a novel formulation as a list-colouring problem of an interval graph and an integer linear programming model to solve it. Trip delays such as early or late arrivals and late departures are a frequent occurrence in actual day to day bus station operations and it is often not possible to assign such buses to their original platforms. For this reason we considered a mathematical programming model to increase the robustness of the solutions by the minimization of the probability that buses assigned to the same gate may be "in conflict". Finally, in order to generate a good solution in a reasonable computation time, we also propose a heuristic algorithm, based on the idea to solve the problem by dividing it into smaller sub-problems, using a receding horizon control, and then reconstructing the complete solution. Computational experiments on a real bus station with 24 platform and more than 200 bus trips have been performed showing the effectiveness of the approach.

Uno dei maggiori problemi che si presenta nella gestione operativa di un’autostazione è l’assegnamento dei bus alle piattaforme disponibili. Tale problema è noto in letteratura come Gate Assignment Problem e consiste nel determinare il miglior assegnamento ammissibile dei bus alle piattaforme basato su certi criteri di preferenza, nota la tabella oraria giornaliera dei bus. Affinché una soluzione sia ammissibile devono essere soddisfatti almeno due vincoli: ogni bus deve essere assegnato a una e una sola piattaforma e due bus i cui intervalli temporali di occupazione della piattaforma si sovrappongono non possono essere assegnati alla stessa piattaforma. Problemi simili all’assegnamento delle piattaforme nelle autostazioni nascono nella gestione di aeroporti, stazioni ferroviarie, porti, interporti e così via. Ci sono anche forti somiglianze con il problema dell’assegnamento dei registri nei processori di segnale digitale (DSP). Nel caso dell’autostazione il gestore può richiedere che gli assegnamenti bus-piattaforme siano tali da occupare il minor numero di piattaforme nell’orizzonte di pianificazione. Per questo problema si propone una formulazione innovativa come problema di list-colouring di un grafo d’intervallo e un modello di programmazione lineare intera per la sua risoluzione. Situazioni di mancato rispetto della tabella oraria, quali arrivi in anticipo o ritardo e partenze in ritardo, sono piuttosto frequenti nella gestione quotidiana di un’autostazione e spesso fanno sì che non sia possibile assegnare i bus coinvolti alla piattaforma prevista. Per questo motivo si è considerato un modello di programmazione matematica per aumentare la robustezza delle soluzioni minimizzando la probabilità che i bus assegnati alla stessa piattaforma siano “in conflitto”. Per finire, allo scopo di generare una buona soluzione in un tempo di calcolo ragionevole, si propone anche un algoritmo euristico basato sull’idea di risolvere il problema mediante una suddivisione in sottoproblemi più piccoli utilizzando un controllo a orizzonte recessivo, e una successiva ricostruzione della soluzione completa. Sono stati svolti esperimenti computazionali su una autostazione esistente con 24 piattaforme e più di duecento corse che hanno dimostrato l’efficacia dell’approccio.