PyVRP:一个高性能的 VRP 求解包
本文提出了一个端到端的框架,使用强化学习来解决车辆路径问题 (VRP),我们训练一个单一的模型,仅通过观察奖励信号和遵守可行性规则,就可以找到给定分布采样的问题实例的近最优解。通过将策略梯度算法应用于优化其参数,我们的模型在实时中以连续操作序列的形式生成解决方案,无需为每个新问题实例重新训练,我们的方法在解决负载容量 VRP 的中等规模实例时,在解决质量上优于经典的启发式算法和 Google 的 OR-Tools,同时具有可比较的计算时间,在本文中还探讨了分裂交付对解决质量的影响。我们的提出的框架可以应用于其他 VRP 变体,例如随机 VRP,并具有应用于组合优化问题的潜力。
Feb, 2018
本文提出了一种元学习框架,通过元学习可以有效地训练出初始化的模型,并具有快速适应新任务的能力,在旅行商问题和车辆路径问题的综合实验中,证明了方法的有效性。
May, 2023
该研究提出了一种基于强化学习的方法,结合拉格朗日松弛技术和约束策略优化,用于解决软限制的车辆路径规划问题,并在旅行商问题、容量限制车辆路径问题和带时间窗口的容量限制车辆路径问题上进行了验证,表明其对解决已有方法难以解决的问题有很好的竞争力。
Jul, 2022
这篇论文提出了一种基于强化学习的名为 “Multi-Agent Attention Model” 的算法,能够利用较长的离线训练时间快速解决城市物流配送中必不可少的 “多车辆路径问题(MVRPSTW)”,该算法以车辆旅游生成过程为基础,提出了一种具有注意力层的编码器 - 解码器框架来迭代地生成多辆车的路径,通过对不同规模的合成网络进行评估,证明该算法的效果优于谷歌 OR-Tools 和传统方法,并验证了模型的稳健性。
Feb, 2020
通过强化学习方法优化随机车辆路径问题,减少货物运输中的行程成本,提出一种新的模型,用于考虑不确定的行程成本和需求,以及确定的客户时间窗口,通过基于注意力的神经网络进行训练,实现路径成本的最小化,并超越基于蚁群算法的模型,在行程成本上减少了 1.73%,该模型独特地整合了外部信息,展现了在不同环境中的稳健性,对未来随机车辆路径问题研究和产业应用具有价值。
Feb, 2024
本文介绍了强化学习在处理 NP-Hard 组合优化问题,特别是车辆路径问题方面的应用。作者将问题建模成一个马尔科夫决策过程,并采用了 Actor-Critic 类的 PPO 方法和基于卷积神经网络的神经架构。尽管与最先进的 OR-TOOLS 解算器相比略逊一筹,但该算法具有较好的泛化能力和较短的解答时间。未来的研究方向是提高算法的性能表现。
Jul, 2022
Deep Policy Dynamic Programming 优先和限制来自深度神经网络的策略,以结合学习嵌入式启发式和动态规划 (DP) 算法的优点,以优化旅行商问题 (TSP)、车辆路径问题 (VRP) 和带时间窗口的 TSP (TSPTW) 的性能,同时胜过大多数其他解决 TSPs、VRPs 和 TSPTWs 的 ' 神经方法 '。
Feb, 2021
该研究介绍了一种用于解决车辆路径问题的 RouteFinder 框架,通过并行化环境、高效的采样方法和全球特征嵌入等技术,实现了对多种 VRP 变体的统一建模和解决,取得了竞争性的实验结果。
Jun, 2024
我们提出了一种创新的多智能体方法,聚焦于合作车辆路径问题,通过驾驶员个体有理性约束来优化物流公司间市场平台上的订单交换,实现降低行驶距离、提高系统运营效率,并确保市场长期可持续性。
Aug, 2023
本文研究使用强化学习解决一种典型的组合优化问题:车辆路径问题,将其形式化为强化学习框架,并在基准实例上比较了两种最有前途的强化学习方法与传统求解技术。研究发现,与传统求解器相比,强化学习算法具有许多优点,尤其是在解决更复杂的组合优化问题以及加速问题求解方面。
Jan, 2022