Jun, 2023

以公平性背景为顺序生成求解 NP-hard 最小最大路由问题

PDF
TL;DR本文提出了一种基于深度学习的新框架 Equity-Transformer 来解决大规模 min-max routing 问题，并在 min-max mTSP 和 min-max mPDP 的两个代表性 routing 任务中展示了其优异性能。
发现论文，激发创造
  • DPN: 分离划分和导航的神经求解器：最大最小车辆路径问题

    通过提出了一个新颖的注意力机制启发式学习的编码器，以及一种有效的分解 - 分区 - 导航（Decoupling-Partition-Navigation）方法，本论文显著超越了现有的学习方法在单车库和多车库的最小 - 最大车辆路径规划问题中。

    May, 2024

  • 在多个分辨率下解决路由问题的保持对称性的图注意力网络

    通过多分辨率和对称性保持，我们提出了一种新的数据驱动方法来解决旅行推销员问题和车辆路径问题。实验证明，我们的模型超过了现有的基准线，并证明了对称性保持和多分辨率对于解决组合问题的重要性。

    Oct, 2023

  • 学习协作策略以解决 NP-hard 路径规划问题

    本论文提出了一种新的层次化问题求解策略，称为学习协作策略，它使用两个迭代的深度强化学习策略：播种机和修订机，旨在有效地找到近似最优解，扩展了深度强化学习框架在解决 NP-hard 路由问题方面的应用。

    Oct, 2021

  • 使用 Transformer 解决团队定向问题

    通过基于集中式 Transformer 神经网络的多智能体路径规划系统，能够以非常快速且准确的方式解决团队定向问题，并在计算速度方面超过大多数现有技术。

    Nov, 2023

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

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

    May, 2024

  • 深度策略动态规划在车辆路径问题中的应用

    Deep Policy Dynamic Programming 优先和限制来自深度神经网络的策略，以结合学习嵌入式启发式和动态规划 (DP) 算法的优点，以优化旅行商问题 (TSP)、车辆路径问题 (VRP) 和带时间窗口的 TSP (TSPTW) 的性能，同时胜过大多数其他解决 TSPs、VRPs 和 TSPTWs 的 ' 神经方法 '。

    Feb, 2021

  • 线性时间内学习在实际图中求解组合优化问题

    本文介绍一种使用强化学习训练图神经网络求解单人游戏定义的图组合优化问题的新框架，可以处理最小生成树、最短路径、旅行商问题和车辆路径问题等一系列问题，该方法可在线性运行时间内输出近似解，并且能够推广到多种情况，包括 NP 困难的问题和真实世界的图。

    Jun, 2020

  • 旅行商问题的 Transformer 网络

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

    Mar, 2021

  • 基于图注意力的深度强化学习求解依赖于负载成本的中国邮递员问题

    该研究论文提出了一个基于深度强化学习的新框架（Arc-DRL），用于解决复杂的有负载约束的弧路由问题（CPP-LC），并通过与元启发式方法的比较实验证明了该框架在解决 CPP-LC 方面的优越性。

    Oct, 2023

  • 强化学习的神经组合优化

    本文提出了一种利用神经网络和强化学习解决组合优化问题的框架，特别关注旅行推销员问题和背包问题，证明了该方法在不需要太多工程和启发式设计的情况下在二维欧几里得图上取得接近最优结果，并且可以得到具有多达 200 个项目实例的最优解。

    Nov, 2016