本研究探讨了时间依赖旅行商问题(TDTSP),证明了其为 NP-hard 和 APX-hard,并针对该问题提出了两个 IP 公式以及不同的定价算法、割平面和基于 LP 的凸先发方法、传播方法和分支规则。同时,开展了计算实验以评估这些方法的有效性,并首次尝试学习 TDTSP 的强分支决策,但该方法目前并未改善运行时间。
May, 2018
本文利用强化学习和 Transformer 结构设计了用于 Traveling Salesman Problem 的新型算法,相较于以往的算法在 TSP50 和 TSP100 上有了更好的表现
Mar, 2021
本文研究 Steiner 旅行商问题(STSP)这一问题,探讨了如何将已有的有效的可行性算法适配到适用于稀疏网络,也对与该问题相关的一些领域进行了讨论。
Mar, 2012
本文提出了一种神经组合优化方法,将学习算法与模型架构相结合,以实现在训练过程中看不到的更大规模的问题的推广。通过对零样本推广的原理研究,控制实验提供了第一手数据,并提供了深度学习的新方向。
Jun, 2020
旅行推销员问题(TSP)是文献中研究充分的 NP 困难问题之一。该论文研究了涵盖从 2,000 到 85,900 个城市的问题,并发现人工组合多个求解器的算法能够在解决 10,000 个城市以上的问题时超越现有的最先进求解器的表现。
Aug, 2023
这篇研究报告讨论了如何解决 NP-Complete 决策问题中的 “相位边界” 问题,介绍了在 K-SAT 中发生的相变的解析解和实验研究。其中,在计算代价随问题规模呈指数级增长的情况下,首次发现了 “随机一阶相变” 的本质,并提出了可能的搜索启发式算法改进方案来应对决策问题中的 “脊骨”。
Oct, 1999
本文设计一种神经网络方法,利用图网络方法将旅行商、城市和货站作为三个具有不同基数的集合,通过搜索方法和特定的损失函数来输出最优解,实验结果表明该方法优于现有领域最先进的元启发式算法。
Mar, 2018
本研究提出了一种基于模仿学习框架的策略来解决旅行商问题,并展示了所训练的图神经网络在大规模的 TSP 实例上的较快求解能力。
Oct, 2022
本文研究了旅行商问题的扩展 —— 多旅行商问题(mTSP),并提出了一个双阶段的迭代式启发式算法 ITSHA 来解决带有 minsum 和 minmax 目标的 mTSP 问题。实验结果表明,该算法在多目标下均优于现有启发式算法。
Jan, 2022
介绍 2021 年国际人工智能联合大会(IJCAI-21)上第一个旅行推销员问题(TSP)人工智能竞赛,关注基于学习的算法,介绍了该竞赛的问题、比赛安排、获胜方法和结果概述。竞赛的胜利方法使 AI 在随机路由问题上取得了技术进步,也使路由问题成为 AI 研究人员感兴趣的问题设定。同时,该比赛所使用的路由问题模拟器现已成为开源工具,可以成为其他研究人员使用的新 AI 方法基准测试。