Расчет матрицы для множества точек

Матрица расстояний и времени между множеством точек в HERE Maps API

В экосистеме HERE Technologies ключевую роль в задачах логистики, маршрутизации и анализа пространственных данных играет построение матриц расстояний и времени. В контексте HERE Maps API матрица маршрутов представляет собой вычисление попарных значений между наборами точек отправления и назначения, где каждая пара описывается метриками вроде времени в пути, длины маршрута или стоимости проезда.

Матрица маршрутов формально представляет собой двумерную структуру:

  • строки — точки отправления (origins)
  • столбцы — точки назначения (destinations)
  • элементы — рассчитанные значения (distance, travel time, tolls, fuel cost и др.)

Для набора из N точек и M точек назначения формируется матрица размером N × M.

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

Matrix Routing API и его роль

В HERE реализован специализированный сервис Matrix Routing, который выполняет массовый расчет маршрутов значительно эффективнее, чем последовательные вызовы обычного routing API.

Использование матричного подхода критично в задачах:

  • оптимизация маршрутов доставки (Vehicle Routing Problem)
  • расчет зон доступности (isochrones approximation)
  • подбор ближайших объектов
  • кластеризация географических точек
  • анализ логистических цепочек

В отличие от поочередных запросов, матричный сервис использует внутреннюю оптимизацию графа дорожной сети и повторное использование промежуточных вычислений.

Типы матриц

В HERE API поддерживаются различные режимы построения матриц:

  1. Time matrix — время в пути между точками
  2. Distance matrix — расстояние по дорожной сети
  3. Cost matrix — комбинированная метрика (включая платные дороги, штрафы, ограничения)
  4. Truck-specific matrix — для грузового транспорта с учетом ограничений веса и габаритов

Каждый тип выбирается через параметры запроса.

Базовая структура запроса

В JavaScript взаимодействие с Matrix Routing API обычно осуществляется через HTTP-запросы к REST endpoint.

Пример базового запроса:

const apiKey = "YOUR_API_KEY";

const requestBody = {
  origins: [
    { lat: 52.5160, lng: 13.3779 },
    { lat: 52.5200, lng: 13.4050 }
  ],
  destinations: [
    { lat: 52.5206, lng: 13.3862 },
    { lat: 52.5170, lng: 13.3889 }
  ],
  regionDefinition: {
    type: "world"
  },
  routingMode: "fast",
  transportMode: "car"
};

fetch("https://matrix.router.hereapi.com/v8/matrix?apiKey=" + apiKey, {
  method: "POST",
  headers: {
    "Content-Type": "application/json"
  },
  body: JSON.stringify(requestBody)
})
  .then(res => res.json())
  .then(data => {
    console.log(data.matrix);
  })
  .catch(err => console.error(err));

В ответе возвращается структура матрицы, где каждая ячейка содержит время и/или расстояние.

Формат ответа и структура данных

Ответ Matrix API обычно включает:

  • matrix.entries — список результатов
  • travelTimes — матрица времени
  • distances — матрица расстояний
  • errorCodes — коды ошибок для отдельных пар

Пример логической структуры:

{
  "matrix": {
    "numOrigins": 2,
    "numDestinations": 2,
    "distances": [1200, 2300, 1500, 900],
    "travelTimes": [180, 320, 200, 140]
  }
}

Матрица может быть представлена в виде плоского массива, где индекс рассчитывается как:

index = originIndex * numDestinations + destinationIndex

Логика расчета и оптимизация

При увеличении количества точек возникает квадратичная сложность O(n²). Для снижения нагрузки HERE применяет несколько механизмов:

1. Пакетная обработка

Запросы автоматически группируются в батчи, особенно при больших наборах координат.

2. Асинхронные вычисления

Для крупных матриц используется асинхронный режим:

  • отправка задания
  • получение jobId
  • опрос статуса
  • получение результата

3. Кэширование сегментов графа

Повторяющиеся участки маршрутов (например, общие дороги между точками) не пересчитываются полностью.

Асинхронный расчет больших матриц

Для больших наборов точек используется job-based модель:

async function createMatrixJob() {
  const response = await fetch(
    "https://matrix.router.hereapi.com/v8/matrix?async=true&apiKey=" + apiKey,
    {
      method: "POST",
      headers: { "Content-Type": "application/json" },
      body: JSON.stringify({
        origins: largeOriginsArray,
        destinations: largeDestinationsArray,
        transportMode: "truck"
      })
    }
  );

  const job = await response.json();
  return job.jobId;
}

Далее выполняется polling:

async function pollJob(jobId) {
  while (true) {
    const res = await fetch(
      `https://matrix.router.hereapi.com/v8/matrix/${jobId}?apiKey=${apiKey}`
    );

    const data = await res.json();

    if (data.status === "completed") {
      return data.result;
    }

    await new Promise(r => setTimeout(r, 2000));
  }
}

Ограничения и практические особенности

При проектировании систем необходимо учитывать ограничения:

  • максимальное число точек в одном запросе
  • ограничение на количество элементов матрицы
  • лимиты API по скорости запросов
  • различия между режимами car, truck, pedestrian

Особенно важно учитывать, что грузовой режим значительно увеличивает время вычислений из-за дополнительных ограничений (вес, высота, тип дорог).

Использование в задачах оптимизации маршрутов

Матрица является базой для алгоритмов:

  • алгоритм ближайшего соседа (Nearest Neighbor)
  • жадные эвристики VRP
  • k-means кластеризация с географическим расстоянием
  • построение графов доступности складов и точек доставки

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

function findNearest(originIndex, matrix) {
  const rowSize = matrix.numDestinations;
  let minIndex = -1;
  let minTime = Infinity;

  for (let i = 0; i < rowSize; i++) {
    const time = matrix.travelTimes[originIndex * rowSize + i];

    if (time < minTime) {
      minTime = time;
      minIndex = i;
    }
  }

  return minIndex;
}

Обработка ошибок и непроходимых маршрутов

В реальных дорожных графах некоторые пары точек могут быть недостижимы. В таких случаях API возвращает:

  • NO_ROUTE
  • ROUTE_NOT_FOUND
  • TIMEOUT
  • INVALID_INPUT

Такие значения должны быть обработаны на уровне приложения, иначе матрица теряет целостность.

Пример фильтрации:

if (travelTime === null || travelTime === 0) {
  // точка недостижима
  continue;
}

Производственные сценарии применения

Матрицы активно используются в:

  • системах доставки последней мили
  • сервисах такси и ride-sharing
  • планировании маршрутов курьерских служб
  • анализе городской мобильности
  • оптимизации размещения складов и точек выдачи

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

Работа с большими географическими наборами

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

  • географическое разбиение на кластеры
  • предварительное сокращение кандидатов
  • иерархический расчет матриц (coarse-to-fine)

Это позволяет снизить вычислительную сложность и уменьшить нагрузку на API, сохраняя точность маршрутизации на локальном уровне.

Оглавление