Routing

Example 1. Exhaustive search versus nearest neighbour

Assumed coordinates in kilometres; H is the hospital.

import math
from itertools import permutations

SITES = {"H": (0, 0), "A": (1.0, 2.5), "B": (1.5, 0.0), "C": (-2.0, 1.0), "D": (4.0, 0.5)}

def length(order):
    stops = ["H", *order, "H"]
    return sum(math.dist(SITES[a], SITES[b]) for a, b in zip(stops, stops[1:]))

best = min(permutations("ABCD"), key=length)

current, left, greedy = "H", set("ABCD"), []
while left:
    nxt = min(sorted(left), key=lambda s: math.dist(SITES[current], SITES[s]))
    greedy.append(nxt)
    left.remove(nxt)
    current = nxt

print(f"exhaustive: H-{'-'.join(best)}-H = {length(best):.2f} km")
print(f"nearest neighbour: H-{'-'.join(greedy)}-H = {length(greedy):.2f} km "
      f"(+{length(greedy) / length(best) - 1:.0%})")

exhaustive: H-B-D-A-C-H = 13.25 km
nearest neighbour: H-B-A-C-D-H = 17.46 km (+32%)

Nearest neighbour starts well at B but gets stuck at C on the left, then has to fly far across to D on the right, ending about a third longer than the best answer. Heuristics should always be checked against better solutions where possible.

Example 2. Energy check and splitting into two trips

Assume 33.3 Wh/km with a 2 kg payload, a 500 Wh battery with 80% usable, and a 20% reserve.

import math
from itertools import combinations, permutations

SITES = {"H": (0, 0), "A": (1.0, 2.5), "B": (1.5, 0.0), "C": (-2.0, 1.0), "D": (4.0, 0.5)}
WH_PER_KM, BATTERY_WH, USABLE, RESERVE = 33.3, 500, 0.8, 0.2
available = BATTERY_WH * USABLE * (1 - RESERVE)

def best_trip(stops):
    def km(order):
        path = ["H", *order, "H"]
        return sum(math.dist(SITES[a], SITES[b]) for a, b in zip(path, path[1:]))
    order = min(permutations(stops), key=km)
    return order, km(order)

order, km = best_trip("ABCD")
print(f"available {available:.0f} Wh; one trip {km:.2f} km needs {km * WH_PER_KM:.0f} Wh "
      f"-> {'OK' if km * WH_PER_KM <= available else 'NOT feasible'}")

plans = []
for pair in combinations("ABCD", 2):
    other = "".join(s for s in "ABCD" if s not in pair)
    trips = [best_trip(pair), best_trip(other)]
    if all(k * WH_PER_KM <= available for _, k in trips):
        plans.append((sum(k for _, k in trips), trips))
total, trips = min(plans)
for o, k in trips:
    print(f"trip H-{'-'.join(o)}-H: {k:.2f} km, {k * WH_PER_KM:.0f} Wh")
print(f"two trips total {total:.2f} km")

available 320 Wh; one trip 13.25 km needs 441 Wh -> NOT feasible
trip H-A-C-H: 8.28 km, 276 Wh
trip H-B-D-H: 8.08 km, 269 Wh
two trips total 16.36 km

A single trip to all four stops needs more energy than is available, so the work is split into two trips. The best pairing is B with D and A with C. The total distance is about 23% longer than one trip, but every trip keeps its full reserve. In strong headwind the energy per kilometre rises, so recalculate before every flight.