A First Guess is Rarely the Final Answer: Learning to Search in the Traveling Salesperson Problem

Andoni Irazusta Garmendia

cs.LGApr 8, 2026

A First Guess is Rarely the Final Answer: Learning to Search in the Traveling Salesperson Problem

Authors: Andoni Irazusta Garmendia

Organizations: University of the Basque Country (UPV/EHU)

Abstract

Most neural solvers for the Traveling Salesperson Problem (TSP) are trained to output a single solution, even though practitioners rarely stop there: at test time, they routinely spend extra compute on sampling or post-hoc search. This raises a natural question: can the search procedure itself be learned? Neural improvement methods take this perspective by learning a policy that applies local modifications to a candidate solution, accumulating gains over an improvement trajectory. Yet learned improvement for TSP remains comparatively immature, with existing methods still falling short of robust, scalable performance. We argue that a key reason is design mismatch: many approaches reuse state representations, architectural choices, and training recipes inherited from single-solution methods, rather than being built around the mechanics of local search. This mismatch motivates NICO-TSP (Neural Improvement for Combinatorial Optimization): a 2-opt improvement framework for TSP. NICO-TSP represents the current tour with exactly $n$ edge tokens aligned with the neighborhood operator, scores 2-opt moves directly without tour positional encodings, and trains via a two-stage procedure: imitation learning to short-horizon optimal trajectories, followed by critic-free group-based reinforcement learning over longer rollouts. Under compute-matched evaluations that measure improvement as a function of both search steps and wall-clock time, NICO-TSP delivers consistently stronger and markedly more step-efficient improvement than prior learned and heuristic search baselines, generalizes far more reliably to larger out-of-distribution instances, and serves both as a competitive replacement for classical local search and as a powerful test-time refinement module for constructive solvers.

Figures & tables

Figure 1: Overview of the edge-based representation and policy architecture. Tours are represented as sequences of edge tokens, each encoding endpoint coordinates and local geometric features. These edge tokens are processed by an edge-attention encoder with local cycle mixing and global context fusion, producing contextualized edge representations. A pairwise decoder then scores all feasible 2-opt moves.

Figure 2: Overview of the proposed two-stage learning framework. An imitation learning stage uses optimal short-horizon trajectories, followed by a group-based reinforcement learning stage that refines the policy through instance-wise competition in longer horizons.

	Uniform Euclidean TSP						TSPLIB-gen
Method	$\mathbf{n=50}$		$\mathbf{n=100}$		$\mathbf{n=500}$		$\mathbf{n=100}$
	Cost $\downarrow$	Time (s) $\downarrow$	Cost $\downarrow$	Time (s) $\downarrow$	Cost $\downarrow$	Time (s) $\downarrow$	Cost $\downarrow$	Time (s) $\downarrow$
Optimum	5.6705		7.7352		16.5396		5.6911
2opt Local Search	5.9466	3.39	8.3318	6.43	18.2049	37.53	6.0862	6.81
3opt Local Search	5.8338	6.54	8.0875	12.37	17.5621	3766.41	5.9126	10.97
Tabu Search	5.9474	14.65	8.2621	31.31	17.9746	307.94	6.0668	31.40

Table 1: Best tour cost and inference time. Single-run search methods use a budget of

10n

improvement steps, while

(\times 8)

and

(\times 32)

denote independent-restart variants with 8 and 32 runs, respectively. Constructive methods use a single forward pass unless otherwise stated. Bold indicates the best cost and fastest time among single-run learned improvement methods.

Panel of Figure 3 — Figure 3: Anytime performance from random initial tours. Average optimality gap to the Concorde optimum is reported as a function of improvement steps for uniform Euclidean TSP instances with $n=20$ (left), $n=100$ (center), and $n=500$ (right).

Panel of Figure 4 — Figure 4: Improvement from strong initial solutions. Average optimality gap as a function of execution time for $n=20$ (left), $n=100$ (center), and $n=500$ (right).

Figure 5: Ablation study. Each row adds one component. Bars show optimality (%).

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Setting	Mean	Std. train ( $5$ )	Std. infer ( $20$ )
unif50	$5.6708$	$0.00268$	$0.000834$
unif100	$7.7420$	$0.00576$	$0.004561$
unif500	$17.0113$	$0.14324$	$0.059026$
tsplib100	$5.7036$	$0.00109$	$0.003047$

Appendix

Table 2: Variability across training and inference randomness on the main evaluation settings from Section 4.2 . We report the mean final best cost, together with the standard deviation across 5 independently trained checkpoints and across 20 inference runs from a fixed checkpoint.

Component	Variant	Best Cost
Stabilization stack	Base RL model	9.235
	+ AdamW	9.129
	+ 8 heads	8.951
	+ RMSNorm	8.930
	+ Mean pooling	8.876
History mechanism	No history (Base + Stabilization stack)	8.876

Appendix

Table 3: Additional disentangled ablations of the final method. Results are reported on the main validation setting using the same evaluation protocol as in the main text on 100 uniform instances with

\mathbf{n=100}

. The default configuration used in the final model is highlighted in bold.

Factor	Setting	Best cost	Relative training cost
Group size $G$	$G=5$	7.747	0.629 $\times$
	$G=10$	7.744	0.843 $\times$
	$\mathbf{G=20}$	7.742	1.000 $\times$
	$G=40$	7.742	1.846 $\times$
Rollout horizon $T$	$T=1$	7.856	0.179 $\times$
	$T=2$	7.778	0.194 $\times$

Appendix

Table 4: Sensitivity of the RL stage to its main design choices. We report final best costs on 100 uniform instances with

n=100

. We also report the relative training cost under a fixed number of parameter-update steps. The default configuration used in the final model is highlighted in bold.

Traveling Salesperson Problem

The Traveling Salesperson Problem studies algorithms for finding shortest tours that visit every city exactly once.

See all 38 papers

Jun 8, 2026

Leveraging Structural Constraints for Diffusion-based Neural TSP Solvers

Neural combinatorial optimization has recently achieved strong results on the Euclidean Traveling Salesman Problem (TSP) using generative models such as diffusion and consistency models. State-ofthe-art approaches like FT2T combine fast consistency-based prediction with gradient-based inference time refinement. However, gradient search often incurs significant computational overhead and may not align with the discrete structure of feasible solutions. We introduce Projected Consistency Inference (PCI), a plug-and-play, retraining-free alternative that replaces gradient refinement with structure-aware projections: PCI decodes valid Hamiltonian tours from the consistency model output and applies a lightweight local search (e.g., 2-opt). PCI achieves an average optimality gap (OG) of 0.17% on TSP with 500 cities, and 0.31% on TSP with 1000 cities, outperforming FT2T best settings (OG 0.22% and 0.36%, respectively) while reducing the inference time up to 30 to 40%. PCI also exhibits lower variance and memory usage, and can surpass classical heuristics such as LKH3 in rapid solution generation. Our results demonstrate that structure-aware inference time operations provide a practical and principled path for neural TSP solvers, complementing training time objectives.

Mickaël Basson, Philippe Preux

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

Traveling Salesperson Problem Inference-Time Optimization Combinatorial Optimization Local Search Neural Combinatorial Optimization Consistency Models

Ask PDF

Jun 22, 2026

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

The traveling salesman problem (TSP) is a canonical NP-hard combinatorial optimization benchmark that tests the representational capacity and generalization of neural solvers. While non-autoregressive (NAR) approaches offer parallel inference, they often lack sufficient geometric inductive bias and stable training signals, leading to degraded performance under cross-scale and cross-distribution shifts. We propose GeoRouteNet, a geometry-enhanced NAR neural solver for Euclidean TSP. On the model side, GeoRouteNet incorporates centered node features, learnable radial distance basis functions, distance-aware graph attention with explicit edge messaging, LayerNorm-SwiGLU feed-forward blocks, and cross-layer attentive residual mixing. On the training side, we design multi-candidate self-comparison reinforcement learning (MCS-RL), which samples multiple candidate tours per instance, constructs adaptive baselines from greedy and peer candidates, and adds winner-candidate guidance with annealed entropy regularization. On 10,000 random TSP50 instances, GeoRouteNet achieves a 0.32% optimality gap under Beam-1000 decoding. On TSP100, the gap is 1.26%. On 27 stratified TSPLIB EUC_2D instances, the overall gap drops from 17.12% (NAR4TSP reproduction) to 3.60%, while batch inference throughput substantially exceeds that of Concorde and LKH3. Ablation studies confirm that geometric structure enhancement and multi-candidate training are complementary: structure improvements dominate cross-distribution gains, while MCS-RL further stabilizes solution quality when paired with a strong geometric encoder.

Xiang Li

College of Computer Science, Yangtze University, Jingzhou, China

Traveling Salesperson Problem Graph Neural Networks Reinforcement Learning Combinatorial Optimization RL for Combinatorial Optimization Neural Combinatorial Optimization

Ask PDF

Jul 26, 2026

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

Humans often find good solutions to combinatorial optimization problems that are computationally hard even for advanced computer algorithms. In the Euclidean traveling salesman problems (TSP), people rapidly produce tours that are near-optimal, despite severe limits on time and computation. What makes a tour human-like, and how might such solutions be learned? Here we address these questions through a large-scale behavioral and computational investigation of human performance in Euclidean TSP. We sampled a broad space of TSP instances, collected human solutions, and compared them with neural policies based on Pointer Networks, which are recurrent neural networks with an attention-based pointing mechanism that define probability distributions over valid tours. We trained these networks under multiple objectives, including reinforcement learning (RL), supervised learning from optimal tours, supervised learning from human tours, and RL fine-tuning after optimal-supervised pretraining. Human tours were not identical to optimal tours, but occupied a near-optimal geometric basin: they shared many structural properties with optimal solutions while preserving systematic human-specific deviations. The best account of human tours was not direct imitation of optimal tours, but a model pretrained on optimal tours, fine-tuned by RL, and decoded through

\text{Best-of-}N

sampling. These findings suggest that human-like solutions may emerge from a combination of structured supervised learning, RL, and test-time search, echoing computational principles underlying many modern artificial intelligence systems.

Haijiang Yan, Jian-Qiao Zhu, Liqiang Huang +1

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

Traveling Salesperson Problem Inference-Time Search Combinatorial Optimization Imitation Learning RL for Combinatorial Optimization Neural Combinatorial Optimization

Ask PDF

Abstract

Traveling Salesperson Problem

Explore similar work

Leveraging Structural Constraints for Diffusion-based Neural TSP Solvers

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

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