Oct, 2023

基于协调方法解决旅行窃贼问题

PDF
TL;DR本研究提出了一种基于协调的解决方案以提高旅行窃贼问题（TTP）求解器的性能，并通过利用循环路径在物品选择时进行协调。我们还建议一种基于机器学习的协调启发式算法，通过捕捉两种人类设计协调启发式算法的特征来进一步提高性能。最终，我们的求解器名为 Cooperation Coordination（CoCo）并且其源代码可从给定的 URL 进行访问。
发现论文，激发创造
  • 关于旅行窃贼问题中相互依赖模型的适应性景观

    本文主要研究尝试不同形式的 TTP（Travelling Thief Problem）依赖性对于简单局部搜索算法的影响，使用适应性景观分析技术进行分析，旨在探讨复杂实际问题的多个相互关联子问题的依赖性。

    Feb, 2022

  • 深度强化学习与旅行购买问题

    基于深度强化学习的旅行购货问题（TPP）解决方案，通过使用双向图表示 TPP、策略网络逐步构建路线，并通过线性规划获取购货计划，利用元学习策略稳定训练策略网络。在综合合成和标准基准测试上，相较于已有启发式算法，我们的 DRL 方法能够显著提升解决方案质量（降低 40%-90% 的最优性差距），尤其在大型实例上具备高效性。

    Apr, 2024

  • 蒙特卡洛树搜索和监督学习相结合的综合框架用于列车时刻表问题

    这篇文章提出了一种综合的蒙特卡洛树搜索（MCTS）计算框架，通过结合启发式方法、无监督学习方法和监督学习方法来解决离散动作空间中的单轨铁路列车时刻表问题（TTP）。

    Nov, 2023

  • 提前预计以避免迟到：解决困难约束旅行推销员问题

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

    Mar, 2024

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

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

    Apr, 2024

  • 旅行商问题的 Transformer 网络

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

    Mar, 2021

  • 同行之路：一种新的 TSP 求解策略

    本研究提出了一种基于模仿学习框架的策略来解决旅行商问题，并展示了所训练的图神经网络在大规模的 TSP 实例上的较快求解能力。

    Oct, 2022

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

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

    Jan, 2022

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

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

    Jan, 2022

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

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

    Jun, 2011