# Generating Diverse TSP Tours via a Combination of Graph Pointer Network and Dispersion

arXiv: https://arxiv.org/abs/2601.01132 · HTML: https://mlsanity.com/paper/2601.01132/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 37 references that are in the map.
- First posted on arXiv 3 Jan 2026.

## Builds on (most cited first, 20 of 20)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Explaining Machine Learning Classifiers through Diverse Counterfactual Explanations](https://mlsanity.com/paper/1905.07697/) (2019)
- [Improving Adversarial Robustness via Promoting Ensemble Diversity](https://mlsanity.com/paper/1901.08846/) (2019)
- [Multi-Decoder Attention Model with Embedding Glimpse for Solving Vehicle Routing Problems](https://mlsanity.com/paper/2012.10638/) (2020)
- [Efficient Active Search for Combinatorial Optimization Problems](https://mlsanity.com/paper/2106.05126/) (2021)
- [Learning Collaborative Policies to Solve NP-hard Routing Problems](https://mlsanity.com/paper/2110.13987/) (2021)
- [Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learning](https://mlsanity.com/paper/1911.04936/) (2019)
- [Learning to Solve Routing Problems via Distributionally Robust Optimization](https://mlsanity.com/paper/2202.07241/) (2022)
- [Graph Pointer Neural Networks](https://mlsanity.com/paper/2110.00973/) (2021)
- [Systemizing Multiplicity: The Curious Case of Arbitrariness in Machine Learning](https://mlsanity.com/paper/2501.14959/) (2025)
- [Quality-Diversity Algorithms Can Provably Be Helpful for Optimization](https://mlsanity.com/paper/2401.10539/) (2024)
- [Feasible Recourse Plan via Diverse Interpolation](https://mlsanity.com/paper/2302.11213/) (2023)
- [Obtaining Approximately Optimal and Diverse Solutions via Dispersion](https://mlsanity.com/paper/2202.10028/) (2022)
- [Diversity Optimization for Travelling Salesman Problem via Deep Reinforcement Learning](https://mlsanity.com/paper/2501.00884/) (2025)
- [Niching-based Evolutionary Diversity Optimization for the Traveling Salesperson Problem](https://mlsanity.com/paper/2201.10316/) (2022)
- [Finding Diverse Minimum s-t Cuts](https://mlsanity.com/paper/2303.07290/) (2023)
- [Pareto Optimal Algorithmic Recourse in Multi-cost Function](https://mlsanity.com/paper/2502.07214/) (2025)
- [Parameterized Complexity of Directed Traveling Salesman Problem](https://mlsanity.com/paper/2506.22127/) (2025)

## Abstract (arXiv)

We address the Diverse Traveling Salesman Problem (D-TSP), a bi-criteria optimization challenge that seeks a set of k distinct TSP tours. The objective requires every selected tour to have a length at most c|T^*| (where |T^*| is the optimal tour length) while minimizing the average Jaccard similarity across all tour pairs. This formulation is crucial for applications requiring both high solution quality and fault tolerance, such as logistics planning, robotics pathfinding or strategic patrolling. Current methods are limited: traditional heuristics, such as the Niching Memetic Algorithm (NMA) or bi-criteria optimization, incur high computational complexity O(n3), while modern neural approaches (e.g., RF-MA3S) achieve limited diversity quality and rely on complex, external mechanisms. To overcome these limitations, we propose a novel hybrid framework that decomposes D-TSP into two efficient steps. First, we utilize a simple Graph Pointer Network (GPN), augmented with an approximated sequence entropy loss, to efficiently sample a large, diverse pool of high-quality tours. This simple modification effectively controls the quality-diversity trade-off without complex external mechanisms. Second, we apply a greedy algorithm that yields a 2-approximation for the dispersion problem to select the final k maximally diverse tours from the generated pool. Our results demonstrate state-of-the-art performance. On the Berlin instance, our model achieves an average Jaccard index of 0.015, significantly outperforming NMA (0.081) and RF-MA3S. By leveraging GPU acceleration, our GPN structure achieves a near-linear empirical runtime growth of O(n). While maintaining solution diversity comparable to complex bi-criteria algorithms, our approach is over 360 times faster on large-scale instances (783 cities), delivering high-quality TSP solutions with unprecedented efficiency and simplicity.