摘要
一直以来，50%以上的物流成本源自运输环节，其中短距离的配送任务涉及大量网点且配送环境复杂，是物流优化系统中的核心问题。车辆路径规划作为提供配送方案的关键技术，是物流企业提高客户满意度及降低成本的必要手段，以其作为核心基础衍生出的物流配送系统、智能导航等对企业运作以及人们的生活带来诸多便利。车辆路径优化作为典型的组合优化问题，NP(No-deterministicPolynomial)-hard属性严重阻碍了它在工业界不断深入实用化的进程。已有求解车辆路径规划问题的传统方法包括精确算法和启发式算法：前者的使用受限于小规模问题，后者需要耗费大量时间进行人工试错以发现有用的算法规则，且两者均忽视了数据自身的结构特征。为设计更高效的路径优化算法，本文从深度强化学习的角度出发，对拥有广泛应用场景的四类路径优化问题：单一车辆路径规划问题（theTravelingSalesmanProblem,TSP）、考虑容量约束的车辆路径问题（theCapacitatedVehicleRoutingProblem,CVRP）、需求可拆分的车辆路径问题（theSplitDeliveryVehicleRoutingProblem,SDVRP）以及考虑配送时间的车辆路径问题（theVehicleRoutingProblemwithTimeWindows,VRPTW）等进行分析研究，给出对应的解决方案。 （1）针对TSP问题，本文从序列选择节点和迭代执行2-opt(2-optimization)操作两个角度出发，设计两个不同的图神经网络-注意力模型预测相应的概率分布，进而得到路径最短的节点排列顺序。为预测节点被选择的概率分布，本文提出图卷积神经网络编码器-多头注意力网络解码器。图卷积神经网络从节点的连接边信息中计算不同邻居节点的重要性程度以聚合带权重的节点信息，并将更新后的节点特征同步用于连接边的信息更新，由此为每个节点生成强大的表示向量。考虑到TSP可行解中第一个被选择的节点影响剩余节点的排列情况，本文将前一时刻被选择节点的嵌入向量、首次被选择的节点嵌入向量以及所有节点嵌入经过下采样后所得的向量拼接后，输入注意力网络，计算其与所有节点嵌入向量的相似度，输出节点被选择的概率分布。另外，为预测2-opt动作的概率分布，本文提出融合位置信息的图注意力网络编码器-自注意力网络解码器。图注意力网络直接利用多头注意力机制计算节点间的关联程度，接收节点在当前可行解的动态排序信息以及节点的静态位置信息，输出节点嵌入向量。为了在每个时刻预测2-opt动作概率分布的准确性，本文将所有节点的嵌入向量与下采样后的图嵌入向量融合，输入自注意力网络。实验设计中，对影响模型性能的重要参数进行了灵敏度分析，使用热力图可视化2-opt动作执行过程，并与传统的启发式算法、优化求解器以及经典的基于DRL的方法进行对比，验证了两种算法求解TSP时在求解时间和质量上均占有突出的优势。 （2）针对CVRP问题，本文提出考虑多层级配送网络图信息与掩码注意力网络的序列生成模型。本文首先利用最近邻方法构建稀疏图，并设计带残差模块的图卷积神经网络编码器接收稀疏图信息，通过跳跃连接堆叠的图卷积网络层，以融合不同层级的配送网络图特征。由于所有车辆均需从配送中心出发并返回配送中心，因此本文在注意力网络解码器中单独计算配送中心与其它客户节点的关联度，并实施“掩码”操作禁止配送中心连续两次被选择。动态变化的车辆剩余装载量在配送中心节点被选择后，被重置为初始值，并与上一个被选择节点的嵌入向量和池化操作后的图嵌入拼接，通过多头注意力网络计算其与每个节点嵌入向量的注意力值，最终输出下一个被选择节点的概率分布。本文提出基于精英基准的REINFORCE算法训练模型参数。其中，多个解码器策略能够在单次循环结束，构建多个可行解，选取最优路径的行驶距离评价选择节点的好坏，提高了模型预测的效率。在不同问题规模的数据集上与三种传统启发式算法、优化求解器以及三个经典的DRL算法作对比，验证了本文所提算法的有效性；消融实验结果验证了残差模块和多个解码器策略对提高模型性能所产生的正面效果；在完全不同于训练集问题规模测试集上，本文所提算法表现出优秀的泛化性。 （3）针对SDVRP问题，本文提出两种多节点选择策略预测可行解序列。由于SDVRP中客户需求被每辆车配送的比率介于0和1之间，因此，本文将每个节点经过图卷积神经网络编码器后的嵌入向量与动态变化的客户需求进行融合后，输入注意力网络解码器，计算其与动态环境之间的关系，以求解节点选择策略。在此基础上，提出两种多节点选择的方法：多解码器-单序列和单解码器-多序列。前者的解码器之间无参数共享，单独执行动作；后者使用相同的解码器输出多个可行解序列。同时，本文提出基于平均基准值的REINFORCE算法训练模型，并通过在不同问题规模的测试集及标准SDVRP测试集上对比求解时间和平均行驶距离，发现所提算法中两种多节点选择策略均能在短时间搜寻到更优的可行解。 （4）针对VRPTW问题，本文通过建立动态图注意力网络编码器-门控循环单元解码器学习邻域搜索中的破坏操作，提出基于DRL的大邻域搜索算法。为融合节点在当前可行解中的排序信息，本文根据每个时刻的可行解构建包含虚拟配送中心的网络结构，并输入动态图注意力网络编码器重构所有节点的特征。基于门控循环单元的解码器接收上一时刻被选择移除所有客户节点的嵌入向量以及当前时刻所有的节点嵌入向量，输出核心节点的概率分布以及所有客户节点在当前可行解中相对重要性的概率分布，以进一步确定当前时刻最终被破坏的客户的节点位置。通过分析实验结果，发现本文所提的算法不仅在合成的测试集中具有优越的泛化能力，在经典的Solomon数据集以及京东物流配送任务上也表现出竞争优势。 本文针对四类重要的车辆路径规划问题分别设计了基于图神经网络和强化学习的算法，并通过实验证明了这些算法在求解质量和运行时间上均具有优越性，为深度强化学习下的路径优化算法提供了有益的借鉴思路。
NETL