计算机应用研究

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

单位：1.西南交通大学a.机械工程学院;b.轨道交通运维技术与装备四川省重点实验室,成都610031；2.宁波工程学院经济与管理学院,浙江宁波315211；

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

基金：浙江省高校重大人文社科攻关计划资助项目(2018QN060)；；

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

来源：2022年第10期

《计算机应用研究》期刊编辑部

查看计算机应用研究杂志2022年第10期