关键词: 车辆路径问题, 强化学习, 深度Q神经网络, 超启发算法

Abstract: To reduce the situation of falling into local optimum and solve the capacitated vehicle routing problem,a hyper-heuristic algorithm based on reinforcement learning was.A high-level heuristic strategy was designed,which included selection strategy and acceptance criteria.Based on the learning mechanism,the deep Q neural network algorithm in reinforcement learning was used to construct the selection strategy,and evaluate the performance of the underlying operator with rewards and punishments;Rewards and punishments as well as simulated annealing was used as the acceptance criteria,and a sequence pool was constructed for high-quality solutions,so as to guide the algorithm searching effectively.Also,the clustering method was used to improve the quality of the initial solution.The optimal value was analyzed,error rate and average value were compared with other algorithms.The experimental results show that the proposed algorithm was effect and stable in solving the problem,and the overall solution effect was better than the comparison algorithm.

Key words: vehicle routing problem, reinforcement learning, deep Q neural network, hyper-heuristic algorithm