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 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.

Keywords

• simultaneous pickup-delivery vehicle routing problem; time window; deep reinforcement learning; large neighborhood search