PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning the Multiple Traveling Salesmen Problem with Permutation Invariant Pooling Networks

Yoav Kaempfer, Lior Wolf

arXiv:1803.09621v2cs.LGstat.ML

TL;DR

The mTSP, a less-studied generalization of the TSP, requires multiple constrained routes rather than one sequence. This paper uses a permutation-invariant network for cities, salesmen, and the depot, with constraint-aware outputs and search; it reports outperforming leading mTSP solver methods across most experiments.

  • Problem

    The mTSP is less studied than the TSP and requires a set of variable-length routes with structural constraints rather than a single sequence.

    Source: §1 · pp. 1–2

  • Method

    The method encodes cities, the depot, and salesmen as separate sets in a permutation-invariant network, with soft constraint enforcement and a search procedure.

    Source: §1 · p. 2, §4.2 · p. 8, §4.2.1 · p. 10

  • Results

    The authors report that their method outperforms combinations of methods in the leading mTSP solver and wins most experiments, including when the best baseline is selected separately for each experiment.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The approach uses generic input and output encodings, with problem-specific information introduced only in Algorithm 1; the authors report that more than one iteration is needed to compete with sophisticated OR-Tools heuristics.

    Source: §6 · p. 19

    The work focuses on the single-depot mTSP; minmax, vehicle-routing, and time-constrained variants remain future work and require changes to training examples, the algorithm, or city encodings.

    Source: §6 · p. 19

Abstract

from arXiv · show

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.

1. Introduction

The mTSP generalizes the TSP to multiple salesmen and has received relatively little research despite its broader real-world applications. Learning combinatorial problems requires architectures that handle structured inputs and enforce complex output constraints; this paper proposes a set-based, permutation-invariant network for the mTSP.

1. Introduction

  • Learning combinatorial problems is difficult because training data can require solving the problem, inputs may be unordered, and feasible outputs have complex constraints.These challenges motivate architectures that represent input invariances and enforce output constraints.Source: §1 · p. 1
  • The mTSP assigns routes to multiple salesmen from and back to a depot, minimizing total distance while each city is visited exactly once; it has received less study than the TSP despite broader applications.The cited applications include satellite surveying and interview scheduling.Source: §1 · p. 2
  • Unlike the TSP’s fixed sequence, the mTSP requires a set of variable-length sequences with structural constraints between routes.The passage notes that sequence-generation approaches have had some success on the TSP, while the mTSP adds complexity.Source: §1 · p. 2
  • The proposed network represents cities, the depot, and salesmen as three sets and combines permutation invariance, spatial weighting, and soft constraint enforcement.A dedicated loss and search method accompany the architecture.Source: §1 · p. 2

2. Related Work

The paper adapts permutation-invariant set architectures and graph-network ideas to the mTSP, whose multi-route output is not naturally handled by sequence-to-sequence models. It situates this approach among TSP and mTSP solvers, including neural methods and OR-Tools heuristics.

2. Related Work

  • Set architectures use pooling for permutation-invariant representations followed by local computation, while this network extends the approach to multiple sets and integrates graph structure through learned distance-based local weights.The paper relates this design to graph-convolutions, which propagate information using graph metrics.Source: §2 · pp. 2–3

2.1 TSP solvers

  • A concatenation of salesman routes does not directly expose mTSP constraints, and sequence-to-sequence models are not permutation invariant; the authors report that initial attempts with this approach failed.Prior neural TSP work included Pointer Networks, LSTM/convolutional models, reinforcement learning, and graph representations.Source: §2.1 · p. 3

2.2 mTSP solvers

  • The authors found weighted max-pooling more effective than attention-based pooling and report that their supervised approach outperforms the leading mTSP solver while remaining competitive on TSP.Prior mTSP methods include OR-Tools local search with meta-heuristics and earlier neural approaches, some of which optimized per sample without training.Source: §2.1 · p. 4, §2.2 · p. 4
  • Concurrent vehicle-routing approaches used attention-based encoder-decoders trained with reinforcement learning and output concatenated sequences, unlike this paper’s sparse output.The cited variants include capacitated routing and split delivery.Source: §2.2 · pp. 4–5

3. Problem Formulation

The paper formulates the single-depot mTSP as minimizing the total distance traveled by multiple salesmen, with every non-depot city visited exactly once and all routes returning to the depot. It focuses on the two-dimensional Euclidean variant and notes that small instances can be solved with integer linear programming.

3. Problem Formulation

  • In the single-depot mTSP, all salesmen start and end at city 1, and each other city is visited exactly once by one salesman; the objective is to minimize total traveled distance.The formulation uses δ_i,j,k to indicate whether salesman k travels from city i to city j.Source: §3 · p. 5
  • The formulation’s constraints require each salesman to leave and return to the depot once, each non-depot city to be entered and exited once overall, and each salesman’s visits to be balanced by departures.The constraints are described as redundant.Source: §3 · p. 5
  • The study addresses the two-dimensional Euclidean mTSP, which the paper identifies as NP-hard; small instances can be solved using ILP solvers.The paper states that no efficient algorithm is currently known for this variant.Source: §3 · p. 6

4. Method

The method builds a permutation-invariant network for variable-sized groups, then adds constraint-enforcing output processing, search, and a representation-invariant loss for mTSP solutions.

4.1 Permutation Invariant Pooling Network

  • Each pooling block forms per-element contexts from groups of variable length while excluding the element itself; learned distance weights add spatial information to the pooled context.The network uses permutation-invariant pooling within each group, and its weighted variant uses a learned function of pairwise distance.Source: §4.1 · pp. 6–7

4.2 Learning the Multiple Traveling Salesmen Problem

  • The mTSP network encodes salesmen, the depot, and other cities as separate groups, then scores each salesman-city-to-city path in an adjacency tensor.It embeds the cities using the inter-city distance matrix and represents each salesman with local and global information.Source: §4.2 · pp. 8–9

4.2.1 Adhering to the mTSP Constraints

  • Softassign alternates constraint-enforcing steps to produce a soft multi-stochastic tensor, while beam search expands and prunes partial routes to return a valid solution.Each iteration satisfies two constraints and may violate the other two; the authors report empirical convergence to a tensor satisfying all four.Source: §4.2.1 · pp. 9–10

4.2.2 Representation Invariant Loss

  • The representation-invariant loss minimizes negative log-likelihood over targets covering salesman permutations and route directions, with an equivalent computation that avoids matrix multiplications.Its loss computation needs O((m + 1)!) simple operations; inference remains polynomial because the loss is used only during training.Source: §4.2.2 · p. 11

5. Experiments

Experiments evaluate the network on generated mTSP data, larger mTSPLib instances, and TSP benchmarks, against OR-Tools methods and a neural baseline. The authors report competitive results across these settings, with spatial weighting and Leave-One-Out pooling important for mTSPLib generalization.

5.1 Datasets

  • The evaluation uses about 7.3 million generated instances with 1–5 salesmen and up to 20 cities, plus 16 larger mTSPLib cases and TSP5, TSP10, and TSP20 benchmarks.The mTSPLib cases are intended to test generalization to larger problems and to instances created by a different process.Source: §5.1 · p. 12

5.1.1 Operations Research Baselines

  • OR-Tools comparisons use OR@25, the best of 25 strategy–metaheuristic combinations per sample, and ORmin, the best combination chosen per experiment.The OR-Tools routing module uses an initial-solution strategy followed by local-search metaheuristics; some TSP-specific strategies did not work on mTSP instances.Source: §5.1.1 · pp. 12–13

5.1.2 The Neural Network Baseline

  • The neural baseline extends Levy and Wolf (2017) with a salesman dimension, LSTM encodings, a 3D CNN, and the paper’s decoding pipeline and custom loss.Positional encoding performed better than the authors’ encoding for salesmen in this baseline.Source: §5.1.2 · p. 13

5.1.3 Our Network

  • For mTSPLib, the network serves as an OR-Tools first strategy, with 10% of the beam budget assigned to beam search and the remainder to Guided Local Search.The reported network uses max pooling and learned spatial weighting; the distance matrix is divided by its mean before the SVD approximation to maintain scale invariance.Source: §5.1.3 · p. 14

5.1.6 Results

  • On mTSP-test, the method outperforms both the neural baseline and the best OR-Tools method selected for each beam size.The representation-invariant loss contributes significantly; with naïve negative log likelihood, predictions can average optimal routes and their reversals, producing a local minimum.Source: Table 1 · p. 14, §5.1.6 · pp. 16–17, Figure 3 · p. 17

5.1.5 Training

  • The paper trains all neural networks on mTSP-train with Adam, using batch size 32 and learning rate 0.001 for the neural baseline versus batch size 128 and learning rate 0.0001 for its networks.For networks not invariant to city order and tour direction, city order is randomly permuted during training.Source: §5.1.5 · p. 16

5.1.4 Ablation Study

  • On mTSPLib, spatial weighting and Leave-One-Out pooling are crucial for competitiveness at larger beam sizes, although removing either causes only small degradation on mTSP-test.The ablation study removes each of the representation-invariant loss, weighted pooling layers, and Leave-One-Out pooling in turn.Source: §5.1.4 · p. 14, §5.1.6 · p. 17

5.1.6 Results

  • On mTSPLib, the pipeline has marginally lower average error at smaller beam sizes and remains the best alternative among individual OR-Tools methods as beam size grows.The reported comparison also finds that, at relatively small beam sizes, the pipeline more often than not outperforms the best OR-Tools method for each experiment.Source: Table 3 · p. 15, §5.1.6 · p. 18, Figure 5 · p. 19

6. Discussion

The discussion presents a broadly encoded approach with problem-specific information concentrated in Alg. 1. It also identifies representation choices and unaddressed mTSP variants as open boundaries.

6. Discussion

  • The input encoding is generic and the output directly represents the solution, with problem-specific information concentrated in Alg. 1.The network can train with one algorithm iteration, but more iterations are needed to compete with OR-Tools heuristics.Source: §6 · p. 19
  • The method uses sparse, overparameterized outputs rather than an economical sequence representation.Whether sequence generation can model combinatorial problems whose output space exceeds a single permutation remains unresolved.Source: §6 · p. 19
  • The minmax variant and VRP remain future work; addressing VRP would require modifying training samples and Alg. 1 to normalize by maximal capacity.Time constraints pose a separate challenge because they must be added to individual city encodings.Source: §6 · p. 19

Related papers

Loading 1803.09621v2…