Energy-optimal BVLOS pathfinding for medical cargo drones — from shortest-path graphs to battery-constrained multi-stop delivery networks
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.
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
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.
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
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.
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
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.
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.
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.
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.