Scholarlink

<p>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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

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

  • 期刊论文

  • 发表日期：

    2025年10月25日

查看全文
  • Zhaohui Wang,
  • Qiao Cui,
  • Bin Tan,
  • Xiao Yang,
  • Weibang Zhou,
  • Xiangsheng Huang

摘要

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.