An Adaptive Large Neighborhood Search framework for the Multi-Depot Two-Echelon Vehicle Routing Problem with Delivery Options

This paper studies the Multi-Depot Two-Echelon Vehicle Routing Problem with Delivery Options (MD-TEVRP-DO), which integrates multi-depot distribution, satellite-based consolidation, and flexible last-mile service. The problem involves strongly interdependent decisions concerning customer delivery modes, satellite utilization, and first- and second-echelon routing, making effective cross-echelon coordination particularly challenging. First-echelon vehicles transport demand from depots to satellites, while second-echelon vehicles serve customers through either home delivery (HD) or customer pickup (CP). To solve this problem, a coverage-aware, feasibility-preserving Adaptive Large Neighborhood Search (ALNS) framework is proposed. The methodological innovation lies in embedding problem-specific coordination mechanisms within the ALNS search. The algorithm jointly optimizes customer-to-satellite assignment, delivery-mode selection, and second-echelon routes, while first-echelon routes are reconstructed according to the active satellites and their resulting replenishment requirements, thereby explicitly coordinating the two routing echelons. The proposed ALNS combines classical destroy- and- repair operators with problem-specific operators for satellite congestion, delivery-mode misfit, and coupled satellite-route insertion. Computational experiments on benchmark MD-TEVRP–DO instances demonstrate that the proposed ALNS consistently outperforms the existing Hybrid Multi-Population Genetic Algorithm (HMPG) and Simulated Annealing (SA) heuristic. A comparison between the HD+CP and HD-only configurations shows that incorporating CP reduces total distribution cost by approximately 16–17% through improved demand consolidation and reduced second-echelon routing requirements. An exploratory economic assessment further suggests that these savings may improve retailer margins or reduce final prices under suitable cost-pass-through conditions,demonstrating the value of coordinating delivery flexibility with multi-depot two-echelon routing from both operational and economic perspectives.