Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/148040
Title: Efficient graph neural networks for travelling salesman problem using multilevel clustering
Authors: Dwivedee, Lakshyajeet
Keywords: Engineering::Computer science and engineering::Computing methodologies::Artificial intelligence
Issue Date: 2021
Publisher: Nanyang Technological University
Source: Dwivedee, L. (2021). Efficient graph neural networks for travelling salesman problem using multilevel clustering. Final Year Project (FYP), Nanyang Technological University, Singapore. https://hdl.handle.net/10356/148040
Project: SCSE20-0266
Abstract: The goal of the Travelling Salesman Problem is to find the shortest route that visits each city exactly once and returns to the origin, given a list of cities and the distances between each pair of cities. Such combinatorial optimization problems are difficult to solve efficiently given large problem sizes. Algorithms that solve such problems have applications in many fields such as transportation, operations, and networks. Most solutions formulate heuristics which are policies used by algorithms to search for approximate solutions. These heuristics are designed manually and require specialized knowledge. Graph neural networks have recently been used to automate the creation of these heuristics. However, current state-of-the-art graph neural networks have slow training and inference times due to their O(n2) time complexity. In this paper, we introduce a Multilevel Graph Neural Network (MGNN) for approximating solutions to the TSP by using graph clustering which solves the TSP at multiple resolutions. We train our models on input graph sizes of up to 128 nodes and measure the accuracy as well as experimental time complexity with respect to the graph size. Our divide-and-conquer strategy effectively combats combinatorial explosion by enabling a linear runtime of O(n) at the cost of model accuracy.
URI: https://hdl.handle.net/10356/148040
Fulltext Permission: restricted
Fulltext Availability: With Fulltext
Appears in Collections:SCSE Student Reports (FYP/IA/PA/PI)

Files in This Item:
File Description SizeFormat 
SCSE20-0266_Report.pdf
  Restricted Access
12.38 MBAdobe PDFView/Open

Page view(s)

195
Updated on May 15, 2022

Download(s)

17
Updated on May 15, 2022

Google ScholarTM

Check

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.