Application of Adapt-CMSA to the Two-Echelon Electric Vehicle Routing Problem with Simultaneous Pickup and Deliveries

This study addresses the two-echelon electric vehicle routing problem with simultaneous pickup and deliveries. In a two-echelon distribution network, large vehicles transport goods from central warehouses to satellites, while smaller and environmentally friendly vehicles distribute goods from these satellites to final customers. The considered problem also includes simultaneous pickup and delivery constraints that usually arise as a reverse logistics practice. A MILP model is developed and solved for small-sized problem instances using CPLEX. Since the tackled problem becomes rather complex because of the multi-tier structure and constraints, solving even small-sized instances using CPLEX requires very long computation times. Therefore, the application of a selfadaptive variant of the hybrid metaheuristic Construct, Merge, Solve & Adapt is proposed. In the context of problem instances too large for the application of CPLEX, our algorithm is compared to probabilistic versions of two well-known constructive heuristics. The numerical results show that our algorithm outperforms CPLEX in the context of rather small problem instances. Moreover, it is shown to outperform the heuristic algorithms when larger problem instances are concerned.