An Adaptive Large Neighborhood Search Method for the Two-Echelon Vehicle Routing Problem with Clustered Customers

In many real-world logistics systems, two-echelon distribution structures and clustered customer demands often coexist. However, traditional Two-Echelon Vehicle Routing Problems (2E-VRPs) mainly focus on the coordination between depots, satellites, and customers, while usually ignoring clustered customer service requirements. To fill this research gap, this study investigates a novel variant of the 2E-VRP, called the 2E-VRP with Clustered Customers (2E-VRP-CC). In this problem, customers in the second echelon are partitioned into predefined clusters, and all customers within a cluster must be visited consecutively by the same vehicle. For the problem, a Mixed-Integer Linear Programming (MILP) model is first established, followed by the development of an Adaptive Large Neighborhood Search (ALNS) algorithm integrated with a local search method. To validate the effectiveness of the proposed algorithm, comparisons are conducted on instance sets adapted from the literature. For the traditional 2E-VRP, which is a special case of the 2E-VRP-CC, the proposed algorithm is compared with existing methods in the literature. For the proposed 2E-VRP-CC, it is compared with the CPLEX solver. Extensive computational experiments demonstrate that the proposed algorithm can achieve high-quality solutions within relatively short computing times, confirming its effectiveness and efficiency. In addition, sensitivity analysis shows that the number of customer clusters has a significant impact on transportation costs. The results indicate that moderately increasing the number of customer clusters can effectively reduce operational costs and provide practical decision support for customer clustering design and two-echelon logistics planning.