通过深度强化学习学习解决包含时间窗和拒绝的多个 TSP

Sep, 2022

通过深度强化学习学习解决包含时间窗和拒绝的多个 TSP

Learning to Solve Multiple-TSP with Time Window and Rejections via Deep Reinforcement Learning

Rongkai Zhang, Cong Zhang, Zhiguang Cao, Wen Song, Puay Siew Tan...

TL;DR提出一种基于深度强化学习的经理 - 工作人员框架来解决一种复杂但非常重要的旅行商问题的变体（即具有时间窗口和拒绝的多车 TSP），其中不能在截止日期前提供服务的客户可能被拒绝。经过实验结果证明，该框架在解决大型问题时具有高质量的解决方案和更短的计算时间。

Abstract

We propose a manager-worker framework based on deep reinforcement learning to tackle a hard yet nontrivial variant of travelling salesman problem

manager-worker framework deep reinforcement learning travelling salesman problem graph isomorphism network multiple-vehicle

发现论文，激发创造

具有软时间窗口的多车辆路径规划问题：一种多智能体强化学习方法

这篇论文提出了一种基于强化学习的名为 “Multi-Agent Attention Model” 的算法，能够利用较长的离线训练时间快速解决城市物流配送中必不可少的 “多车辆路径问题（MVRPSTW）”，该算法以车辆旅游生成过程为基础，提出了一种具有注意力层的编码器 - 解码器框架来迭代地生成多辆车的路径，通过对不同规模的合成网络进行评估，证明该算法的效果优于谷歌 OR-Tools 和传统方法，并验证了模型的稳健性。

Feb, 2020

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

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

Apr, 2023

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

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

Mar, 2024

强化学习解决带时间窗的随机车辆路径问题

通过强化学习方法优化随机车辆路径问题，减少货物运输中的行程成本，提出一种新的模型，用于考虑不确定的行程成本和需求，以及确定的客户时间窗口，通过基于注意力的神经网络进行训练，实现路径成本的最小化，并超越基于蚁群算法的模型，在行程成本上减少了 1.73%，该模型独特地整合了外部信息，展现了在不同环境中的稳健性，对未来随机车辆路径问题研究和产业应用具有价值。

Feb, 2024

图形指针网络和层次强化学习的组合优化

本研究提出使用强化学习训练的图指针网络（Graph Pointer Networks，GPNs）来解决旅行商问题。我们使用 GPNs 对输入图进行嵌入并通过学习分层策略来优化城市排列。实验结果表明，GPNs 对小规模的 TSP50/100 问题的泛化性能不错，且在 TSP500/1000 问题中获得了更短的旅行路径和更快的计算时间，同时当问题涉及时间窗口约束时，支持最优解的分层强化学习训练优于以往的基准方法。

Nov, 2019

强化学习的神经组合优化

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

Nov, 2016

基于强化学习的无自回归旅行商问题求解器

NAR4TSP 是第一个成功结合强化学习和非循环解码的解决 TSP 问题的算法，通过使用一个特殊设计的图神经网络以非循环的方式生成 TSP 解决方案，实现更快的推理速度，其训练使用了增强型强化学习策略，消除了传统基于监督学习的非循环模型的昂贵标签依赖，实验结果表明 NAR4TSP 在解决质量、推理延迟和泛化能力方面优于四个最先进的模型，此外，我们展示了 NAR4TSP 解码过程和整体路径规划的可行性和有效性的可视化。

Aug, 2023

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

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

Apr, 2024

使用 Lagrangian Relaxation 学习解决软约束车辆路径问题

该研究提出了一种基于强化学习的方法，结合拉格朗日松弛技术和约束策略优化，用于解决软限制的车辆路径规划问题，并在旅行商问题、容量限制车辆路径问题和带时间窗口的容量限制车辆路径问题上进行了验证，表明其对解决已有方法难以解决的问题有很好的竞争力。

Jul, 2022

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

本文旨在开发一种用于一类特殊旅行推销员问题（TSP）的学习方法，即接送 TSP（PDTSP），该方法通过一系列一对一接送节点找到最短路径。我们利用可行解算空间中的操作符来解决 PDTSP，这些操作符将一个可行解映射到另一个可行解，从而限制解决方案搜索范围。通过与经典 OR 算法和现有学习方法进行比较，结果表明我们的方法可以找到比基准更短的路径。

Apr, 2024