Cmsa Algorithms for the Electric Vehicle Routing Problem with Simultaneous Pickup and Deliveries, Time Windows and Partial Battery Charging

This study addresses the electric vehicle routing problem with time windows and simultaneous pickup and deliveries in the context of sustainable city logistics. Time windows and simultaneous pickup and delivery constraints are two important real-life constraints to effectively organize freight distribution activities, especially in cities. In addition, we also consider partial recharging of electric vehicles at charging stations. A recent self-adaptive variant of the metaheuristic “Construct, Merge, Solve & Adapt” (CMSA) is applied in two different ways to solve the tackled problem. The two algorithm variants differ from each other in terms of the solution representations and the mixed-integer linear programming (MILP) models used to solve sub-instances. The effectiveness of both CMSA variants is tested on well-known benchmark instances, and their performances are compared with probabilistic implementations of two constructive heuristics, a Clark & Wright Savings algorithm, and a sequential insertion heuristic. In addition, the proposed algorithm was tested on a reduced version of the problem, the electric vehicle routing problem with simultaneous pickup and delivery, and compared with variable neighborhood search algorithms from the literature. The numerical results show that both CMSA variants outperform CPLEX in the context of small problem instances. Moreover, it is shown that our approach outperforms heuristics and variable neighborhood search algorithms when large problem instances are concerned