Research map / Large language models / Reasoning and chain of thought
Improving Generalization of Neural Combinatorial Optimization for Vehicle Routing Problems via Test-Time Projection Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes TTPL, an LLM-driven evolutionary search (EoH-style) that designs coordinate projection strategies applied at inference time to a LEHD backbone trained on 100-node instances, plus Multi-View Decision Fusion, to generalize to 1K-100K node TSP/CVRP.
Problem
Neural combinatorial optimization models trained on small (100-node) VRP instances degrade sharply on large-scale instances due to distribution shift in KNN subgraphs during construction.
Approach
Use an LLM-driven evolutionary search to automatically design a test-time coordinate projection that maps KNN subgraphs to the training distribution, combined with multi-view (geometric augmentation) logit aggregation; no retraining of the NCO model is required.
Key results
- TTPL-MVDF with RRC1000 achieves 1.63% gap on TSP100K and 1.13% on TSP10K, outperforming the best baselines (e.g., LEHD RRC1,000 at 12.5% on TSP10K).
- On TSPLIB (33 instances, >1K nodes), TTPL-MVDF RRC1000 reaches 1.37% average gap versus 7.37% for LEHD RRC1,000 and 11.04% for INViT greedy.
- On CVRP100K, TTPL-MVDF RRC1000 achieves 3.32% gap; the projection also improves POMO from 597.8 to 296.6 on TSP100K objective.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add TTPL-designed projection instead of using KNN without projection (ablation) | LEHD · TSP1K–TSP100K | optimality gap: 4.49% -> 2.65%; 12.80% -> 3.25%; 17.42% -> 3.63%; 48.00% -> 3.29%; 121.42% -> 3.22% | Helped |
| Replace TTPL projection with the seed projection strategy (ablation) | LEHD · TSP1K–TSP100K | optimality gap: 2.96% -> 2.65%; 3.32% -> 3.25%; 3.77% -> 3.63%; 3.42% -> 3.29%; 3.24% -> 3.22% | Hurt |
| Add MVDF to the TTPL projection (ablation) | LEHD · TSP1K–TSP100K | optimality gap: 2.65% -> 2.26%; 3.25% -> 2.86%; 3.63% -> 2.39%; 3.29% -> 2.69%; 3.22% -> 2.56% | Helped |
| Use POMO augmentation instead of MVDF (ablation) | LEHD with TTPL projection · TSP1K–TSP100K | optimality gap: 2.65% -> 0.89%; 3.25% -> 2.22%; 3.63% -> 2.56%; 3.29% -> 2.86%; 3.22% -> 2.85% | Mixed |
| Add RRC1000 to TTPL-MVDF | LEHD · TSP1K–TSP100K | optimality gap: 2.26% -> 0.28%; 2.86% -> 1.04%; 2.39% -> 1.13%; 2.69% -> 1.55%; 2.56% -> 1.63% | Helped |
| Add RRC1000 to TTPL-MVDF | LEHD · CVRP5K–CVRP100K | optimality gap: 4.88% -> 2.37%; 2.54% -> 1.02%; 2.73% -> 2.25%; 3.60% -> 3.32% | Helped |
| Use TTPL-MVDF projection rather than KNN alone | POMO · TSP1K–TSP100K | objective: 33.4 -> 29.8; 96.1 -> 67.6; 153.4 -> 94.6; 392.4 -> 212.1; 597.8 -> 296.6 | Helped |
| Replace POMO seed projection with the TTPL-designed projection and MVDF | POMO · TSP1K–TSP100K | objective: 30.0 -> 29.8; 73.8 -> 67.6; 103.0 -> 94.6; 235.8 -> 212.1; 331.3 -> 296.6 | Helped |
Surprising findings
- Applying the LLM-designed projection to LEHD with plain KNN degrades to 121.42% gap on TSP100K, showing how severe the distribution shift is without projection.
- Strategies evolved on 10K instances were reused for 50K and 100K due to computational burden, suggesting transfer across scales.
Limitations
- Slow convergence of the LLM evolution phase to optimal projection strategies.
- Projection strategies for 50K and 100K are transferred from 10K rather than optimized per scale due to compute cost.
- Code and data are not released at submission time.
Experimental setup
Datasets: TSP/CVRP synthetic instances (1K-100K nodes) TSPLIB CVRPLIB cross-distribution instances (cluster, explosion, implosion)
Benchmarks: TSP1K TSP5K TSP10K TSP50K TSP100K CVRP1K CVRP5K CVRP10K CVRP50K CVRP100K TSPLIB CVRPLIB
Metrics: optimality gap inference time
Baselines: LKH3 Concorde HGS Random Insertion DIFUSCO H-TSP GLOP POMO BQ LEHD INViT SIGD
Builds on: EoH LEHD INViT POMO
Closest papers by meaning
- Rethinking Neural Combinatorial Optimization for Vehicle Routing Problems with Different Constraint Tightness Degrees (NeurIPS 2025 · similarity 0.93)
- Learning to Insert for Constructive Neural Vehicle Routing Solver (NeurIPS 2025 · similarity 0.92)
- CaDA: Cross-Problem Routing Solver with Constraint-Aware Dual-Attention (ICML 2025 · similarity 0.92)
- Neural Solver Selection for Combinatorial Optimization (ICML 2025 · similarity 0.91)
- Neural Combinatorial Optimization for Robust Routing Problem with Uncertain Travel Times (NeurIPS 2024 · similarity 0.89)
- MTL-KD: Multi-Task Learning Via Knowledge Distillation for Generalizable Neural Vehicle Routing Solver (NeurIPS 2025 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.