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 reinforcement 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 designed 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 autoregressive structures. The neural network architecture uses reinforcement learning for training. A hybrid strategy is also designed, 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

摘要： 带时间窗约束的同时取送货车辆路径问题（VRPSPDTW）是NP难问题，属于约束较复杂的车辆路径问题，在现代物流中有广泛应用。提出深度强化学习Memetic算法求解该问题，将Memetic算法求解VRPSPDTW问题中的大邻域搜索过程建模成马尔可夫决策过程，构建编码器-解码器架构的深度神经网络模型完成大邻域搜索中的移除操作。编码器对当前解中各结点的个体特征和位置特征进行信息交互，解码器输出需要移除的结点，设计了非自回归和自回归两种网络结构，采用强化学习算法训练神经网络模型。设计了混合策略，将人工设计的启发式策略与深度强化学习到的策略相结合，以提高寻优能力。实验结果显示提出的算法具有更强的跳出局部最优的能力，能在有效的时间内获得比对比算法更优的解，特别是在大规模问题上。最后，对提出算法的新组件进行了消融实验，证明了算法的有效性。

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