Jan, 2022

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

PDF
TL;DR本文研究了旅行商问题的扩展 —— 多旅行商问题（mTSP），并提出了一个双阶段的迭代式启发式算法 ITSHA 来解决带有 minsum 和 minmax 目标的 mTSP 问题。实验结果表明，该算法在多目标下均优于现有启发式算法。
multiple traveling salesmen problemmtspminsum objectiveminmax objectiveiterated two-stage heuristic algorithm
发现论文，激发创造
  • iMTSP: 用命令式学习解决最小 - 最大多旅行商问题

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

    May, 2024

  • 旅行商问题的并行元启发式求解器集成

    旅行推销员问题（TSP）是文献中研究充分的 NP 困难问题之一。该论文研究了涵盖从 2,000 到 85,900 个城市的问题，并发现人工组合多个求解器的算法能够在解决 10,000 个城市以上的问题时超越现有的最先进求解器的表现。

    Aug, 2023

  • 旅行推销员问题的增强自组织映射解决方案

    本文通过改进的自组织映射方法提供了旅行推销员问题的次优解，并运用超参数调整来确定算法中最关键的特征，所有基准工作的改进都带来了一致的结果，可以激励未来的努力来改进这个算法并将其应用于不同的问题。

    Dec, 2021

  • 使用置换不变汇聚网络学习多个旅行商问题

    本文设计一种神经网络方法，利用图网络方法将旅行商、城市和货站作为三个具有不同基数的集合，通过搜索方法和特定的损失函数来输出最优解，实验结果表明该方法优于现有领域最先进的元启发式算法。

    Mar, 2018

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

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

    Oct, 2022

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

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

    Mar, 2024

  • 针对旅行商问题的强化 Lin-Kernighan-Helsgaun 算法

    本研究提出了 Variable Strategy Reinforced LKH (VSR-LKH) 与 VSR-LKH-3 算法，分别引入了三种强化学习方法与 LKH 算法相结合，以解决 TSP 问题和 TSP 变体（包括 TSPTW 和 CTSP），经 236 个 TSP 基准测试表明，这些算法具有显著的性能优势。

    Jul, 2022

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

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

    Mar, 2012

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

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

    Apr, 2023

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

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

    May, 2018