Edge-Driven Multiple Trajectory Attention Model for Vehicle Routing Problems

The vehicle routing problem (VRP), as one of the classic combinatorial optimization problems, has garnered widespread attention in recent years. Existing deep reinforcement learning (DRL)-based methods predominantly focus on node information, neglecting the edge information inherent in the graph structure. Moreover, the solution trajectories produced by these methods tend to exhibit limited diversity, hindering a thorough exploration of the solution space. In this work, we propose a novel Edge-Driven Multiple Trajectory Attention Model (E-MTAM) to solve VRPs with various scales. Our model is built upon the encoder–decoder architecture, incorporating an edge-driven multi-head attention (EDMHA) block within the encoder to better utilize edge information. During the decoding process, we enhance graph embeddings with visitation information, integrating dynamic updates into static graph embeddings. Additionally, we employ a multi-decoder architecture and introduce a regularization term to encourage the generation of diverse trajectories, thus promoting solution diversity. We conduct comprehensive experiments on three types of VRPs: (1) traveling salesman problem (TSP), (2) capacitated vehicle routing problem (CVRP), and (3) orienteering problem (OP). The experimental results demonstrate that our model outperforms existing DRL-based methods and most traditional heuristic approaches, while also exhibiting strong generalization across problems of different scales.