Two-Stage Stochastic Location–Routing for Vehicle–Drone Blood Delivery with Blood Compatibility-Based Substitution

Timely blood delivery, particularly the delivery of red blood cells (RBCs), is critical to emergency medical services (EMS), but supplies of specific blood types are often insufficient. To mitigate these shortages, we consider compatible substitution under the ABO-Rh transfusion rules, which allow selected donor blood types to meet compatible recipient demand when identical-type units are insufficient. We formulate a two-stage stochastic location–routing model for joint vehicle–drone blood delivery that minimizes the expected urgency-weighted average arrival time. In the first stage, the model selects cluster centers that serve as drone launch-and-recovery sites. In the second stage, it jointly determines vehicle routes, drone deliveries, and blood allocations after the uncertainty is revealed. We develop a problem-specific adaptive large neighborhood search (ALNS) to address the computational complexity arising from the interaction among location, routing, and compatible blood-allocation decisions. The numerical experiments yield three main findings: (i) ALNS achieves an average best-run deviation of 0.404% and a ten-run average deviation of 4.516% relative to exact benchmarks for small instances and best-known solutions for larger instances, while solving instances with up to 50 hospitals in under 19 s per run; (ii) full compatibility maintains 100% full-demand feasibility across all tested A+ shortage levels; and (iii) the exact value of the stochastic solution (VSS) is non-negative for the small instances, while heuristic VSS estimates indicate that stochastic planning becomes more valuable as demand uncertainty increases. These findings provide decision support for EMS blood delivery under supply shortages and operational uncertainty.