Оптимальний маршрут дронів — задача комівояжера злітає у повітря

1. Формалізація задачі

Маючи n точок маршруту та функцію відстані (або енергетичної вартості) між кожною парою, TSP запитує найкоротший замкнений тур, що відвідує кожну точку рівно один раз і повертається до старту:

2. Чому це складно: обчислювальна складність

TSP є NP-складною задачею: жоден відомий алгоритм не розв'язує кожен екземпляр за поліноміальний від n час, і більшість дослідників вважають, що такого алгоритму не існує (гіпотеза P ≠ NP). Точні методи існують, але погано масштабуються:

• Повний перебір: O(n!) — нездійсненно вже при n ≈ 12.
• Динамічне програмування Хелда-Карпа: O(n² · 2ⁿ) — точний, але обмежений пам'яттю приблизно до n ≈ 20-25 точок.
• Метод гілок і меж / ILP (розв'язувач Concorde): може розв'язати реальні екземпляри з тисячами міст за достатнього часу, використовуючи січні площини та LP-релаксацію.
• Практичні місії дронів (10-200 точок, перепланування в реальному часі через зміни вітру чи заряду батареї) вимагають евристик, що повертають майже оптимальні тури за мілісекунди.

3. Конструктивні евристики

Швидкі евристики будують прийнятний початковий тур, зазвичай у межах 10-25% від оптимуму:

4. Локальний пошук: 2-opt і Or-opt

Починаючи з евристичного туру, локальний пошук повторно шукає малі зміни, що скорочують його:

5. Обмеження, специфічні для дронів

6. Генетичні алгоритми для маршрутизації флоту

Для флотів кількох дронів, що розподіляють точки між апаратами (задача маршрутизації транспорту, VRP — узагальнення TSP), генетичні алгоритми та рійні методи масштабуються краще за точні розв'язувачі:

7. JavaScript-оптимізатор маршруту 2-opt

// Локальний пошук 2-opt для туру точок дрона (евклідова 3D відстань)
function dist(a, b) {
  return Math.hypot(a.x-b.x, a.y-b.y, (a.z-b.z)*1.6); // підйом важить більше
}

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); // старт: тут міг би бути тур найближчого сусіда
  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 дахів доставки (x, y в метрах, z = висотний ешелон)
const waypoints = [
  {x:0,y:0,z:30}, {x:120,y:40,z:35}, {x:80,y:150,z:28} /* ...ще... */
];
const best = twoOpt(waypoints);
console.log(`Довжина оптимізованого маршруту: ${best.length.toFixed(0)} м`);

8. Реальні застосування