Graph attention, learning 2-opt algorithm for the traveling salesman problem
Abstract In recent years, deep graph neural networks (GNNs) have been used as solvers or helper functions for the traveling salesman problem (TSP), but they are usually used as encoders to generate static node representations for downstream tasks and are incapable of obtaining the dynamic permutatio...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Springer
2025-01-01
|
| Series: | Complex & Intelligent Systems |
| Subjects: | |
| Online Access: | https://doi.org/10.1007/s40747-024-01716-5 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832571167742885888 |
|---|---|
| author | Jia Luo Herui Heng Geng Wu |
| author_facet | Jia Luo Herui Heng Geng Wu |
| author_sort | Jia Luo |
| collection | DOAJ |
| description | Abstract In recent years, deep graph neural networks (GNNs) have been used as solvers or helper functions for the traveling salesman problem (TSP), but they are usually used as encoders to generate static node representations for downstream tasks and are incapable of obtaining the dynamic permutational information in completely updating solutions. For addressing this problem, we propose a permutational encoding graph attention encoder and attention-based decoder (PEG2A) model for the TSP that is trained by the advantage actor-critic algorithm. In this work, the permutational encoding graph attention (PEGAT) network is designed to encode node embeddings for gathering information from neighbors and obtaining the dynamic graph permutational information simultaneously. The attention-based decoder is tailored to compute probability distributions over picking pair nodes for 2-opt moves. The experimental results show that our method outperforms the compared learning-based algorithms and traditional heuristic methods. |
| format | Article |
| id | doaj-art-5ae247dca1394ab38b00ed70d0b44f8f |
| institution | Kabale University |
| issn | 2199-4536 2198-6053 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | Springer |
| record_format | Article |
| series | Complex & Intelligent Systems |
| spelling | doaj-art-5ae247dca1394ab38b00ed70d0b44f8f2025-02-02T12:49:47ZengSpringerComplex & Intelligent Systems2199-45362198-60532025-01-0111112110.1007/s40747-024-01716-5Graph attention, learning 2-opt algorithm for the traveling salesman problemJia Luo0Herui Heng1Geng Wu2School of Economics and Management, Ningbo University of TechnologyInstitute of Logistics Science and Engineering, Shanghai Maritime UniversitySchool of Economics and Management, Ningbo University of TechnologyAbstract In recent years, deep graph neural networks (GNNs) have been used as solvers or helper functions for the traveling salesman problem (TSP), but they are usually used as encoders to generate static node representations for downstream tasks and are incapable of obtaining the dynamic permutational information in completely updating solutions. For addressing this problem, we propose a permutational encoding graph attention encoder and attention-based decoder (PEG2A) model for the TSP that is trained by the advantage actor-critic algorithm. In this work, the permutational encoding graph attention (PEGAT) network is designed to encode node embeddings for gathering information from neighbors and obtaining the dynamic graph permutational information simultaneously. The attention-based decoder is tailored to compute probability distributions over picking pair nodes for 2-opt moves. The experimental results show that our method outperforms the compared learning-based algorithms and traditional heuristic methods.https://doi.org/10.1007/s40747-024-01716-5TSP2-optPermutational encodingGraph attention networkAttention-based mechanismActor-critic algorithm |
| spellingShingle | Jia Luo Herui Heng Geng Wu Graph attention, learning 2-opt algorithm for the traveling salesman problem Complex & Intelligent Systems TSP 2-opt Permutational encoding Graph attention network Attention-based mechanism Actor-critic algorithm |
| title | Graph attention, learning 2-opt algorithm for the traveling salesman problem |
| title_full | Graph attention, learning 2-opt algorithm for the traveling salesman problem |
| title_fullStr | Graph attention, learning 2-opt algorithm for the traveling salesman problem |
| title_full_unstemmed | Graph attention, learning 2-opt algorithm for the traveling salesman problem |
| title_short | Graph attention, learning 2-opt algorithm for the traveling salesman problem |
| title_sort | graph attention learning 2 opt algorithm for the traveling salesman problem |
| topic | TSP 2-opt Permutational encoding Graph attention network Attention-based mechanism Actor-critic algorithm |
| url | https://doi.org/10.1007/s40747-024-01716-5 |
| work_keys_str_mv | AT jialuo graphattentionlearning2optalgorithmforthetravelingsalesmanproblem AT heruiheng graphattentionlearning2optalgorithmforthetravelingsalesmanproblem AT gengwu graphattentionlearning2optalgorithmforthetravelingsalesmanproblem |