DBLS-SP: A Dynamic Balanced Local Search with Solution Pool for the Vehicle Routing Problem with Simultaneous Pickup and Delivery and Time Windows
Abstract
This paper studies the Vehicle Routing Problem with Simultaneous Pickup and Delivery and Time Windows (VRPSPDTW). The problem arises from reverse logistics, last-mile distribution, and circular logistics, where vehicles must serve delivery and pickup demands while respecting vehicle capacity and customer time-window constraints. This work develops DBLS-SP. The method combines an improved insertion-based initialization procedure, a repair-oriented dynamic scoring strategy, ejection-based reinsertion, multi-armed-bandit control of the route-inheritance ratio, vehicle-layer archive-guided route descent, and quality-first nearest-neighbor pool replacement. Computational experiments on the Wang–Chen (WC) and JD Logistics (JD) benchmark instances show that DBLS-SP obtains the best algorithmic solution on 67 of 68 WC instances and the best or tied-best objective value on 16 of 20 JD instances. The ablation study confirms the contribution of the main components, and the proposed reduction strategy removes more infeasible paths than the original reduction rule while preserving feasibility.