Abstract: Capacitated vehicle routing problem is one of the classic combinatorial optimization problems, which has been studied repeatedly for many years. Recently, Transformer has become the dominant deep learning architecture for solving vehicle routing problems. However, traditional positional encoding method is not suitable for extracting location information for dynamic optimization problems. The state of an instance is changed according to the model at different construction steps, and the node features should be updated correspondingly. Therefore, current methods have poor effect on improving learning efficiency. With the goal of minimizing the routing length, a dynamic graph transformer model (DGTM) and a dynamic positional encoding (DPE) method are proposed, and a double-loss REINFORCE algorithm is used to train the DGTM model. In addition, reinforcement learning, graph neural networks and Transformer architecture are combined to improve the training efficiency of the model. It enhances the information representation of the neural network for routing problems with constraints. The experimental results show that the optimization of the model on this problem outperforms current deep reinforcement learning methods and some traditional algorithms. The DGTM model has better overall performance than the professional solver and has good generalization performance, which provides an effective method for solving the combinatorial optimization problems on graphs.

Key words: capacitated vehicle routing problem (CVRP), dynamic graph transformer model (DGTM), dynamic positional encoding (DPE), deep reinforcement learning (DRL), graph neural networks (GNNs), combinatorial optimization (CO)