Efficient graph neural networks for travelling salesman problem using multilevel clustering
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 proble...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Final Year Project (FYP) |
| Language: | English |
| Published: |
Nanyang Technological University
2021
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/148040 |
| _version_ | 1824457086080122880 |
|---|---|
| author | Dwivedee, Lakshyajeet |
| author2 | Xavier Bresson |
| author_facet | Xavier Bresson Dwivedee, Lakshyajeet |
| author_sort | Dwivedee, Lakshyajeet |
| collection | NTU |
| description | 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. |
| first_indexed | 2025-02-19T04:04:24Z |
| format | Final Year Project (FYP) |
| id | ntu-10356/148040 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2025-02-19T04:04:24Z |
| publishDate | 2021 |
| publisher | Nanyang Technological University |
| record_format | dspace |
| spelling | ntu-10356/1480402021-04-22T06:21:59Z Efficient graph neural networks for travelling salesman problem using multilevel clustering Dwivedee, Lakshyajeet Xavier Bresson School of Computer Science and Engineering xbresson@ntu.edu.sg Engineering::Computer science and engineering::Computing methodologies::Artificial intelligence 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. Bachelor of Engineering (Computer Engineering) 2021-04-22T06:21:59Z 2021-04-22T06:21:59Z 2021 Final Year Project (FYP) 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 https://hdl.handle.net/10356/148040 en SCSE20-0266 application/pdf Nanyang Technological University |
| spellingShingle | Engineering::Computer science and engineering::Computing methodologies::Artificial intelligence Dwivedee, Lakshyajeet Efficient graph neural networks for travelling salesman problem using multilevel clustering |
| title | Efficient graph neural networks for travelling salesman problem using multilevel clustering |
| title_full | Efficient graph neural networks for travelling salesman problem using multilevel clustering |
| title_fullStr | Efficient graph neural networks for travelling salesman problem using multilevel clustering |
| title_full_unstemmed | Efficient graph neural networks for travelling salesman problem using multilevel clustering |
| title_short | Efficient graph neural networks for travelling salesman problem using multilevel clustering |
| title_sort | efficient graph neural networks for travelling salesman problem using multilevel clustering |
| topic | Engineering::Computer science and engineering::Computing methodologies::Artificial intelligence |
| url | https://hdl.handle.net/10356/148040 |
| work_keys_str_mv | AT dwivedeelakshyajeet efficientgraphneuralnetworksfortravellingsalesmanproblemusingmultilevelclustering |