技术人员路径规划和调度问题的增强迭代局部搜索
针对一个多路径单仓库场景下的检测车辆,提出了一种最优的输电线检测方法,该方法以旅行商问题为基础,运用了整数线性规划和组合元启发式算法。该方法在电力变电站进行了验证。
Feb, 2023
本文旨在开发一种用于一类特殊旅行推销员问题(TSP)的学习方法,即接送 TSP(PDTSP),该方法通过一系列一对一接送节点找到最短路径。我们利用可行解算空间中的操作符来解决 PDTSP,这些操作符将一个可行解映射到另一个可行解,从而限制解决方案搜索范围。通过与经典 OR 算法和现有学习方法进行比较,结果表明我们的方法可以找到比基准更短的路径。
Apr, 2024
本研究提出了 Variable Strategy Reinforced LKH (VSR-LKH) 与 VSR-LKH-3 算法,分别引入了三种强化学习方法与 LKH 算法相结合,以解决 TSP 问题和 TSP 变体(包括 TSPTW 和 CTSP),经 236 个 TSP 基准测试表明,这些算法具有显著的性能优势。
Jul, 2022
对于庞大规模的旅行推销员问题(TSP),现有算法在计算效率和解决方案质量方面面临巨大挑战。为了解决这个问题,我们提出了一种分层销毁和修复(HDR)方法,通过一系列精心设计的销毁和修复操作来改进初始解。一个关键创新概念是分层搜索框架,它递归地修复部分边缘,并将输入实例压缩成小规模的 TSP,在某种等价保证下。这个巧妙的搜索框架能够在合理的时间内提供极具竞争力的解决方案。基于 19 个著名的大规模实例(城市数量从 10,000 到 10,000,000 个),公平比较显示 HDR 在计算效率和解决方案质量方面与现有最先进的 TSP 算法高度竞争。值得注意的是,在 3,162,278 个和 10,000,000 个城市的两个大型实例中,HDR 打破了 LKH 及其变体先前创下的世界纪录(即无论计算时间如何,都是最好的已知结果),而 HDR 完全独立于 LKH。最后,通过消融研究来证明分层搜索框架的重要性和有效性。
Aug, 2023
提出了一种基于图神经网络和引导局部搜索的 TSP(旅行商问题)混合数据驱动方法,该方法能够在不损失解决方案质量的同时,快速求解大规模 TSP 实例,经实验证明,我们将 100 个节点问题集的平均最优性差从 1.534% 减少到 0.705%,将 20 个节点实例推广到 100 个节点问题集时,我们将最优性差从 18.845% 减少到 2.622%,提高了 2 倍和 7 倍。
Oct, 2021
通过聚类的数据驱动方法,将车辆路径问题分解成子问题以降低复杂性,并应用剪枝和局部搜索来优化解决方案。结果表明,该方法在解决大规模车辆路径问题时优于传统基于空间信息的方法,并能够适应不同情景的路由问题。
Jan, 2024
介绍 2021 年国际人工智能联合大会(IJCAI-21)上第一个旅行推销员问题(TSP)人工智能竞赛,关注基于学习的算法,介绍了该竞赛的问题、比赛安排、获胜方法和结果概述。竞赛的胜利方法使 AI 在随机路由问题上取得了技术进步,也使路由问题成为 AI 研究人员感兴趣的问题设定。同时,该比赛所使用的路由问题模拟器现已成为开源工具,可以成为其他研究人员使用的新 AI 方法基准测试。
Jan, 2022
本研究提出了一种基于层次强化学习的端到端学习框架,称为 H-TSP,用于解决大规模 TSP 问题,通过选择子集并使用深度学习模型直接生成解决方案,具有可扩展和高效性。
Apr, 2023
本文研究了旅行商问题的扩展 —— 多旅行商问题(mTSP),并提出了一个双阶段的迭代式启发式算法 ITSHA 来解决带有 minsum 和 minmax 目标的 mTSP 问题。实验结果表明,该算法在多目标下均优于现有启发式算法。
Jan, 2022
本文使用深度图卷积神经网络模型对荷兰铁路公司列车单元调遣问题进行了研究,为了提高本问题的计算效率,将神经网络模型和局部搜索启发算法相结合,提高了解决方案的预测准确率和决策速度。
Jul, 2019