Research map / Probabilistic and scientific modeling / Molecules and proteins

SVRPBench: A Realistic Benchmark for Stochastic Vehicle Routing Problem

NeurIPS 2025 · Probabilistic and scientific modeling › Molecules and proteins · approach: Machine learning for physical simulation · 1 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.

Introduces SVRPBench, an open benchmark of 500+ stochastic vehicle routing instances (time-dependent congestion, log-normal delays, accidents, residential/commercial time windows) and benchmarks classical, metaheuristic, OR-Tools, and RL solvers (AM, POMO) on it.

Problem

Vehicle routing under realistic uncertainty (time-dependent congestion, stochastic delays, accidents, customer time windows) is poorly covered by existing static VRP benchmarks.

Approach

A benchmark generator that embeds time-dependent Gaussian-mixture congestion, log-normal delays, Poisson accident events, and empirically motivated residential/commercial time-window distributions into VRP instances, plus a standardized evaluation protocol with feasibility, robustness, and runtime metrics.

Key results

• OR-Tools achieved the best aggregate total cost (40,259.3) with 98.4% feasibility, while POMO reached 40,650 cost with 93.3% feasibility at 1.421s runtime.
• Adding time windows (TWCVRP) increased total cost by 536–648% across solvers; POMO maintained 87.9% feasibility and AM 85.4% on TWCVRP.
• Multi-depot configurations reduced costs across methods; OR-Tools cost fell from 34,611 (single depot) to 9,561 (multi-depot).

Measured effects reported in the paper

Surprising findings

• Abstract claims RL solvers POMO and AM degrade by over 20% under distributional shift while classical and metaheuristic methods remain robust, though the reported tables show OR-Tools and NN+2opt as the strongest.
• Multi-depot configurations improved cost and feasibility for learning-based solvers, reaching 100% feasibility for POMO and AM in the multi-depot setting.

Limitations

• Delay models are Gaussian and log-normal and do not capture network-level effects such as bottlenecks, cascading congestion, or real-time rerouting.
• RL methods show limited scalability to larger instances, and the evaluation protocol lacks standardized procedures for robustness across scales and distribution shifts.
• Road-constrained instances from OpenStreetMap are not yet included; instances are Euclidean.

Experimental setup

Datasets: SVRPBench synthetic instances real city layouts (Michigan, Abu Dhabi, Milan) for visual comparison

Benchmarks: SVRPBench

Metrics: total cost constraint violation rate feasibility rate runtime robustness (cost variance across stochastic samples)

Baselines: Nearest Neighbor + 2-opt Tabu Search ACO OR-Tools Attention Model POMO

Builds on: RL4CO POMO Attention Model (Kool et al.) REINFORCE

Closest papers by meaning

• Hybrid-Balance GFlowNet for Solving Vehicle Routing Problems (NeurIPS 2025 · similarity 0.84)
• SHIELD: Multi-task Multi-distribution Vehicle Routing Solver with Sparsity and Hierarchy (ICML 2025 · similarity 0.83)
• URB - Urban Routing Benchmark for RL-equipped Connected Autonomous Vehicles (NeurIPS 2025 · similarity 0.83)
• BO4Mob: Bayesian Optimization Benchmarks for High-Dimensional Urban Mobility Problem (NeurIPS 2025 · similarity 0.82)
• MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of-Experts (ICML 2024 · similarity 0.82)
• Equity-Transformer: Solving NP-Hard Min-Max Routing Problems as Sequential Generation with Equity Context (AAAI 2024 · similarity 0.82)