A Variable Neighborhood Search Branching for the Electric Vehicle Routing Problem with Time Windows

E-mobility plays a key role especially in contexts where the transportation activities impact a lot on the total costs. The Electric Vehicles (EVs) are becoming an effective alternative to the internal combustion engines guaranteeing cheaper and eco-sustainable transport solutions. However, the poor battery autonomy is still an Achille’s hell since the EVs require many stops for being recharged. We aim to optimally route the EVs for handling a set of customers in time considering the recharging needs during the trips. A Mixed Integer Linear Programming formulation of the problem is proposed assuming that the battery recharging level reached at each station is a decision variable in order to guarantee more flexible routes. The model aims to minimize the total travel, waiting and recharging time plus the number of
the employed EVs. Finally, a Variable Neighborhood Search Branching (VNSB) is also designed for solving the problem at hand in reasonable computational times. Numerical results on benchmark instances show the performances of both the mathematical formulation and the VNSB compared to the ones of the model in which the battery level reached at each station is always equal to the maximum capacity.