Research map / Probabilistic and scientific modeling / Differential equations and PDEs
Learning to Insert for Constructive Neural Vehicle Routing Solver
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 L2C-Insert, a learned insertion-based constructive NCO solver for TSP and CVRP that predicts insertion positions via supervised learning and refines solutions with distance-based insertion local reconstruction, scaling to 100K nodes.
Problem
Appending-based constructive neural combinatorial optimization for VRPs builds solutions by appending nodes to the end of partial solutions, causing path intersections and early greedy suboptimality; insertion-based construction is unexplored in NCO.
Approach
Insert each selected unvisited node at any valid position in the partial solution, with an attention-based decoder that scores adjacent-node position embeddings, trained by supervised re-insertion toward labeled tours, and refined at inference by distance-based destruction and insertion-based reconstruction.
Key results
- On TSP1K, L2C-Insert (I=1000) reaches 0.481% gap versus 0.731% for LEHD RRC1000, a 34.2% gap reduction at 6.7x speedup.
- On TSP10K, L2C-Insert (I=1000) achieves 2.079% gap, outperforming DIFUSCO (2.58%) and GLOP (4.545%).
- On TSPLIB, L2C-Insert (I=1000) achieves 0.308% average gap versus 0.380% for LEHD RRC1000.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use insertion-based instead of appending-based construction (ablation) | L2C-Insert vs. L2C-Append · TSP1000 | Gap: 0.974% -> 0.481% | Helped |
| Use insertion-based instead of appending-based construction (ablation) | L2C-Insert vs. L2C-Append · TSP10000 | Gap: 12.881% -> 2.079% | Helped |
| Use distance-based rather than sequence-based destruction (ablation) | L2C-Insert local reconstruction · TSP1000 | Gap: 1.182% -> 0.481% | Helped |
| Use distance-based rather than sequence-based destruction (ablation) | L2C-Insert local reconstruction · TSP10000 | Gap: 6.980% -> 2.079% | Helped |
| Use Polar Angle rather than Euclidean Distance as distance criterion (ablation) | L2C-Insert · CVRP100 | Gap: 5.151% -> 3.892% | Helped |
| Use Polar Angle rather than Euclidean Distance as distance criterion (ablation) | L2C-Insert · CVRP1000 | Gap: 10.155% -> 8.009% | Helped |
| Select the current node by nearest neighbor rather than randomly (ablation) | L2C-Insert · TSP100 | Gap: 1.1557% -> 0.9535% | Helped |
| Select the current node by nearest neighbor rather than randomly (ablation) | L2C-Insert · CVRP100 | Gap: 11.370% -> 3.892% | Helped |
| Add positional encoding to position embeddings (ablation) | L2C-Insert · TSP100 | Gap: 0.9535% -> 1.0475% | Hurt |
| Add positional encoding to position embeddings (ablation) | L2C-Insert · CVRP100 | Gap: 3.892% -> 5.802% | Hurt |
| Include unvisited nodes as decoder input (ablation) | L2C-Insert · TSP100 | Gap: 5.161% -> 0.460% | Helped |
| Include unvisited nodes as decoder input (ablation) | L2C-Insert · TSP1K | Gap: 23.979% -> 4.757% | Helped |
Surprising findings
- Greedy L2C-Insert alone is weaker than some baselines on small instances; gains require the local reconstruction iterations.
- Adding positional encoding to position embeddings hurt performance on TSP100 and CVRP100.
Limitations
- Performance is bounded by the model architecture, which the authors suggest could be improved.
- Node selection uses a fixed nearest-neighbor heuristic rather than a learned policy.
- Only TSP and CVRP are evaluated; the approach is not extended to other COPs.
Experimental setup
Datasets: TSP100 training instances (1M, Concorde labels) CVRP100 training instances (1M, HGS labels) TSPLIB CVRPLIB Set-X TSP1K/TSP10K/TSP50K/TSP100K test sets CVRP1K/CVRP10K/CVRP50K/CVRP100K test sets
Benchmarks: TSP100 TSP1K TSP10K TSP50K TSP100K CVRP100 CVRP1K CVRP10K CVRP50K CVRP100K TSPLIB CVRPLIB Set-X
Metrics: average tour length optimality gap inference time
Baselines: LKH3 Concorde HGS POMO BQ LEHD INViT ELG DIFUSCO T2T GLOP UDC
Builds on: Attention Model LEHD POMO
Closest papers by meaning
- Improving Generalization of Neural Combinatorial Optimization for Vehicle Routing Problems via Test-Time Projection Learning (NeurIPS 2025 · similarity 0.92)
- Neural Solver Selection for Combinatorial Optimization (ICML 2025 · similarity 0.90)
- Rethinking Neural Combinatorial Optimization for Vehicle Routing Problems with Different Constraint Tightness Degrees (NeurIPS 2025 · similarity 0.89)
- CaDA: Cross-Problem Routing Solver with Constraint-Aware Dual-Attention (ICML 2025 · similarity 0.89)
- Memory-Enhanced Neural Solvers for Routing Problems (NeurIPS 2025 · similarity 0.86)
- Neural Combinatorial Optimization for Robust Routing Problem with Uncertain Travel Times (NeurIPS 2024 · similarity 0.86)
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.