В задачах, связанных с картографией и маршрутизацией в HERE Maps API, последовательность точек определяет не только визуальное представление маршрута, но и итоговую эффективность вычислений, стоимость запроса к маршрутизатору и качество полученного пути. При работе с большими наборами координат (доставка, трекинг, мобильные сенсоры, геоаналитика) порядок точек становится критическим фактором.
Набор точек без оптимизации часто отражает фактический порядок поступления данных: время фиксации GPS, порядок загрузки из базы, случайная сортировка. Такой порядок редко совпадает с географически рациональным маршрутом, что приводит к:
Оптимизация последовательности точек направлена на перестройку входного набора координат в структуру, минимизирующую целевую функцию: расстояние, время или стоимость перемещения.
В рамках API HERE каждая точка маршрута рассматривается как вершина графа:
{lat, lng}Базовая модель:
[ G = (V, E)]
где:
В реальных сценариях используется не полносвязный граф, а динамически вычисляемые ребра через Routing API или Matrix Routing API.
Классическая формализация:
[ {i=1}^{n-1} d(p_i, p{i+1})]
В контексте HERE Maps API задача решается либо приближённо, либо через специализированные сервисы оптимизации маршрутов.
Расширение TSP:
Используется при обработке GPS-треков:
Один из самых простых подходов:
Пример реализации с использованием JavaScript и Matrix Routing API:
const points = [
{ lat: 52.5200, lng: 13.4050 },
{ lat: 52.5206, lng: 13.4098 },
{ lat: 52.5155, lng: 13.3777 }
];
async function calculateMatrix(points) {
const response = await fetch("https://matrix.router.hereapi.com/v8/matrix", {
method: "POST",
headers: {
"Content-Type": "application/json",
"Authorization": `Bearer YOUR_API_KEY`
},
body: JSON.stringify({
origins: points,
destinations: points,
regionDefinition: { type: "world" },
routingMode: "fast",
transportMode: "car"
})
});
return response.json();
}После получения матрицы расстояний применяется жадный выбор следующего узла:
function nearestNeighbor(matrix, startIndex) {
const n = matrix.length;
const visited = new Array(n).fill(false);
const order = [startIndex];
visited[startIndex] = true;
for (let i = 0; i < n - 1; i++) {
const last = order[order.length - 1];
let next = -1;
let best = Infinity;
for (let j = 0; j < n; j++) {
if (!visited[j] && matrix[last][j] < best) {
best = matrix[last][j];
next = j;
}
}
visited[next] = true;
order.push(next);
}
return order;
}Алгоритм улучшения маршрута:
[ (a, b), (c, d) (a, c), (b, d)]
Применение:
function twoOpt(route, dist) {
let improved = true;
while (improved) {
improved = false;
for (let i = 1; i < route.length - 2; i++) {
for (let j = i + 1; j < route.length - 1; j++) {
const a = route[i - 1];
const b = route[i];
const c = route[j];
const d = route[j + 1];
const current = dist[a][b] + dist[c][d];
const swapped = dist[a][c] + dist[b][d];
if (swapped < current) {
route.splice(i, j - i + 1, ...route.slice(i, j + 1).reverse());
improved = true;
}
}
}
}
return route;
}В HERE Maps API можно делегировать оптимизацию серверной части Routing API v8.
Пример запроса с оптимизацией waypoint’ов:
const url = "https://router.hereapi.com/v8/routes";
const params = new URLSearchParams({
transportMode: "car",
origin: "52.5200,13.4050",
destination: "52.5300,13.3900",
return: "polyline,summary",
via: "52.5250,13.4100;52.5220,13.3950"
});
fetch(`${url}?${params.toString()}`, {
headers: {
"Authorization": "Bearer YOUR_API_KEY"
}
});Хотя Routing API сам по себе не выполняет полноценную перестановку множества точек, он используется как базовый инструмент оценки стоимости маршрута между перестановками.
Matrix Routing API позволяет получить попарные расстояния между всеми точками, что формирует основу для дальнейших алгоритмов оптимизации.
Пусть имеется набор точек:
[ P = {p_1, p_2, …, p_n}]
Матрица расстояний:
[ D[i][j] = cost(p_i p_j)]
Свойства:
При большом количестве точек (100+) прямая оптимизация становится вычислительно дорогой. Используется предварительная кластеризация:
После кластеризации:
Неоптимальные маршруты часто содержат пересечения линий на карте. Их устранение повышает качество маршрута.
Критерии улучшения:
Методы:
В реальных задачах оптимизация последовательности точек должна учитывать ограничения:
Это приводит к модифицированной функции стоимости:
[ C = d + t + p]
где:
Для сложных сценариев логистики в экосистеме HERE Maps API применяется специализированный сервис оптимизации маршрутов (Tour Planning API):
JavaScript-логика обычно строится вокруг:
После вычисления порядка точки передаются в Polyline и Marker объекты.
const lineString = new H.geo.LineString();
optimizedRoute.forEach(point => {
lineString.pushPoint(point);
});
const routeLine = new H.map.Polyline(lineString, {
style: { strokeColor: 'blue', lineWidth: 4 }
});
map.addObject(routeLine);Отображение порядка критически важно для:
При росте числа точек ключевым становится:
Часто используется гибрид:
Геометрическая близость точек не равна транспортной близости. В HERE Maps API учитываются:
Это приводит к необходимости использовать именно routing-based distance, а не Haversine формулу.
Типовой pipeline:
Такая многоуровневая схема обеспечивает баланс между скоростью и качеством маршрута в рамках HERE Maps API.