Solving the Vehicle Routing Problem with Time Windows Using Modified Rat Swarm Optimization Algorithm Based on Large Neighborhood Search

The vehicle routing problem with time windows (VRPTW) remains a formidable challenge, due to the intricate constraints of vehicle capacity and time windows. As a result, an algorithm tailored for this problem must demonstrate robust search capabilities and profound exploration abilities. Traditional methods often struggle to balance global search capabilities with computational efficiency, thus limiting their practical applicability. To address these limitations, this paper introduces a novel hybrid algorithm known as large neighborhood search with modified rat swarm optimization (LNS-MRSO). Modified rat swarm optimization (MRSO) is inspired by the foraging behavior of rat swarms and simulates the search process for optimization problems. Meanwhile, large neighborhood search (LNS) generates potential new solutions by removing and reinserting operators, incorporating a mechanism to embrace suboptimal solutions and strengthening the algorithm's prowess in global optimization. Initial solutions are greedily generated, and five operators are devised to mimic the position updates of the rat swarm, providing rich population feedback to LNS and further enhancing algorithm performance. To validate the effectiveness of LNS-MRSO, experiments were conducted using the Solomon VRPTW benchmark test set. The results unequivocally demonstrate that LNS-MRSO achieves optimal solutions for all 39 test instances, particularly excelling on the R2 and RC2 datasets with percentage deviations improved by 5.1% and 8.8%, respectively, when compared to the best-known solutions (BKSs). Furthermore, when compared to state-of-the-art algorithms, LNS-MRSO exhibits remarkable advantages in addressing VRPTW problems with high loading capacities and lenient time windows. Additionally, applying LNS-MRSO to an unmanned concrete-mixing station further validates its practical utility and scalability.