Electric vehicles routing charging problem

The vehicle routing problem (VRP) is an optimization problem that has the aim to minimize the costs of serving a list of customers, with a fleet of vehicles starting from a depot. In particular, the electric vehicle routing problems (E-VRPs) are increasingly emerging in the panorama of operations research. The major limitation for the electric vehicles is their restricted autonomy, leading to introduce planned detour to charging stations. Hence the importance of the charging function should be considered. Many models take into account constant or linear charging functions. However we decided to adopt a piecewise linear approximation of such functions, since this is more realistic. Basing our work on the electric vehicle routing problem with nonlinear charging functions (E-VRP-NL), we extend previous research by considering heterogeneous fleet with different batteries and costs. To solve optimally our problem we initially proposed a mixed integer linear programming (MILP) node based formulation. But this model is computationally expensive, so we developed a heuristic algorithm. It is based on the one in Froger et al. (2020), that combines an iterated local search, to find high quality routes, with a solution assembler. We adapted test instances from the EVRP-NL literature to the heterogeneous vehicle case. We report results of application of the model and heuristic on a number of test instances up to 320 customers.

Il problema di instradamento dei veicoli (VRP) è un problema di ottimizzazione che ha lo scopo di minimizzare i costi per servire una lista di clienti, con una flotta di veicoli in partenza da un deposito. In particolare, i problemi di instradamento dei veicoli elettrici (E-VRP) stanno emergendo sempre più nel panorama della ricerca operativa. La principale limitazione per i veicoli elettrici è la loro autonomia limitata, che porta a introdurre deviazioni pianificate verso le stazioni di ricarica. Per questo è importante decidere con attenzione quale funzione di ricarica utilizzare. Molti modelli prendono in considerazione funzioni di ricarica costanti o lineari. Tuttavia abbiamo deciso di adottare un'approssimazione lineare a tratti di tali funzioni, poiché questa è più realistica. Basando il nostro lavoro sul problema dell'instradamento dei veicoli elettrici con funzioni di carica non lineari (E-VRP-NL), estendiamo la ricerca precedente considerando flotte eterogenee con batterie e costi diversi. Per risolvere in modo ottimale il nostro problema abbiamo inizialmente proposto una formulazione di programmazione lineare integrale mista (MILP). Ma questo modello è computazionalmente costoso, quindi abbiamo sviluppato un algoritmo euristico. L'algoritmo è basato su quello in Froger et al. (2020), che combina una ricerca locale iterata, per trovare percorsi di alta qualità, con un assemblatore di soluzioni. Abbiamo adattato le istanze dalla letteratura E-VRP-NL, aggiungendo più veicoli elettrici con caratteristiche differenti. Riportiamo i risultati dell'applicazione del modello e dell'euristica su più istanze aventi fino a 320 clienti.