Optimal Drone Routing — The Travelling Salesman Problem Takes Flight

1. Formalizing the Problem

Given n waypoints and a distance (or energy-cost) function between each pair, TSP asks for the shortest closed tour visiting every waypoint exactly once and returning to the start:

2. Why It's Hard: Complexity

TSP is NP-hard: no known algorithm solves every instance in time polynomial in n, and most researchers believe none exists (P ≠ NP conjecture). Exact methods exist but scale poorly:

• Brute force: O(n!) — infeasible beyond n ≈ 12.
• Held-Karp dynamic programming: O(n² · 2ⁿ) — exact, but memory-bound to roughly n ≈ 20-25 waypoints.
• Branch-and-bound / ILP (Concorde solver): can solve real instances with thousands of cities given enough time, using cutting planes and LP relaxation.
• Practical drone missions (10-200 waypoints, re-planned in real time for wind/battery changes) demand heuristics that return near-optimal tours in milliseconds.

3. Construction Heuristics

Fast heuristics build a reasonable starting tour, typically within 10-25% of optimal:

4. Local Search: 2-opt and Or-opt

Starting from a heuristic tour, local search repeatedly finds small changes that shorten it:

5. Drone-Specific Constraints

6. Genetic Algorithms for Fleet Routing

For multi-drone fleets splitting waypoints among vehicles (the vehicle routing problem, VRP — a generalisation of TSP), genetic algorithms and swarm methods scale better than exact solvers:

7. JavaScript 2-opt Route Optimizer

// 2-opt local search for drone waypoint tour (Euclidean 3D distance)
function dist(a, b) {
  return Math.hypot(a.x-b.x, a.y-b.y, (a.z-b.z)*1.6); // climb weighted higher
}

function tourLength(tour, pts) {
  let total = 0;
  for (let i = 0; i < tour.length; i++) {
    total += dist(pts[tour[i]], pts[tour[(i+1) % tour.length]]);
  }
  return total;
}

function twoOpt(pts) {
  let tour = pts.map((_, i) => i); // start: nearest-neighbour tour would go here
  let improved = true;
  while (improved) {
    improved = false;
    for (let i = 0; i < tour.length - 1; i++) {
      for (let j = i + 2; j < tour.length; j++) {
        const a = pts[tour[i]], b = pts[tour[i+1]];
        const c = pts[tour[j]], d = pts[tour[(j+1) % tour.length]];
        const before = dist(a,b) + dist(c,d);
        const after  = dist(a,c) + dist(b,d);
        if (after < before - 1e-9) {
          const seg = tour.slice(i+1, j+1).reverse();
          tour = [...tour.slice(0, i+1), ...seg, ...tour.slice(j+1)];
          improved = true;
        }
      }
    }
  }
  return { tour, length: tourLength(tour, pts) };
}

// 12 delivery rooftops (x, y in metres, z = altitude band)
const waypoints = [
  {x:0,y:0,z:30}, {x:120,y:40,z:35}, {x:80,y:150,z:28} /* ...more... */
];
const best = twoOpt(waypoints);
console.log(`Optimized route length: ${best.length.toFixed(0)} m`);

8. Real-World Applications