规划电力传输线巡检的多旅行商问题
本文通过应用组合元启发式算法,采用适当的代价函数,提出了一种基于自主多旋翼的容错电力传输线检查规划方法,其涉及故障容错、电池预算限制、以及满足成功重新规划时间窗口的多车辆路径规划问题。
Feb, 2023
本文旨在开发一种用于一类特殊旅行推销员问题(TSP)的学习方法,即接送 TSP(PDTSP),该方法通过一系列一对一接送节点找到最短路径。我们利用可行解算空间中的操作符来解决 PDTSP,这些操作符将一个可行解映射到另一个可行解,从而限制解决方案搜索范围。通过与经典 OR 算法和现有学习方法进行比较,结果表明我们的方法可以找到比基准更短的路径。
Apr, 2024
本文利用强化学习和 Transformer 结构设计了用于 Traveling Salesman Problem 的新型算法,相较于以往的算法在 TSP50 和 TSP100 上有了更好的表现
Mar, 2021
本文提出了一种具有信息收集和信念建模能力的随机车辆路径问题的解决方案,该方案可以使用电话来创建有关停电的信仰,并使用实用车辆作为收集其他信息的机制。并使用蒙特卡罗树搜索 (MCTS) 来生成实际策略。实验结果表明,该策略比标准行业启发式方法更快地恢复了电网。
May, 2016
本文研究了旅行商问题的扩展 —— 多旅行商问题(mTSP),并提出了一个双阶段的迭代式启发式算法 ITSHA 来解决带有 minsum 和 minmax 目标的 mTSP 问题。实验结果表明,该算法在多目标下均优于现有启发式算法。
Jan, 2022
本文设计一种神经网络方法,利用图网络方法将旅行商、城市和货站作为三个具有不同基数的集合,通过搜索方法和特定的损失函数来输出最优解,实验结果表明该方法优于现有领域最先进的元启发式算法。
Mar, 2018
该论文提出了一种新颖的自我监督、双层优化学习框架(imperative MTSP),将多旅行商问题(MTSP)通过强制性学习的方式分解为多个单旅行商问题(TSP),并使用控制变量梯度估计算法克服了梯度方差问题,实验证明该方法在大规模问题下比先进的强化学习基线收敛更快,并找到比 Google OR-Tools MTSP 求解器短 80% 的最优旅行路径。
May, 2024
本文研究 Steiner 旅行商问题(STSP)这一问题,探讨了如何将已有的有效的可行性算法适配到适用于稀疏网络,也对与该问题相关的一些领域进行了讨论。
Mar, 2012
该研究介绍了一个新的公式,用于寻找移动目标旅行推销员问题(MT-TSP)的最佳解,通过在空间 - 时间坐标系中寻找凸集图形内的最短路径,相比现有的混合整数锥规划器(MICP)求解器,该公式在运行时间上减少了两个数量级,同时缩小了高达 60% 的最优性差距。
Mar, 2024