Learning to Search, Searching to Learn: A Closed-Loop Framework for Large-Scale Vehicle Routing
NeurIPS 2026
abstract
Large-scale Vehicle Routing Problems (VRPs) face two long-standing difficulties. On the one hand, many scalable methods rely on partitioning, local candidate restriction, or staged decision making to control computation, which weakens their modeling of global structure. On the other hand, although many methods introduce search at test time to improve the final solution, search is still typically used only as a one-shot post-processing step after model prediction. The model makes a prediction, search repairs it, and little sustained feedback is formed between the two. Improved structural states are rarely fed back to the model for subsequent inference, and high-quality search solutions are seldom turned into later training supervision.
To address this issue, we propose LSSL (Learning to Search, Searching to Learn), a closed-loop learning-search framework for large-scale VRPs. LSSL first predicts search-friendly structural priors on a sparse candidate graph, and search then iteratively refines the current solution under the guidance of these priors. In turn, search does not leave the system after one round of refinement. At inference time, the structural states returned by search are fed back to the model for the next round of prediction, while at training time, multiple high-quality search solutions are reorganized into row-wise soft targets for model update. In this way, learning tells search where to explore, and search tells the model which structures are worth learning. Experiments show that LSSL achieves strong scalability, efficiency, and solution quality across multiple large-scale VRP benchmarks.
Motivation
Existing learning-based VRP solvers scale by cutting the decision space — partitioning the graph, masking candidates, or making decisions in stages. These shortcuts help the model fit in memory but also throw away the global structure the model needs to reason over. Meanwhile, test-time search is usually bolted on at the end as a fixed post-processor, and what it discovers never flows back into the model.
Framework
LSSL closes the loop between learning and search:
- Sparse structural prior. The model predicts a search-friendly prior over a sparse candidate graph, giving search a warm direction instead of starting cold.
- Guided iterative search. Local search refines the current solution under that prior, keeping the exploration budget focused.
- Structural feedback at inference. The structural state produced by search is fed back to the model for the next prediction round — not discarded.
- Soft supervision at training. Multiple high-quality search solutions are aggregated into row-wise soft targets so the model keeps learning from what search has already found.
The two directions reinforce each other: learning tells search where to explore, search tells the model which structures are worth learning.
Figure
Results
On six real-world Art-TSP instances ranging from 100K to 200K nodes — each a famous artwork rendered as a giant TSP tour — LSSL stays within 0.023%–0.039% of the optimal tour length, well inside the gap of every baseline compared:
| Instance | Random Insertion | L2C-Insert | GLOP | LSSL (C=1, 128 trials) | LSSL (C=2, 256 trials) |
|---|---|---|---|---|---|
| mona-lisa100K | 6.706% | 3.764% | 3.224% | 0.034% (0.33h) | 0.026% (1.37h) |
| vangogh120K | 6.812% | 4.022% | 3.156% | 0.038% (0.49h) | 0.028% (1.91h) |
| venus140K | 6.581% | 4.102% | 3.067% | 0.027% (0.62h) | 0.023% (2.54h) |
| pareja160K | 6.830% | 4.259% | 3.158% | 0.032% (0.87h) | 0.024% (3.50h) |
| courbet180K | 7.145% | 4.777% | 3.294% | 0.035% (1.04h) | 0.025% (4.00h) |
| earring200K | 7.605% | 4.514% | 3.528% | 0.039% (1.32h) | 0.029% (5.18h) |
| Mean | 6.947% | 4.240% | 3.238% | 0.034% (0.78h) | 0.026% (3.08h) |
At 100K nodes — the mona-lisa100K instance below — a single 0.33-hour (≈20-minute) run
already lands within 0.034% of optimal: LSSL can solve instances at this scale in a very short
amount of time.
mona-lisa100K (N = 100,000 cities), tour length 5,757,191.