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

Курьерская служба, интернет-магазин с собственной доставкой, выездные мастера, развоз воды или цветов — везде встаёт один и тот же вопрос: в каком порядке ехать по адресам, чтобы потратить меньше времени и топлива. Руками его решают до пяти-шести точек, дальше число вариантов растёт быстрее, чем способен перебрать человек: для десяти адресов их уже больше трёх миллионов. В Karty для этого есть три связанных инструмента: маршрут между точками, матрица расстояний и оптимизация объезда. В статье — что каждый делает, как их вызвать и где у них границы.

Три инструмента: что для чего

Инструмент	Вопрос, на который отвечает	Ключ
Маршрут	Как проехать из A в B (или через несколько точек) и сколько это займёт	публичный или секретный
Матрица расстояний	Сколько времени и километров между каждой парой точек: какой курьер ближе всех к заказу	только секретный
Оптимизация объезда	В каком порядке объехать N адресов одной или несколькими машинами	только секретный

Маршрут: расстояние, время и линия на карте

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

map.route([83.7636, 53.3478], [83.7355, 53.3601])
   .then(function (route) { console.log(route.distance, route.duration); }) // метры, секунды
   .catch(function (err) { console.error(err.message); });

Если нужны данные без карты, запрашивайте напрямую: GET /v1/route/driving/{lon,lat;lon,lat;…} — до 25 точек. Ответ приходит в стандартном для маршрутизации формате: у маршрута есть distance в метрах и duration в секундах. Для центра Барнаула наш тестовый запрос между двумя точками дал 4 567 м и 392 секунды (6,5 минуты). Параметры overview=full&geometries=geojson добавят геометрию линии, steps=true — пошаговые манёвры.

Время в пути считается по ограничениям скорости дорог — без пробок. Для оценки «сколько ехать в обычное время суток» этого хватает, но в час пик закладывайте запас.

Матрица расстояний: кто ближе всех к заказу

Задача диспетчера: пришёл новый заказ, на линии пять курьеров — кому его отдать? Матрица считает время и расстояние между всеми парами точек за один запрос.

curl -H "Authorization: Bearer sk_live_ВАШ_СЕКРЕТНЫЙ_КЛЮЧ" \
  "https://kartrout.ru/v1/matrix/driving/83.7636,53.3478;83.7355,53.3601;83.7902,53.3299"

В ответе — таблицы durations (секунды) и distances (метры), где строка — «откуда», столбец — «куда». Для трёх точек выше время выглядит так:

"durations": [
  [   0, 392, 280],   // из точки 0: до 1 — 6,5 мин, до 2 — 4,7 мин
  [ 465,   0, 544],
  [ 299, 593,   0]
]

Обратите внимание на асимметрию: из точки 1 в точку 0 ехать 465 секунд, а обратно — 392. Дороги с односторонним движением и разворотами делают матрицу несимметричной, поэтому нельзя считать «туда» и «обратно» одним числом.

• До 25 точек в запросе. Чтобы не считать лишнее, укажите sources=0;1 и destinations=2;3;4: например, «курьеры» в источниках, «заказы» в назначениях.
• Квота считается по ячейкам матрицы (источники × назначения), а не по запросам: матрица 5×5 — это 25 единиц, 25×25 — 625. Лимиты: 3 000 ячеек за 30 дней на «Базовом», 15 000 на «Старте», 100 000 на «Бизнесе», 600 000 на «Масштабе».
• Матрица — «сырьё» для собственных алгоритмов распределения. Если нужен готовый порядок объезда, берите следующий инструмент.

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

Оптимизация решает классическую задачу маршрутизации транспорта. Вы передаёте адреса (как координаты) и свои машины, а в ответ получаете оптимальный порядок посещения для каждой машины. Минимальный запрос:

curl -X POST "https://kartrout.ru/v1/optimize" \
  -H "Authorization: Bearer sk_live_ВАШ_СЕКРЕТНЫЙ_КЛЮЧ" \
  -H "Content-Type: application/json" \
  -d '{
    "jobs": [
      {"id": 1, "location": [83.7636, 53.3478], "service": 300},
      {"id": 2, "location": [83.7355, 53.3601], "service": 300},
      {"id": 3, "location": [83.7902, 53.3299], "service": 300},
      {"id": 4, "location": [83.7054, 53.3482], "service": 300}
    ],
    "vehicles": [
      {"id": 1, "start": [83.7500, 53.3400], "end": [83.7500, 53.3400]}
    ]
  }'

Поля запроса:

• jobs — задачи (остановки): id (уникальный), location как [долгота, широта], необязательные service (время обслуживания на месте, секунды, до суток) и priority (0–100, чем выше, тем важнее взять заказ в рейс).
• vehicles — машины: id, start, необязательные end (вернуться на склад) и time_window (рабочее окно машины: начало и конец смены в секундах).

В ответе приходит план: для каждой машины — список шагов в порядке выполнения с расчётным временем прибытия. Для примера выше результат такой:

старт (склад)                      0 с
задача 4   прибытие  440 с
задача 2   прибытие 1153 с
задача 3   прибытие 1997 с
задача 1   прибытие 2596 с
финиш (склад)       3038 с
// в сводке: время в пути 1838 с (≈31 мин) + 1200 с работы на точках; unassigned: 0

Остановки в каждом шаге содержат job (ваш id), location, arrival (время прибытия в секундах от начала смены) и service. Поле unassigned перечисляет задачи, которые не удалось вписать в рейс — например, из-за рабочего окна машины. Если оно не пустое, добавьте машину или увеличьте смену.

Несколько машин

Добавьте в vehicles столько машин, сколько есть. Решатель распределит остановки между ними так, чтобы суммарное время было минимальным, и вернёт отдельный маршрут для каждой. Ограничения одного вызова: до 10 машин и до 90 точек суммарно (задачи плюс по 2 точки на машину — старт и финиш). Для большего парка делите работу по районам или рейсам.

Что пока не поддерживается

Чтобы вы не строили планы на том, чего нет, перечислим прямо: грузоподъёмность машин, навыки водителей (кто что умеет возить), парные задачи «забрать — доставить», перерывы и временные окна клиентов («доставка с 14 до 16») не учитываются. Сервис отвечает на вопрос «в каком порядке ехать», а не решает полное расписание с ограничениями клиентов. Если окна клиентов критичны, эту часть придётся добавить в своей логике поверх нашего порядка.

Стоимость: квота «Оптимизация маршрутов» считается по числу задач (jobs). Лимиты: 300 за 30 дней на «Базовом», 1 500 на «Старте», 10 000 на «Бизнесе», 60 000 на «Масштабе». Один вызов на 40 остановок потратит 40 единиц.

Как собрать всё вместе: типовой процесс диспетчерской

1. Получили заказы с адресами. Если у вас только адреса, а не координаты, переведите их в координаты массовым геокодингом или пакетным методом POST /v1/geocode/batch (до 50 адресов за вызов).
2. Распределили заказы по курьерам. Либо вручную, либо матрицей («кто ближе»), либо сразу передав все заказы и всех курьеров в оптимизацию.
3. Получили порядок объезда для каждой машины и сохранили его в своей системе.
4. Показали маршрут на карте диспетчеру или курьеру — виджетом, а линию между остановками можно рисовать по геометрии из запроса маршрута.
5. Пересчитали при изменениях: появился срочный заказ или машина вышла из строя — повторите оптимизацию с новыми данными.

Для оценки зоны, в которую курьер вообще может доехать за заданное время, пригодятся зоны доступности: ими удобно отсекать заказы, которые слишком далеко от склада.

Типичные ошибки и как их избежать

• Перепутаны широта и долгота. Везде — [долгота, широта]. Точка, «уехавшая» из города в океан, — признак перестановки.
• Один и тот же id у двух задач. Идентификаторы должны быть уникальными, иначе запрос отклоняется.
• Точки вне покрытия. Адрес за границей поддерживаемой территории возвращает ошибку: проверьте геокодинг.
• Ждёте окна доставки. Если важны окна клиентов, учтите, что сервис их не знает (см. выше).
• Ключ в браузере. Серверные методы вызывайте только с сервера. Ключ в клиентском коде — повод немедленно перевыпустить его.
• Слишком большой запрос. При 90+ точках разбейте задачу на несколько запросов по районам.

Частые вопросы