Metodi e modelli di programmazione matematica per l'ottimizzazione del routing dei veicoli elettrici

The electromobility plays a key role for locally reducing the harmful emissions, usually due to the internal combustion engine vehicles. Unlike these vehicles, the Electric Vehicles (EVs) guarantee eco-sustainable transport solutions and several economic benefits. Moreover, they can be used for providing services in limited traffic areas and/or services on demand. The aim of this thesis is to efficiently plan the routes of a fleet of EVs in a transport network for serving the demand of a set of customers. The problem, known in Operations Research as Electric Vehicle Routing Problem with Time Windows, has been addressed, from the modeling point of view, by proposing a mixed integer linear programming formulation, for optimizing the number of EVs used and the time spent by them outside the depot. Time windows within the customers have to be served and the related service times are considered; constraints on the maximum time duration of the trips and on the capacity of the EVs are imposed. Moreover, the use of a fleet of EVs implies constraints on the battery capacity. Therefore, defining the visit sequences, stops at the recharging stations are also included. Each EV starts from the depot and it returns to the depot after serving the demand of a certain set of customers, respecting the conditions listed above with the traditional routing constraints. The contribution of this thesis is to consider the battery quantity recharged at the stations as decision variable, established by the model during the route planning. Since the solution of the problem at hand is hard on instances with a large number of customers, a matheuristic is proposed that, combining a metaheuristic (Variable Neighborhood Search) with the mathematical programming, detects good quality solutions in reasonable amount of time. The numerical results, on benchmark instances taken from the literature, remark that the proposed mathematical model finds solutions also dominant the ones of the model with fixed recharges and the good performances of the matheuristic.

La mobilità elettrica ha un ruolo chiave nella riduzione, localmente, delle emissioni nocive, tipicamente dovute ai veicoli a combustione interna. Rispetto a questi, i Veicoli Elettrici (VE) garantiscono soluzioni di trasporto eco-sostenibili e diversi benefici economici. Inoltre, possono essere usati per espletare servizi in aree a circolazione limitata e/o servizi a chiamata. Obiettivo di questa tesi è pianificare efficientemente le rotte di una flotta di VE in una rete di trasporto per servire la domanda di un insieme di clienti. Il problema, noto in Ricerca Operativa come Electric Vehicle Routing Problem with Time Windows, è stato trattato, dal punto di vista modellistico, proponendo una formulazione matematica di programmazione lineare intera mista, per ottimizzare il numero di VE usati e il tempo speso dagli stessi al di fuori del deposito. Si considerano: finestre temporali entro cui soddisfare i clienti ed il relativo tempo di servizio; vincoli sulla durata massima di ogni percorso e sulla capacità dei VE. L’uso di VE comporta inoltre vincoli sulla capacità delle batterie. Quindi, nel definire le sequenze di visita, si prevedono anche fermate alle stazioni di ricarica. Ogni VE parte dal deposito e vi ritorna dopo aver servito la domanda di un certo numero di clienti, rispettando le condizioni sopra elencate ed i tradizionali vincoli per l’instradamento. Contributo di questa tesi è considerare la quantità di ricarica della batteria, presso le stazioni, come variabile decisionale, stabilita dal modello in fase di pianificazione delle rotte. Essendo il problema di difficile soluzione su istanze con un numero elevato di clienti, si è proposta una mateuristica che, combinando una metaeuristica (Variable Neighborhood Search) con la programmazione matematica, ottiene soluzioni di buona qualità in tempi di calcolo ragionevoli. I risultati numerici, su istanze benchmark della letteratura, evidenziano che il modello proposto trova soluzioni anche dominanti quelle del modello a ricarica fissa e buone prestazioni della mateuristica.