Solving the Electric Vehicle Routing Problem with Time Windows and Partial Recharges

Electromobility aims promoting transportation solutions employing the Electric Vehicles (EVs) in place of the traditional internal combustion engine vehicles in order to reduce the harmful CO2 emissions that are polluting more and more the big cities. In addition, the recent technological progresses concerning the EVs allow also partial battery recharges. In this context, the aim of our work is to efficiently route a fleet of EVs, exploiting such recent technological advancements, in order to handle a set of customers within their time windows. Each EV route starts/ends from/at a common depot. Moreover, along each route, intermediate stops at the recharging stations for (also partial) battery recharges are allowed. The problem, known as Electric Vehicle Routing Problem with Time Windows, is here mathematically formulated as a Mixed Integer Linear Program (MILP) with the aim of firstly minimizing the number of EVs used and then, of optimizing the total time spent by the EVs outside the depot i.e., the total recharging, traveling and waiting times. In order to handle the problem hardness and to find good quality solutions in real life settings, a matheuristic, based on the Variable Neighborhood Search, is proposed. Numerical results, carried out on some benchmark instances, are shown for the solutions found by both the proposed MILP and the matheuristic.