May, 2018

时变旅行商问题的割、原始启发和学习分支

PDF
TL;DR本研究探讨了时间依赖旅行商问题（TDTSP），证明了其为 NP-hard 和 APX-hard，并针对该问题提出了两个 IP 公式以及不同的定价算法、割平面和基于 LP 的凸先发方法、传播方法和分支规则。同时，开展了计算实验以评估这些方法的有效性，并首次尝试学习 TDTSP 的强分支决策，但该方法目前并未改善运行时间。
time-dependent traveling salesman problemnp-hardcutting planeslp-based primal heuristicsbranching rule
发现论文，激发创造
  • 提前预计以避免迟到：解决困难约束旅行推销员问题

    使用前瞻信息作为特征，提出一种利用学习方法改善具有时间窗口的 TSP 解决方案合法性的新方法，并构建了具有硬约束条件的 TSPTW 数据集进行准确评估和基准测试。通过对多种数据集进行综合实验，MUSLA 优于现有基线算法且具有一定的泛化能力。

    Mar, 2024

  • 非对称旅行商问题的相变和骨架

    本文研究了 ATSP 中的相变现象，发现随着城市间距离精度的提高，问题的最优解成本和计算成本都会出现急剧的变化。这些结果有助于更好地生成 ATSP 问题实例。

    Jun, 2011

  • 学会使用硬度自适应课程解决旅行商问题

    本文研究了使用自适应难度方法的基于学习的旅行商问题方法，通过定义硬度测量，使用硬度自适应生成器生成不同难度的实例，再利用课程学习器完全利用这些实例来训练 TSP 求解器。实验结果表明，我们的硬度自适应生成器可以生成比现有方法更困难的实例，而我们提出的方法在最优性差距方面显著优于最先进的模型。

    Apr, 2022

  • 旅行商问题的 Transformer 网络

    本文利用强化学习和 Transformer 结构设计了用于 Traveling Salesman Problem 的新型算法，相较于以往的算法在 TSP50 和 TSP100 上有了更好的表现

    Mar, 2021

  • H-TSP：层次化解决大规模旅行推销员问题

    本研究提出了一种基于层次强化学习的端到端学习框架，称为 H-TSP，用于解决大规模 TSP 问题，通过选择子集并使用深度学习模型直接生成解决方案，具有可扩展和高效性。

    Apr, 2023

  • 学习巡回：运算符设计用于解决方案可行性映射的接送旅行推销员问题

    本文旨在开发一种用于一类特殊旅行推销员问题（TSP）的学习方法，即接送 TSP（PDTSP），该方法通过一系列一对一接送节点找到最短路径。我们利用可行解算空间中的操作符来解决 PDTSP，这些操作符将一个可行解映射到另一个可行解，从而限制解决方案搜索范围。通过与经典 OR 算法和现有学习方法进行比较，结果表明我们的方法可以找到比基准更短的路径。

    Apr, 2024

  • 学会解决旅行商问题要重新思考泛化

    本文提出了一种神经组合优化方法，将学习算法与模型架构相结合，以实现在训练过程中看不到的更大规模的问题的推广。通过对零样本推广的原理研究，控制实验提供了第一手数据，并提供了深度学习的新方向。

    Jun, 2020

  • 多旅行商问题的有效迭代二阶段启发式算法

    本文研究了旅行商问题的扩展 —— 多旅行商问题（mTSP），并提出了一个双阶段的迭代式启发式算法 ITSHA 来解决带有 minsum 和 minmax 目标的 mTSP 问题。实验结果表明，该算法在多目标下均优于现有启发式算法。

    Jan, 2022

  • 史塔纳旅行商问题及其相关问题的简约公式化

    本文研究 Steiner 旅行商问题（STSP）这一问题，探讨了如何将已有的有效的可行性算法适配到适用于稀疏网络，也对与该问题相关的一些领域进行了讨论。

    Mar, 2012

  • 第一届 AI4TSP 大赛：学习解决随机路线问题

    介绍 2021 年国际人工智能联合大会（IJCAI-21）上第一个旅行推销员问题（TSP）人工智能竞赛，关注基于学习的算法，介绍了该竞赛的问题、比赛安排、获胜方法和结果概述。竞赛的胜利方法使 AI 在随机路由问题上取得了技术进步，也使路由问题成为 AI 研究人员感兴趣的问题设定。同时，该比赛所使用的路由问题模拟器现已成为开源工具，可以成为其他研究人员使用的新 AI 方法基准测试。

    Jan, 2022