TY - JOUR

T1 - G-DGANet

T2 - Gated deep graph attention network with reinforcement learning for solving traveling salesman problem

AU - Fellek, Getu

AU - Farid, Ahmed

AU - Fujimura, Shigeru

AU - Yoshie, Osamu

AU - Gebreyesus, Goytom

N1 - Publisher Copyright:
© 2024 Elsevier B.V.

PY - 2024/4/28

Y1 - 2024/4/28

N2 - Combinatorial optimization problem (COP) is an NP-hard problem for which finding an optimal solution is difficult, especially as the problem size increases. The Traveling Salesman Problem (TSP), one of the COPs that can be formulated over a graph, is a well-researched area in operations research and computer science. Deep Reinforcement Learning (DRL) is now regarded as a promising approach for solving TSP and other NP hard problems. In this paper, we propose a novel Gated Deep Graph Attention Network (G-DGANet) which builds upon the existing Graph Neural Network (GNN) to solve TSP. The proposed G-DGANet uses gating mechanism between subsequent layers of the network to extract representations of nodes deeper in the network without loss in performance. G-DGANet also designs a novel aggregator to construct global graph embeddings from different embedding preferences. In addition, to effectively learn underlying structure of a graph, G-DGANet integrates node and edge information of the graph while updating node representations in the message passing mechanism. We used proximal policy optimization (PPO) to train G-DGANet on randomly generated instances. We conducted an experiment on randomly generated instances and on real-world road network data generated from digital maps to verify the performance of G-DGANet. The findings from experiments demonstrate that G-DGANet outperforms most traditional heuristics and existing DRL approaches, with high generalization abilities from random instance training to random instance testing and real-world road network instance testing.

AB - Combinatorial optimization problem (COP) is an NP-hard problem for which finding an optimal solution is difficult, especially as the problem size increases. The Traveling Salesman Problem (TSP), one of the COPs that can be formulated over a graph, is a well-researched area in operations research and computer science. Deep Reinforcement Learning (DRL) is now regarded as a promising approach for solving TSP and other NP hard problems. In this paper, we propose a novel Gated Deep Graph Attention Network (G-DGANet) which builds upon the existing Graph Neural Network (GNN) to solve TSP. The proposed G-DGANet uses gating mechanism between subsequent layers of the network to extract representations of nodes deeper in the network without loss in performance. G-DGANet also designs a novel aggregator to construct global graph embeddings from different embedding preferences. In addition, to effectively learn underlying structure of a graph, G-DGANet integrates node and edge information of the graph while updating node representations in the message passing mechanism. We used proximal policy optimization (PPO) to train G-DGANet on randomly generated instances. We conducted an experiment on randomly generated instances and on real-world road network data generated from digital maps to verify the performance of G-DGANet. The findings from experiments demonstrate that G-DGANet outperforms most traditional heuristics and existing DRL approaches, with high generalization abilities from random instance training to random instance testing and real-world road network instance testing.

KW - Deep graph representation learning

KW - Deep reinforcement learning

KW - Graph neural network

KW - Traveling salesman problem

UR - http://www.scopus.com/inward/record.url?scp=85186604554&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85186604554&partnerID=8YFLogxK

U2 - 10.1016/j.neucom.2024.127392

DO - 10.1016/j.neucom.2024.127392

M3 - Article

AN - SCOPUS:85186604554

SN - 0925-2312

VL - 579

JO - Neurocomputing

JF - Neurocomputing

M1 - 127392

ER -