Enhancing Column Generation by Reinforcement Learning-Based Hyper-Heuristic for Vehicle Routing and Scheduling Problems

📄 arXiv: 2310.09686v1 📥 PDF

作者: Kuan Xu, Li Shen, Lindong Liu

分类: cs.LG

发布日期: 2023-10-15

💡 一句话要点

提出基于强化学习的超启发式方法以增强列生成算法在车辆调度中的应用

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 列生成 强化学习 超启发式 车辆调度 组合优化 调度问题 算法优化

📋 核心要点

  1. 现有的列生成方法在解决组合优化问题时，迭代步骤需要处理NP难度的约束最短路径问题，效率较低。
  2. 本文提出的RLHH框架通过强化学习选择低级启发式方法，优化CG的迭代过程，加速收敛并提高解的质量。
  3. 实验结果表明，RLHH在VRPTW和BDSP问题上分别实现了27.9%和15.4%的成本降低，且计算时间相对较短。

📝 摘要（中文）

列生成（CG）是一种通过动态生成变量来解决大规模问题的重要方法，广泛应用于车辆调度等组合优化问题。现有的启发式加速方法在解决不同问题时缺乏通用性。本文提出了一种基于强化学习的超启发式框架RLHH，旨在提升CG的性能。RLHH作为CG中的选择模块，在每次迭代中由RL代理选择低级启发式方法，构建仅包含更可能成为最优解边的简化网络。针对时间窗车辆调度问题（VRPTW）和公交司机调度问题（BDSP），RLHH在测试场景中分别将总成本降低了27.9%和15.4%，且计算时间相当或更少。该方法是首个在解质量上超越传统方法的RL基础CG方法，推动了CG在组合优化中的应用。

🔬 方法详解

问题定义：本文旨在解决车辆调度和调度问题中的列生成算法效率低下的问题，现有的启发式方法在不同问题上的适用性不足，导致求解效率和解质量不理想。

核心思路：通过引入强化学习，RLHH框架能够在每次CG迭代中选择最合适的低级启发式方法，从而构建一个简化的网络，专注于更有可能成为最优解的边，提升求解效率。

技术框架：RLHH框架嵌入在列生成算法中，主要包括RL代理、低级启发式选择模块和简化网络构建模块。RL代理通过学习历史数据来优化选择策略，低级启发式方法则用于生成有效的解。

关键创新：RLHH是首个基于强化学习的列生成方法，显著提高了解的质量，超越了传统的启发式方法，展示了在组合优化领域的广泛应用潜力。

关键设计：在RLHH中，强化学习代理的训练使用了特定的奖励机制，以鼓励选择能够有效减少成本的启发式方法，网络结构设计上采用了适应性调整策略，以应对不同问题的复杂性。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果显示，RLHH在时间窗车辆调度问题（VRPTW）中将总成本降低了27.9%，在公交司机调度问题（BDSP）中降低了15.4%。这些结果在计算时间上与现有最佳低级启发式方法相当或更少，展示了RLHH的优越性。

🎯 应用场景

该研究的潜在应用领域包括物流管理、公共交通调度和智能交通系统等。通过优化车辆调度和司机排班，RLHH能够有效降低运营成本，提高服务效率，具有显著的实际价值和广泛的应用前景。

📄 摘要（原文）

Column generation (CG) is a vital method to solve large-scale problems by dynamically generating variables. It has extensive applications in common combinatorial optimization, such as vehicle routing and scheduling problems, where each iteration step requires solving an NP-hard constrained shortest path problem. Although some heuristic methods for acceleration already exist, they are not versatile enough to solve different problems. In this work, we propose a reinforcement learning-based hyper-heuristic framework, dubbed RLHH, to enhance the performance of CG. RLHH is a selection module embedded in CG to accelerate convergence and get better integer solutions. In each CG iteration, the RL agent selects a low-level heuristic to construct a reduced network only containing the edges with a greater chance of being part of the optimal solution. In addition, we specify RLHH to solve two typical combinatorial optimization problems: Vehicle Routing Problem with Time Windows (VRPTW) and Bus Driver Scheduling Problem (BDSP). The total cost can be reduced by up to 27.9\% in VRPTW and 15.4\% in BDSP compared to the best lower-level heuristic in our tested scenarios, within equivalent or even less computational time. The proposed RLHH is the first RL-based CG method that outperforms traditional approaches in terms of solution quality, which can promote the application of CG in combinatorial optimization.