计算机科学与探索2024，Vol.18Issue(3)：818-830,13.DOI:10.3778/j.issn.1673-9418.2302072
深度强化学习Memetic算法求解取送货车辆路径问题
Memetic Algorithm Based on Deep Reinforcement Learning for Vehicle Routing Problem with Pickup-Delivery
摘要
Abstract
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.关键词
同时取送货车辆路径问题/时间窗/深度强化学习/大邻域搜索Key words
simultaneous pickup-delivery vehicle routing problem/time window/deep reinforcement learning/large neighborhood search分类
信息技术与安全科学引用本文复制引用
周雅兰,廖易天,粟筱,王甲海..深度强化学习Memetic算法求解取送货车辆路径问题[J].计算机科学与探索,2024,18(3):818-830,13.基金项目
国家自然科学基金(62072483) （62072483）
广东省自然科学基金(2021A1515012298).This work was supported by the National Natural Science Foundation of China(62072483),and the Natural Science Foundation of Guangdong Province(2021A1515012298). （2021A1515012298）
