强化学习解决带时间窗的随机车辆路径问题
本研究旨在解决在不确定条件下优化车辆路线的具有挑战性任务的随机车辆路径问题(SVRP)中,利用强化学习(RL)和机器学习(ML)技术的利用不足的问题。我们提出了一个全面解决 SVRP 中预测性关键源的全新端到端框架,采用简单而有效的架构和定制的训练方法来利用 RL agent。通过比较分析,我们的模型相较于一个广泛采用的最先进元启发式算法表现出了更好的性能,实现了显著的 3.43% 的行程成本降低。此外,该模型在不同的 SVRP 设置中表现出了鲁棒性,突出了它的适应能力和学习优化路径策略在不同环境中。我们框架的公开实现作为未来研究努力的宝贵资源,旨在推进基于 RL 的 SVRP 解决方案。
Nov, 2023
这篇论文提出了一种基于强化学习的名为 “Multi-Agent Attention Model” 的算法,能够利用较长的离线训练时间快速解决城市物流配送中必不可少的 “多车辆路径问题(MVRPSTW)”,该算法以车辆旅游生成过程为基础,提出了一种具有注意力层的编码器 - 解码器框架来迭代地生成多辆车的路径,通过对不同规模的合成网络进行评估,证明该算法的效果优于谷歌 OR-Tools 和传统方法,并验证了模型的稳健性。
Feb, 2020
本文提出了一个端到端的框架,使用强化学习来解决车辆路径问题 (VRP),我们训练一个单一的模型,仅通过观察奖励信号和遵守可行性规则,就可以找到给定分布采样的问题实例的近最优解。通过将策略梯度算法应用于优化其参数,我们的模型在实时中以连续操作序列的形式生成解决方案,无需为每个新问题实例重新训练,我们的方法在解决负载容量 VRP 的中等规模实例时,在解决质量上优于经典的启发式算法和 Google 的 OR-Tools,同时具有可比较的计算时间,在本文中还探讨了分裂交付对解决质量的影响。我们的提出的框架可以应用于其他 VRP 变体,例如随机 VRP,并具有应用于组合优化问题的潜力。
Feb, 2018
本文提出一种基于注意力机制、可同时开展多个路径,并能在路径和客户之间进行艰难的权衡的政策模型 ——JAMPR,通过对三个不同工具路由问题的全面实验,表明该模型对不同问题规模均有效,并且优于现有的基于构造算法方法,对于其中两个问题类型,甚至优于相应比较方法。
Jun, 2020
该研究提出了一种基于强化学习的方法,结合拉格朗日松弛技术和约束策略优化,用于解决软限制的车辆路径规划问题,并在旅行商问题、容量限制车辆路径问题和带时间窗口的容量限制车辆路径问题上进行了验证,表明其对解决已有方法难以解决的问题有很好的竞争力。
Jul, 2022
本文提出一种混合方法,将强化学习、策略推进和可满足性求解器相结合,以实现计算时间和解决方案质量之间的可调节权衡,该方法可以解决任意规模的问题,且无需额外训练,在解决车辆路由问题中的效果优于现有的基于学习的方法和元启发式算法,更具有泛化性。
Jun, 2022
我们研究了带时间窗的车辆路径问题(VRPTW)和随机旅行时间,在做出路径决策之前,决策者观察相关的上下文信息,表示为特征变量。尽管有大量有关随机 VRP 的文献,但在此情境中对特征变量的整合受到了限制的关注。我们介绍了上下文随机 VRPTW,该问题在观察到的特征条件下最小化总运输成本和预期迟到惩罚。由于旅行时间和特征的联合分布是未知的,我们提出了使用历史数据提供问题的近似解的新型数据驱动规定模型。我们区分了基于点的近似、样本平均近似和惩罚近似这些规定模型,并从不同角度处理随机旅行时间和特征问题。我们开发了专门的分枝 - 定价割算法来解决这些数据驱动的规定模型。在我们的计算实验中,我们比较了不同方法在多达一百个客户的实例上的样本外成本性能。我们的结果表明,令人惊讶的是,一个基于特征的样本平均近似在大多数设置中优于现有方法和新方法。
Feb, 2024
本文研究使用强化学习解决一种典型的组合优化问题:车辆路径问题,将其形式化为强化学习框架,并在基准实例上比较了两种最有前途的强化学习方法与传统求解技术。研究发现,与传统求解器相比,强化学习算法具有许多优点,尤其是在解决更复杂的组合优化问题以及加速问题求解方面。
Jan, 2022
本文介绍了强化学习在处理 NP-Hard 组合优化问题,特别是车辆路径问题方面的应用。作者将问题建模成一个马尔科夫决策过程,并采用了 Actor-Critic 类的 PPO 方法和基于卷积神经网络的神经架构。尽管与最先进的 OR-TOOLS 解算器相比略逊一筹,但该算法具有较好的泛化能力和较短的解答时间。未来的研究方向是提高算法的性能表现。
Jul, 2022
使用注意力编码解码结构和一种新颖的插入启发式算法,我们以构造迭代深度学习算法解决带时间窗口的车辆路径问题,并比最佳已知学习解决方案更好地解决了该问题。
Dec, 2022