A hybrid simulated annealing and variable neighborhood search algorithm for the close-open electric vehicle routing problem

Electric Vehicles (EVs) are the future of transportation, but due to their battery and charging technology they cannot yet directly replace traditional vehicles. Nonetheless, EVs are a great option for city-logistics, due to the small distances and their zero local emissions. In this paper, a novel variant of the Electric Vehicle Routing Problem (EVRP), called Close-Open EVRP (COEVRP), is presented. It considers ending EV trips at Charging Stations, as opposed to other EVRP variants that only allow for en-route charging. This new variant follows a traditional routing scheme, allowing EVs to recharge only at the end of their route. The objective is to minimize energy consumption, as well as the number of vehicles. The energy consumption function takes into account the weight of the transported items. A mathematical formulation for the problem is presented and small instances were solved using a commercial solver. To solve larger instances, a hybrid metaheuristic combining Simulated Annealing and Variable Neighborhood Search algorithm was employed and thoroughly tested.