Optimization of electric vehicle recharge schedule and routing problem with time windows and partial recharge: A comparative study for an urban logistics fleet

The use of electric vehicles (EVs) is becoming more and more widespread and the interest in these vehicles is increasing each day. EVs promise to emit less air pollution and greenhouse gas (GHG) emissions with lower operational costs when compared to fossil fuel-powered vehicles. However, many factors such as the limited mileage of these vehicles, long recharging times, and the sparseness of available recharging stations adversely affect the preferability of EVs in industrial and commercial logistics. Effective planning of EV routes and recharge schedules is vital for the future of the logistics sector. This paper proposes an electric vehicle routing problem with the time windows (EVRPTW) framework, which is an extension of the well-known vehicle routing problem (VRP). In the proposed model, partial recharging is considered for the EVRPTW with the multiple depots and heterogeneous EV fleet and multiple visits to customers. While routing a set of heterogeneous EVs, their limited ranges, interdependent on the battery capacity, should be taken into consideration and all the customers' deliveries should be completed within the predetermined time windows. To deal with this problem, a series of neighbourhood operators are developed for the local search process in the variable neighbourhood search (VNS) and variable neighbourhood descent (VND) heuristics. The proposed solution algorithms are tested in large-scale instances. Results indicate that the proposed heuristics perform well as to this problem in terms of optimizing recharging times, idle waiting times, overtime of operators, compliance with time windows, number of vehicles, depots, and charging stations used.