SVRPBench: A Realistic Benchmark for Stochastic Vehicle Routing Problem

Ahmed Heakl, Yahia Salaheldin Shaaban, Martin Takáč, Salem Lahlou, Zangir Iklassov · 2025

Read SVRPBench: A Realistic Benchmark for Stochastic Vehicle Routing Problem by Ahmed Heakl, Yahia Salaheldin Shaaban, Martin Takáč, Salem Lahlou, Zangir Iklassov (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-21887.txt.

Introduction

Ahmed Heakl and co-authors release in a 2025 benchmark a sterner test for delivery routing under real-world doubt. Most tests assume calm, fixed streets, which flatters new solvers. Their set holds over five hundred cases with up to a thousand customers, with rush-hour jams, delays, mishaps, and time windows drawn from real patterns.

Top learning solvers lost over a fifth of their skill when the setting shifted, while classic methods held firm. The data and scoring tools are open, so labs can compare fairly. The bench pushes the field toward solvers that survive the street, not just the page.

Catalog record

CREATORAhmed Heakl, Yahia Salaheldin Shaaban, Martin Takáč, Salem Lahlou, Zangir Iklassov
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE47 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-21887

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

SVRPBench: A Realistic Benchmark for Stochastic Vehicle Routing Problem Ahmed Heakl, Yahia Salaheldin Shaaban, Martin Takáč, Salem Lahlou, Zangir Iklassov Abstract Robust routing under uncertainty is central to real-world logistics, yet most benchmarks assume static, idealized settings. We present SVRPBench , the first open benchmark to capture high-fidelity stochastic dynamics in vehicle routing at urban scale. Spanning more than 500 instances with up to 1000 customers, it simulates realistic delivery conditions: time-dependent congestion, log-normal delays, probabilistic accidents, and empirically grounded time windows for residential and commercial clients. Our pipeline generates diverse, constraint-rich scenarios, including multi-depot and multi-vehicle setups. Benchmarking reveals that state-of-the-art RL solvers like POMO and AM degrade by over 20% under distributional shift, while classical and metaheuristic methods remain robust. To enable reproducible research, we release the dataset ( Hugging Face ) and evaluation suite ( GitHub ). SVRPBench challenges the community to design solvers that generalize beyond synthetic assumptions and adapt to real-world uncertainty. 1 Introduction Efficient vehicle routing is fundamental to modern logistics and last-mile delivery. The classical Vehicle Routing Problem (VRP) ( dantzig1959truck ; gendreau1996survey ) seeks cost-effective routes for servicing customers under constraints such as vehicle capacities and time windows. Although well studied, real-world deployments face uncertain and dynamic conditions that most existing benchmarks do not adequately capture. Table 1 : Comparison of SVRPBench with existing VRP benchmarks. ✓ indicates full support, \triangle indicates partial or limited support, and ✗ indicates no support. Feature SVRPBench CVRPLIB SINTEF VRP-REP TSPLIB RL4CO Stochastic Elements Time-dependent travel delays ✓ ✗ \triangle \triangle ✗ ✗ Peak-hour traffic patterns ✓ ✗ ✗ ✗ ✗ ✗ Random travel time noise ✓ ✗ \triangle \triangle ✗ \triangle Probabilistic accidents ✓ ✗ ✗ ✗ ✗ ✗ Heterogeneous time windows ✓ ✗ \triangle \triangle ✗ ✗ Problem Configurations Multi-depot support ✓ \triangle ✓ ✓ ✗ ✗ Multi-vehicle fleets ✓ ✓ ✓ ✓ ✗ ✓ Capacity constraints ✓ ✓ ✓ ✓ ✗ ✓ Time window constraints ✓ \triangle ✓ ✓ ✗ \triangle Clustered customer distributions ✓ \triangle \triangle ✓ \triangle ✗ Scale & Diversity Small instances ( \leq 100 customers) ✓ ✓ ✓ ✓ ✓ ✓ Medium instances (100-300) ✓ ✓ ✓ ✓ \triangle ✓ Large instances (>300) ✓ \triangle \triangle \triangle ✗ \triangle Varying stochasticity levels ✓ ✗ \triangle \triangle ✗ ✗ One key extension addressing real-world complexity is the Stochastic Vehicle Routing Problem (SVRP). Unlike deterministic VRP, SVRP explicitly incorporates uncertainty into routing decisions, with problem elements such as travel times, customer demands, service times, and even customer presence considered random variables ( gendreau1996survey ; oyola2018a ) . Consequently, routes are planned a priori , and corrective actions, known as recourse strategies, are applied when realized conditions deviate from planned values ( dror1989 ; bastian1992 ) . Prominent examples include random travel times modeled by probabilistic distributions or random customer presence known as probabilistic VRP (PVRP) ( laporte1992 ; bertsimas1990 ) . Despite this extensive body of research, many existing public benchmarks for SVRP still rely on static assumptions, such as deterministic travel times, fixed customer availability, and unchanged route constraints, thus limiting their practical applicability and robustness evaluations, as shown in Table 1 . The Case for a Realistic SVRP Benchmark. Urban logistics operates under dynamic and uncertain conditions, yet most existing benchmarks fail to reflect this complexity. Practical routing systems must account for peak-hour congestion, random incidents like accidents, and diverse delivery preferences across customer types ( hvattum2006 ; bent2004 ; peric2024adaptive ) . Ignoring these factors leads to overly optimistic performance assessments and misdirects algorithmic development toward unrealistic assumptions ( adulyasak2016 ) . Our Contributions. To address these gaps, we introduce SVRPBench , a novel, open-source benchmark suite for the Stochastic Vehicle Routing Problem (SVRP), designed to simulate realistic logistics scenarios with embedded uncertainty. Our key contributions include: • Stochastic Realism. We model time-dependent congestion using Gaussian mixtures, inject log-normal delays and probabilistic accidents ( laporte1992 ) , and generate customer time windows from empirical residential and commercial distributions. • Constraint-Rich Instance Generation. Our framework supports multi-depot and multi-vehicle setups, strict capacity constraints, and diverse time window widths, all grounded in spatially realistic demand distributions. • Diverse Baseline Evaluation. We benchmark classical heuristics (e.g., Nearest Neighbor, 2-opt), metaheuristics (e.g., ACO, Tabu Search ( gendreau1996tabu ; chepuri2005 ) ), industrial solvers (OR-Tools ortools , LKH3 lkh3 ), and learning-based methods (AM kool2018attention , POMO kwon2020pomo ), highlighting how stochastic conditions affect solution quality, feasibility, and robustness. • Open Community Platform. We release datasets, solvers, and evaluation scripts through a public repository to support reproducibility and foster future contributions. By advancing realism and accessibility in SVRP benchmarking, SVRPBench aims to accelerate the development of robust, deployable routing algorithms suited for real-world logistics. 2 Realistic Stochastic Modeling A core contribution of SVRPBench is its simulation of real-world uncertainty in urban-scale logistics. Classical VRP benchmarks often assume static travel times and rigid customer schedules ( gendreau1996 ) , overlooking time-varying conditions and operational stochasticity. Informed by empirical and theoretical literature ( bent2004 ; hvattum2006 ; adulyasak2016 ; oyola2018 ; peric2024 ; schrank2021 ; li2015 ; brilon2008 ; homeDeliveryFedex2020 ; bringlogistics2021 ) , our benchmark introduces: (1) time-dependent congestion, (2) stochastic travel time delays, (3) accident-induced disruptions, and (4) customer-specific time window distributions. 2.1 Time-Dependent Travel Time Modeling We model the travel time from node a to b at time t as: \textstyle T(a,b,t)=\frac{D(a,b)}{V}+B(a,b,t)\cdot R(t)+I_{\text{accidents}}(t)\cdot D_{\text{accident}}, (1) where D(a,b) is Euclidean distance and V is average road speed. The congestion factor B(a,b,t) is defined as: \textstyle B(a,b,t)=\alpha\cdot F_{\text{time}}(t)\cdot F_{\text{distance}}(D(a,b)), (2) with: \displaystyle\textstyle F_{\text{time}}(t) \displaystyle=\beta+\gamma\cdot\left[f(t;\mu_{\text{morning}},\sigma_{\text{peak}})+f(t;\mu_{\text{evening}},\sigma_{\text{peak}})\right], (3) \displaystyle f(t;\mu,\sigma) \displaystyle=\frac{1}{\sigma\sqrt{2\pi}}e^{-\frac{1}{2}\left(\frac{t-\mu}{\sigma}\right)^{2}}, (4) \displaystyle F_{\text{distance}}(D) \displaystyle=1-e^{-D/\lambda_{\text{dist}}}, (5) where the Gaussian peaks around \mu_{\text{morning}}=8 and \mu_{\text{evening}}=17 ( \sigma_{peak}=1.5 ) align with observed urban traffic congestion patterns ( schrank2021 ) . The distance decay \lambda_{\text{dist}}=50 modulates slowdown severity, reflecting empirical findings that longer trips are more likely to encounter congestion ( brilon2008 ) . The multiplicative stochastic delay R(t) is drawn from a log-normal distribution: \displaystyle\textstyle\mu(t) \displaystyle=\mu_{\text{base}}+\delta\cdot\left[f(t;\mu_{\text{morning}},\sigma_{\text{peak}})+f(t;\mu_{\text{evening}},\sigma_{\text{peak}})\right], (6) \displaystyle\sigma(t) \displaystyle=\sigma_{\text{base}}+\epsilon\cdot\left[f(t;\mu_{\text{morning}},\sigma_{\text{peak}})+f(t;\mu_{\text{evening}},\sigma_{\text{peak}})\right], (7) \displaystyle R(t) \displaystyle\sim\text{LogNormal}(\mu(t),\sigma(t)), (8) reflecting both the skewed and bursty nature of traffic delays ( li2015 ; brilon2008 ) . Baseline values \mu_{\text{base}}=0 and \sigma_{\text{base}}=0.3 reflect free-flow conditions, while \delta=0.1 and \epsilon=0.2 capture peak-hour amplification. Accident delays are modeled using a time-inhomogeneous Poisson process: \displaystyle\textstyle\lambda(t) \displaystyle=\lambda_{\text{scale}}\cdot f(t;\mu_{\text{night}},\sigma_{\text{acc}}), (9) \displaystyle I_{\text{accidents}}(t) \displaystyle\sim\text{Poisson}(\lambda(t)), (10) \displaystyle D_{\text{accident}} \displaystyle\sim U(d_{\text{min}},d_{\text{max}}), (11) where accidents peak around \mu_{\text{night}}=21 ( \sigma_{acc}=2 ) due to elevated nighttime risks from fatigue and impaired driving ( mutcd2009 ) . The delay duration is drawn from U(0.5,2.0) hours, consistent with industry reports on incident clearance times ( mutcd2009 ) . 2.2 Customer Time Window Sampling Residential and commercial customers exhibit different temporal availability patterns ( oyola2018 ; bringlogistics2021 ) . For residential profiles, delivery windows are sampled from a bimodal Gaussian mixture: T_{\text{start}}\sim\begin{cases}\mathcal{N}(\mu_{\text{res,morning}},\sigma_{\text{res,morning}}^{2}),&\text{w.p. }0.5,\\ \mathcal{N}(\mu_{\text{res,evening}},\sigma_{\text{res,evening}}^{2}),&\text{w.p. }0.5,\end{cases} (12) where \mu_{\text{res,morning}}=480 (8:00 AM) and \mu_{\text{res,evening}}=1140 (7:00 PM), with variances \sigma=90 and 120 mins, respectively, aligning with common parcel service offerings such as FedEx and Bring ( homeDeliveryFedex2020 ; bringlogistics2021 ) . The window duration is drawn from: W_{\text{length}}\sim U(w_{\min},w_{\max}),\quad T_{\text{start}}=\max(0,\min(T_{\text{start}},1440-W_{\text{length}})). (13) Commercial customers follow a single-mode Gaussian: T_{\text{start}}\sim\mathcal{N}(\mu_{\text{com}},\sigma_{\text{com}}^{2}),\quad W_{\text{length}}\sim U(w_{\min},w_{\max}^{\text{com}}), (14) with \mu_{\text{com}}=780 (1:00 PM), \sigma_{\text{com}}=60 , and w_{\max}^{\text{com}}=120 minutes, reflecting standard daytime business hours and delivery norms ( vanDuin2016 ) .

Read the complete text