A heuristic algorithm for the electric freight vehicles charge scheduling problem

The introduction of electric vehicles in logistics activities is facing new challenges concerning in particular their daily operational planning. A proper management of all possible resources and a good scheduling procedure are important elements to expand the use of electric vehicles for commercial purposes. As a consequence, the optimization of a scheduling problem is essential to obtain good results in terms of costs and organization. The work developed in this thesis is focused on the "Electric Freight Vehicles Charge Scheduling Problem (EFV-CSP)", introduced by Pelletier, Jabali and Laporte 2018. The paper proposes an optimization model aimed at reducing the costs related to the charging of a fleet of fright electric vehicles, taking into account a realistic charging process, time-dependent energy costs, battery degradation, grid restrictions, and facility-related demand charges. The aim of this thesis is to develop a heuristic algorithm for the solution of EFV-CSP, in order to find near optimal results in a short time. The heuristic algorithm is the result of the analysis of different algorithms, aimed at sequentially improving the solution. The effectiveness of the heuristic algorithm is demonstrated through some tests, generated by varying the characteristics of the routes performed by the vehicles. The different results, obtained from the different configurations adopted, are also analyzed.

L'introduzione dei veicoli elettrici nelle attività logistiche sta affrontando nuove sfide riguardanti in particolare la loro pianificazione operativa quotidiana. Una adeguata gestione di tutte le risorse possibili e una buona pianificazione degli orari sono elementi importanti per espandere l'utilizzo di veicoli elettrici per scopi commerciali. Di conseguenza, l'ottimizzazione di un problema di scheduling è fondamentale per ottenere buoni risultati in termini di costi e organizzazione. Il lavoro sviluppato in questa tesi è focalizzato sull' “Electric Freight Vehicles Charge Scheduling Problem (EFV-CSP)”, introdotto da Pelletier, Jabali e Laporte 2018. Il paper propone un modello di ottimizzazione finalizzato alla riduzione dei costi legati alla ricarica di una flotta di veicoli elettrici per il trasporto di merci, tenendo conto di un processo di ricarica realistico, delle fasce orarie di consumo, del degrado della batteria, delle restrizioni della rete elettrica e degli oneri di richiesta relativi all’impianto. Lo scopo di questa tesi è sviluppare un algoritmo euristico per la soluzione di EFV-CSP, al fine di trovare risultati quasi ottimali in breve tempo. L'algoritmo euristico finale è il risultato dell'analisi di diversi algoritmi, finalizzati al miglioramento progressivo della soluzione. Tramite dei test, generati variando le caratteristiche dei tragitti percorsi dai veicoli, viene dimostrata l'efficacia dell'algoritmo euristico. Si analizzano inoltre i vari risultati trovati in base alle diverse configurazioni adottate.