深度强化学习Memetic算法求解取送货车辆路径问题  

Memetic Algorithm Based on Deep Reinforcement Learning for Vehicle Routing Problem with Pickup-Delivery

作　　者：周雅兰 廖易天 粟筱 王甲海 ZHOU Yalan;LIAO Yitian;SU Xiao;WANG Jiahai(College of Information,Guangdong University of Finance&Economics,Guangzhou 510320,China;School of Computer Science,Sun Yat-sen University,Guangzhou 510275,China)

机构地区：[1]广东财经大学信息学院,广州510320 [2]中山大学计算机学院,广州510275

出　　处：《计算机科学与探索》2024年第3期818-830,共13页Journal of Frontiers of Computer Science and Technology

基　　金：国家自然科学基金(62072483);广东省自然科学基金(2021A1515012298)。

摘　　要：带时间窗约束的同时取送货车辆路径问题(VRPSPDTW)是NP难问题,属于约束较复杂的车辆路径问题,在现代物流中有广泛应用。提出深度强化学习Memetic算法求解该问题,将Memetic算法求解VRPSPDTW问题中的大邻域搜索过程建模成马尔可夫决策过程,构建编码器-解码器架构的深度神经网络模型完成大邻域搜索中的移除操作。编码器对当前解中各结点的个体特征和位置特征进行信息交互,解码器输出需要移除的结点,设计了非自回归和自回归两种网络结构,采用强化学习算法训练神经网络模型。设计了混合策略,将人工设计的启发式策略与深度强化学习到的策略相结合,以提高寻优能力。实验结果显示提出的算法具有更强的跳出局部最优的能力,能在有效的时间内获得比对比算法更优的解,特别是在大规模问题上。最后,对提出算法的新组件进行了消融实验,证明了算法的有效性。The vehicle routing problem with simultaneous pickup-delivery and time windows(VRPSPDTW)is a NP hard problem,which has a wide application in modern logistics.Memetic algorithm based on deep reinforce-ment learning is proposed to solve the problem.The large neighborhood search process of Memetic algorithm for VRPSPDTW is modeled into a Markov decision process.An encoder-decoder neural network architecture is de-signed for the removal operation in large neighborhood search.The extracted individual characteristics and location characteristics of all nodes in the current solution are input into the encoder for information interaction.The decoder outputs the nodes to be removed.Two kinds of decoders are designed including non-autoregressive and autoregres-sive structures.The neural network architecture uses reinforcement learning for training.A hybrid strategy is also de-signed,combining manually designed heuristic strategies with strategies learned through deep reinforcement learning to improve the optimization ability.Experimental results show that the proposed algorithm has a stronger ability to jump out of the local optimum,and can provide better solutions than the comparison algorithms in an effective time,especially in solving large-scale problems.In addition,ablation experiments are conducted on the new components of the proposed algorithm to show the effectiveness.

关 键 词：同时取送货车辆路径问题 时间窗 深度强化学习 大邻域搜索 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]