Travel the Same Path: A Novel TSP Solving Strategy

2022/10/12 by Pingbang Hu, Hu, Pingbang
Computer Science · #Advanced Graph Neural Networks #Artificial Intelligence (cs.AI) #Constraint Satisfaction and Optimization #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Metaheuristic Optimization Algorithms Research #Optimization and Control (math.OC)

paper · pdf · doi:10.48550/arxiv.2210.05906

openalex publication_date 2022/10/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper, we provide a novel strategy for solving Traveling Salesman Problem, which is a famous combinatorial optimization problem studied intensely in the TCS community. In particular, we consider the imitation learning framework, which helps a deterministic algorithm making good choices whenever it needs to, resulting in a speed up while maintaining the exactness of the solution without suffering from the unpredictability and a potential large deviation. Furthermore, we demonstrate a strong generalization ability of a graph neural network trained under the imitation learning framework. Specifically, the model is capable of solving a large instance of TSP faster than the baseline while has only seen small TSP instances when training.

Related

• Improving Generalization of Deep Reinforcement Learning-based TSP Solvers
• Unsupervised Training for Neural TSP Solver
• A Generative Graph Method to Solve the Travelling Salesman Problem
• Learning to Optimise General TSP Instances
• Unsupervised Learning for Solving the Travelling Salesman Problem