分类: 计算机科学 >> 计算机科学的集成理论 提交时间: 2022-05-18 合作期刊: 《计算机应用研究》
摘要: 为提高多车场车辆路径问题(Multi-Depot Vehicle Routing Problem,MDVRP)的求解效率,提出了端到端的深度强化学习框架。首先,将MDVRP建模为马尔可夫决策过程(Markov Decision Process,MDP),包括对其状态、动作、收益的定义。同时,提出了改进图注意力网络(Graph Attention Network,GAT)作为编码器对MDVRP的图表示进行特征嵌入编码,设计了基于Transformer的解码器。并采用改进REINFORCE算法来训练该模型。该模型不受图的大小约束,即其一旦完成训练,就可用于求解任意车场和客户数量的算例问题。最后,通过随机生成的算例和公开的标准算例验证了所提出框架的可行性和有效性。即使在求解客户节点数为100的MDVRP上,经训练的模型平均仅需2毫秒即可得到与现有方法相比更具优势的解。