An improved matheuristic for solving the electric vehicle routing problem with time windows and synchronized mobile charging/battery swapping

The shift towards low-emission vehicles in transportation activities, electric vehicles (EVs) in particular, has accelerated lately due to the growing concerns in modern societies regarding greenhouse gas emissions and climate change. Delivery companies have started using EVs in their fleets to reduce their dependency on fossil fuels and improve their carbon footprints. However, range anxiety, long recharge durations and insufficient recharging infrastructure still restrain the wider adoption of EVs in the sector. As a remedy, battery swapping vans (BSVs) were proposed in the literature to supply energy to EVs at points of need and the arising problem was referred to as the Electric Vehicle Routing Problem with Time Windows and Synchronized Mobile Battery Swapping (EVRPTW-SMBS). However, the use of BSVs is limited to small commercial vehicles. In this study, we generalize the problem and present the Electric Vehicle Routing Problem with Time Windows and Mobile Charging Stations (EVRPTW-MCS). In this problem, EVs serve the customers within their time windows and electric trucks/vans are employed to recharge or swap their batteries at selected customer locations during their visits. The objective is to minimize the total operational cost with the minimum fleet size. First, we present the mathematical model of the EVRPTW-MCS. Next, we propose a matheuristic approach that combines the Variable Neighborhood Search with exact method to solve it. Then, we perform an extensive numerical study to validate the performance of the proposed approach and present new best solutions for two related problems in the literature. We also investigate the potential benefits of utilizing MCSs and provide several trade-off analyses. Finally, we provide a case study based on real data to present managerial insights.