Improved Adaptive Large Neighborhood Search Combined with Simulated Annealing (IALNS-SA) Algorithm for Vehicle Routing Problem with Simultaneous Delivery and Pickup and Time Windows
Huan Ma, Tianbin Yang
Abstract
Adaptive Large Neighborhood Search (ALNS) represents a versatile and highly efficient optimization methodology that has demonstrated significant effectiveness in practical applications. This study introduces an enhanced ALNS approach integrated with Simulated Annealing (SA), termed IALNS-SA. The proposed algorithm incorporates supplementary destruction and repair operators within the ALNS framework to augment its robustness and generalization capacity. Additionally, it adopts the SA acceptance criterion to mitigate local optima entrapment. The research investigates the applicability of IALNS-SA to the Vehicle Routing Problem with Simultaneous Delivery and Pickup and Time Windows (VRPSDPTWs), a pivotal challenge in logistics optimization. Through comprehensive evaluation across 56 large-scale benchmark instances, the algorithm’s performance is systematically compared against four established methods: p-SA, DCS, VNS-BSTS, and DGWO. Empirical results indicate that IALNS-SA achieves superior performance relative to DGWO in 69.64% of cases, surpasses VNS-BSTS in 94.64% of instances, and consistently outperforms both p-SA and DCS. The obtained optimal solutions exhibit reduced total vehicle routing distances, thereby substantiating the operational feasibility and algorithmic efficacy of the proposed methodology.