An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem

Abstract

This paper introduces a new learning-based approach for approximately solving the Travelling Salesman Problem on 2D Euclidean graphs. We use deep Graph Convolutional Networks to build efficient TSP graph representations and output tours in a non-autoregressive manner via highly parallelized beam search. Our approach outperforms all recently proposed autoregressive deep learning techniques in terms of solution quality, inference speed and sample efficiency for problem instances of fixed graph sizes. In particular, we reduce the average optimality gap from 0.52% to 0.01% for 50 nodes, and from 2.26% to 1.39% for 100 nodes. Finally, despite improving upon other learning-based approaches for TSP, our approach falls short of standard Operations Research solvers.

References in corpus (4)

• Sequence to Sequence Learning with Neural Networks
• Semi-Supervised Classification with Graph Convolutional Networks
• Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation
• Learning Heuristics over Large Graphs via Deep Reinforcement Learning

Cited by in corpus (49)

• Principal Neighbourhood Aggregation for Graph Nets
• Benchmarking Graph Neural Networks
• Combinatorial Optimization with Physics-Inspired Graph Neural Networks
• Learning Combinatorial Optimization on Graphs: A Survey with Applications to Networking
• Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learning
• POMO: Policy Optimization with Multiple Optima for Reinforcement Learning
• Deep Reinforcement Learning for Combinatorial Optimization: Covering Salesman Problems
• Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learning
• On Representation Knowledge Distillation for Graph Neural Networks
• The Transformer Network for the Traveling Salesman Problem
• Neural Airport Ground Handling
• Reinforcement Learning with Combinatorial Actions: An Application to Vehicle Routing
• Efficient Neural Neighborhood Search for Pickup and Delivery Problems
• NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problem
• Learning the Travelling Salesperson Problem Requires Rethinking Generalization
• One model Packs Thousands of Items with Recurrent Conditional Query Learning
• Efficient Active Search for Combinatorial Optimization Problems
• Neural Large Neighborhood Search for the Capacitated Vehicle Routing Problem
• Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformer
• What graph neural networks cannot learn: depth vs width
• An Expandable Machine Learning-Optimization Framework to Sequential Decision-Making
• Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances
• Building powerful and equivariant graph neural networks with structural message-passing
• On Learning Paradigms for the Travelling Salesman Problem
• Hybrid Pointer Networks for Traveling Salesman Problems Optimization
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs
• Matrix Encoding Networks for Neural Combinatorial Optimization
• Learning for routing: A guided review of recent developments and future directions
• Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs
• A State Aggregation Approach for Solving Knapsack Problem with Deep Reinforcement Learning
• Evaluating Curriculum Learning Strategies in Neural Combinatorial Optimization
• How to Evaluate Machine Learning Approaches for Combinatorial Optimization: Application to the Travelling Salesman Problem
• Graph Neural Network Guided Local Search for the Traveling Salesperson Problem
• From Local Structures to Size Generalization in Graph Neural Networks
• Message Passing Variational Autoregressive Network for Solving Intractable Ising Models
• Graph Learning for Combinatorial Optimization: A Survey of State-of-the-Art
• Generalization in Deep RL for TSP Problems via Equivariance and Local Search
• Learning to Optimise General TSP Instances
• A pipeline for fair comparison of graph neural networks in node classification tasks
• Boosting Column Generation with Graph Neural Networks for Joint Rider Trip Planning and Crew Shift Scheduling
• A step towards neural genome assembly
• Learning Vehicle Routing Problems using Policy Optimisation
• CPPNet: A Coverage Path Planning Network
• Reversible Action Design for Combinatorial Optimization with Reinforcement Learning
• Learning Combinatorial Node Labeling Algorithms
• Learning Enhanced Optimisation for Routing Problems
• QROSS: QUBO Relaxation Parameter Optimisation via Learning Solver Surrogates
• Fast Approximate Solutions using Reinforcement Learning for Dynamic Capacitated Vehicle Routing with Time Windows
• Experiments with graph convolutional networks for solving the vertex $p$-center problem