一种求解CVRP的动态图转换模型  

A dynamic graph transformer model for solving CVRP

作　　者：王扬 陈智斌[1] WANG Yang;CHEN Zhi-bin(Faculty of Science,Kunming University of Science and Technology,Kunming 650000,China)

机构地区：[1]昆明理工大学理学院,云南昆明650000

出　　处：《计算机工程与科学》2023年第5期859-868,共10页Computer Engineering & Science

基　　金：国家自然科学基金(11761042)。

摘　　要：带容量的车辆路径问题是组合最优化问题中的经典问题,多年以来一直被反复研究。最近,Transformer已经成为解决车辆路径问题的主流深度学习架构。然而,由于一个实例在模型不同构造步骤中会发生改变,相应的节点特征也需要更新,传统位置编码方法不适用于提取动态优化问题的位置信息。因此,现有方法在提高学习效率方面效果较差。以最小化路径长度为目标,提出一种动态图转换模型(DGTM)和动态位置编码(DPE)方法,并使用一种双重损失REINFORCE算法训练DGTM模型。此外,强化学习、图神经网络和Transformer架构相结合,提高了模型的训练效率,增强了神经网络对带约束路径问题信息的表征能力。实验结果表明,DGTM模型在此问题上的优化效果超越了目前基于深度强化学习的方法和部分传统算法,整体性能优于专业求解器的,且具有较好的泛化性能,为求解图上组合最优化问题提供了一种有效方法。Capacitated vehicle routing problem is one of the classic combinatorial optimization problems,which has been studied repeatedly for many years.Recently,Transformer has become the dominant deep learning architecture for solving vehicle routing problems.However,traditional positional encoding method is not suitable for extracting location information for dynamic optimization problems.The state of an instance is changed according to the model at different construction steps,and the node features should be updated correspondingly.Therefore,current methods have poor effect on improving learning efficiency.With the goal of minimizing the routing length,a dynamic graph transformer model(DGTM)and a dynamic positional encoding(DPE)method are proposed,and a double-loss REINFORCE algorithm is used to train the DGTM model.In addition,reinforcement learning,graph neural networks and Transformer architecture are combined to improve the training efficiency of the model.It enhances the information representation of the neural network for routing problems with constraints.The experimental results show that the optimization of the model on this problem outperforms current deep reinforcement learning methods and some traditional algorithms.The DGTM model has better overall performance than the professional solver and has good generalization performance,which provides an effective method for solving the combinatorial optimization problems on graphs.

关 键 词：带容量的车辆路径问题 动态图转换模型 动态位置编码 深度强化学习 图神经网络 组合最优化问题 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]