Understanding Human-like Solutions in Combinatorial Optimization via Learning and Search
Haijiang Yan, Jian-Qiao Zhu, Liqiang Huang, Ming Meng
cs.AI
2026-07-27
From 1,107 people and 150k traveling-salesman instances, human tours fall in a near-optimal geometric basin yet carry systematic biases that a pointer network reproduces via optimal tours plus reinforcement learning.
The traveling salesman problem (TSP) is a classic NP-hard combinatorial optimization: given a set of points, find the shortest tour that visits them all and returns. Algorithms rely on exact solvers like Concorde or heuristic search. Humans sketch a good tour in milliseconds without anything resembling exhaustive search, and how they do it has long puzzled the boundary between cognitive science and AI.
This paper asks two questions: what exactly makes human TSP tours human, and can a learning model reproduce that strategy.
The authors collected tours from 1,107 participants on 150,000 Euclidean TSP instances, about 20.8 million routes in total (around 139 human tours per instance). Instance sizes range from 10 to 24 cities.
The model is a Pointer Network, a recurrent net with attention that points at input positions to emit an ordering. Four training regimes are compared: supervised learning on optimal tours only (poptimal), pure reinforcement learning (pRL), supervised pretraining on optima followed by RL fine-tuning (poptimal+RL), and supervised learning on human tours (phuman). At inference, three decoding strategies stack on top: greedy, beam search (B=100), and Best-of-N sampling (N=1, 10, 100). Search-only baselines round out the comparison: exact Concorde, nearest neighbor, convex-hull cheapest insertion, largest interior angle, and elastic net.
The key twist is that the metric is not just shortest but most human-like. The authors define a human-likeness geometric score based on features such as smoothness, 2-opt local optimality, and convex-hull boundary preservation.
Human tours are near-optimal but not optimal. The optimality gap grows from 6.2% at 10 cities to 11.0% at 24 cities, while each person's best tour sits within 0.3% of optimal. Humans land in a near-optimal geometric basin without hitting the exact optimum.
The human bias is consistent: less smooth than optimal tours, lower 2-opt local optimality, weaker preservation of the convex hull. These are stable and reproducible, and they are what human means here.
Among models trained without human data, poptimal+RL with Best-of-100 sampling is the most human-like, reaching a Pearson correlation of 0.583 with the human-likeness score. On a human-likeness scale of 1.0, Concorde scores 0.592, elastic net 0.593, and this model 0.600, while plain nearest neighbor manages only 0.447. The phuman model with beam search reaches 0.600 and is treated as an empirical upper bound.
One counterintuitive finding: the pure-RL model has an over-concentrated geometric profile and is less responsive to test-time search, while the supervised-plus-RL model converges toward the human near-optimal region through Best-of-N sampling.
| Method | Human-likeness |
| Nearest neighbor | 0.447 |
| Concorde (exact) | 0.592 |
| Elastic net | 0.593 |
| poptimal+RL, Best-of-100 | 0.600 |
For anyone in combinatorial optimization or learning, the value here is that the paper separates optimal from human-like. A model that finds the optimum need not be human-like, and a human-like model need not be optimal. Humans likely use a set of geometric heuristics with stable biases rather than exhaustive search, and those heuristics can be learned. That is a concrete entry point for improving search with cognitive strategies.
The scope caveat matters: this is 10 to 24 cities. Scaling to thousand-node logistics is a different problem.
The authors concede several points. Humans in real life cannot observe optimal solutions at the scale supervised training assumes, so where the human-style demonstrations come from is left unexplained at the cognitive level. The network has limited capacity and still assigns non-negligible probability to tours that are neither optimal nor human-like. More sophisticated test-time search such as MCMC is left for future work.
There is also a methodological tension worth naming: the human-likeness metric is the authors' own construction, and phuman is advantaged on it by design (trained on human tours, scored by a human metric). Treating it as an empirical ceiling is reasonable, but it is not a clean comparison.