DPN: 分离划分和导航的神经求解器:最大最小车辆路径问题
本文提出了一种基于深度神经网络和注意力机制的学习启发式算法的大邻域搜索框架,用于解决车辆路径问题,该方法在性能方面优于现有的机器学习方法,也接近于现有优化方法的性能。
Nov, 2019
本文介绍了强化学习在处理 NP-Hard 组合优化问题,特别是车辆路径问题方面的应用。作者将问题建模成一个马尔科夫决策过程,并采用了 Actor-Critic 类的 PPO 方法和基于卷积神经网络的神经架构。尽管与最先进的 OR-TOOLS 解算器相比略逊一筹,但该算法具有较好的泛化能力和较短的解答时间。未来的研究方向是提高算法的性能表现。
Jul, 2022
Deep Policy Dynamic Programming 优先和限制来自深度神经网络的策略,以结合学习嵌入式启发式和动态规划 (DP) 算法的优点,以优化旅行商问题 (TSP)、车辆路径问题 (VRP) 和带时间窗口的 TSP (TSPTW) 的性能,同时胜过大多数其他解决 TSPs、VRPs 和 TSPTWs 的 ' 神经方法 '。
Feb, 2021
基于深度强化学习,使用编码器 - 解码器的注意机制生成的策略在某些车辆路径问题上表现出有效性,但在某些复杂车辆路径问题上,仍缺乏有效的强化学习方法。本研究针对一种包含多辆卡车和多段路径要求的车辆路径问题变体,扩展现有的编码器 - 解码器注意模型,使其能够处理多辆卡车和多段路径需求,并在日本汽车零部件制造商爱信公司的实际供应链环境中测试,发现我们的算法优于爱信公司的最佳解决方案。
Jan, 2024
本文提出了一种新的分层路由优化器,该优化器结合了优化和机器学习,通过可学习参数解决了有挑战性的最后一英里物流服务中遇到的困难的实际问题,并使用亚马逊的真实交付数据集证明了这种方法的重要性。
Mar, 2023
为了提高神经车辆路径问题(VRP)求解器在实际环境中的可行性,我们设计了一个辅助策略,通过学习本地可转移的拓扑特征来改善神经 VRP 求解器的表现,将其与典型的建构策略相结合,形成一个集成策略。经过联合训练,这个集成策略使得各个策略相互协作和互补,从而提高了泛化能力。实验证明,与最先进的构造方法相比,这个集成策略在两个著名的基准测试中(TSPLIB 和 CVRPLIB)表现出更好的泛化性能,并且在数千个节点的真实世界问题上也能工作得很好。
Aug, 2023
该论文通过属性组合的方式,建立了一个统一模型,成功解决了车辆路径问题的不同组合情况,大幅提高了解决方案的效率并在物流应用中取得了显著的性能提升。
Feb, 2024
使用注意力编码解码结构和一种新颖的插入启发式算法,我们以构造迭代深度学习算法解决带时间窗口的车辆路径问题,并比最佳已知学习解决方案更好地解决了该问题。
Dec, 2022
研究论文研究了无人机车辆路径问题,提出了一种综合考虑启发式方法和强化学习框架的解决方案,以提高解决方案的质量和计算速度。
Apr, 2024
本文提出了一个端到端的框架,使用强化学习来解决车辆路径问题 (VRP),我们训练一个单一的模型,仅通过观察奖励信号和遵守可行性规则,就可以找到给定分布采样的问题实例的近最优解。通过将策略梯度算法应用于优化其参数,我们的模型在实时中以连续操作序列的形式生成解决方案,无需为每个新问题实例重新训练,我们的方法在解决负载容量 VRP 的中等规模实例时,在解决质量上优于经典的启发式算法和 Google 的 OR-Tools,同时具有可比较的计算时间,在本文中还探讨了分裂交付对解决质量的影响。我们的提出的框架可以应用于其他 VRP 变体,例如随机 VRP,并具有应用于组合优化问题的潜力。
Feb, 2018