mlsanityData to 14 Oct 2026

Diversity Optimization for Travelling Salesman Problem via Deep Reinforcement Learning

arXiv 2501.00884 ↗First posted 1 Jan 2025cs.LG cs.AIcited by 2

On the map: Deep reinforcement learning methods → RL for games and combinatorial optimization

Abstract (arXiv)

Existing neural methods for the Travelling Salesman Problem (TSP) mostly aim at finding a single optimal solution. To discover diverse yet high-quality solutions for Multi-Solution TSP (MSTSP), we propose a novel deep reinforcement learning based neural solver, which is primarily featured by an encoder-decoder structured policy. Concretely, on the one hand, a Relativization Filter (RF) is designed to enhance the robustness of the encoder to affine transformations of the instances, so as to potentially improve the quality of the found solutions. On the other hand, a Multi-Attentive Adaptive Active Search (MA3S) is tailored to allow the decoders to strike a balance between the optimality and diversity. Experimental evaluations on benchmark instances demonstrate the superiority of our method over recent neural baselines across different metrics, and its competitive performance against state-of-the-art traditional heuristics with significantly reduced computational time, ranging from 1.3× to 15× faster. Furthermore, we demonstrate that our method can also be applied to the Capacitated Vehicle Routing Problem (CVRP).

Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Placed in RL for games and combinatorial optimization, one of 15 directions in Deep reinforcement learning methods. Builds on 21 of its 40 references that are in the map. First posted on arXiv 1 Jan 2025.

Builds on

21 of 40 references.

References · 21

  1. 2017Attention Is All You Needcited by 60,361
  2. 2014Neural Machine Translation by Jointly Learning to Align and Translatecited by 4,548
  3. 2015Pointer Networkscited by 895
  4. 2018Attention, Learn to Solve Routing Problems!cited by 656
  5. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 623
  6. 2020POMO: Policy Optimization with Multiple Optima for Reinforcement Learningcited by 348
  7. 2019An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problemcited by 269
  8. 2024Reinforcement learningcited by 247
  9. 2020Reinforcement Learning for Combinatorial Optimization: A Surveycited by 236
  10. 2023Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalizationcited by 142
  11. 2022Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimizationcited by 119
  12. 2021Global Self-Attention as a Replacement for Graph Convolutioncited by 114
9 more
  1. 2020Multi-Decoder Attention Model with Embedding Glimpse for Solving Vehicle Routing Problemscited by 100
  2. 2021Learning Collaborative Policies to Solve NP-hard Routing Problemscited by 86
  3. 2022Simulation-guided Beam Search for Neural Combinatorial Optimizationcited by 84
  4. 2023Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Optcited by 81
  5. 2023Learning Large Neighborhood Search for Vehicle Routing in Airport Ground Handlingcited by 10
  6. 2016Compressing Graphs and Indexes with Recursive Graph Bisectioncited by 8
  7. 2022Learning to Solve Multiple-TSP with Time Window and Rejections via Deep Reinforcement Learningcited by 8
  8. 2020Balanced Order Batching with Task-Oriented Graph Clusteringcited by 1
  9. 2023Maximizing Neutrality in News Orderingcited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026Generating Diverse TSP Tours via a Combination of Graph Pointer Network and Dispersioncited by 0
  2. 2026WeCon: An Efficient Weight-Conditioned Neural Solver for Multi-Objective Combinatorial Optimization Problemscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025A Unified Deep Reinforcement Learning Approach for Close Enough Traveling Salesman Problem
  2. 2024Memory-Enhanced Neural Solvers for Routing Problems
  3. 2025ASAP: Exploiting the Satisficing Generalization Edge in Neural Combinatorial Optimization
  4. 2025An End-to-End Deep Reinforcement Learning Approach for Solving the Traveling Salesman Problem with Drones
  5. 2025Generative Modeling for Robust Deep Reinforcement Learning on the Traveling Salesman Problem
  6. 2026GeoRouteNet: A Geometry-Aware Non-Autoregressive Neural Solver for the Euclidean Traveling Salesman Problem
  7. 2025LocalEscaper: A Weakly-supervised Framework with Regional Reconstruction for Scalable Neural TSP Solvers
  8. 2025TuneNSearch: a hybrid transfer learning and local search approach for solving vehicle routing problems