The Electric Vehicle Routing Problem With Time Windows and Multiple Recharging Options

Abstract

Driven by environmental concerns and new regulations, electric vehicles (EVs) are increasingly becoming popular for package delivery. However, due to their limited driving range, the EV has to be recharged during the route in many situations. A new variant of the electric vehicle routing problem with time windows is investigated through integrating decisions on multiple recharging options, which are partial recharging and battery swapping. A mixed integer programming model is developed to formulate the problem. An improved ant colony optimization (ACO) algorithm hybridized with insertion heuristic and enhanced local search is designed to solve the problem. Also, a new probabilistic selection model in ACO is proposed by integrating the impact of both distances and time windows. Computational experiments based on open data source is utilized to validate the performance of the algorithm, and the results indicate that the newly designed insertion heuristic and local search strategies improve the efficiency for solving the problem. The results for all the instances under the strategy of multiple recharging options are compared with those under strategies of partial recharging and battery swapping, which shows that the former strategy can help saving costs for most of the situations.

Keywords

• Electric vehicle
• vehicle routing problem
• ant colony optimization
• partial recharge
• battery swapping