Mar, 2024

基于凸集图的移动目标旅行推销员问题的混合整数锥规划

PDF
TL;DR该研究介绍了一个新的公式，用于寻找移动目标旅行推销员问题（MT-TSP）的最佳解，通过在空间 - 时间坐标系中寻找凸集图形内的最短路径，相比现有的混合整数锥规划器（MICP）求解器，该公式在运行时间上减少了两个数量级，同时缩小了高达 60% 的最优性差距。
moving-target traveling salesman problemoptimumformulationconvex setsshortest path
发现论文，激发创造
  • 史塔纳旅行商问题及其相关问题的简约公式化

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

    Mar, 2012

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

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

    Jan, 2022

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

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

    May, 2024

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

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

    Mar, 2024

  • 旅行商问题的高效图卷积网络技术

    本文介绍了一种基于深度学习算法的解决平面欧几里得图中旅行商问题的方法，通过使用图卷积网络构建 TSP 图表示，并通过高度并行化的 Beam Search 非自回归方法输出巡回路径，我们在解决相同节点规模下的问题中比最近提出的自回归深度学习技术表现更好，最终平均优化差距从 50 个节点降低到 0.01％，100 个节点从 2.26％降至 1.39％，尽管相较于标准的运筹学求解器，我们的方法还有所欠缺。

    Jun, 2019

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

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

    Mar, 2018

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

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

    May, 2018

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

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

    Oct, 2022

  • 追逐长期约束的凸函数

    我们研究了一类带有长期约束的在线度量问题，该问题涉及在线玩家在度量空间中进行决策以同时最小化击中成本和度量确定的切换成本。我们设计了特定实例的最优竞争性和学习增强算法，并进一步在数值实验中证明了我们提出的算法的良好性能。

    Feb, 2024

  • 容量覆盖业务员问题的精确算法和启发式算法

    本文介绍了容量限制的覆盖旅行商问题（CCSP），通过容量车辆路径问题中的服务覆盖概念。通过提供车辆可以过渡的位置，其中一些位置有需求的客户，旨在通过一批车辆为客户提供服务，并在车辆行驶的总距离最小化。本文提出了基于整数线性规划（ILP）和偏向随机键遗传算法（BRKGA）元启发式的 CCSP 优化方法。计算实验评估了这些方法在 CCSP 基准实例上与原始界限的性能，并扩展了 ILP 公式以创建多车场覆盖回旋（MDCTVRP）的混合整数线性规划（MILP）。计算实验表明，扩展的 MILP 公式在优化空隙方面优于先前的最优方法，特别是对于一些以前未解决的实例获得了最优解。

    Mar, 2024