[论文分享] ICML 2024 MVMoE: 基于混合专家模型的多任务车辆路径规划求解器

1. Abstract

学习求解车辆路径问题(VRP)已经引起了人们的广泛关注。然而，大多数神经解算器仅针对特定问题进行结构化和独立训练，这使得它们不那么通用和实用。在本文中，目标是开发一个统一的神经求解器，可以同时处理一系列VRP变量。具体来说，作者提出了一种混合专家()的多任务车辆路径求解器，它在不增加计算量的情况下大大提高了模型的容量。作者进一步为设计了一种分层门控机制，在经验性能和计算复杂性之间提供了良好的权衡。在实验中，作者的方法显著提高了10个未见过的VRP变量的零样本泛化性能，并在少数射击设置和现实世界的基准测试实例上展示了不错的结果。作者进一步对MoE配置在求解VRP中的作用进行了广泛的研究，并观察到分层门控在面对分布外数据时的优越性。

2. Introduction

2.1 简介

固有的NP-hard性质使得VRP的精确求解代价呈指数级增长。作为替代方案，启发式求解器在合理的时间内提供次优解决方案，但需要为每个问题设计大量的领域专业知识。最近，学习解决VRP受到了很多关注，正在开发有成效的神经求解器。其中大多数应用深度神经网络通过各种训练范式(例如强化学习(RL))来学习解决方案构建策略。除了获得良好的性能外，它们比传统求解器需要的计算开销和领域专业知识更少。然而，主流的神经解算器仍然需要针对每个特定的VRP进行定制和独立训练的网络结构，这导致了高昂的训练开销，并且在面对多个VRP任务时实用性较低。

受到大型语言模型(LLM)最新进展的启发，作者提出了基于混合专家模型的多任务VRP求解器。通常，混合专家模型用一些“专家”层代替基于Transformer模型中的前馈网络(FFN)，对MoE层的输入通过门控网络路由到特定的专家只有选定的专家的参数才会被激活。这样，部分激活的参数可以在不增加计算量的情况下有效地增强模型容量。因此，为了实现更通用、更强大的神经求解器，作者首先提出了一种基于MoE的神经VRP求解器，并提出了一种分层门控机制，在经验性能和计算复杂度之间进行了良好的权衡。

2.2 近年神经VRP求解器介绍

在学习解决VRP的文献中存在两种主流方法：(1) 基于构造的求解器，它学习策略以端到端方式构建解决方案。(2) 基于改进的求解器，它学习策略，迭代地改进初始解，直到满足终止条件。策略通常是在经典的局部搜索环境中训练的或专门的启发式求解器，用于获得更高效或更有效的搜索组件。最近的研究揭示了神经求解器泛化能力的不足，它在训练时未见的数据上性能会严重下降。以往的研究主要集中在单个问题上的跨尺度泛化或交叉分布泛化或两者兼而有之，在本文中，作者进一步探讨了不同VRP变体之间的泛化。

2.3 混合专家模型

MoEs的最初想法是在30年前提出的。在早期的概念中，专家被定义为一个完整的神经网络，因此MoEs类似于神经网络的集合。作为MoEs在大型神经网络中应用的早期成功案例，Shazeer等人(2017)在语言建模和机器翻译中引入了稀疏门选MoEs，在计算效率上只有很小的损失的情况下获得了当时最先进的结果，后续工作主要集中于改进门控机制或将MoEs应用于其他领域。

2.4 本文主要贡献

(1) 作者提出了一种统一的神经求解器来求解多个VRP任务，首次将MoE引入到组合优化问题的研究中。单独的可以在不同的VRP变体上进行训练，并在未见过的VRP上提供强大的零样本泛化能力。

(2) 为了在经验性能和计算开销之间取得良好的平衡，作者设计了的分层门控机制。令人惊讶的是，它表现出比基门控更强的分布外泛化能力。

(3) 大量的实验表明，在10个未见过的VRP变量上显著提高了对基线的零样本泛化性能，并且在少样本设置的情况下和现实世界实例上取得了不错的结果。作者进一步对MoE配置(如MoE位置、专家数量和门控机制)对零样本泛化性能的影响进行了广泛的研究。

3. Preliminaries

3.1 CVRP变体以附加约束为特征

CVRP的定义此处不过多赘述，问题的目标是寻找代价最小的最优路径：，其中为包含所有可行路径的离散搜索空间。在CVRP的基础上，几个VRP变体涉及额外的约束：(1) Open Route(O)：车辆访问客户之后不需要返回停车场；(2)Backhaul(B)：在CVRP中，需求为正，表示车辆在客户节点卸载货物。在实践中，客户可以有一个负需求，要求车辆装载货物，将的客户节点命名为linehauls， 的客户节点命名为backhauls。因此，带回程的VRP允许车辆以混合方式穿越线路和回程，没有严格的优先级；(3) Duration Limit (L)：为了保持合理的工作量，每条路由的开销(即长度)都有一个预定义的阈值上限；(4) Time Window (TW)：每个节点与一个时间窗口和一个服务时间相关联。车辆必须在从到的时间段开始为客户服务。如果车辆早于到达，则必须等到。所有车辆必须不迟于返回仓库。上述约束条件如下图所示。组合这些属性，可以得到16种VRP变体。

3.2 使用强化学习方法训练求解器

本文考虑强化学习训练范式，其中解构建过程被表述为马尔可夫决策过程(MDP)。给定一个输入实例，编码器处理它并获得所有节点嵌入，这些节点嵌入与构造的部分路径的上下文一起表示当前状态，解码器将它们作为输入，并输出要选择的有效节点(即动作)的概率。构造完整的解后，可通过链式法则分解其概率，奖励定义为路径长度的负值，即。给定训练稳定性的基线函数，通常使用reinforcement算法来训练策略网络，它应用预期奖励的估计梯度来优化策略：

4. Methodology

4.1 基于MoEs的多任务VRP求解器

多任务VRP求解器：在不失去一般性的情况下，目标是学习基于构造的神经求解器，来解决在五个约束条件下的VRP变体。结构如下图所示：

给定特定VRP变体实例，每个节点的静态特征用表示，其中分别表示节点的坐标、客户需求、开始时间和结束时间。编码器将这些静态节点特征作为输入，输出d维节点嵌入。在第n步解码时，解码器以节点嵌入和上下文表示作为输入，包括最后选择节点的嵌入和动态特征，其中分别表示车辆的剩余容量、当前时间、当前部分路线的长度和是否为开放路径的指示。然后，解码器输出节点的概率分布，从中选择一个有效节点并添加到目前的解中，通过迭代解码过程，以自回归的方式构造完整的解。如果当前选择的VRP变体中只涉及静态或动态特征的子集，则将其他特征填充为默认值(0)。

综上所述，考虑到不同的VRP变体可能包含一些共同的属性(如坐标、需求)，作者将静态和动态特征定义为存在于所有VRP变体中的属性的联合集。通过对具有这些属性的几个VRP变体进行训练，策略网络有可能解决看不见的变体，这些变体的特征是这些属性的不同组合。

混合专家模型：通常，一个MoE层由两部分组成：(1) m个专家，每个专家都是一个具有独立可训练参数的线性层或FFN；(2) 一个由参数化的门控网络，它决定了输入如何分配给专家。给定单个输入,和分别表示门控网络的输出(即m维向量)和第j位专家的输出。因此，一个MoE层的输出计算为：

稀疏向量只激活具有部分模型参数的一小部分专家，从而节省了计算量。通常，TopK算子可以通过只保留k个最大的值而将其他值设置为负无穷来实现这样的稀疏性。在这种情况下，门控网络将输出计算为。考虑到更大的稀疏模型并不总是带来更好的性能，设计有效和高效的门控机制使得每个得到充分训练的专家得到足够的训练数据是至关重要的且棘手的。

：通过对以上部分的综合，可以得到带有MoEs的多任务VRP求解器。其中在编码器和解码器中都使用了MoE。具体来说，作者用MoE代替了编码器中的FFN层，用MoE代替解码器中的多头注意最后的线性层。作者的经验发现，作者的设计在生成高质量的解决方案方面是有效的，特别是在解码器中使用MoE往往会对性能产生更大的影响。同时优化所有可训练参数，目标公式为:

其中，表示VRP求解器的原始损失函数(例如，用于训练求解VRP变量的策略的强化损失)，表示与MoEs相关的损失函数，是控制其强度的超参数。

4.2 门控机制

本文主要考虑节点级门控，通过该门控，每个节点独立地路由到专家。在每一个MoE层，额外的计算来自于门控网络的前向传递和节点分配给选定的专家。虽然在解码器中使用MoE可以显着提高性能，但随着问题大小n的扩大，解码步骤的数量T也会增加。这表明，与门步数固定的编码器相比，在解码器中应用MoE可能会大大增加计算复杂度。鉴于此，本文提出了一种分层门控机制，以更好地利用解码器中的MoE，从而在经验性能和计算复杂性之间获得良好的权衡。

节点级门控：节点级门控按节点粒度对输入进行路由，表示节点嵌入向量的维度，表示中门控网络的可训练参数，给定一batch的输入，其中I为节点总数，每个节点根据门控网络预测的评分矩阵路由到选定的专家。在下图中举例说明了得分矩阵，其中表示第i个节点，表示节点级门控中的第j个专家。

在本文中，主要考虑两种流行的门控算法(1) 输入选择门控：每个节点根据H选择Top-k专家。通常，将K设置为1或2以保持合理的计算复杂度。输入选择门控如上图左侧所示，其中每个节点被路由到两个得分最高的专家(即Top2)。但是，这种方法不能保证负载均衡。某个专家可能会收到比其他专家更多的节点，导致一个专家占主导地位，而让其他专家欠拟合。为了解决这个问题，大多数工作使用辅助损失来平衡在训练期间发送给不同专家的节点数量。(2) 专家选择门控：每个专家基于H选择Top-k的节点。通常，K设置为。专家选择门控如上图右侧所示，在给定的情况下，每个专家选择两个得分最高的节点。虽然这种门控算法显式地确保了负载平衡，但有些节点可能没有任何专家选择。

分级门控：在VRP中，在每个解码步骤中都使用MoE的计算成本很高，因为(1) 解码步骤的数量T随着问题大小n的增加而增加；(2) 解码过程中必须满足特定于问题的可行性约束。因此，本文提出了一种分层门控，在解码过程中学习有效地利用MoE。

上图为分级门控的示意图，分级门控MoE层包括两个门控网络、m个专家和密集层D(例如，线性层)。给定输入，分级门控将分为两个阶段处理。在第一阶段，根据问题级表示决定将输入分配到稀疏层还是密集层。具体来说，沿着的第一维应用均值池化得到，并对其进行处理得到得分矩阵。然后，通过从概率分布中采样，将输入路由到稀疏或密集层。在第二阶段，如果被路由到稀疏层，则激活门控网络，使用前面提到的门控算法(例如输入选择门控)将节点路由到节点级的专家。否则，将路由到密集层D，并变换为。综上所述，分级门控学习输出或。总体而言，分层门控提高了计算效率，但对经验性能的影响较小。为了平衡的效率和性能，本文在编码器中使用基本门控，在解码器中使用分级门控。

5. 实验及结论

Baseline：(1) 传统求解器：HGS(CVRP、VRPTW)、LKH3(CVRP、OVRP、VRPL、VRPTW)、OR-Tools(所有16种实例)；(2) 神经求解器：将本文的方法与POMO和POMO- mtl 进行了比较。POMO是在单个VRP上进行训练，而POMO- mtl是通过多任务学习在多个VRP上进行训练。

5.1 实验结果

在训练的问题上评估：在6个经过训练的VRP问题上评估了所有方法，如下表所示。单任务神经解算器(即POMO)在每个单个问题上都比多任务神经解算器获得更好的性能，因为它是在每个VRP上独立重构和重新训练的。然而，它在所有训练过的VRP中的平均性能相当差，因为每个训练过的POMO都过拟合到特定的VRP。值得注意的是，我们的神经求解器一直优于POMO-MTL。MVMoE/4E性能略好于MVMoE/4E- l，但代价是更多的计算。尽管如此，MVMoE/4E- l表现出比MVMoE/4E更强的分布外泛化能力。

在未见的变体上进行评估：在10个未见的VRP变体上评估多任务求解器。(1) Zero-shot泛化：直接在未见过的VRP上测试训练好的求解器。下图结果显示，所提出的在所有VRP变体中都明显优于POMO-MTL。

(2) Few-shot泛化：作者还考虑n = 50的Few-shot设置，其中训练好的求解器在每个epoch使用10K个实例(总训练实例的0.01%)对目标VRP进行微调。在不失去一般性的前提下，我们在训练设置之后对VRPBLTW和OVRPBLTW进行了实验。下图的结果显示比POMO-MTL的泛化效果更好。

5.2 对MoE的消融实验

本节探讨了不同MoE设置对神经求解器零样本泛化的影响，并为如何有效地应用MoE求解VRP提供了一些见解。由于快速收敛，将大小为n = 50的VRP上的epoch数量减少到2500，同时保持其他设置不变。我们将MVMoE/4E设置为默认基线。

MoE的位置：作者考虑了在神经求解器中应用MoE的三个位置：(1) 原始特征处理(Raw)：将原始特征投影到初始嵌入中的线性层被MoE取代。(2) 编码器(Enc)：将编码器层中的FFN替换为MoE。此外，进一步尝试在所有编码器层中使用MoE。(3) 解码器(Dec)：多头注意力的最后一层线性被解码器中的MoE所取代。在上图中显示了10个未见过的vrp的平均性能。结果表明，在浅层(如Raw)应用MoE可能会使模型性能恶化，而在所有编码器层(Enc_All)或解码器层(Dec)使用MOE则有利于零样本泛化。

专家的数量：将每个MoE层的专家人数增加到8和16，并将推导的MVMoE/8E/16E模型与MVMoE/4E模型进行比较。首先使用相同数量(50M)的实例来训练所有模型。之后，我们还使用更多的数据和计算来训练MVMoE/8E/16E，以探索基于缩放定律的潜在更好结果。具体来说，通过使用更大的批大小为MVMoE/8E/16E提供更多的数据，这些数据与专家的数量呈线性增长。上图的结果表明，拥有更多训练数据的专家数量的增加进一步激发了的力量，说明了MoE在解决VRP方面的有效性。

门控机制：本文研究了不同的门控级别和算法的效果，包括三个级别(即节点级，实例级和问题级)和三种算法(即输入选择，专家选择和随机门控)。如上图所示，节点级输入选择门控表现最好，而节点级专家选择门控表现最差。有趣的是，我们观察到解码器中的专家选择门控使得难以优化。这可能表明每种门控算法都有其最适合服务于MoE的位置。

6. 总结及未来工作

本文针对更通用、功能更强大的VRP求解器，提出了一种具有MoE的多任务车辆路径求解器()，该算法可以同时求解多个VRP，甚至可以以零样本方式求解。我们对如何将MoEs应用于神经VRP求解器提供了见解，并提出了一种有效的分级门控机制。从经验上看，在Zero-shot、Few-shot设置和真实基准测试上表现出了较强的泛化能力。尽管本文首次尝试了大型VRP模型，但参数的尺度仍然远远小于LLM。还存在以下问题(1) 在解决大规模VRP时开发可扩展的基于MoE的模型，(2) 对不同问题的通用表示的挑战，(3) 探索门控机制的可解释性。