Apr, 2024

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

PDF
TL;DR本文旨在开发一种用于一类特殊旅行推销员问题（TSP）的学习方法，即接送 TSP（PDTSP），该方法通过一系列一对一接送节点找到最短路径。我们利用可行解算空间中的操作符来解决 PDTSP，这些操作符将一个可行解映射到另一个可行解，从而限制解决方案搜索范围。通过与经典 OR 算法和现有学习方法进行比较，结果表明我们的方法可以找到比基准更短的路径。
pickup-and-delivery tspprecedence constraintsreinforcement learningfeasible solutionrl framework
发现论文，激发创造
  • 提前预计以避免迟到：解决困难约束旅行推销员问题

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

    Mar, 2024

  • 通过深度强化学习学习旅行商问题的 2-opt 启发式算法

    本论文使用基于深度加强学习方法的策略梯度算法，通过 2-opt 操作符学习本地搜索启发式，提出了一种可以轻松扩展到更一般 k-opt 移动的策略神经网络，实验结果表明，所学习的策略比之前的具有最先进性能的深度学习方法更快接近最优解。

    Apr, 2020

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

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

    Mar, 2022

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

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

    Apr, 2023

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

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

    Oct, 2021

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

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

    Apr, 2024

  • 旅行商问题的 Transformer 网络

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

    Mar, 2021

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

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

    Jun, 2020

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

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

    Oct, 2022

  • 面向偏好的末端物流配送规划

    本文提出了一种新的分层路由优化器，该优化器结合了优化和机器学习，通过可学习参数解决了有挑战性的最后一英里物流服务中遇到的困难的实际问题，并使用亚马逊的真实交付数据集证明了这种方法的重要性。

    Mar, 2023