A Generative Graph Method to Solve the Travelling Salesman Problem

Amal Nammouchi, Hakim Ghazzai, Yehia Massoud

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations


The Travelling Salesman Problem (TSP) is a challenging graph task in combinatorial optimization that requires reasoning about both local node neighborhoods and global graph structure. In this paper, we propose to use the novel Graph Learning Network (GLN), a generative approach, to approximately solve the TSP. GLN model learns directly the pattern of TSP instances as training dataset, encodes the graph properties, and merge the different node embeddings to output node-to-node an optimal tour directly or via graph search technique that validates the final tour. The preliminary results of the proposed novel approach proves its applicability to this challenging problem providing a low optimally gap with significant computation saving compared to the optimal solution.
Original languageEnglish (US)
Title of host publicationMidwest Symposium on Circuits and Systems
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages4
ISBN (Print)9781538629161
StatePublished - Aug 1 2020
Externally publishedYes

Bibliographical note

Generated from Scopus record by KAUST IRTS on 2022-09-13


Dive into the research topics of 'A Generative Graph Method to Solve the Travelling Salesman Problem'. Together they form a unique fingerprint.

Cite this