Source-linked AI summary
The Optimal Sampler for Diverse TSP Solutions: Characterization, Limits, and Learning
Ssu-Yuan Lo, Ching-Kai Wang, Kuan-Lun Chen, Hao-Tsung Yang
TL;DR
D-TSP asks for multiple near-optimal tours that are as dissimilar as possible, a problem with difficult sampling and selection stages. The paper develops a sample-then-select framework with sampling guarantees and a spanning-tree-to-tour pipeline. Its learned sampler outperforms the reported baselines on both in-distribution and out-of-distribution instances, with scope limits on the theoretical guarantees.
Problem
Method
The paper separates sampling from max–min selection, analyzes optimal sampling distributions, and learns a sampler that can generate spanning trees for conversion into tours.
Source: §1 · p. 2, §8 · p. 22Results
The learned sampler beats existing methods both in distribution and on TSPLIB instances, without fine-tuning.
Source: §1 · p. 2, §8 · p. 22Takeaways & Limitations
The analysis gives an O(k)-sample guarantee for finding k mutually distant tours, with a weaker benchmark than the best k tours.
Source: §1 · p. 2, §8 · p. 22The factor-two hardness result applies to general metric spaces, so whether tour distances admit a better constant remains open.
Source: §4 · p. 7
Abstract
from arXiv · showhide
We address the Diverse Traveling Salesman Problem (D-TSP) that seeks a set of $k$ distinct TSP tours. Each selected tour must not exceed a prescribed multiple of the optimal tour length, while the maximum pairwise Jaccard similarity within the selected set is minimized. This formulation is important for applications requiring both solution quality and fault tolerance, such as logistics planning, robotics, and strategic patrolling. We propose a novel hybrid framework that decomposes D-TSP into a sampling stage and a selection stage. The selection stage is a max-min dispersion problem, for which any approximation better than a factor of two is NP-hard; we therefore focus on the sampling stage. Our contributions are both theoretical and empirical. Theoretically, we give two end-to-end guarantees for the optimal sampling distribution, from two perspectives: including an optimal set in the sampled pool, or having at least $k$ mutually distant tours in the pool. The second reduces the number of samples from exponential to linear in $k$, at the cost of weakening the benchmark from the best $k$ tours to the best $\beta k$ for some $\beta > 1$. For practical use, we prove that a pipeline that samples spanning trees and then converts to tours does not hurt the quality of the pool in principle. Empirically, both objectives are learnable, and our experiments not only validate the analysis but also outperform the baselines on both in-distribution and out-of-distribution instances, by a single trained model with no fine-tuning.
1 Introduction
D-TSP seeks a set of high-quality tours with low pairwise similarity, but scalable guarantees remain challenging because prior approaches address only parts of the problem. The paper separates sampling from selection and gives theoretical guarantees and empirical evidence for a learnable sampling approach.
1 Introduction
- D-TSP selects k distinct tours within a cost bound of the optimum while minimizing their maximum pairwise Jaccard similarity.The formulation targets high-quality, structurally dissimilar solutions.Source: §1 · p. 2
- Existing approaches leave open guaranteed approximation for D-TSP, while spanning-tree methods can lose diversity when converted to tours and budget constraint programming can limit scalability.Potential applications include fault-tolerant logistics and robotics route planning.Source: §1 · p. 2
- The paper decomposes D-TSP into sampling and selection, with a 2-approximation guarantee for uniform feasible-region sampling requiring a number of draws proportional to the exponential feasible-tour count.Its second guarantee uses O(k) expected draws to obtain k mutually distant tours, with a weaker benchmark; a spanning-tree-to-tour pipeline incurs no quality loss in principle.Source: §1 · p. 2
- The learned method beats three state-of-the-art methods on every tested in-distribution and out-of-distribution instance at its training budget.The out-of-distribution tests use TSPLIB instances with 51–101 cities.Source: §1 · p. 2
2 Related Work
Prior work on multiple TSP solutions includes traditional evolutionary heuristics and neural approaches. These methods face computational or inference costs, while neural methods also face transfer challenges across graph sizes and topologies.
Neural Approaches for Diverse TSP
- Distinct spanning trees with minimal overlap can produce the same tour under the double-tree heuristic, so tree dissimilarity need not survive conversion.Figure 1 illustrates the limitation of converting diverse spanning trees into tours.Source: Figure 1 · p. 3
Traditional Heuristics for MSTSP
- Traditional Multi-Solution TSP heuristics use evolutionary search to balance solution quality and diversity, but computation becomes costly as problems scale.NMA maintains niches of similar tours; EDO methods optimize diversity, often evolving from a known optimum.Source: §2 · p. 3
Neural Approaches for Diverse TSP
- Neural combinatorial-optimization methods offer fast GPU inference after training, but transferring policies across graph sizes and topologies remains challenging.Early neural TSP work focused on single-criterion optimization before moving toward multi-solution generation.Source: §2 · p. 3
- A prior neural solver for Diverse TSP adds filtering, temperature softmax, and active search, increasing architectural complexity and slowing inference for large instances.The cited approach is Li et al. [Li et al. 2025].Source: §2 · p. 4
3 Problem Definition
The paper defines D-TSP over edge-set tours in a cost-feasible region and measures diversity using Jaccard distance. Its max–min objective asks for k feasible tours whose minimum pairwise distance is as large as possible.
3 Problem Definition
- D-TSP seeks a set of tours that are near-optimal and structurally different from one another.The paper frames this as a multi-solution TSP problem.Source: §3 · p. 4
3.1 Tours and cost
- A TSP solution is a Hamiltonian cycle represented by its edge set, and its cost is the sum of its edge weights.The tour edge sets have equal cardinality, a property later used in the analysis.Source: §3.1 · pp. 4–5
3.2 Feasible region and distance
- The feasible region applies a hard cost filter, while Jaccard distance is used because it is a metric; related Dice–Sørensen and cosine dissimilarities lack the triangle inequality.The paper notes that the distance is coarse: distinct tours have distance at least 4/(n+2), attained by pairs differing in two edges.Source: §3.2 · pp. 5–6
3.3 The Diverse TSP
- D-TSP maximizes the minimum pairwise distance among k tours in the feasible region, equivalently minimizing their largest pairwise Jaccard similarity.The paper also relates the objective to max–min Hamming diversity because both measures order tour pairs by overlap in the same way.Source: §3.3 · p. 6
4 Sampling and Selection
The section separates D-TSP into sampling feasible tours and selecting a diverse subset, then studies which sampling distributions provide useful pools. It gives guarantees for hitting an optimal set and a matching lower bound, followed by an end-to-end guarantee.
4 Sampling and Selection
- The selection stage is greedy max-min dispersion on the sampled pool, with a factor-2 guarantee in metric spaces; whether tour distances admit a better constant remains open.The cited hardness result concerns general metric spaces, not specifically the family of tour distances.Source: §4 · p. 7
4.1 Hitting an optimal set
- With M ≥ ln(k/δ)/q independent draws, the pool contains a fixed optimal set with probability at least 1 − δ, enabling the selection guarantee.Here q is the minimum sampler mass on a tour in that optimal set.Source: §4.1 · p. 7
- Uniform sampling is worst-case optimal for hitting an unknown optimal set, while a flat feasible-region reward makes the learned Gibbs sampler uniform there for every α > 0.The hinge reward is flat on Ω_c, so its non-uniformity factor Δ equals 1.Source: §4.1 · pp. 7–8
4.2 A matching lower bound
- The lower-bound construction tunes a cell-traversal cost gap while holding other lengths fixed, leaving exactly g + 1 feasible tours at the chosen tolerance.These are the all-cheap tour and g tours that deviate in one cell each.Source: §4.2 · p. 9
- A Euclidean family with 4g cities makes the sampling penalty real: uniform sampling recovers the unique optimum with M ≥ (g + 1) ln(g/δ), while a non-uniform sampler may need more than (g + 1)Δ(μ)/2 draws.In this construction, choosing any g tours other than the unique optimum incurs a dispersion factor tending to 1/2.Source: §4.2 · pp. 9–10
4.3 The end-to-end guarantee
- The end-to-end guarantee composes the optimal-set sampling lemma with the selection theorem; for uniform sampling, M ≥ N_c ln(k/δ) suffices uniformly over target sets.The proof also sharpens the similarity-scale guarantee using the equal-cardinality property, without additional algorithmic cost.Source: §4.3 · p. 10
5 Sampling Trees and Converting Them to Tours
The framework generates spanning trees rather than tours, then converts them into tours for filtering and selection. The sequence-to-tree step preserves uniformity at the objective optimum, but the tree-to-tour step can distort tour probabilities even though the architecture can represent any feasible-tour distribution.
5.1 Generating trees and converting them
- A tree policy adds edges sequentially without closing cycles; tours come from either a depth-first traversal or a learned matching on odd-degree vertices followed by Euler-circuit shortcutting.Both conversion methods are randomized in general.Source: §5.1 · p. 11
5.2 Training objective
- The training objective uses the mean tour cost over L conversion runs with a hinge reward flat for trees meeting the budget on average, and a summed entropy term scaled by the temperature.The summed entropy makes its coefficient match the temperature used in the analysis.Source: §5.2 · p. 12
5.3 (Un-)biased sampling from sequences to trees to tours
- At the objective maximizer, the sequence entropy term yields uniform sampling over spanning trees because every tree has the same number of admissible edge orderings.That equal multiplicity is what cancels in the induced tree distribution.Source: §5.3 · p. 13
- The uniform-tree result applies to the objective maximizer; parametric approximation and nonuniform edge-sequence probabilities within a tree remain separate sources of error.The constant number of edge orderings per tree does not measure the latter error.Source: §5.3 · p. 13
- The tree representation can express any distribution over feasible tours under either conversion method, but pushing a tree distribution through the conversion need not preserve tour weights.Each feasible tour corresponds to two trees in a construction that realizes its target probability exactly.Source: §5.3 · p. 13
- The induced tour weights vary with how many trees can produce each tour, so the resulting nonuniformity can make the sampling factor exceed one.A duplicate-tour penalty is proposed as a heuristic, but it does not cancel this ratio.Source: §5.3 · p. 14
6 The Conflict Graph
The conflict-graph view replaces the demand to sample a particular optimal set with a demand for enough mutually distant tours in the pool. This supports a linear-in-k sample guarantee at the cost of benchmarking against the best 4k tours rather than the best k.
6.1 The independent set v.s. D-TSP
- A pool has dispersion at least rho exactly when its conflict graph contains an independent set of at least k tours, so maximizing the threshold recasts D-TSP as finding separated tours.The sampled-pool guarantee follows by translating its independence number back into dispersion.Source: §6.1 · pp. 14–15
6.2 Analysis on 𝜌
- With 4k samples, the guarantee retains the factor-two dispersion approximation but benchmarks against the best 4k feasible tours, rather than the best k.The stated condition includes ln(1/δ) ≤ k/2.Source: §6.2 · pp. 15–16
- The minimum collision rate is attained by a uniform sampler on a maximum independent set, and finding that minimum is NP-hard.The collision rate therefore provides a sampler-quality target, but not an easy exact optimization.Source: §6.2 · p. 16
6.3 The learning objective
- The learning objective replaces the entropy bonus with a collision-rate term within the feasible region, while the hinge filters infeasible tours.Its learned threshold tracks the current policy's 1/k distance quantile, not the optimal k-tour dispersion; lowering collision rate improves the stated bound.Source: §6.3 · pp. 16–17
7 Experiments
The experiments validate the predicted role of collision rates and sample-size saturation, then compare one trained sampler with traditional and neural baselines. It performs strongly in-distribution and on TSPLIB without fine-tuning, though larger instances need wider budgets for enough tours to pass the cost filter.
7.1 Setup
- One sampler was trained once on random 40-city instances and evaluated on random instances and TSPLIB instances with 51–101 cities, without adaptation.The evaluation used pools of 1,000 tours, cost filtering, and selection; results were medians over three seeds.Source: §7.1 · pp. 17–18
7.2 Validating the theoretical analysis
- Across samplers, 250 samples reached 90% of the full-pool best dispersion, and dispersion later saturated as additional draws stopped helping.At k=80, most curves flattened between 500 and 2,000 samples; this ceiling is attributed to the distribution rather than the draw count.Source: §7.2 · pp. 19–20, Figure 4 · p. 19
- Lower collision rates tracked higher dispersion across all seven samplers, with rank correlation around −0.99 (n=6, p<0.001).This relation held across thresholds where all samplers had positive collision rates.Source: Figure 5 · p. 20, §7.2 · p. 20
7.3 Comparison with existing methods
- On random 40-city instances, the sampler beat all three baselines on every instance at c=2.0 and c=2.5, and on 18/20 instances against Bi-Criteria at c=4.0.At c=3.0 it tied Bi-Criteria at the median and won outright on five instances.Source: §7.3 · p. 20, Table 3 · p. 21
- At c=4.0, the sampler raised median D(Π) from 0.844 (Bi-Criteria) to 0.931 and reduced maximum pairwise Jaccard index from 0.156 to 0.069, a factor of 2.17.It beat all three baselines on all 13 TSPLIB instances using the same checkpoint without fine-tuning.Source: Table 4 · p. 21, §7.3 · p. 21
- Among 26 feasible-tour comparisons across budgets, the sampler won 25 and tied once, but returned k feasible tours on only 1/13 instances at c=2.0 versus 13/13 at c=4.0.Acceptance fell with instance size, reaching zero for n≥70 at the tightest budget; the authors identify larger instances as requiring a wider budget or retraining.Source: §7.3 · pp. 21–22, Table 5 · p. 22, Table 6 · p. 22
8 Conclusion
The paper frames D-TSP as a sample-then-select problem and focuses its guarantees on sampling. It reports that a single sampler can outperform existing methods in-distribution and on TSPLIB without fine-tuning, when the evaluation budget matches training.
8 Conclusion
- The paper locates D-TSP’s difficulty in sampling and studies it through a sample-then-select framework.It gives end-to-end guarantees for the optimal sampling distribution, including a linear-in-k sample bound with a weaker benchmark, and analyzes sampling spanning trees before converting them to tours.Source: §8 · p. 22
- The authors report that one sampler, trained once and used without fine-tuning, beats existing methods in-distribution and on TSPLIB when the evaluation budget matches training.The paper also states that learning the diverse spanning trees and converting them to tours does not hurt pool quality in principle.Source: §8 · p. 22
A Uniform sampling of tours
The appendix argues that rejection sampling cannot produce a uniform sampler over the feasible tours on large random Euclidean instances. A uniformly random tour is typically too costly relative to the optimum, so its probability of meeting a fixed-factor cost budget decays exponentially.
A Uniform sampling of tours
- A uniformly random ordering of n random points has expected tour cost approximately 0.5214n, while the optimal tour grows as β√n with β≈0.7124.The expected-cost ratio grows like 0.73√n, eventually exceeding 2c for any fixed c.Source: A Uniform sampling of tours · p. 25
- For sufficiently large n, the probability that a uniformly random tour meets the c-budget is at most e^-Θ(n), with probability over the point set tending to one.The proof uses bounded differences for uniform permutations because tour-cost coordinates are dependent; swapping two positions changes at most four edges.Source: A Uniform sampling of tours · p. 25
B The lower-bound instance
A constructed family of tours yields a small feasible region whose best mutually distant set can be much better than other selections. The same instance also shows how a sampler can miss a needed tour, including under rewards that favor the cheap tour.
B The lower-bound instance
- The instance uses n = 4g points arranged from g cells, and a tour of the illustrated shape has three internal edges per cell plus g connecting edges.The authors exhaustively checked both stated laws for g = 3 on 12 points at three offsets; the structure margin increased from 32 to 632 across that range.Source: B The lower-bound instance · p. 25
- For sufficiently small offset ϑ, every tour within C* + gη visits the cells in ring order and uses one of two traversals per cell.At ϑ = 0, structured tours have equal cost and unstructured tours cost at least σ more; 2ϑ < σ preserves the structure.Source: B The lower-bound instance · p. 25
- For k = g, the g expensive tours are pairwise at distance 2/(g + 1), while each is 2/(2g + 1) from the cheap tour; choosing any other g feasible tours gives the latter dispersion.The optimal set consists of all g expensive tours.Source: B The lower-bound instance · p. 26
- If M ≤ (g + 1)Δ(μ)/2, the probability of missing a least-mass expensive tour is at least 1/2; the resulting pool cannot return the optimal g-tour set.The pool is contained in the cheap tour and the other g − 1 expensive tours, or has too few distinct tours to return g.Source: B The lower-bound instance · p. 26
- When the reward gap is Γ > 0, the Gibbs sampler assigns unnormalized weight e^(Γ/α) to the cheap tour and weight 1 to each expensive tour, placing its smallest mass on an expensive tour.Source: B The lower-bound instance · p. 26
- Any reward that strictly prefers the cheap tour meets the theorem’s second-clause hypothesis at every temperature.Source: B The lower-bound instance · p. 26
C Network architecture
The network encodes vertex and edge context, then decodes a tour sequentially with masked edge choices. The architecture follows Ma et al. [2019] and is included for completeness, not claimed as a contribution.
C Network architecture
- The encoder embeds vertex coordinates and updates them through ℓ residual message-passing layers, then combines final vertex embeddings with initial edge embeddings.A trainable aggregation function and coefficient balance each vertex’s prior representation with its aggregated neighborhood.Source: C Network architecture · p. 26
- An LSTM reads the previously selected edge embedding and emits a query vector for the next decoding step.Source: C Network architecture · p. 26
- The decoder scores edges, masks inadmissible choices, and applies softmax; the selected edge embedding feeds the next step, while the matching policy uses the same network with an unmatched-endpoint mask.The architecture follows Ma et al. [2019] and is shown for completeness.Source: C Network architecture · p. 26