Traveling Salesperson Problem

Also known as TSP

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

39 papers2 papers in the last four weeks, down 50% on the four weeks before. 0.0% of all new papers.

  1. PISG: Constraint-Aligned Signal Amplification for Diffusion-Based Combinatorial Optimization

    Nov 15, 2026Yuming Zhang, Xianchen Zhou, Hongxia WangCombinatorial OptimizationNeural Combinatorial Optimization

  2. 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

  3. Size Generalization for Diffusion Routing Solvers

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

  4. EDISCO: Equivariant DIScrete Diffusion for Euclidean Combinatorial Optimization

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

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

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

  6. COMPASS: Ordered Clustered Routing at 100K Scale

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

  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

  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

  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

  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

  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

  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

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

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

  14. 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

  15. 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

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

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

  17. GES-TSP: Graph Edge Sparsification for TSP

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

  18. 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

  19. 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

  20. Baseline-Free Policy Optimization for Neural Combinatorial Optimization

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

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

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

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

    Jun 2, 2026Dat Thanh Tran, Van Khu Vu, Yining MaTraveling Salesperson Problemant colony optimization

  23. 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

  24. 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