大规模车辆路径规划的委派学习
为了提高神经车辆路径问题(VRP)求解器在实际环境中的可行性,我们设计了一个辅助策略,通过学习本地可转移的拓扑特征来改善神经 VRP 求解器的表现,将其与典型的建构策略相结合,形成一个集成策略。经过联合训练,这个集成策略使得各个策略相互协作和互补,从而提高了泛化能力。实验证明,与最先进的构造方法相比,这个集成策略在两个著名的基准测试中(TSPLIB 和 CVRPLIB)表现出更好的泛化性能,并且在数千个节点的真实世界问题上也能工作得很好。
Aug, 2023
本文提出了一种元学习框架,通过元学习可以有效地训练出初始化的模型,并具有快速适应新任务的能力,在旅行商问题和车辆路径问题的综合实验中,证明了方法的有效性。
May, 2023
本文提出了一种基于深度神经网络和注意力机制的学习启发式算法的大邻域搜索框架,用于解决车辆路径问题,该方法在性能方面优于现有的机器学习方法,也接近于现有优化方法的性能。
Nov, 2019
本文提出了一个端到端的框架,使用强化学习来解决车辆路径问题 (VRP),我们训练一个单一的模型,仅通过观察奖励信号和遵守可行性规则,就可以找到给定分布采样的问题实例的近最优解。通过将策略梯度算法应用于优化其参数,我们的模型在实时中以连续操作序列的形式生成解决方案,无需为每个新问题实例重新训练,我们的方法在解决负载容量 VRP 的中等规模实例时,在解决质量上优于经典的启发式算法和 Google 的 OR-Tools,同时具有可比较的计算时间,在本文中还探讨了分裂交付对解决质量的影响。我们的提出的框架可以应用于其他 VRP 变体,例如随机 VRP,并具有应用于组合优化问题的潜力。
Feb, 2018
本文介绍了强化学习在处理 NP-Hard 组合优化问题,特别是车辆路径问题方面的应用。作者将问题建模成一个马尔科夫决策过程,并采用了 Actor-Critic 类的 PPO 方法和基于卷积神经网络的神经架构。尽管与最先进的 OR-TOOLS 解算器相比略逊一筹,但该算法具有较好的泛化能力和较短的解答时间。未来的研究方向是提高算法的性能表现。
Jul, 2022
该研究提出了一种基于强化学习的方法,结合拉格朗日松弛技术和约束策略优化,用于解决软限制的车辆路径规划问题,并在旅行商问题、容量限制车辆路径问题和带时间窗口的容量限制车辆路径问题上进行了验证,表明其对解决已有方法难以解决的问题有很好的竞争力。
Jul, 2022
通过跨问题学习和细调不同变种目标问题的 Transformer 模型,本论文提出了一种用于改善车辆路线问题的神经启发式训练方法,展示了与从头开始训练相比较,全细调和适配器细调技术能够取得更好性能和参数效率的优势,并证明了该方法在交叉分布应用和通用性方面的有利影响。
Apr, 2024
基于深度强化学习,使用编码器 - 解码器的注意机制生成的策略在某些车辆路径问题上表现出有效性,但在某些复杂车辆路径问题上,仍缺乏有效的强化学习方法。本研究针对一种包含多辆卡车和多段路径要求的车辆路径问题变体,扩展现有的编码器 - 解码器注意模型,使其能够处理多辆卡车和多段路径需求,并在日本汽车零部件制造商爱信公司的实际供应链环境中测试,发现我们的算法优于爱信公司的最佳解决方案。
Jan, 2024
本文研究使用强化学习解决一种典型的组合优化问题:车辆路径问题,将其形式化为强化学习框架,并在基准实例上比较了两种最有前途的强化学习方法与传统求解技术。研究发现,与传统求解器相比,强化学习算法具有许多优点,尤其是在解决更复杂的组合优化问题以及加速问题求解方面。
Jan, 2022
该论文通过属性组合的方式,建立了一个统一模型,成功解决了车辆路径问题的不同组合情况,大幅提高了解决方案的效率并在物流应用中取得了显著的性能提升。
Feb, 2024