วางแผนเส้นทางและ waypoint

ตัวอย่างที่ 1 จัดลำดับ 10 จุดตรวจ

พิกัดเป็นเมตรตะวันออกและเหนือจากจุดขึ้นบิน 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:                                    # เพื่อนบ้านใกล้สุด
    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 ย้าย P10 ไปบินต่อจาก P2 ซึ่งอยู่ใกล้กัน แทนที่จะทิ้งไว้เป็นจุดสุดท้ายแล้วบินกลับไกล ระยะรวมลดลงเล็กน้อยในกรณีนี้ แต่เมื่อจุดมากขึ้นหรือกระจายกว่านี้ ส่วนต่างมักมากขึ้น ทั้งสองวิธีไม่รับประกันคำตอบดีที่สุด แต่เร็วพอสำหรับงานภาคสนาม

ตัวอย่างที่ 2 แบ่งเส้นทางตามระยะต่อเที่ยว

โดรนบินได้ไม่เกิน 3,500 m ต่อเที่ยวหลังหักพลังงานสำรอง ใช้ลำดับจากตัวอย่างที่ 1 แล้วเติมจุดตามลำดับจนกว่าจะเกิน

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"]   # จากตัวอย่างที่ 1
L_MAX = 3500                                   # m ต่อเที่ยว

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

การแบ่งทำให้ระยะรวมเพิ่มขึ้น เพราะต้องบินกลับจุดขึ้นบินหลายครั้ง วิธีแบ่งตามลำดับแบบนี้ง่ายแต่ไม่ดีที่สุด ถ้าต้องการลดจำนวนเที่ยวหรือระยะรวมจริงจัง ต้องใช้วิธีจัดเส้นทางยานพาหนะ (vehicle routing) ซึ่งพิจารณาการแบ่งกับลำดับพร้อมกัน