VRP-TSP系列论文3 2023-06-22 组合优化 暂无评论 139 次阅读 ---- # Learning to Solve Multiple-TSP with Time Window and Rejections via Deep Reinforcement Learning 《通过深度强化学习学习解决带有时间窗和拒绝的多 TSP》 IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS 期刊 中科院1区 JCR1区  [zcaicaros/manager-worker-mtsptwr: Official implementation of paper "Learning to Solve Multiple-TSP with Time Window and Rejections via Deep Reinforcement Learning" (github.com)](https://github.com/zcaicaros/manager-worker-mtsptwr) ## 问题 mTSPTWR（multiplevehicle TSP with time window and rejections具有时间窗口和拒绝的多车辆 TSP） **TSPTW**：具有时间窗口的TSP问题，节点只能在预定义的时间窗口内访问。 **mTSPTWR**：mTSPTWR 会派遣车队为分散在不同地点的客户提供服务。作为 TSPTW 变体中的一个共同且实用的属性，客户有各自的服务时间窗口。然而，未能在截止日期前得到服务的客户将在 mTSPTWR 中被拒绝。总体目标是最大程度地缩短总旅行时间，同时为尽可能多的客户提供服务。 ## 模型 ### 一些定义   The depot （被视为虚拟客户）容纳 m 辆车辆 :     ### 整体  为了有效地解决 mTSPTWR，我们提出了一种基于 DRL 的 manager-work 框架，该框架将问题分别解耦为上层任务和下层任务，如图 1 所示。对于上层任务，Manager agent 学习划分将客户分成小组，然后将他们分配到不同的车辆。对于较低级别的任务，Work agent 会考虑分配的客户和混合成本来学习为每辆车制定路线。采用较低级别任务的（选定的）输出来训练两个代理，以帮助优化方程式(1)中的目标。 ### 网络 对于Manager agent，我们利用图神经网络（GNN）与自注意力相结合来参数化策略，该策略根据学习的图嵌入对每个车辆进行显式建模，然后将每个客户分配给车辆。 对于Work agent，我们利用类似于[22]的基于自注意力的编码器-解码器模型来参数化策略。 > [22] R. Zhang, A. Prokhorchuk, and J. Dauwels, “Deep reinforcement learning for traveling salesman problem with time windows and rejections,” in 2020 International Joint Conference on Neural Networks, 2020, pp. 1–8. #### 1) The Manager Agent Manager agent分配客户的过程可以表示为一步 MDP + state:  + action: 将客户分配到不同的车辆 + reward:  + policy: 动作的概率分布，从policy中sampling得到action   + 训练  > [16] W. Kool, H. van Hoof, and M. Welling, “Attention, learn to solve routing problems!” in International Conference on Learning Representations, 2019. #### 2) The Worker Agent + 两阶段训练 分配给车辆的客户规模总是不同的，联合训练Manager agent和Work agent将具有很大的挑战性。为了缓解这个问题，我们以两阶段的方式训练它们。在第一阶段，Work agent以自己的成本单独进行培训。在第二阶段，训练好的Work agent是固定的，并采用输出来计算Manager agent学习更好的任务的成本。 + 一旦被Manager agent 代理分解，mTSPTWR 就变成相应车辆的 TSPTWR。 利用类似于[22]的基于自注意力的编码器解码器模型来参数化策略。 > [22] R. Zhang, A. Prokhorchuk, and J. Dauwels, “Deep reinforcement learning for traveling salesman problem with time windows and rejections,” in 2020 International Joint Conference on Neural Networks, 2020, pp. 1–8.  将 Gb 通过基于自注意力的编码器-解码器策略网络 πθ(r|Gb)，生成为 Gb 中的所有客户提供服务的旅行 r（可能不可行）。然后通过回溯过程将 r 映射到 rb （有保证的可行解）[22]。车辆 b 的最终混合成本由 Jb = l(rb) + β·rej(rb) 给出。负混合成本−Jb 用作对工作代理的奖励。 + 训练： REINFORCE with a rollout baseline The final parameter Θ∗ for inference is set to ΘBL  ## 实验 + 数据 随机生成具有不同规模的客户 (n) 和车辆 (m) 的问题实例。 将 n = {50, 100, 150} 视为较小的尺寸来训练和测试我们的方法，并将 n = {200, 300, 400, 500} 视为相对较大的尺寸以评估泛化性能。 对于每个客户规模，我们还分别考虑 m=5 和 10，其中 m=5 被认为更困难，因为可用车辆较少。 + 对比实验 Manager 和 Work agent 都根据计算的概率贪婪地选择各自的动作，没用sampling tabu search (TS)：禁忌搜索 (TS) simulated annealing (SA)： 模拟退火（SA） bees algorithm (BA)： 蜜蜂算法（BA）   + 分配策略的消融实验 我们将Manager agent学习到的分配策略与 K 均值启发式（一种常用于两阶段路由问题 [34] 的聚类方法）和 3 层 MLP 学习到的分配策略进行比较。对于前一个基线，基于空间信息（位置）和时间信息（时间窗口）通过 K-means 将客户划分为 m 个集群，之后将相同的工作代理应用于每个集群。对于后一个基线，我们主要用MLP替换GIN，同时保持整个框架的其余部分不变。  可以看出，尽管 K 均值在某些情况下产生较短的路由长度，但在大多数情况下，其拒绝率和混合成本远低于我们的管理代理和 MLP。这意味着 K 均值无法通过挖掘给定的空间和时间信息来生成所需的集群（这将导致较低的混合成本）。此外，与 MLP 相比，我们基于 GIN 的管理代理可以成功地从这些异构原始特征中学习更有效的分配策略，从而在大多数情况下产生更好的性能。 + 不同惩罚系数（β）的消融实验     (a) The ablation study for different values of β with size (n = 150, m = 5); 还有一些其它的关于多头注意力、the compensation from the manager agent to the worker agent的实验 ## 总结 TSP变体问题 图神经网络，attention， 主要贡献应该在上层划分子问题的分配策略，下层解决子问题的方法是作者的另一篇文章。 强化学习，AM一样的带self-critical rollout baseline的REINFORCE --- # Deep Reinforcement Learning for Solving the Heterogeneous Capacitated Vehicle Routing Problem 《深度强化学习解决异构容量车辆路径问题》 IEEE TRANSACTIONS ON CYBERNETICS, 2021 期刊 中科院1区 JCR1区  ## 问题 heterogeneous CVRP (HCVRP)： 异构CVRP + 同质车队： 车队中的车辆是一样的。因此，他们构建解决方案的关键在于选择下一个访问的节点（客户），而不包括车辆的选择。然而，现实场景中的车辆可能是异构的，具有影响其容量（或行驶速度）的不同特征。 + 本文考虑的异质车队： 车辆主要具有不同的容量特征。我们考虑 HCVRP 的最小-最大和最小-和目标，旨在最大限度地减少车队中车辆的最长或总行驶时间。 ## 模型 在本文中，我们的目标是解决具有最小和和最小-最大目标的 HCVRP，同时强调解决上述问题。我们提出了一种与注意力机制相结合的新型神经架构，以改进基于 DRL 的构造方法，该方法将车辆选择和节点选择的决策结合在一起，以产生更高质量的解决方案。与现有的按顺序为同质车队的每辆车构建路线的工作不同，我们的策略网络能够在每一步自动、灵活地从异构车队中选择车辆。具体来说，我们的策略网络采用 Transformer 式的[25]编码器-解码器结构，其中解码器由两部分组成，分别是车辆选择解码器和节点选择解码器。通过编码器处理问题特征（即客户位置、客户需求和车辆容量）以更好地表示，策略网络首先使用基于所有车辆和部分路线的状态的车辆选择解码器从车队中选择车辆，然后在每个解码步骤使用节点选择解码器为该车辆选择一个节点。重复此过程，直到为所有顾客提供服务为止。 ### State  + Vt: vehicle state  $o_{t}^i$ : 车辆vi在步骤t时的剩余容量。 $T_{t}^i$ : 车辆vi在步骤t时的累计行驶时间。 $G_t^i$ : 表示车辆 vi 在步骤 t 的部分路线，其中 $g^i_j$ 指车辆 vi 在步骤 j 访问的节点。  + St: node state  ### Action 选择要访问的车辆和节点（客户或仓库）。  ### Transition 转换规则 τ 将根据执行的动作将前一个状态 st 转换到下一个状态 st+1  ### Reward MM-HCVRP: 对于MM-HCVRP，为了最小化所有车辆的最大行程时间，奖励被定义为该最大值的负值，其中奖励是通过分别累加每辆车多次行程的行程时间来计算的。  MS-HCVRP: 对于MS-HCVRP，奖励定义为所有车辆总行程时间的负值  ### Policy Network  图 1：我们的Policy Network框架。利用编码器处理的实例的原始特征，我们的策略网络首先使用车辆选择解码器选择车辆(vi_t)，然后使用节点选择解码器选择节点(xj_t)，以便该车辆在每个路线构建步骤访问t。所选车辆和节点都构成该步骤的动作，即 at = (vi_t, xj_t )，其中部分解和状态相应更新。对于单个实例，编码器执行一次，而车辆和节点选择解码器执行多次以构建解决方案。  图 2：我们的Policy Network架构，包含 m 个异构车辆和 n 个客户。值得注意的是，我们的车辆选择解码器利用车辆特征（最后一个节点位置和累积行程时间）、路线特征（m 辆车路线的最大池化）及其组合来计算选择每辆车的概率。 ### Training Algorithm 采用带基线的策略梯度来训练路线构建的车辆选择和节点选择策略。 根据第 15 行中多个实例的paired t-test，如果最新策略网络的参数显着优于前者，则基线网络的参数将被替换。  ## 实验 + 数据 仓库和顾客的坐标是使用均匀分布在单位正方形 [0, 1] × [0, 1] 内随机采样的。客户的需求是从集合{1,2,..,9}中随机选择的离散数（仓库的需求为0）。 为了全面验证性能，我们考虑异构队列的两种设置。第一个车队考虑三辆异构车辆（称为V3），其容量分别设置为20、25和30。第二车队考虑五辆异构车辆（称为V5），其容量分别设置为20、25、30、35和40。 + 对比实验 1) Slack Induction by String Removals (SISR), a state-of-the-art heuristic method for CVRP and its variants; 2) Variable Neighborhood Search (VNS), a efficient heuristic method for solving the consistent VRP 3) Ant Colony Optimization (ACO), an improved version of ant colony system for solving HCVRP with time windows, where we run the solution construction for all ants in parallel to reduce computation time; 4) Firefly Algorithm (FA), an improved version of standard FA method for solving the heterogeneous fixed fleet vehicle routing problem; 5) the state-of-the-art DRL based attention model (AM), learning a policy of node selection to construct a solution for TSP and CVRP.   为了进一步研究我们的 DRL 方法针对 SISR 的效率，我们用有限的时间预算（即 500 秒）评估它们的性能。 可以观察到，随着问题规模的扩大，SISR 需要更长的计算时间才能赶上 DRL 方法。  + 泛化性实验 横坐标指的是要解决的问题，纵坐标指的是不同方法的平均目标值。  ## 总结 VRP变体 transformer, attention based, 自回归 强化学习，policy based , 很像AM用的带self-critical rollout baseline的REINFORCE --- # Continuous Latent Search for Combinatorial Optimization 《组合优化的连续潜在搜索》 Learning Meets Combinatorial Algorithms at NeurIPS2020  ## 总体思想 连续潜在搜索或 CLS 背后的总体思想是将求解离散或混合整数变量 x 上的优化问题转化为最小化连续变量 z ∈ Z ⊆ RL 上的可微代理项 s(z)，其中离散变量可以使用解码器 g(z) 恢复解。另一种思考方式是，我们想要学习一个类似于梯度的解改进算子，而这在离散问题中是不可用的。  ## 方法 原目标： f( x ) x离散 目标代理：$s\theta (z)$ 连续可微  通过$s\theta$ 的梯度下降，优化z:  Loss:  Denoting the problem description as  objective:  feasibility: 可行性约束 latent supervision: 我们可以选择使用有关最佳解决方案（或可以作为目标的另一个好的解决方案）的信息，将其编码到潜在空间中并确保其嵌入的代理值 z* ≈ arg maxz p(x*| z) 小于优化轨迹中的任何其他点。我们将其称为潜在监督，并且通过实验我们发现它对于改进模型的结果非常有用。 ## 网络 代理和decoder都是GNN ## 实验 三个组合问题上评估 CLS：Set Cover, Combinatorial Auction and Maximum Independent Set problems （集合覆盖、组合拍卖和最大独立集合问题） 将 CLS 集成到最先进的开源求解器 SCIP 中 我们可以注意到，CLS 在所考虑的三个数据集中的两个数据集上提供了对最优解的更快收敛，对最大独立集问题具有中性影响。  标签: 组合优化 本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。
评论已关闭