The electric vehicle routing problem with synchronized mobile partial recharging and non-strict waiting strategy

Many transportation activities have shifted to use electric vehicles (EVs) due to low-carbon and sustainability concerns. The main challenges faced by companies during the transition are the short range of EVs and the lack of recharging infrastructure. To cope with this situation, mobile charging vehicles (MCVs) are used in the system. However, this significantly increases the complexity of the electric vehicle routing problem (EVRP), as the routes for both EVs and MCVs should be optimized, and the two routes are highly interdependent. Moreover, most existing literature assumes that EVs need to be fully recharged or swapped, and EVs cannot wait for MCVs. This may lead to MCVs detour and increase scheduling difficulties, increasing the overall cost for both routes and reducing efficiency. Therefore, this paper proposes an EVRP model with synchronized mobile partial recharging and non-strict waiting strategy. The model relaxed the assumptions about full recharging and MCV waiting strategy, further increasing the complexity of the EVRP. To solve this model, we propose a two-stage dynamic programming and forward time slack algorithm based on the labeling algorithm, which is integrated into the framework of an improved adaptive large neighborhood search algorithm. Extensive numerical experiments are then conducted to demonstrate the efficiency of the algorithm and the benefits of the non-strict waiting strategy. Finally, the paper discusses some management insights based on the above analysis.