Feb, 2022

关于旅行窃贼问题中相互依赖模型的适应性景观

PDF
TL;DR本文主要研究尝试不同形式的 TTP（Travelling Thief Problem）依赖性对于简单局部搜索算法的影响，使用适应性景观分析技术进行分析，旨在探讨复杂实际问题的多个相互关联子问题的依赖性。
travelling thief problemdependencyknapsacklocal search algorithmfitness landscape
发现论文，激发创造
  • 基于协调方法解决旅行窃贼问题

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

    Oct, 2023

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

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

    Apr, 2024

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

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

    May, 2018

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

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

    Nov, 2023

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

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

    Mar, 2018

  • 旅行推销员问题的测试时间增强

    通过测试时间增强（TTA）作为一种有效的技术，我们提出了解决组合优化问题，包括旅行推销员问题。与学习图结构的已提出的具有不变性特性的深度学习模型不同，我们将节点索引的排列解释为一种 TTA 方案。结果表明，我们的方法能够获得比最新模型更短的解决方案。此外，我们展示了找到接近精确解的解决方案的概率随增强尺寸的增加而增加。

    May, 2024

  • 旅行商问题的 Transformer 网络

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

    Mar, 2021

  • 结合强化学习和最优传输的旅行商问题

    利用熵正则化最优传输技术作为深度强化学习网络中的一层，以实现更快速的学习并在端到端训练期间强制执行分配约束和规定，从而对于解决组合优化问题的效率进行优化。

    Mar, 2022

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

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

    Mar, 2012

  • 规划电力传输线巡检的多旅行商问题

    针对一个多路径单仓库场景下的检测车辆，提出了一种最优的输电线检测方法，该方法以旅行商问题为基础，运用了整数线性规划和组合元启发式算法。该方法在电力变电站进行了验证。

    Feb, 2023