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 str...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-03-01
|
| Series: | Applied Sciences |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2076-3417/15/5/2679 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850030814116446208 |
|---|---|
| author | Dapeng Yan Bei Ou Qingshu Guan Zheng Zhu Hui Cao |
| author_facet | Dapeng Yan Bei Ou Qingshu Guan Zheng Zhu Hui Cao |
| author_sort | Dapeng Yan |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-9652984ba5c746528484f8b407a2e2cf |
| institution | DOAJ |
| issn | 2076-3417 |
| language | English |
| publishDate | 2025-03-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Applied Sciences |
| spelling | doaj-art-9652984ba5c746528484f8b407a2e2cf2025-08-20T02:59:07ZengMDPI AGApplied Sciences2076-34172025-03-01155267910.3390/app15052679Edge-Driven Multiple Trajectory Attention Model for Vehicle Routing ProblemsDapeng Yan0Bei Ou1Qingshu Guan2Zheng Zhu3Hui Cao4State Key Laboratory of Electrical Insulation and Power Equipment, Xi’an Jiaotong University, Xi’an 710049, ChinaSchool of Electrical Engineering, Xi’an Jiaotong University, Xi’an 710049, ChinaSchool of Electrical Engineering, Xi’an Jiaotong University, Xi’an 710049, ChinaSchool of Electrical Engineering, Xi’an Jiaotong University, Xi’an 710049, ChinaState Key Laboratory of Electrical Insulation and Power Equipment, Xi’an Jiaotong University, Xi’an 710049, ChinaThe 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.https://www.mdpi.com/2076-3417/15/5/2679combinatorial optimizationvehicle routing problemdeep reinforcement learningedge-driven multi-head attention |
| spellingShingle | Dapeng Yan Bei Ou Qingshu Guan Zheng Zhu Hui Cao Edge-Driven Multiple Trajectory Attention Model for Vehicle Routing Problems Applied Sciences combinatorial optimization vehicle routing problem deep reinforcement learning edge-driven multi-head attention |
| title | Edge-Driven Multiple Trajectory Attention Model for Vehicle Routing Problems |
| title_full | Edge-Driven Multiple Trajectory Attention Model for Vehicle Routing Problems |
| title_fullStr | Edge-Driven Multiple Trajectory Attention Model for Vehicle Routing Problems |
| title_full_unstemmed | Edge-Driven Multiple Trajectory Attention Model for Vehicle Routing Problems |
| title_short | Edge-Driven Multiple Trajectory Attention Model for Vehicle Routing Problems |
| title_sort | edge driven multiple trajectory attention model for vehicle routing problems |
| topic | combinatorial optimization vehicle routing problem deep reinforcement learning edge-driven multi-head attention |
| url | https://www.mdpi.com/2076-3417/15/5/2679 |
| work_keys_str_mv | AT dapengyan edgedrivenmultipletrajectoryattentionmodelforvehicleroutingproblems AT beiou edgedrivenmultipletrajectoryattentionmodelforvehicleroutingproblems AT qingshuguan edgedrivenmultipletrajectoryattentionmodelforvehicleroutingproblems AT zhengzhu edgedrivenmultipletrajectoryattentionmodelforvehicleroutingproblems AT huicao edgedrivenmultipletrajectoryattentionmodelforvehicleroutingproblems |