Reinforcement learning-guided adaptive large neighborhood search for vehicle routing problem with time windows

This paper presents PPO-ALNS, a novel hybrid framework that integrates Proximal Policy Optimization (PPO) with Adaptive Large Neighborhood Search (ALNS) for solving the Vehicle Routing Problem with Time Windows (VRPTW). Traditional heuristic methods struggle with balancing exploration and exploitation, while pure reinforcement learning approaches face challenges with discrete decision spaces and complex constraints. Our approach addresses these limitations by formulating ALNS as a Markov Decision Process, where a PPO agent dynamically guides destroy-repair operator selection, solution acceptance criteria, and search termination decisions. We design a comprehensive state representation incorporating problem-specific features and search dynamics, coupled with a four-dimensional action space for effective search coordination. The compound reward mechanism combines immediate rewards with terminal episode rewards, introducing dynamic penalties and adaptive early-stopping to optimize solution quality and computational efficiency. Experiments on VRPTW instances with 20, 50, and 100 customers demonstrate that PPO-ALNS consistently outperforms traditional ALNS, Ant Colony Optimization (ACO), and other Reinforcement Learning (RL)-based operator selection methods, achieving improvements of 11.37–17.41% over baseline approaches. The performance advantage increases with problem complexity, indicating strong scalability. Ablation studies validate the synergistic effect of simultaneous operator learning, while sensitivity analysis confirms optimal performance in medium time window scenarios, highlighting the framework’s effectiveness for complex routing optimization.