Solving the VRP Using Transformer-Based Deep Reinforcement Learning

The Vehicle Routing Problem (VRP) is a well-known NP-hard problem, and finding fast and efficient algorithms for VRP has been a major research focus in the academic community. In recent years, the advancements in deep reinforcement learning have provided new possibilities for solving VRP. This paper proposes a novel approach for solving VRP using a Transformer-based deep reinforcement learning framework with an encoder-decoder structure. The encoder utilizes a Transformer model to encode the VRP problem, while the decoder incorporates the positional information of the nodes that have already been visited as input and generates a sequence of nodes to be visited as the output solution. Finally, the entire model is trained using reinforcement learning. Experimental results demonstrate that that the GAP value of our model in CRP20 has decreased to 0.705%, which is more stable than other models and has a much faster solving speed than the heuristic model.