Mar, 2024

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

PDF
TL;DR使用前瞻信息作为特征，提出一种利用学习方法改善具有时间窗口的 TSP 解决方案合法性的新方法，并构建了具有硬约束条件的 TSPTW 数据集进行准确评估和基准测试。通过对多种数据集进行综合实验，MUSLA 优于现有基线算法且具有一定的泛化能力。
constrained traveling salesman problemheuristic algorithmslearning-based methodshard constraintstsptw datasets
发现论文，激发创造
  • 使用 Lagrangian Relaxation 学习解决软约束车辆路径问题

    该研究提出了一种基于强化学习的方法，结合拉格朗日松弛技术和约束策略优化，用于解决软限制的车辆路径规划问题，并在旅行商问题、容量限制车辆路径问题和带时间窗口的容量限制车辆路径问题上进行了验证，表明其对解决已有方法难以解决的问题有很好的竞争力。

    Jul, 2022

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

    本研究探讨了时间依赖旅行商问题（TDTSP），证明了其为 NP-hard 和 APX-hard，并针对该问题提出了两个 IP 公式以及不同的定价算法、割平面和基于 LP 的凸先发方法、传播方法和分支规则。同时，开展了计算实验以评估这些方法的有效性，并首次尝试学习 TDTSP 的强分支决策，但该方法目前并未改善运行时间。

    May, 2018

  • 面向旅行商问题的图神经网络引导局部搜索

    提出了一种基于图神经网络和引导局部搜索的 TSP（旅行商问题）混合数据驱动方法，该方法能够在不损失解决方案质量的同时，快速求解大规模 TSP 实例，经实验证明，我们将 100 个节点问题集的平均最优性差从 1.534% 减少到 0.705%，将 20 个节点实例推广到 100 个节点问题集时，我们将最优性差从 18.845% 减少到 2.622%，提高了 2 倍和 7 倍。

    Oct, 2021

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

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

    Apr, 2024

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

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

    Apr, 2022

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

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

    Oct, 2022

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

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

    Jun, 2020

  • iMTSP: 用命令式学习解决最小 - 最大多旅行商问题

    该论文提出了一种新颖的自我监督、双层优化学习框架（imperative MTSP），将多旅行商问题（MTSP）通过强制性学习的方式分解为多个单旅行商问题（TSP），并使用控制变量梯度估计算法克服了梯度方差问题，实验证明该方法在大规模问题下比先进的强化学习基线收敛更快，并找到比 Google OR-Tools MTSP 求解器短 80% 的最优旅行路径。

    May, 2024

  • 基于强化学习的无自回归旅行商问题求解器

    NAR4TSP 是第一个成功结合强化学习和非循环解码的解决 TSP 问题的算法，通过使用一个特殊设计的图神经网络以非循环的方式生成 TSP 解决方案，实现更快的推理速度，其训练使用了增强型强化学习策略，消除了传统基于监督学习的非循环模型的昂贵标签依赖，实验结果表明 NAR4TSP 在解决质量、推理延迟和泛化能力方面优于四个最先进的模型，此外，我们展示了 NAR4TSP 解码过程和整体路径规划的可行性和有效性的可视化。

    Aug, 2023

  • 通过深度强化学习学习解决包含时间窗和拒绝的多个 TSP

    提出一种基于深度强化学习的经理 - 工作人员框架来解决一种复杂但非常重要的旅行商问题的变体（即具有时间窗口和拒绝的多车 TSP），其中不能在截止日期前提供服务的客户可能被拒绝。经过实验结果证明，该框架在解决大型问题时具有高质量的解决方案和更短的计算时间。

    Sep, 2022