Research map / Label-efficient and robust learning / OOD and anomaly detection

Rethinking Light Decoder-based Solvers for Vehicle Routing Problems

ICLR 2025 · Label-efficient and robust learning › OOD and anomaly detection · approach: Robust fine-tuning for OOD generalization · 0 citations (OpenAlex)

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.

Revisits light decoder-based neural VRP solvers, argues their static embeddings are overloaded and the simple decoder is the bottleneck, and proposes ReLD (identity mapping + feed-forward layer in the decoder, plus distance heuristic and varying-attribute training) to improve OOD generalization.

Problem

Light decoder-based neural solvers for vehicle routing problems generalize poorly to larger instances and to different VRP variants, because static node embeddings must encode information for all future decision contexts and the shallow decoder cannot exploit them well.

Approach

Enhance the light decoder's capacity without changing its shared static embeddings: add a residual identity mapping from the context (last node embedding plus dynamic features) to the query, and a feed-forward residual block after the MHA, so the decoder is a single-query transformer block. Combined with a logarithmic distance heuristic and varying vehicle-capacity/route-size training.

Key results

• On CVRP1000, ReLD augx8 reaches 6.757% gap vs. POMO 110.632% and ELG 10.760%, while CVRP500 gap is 2.975% vs. POMO 11.135%.
• On CVRPLib Set-X (100 instances), ReLD achieves 4.64% total gap (with augmentation) versus LEHD greedy 12.52% and POMO 11.52%; ReLD-MoEL+ reaches 3.54% total.
• In cross-problem experiments, ReLD-MoEL achieves an average gap of 3.842% over all 16 VRPs versus 4.596% for MVMoE.

Measured effects reported in the paper

Surprising findings

• Adding extra encoder layers to ReLD (ReLD-7Layer) does not improve OOD size generalization and sometimes worsens it.
• Simply increasing decoder parameters via FF on query/key (+FF_qk, +FF_qkv) or an extra MHA can degrade performance, showing placement of parameters matters.

Limitations

• ReLD still trails heavy decoder solvers such as BQ and LEHD on very large instances (CVRP1000 in some settings), as the authors acknowledge.
• Distance heuristic and varying-attribute training trade off a bit of in-distribution performance for OOD gains.
• Experiments are limited to single-GPU settings and CVRP-style constructive solvers; theory for the information-density argument is informal.

Experimental setup

Datasets: CVRPLib Set-X CVRPLib Set-XXL synthetic CVRP instances (Uniform(40,100) training) 16 VRP variants (cross-problem)

Benchmarks: CVRP100 CVRP200 CVRP500 CVRP1000 CVRPLib Set-X CVRPLib Set-XXL 16 VRP variants (1K instances) ATSP20-500

Metrics: optimality gap computation time objective value

Baselines: POMO LEHD BQ ELG MDAM GLOP ICAM INViT MVMoE POMO-MTL LKH3 HGS

Builds on: POMO Attention Model MVMoE LEHD

Closest papers by meaning

• SPACE: Unifying Symmetric and Asymmetric Routing Problems for Generalist Neural Solver (NeurIPS 2026 · similarity 0.88)
• DPN: Decoupling Partition and Navigation for Neural Solvers of Min-max Vehicle Routing Problems (ICML 2024 · similarity 0.87)
• Memory-Enhanced Neural Solvers for Routing Problems (NeurIPS 2025 · similarity 0.87)
• MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of-Experts (ICML 2024 · similarity 0.87)
• MTL-KD: Multi-Task Learning Via Knowledge Distillation for Generalizable Neural Vehicle Routing Solver (NeurIPS 2025 · similarity 0.87)
• LINC: Decoupling Local Consequence Scoring from Hidden Matching in Constructive Neural Routing (NeurIPS 2026 · similarity 0.87)