Оптимизация порядка точек

В Google Maps JavaScript API работа с маршрутами через DirectionsService включает задачу упорядочивания промежуточных точек (waypoints) для минимизации общего расстояния или времени в пути. Эта задача относится к классу NP-трудных задач маршрутизации, и в реальных сценариях решается приближёнными методами — как на стороне API, так и в пользовательской логике.

Базовая модель маршрута с промежуточными точками

Маршрут в Directions API задаётся через три ключевых компонента:

  • origin — начальная точка
  • destination — конечная точка
  • waypoints — промежуточные точки

Каждая промежуточная точка может быть фиксированной или оптимизируемой.

const request = {
  origin: "Almaty, Kazakhstan",
  destination: "Astana, Kazakhstan",
  waypoints: [
    { location: "Karaganda, Kazakhstan", stopover: true },
    { location: "Balkhash, Kazakhstan", stopover: true }
  ],
  travelMode: google.maps.TravelMode.DRIVING
};

Встроенная оптимизация порядка точек

Google Maps JavaScript API предоставляет параметр optimizeWaypoints, который включает автоматическую перестановку промежуточных точек для сокращения общего маршрута.

const request = {
  origin: "Almaty",
  destination: "Astana",
  waypoints: [
    { location: "Balkhash", stopover: true },
    { location: "Karaganda", stopover: true }
  ],
  optimizeWaypoints: true,
  travelMode: google.maps.TravelMode.DRIVING
};

После выполнения запроса API возвращает:

  • оптимизированный порядок индексов
  • перестроенный маршрут
directionsService.route(request, (result, status) => {
  if (status === "OK") {
    console.log(result.routes[0].waypoint_order);
  }
});

waypoint_order — массив индексов, отражающий новый порядок точек.

Принцип работы оптимизации

Внутри Google Maps JavaScript API используется эвристика, приближённая к задаче коммивояжёра (TSP). Алгоритм:

  • не гарантирует глобальный оптимум
  • использует матрицу расстояний между точками
  • применяет жадные и перестановочные эвристики
  • учитывает дорожную сеть, а не евклидово расстояние

Особенность: оптимизация выполняется только для промежуточных точек, origin и destination остаются фиксированными.

Ограничения встроенной оптимизации

Использование optimizeWaypoints имеет ряд ограничений:

  • максимальное число waypoint ограничено (зависит от тарифа API)
  • рост сложности вычислений при увеличении точек
  • невозможность контроля алгоритма оптимизации
  • отсутствие поддержки пользовательских весов (например, приоритетов точек)

При большом количестве точек результат может быть субоптимальным.

Построение матрицы расстояний

Для кастомной оптимизации используется Distance Matrix Service:

const service = new google.maps.DistanceMatrixService();

service.getDistanceMatrix({
  origins: points,
  destinations: points,
  travelMode: google.maps.TravelMode.DRIVING
}, callback);

Результат — матрица расстояний N × N, которая используется для построения маршрута.

Жадный алгоритм ближайшего соседа

Один из базовых методов оптимизации порядка:

function nearestNeighbor(points, startIndex = 0) {
  const visited = new Array(points.length).fill(false);
  const order = [startIndex];
  visited[startIndex] = true;

  for (let i = 1; i < points.length; i++) {
    const last = order[order.length - 1];
    let nearest = -1;
    let bestDist = Infinity;

    for (let j = 0; j < points.length; j++) {
      if (!visited[j] && distance[last][j] < bestDist) {
        bestDist = distance[last][j];
        nearest = j;
      }
    }

    order.push(nearest);
    visited[nearest] = true;
  }

  return order;
}

Характеристики:

  • низкая вычислительная сложность
  • быстрый результат
  • склонность к локальным минимумам

Улучшение маршрута методом 2-opt

После начального решения применяется локальная оптимизация:

  • выбираются две рёбра
  • выполняется их перестановка
  • проверяется уменьшение общего расстояния
function twoOpt(route) {
  let improved = true;

  while (improved) {
    improved = false;

    for (let i = 1; i < route.length - 2; i++) {
      for (let k = i + 1; k < route.length - 1; k++) {

        const newRoute = route.slice(0, i)
          .concat(route.slice(i, k + 1).reverse())
          .concat(route.slice(k + 1));

        if (cost(newRoute) < cost(route)) {
          route = newRoute;
          improved = true;
        }
      }
    }
  }

  return route;
}

Этот подход часто даёт более качественные маршруты, чем встроенная оптимизация.

Снижение количества API-запросов

Оптимизация порядка точек напрямую связана с экономией запросов к Google Maps JavaScript API:

  • предварительная агрегация точек
  • удаление дубликатов координат
  • кластеризация близких точек
  • кэширование Distance Matrix

Кластеризация может выполняться алгоритмами:

  • K-means
  • DBSCAN (для нерегулярных распределений)

Кластеризация маршрутов

При большом наборе точек маршрут разбивается на подзадачи:

  1. кластеризация точек по регионам
  2. оптимизация внутри кластера
  3. объединение кластеров в глобальный маршрут

Такой подход уменьшает сложность с O(n²) до нескольких меньших задач.

Приближённая глобальная оптимизация

Комбинированные стратегии:

  • nearest neighbor для начального решения
  • 2-opt или 3-opt для улучшения
  • случайные перестановки (simulated annealing)
function simulatedAnnealing(route, temp) {
  while (temp > 1) {
    const newRoute = swapRandom(route);
    if (acceptanceProbability(cost(route), cost(newRoute), temp) > Math.random()) {
      route = newRoute;
    }
    temp *= 0.99;
  }
  return route;
}

Ограничения точности дорожной модели

Оптимизация в Google Maps JavaScript API основана на:

  • реальной дорожной сети
  • актуальных данных трафика (если включено)
  • типе транспорта

Это приводит к особенностям:

  • асимметрия расстояний (A → B ≠ B → A)
  • зависимость от времени суток
  • изменение оптимального порядка в динамике

Параллельная оптимизация и батчинг

При большом количестве точек применяется:

  • разбиение массива на батчи
  • параллельные запросы Distance Matrix
  • агрегация промежуточных результатов

Это позволяет уменьшить задержки при построении маршрутов в интерфейсах реального времени.

Практическая структура обработки маршрута

Типичный pipeline:

  1. получение точек
  2. фильтрация и очистка данных
  3. построение матрицы расстояний
  4. первичная эвристика (nearest neighbor)
  5. локальная оптимизация (2-opt)
  6. отправка в DirectionsService
  7. визуализация результата на карте

Оптимизация визуализации маршрута

После вычисления порядка точек важна оптимизация рендера:

  • использование Polyline encoding
  • снижение количества сегментов линии
  • отключение лишних маркеров
  • переиспользование объектов google.maps.Marker

Масштабирование на большие наборы точек

При росте числа точек применяются ограничения:

  • ограничение глубины оптимизации
  • сокращение числа перестановок
  • предварительное ранжирование по географической близости
  • использование серверной предобработки

Итеративное улучшение маршрута

В системах логистики маршрут часто пересчитывается динамически:

  • добавление новых точек
  • удаление устаревших
  • перераспределение порядка без полного пересчёта

Это снижает нагрузку на Google Maps JavaScript API и улучшает отзывчивость интерфейса.

Оглавление