Research map / Learning theory and algorithms / Combinatorial and search optimization
Rethinking Neural Combinatorial Optimization for Vehicle Routing Problems with Different Constraint Tightness Degrees
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.
Shows that NCO solvers for CVRP overfit to the training capacity (C=50) and proposes varying-constraint-tightness training plus a multi-expert module on LEHD, which generalizes across capacities for CVRP and CVRPTW.
Problem
Neural combinatorial optimization solvers for vehicle routing are trained on a single fixed constraint tightness (e.g., CVRP100 with C=50) and degrade sharply on instances with tight or loose capacity or time-window constraints.
Approach
Train on instances whose capacity (or time-window tightness) is sampled uniformly per instance over the full range, and add a gated multi-expert module in the decoder (LEHD) where each expert handles a sub-range of tightness, so one model adapts across tightness levels.
Key results
- The proposed LEHD-based model reaches an average gap of 1.86% across seven CVRP100 capacity datasets, versus 3.71% average best for prior NCO methods (and 9.62% for LEHD).
- Varying constraint tightness training alone reduces the base model's average gap from 10.78% to 2.41%; adding the multi-expert module gives 1.86%.
- On CVRPTW100 with POMO, VCT+MEM lowers the average gap from 19.58% (POMO) to 11.58%.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Train across capacities from 10 to 500 and add the multi-expert module (ablation) | LEHD · CVRP100 varying capacities | average optimality gap: 10.78% -> 1.86% | Helped |
| Add varying-capacity training without MEM (ablation) | LEHD · CVRP100 varying capacities | average optimality gap: 10.78% -> 2.41% | Helped |
| Add varying-capacity training without MEM (ablation) | LEHD · CVRP100 C=50 and C=100 | optimality gap: 3.72% -> 4.51%; 4.21% -> 4.69% | Hurt |
| Add MEM to the fixed-capacity base model (ablation) | LEHD · CVRP100 varying capacities | average optimality gap: 10.78% -> 8.95% | Helped |
| Add MEM to varying-capacity training (ablation) | LEHD · CVRP100 varying capacities | average optimality gap: 2.41% -> 1.86% | Helped |
| Use discrete expert switching instead of soft Top-K MoE gating (ablation) | LEHD+VCT+MEM · CVRP100 varying capacities | average optimality gap: 2.17% -> 1.86% | Helped |
| Assign each instance its own random capacity rather than one capacity per batch (ablation) | LEHD+VCT+MEM · CVRP100 capacities 10–500 | optimality gap: 1.99% -> 1.54%; 4.66% -> 3.82%; 5.02% -> 3.67%; 2.46% -> 1.49%; 1.06% -> 0.87%; 0.89% -> 0.75%; 0.94% -> 0.87% | Helped |
| Apply varying-tightness training and MEM (ablation) | POMO · CVRPTW100 varying time windows | average optimality gap: 19.58% -> 11.58% | Helped |
| Add varying time-window tightness training without MEM (ablation) | POMO · CVRPTW100 α=1.0 | optimality gap: 11.39% -> 12.37% | Hurt |
| Add MEM after varying-tightness training (ablation) | POMO+VCT · CVRPTW100 varying time windows | average optimality gap: 12.14% -> 11.58% | Helped |
| Train across capacity values rather than only at C=50 (ablation) | LEHD · CVRP100 C=50 | optimality gap: 3.72% -> 4.51% | Hurt |
| Train across capacity values rather than only at C=50 (ablation) | LEHD · CVRP100 C=10 and C=200–500 | optimality gap: 45.64% -> 1.88%; 3.62% -> 2.25%; 5.61% -> 1.28%; 5.36% -> 1.03%; 7.29% -> 1.25% | Helped |
Surprising findings
- Batch-level capacity sampling performs worse than instance-level sampling in training, with ablation showing consistently higher gaps.
- Uniform varying-capacity training slightly degrades performance at C=50 and C=100 relative to fixed-capacity training.
Limitations
- Training uses uniform sampling of constraint tightness; adaptive sampling is left for future work.
- Evaluated only on CVRP and CVRPTW with greedy decoding; no error bars reported since NCO inference is deterministic.
- Multi-expert module uses discrete rule-based switching; a learned soft Top-K MoE variant performed worse (2.17% vs 1.86% average gap).
Experimental setup
Datasets: CVRP100 instances with HGS labels CVRPTW100 instances
Benchmarks: CVRP100 with capacities C=10,50,100,200,300,400,500 CVRPTW100 with time-window tightness alpha 0.2-3.0
Metrics: optimality gap average gap inference time
Baselines: AM POMO MDAM BQ LEHD ELG INViT POMO-MTL MVMoE HGS
Builds on: LEHD POMO MVMoE Attention Model
Closest papers by meaning
- Improving Generalization of Neural Combinatorial Optimization for Vehicle Routing Problems via Test-Time Projection Learning (NeurIPS 2025 · similarity 0.93)
- 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.90)
- Learning to Insert for Constructive Neural Vehicle Routing Solver (NeurIPS 2025 · similarity 0.89)
- Neural Combinatorial Optimization for Robust Routing Problem with Uncertain Travel Times (NeurIPS 2024 · similarity 0.88)
- Learning to Handle Complex Constraints for Vehicle Routing Problems (NeurIPS 2024 · similarity 0.87)
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.