Oct, 2023

基于强化学习的超启发式方法增强列生成在车辆路径规划与调度问题中的应用

PDF
TL;DR基于强化学习的超启发式框架，在列生成中提供更好的整数解和加速收敛，通过减少含潜在最优解边的网络规模，在解决车辆路径和巴士司机调度问题中比传统方法降低至多 27.9% 和 15.4% 的总成本。
column generationreinforcement learning-based hyper-heuristic frameworkcombinatorial optimizationvehicle routing problembus driver scheduling problem
发现论文，激发创造
  • 基于深度强化学习的列生成算法框架

    本文提出了 RLCG—— 一种用于解决大规模整数线性规划的迭代算法，它是第一个采用强化学习方法的列生成算法，并使用图神经网络表示感兴趣的 LP 的变量约束结构，成功应用于切割库存问题和带时间窗口的车辆路由问题中，相对于常用的贪心策略，该算法平均缩短 22.4％CSP 和 40.9％VRPTW 的 CG 迭代次数。

    Jun, 2022

  • 利用图神经网络增强列生成算法，实现乘客行程规划和机组班次安排的联合优化

    通过使用 AGGNNI-CG 方法（基于注意力机制和门控循环神经网络的混合方法）解决服务调度的基本问题，本研究在复杂的动态移动服务中联合优化乘客行程规划和人员排班，取得了接近最优解决方案，对现有系统进行了显著改进。

    Jan, 2024

  • 基于机器学习的定价启发式算法增强列生成法在图着色中的应用

    本文提出使用基于机器学习的定价启发式方法（MLPH）解决大规模优化问题中的瓶颈，经过在图着色问题中的实验表明 MLPH 相比于六种最先进的方法可以显着提高 Column Generation 方法的效率，使其与分支定界法得到更好的表现。

    Dec, 2021

  • 一种基于强化学习的多列选择策略对于列生成

    利用基于强化学习的多列选择策略，通过选择最有前途的列以提高目标值和加快收敛速度，比较传统单列和多列选择策略，在切割库存问题和图着色问题中取得了显著的收敛速度和迭代次数的减少。

    Dec, 2023

  • 基于自适应模拟退火和强化学习的电动车容量路径问题新超启发式

    本研究提出了一种称为 HHASA_{RL} 的超启发式方法来解决容量限制电动车路线问题，该问题包含了电动车的充电站数量有限以及行驶范围的限制，这种方法通过将多臂赌博机方法和自适应模拟退火算法相结合，以改进已有的解决方案并在 IEEE WCCI2020 竞赛中获得最佳平均值。

    Jun, 2022

  • 解决路径规划问题学习改进启发式方法

    本文提出一种基于 self-attention 的深度强化学习框架，以学习解决旅行商问题（TSP）和有容量车辆路径问题（CVRP）的改进启发式算法，实验表明该方法性能优于现有的深度学习方法，并且具有良好的泛化能力。

    Dec, 2019

  • 利用强化学习实现碳减排潜力的三维装载有容量的车辆路径问题

    使用强化学习模型解决三维装备车辆路径问题，使得物流优化向大规模应用迈出有希望的第一步。

    Jul, 2023

  • 一种基于神经列生成理论的二维装箱车辆路径问题的求解方法

    本研究论文通过整合注意力和循环机制的先进机器学习技术，提出了一种精确算法来解决具有二维装载约束和后进先出规则的车辆路径问题。该算法在各个问题实例中平均加速了 29.79%，并成功解决了标准测试环境中的一个开放问题，表明了机器学习模型的结合带来的显著改进。

    Jun, 2024

  • 运用深度强化学习解决车辆路径问题

    本文介绍了强化学习在处理 NP-Hard 组合优化问题，特别是车辆路径问题方面的应用。作者将问题建模成一个马尔科夫决策过程，并采用了 Actor-Critic 类的 PPO 方法和基于卷积神经网络的神经架构。尽管与最先进的 OR-TOOLS 解算器相比略逊一筹，但该算法具有较好的泛化能力和较短的解答时间。未来的研究方向是提高算法的性能表现。

    Jul, 2022

  • 电容车辆路径问题的神经大邻域搜索

    本文提出了一种基于深度神经网络和注意力机制的学习启发式算法的大邻域搜索框架，用于解决车辆路径问题，该方法在性能方面优于现有的机器学习方法，也接近于现有优化方法的性能。

    Nov, 2019