🚁 Medical Drone Delivery Route Optimization Simulator

Modeling the Medical Delivery Network as a Constrained Weighted Graph

Route optimization for medical cargo drones begins by encoding the physical service area — hub, clinics, terrain, and airspace restrictions — as a directed weighted graph. Zipline's network in Rwanda operates from two distribution centers (Muhanga and Kayonza) covering the entire country with a combined service radius that puts 12 million people within a ~30-minute flight of blood products, vaccines, and essential medicines. Each candidate flight corridor is represented as a graph edge whose weight will later be redefined by distance, energy, or multi-stop cost depending on the optimization stage.

• ~100%: Zipline Rwanda coverage (national population, since 2016)
• 65–80 km: Nest service radius (one-way, Zip cargo fixed-wing)
• 6 centers: Ghana network nests (covering ~2,000 health facilities)
• 150–500: Graph nodes (typical) (clinics + waypoints per country)

Graph construction: nodes, edges, and airspace constraints

Building the routable network for a national medical drone service requires layering several geospatial datasets:

Node types: • Hub/nest nodes: distribution centers with cold-chain storage, launch catapults, and net-recovery landing systems (Zipline Gen2 "Zip" platform) • Clinic nodes: rural health posts, district hospitals — geocoded delivery drop points, typically parachute-delivered from 30–60m AGL • Waypoint nodes: intermediate corridor markers used to shape flight paths around terrain and restricted airspace • Alternate/divert nodes: emergency landing sites pre-surveyed for automated contingency recovery

Edge weight — geometric baseline: • Great-circle (haversine) distance between node pairs, adjusted for terrain-following altitude profile (SRTM 30m DEM) • Rwanda's terrain (hills up to 1.5 km relief) adds 8–15% effective distance vs. flat-earth calculation

Airspace constraint layers: • No-fly polygons: 5 km radius around Kigali International Airport, military installations, and international borders • Temporary restrictions (NOTAMs): weather cells, VIP movements, other UAV operations sharing the corridor • Visibility-graph pruning: any candidate edge crossing a restricted polygon is removed or re-routed around polygon vertices with a small buffer margin (typically 200–500m)

Regulatory basis: • Rwanda Civil Aviation Authority (RCAA) BVLOS operational approval — first national-scale BVLOS medical drone authorization, 2016 • Comparable frameworks: FAA Part 135 air carrier certificate (Zipline's U.S. Salt Lake City, Arkansas, North Carolina operations), EASA U-space regulatory framework (EU 2021/664) for U-space airspace in Europe • Ghana Civil Aviation Authority certification for the 2019-launched 6-nest national network, the largest drone delivery network in the world at the time of launch

Graph size in production: • Typical national deployment: 150–500 delivery nodes, 2–6 hub nodes, edge count scales combinatorially but is pruned to k-nearest-neighbor corridors (k≈15) plus all direct hub-to-clinic edges for tractable real-time solving

Dijkstra and A* — The Baseline Shortest-Distance Router

The simplest routing strategy minimizes geometric distance using classical graph search: Dijkstra's algorithm or its heuristic-accelerated variant, A*. This produces the fastest point-to-point corridor but ignores energy cost entirely — a critical omission for battery-limited aircraft where a shorter path directly into a strong headwind can consume more energy than a longer path that avoids it.

• O((V+E)logV): Dijkstra complexity (binary-heap priority queue)
• 3–8×: A* speedup vs Dijkstra (with admissible haversine heuristic)
• 20–65 km: Typical corridor length (one-way, single clinic delivery)
• <50 ms: Solve time (500 nodes) (onboard flight computer, single-query)

Shortest-path algorithm mechanics and its limitations for aerial routing

Dijkstra's algorithm:

• Maintains a priority queue of nodes ordered by tentative distance from the source (hub) • Repeatedly extracts the minimum-distance unvisited node, relaxes all outgoing edges • Guarantees globally optimal shortest path for non-negative edge weights • Runtime O((V+E) log V) with a binary heap — for a 500-node, ~7,500-edge network, solves in single-digit milliseconds

A* enhancement: • Adds a heuristic function h(n) = haversine distance from node n to the goal clinic • Admissible heuristic (never overestimates true remaining cost) guarantees optimality is preserved • Explores far fewer nodes than plain Dijkstra by prioritizing search toward the goal — 3–8× fewer node expansions in typical corridor networks • Standard choice for real-time onboard re-planning where compute budget is constrained (ARM Cortex-A72-class flight computers)

Why pure shortest-distance routing is insufficient: • Distance ≠ energy: a 42.6 km direct corridor into a 12 m/s headwind can cost more battery than a 46 km corridor that routes through a wind-sheltered valley or exploits a tailwind segment • Ignores terrain-induced climb energy: a corridor crossing a 400m ridge costs disproportionately more Wh than the horizontal distance implies • No payload sensitivity: a fully loaded 1.75 kg blood/vaccine payload increases induced drag and reduces still-air range by roughly 15–20% versus an empty return leg

Operational use: • Shortest-path routing remains valuable as the fast default for short corridors (<25 km) in calm wind (<5 m/s) where the energy and distance-optimal solutions nearly coincide • Also used as the admissible-heuristic seed for the more expensive energy-cost re-solve in Stage 3

Battery-Aware Cost Functions — Routing on Watt-Hours, Not Kilometers

Energy-optimal routing replaces the static distance edge-weight with a dynamic Wh-consumption model that accounts for airspeed, wind vector, air density at cruise altitude, and payload mass. This is the routing mode that actually matters operationally: a fixed-wing hybrid VTOL medical drone like Zipline's Zip or Matternet's M2 has a hard, non-negotiable battery budget, and running out of charge over unlandable terrain is a mission-critical failure mode, not just a delay.

• ~100 km/h: Zip cruise airspeed (~28 m/s true airspeed)
• ~350 Wh: Usable battery energy (LiPo pack, hybrid VTOL fixed-wing)
• 1.75–2.5 kg: Max payload (blood units, vaccines, ARVs, snakebite antivenom)
• ~160 km: Round-trip range (no-wind, max payload one-way)

Energy consumption model and re-solving the graph on Wh cost

Per-edge energy cost function:

E(edge) = f(airspeed, wind_component, altitude_density, payload_mass, climb_delta)

Key terms: • Ground speed = airspeed ± wind component along heading; headwind increases time-on-edge and thus energy at fixed power draw • Power required scales roughly with the cube of airspeed for the aerodynamic (cruise) component, plus a near-constant hotel load for avionics, GPS, cellular/LTE telemetry link, and payload-bay servo • Payload mass linearly increases induced drag power in cruise flight; +1 kg of payload typically costs 3–6% additional range depending on airframe • Climb energy: potential energy mgh recovered only partially on descent (regenerative descent uncommon on fixed-wing cargo drones); ridge-crossing corridors penalized heavily

Re-solving with dynamic weights: • Same Dijkstra/A* graph search, but edge weight = predicted Wh rather than km • Because energy cost is direction-dependent (headwind ≠ tailwind), the graph effectively becomes asymmetric — edge(A→B) ≠ edge(B→A) in cost, unlike the purely geometric Stage 2 case • Result: energy-optimal path can be geometrically longer (e.g., 46.1 km vs. the 42.6 km shortest path) while consuming meaningfully less battery, by routing through wind-sheltered terrain or avoiding a ridge climb

Real-world validation: • Zipline reports typical delivery flights averaging 30 minutes hub-to-clinic across its Rwanda and Ghana networks, versus 4+ hours by road during rainy season when dirt roads become impassable • Matternet's M2 platform (Switzerland, UAE, US FAA-approved hospital campus operations) uses a comparable dynamic energy-cost router for its hospital-to-hospital lab sample network, targeting sub-30-minute STAT sample delivery • Reserve margin policy: operators typically require the energy-optimal solve to reserve ≥20% battery beyond the predicted mission cost before dispatch is authorized

Capacitated Vehicle Routing — Scheduling Multi-Clinic Milk-Run Deliveries

Routine resupply (vaccines, reagents, non-urgent blood stock rotation) rarely serves one clinic per flight — it is more efficient to sequence several stops in a single sortie, subject to the payload capacity limit and the aircraft's absolute range. This is a Capacitated Vehicle Routing Problem (CVRP), an NP-hard combinatorial optimization solved in practice with fast heuristics rather than exact methods, since dispatch decisions must be made in seconds, not hours.

• 1.75–2.5 kg: Payload capacity (per sortie, multi-parcel bay)
• 2–5: Typical stops/sortie (milk-run resupply flights)
• <200 ms: Clarke-Wright solve time (for 20-clinic candidate set)
• 4 continents: Swoop Aero network (Vanuatu, Malawi, DRC, Australia)

CVRP formulation and the Clarke-Wright savings heuristic

Problem formulation:

• One depot (hub/nest), n delivery clinics each with a demand vector (mass, volume, cold-chain requirement) • Vehicle capacity constraint: total sortie payload ≤ 1.75–2.5 kg depending on airframe variant • Range constraint: total tour energy (hub→stop1→stop2→...→hub) ≤ usable battery minus 20% safety reserve • Objective: minimize total energy (or, secondarily, total time) across all sorties required to serve the full demand set

Clarke-Wright savings algorithm: 1. Start with a separate round-trip route for every clinic (hub→clinic→hub) 2. Compute the "savings" of merging two routes: S(i,j) = cost(hub,i) + cost(hub,j) − cost(i,j) 3. Sort all pairwise savings descending; greedily merge routes when savings is positive AND the merge doesn't violate capacity or range constraints 4. Result: a good (not always optimal) set of multi-stop tours, computed in well under a second for realistic clinic counts (dozens per hub)

2-opt refinement: • After the greedy merge, a local-search pass swaps pairs of edges within each tour to eliminate path crossings • Typically improves the Clarke-Wright solution by 3–8% additional distance/energy reduction • Iterated until no improving swap is found or a time budget (≈150 ms) expires

Operational examples: • Zipline's Muhanga, Rwanda nest routinely sequences multi-clinic vaccine resupply runs during scheduled morning dispatch windows, batching demand submitted the previous evening via the health-ministry ordering platform • Swoop Aero (Australia) has operated milk-run multi-stop immunization delivery networks in Vanuatu (2019, the first national vaccine drone network) and in Malawi and DR Congo under UNICEF/Gavi-funded programs, each sortie serving 2–4 island or rural outposts per flight • DHL Parcelcopter trials in Tanzania (2018, with WeRobotics) and Papua New Guinea tested multi-drop diagnostic sample collection loops feeding into a single return sortie to the central lab

Vaccine cold-chain integrity constrains stop sequencing: routes must be ordered so cumulative time-out-of-refrigeration for the earliest-loaded parcel never exceeds product-specific limits (e.g., certain reconstituted vaccines: 6–8 hours at ambient temperature) — the VRP solver treats this as an additional time-window constraint on top of payload and range.

In-Flight Contingency Replanning — Weather, NOTAMs, and Battery Abort Thresholds

A dispatched route is a plan, not a guarantee. Wind forecasts drift, a temporary no-fly NOTAM can appear mid-flight, and battery consumption can exceed prediction due to gustier-than-forecast headwinds. Production medical drone autopilots continuously monitor state-of-charge against the planned energy budget and are authorized to autonomously re-solve the route — or abort to the nearest safe recovery site — without waiting for ground operator confirmation, since a lost telemetry link cannot be allowed to become a lost aircraft.

• 20%: Battery abort threshold (reserve below which auto-divert triggers)
• every 2–5 s: Re-solve trigger interval (or on state-of-charge deviation >5%)
• 3–8 per corridor: Alternate landing sites (pre-surveyed net/parachute recovery zones)
• FAA Part 135: BVLOS waiver basis (+ Part 107 waiver stack, U.S. ops)

Contingency architecture: live re-planning and the safety envelope

Continuous monitoring loop:

• Onboard flight computer compares actual state-of-charge (from battery telemetry: voltage, current integration, cell temperature) against the pre-flight predicted consumption curve at each corridor waypoint • Deviation >5% from predicted triggers an immediate A* re-solve using current GPS position as the new source node and current battery reserve as the new energy budget • A fresh NOTAM or dynamically-reported restricted airspace polygon (received via cellular/LTE uplink where coverage exists, or pre-loaded conservative buffers where it doesn't) is treated identically to a graph edge deletion, forcing a re-route

Hard abort logic: • If, after re-solving, no route to either the original destination or a designated alternate can be completed within the remaining battery budget minus reserve margin, the autopilot commands an immediate divert to the nearest pre-surveyed alternate landing site • Alternate sites are net-recovery or parachute-drop zones surveyed during initial network deployment, typically 3–8 per major corridor, chosen for open terrain and minimal risk to people/property • 20% state-of-charge is a common industry abort threshold — analogous to manned-aviation fuel reserve requirements — below which continuing to the primary destination is disallowed regardless of remaining geometric distance

Regulatory and safety-case context: • U.S. operations (Zipline North Carolina/Arkansas, Matternet) operate under FAA Part 135 air carrier certification layered with Part 107 BVLOS waivers, requiring documented contingency procedures including lost-link behavior, geofencing, and auto-return/auto-land logic as part of the safety case • EASA U-space regulation (Implementing Regulation (EU) 2021/664) mandates comparable "U-space service" contingency management for European BVLOS drone corridors, including conflict management and emergency management services • Redundancy: dual GPS/GNSS receivers, independent barometric and radar altimetry, and a ballistic or net-recovery fallback are standard on certified medical cargo airframes so that a full propulsion or navigation failure — not just a low-battery scenario — still ends in a controlled, location-known landing rather than an uncontrolled crash

Zipline reports a completed-delivery rate exceeding 98% across hundreds of thousands of cumulative flights in Rwanda, Ghana, and U.S. operations, with the small residual fraction accounted for almost entirely by weather holds and pre-flight aborts rather than in-flight contingency landings — evidence that the layered re-routing and abort architecture keeps failures rare and, when they occur, controlled.