Solution algorithms for the electric bus charge scheduling problem

Considering the irreversible effects of climate change, a shift towards sustainability is absolutely necessary. The transportation sector is one of the most important sectors affecting climate change and pollution. Therefore, public transport in many countries is shifting towards using electric vehicles instead of conventional ones. In this scenario, it is of great importance to have an optimized schedule for charging a fleet of electric buses not only to ensure proper execution of their tasks but also to reduce operational costs. In this work, we propose an improved MILP formulation for charge scheduling of a fleet of electric buses with Vehicle-to-Grid (V2G) technologies. Our model takes into account the costs related to the Time-of-Use energy plan, the cost for maximum power requested from the grid and battery degradation cost. Furthermore, we develop a constructive heuristic to generate an initial feasible solution, which we use in a local branching heuristic. A set of instances based on the realistic operational conditions in Milan is used. Finally, we run extensive experiments to validate the model and compare the results of our proposed heuristic with the results generated by a commercial solver and another alternative heuristic. Notably, our algorithm is able to find a feasible solution for all instances, including those with a fleet size of up to 100, achieving an average gap of 2.85%. In contrast, the standard solver is only able to obtain a feasible solution for instances with a maximum fleet size of 20.

Considerando gli effetti irreversibili del cambiamento climatico, è assolutamente necessario un passaggio alla sostenibilità. Il settore dei trasporti è uno dei più rilevanti per quanto riguarda il cambiamento climatico e l'inquinamento. Per questo motivo, in molti Paesi il trasporto pubblico si sta orientando verso l'utilizzo di veicoli elettrici al posto di quelli convenzionali. In questo scenario, è di grande importanza avere una programmazione ottimizzata per la ricarica di una flotta di autobus elettrici, non solo per garantire il corretto svolgimento delle loro attività, ma anche per ridurre i costi operativi. In questo lavoro, proponiamo una formulazione MILP migliorata per la programmazione della ricarica di una flotta di autobus elettrici con tecnologie Vehicle-to-Grid (V2G). Il nostro modello tiene conto dei costi relativi al piano energetico Time-of-Use, del costo della potenza massima richiesta alla rete e del costo di degrado della batteria. Inoltre, sviluppiamo un'euristica costruttiva per generare una soluzione iniziale fattibile, che utilizziamo in un'euristica di diramazione locale. Un insieme di istanze basate sulle condizioni operative realistiche di Milano viene utilizzato. Infine, conduciamo esperimenti approfonditi per validare il modello e confrontiamo i risultati della nostra euristica proposta con quelli generati da un risolutore commerciale e un'altra euristica alternativa. In particolare, il nostro algoritmo è in grado di trovare una soluzione fattibile per tutte le istanze, comprese quelle con una flotta di dimensione fino a 100, ottenendo un gap medio del 2,85%. Al contrario, il risolutore standard è in grado di ottenere una soluzione fattibile solo per istanze con una dimensione massima della flotta pari a 20.