基于强化学习的超启发算法求解有容量车辆路径问题

Hyper-heuristic for CVRP with reinforcement learning

为了更高效地求解物流优化领域中的有容量车辆路径问题,减少陷入局部最优的情况,提出一种基于强化学习的超启发算法。设计了算法的高层启发式策略,包括选择策略和解的接受准则:基于学习机制,使用强化学习中的深度Q神经网络算法构造该算法的选择策略,对底层算子的性能进行奖惩评价;利用奖惩值以及模拟退火作为算法的接受准则,对优质解建立序列池,从而引导算法更有效地搜索解空间,并采用聚类思想提升初始解的质量。对有容量车辆问题的标准算例进行计算,并与其他算法对比,统计分析了最优值、误差率和平均值,实验结果表明了所提算法在该问题求解上的有效性和稳定性,总体求解效果优于对比算法。

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.