A Time effective Optimization model for the Electric Vehicle Routing Problem with Time Windows

Nowadays, the use of Electric Vehicles (EVs) is increasing in both the public and the private urban transportation systems. They are also employed in the last mile transportation services and to access to the Limited Traffic Zones. The main advantages are in a reduction of both the use of fossil fuels and the harmful CO2 emissions. However, even though significant improvements of their performances have been reached in the last years, the limited battery autonomy in terms of travelled kilometers still remains a critical issue. Consequently, stops at recharging stations are usually required during the trips. This work addresses the problem of optimally routing an EV fleet in order to handle the customer demands. Each customer request is specified in terms of a time window and a demand. The related optimization problem (also known as the Electric Vehicle Routing Problem with Time Windows, E-VRPTW) has been already addressed in the literature [1,3]. Due to the particular features of the EVs, the E-VRPTW has been mathematically formulated including the need of using the Recharging Stations (RSs) during the trips [2]. However, the EVs are always fully recharged at the RSs and the goal is to minimize both the number of used EVs and the total travelled distance. We propose a variant of the original E-VRPTW such that the batteries are not necessarily fully charged. Consequently, the partial recharges guarantee higher flexibility during the route planning. Then, for each EV, the level of battery, recharged at a RS, is a decision variable of the optimization process. Moreover, the objective function takes into account also the total waiting time of each EV at each served customer and the total recharging time. The resulting proposed mathematical model is a Mixed Integer Linear Program formulation of the E-VRPTW. Finally, computational results on instances taken from the literature are compared to the ones described in [2]