Skip to search boxSkip to navigationSkip to main content

Revisit the Algorithm Selection Problem for TSP with Spatial Information Enhanced Graph Neural Networks

Output:
Chapter in Book/Report/Conference proceeding
Conference contribution
Academic
Peer-review

Open access

Information

Output type

Output:
Chapter in Book/Report/Conference proceeding
Conference contribution
Academic
Peer-review

Host publication Subtitle

Volume 3: ICAART

Original language

English

Pages from-to (Number of pages)

Pages 472-479 (8 pages)

Publication milestones

  • Published - 2025

Publication status

Published - 2025

Publisher

SciTePress Digital Library

ISBN (Electronic)

978-989-758-737-5

Host publication title

Proceedings of the 17th International Conference on Agents and Artificial Intelligence

Host publication editors

  • Ana Paula Rocha
  • Luc Steels
  • H. Jaap van den Herik

Related Event

Title

17th International Conference on Agents and Artificial Intelligence , ICAART 2025

Event type

Conference

Degree of recognition

International event

Date

23/02/2025 - 25/02/2025

Location

PortoPortugal

Abstract

Algorithm selection is a well-known problem where researchers investigate how to construct useful features representing the problem instances and then apply feature-based machine learning models to predict the best algorithm for each instance. However, even for simple optimization problems like Euclidean Traveling Salesman Problem (TSP), there lacks a general and effective feature representation for problem instances. The important features of TSP are relatively well understood in the literature, based on extensive domain knowledge and post-analysis of the solutions. In recent years, Convolutional Neural Network (CNN) has gained popularity for TSP algorithm selection. Compared to traditional feature-based models, CNN has an automatic feature-learning ability and demands less domain expertise. However, it is still required to generate intermediate representations, i.e., multiple images to represent TSP instances first. In this paper, we revisit algorithm selection for TSP and propose GINES, a new Graph Neural Network (GNN) that uses city coordinates and distances as input. GINES introduces a novel message-passing mechanism and local feature extractor to learn TSP’s spatial information. Evaluation of two benchmarks shows GINES outperforms CNN and GINE models and surpasses traditional feature-based methods on one dataset. Our codes and datasets are available at https://github.com/lurenyi233/GINES TSP.

Metrics

Metrics

SciVal
FWCI
0.73
SciVal
Author count
3
SciVal
Paper percentile
64
SciVal
citations
1
Scopus
citations
1

PlumX, opens in new tab

Citation count
1
Captures
5