Synergetic attention-driven transformer: A deep reinforcement learning approach for vehicle routing problems

Recently, deep reinforcement learning (DRL) has emerged as a promising avenue for tackling vehicle routing problems (VRPs). However, prevailing methods predominantly concentrate on learning construction policies, which often yield suboptimal outcomes in terms of generalization. In this study, we build upon an encoder–decoder framework and propose a synergetic attention-driven transformer (SAT) to acquire improvement policies, which strive to refine the current complete solution iteratively. During the encoding phase, we devise a multi-head synergetic attention mechanism to simultaneously learn node feature tokens and access index tokens in a dual pathway, thereby mitigating potential noises and incompatible correlations. Furthermore, we employ a cyclic mapping strategy to embed access sequences, enabling the capture of the inherent circularity and symmetry attributes within VRP solutions. In the decoding phase, we incorporate multiple decoders and formulate two regularization losses from perspectives of external policies and internal parameters to enhance the diversity of alternative solutions, thus broadening the search space efficiently. In the training phase, we utilize proximal policy optimization to ensure rapid and stable convergence of our model. Finally, we evaluate the efficacy of our method on two representative VRPs, namely the traveling salesman problem (TSP) and the capacitated VRP (CVRP). Comprehensive experiments on both synthetic and real-world benchmarks demonstrate that our SAT outperforms heuristic and DRL methods by a significant margin of up to 8.56% in precision, and also exhibits much better generalization performance on problems across varying sizes and distributions.