学习协作策略以解决 NP-hard 路径规划问题
本文提出一种基于 self-attention 的深度强化学习框架,以学习解决旅行商问题(TSP)和有容量车辆路径问题(CVRP)的改进启发式算法,实验表明该方法性能优于现有的深度学习方法,并且具有良好的泛化能力。
Dec, 2019
本文介绍了强化学习在处理 NP-Hard 组合优化问题,特别是车辆路径问题方面的应用。作者将问题建模成一个马尔科夫决策过程,并采用了 Actor-Critic 类的 PPO 方法和基于卷积神经网络的神经架构。尽管与最先进的 OR-TOOLS 解算器相比略逊一筹,但该算法具有较好的泛化能力和较短的解答时间。未来的研究方向是提高算法的性能表现。
Jul, 2022
基于深度强化学习的旅行购货问题(TPP)解决方案,通过使用双向图表示 TPP、策略网络逐步构建路线,并通过线性规划获取购货计划,利用元学习策略稳定训练策略网络。在综合合成和标准基准测试上,相较于已有启发式算法,我们的 DRL 方法能够显著提升解决方案质量(降低 40%-90% 的最优性差距),尤其在大型实例上具备高效性。
Apr, 2024
Deep Policy Dynamic Programming 优先和限制来自深度神经网络的策略,以结合学习嵌入式启发式和动态规划 (DP) 算法的优点,以优化旅行商问题 (TSP)、车辆路径问题 (VRP) 和带时间窗口的 TSP (TSPTW) 的性能,同时胜过大多数其他解决 TSPs、VRPs 和 TSPTWs 的 ' 神经方法 '。
Feb, 2021
本文研究使用强化学习解决一种典型的组合优化问题:车辆路径问题,将其形式化为强化学习框架,并在基准实例上比较了两种最有前途的强化学习方法与传统求解技术。研究发现,与传统求解器相比,强化学习算法具有许多优点,尤其是在解决更复杂的组合优化问题以及加速问题求解方面。
Jan, 2022
为了提高神经车辆路径问题(VRP)求解器在实际环境中的可行性,我们设计了一个辅助策略,通过学习本地可转移的拓扑特征来改善神经 VRP 求解器的表现,将其与典型的建构策略相结合,形成一个集成策略。经过联合训练,这个集成策略使得各个策略相互协作和互补,从而提高了泛化能力。实验证明,与最先进的构造方法相比,这个集成策略在两个著名的基准测试中(TSPLIB 和 CVRPLIB)表现出更好的泛化性能,并且在数千个节点的真实世界问题上也能工作得很好。
Aug, 2023
本文介绍了一种基于深度强化学习和约束编程的混合算法,应用于复杂的组合优化问题,并在实验中成功运用于旅行商问题和投资组合优化问题,表现优于单独的深度强化学习和约束编程算法,同时也达到了与工业级求解器相竞争的水平。
Jun, 2020
本文提出了一种利用神经网络和强化学习解决组合优化问题的框架,特别关注旅行推销员问题和背包问题,证明了该方法在不需要太多工程和启发式设计的情况下在二维欧几里得图上取得接近最优结果,并且可以得到具有多达 200 个项目实例的最优解。
Nov, 2016
本文提出了一个端到端的框架,使用强化学习来解决车辆路径问题 (VRP),我们训练一个单一的模型,仅通过观察奖励信号和遵守可行性规则,就可以找到给定分布采样的问题实例的近最优解。通过将策略梯度算法应用于优化其参数,我们的模型在实时中以连续操作序列的形式生成解决方案,无需为每个新问题实例重新训练,我们的方法在解决负载容量 VRP 的中等规模实例时,在解决质量上优于经典的启发式算法和 Google 的 OR-Tools,同时具有可比较的计算时间,在本文中还探讨了分裂交付对解决质量的影响。我们的提出的框架可以应用于其他 VRP 变体,例如随机 VRP,并具有应用于组合优化问题的潜力。
Feb, 2018
该研究论文提出了一个基于深度强化学习的新框架(Arc-DRL),用于解决复杂的有负载约束的弧路由问题(CPP-LC),并通过与元启发式方法的比较实验证明了该框架在解决 CPP-LC 方面的优越性。
Oct, 2023