Medical Supply Distribution
Capacitated Vehicle Routing
A 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.
Academic References
- (2009). "Fifty years of vehicle routing." Computers & Operations Research, 36(11), 2927–2936. DOI: 10.1016/j.cor.2008.04.007
- (2018). "Application of hierarchical facility location problem for optimization of a drone delivery system." International Journal of Advanced Manufacturing Technology, 95, 3141–3153. DOI: 10.1007/s00170-017-1363-1
- (2014). "Temperature sensitivity of vaccines." WHO/IVB/06.10.
Explore More Applications
This medical supply routing demo is part of a comprehensive library of optimization models across healthcare, agriculture, manufacturing, and logistics.