Traveling Salesperson Problem

Also known as TSP

Ask about this topic

Overview

The Traveling Salesperson Problem (TSP) asks for the shortest closed route through a set of cities, a difficult problem with practical links to logistics, manufacturing, and circuit design. Classical approaches include exact branch-and-cut and integer programming, alongside heuristics such as Lin–Kernighan search, genetic algorithms, ant colony optimization, and 2-opt local search. Neural methods use graph neural networks, reinforcement learning, diffusion models, and geometric symmetry to construct or improve tours, often tested on synthetic Euclidean instances and TSPLIB benchmarks. A central challenge is balancing solution quality, runtime, and scalability to very large instances while preserving reliable generalization and, where possible, guarantees of validity or optimality.

Latest papers

CardsList

38 papers5 papers in the last four weeks, against 2 the four weeks before. 0.0% of all new papers.

  1. The Optimal Sampler for Diverse TSP Solutions: Characterization, Limits, and Learning

    Oct 20, 2026Ssu-Yuan Lo, Ching-Kai Wang, Kuan-Lun Chen +1Traveling Salesperson ProblemCombinatorial Optimization

    National Central University, Department of Computer Science and Information Engineering, Taiwan

  2. Size Generalization for Diffusion Routing Solvers

    Oct 12, 2026Barak Itzchak Davidovitch, Eli Meirom, Ethan Fetaya +1Combinatorial OptimizationVehicle Routing

    Bar-Ilan University · NVIDIA

  3. EDISCO: Equivariant DIScrete Diffusion for Euclidean Combinatorial Optimization

    Oct 4, 2026Ruogu Chen, Jie HanCombinatorial OptimizationNeural Combinatorial Optimization

    Department of Electrical and Computer Engineering, University of Alberta, Edmonton, AB, Canada T6G 1H9

  4. Just Initialize: A Training-Free Initialization Component for Large-Scale Routing Optimization

    Sep 28, 2026Jiale Zhao, Sirui Mao, Zimu Chen +5Traveling Salesperson ProblemCombinatorial Optimization

    School of Automation Science and Electrical Engineering, Beihang University, Beijing, China · School of Computer Science and Engineering, Beihang University, Beijing, China · School of Cyber Science and Technology, Beihang University, Beijing, China +1

  5. Compute Time Scaling with Recursive Models for Combinatorial Optimization

    Sep 28, 2026Zhengxi Zhang, Paul SwobodaTraveling Salesperson ProblemInference-Time Scaling

  6. COMPASS: Ordered Clustered Routing at 100K Scale

    Sep 17, 2026Ido Greenberg, Hugo Linsenmaier, Piotr Sielski +4Traveling Salesperson ProblemCombinatorial Optimization

    NVIDIA

  7. LLM-Driven Joint Evolution of Coupled Heuristics Components for Routing Optimization

    Sep 2, 2026Juntao Wei, Yangming Zhou, Zhibin Jiang +1LLMs for Evolutionary OptimizationAutomated Heuristic Design

    Antai College of Economics and Management, Shanghai Jiao Tong University, Shanghai 200030, China · Global Institute of Future Technology, Shanghai Jiao Tong University, Shanghai 200240, China

  8. Unified Branch-and-Bound Search for the Steiner Traveling Salesman Problem on Graphs of Convex Sets

    Aug 21, 2026Jingtao Tang, Hang MaTraveling Salesperson ProblemBranch and Bound

    School of Computing Science, Simon Fraser University, Burnaby, BC V5A1S6, Canada

  9. Fine-Grain GPU Parallelization of the Generalized Partition Crossover for Large-Scale Traveling Salesman Problems

    Aug 21, 2026Swetha Varadarajan, Darrell WhitleyTraveling Salesperson ProblemGenetic Algorithms

    Seattle University, Seattle, WA, USA · Colorado State University, Fort Collins, CO, USA

  10. Insights from Multi-tasking the EAX Algorithm for the Travelling Salesperson Problem

    Aug 13, 2026Liam Wigney, Aneta Neumann, Yew-Soon Ong +1Traveling Salesperson ProblemEvolutionary Multitask Optimization

    Optimisation and Logistics · School of Computer Science and Information Technology · College of Computing & Data Science

  11. Enhanced Filtering Algorithms for the Euclidean Traveling Salesperson Problem and its variants in Constraint Logic Programming

    Aug 11, 2026Alessandro Bertagnon, Marco GavanelliTraveling Salesperson ProblemConstraint Propagation

    Department of Environmental and Prevention Sciences, University of Ferrara, Italy · Department of Engineering, University of Ferrara, Italy

  12. DualCert: A Solver for the Traveling Salesman Problem with Constraint-Coupled Learning

    Aug 10, 2026Yancheng Song, Yongzhi Qi, Wei Qi +1Traveling Salesperson ProblemPrimal-Dual Optimization

    Department of Industrial Engineering, Tsinghua University, Beijing 100084, China · JD.com, Beijing, China · College of Engineering, UC Berkeley, Berkeley, CA 94720, USA; Faculty of Engineering, Faculty of Business and Economics, University of Hong Kong, Hong Kong, China

  13. Stabilized Best-of-KK Training for Neural Combinatorial Optimization

    Jul 31, 2026Melveena Jolly, Midhun XavierTraveling Salesperson ProblemBest-of-N Sampling

    1Independent Researcher

  14. Geometric Self-Supervised Pre-training for Neural Combinatorial Optimization

    Jul 31, 2026David Aguado, Daniel Fuertes, Carlos R. del-Blanco +1Traveling Salesperson ProblemSelf-Supervised Learning

    Grupo de Tratamiento de Imágenes, Information Processing and Telecomunications Center, ETSI Telecomunicación, Universidad Politécnica de Madrid, 28040, Madrid, Spain

  15. Understanding Human-like Solutions in Combinatorial Optimization via Learning and Search

    Jul 26, 2026Haijiang Yan, Jian-Qiao Zhu, Liqiang Huang +1Traveling Salesperson ProblemInference-Time Search

    Department of Psychology, The University of Warwick, Coventry, United Kingdom. · Department of Psychology, The University of Hong Kong, Hong Kong, China. · Department of Psychology, The Chinese University of Hong Kong, Hong Kong, China. +2

  16. On the Effectiveness of Pretraining for Graph Combinatorial Optimization

    Jul 21, 2026David Aguado, Daniel Fuertes, Carlos R. del-Blanco +1Traveling Salesperson ProblemSelf-Supervised Pre-Training

    Grupo de Tratamiento de Imágenes, Information Processing and Telecomunications Center, ETSI Telecomunicación, Universidad Politécnica de Madrid, 28040, Madrid, Spain

  17. Graph Neural Network-based Algorithm Selection for the Traveling Salesman Problem: A Systematic Study of Cost and Rank Losses under Distinct Budget Regimes

    Jul 21, 2026Zhaoxuan Li, Jiale Yang, Yifei Lu +1Traveling Salesperson ProblemAlgorithm Selection

    Duke Kunshan University, 8 Duke Avenue, Kunshan, 215316, China

  18. Connected by Construction: Learning Tractable Near-Tour Marginals for Traveling Salesman Problems

    Jul 13, 2026Ke Sun, Xinyuan Zhang, Xinwu QianTraveling Salesperson ProblemCombinatorial Optimization

    Department of Civil and Environmental Engineering, Rice University, Houston, TX

  19. TSP with Predictions: Heatmap to Tour with Provable Guarantees

    Jul 4, 2026Marek Eliáš, Fabrizio Grandoni, Adam Polak +1Traveling Salesperson ProblemCombinatorial Optimization

  20. GES-TSP: Graph Edge Sparsification for TSP

    Jun 23, 2026Tianfeng Chen, Xianyue LiTraveling Salesperson ProblemGraph Structure Learning

    School of Mathematics and Statistics Lanzhou Universtiy

  21. GeoRouteNet: Geometry-Enhanced Non-Autoregressive Neural Solver for the Traveling Salesman Problem

    Jun 22, 2026Xiang LiTraveling Salesperson ProblemGraph Neural Networks

    College of Computer Science, Yangtze University, Jingzhou, China

  22. AGDN: Learning to Solve Traveling Salesman Problem with Anisotropic Graph Diffusion Network

    Jun 17, 2026Bolin Shen, Ziwei Huang, Zhiguang Cao +1Traveling Salesperson ProblemGraph Neural Networks

    Florida State University · Tallahassee, United States · Singapore Management University +1

  23. Two-Phase Bilevel Search for the Moving-Target Traveling Salesman Problem with Moving Obstacles

    Jun 17, 2026Allen George Philip, Anoop Bhat, Sivakumar Rathinam +1Traveling Salesperson ProblemCombinatorial Optimization

    Mechanical Engineering, Texas A&M University, College Station, TX 77843-3123 · Robotics Institute, Carnegie Mellon University, 5000 Forbes Ave., Pittsburgh, PA 15213, USA · Mechanical Engineering, and Computer Science and Engineering, Texas A&M University, College Station, TX 77843-3123

  24. Baseline-Free Policy Optimization for Neural Combinatorial Optimization

    Jun 9, 2026Carlos S. Sepúlveda, Gonzalo A. RuzTraveling Salesperson ProblemGroup Relative Policy Optimization

    Facultad de Ingeniería y Ciencias, Universidad Adolfo Ibáñez Millennium Nucleus for Social Data Science (SODAS) Millennium Nucleus in Data Science for Plant Resilience (PhytoLearning) Santiago, Chile

  25. Hybrid Metaheuristic Combining the Dragonfly Algorithm and Tabu Search for the Traveling Salesman Problem

    Jun 8, 2026Ammar BoukettaTraveling Salesperson ProblemMetaheuristic Optimization

    Ecole Nationale Superieure d’Informatique (ESI), Algiers, Algeria

  26. Leveraging Structural Constraints for Diffusion-based Neural TSP Solvers

    Jun 8, 2026Mickaël Basson, Philippe PreuxTraveling Salesperson ProblemInference-Time Optimization

    CRIStAL, Scool · Université de Lille, France · CNRS, France +2

  27. Beyond Static Priors: Dynamic Neural Guidance for Large-Scale Ant Colony Optimization

    Jun 2, 2026Dat Thanh Tran, Van Khu Vu, Yining MaTraveling Salesperson ProblemMetaheuristic Optimization

    Center for AI Research VinUniversity Hanoi, Vietnam · College of Engineering and Computer Science VinUniversity Hanoi, Vietnam · Laboratory for Information and Decision Systems Massachusetts Institute of Technology Cambridge, MA, USA

  28. MViewRouter: Internalizing Geometric Equivariance via Multi-view Alternating Attention for Combinatorial Routing

    May 31, 2026Shiyan Liu, Bohan Tan, Yaoxin Wu +1Traveling Salesperson ProblemMulti-View Learning

    Huazhong University of Science and Technology · Eindhoven University of Technology

  29. Scalable Solution of the Stochastic Multi-path Traveling Salesman Problem via Neural Networks

    May 14, 2026Xiaochen Chou, Ludovica Di Marco, Enza MessinaNeural Surrogate ModelingStochastic Optimization

    Department of Informatics, Systems and Communication, University of Milano-Bicocca, Viale Sarca 336, Milan, 20125, Italy.

  30. Machine Learning-based Two-Stage Graph Sparsification for the Travelling Salesman Problem

    Apr 22, 2026Bo-Cheng Lin, Yi Mei, Mengjie ZhangTraveling Salesperson ProblemGraph Sparsification

    Centre for Data Science and Artificial Intelligence, and the School of Engineering and Computer Science, Victoria University of Wellington, Wellington, 6140, New Zealand