Research map / Reinforcement learning / Visual and representation RL
DPN: Decoupling Partition and Navigation for Neural Solvers of Min-max 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 DPN, an RL sequential-planning neural solver for min-max VRPs that decouples customer partition and navigation via a P&N encoder, an agent-permutation-symmetric loss, and a rotation-based positional encoding.
Problem
Neural solvers for min-max vehicle routing problems (minimizing the longest route) struggle because existing sequential-planning encoders entangle the customer partition and navigation features, yielding less effective representations and imbalanced routes.
Approach
Split each encoder layer into a navigation part (customer self-attention) and a partition part (agent-customer attention with a sharp Softmax-free attention), add an APS loss that exploits the unordered nature of agent routes to build a permutation-averaged baseline, and use a depot-aware rotation-based positional encoding for agents.
Key results
- DPN-x8aug-x16per achieves the best learning-based results on all 12 medium-scale datasets, with an average 0.72% gap reduction over Equity-Transformer on min-max mTSP and 33.7% on min-max mPDP.
- On larger scales, DPN-F-x8aug-x16per gives the best objectives on four mTSP and all nine mPDP datasets (200-1000 nodes).
- Ablations on mTSP100 and mPDP100 (M=5) show removing the P&N Encoder or APS-Loss hurts most, e.g., mPDP100 rises from 3.4960 to 4.5119 without the P&N Encoder and 5.1915 without APS-Loss.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add ×8aug and ×16per test-time augmentation | DPN · Min-max mTSP50 (M=3) | Obj.: 2.5149 -> 2.4637 | Helped |
| add ×8aug and ×16per test-time augmentation | DPN · Min-max mPDP100 (M=5) | Obj.: 3.6500 -> 3.4960 | Helped |
| add P&N Encoder (ablation) | DPN-×8aug-×16per · Min-max mTSP100 (M=5) | Obj.: 2.2406 -> 2.2314 | Helped |
| add APS-Loss (ablation) | DPN-×8aug-×16per · Min-max mTSP100 (M=5) | Obj.: 2.2621 -> 2.2314 | Helped |
| add Rotation-based PE (ablation) | DPN-×8aug-×16per · Min-max mTSP100 (M=5) | Obj.: 2.2347 -> 2.2314 | Helped |
| add P&N Encoder (ablation) | DPN-×8aug-×16per · Min-max mPDP100 (M=5) | Obj.: 4.5119 -> 3.4960 | Helped |
| add APS-Loss (ablation) | DPN-×8aug-×16per · Min-max mPDP100 (M=5) | Obj.: 5.1915 -> 3.4960 | Helped |
| add Rotation-based PE (ablation) | DPN-×8aug-×16per · Min-max mPDP100 (M=5) | Obj.: 3.5158 -> 3.4960 | Helped |
| apply DPN-F-×8aug-×16per instead of CE | Min-max FMDVRP100 · FMDVRP100 (M=5) | Obj.: 1.74 -> 1.7638 | Hurt |
Surprising findings
- Removing APS-Loss increases mPDP100 error far more than removing the P&N Encoder (5.19 vs 4.51 against 3.50 for the full model), indicating the symmetry-based baseline matters most for pickup-delivery.
Limitations
- The method cannot be directly applied to general VRPs with capacity or other constraints, as stated by the authors.
- Gains over strong heuristics such as HGA and LKH3 are not achieved; DPN is competitive but not best on several settings.
- On 100-scale FMDVRP, CE and NCE outperform DPN.
Experimental setup
Datasets: randomly generated min-max mTSP instances randomly generated min-max mPDP instances randomly generated min-max MDVRP instances randomly generated min-max FMDVRP instances
Benchmarks: min-max mTSP50/100/200/500/1000 min-max mPDP50/100/200/500/1000 min-max MDVRP50/100 min-max FMDVRP50/100
Metrics: average objective (longest route length) optimality gap testing time
Baselines: HGA LKH3 OR-Tools DAN Equity-Transformer ScheduleNet NCE CROSS exchange
Builds on: Equity-Transformer POMO REINFORCE Rotary positional encoding ReZero
Closest papers by meaning
- Neural Combinatorial Optimization for Robust Routing Problem with Uncertain Travel Times (NeurIPS 2024 · similarity 0.88)
- Multi-Task Vehicle Routing Solver via Mixture of Specialized Experts under State-Decomposable MDP (NeurIPS 2025 · similarity 0.88)
- Rethinking Light Decoder-based Solvers for Vehicle Routing Problems (ICLR 2025 · similarity 0.87)
- MTL-KD: Multi-Task Learning Via Knowledge Distillation for Generalizable Neural Vehicle Routing Solver (NeurIPS 2025 · similarity 0.87)
- CaDA: Cross-Problem Routing Solver with Constraint-Aware Dual-Attention (ICML 2025 · similarity 0.87)
- Memory-Enhanced Neural Solvers for Routing Problems (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.