基于end-to-end深度强化学习的多车场车辆路径优化

作者：雷坤; 郭鹏; 王祺欣; 赵文超; 唐连生^*

来源：计算机应用研究, 2022, 39(10): 3013-3019.

DOI：10.19734/j.issn.1001-3695.2022.03.0095

• 多车场车辆路径问题
• 深度强化学习
• 图神经网络
• REINFORCE算法
• Transformer模型

为提高多车场车辆路径问题(multi-depot vehicle routing problem, MDVRP)的求解效率，提出了端到端的深度强化学习框架。首先，将MDVRP建模为马尔可夫决策过程(Markov decision process, MDP),包括对其状态、动作、收益的定义；同时，提出了改进图注意力网络(graph attention network, GAT)作为编码器对MDVRP的图表示进行特征嵌入编码，设计了基于Transformer的解码器；采用改进REINFORCE算法来训练该模型，该模型不受图的大小约束，即其一旦完成训练，就可用于求解任意车场和客户数量的算例问题。最后，通过随机生成的算例和公开的标准算例验证了所提出框架的可行性和有效性，即使在求解客户节点数为100的MDVRP上，经训练的模型平均仅需2 ms即可得到与现有方法相比更具优势的解。

• 单位
  西南交通大学; 宁波工程学院