Research map / Architectures and efficiency / RNNs and normalization
Learning to Handle Complex Constraints for Vehicle Routing Problems
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 PIP and PIP-D, which combine a Lagrangian multiplier with one-step preventative infeasibility masking (learned by an auxiliary decoder) to let neural constructive VRP solvers handle complex interdependent constraints in TSPTW and TSPDL.
Problem
Neural constructive VRP solvers rely on feasibility masking, which fails for VRPs with complex interdependent constraints (e.g., time windows, draft limits) because local masks do not guarantee global feasibility and exact global masks are NP-hard.
Approach
Integrate a fixed Lagrangian multiplier penalty into the RL reward for constraint awareness, plus a one-step preventative infeasibility mask that marks nodes whose selection would make remaining nodes unvisitable; an auxiliary PIP decoder learns these masks with periodic updates and hardness-adaptive class weighting.
Key results
- On Hard TSPTW-100, POMO* instance-level infeasibility drops from 100% to 6.48% with PIP-D (optimality gap 0.31%).
- PIP achieves up to 93.52% infeasible-rate reduction across backbones and settings, per the paper's claim.
- PIP-D trains about 1.5x faster than PIP at n=50 and 5.8x faster at n=100 while matching or beating its quality on many settings.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add learned PI masking to POMO* | POMO* · Easy TSPTW-50 | Sol. infeasible rate: 1.75% -> 0.28% | Helped |
| Add learned PI masking to POMO* | POMO* · Hard TSPTW-100 | Inst. infeasible rate: 100.00% -> 6.48% | Helped |
| Add one-step PI masking to POMO* | POMO* · Medium TSPDL-50 | Sol. infeasible rate: 17.72% -> 2.21% | Helped |
| Add learned PI masking to POMO* | POMO* · Hard TSPDL-100 | Inst. infeasible rate: 99.85% -> 7.91% | Helped |
| Add learned PI masking to GFACS* | GFACS* · Medium TSPTW-500 | Gap: 21.32% -> 11.95% | Helped |
| Use zero PIP steps instead of one (ablation) | POMO* + PIP · Medium TSPTW-50 | Sol. infeasible rate: 4.53% -> 76.92% | Hurt |
| Use two PIP steps instead of one (ablation) | POMO* + PIP · Medium TSPTW-50 | Time: 15s -> 4.2m | Hurt |
| Use zero PIP steps instead of one (ablation) | POMO* + PIP-D · Hard TSPTW-100 | Inst. infeasible rate: 6.48% -> 63.29% | Hurt |
| Use two PIP steps instead of one (ablation) | POMO* + PIP-D · Hard TSPTW-100 | Time: 48s -> 35m | Hurt |
| Use weighted balancing for feasible and infeasible PI labels (ablation) | POMO* + PIP-D · Hard datasets | Sol. infeasible rate: 100% infeasible rate without weighted balancing | Helped |
| Increase the number of periodic PIP-decoder updates (ablation) | PIP-D · Reported PIP-D datasets | Performance | Helped |
| Increase the Lagrangian multiplier (ablation) | PIP · Reported multiplier analysis | Infeasible rate | Helped |
Surprising findings
- Removing POMO's diverse starting-node stipulation was necessary: POMO with it had about 50.70% infeasible rate on Easy TSPTW-50 versus 1.75% without.
- Zero-step PIP (Lagrangian only, no lookahead) leaves 47.28% instance-level infeasibility on the Hard setting, showing the one-step PI mask is essential.
Limitations
- Gains are not uniform; the paper acknowledges PIP may not improve every backbone or VRP variant.
- One-step PI masking is an approximation to the NP-hard full feasibility mask; multi-step variants are costly (e.g., 35m inference for 2-step).
- Lagrangian multiplier is fixed (lambda=1) rather than learned, requiring tuning of the trade-off between feasibility and objective.
Experimental setup
Datasets: synthetic TSPTW instances (Easy, Medium, Hard) synthetic TSPDL instances (Medium, Hard)
Benchmarks: TSPTW-50 TSPTW-100 TSPTW-500 TSPDL-50 TSPDL-100
Metrics: solution-level infeasible rate instance-level infeasible rate optimality gap objective value inference time
Baselines: LKH3 OR-Tools Greedy-L Greedy-C JAMPR MUSLA AM POMO GFACS
Builds on: attention model (AM) POMO GFACS REINFORCE
Closest papers by meaning
- CaDA: Cross-Problem Routing Solver with Constraint-Aware Dual-Attention (ICML 2025 · similarity 0.88)
- Memory-Enhanced Neural Solvers for Routing Problems (NeurIPS 2025 · similarity 0.88)
- Neural Combinatorial Optimization for Robust Routing Problem with Uncertain Travel Times (NeurIPS 2024 · similarity 0.87)
- Multi-Task Vehicle Routing Solver via Mixture of Specialized Experts under State-Decomposable MDP (NeurIPS 2025 · similarity 0.87)
- LINC: Decoupling Local Consequence Scoring from Hidden Matching in Constructive Neural Routing (NeurIPS 2026 · similarity 0.87)
- Improving Generalization of Neural Combinatorial Optimization for Vehicle Routing Problems via Test-Time Projection Learning (NeurIPS 2025 · 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.