Route and waypoint planning

Example 1 Ordering 10 inspection points

Coordinates are metres east and north of the take-off point H.

import math

pts = {"H": (0, 0), "P1": (420, 150), "P2": (900, -200), "P3": (1300, 400), "P4": (700, 800),
       "P5": (250, 1100), "P6": (-300, 900), "P7": (-600, 300), "P8": (-400, -500),
       "P9": (300, -700), "P10": (1100, -900)}

def dist(a, b):
    return math.dist(pts[a], pts[b])

def length(route):
    return sum(dist(route[i], route[i + 1]) for i in range(len(route) - 1))

left, route = [k for k in pts if k != "H"], ["H"]
while left:                                    # nearest neighbour
    nxt = min(left, key=lambda k: dist(route[-1], k))
    route.append(nxt)
    left.remove(nxt)
route.append("H")
print(f"nearest neighbour: {length(route):.0f} m  {'-'.join(route)}")

improved = True
while improved:                                # 2-opt
    improved = False
    for i in range(1, len(route) - 2):
        for j in range(i + 1, len(route) - 1):
            cand = route[:i] + route[i:j + 1][::-1] + route[j + 1:]
            if length(cand) < length(route) - 1e-9:
                route, improved = cand, True
print(f"after 2-opt:       {length(route):.0f} m  {'-'.join(route)}")

nearest neighbour: 8078 m  H-P1-P2-P3-P4-P5-P6-P7-P8-P9-P10-H
after 2-opt:       7916 m  H-P1-P2-P10-P3-P4-P5-P6-P7-P8-P9-H

2-opt moves P10 to follow P2, which is close to it, instead of leaving it as the last point with a long flight home. The total distance falls only slightly in this case, but with more or more scattered points the difference is usually larger. Neither method guarantees the best answer, but both are fast enough for field work.

Example 2 Splitting the route by distance per sortie

The drone can fly at most 3,500 m per sortie after reserves. Use the order from Example 1 and add points in order until the limit would be exceeded.

import math

pts = {"H": (0, 0), "P1": (420, 150), "P2": (900, -200), "P3": (1300, 400), "P4": (700, 800),
       "P5": (250, 1100), "P6": (-300, 900), "P7": (-600, 300), "P8": (-400, -500),
       "P9": (300, -700), "P10": (1100, -900)}
order = ["P1", "P2", "P10", "P3", "P4", "P5", "P6", "P7", "P8", "P9"]   # from Example 1
L_MAX = 3500                                   # m per sortie

def length(route):
    return sum(math.dist(pts[route[i]], pts[route[i + 1]]) for i in range(len(route) - 1))

sorties, cur = [], ["H"]
for p in order:
    if length(cur + [p, "H"]) <= L_MAX:
        cur.append(p)
    else:
        sorties.append(cur + ["H"])
        cur = ["H", p]
sorties.append(cur + ["H"])
for k, s in enumerate(sorties, 1):
    print(f"sortie {k}: {'-'.join(s):<20} {length(s):5.0f} m")
print(f"{len(sorties)} sorties, total {sum(length(s) for s in sorties):.0f} m")

sortie 1: H-P1-P2-P10-H         3189 m
sortie 2: H-P3-P4-H             3144 m
sortie 3: H-P5-P6-P7-H          3055 m
sortie 4: H-P8-P9-H             2130 m
4 sorties, total 11518 m

Splitting increases the total distance because the drone must return to the take-off point several times. This in-order split is simple but not optimal. To seriously reduce the number of sorties or the total distance, use vehicle routing methods, which consider the split and the order together.