深度强化学习求解车辆路径问题的研究综述  

Review of Deep Reinforcement Learning Model Research on Vehicle Routing Problems

作　　者：杨笑笑 柯琳 陈智斌[1] YANG Xiaoxiao;KE Lin;CHEN Zhibin(School of Science and Technology,Kunming University of Science and Technology,Kunming 650000,China)

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

出　　处：《计算机工程与应用》2023年第5期1-13,共13页Computer Engineering and Applications

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

摘　　要：车辆路径问题(VRP)是组合优化问题中经典的NP难问题,广泛应用于交通、物流等领域,随着问题规模和动态因素的增多,传统算法很难快速、智能地求解复杂的VRP问题。近年来随着人工智能技术的发展,尤其是深度强化学习(DRL)在AlphaGo中的成功应用,为路径问题求解提供了全新思路。鉴于此,针对近年来利用DRL求解VRP及其变体问题的模型进行文献综述。回顾了DRL求解VRP的相关思路,并梳理基于DRL求解VRP问题的关键步骤,对基于指针网络、图神经网络、Transformer和混合模型的四类求解方法分类总结,同时对目前基于DRL求解VRP及其变体问题的模型性能进行对比分析,总结了基于DRL求解VRP问题时遇到的挑战以及未来的研究方向。Vehicle routing problem(VRP)is a classic NP-hard problem, which is widely used in transportation, logistics and other fields. With the scale of problem and dynamic factor increasing, the traditional method of solving the VRP is challenged in computational speed and intelligence. In recent years, with the rapid development of artificial intelligence technology, in particular, the successful application of reinforcement learning in AlphaGo provides a new idea for solving routing problems. In view of this, this paper mainly summarizes the recent literature using deep reinforcement learning to solve VRP and its variants. Firstly, it reviews the relevant principles of DRL to solve VRP and sort out the key steps of DRL-based to solve VRP. Then it systematically classifies and summarizes the pointer network, graph neural network,Transformer and hybrid models four types of solving methods, meanwhile this paper also compares and analyzes the current DRL-based model performance in solving VRP and its variants. Finally, this paper sums up the challenge of DRL-based to solve VRP and future research directions.

关 键 词：车辆路径问题 深度强化学习 指针网络 图神经网络 混合模型 

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