AN ALGORITHM FOR THE OPTIMAL ROUTING OF ELECTRIC VEHICLES

A relevant variation of the classical VRP problem, called the Electric Vehicle Routing Problem (EVRP), aims to properly route Electric Vehicles planning their stops at Recharge Stations. Electric vehicles have the peculiar feature of being operated by batteries of limited capacity, and therefore may need to visit a charging station in between customer visits. The aim of this thesis is to develop an exact branch-and-price algorithm for solving this problem to optimality. We realistically assume that partial recharges are possible, even with different recharge technologies during the same route, and that more than one recharge technology can be available at any given station. Existing methodologies for the EVRP focus on constructive heuristics, and very few benchmark instances with proven optimal solutions are available. We improve and integrate methods from the literature, such as bidirectional dynamic programming algorithms for pricing and incompatibility branching rules. The resulting branch-and-price algorithm is governed by critical parameters whose value can heavily affect the computational performances, although not the optimality guarantee. To overcome this limitation, we design both combinatorial heuristics and data-driven methods to automatically tune these critical parameters, possibly instance-by-instance in an adaptive fashion. We perform extensive computational experiments to assess the overall performance of our method and a comparison with another exact approach, and report solutions solved to proven optimality in a benchmark dataset.

Una variante rilevante del classico problema di VRP, nota come EVRP (Electric Vehicle Routing Problem), mira ad instradare correttamente dei veicoli elettrici pianificandone le soste presso apposite stazioni di ricarica. I veicoli elettrici hanno la peculiare caratteristica di essere azionati da batterie di capacità limitata, e necessitano potenzialmente di soste presso una stazione di ricarica tra le visite ai clienti. Lo scopo di questa tesi è lo sviluppo di un algoritmo esatto di branch-and-price per risolvere all’ottimo tale problema. Assumiamo realisticamente che siano possibili ricariche parziali, anche con diverse tecnologie di ricarica durante la stessa rotta, e che ad ogni stazione siano potenzialmente disponibili più tecnologie di ricarica. Le metodologie esistenti per risolvere l’EVRP si focalizzano prevalentemente su euristiche costruttive, e ben poche istanze di benchmark con soluzioni ottime sono disponibili. Miglioriamo e integriamo i metodi disponibili in letteratura, come la programmazione dinamica bidirezionale per il sottoproblema di pricing e le regole di branching basate sull’incompatibilità. L’algoritmo di branch-and-price risultante è governato da parametri critici, i cui valori influenzano pesantemente le performance computazionali (ma non la garanzia di ottimalità). Per superare questa limitazione, sviluppiamo metodi automatici per tarare i parametri critici, possibilmente istanza per istanza in modo adattivo, sia tramite euristiche combinatorie che tramite modelli data-driven. Eseguiamo ampi esperimenti computazionali per valutare le prestazioni complessive del nostro metodo, lo confrontiamo con un altro approccio esatto e riportiamo soluzioni di provata ottimalità in un dataset di riferimento.