A bidirectional graph neural network for traveling salesman problems on arbitrary symmetric graphs

Simple item page
dc.contributor.authorHu, Y.
dc.contributor.authorZhang, Z.
dc.contributor.authorYao, Y.
dc.contributor.authorHuyan, X.
dc.contributor.authorZhou, X.
dc.contributor.authorLee, W.S.
dc.date.issued2021
dc.descriptionAvailable online 10 November 2020
dc.description.abstractDeep learning has recently been shown to provide great achievement to the traveling salesman problem (TSP) on the Euclidean graphs. These methods usually fully represent the graph by a set of coordinates, and then captures graph information from the coordinates to generate the solution. The TSP on arbitrary symmetric graphs models more realistic applications where the working graphs maybe sparse, or the distance between points on the graphs may not satisfy the triangle inequality. When prior learning-based methods being applied to the TSP on arbitrary symmetric graphs, they are not capable to capture graph features that are beneficial to produce near-optimal solutions. Moreover, they suffer from serious exploration problems. This paper proposes a bidirectional graph neural network (BGNN) for the arbitrary symmetric TSP. The network learns to produce the next city to visit sequentially by imitation learning. The bidirectional message passing layer is designed as the most important component of BGNN. It is able to encode graphs based on edges and partial solutions. By this way, the proposed approach is much possible to construct near-optimal solutions for the TSP on arbitrary symmetric graphs, and it is able to be combined with informed search to further improve performance.
dc.description.statementofresponsibilityYujiao Hu, Zhen Zhang, Yuan Yao, Xingpeng Huyan, Xingshe Zhou, Wee Sun Lee
dc.identifier.citationEngineering Applications of Artificial Intelligence, 2021; 97:104061-1-104061-9
dc.identifier.doi10.1016/j.engappai.2020.104061
dc.identifier.issn0952-1976
dc.identifier.issn1873-6769
dc.identifier.orcidZhang, Z. [0000-0003-2805-4396]
dc.identifier.urihttp://hdl.handle.net/2440/131947
dc.language.isoen
dc.publisherElsevier
dc.rights© 2020 Elsevier Ltd. All rights reserved.
dc.source.urihttps://doi.org/10.1016/j.engappai.2020.104061
dc.subjectDeep learning; Graph neural network; Traveling salesman problem; Combinatorial optimization problems; Planning
dc.titleA bidirectional graph neural network for traveling salesman problems on arbitrary symmetric graphs
dc.typeJournal article
pubs.publication-statusPublished

Files

Collections

Australian Institute for Machine Learning publications