Learning the Multiple Traveling Salesmen Problem with Permutation Invariant Pooling Networks

Abstract

While there are optimal TSP solvers, as well as recent learning-based approaches, the generalization of the TSP to the Multiple Traveling Salesmen Problem is much less studied. Here, we design a neural network solution that treats the salesmen, cities and depot as three different sets of varying cardinalities. We apply a novel technique that combines elements from recent architectures that were developed for sets, as well as elements from graph networks. Coupled with new constraint enforcing output layers, a dedicated loss, and a search method, our solution is shown to outperform all the meta-heuristics of the leading solver in the field.

References in corpus (2)

• Learning Combinatorial Optimization Algorithms over Graphs
• Reinforcement Learning for Solving the Vehicle Routing Problem

Cited by in corpus (11)

• Learning to schedule job-shop problems: Representation and policy learning using graph neural network and reinforcement learning
• An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem
• The Transformer Network for the Traveling Salesman Problem
• Learning Improvement Heuristics for Solving Routing Problems
• Neural Airport Ground Handling
• Neural Large Neighborhood Search for the Capacitated Vehicle Routing Problem
• ScheduleNet: Learn to solve multi-agent scheduling problems with reinforcement learning
• Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances
• Learning to Solve Vehicle Routing Problems with Time Windows through Joint Attention
• Evaluating Curriculum Learning Strategies in Neural Combinatorial Optimization
• Learning Combined Set Covering and Traveling Salesman Problem