VRP求解哪家强？深度强化学习来挑战！

● 前言

大家作为我们公众号的忠实粉丝，想必对VRP不陌生吧。VRP问题作为运筹学领域的重要问题之一，不断有学者提出新的算法来求解这一问题，包括列生成、分支定价等精确算法，以及模拟退火、禁忌搜索等启发式算法。

深度学习是这两年大火的技术，在CV（计算机视觉）和NLP（自然语言处理）等领域获得了重大突破。特别是Attention机制的出现，使得NLP的发展取得了重大突破。

Attention机制模仿了生物观察行为的内部过程，即一种将内部经验和外部感觉对齐从而增加部分区域的观察精细度的机制。例如人的视觉在处理一张图片时，会通过快速扫描全局图像，获得需要重点关注的目标区域，也就是注意力焦点。然后对这一区域投入更多的注意力资源，以获得更多所需要关注的目标的细节信息，并抑制其它无用信息。

VRP的本质就是序列决策问题，这意味着深度学习技术在VRP上也可能有所突破。使用完全端到端求解的深度强化学习方法可直接将问题的已知条件输入训练好的深度神经网络快速得到输出的序列决策，该神经网络使用强化学习算法向着总路径长度最小化的方向训练。

实际上，已经有不少学者将深度强化学习方法应用在了VRP上，并写成了论文（直接Google论文名称就可以找到这些论文）：

这些论文中的深度强化学习均使用了基于Encoder-Decoder的框架（目前大部分Attention模型都依附在Encoder-Decoder框架下，有关这一框架大家可以自行了解哦）。将问题已知条件通过各种形式输入到Encoder中并将Decoder的每一步输出状态通过与Encoder做Attention从而指向Encoder中的某一点形成指针网络用于端到端求解的序列决策。

下面以论文"Attention, learn to solve routing problems"为例子讲解这种完全端到端的求解方法。这篇论文是上面5篇论文中效果最好的。

● 模型介绍

VRP的目标是找到总成本最小的一组路径，每条路径中车辆从指定的仓库出发并最终回到 仓库，路径上的总需求不能超过车辆的承载能力。求解VRP的算法可分为精确算法和启发式算法。精确算法提供了最优的保证解，但由于计算复杂度高，无法处理大规模算例，而启发式算法往往速度快，但由于没有精确理论保证往往只能得到次优解。考虑到最优性和计算代价之间的权衡，启发式算法可以在大规模算例可接受的运行时间内找到次优解。然而，设计性能良好的启发式算法并不容易。

设计启发式算法是一个繁琐的过程。我们可以使用深度强化学习的方法来设计完全端到端的神经网络，在不需要人工干预的情况下自动地学习到隐含的启发式信息，尽可能地达到与启发式算法相近的效果。

对于本文求解的最经典的带容量限制的车辆路径规划问题(CVRP)，一辆有特定容量限制的车辆负责从仓库节点出发，需要将货物运送到多个客户节点，当车辆容量不足以满足任何客户点的需求时，必须返回仓库将货物装满。该问题的解决方案可以看作一组路径序列，每个路径序列的起点和终点都在车站，中间经过的都是客户节点。

VRP可以看作是一个连续的决策问题，可将编码器-解码器(Encoder-Decoder)架构作为解决这类问题的有效框架。以神经机器翻译(NMT)为例，编码器从源语言文本中提取句法结构和语义信息，然后解码器根据编码器给出的特征构造目标语言文本。由于求解VRP的输入输出均为特定内容的序列，所以编码器-解码器架构也可以用来求解VRP。首先利用编码器提取输入实例的特征，然后经过一系列的处理，最后用解码器迭代地构造解，在每个解序列的构建过程中，解码器预测选择每个节点的概率分布，然后选择一个节点将其放到当前已生成序列的末尾。因此，对每个输入实例X和模型的所有参数θ 该方法生成的解序列概率可由链式法则分解为如下:

本篇推文的Encoder-Decoder框架借鉴了论文"Attention is all you need，31st Conference on Neural Information Processing Systems (NIPS 2017), Long Beach, CA, USA" 中提出的transformer模型，引入一个上下文向量来表示解码上下文，使用具有带确定性贪心基准值(greedy rollout baseline)的深度强化学习算法对模型进行训练。该模型将一个算例视为一个图，并提取节点特征来表示这样一个复杂的图结构，该结构捕获节点在其图邻居上下文中的属性，并根据这些节点特性逐步构造解。

● 编码器 Encoder

编码器(Encoder)部分的架构如下图所示，图中以输入四个点(n=4)为例，编码器产生所有输入节点的嵌入信息，这与transformer模型非常类似，其中使用了N个transformer模型中的注意力层，每个注意力层包含两个子层：多头注意力层(Multi-Head Attention layer, MHA)和全连接前馈层(fully connected Feed-Forward layer, FF)，每个子层都使用了残差连接(Skip connection)和批归一化(Batch Normalization, BN)。

编码器(Encoder)架构

每个注意力层的计算过程如下式：

其中h_i分别由x_i经过全连接将维度扩展为后续计算的embedding_size得到，l表示所在的注意力层数，MHA表示节点i与所有节点进行多头注意力计算，过程如下：

由于输入的节点之间没有序列信息，故该架构去除了transformer模型中的位置序列编码部分。该编码器最后将所有节点的嵌入信息取平均得到整个图的嵌入信息，如下式：

● 解码器 Decoder

解码器的架构及其解码过程如下图所示，图中依然以四个点为例。解码是按顺序进行的，在第t步时，解码器根据编码器的图嵌入以及t’(t’< t)时刻产生的输出信息从而输出选择各个节点的概率。解码器计算编码器上的一个注意(子)层，但是为了提高计算效率，与编码器中每个节点都与其他所有节点进行信息交互不同的是，每一步解码只将编码器中计算得到的各节点嵌入信息发送到综合当前已有信息的Context node embedding中。

解码器(Decoder)架构及其解码过程

在解码器的每一步解码中，为得到综合当前已有信息的Context node embedding，首先将从编码器得到的图嵌入信息与每一步解码需要增加的信息嵌入(对于TSP的求解，增加的信息为起点和当前点的embedding；对于VRP的求解，增加的信息为当前点的embedding和车辆的剩余容量)做连接(即图中左上角的Concatenation部分，上图是该论文求解TSP为例的decoder模型图，如果求解VRP那么将Concatenation部分的后两位改成当前点的embedding和车辆的剩余容量即可)，如下式所示

然后将结果与编码器中得到的所有节点通过一个多头注意力层(Multi-Head Attention layer, MHA)进行注意力计算后得到Context node embedding，如下式所示

最后，将 Context node embedding 再与编码器中得到的所有节点进行注意力匹配后得到其与每个节点的匹配度，通过softmax函数对这些匹配度归一化后得到最后的选择每个节点的概率，这最后的概率是使用单头注意力机制计算的。解码的每一步中不允许在下一步中访问的点的选取概率会被置为0，即将其通过掩蔽过程(mask)去掉。

● 基于策略梯度的深度强化学习算法

在"Attention, learn to solve routing problems"这篇论文中，该基于transformer模型的Encoder-Decoder架构的方法提出使用一种带确定性贪心基准值(greedy rollout baseline)的深度强化学习算法对模型进行训练，给定一些算例，训练的目标是最小化路径的总长度，将解码的每一步选择节点视为马尔可夫决策过程，不断地最小化策略梯度，该训练算法的伪码如下Algorithm 1。

算法中SampleRollout表示对该模型使用按节点选择的概率采样的策略得到解的神经网络；GreedyRollout表示对该模型使用取最大选择概率的节点的策略得到解的神经网络；OneSidedPairedTTest表示对当前SampleRollout和GreedyRollout的解做单侧配对t检验(α=5%)，如果当前SampleRollout的解效果在该t检验中要显著好于GreedyRollout的解效果，那么就将GreedyRollout的网络参数更新为当前SampleRollout的网络参数。

● 实验结果

将本篇论文的方法(Attention Model)应用于求解带容量限制的车辆路径规划问题(CVRP)，并将其与其他求解CVRP的方法进行效果对比，实验结果如表所示。

该实验将所有点的欧式空间坐标都归一化到区间(0,1)之间，表中的n表示样例中节点的总数目(分别对20、50个节点的情况做了对比实验)，mean_dis表示得到解的平均路径总长度，Gap表示其与最优解的差距百分比，Time表示生成解的平均时间。

表中的Gurobi和LKH3是目前求解路径规划问题的公认较好的最优解和次优解的求解器，RL是论文"Reinforcement learning for solving the vehicle routing problem"中提出的改进指针网络的方法，OR Tools是论文"Neural combinatorial optimization with reinforcement learning"的实验中用到求解工具。

本次实验使用的设备是一块GPU 2080Ti，代码实现基于Pytorch框架,表中最后两行为小编实现论文方法求解CVRP的实验结果，Mean_dis和Gap的对比结果与原文基本一致，生成10000个解的时间Time结果因具体设备、具体代码实现、并发数据量等的不同而存在差异。

● 结论

从论文原文和实验结果均可以看出，这种完全端到端求解的深度强化学习方法相比LKH3启发式搜索方法最大的优势在于端到端神经网络的求解速度快(尤其在使用greedy策略时)；而相比同类型的完全端到端深度强化学习方法，本文使用的基于transformer的多头Attention模型具有更好地传递VRP中节点与节点之间信息的作用，它相比非多头注意力的embedding结合LSTM的RL模型具有提升求解质量的效果。

● 代码

为了方便大家后续自己测试，将论文作者的源码和小编实现的代码贴在下面。

论文原作者给出的源码：

https://github.com/wouterkool/attention-learn-to-route

实现论文方法求解CVRP的源码：

https://github.com/echofist/AM-VRP

- END -