Abstract:

The capacitated vehicle routing problem (CVRP) is a well-known combinatorial optimization challenge recognized as NP-hard due to its significant complexity. Building upon existing research, this paper introduces a novel end-to-end deep reinforcement learning approach based on a multi-pointer Transformer to tackle the CVRP. The proposed algorithm employs an invertible residual network in the encoder to encode input features, effectively reducing memory consumption. In the decoder, a multi-pointer network determines the probability distribution of solutions. To further enhance the performance of CVRP solutions, the algorithm leverages the symmetry in combinatorial optimization by implementing multi-trajectory parallel processing during both training and inference phases. Additionally, an enhanced contextual embedding method is utilized, and the model is trained using an improved reinforcement learning algorithm. Experimental results demonstrate that the proposed model strikes the best balance between solving speed and quality with lower memory usage compared to current classic heuristic algorithms and other deep learning approaches.

Key words: deep reinforcement learning, vehicle routing problem, invertible residual networks, attention mechanisms, improved REINFORCE algorithm