Medical Supply Distribution
Capacitated Vehicle Routing
Healthcare · Home · Offline-op Canonical method: CVRPA regional medical depot must deliver medications, vaccines, and consumables to 18 rural clinics using refrigerated vans. The WHO estimates up to 50% of vaccines are wasted due to cold-chain failures during last-mile transport. Route optimization reduces cold-chain exposure by 20–35% and fuel costs by 15–25%.
Where This Decision Fits
Healthcare operations chain — the highlighted step is what this page optimizes
Problem Definition
Mapping the real-world medical logistics problem to a CVRP formulation
| Real-World Element | CVRP Abstraction | Description |
|---|---|---|
| Rural clinic | Customer node | 18 facilities requiring medical supplies |
| Refrigerated van | Vehicle | Homogeneous fleet, 500 kg capacity each |
| Supply demand (kg) | Load / demand | 15–120 kg per clinic, 915 kg total |
| Medical depot | Depot | Central hub at coordinates (50, 50) |
| Road distance | Edge cost | Euclidean distance (proxy for travel time) |
subject to
Σk Σj xijk = 1 /* every clinic visited exactly once */
Σi di · yik ≤ Q /* vehicle capacity Q = 500 kg */
Σj x0jk = Σj xj0k = 1 /* each vehicle starts and returns to depot */
xijk ∈ {0, 1} /* binary assignment */
/* subtour elimination constraints (MTZ or SEC) */
Interactive Solver
Select a scenario, choose algorithms, and optimize delivery routes
Route Optimizer
| Clinic | X | Y | Demand | Type |
|---|
| Algorithm | Distance (km) | Vehicles | Cold-Chain (hr) | Time (ms) |
|---|
Solution Algorithms
Three approaches from constructive heuristics to metaheuristic search
Key Insight
Clarke-Wright Savings computes a savings value s(i,j) = d(0,i) + d(0,j) − d(i,j) for every pair of clinics, representing how much distance is saved by serving i and j on the same route instead of separate trips from the depot. Routes are merged greedily by decreasing savings — yielding near-optimal CVRP solutions in O(n² log n) time.
Clarke-Wright Savings
Constructive HeuristicThe classical CVRP heuristic from 1964. Starts with one route per clinic, then iteratively merges the two routes that yield the greatest distance savings, subject to vehicle capacity. Produces compact routes that minimize total distance.
- Initialize: create n individual depot→clinic→depot routes
- Compute savings s(i,j) = d(0,i) + d(0,j) − d(i,j) for all pairs
- Sort savings in decreasing order
- For each saving: merge routes if i and j are at route endpoints and merged demand ≤ Q
- Return remaining routes
Sweep Algorithm
Constructive HeuristicGillett & Miller (1974). Sorts clinics by their polar angle relative to the depot, then “sweeps” around adding clinics to the current route until the vehicle capacity is reached. Simple and fast, especially effective when clinics are geographically clustered.
- Compute polar angle θi = atan2(yi−y0, xi−x0) for each clinic
- Sort clinics by increasing θ
- Sweep: add clinic to current route while demand ≤ Q
- When capacity exceeded, start a new route and continue sweep
Simulated Annealing
MetaheuristicA stochastic local-search method that explores the neighbourhood of a current solution by performing random swap and relocate moves. Worse solutions are accepted with probability e−Δ/T, allowing escape from local optima. Temperature T decreases over iterations, gradually focusing the search.
- Start from Clarke-Wright solution as initial state
- Generate neighbour by swap (within route) or relocate (between routes)
- Accept if better; accept worse with probability e−Δ/T
- Cool: T ← T × α (cooling rate 0.9995)
- Repeat for N iterations; return best solution found
Real-World Complexity
Factors that extend the textbook CVRP in pharmaceutical logistics
Cold Chain
Vaccines require 2–8°C throughout transport. Total route duration directly impacts cold-chain integrity. WHO reports up to 50% wastage from temperature excursions during last-mile delivery.
Heterogeneous Demand
Hospitals need 85–120 kg; health posts need 15–25 kg. Demand variance makes bin-packing within vehicle capacity non-trivial and affects route balance across the fleet.
Road Quality
Rural roads may be unpaved, seasonal, or flood-prone. Euclidean distance underestimates actual travel time. Real deployments use road-network distances and seasonal accessibility matrices.
Multi-Compartment
Controlled substances, frozen vaccines, and ambient consumables require separate compartments. This extends CVRP to multi-compartment VRP (MCVRP) with per-compartment capacity constraints.
Time Sensitivity
Emergency resupply for antivenoms or blood products requires time-window constraints (CVRPTW). Priority clinics may need guaranteed delivery within 2–4 hours of dispatch.
Two lenses on the same decision
Medical supply distribution sits at the intersection of two complementary frameworks. On the primary Hulshof (2012) care-service matrix, it occupies Home × Offline-operational because the end consumer is the patient at home or in a rural clinic. On the Hans (2012) managerial-area lens, it occupies Materials planning × Offline-operational because the decision variable is consumables (drugs, vaccines, supplies), not renewable care capacity.
The CVRP on this page captures the logistics side of that overlap. Upstream sit pharmaceutical inventory policies (s, S) and lot-sizing (Wagner–Whitin); downstream sit stochastic stockout constraints at the clinic. The repository’s routing family page documents the full CVRP algorithm bestiary.
Academic References
- (1964). Seminal “Scheduling of vehicles from a central depot to a number of delivery points.” Operations Research, 12(4), 568–581. doi:10.1287/opre.12.4.568 — the savings algorithm underlying the solver on this page.
- (2009). Survey “Fifty years of vehicle routing.” Transportation Science, 43(4), 408–416. doi:10.1287/trsc.1090.0301
- (Eds.). (2014). Textbook Vehicle Routing: Problems, Methods, and Applications (2nd ed.). SIAM. doi:10.1137/1.9781611973594 — the canonical CVRP reference; covers MCVRP and CVRPTW variants flagged in this page’s complexity notes.
- (2014). Survey “The top ten global health supply chain issues: Perspectives from the field.” Operations Research for Health Care, 3(4), 226–230. doi:10.1016/j.orhc.2014.09.002
- (2020). Applied “The roadside healthcare facility location problem: A managerial network design challenge.” Production and Operations Management, 29(5), 1165–1187. doi:10.1111/poms.13152
- (2015). Report “Achieving immunization targets with the comprehensive effective vaccine management (EVM) framework.” World Health Organization / UNICEF. apps.who.int/iris/handle/10665/204382 — cold-chain management and vaccine-wastage benchmarks referenced in the hero text.
- (2018). Applied “Application of hierarchical facility location problem for optimization of a drone delivery system: A case study of Amazon Prime Air in the city of San Francisco.” International Journal of Advanced Manufacturing Technology, 95, 3141–3153. doi:10.1007/s00170-017-1363-1 — speculative drone-delivery extension relevant to medical supply in underserved areas.
- (2012). Taxonomy “Taxonomic classification of planning decisions in health care: A structured review of the state of the art in OR/MS.” Health Systems, 1(2), 129–175. doi:10.1057/hs.2012.18 — this page sits at Home × Offline-operational (primary delivery cell) in the Hulshof taxonomy and simultaneously at Materials × Offline-operational in the Hans (2012) managerial-area framework.
Explore More Applications
This medical supply routing demo is part of a comprehensive library of optimization models across healthcare, agriculture, manufacturing, and logistics.