Матрица расстояний, это сетка времён и расстояний в пути между множеством точек отправления и множеством точек назначения. Это структура данных, лежащая в основе каждого ранжирования «ближайший магазин», каждого решения о диспетчеризации доставки и каждого решателя задач оптимизации маршрутов. Когда приложению нужно выбрать лучшего из множества кандидатов по времени в пути, под капотом работает матрица расстояний.
В этом руководстве разбираем, что такое матрица расстояний на самом деле, чем время в пути отличается от расстояния по прямой, где матрицы появляются в продакшен-системах и какие подводные камни кусают команды, как только входной набор разрастается за пределы нескольких точек.
Что такое матрица расстояний на самом деле
В простейшей форме матрица расстояний, это двумерная таблица. Строки, это точки отправления, столбцы, это точки назначения, а каждая ячейка хранит два числа: расстояние и продолжительность. При N точках отправления и M точках назначения в матрице N умножить на M ячеек. Запрос с 25 водителями и 25 заданиями даёт 625 ячеек за один вызов.
Значения в этих ячейках приходят от routing-движка, который проходит реальный граф дорожной сети. Он выбирает самый быстрый путь от каждой точки отправления к каждой точке назначения, суммирует стоимости сегментов и возвращает итог. Это принципиально отличается от вычисления по формуле гаверсинусов, которая проводит прямую линию между двумя координатами и игнорирует тот факт, что существуют здания, реки и улицы с односторонним движением.
Пара координат говорит вам, где находятся две точки. Матрица расстояний говорит, во что реально обходится путь между ними.
Расстояние vs продолжительность
Часто три разных числа называют «расстоянием», и их путаница, самый частый баг в коде маршрутизации.
Расстояние по гаверсинусу, это расстояние по большому кругу между двумя парами широты и долготы. Вычисляется быстро, не требует сетевого вызова и неверно для любой задачи, связанной с вождением. Расстояние 2 км по гаверсинусу может оказаться 7 км езды, как только вы учтёте реку, через которую невозможно переехать.
Расстояние по дорожной сети, это длина реально проезжаемого пути. Оно учитывает улицы с односторонним движением, ограничения поворотов и топологию графа дорог. Именно это возвращает API матрицы расстояний в поле distance.
Продолжительность с учётом трафика, это время, которое поездка займёт при текущих или прогнозируемых условиях трафика. Сегмент автомагистрали в 12 км занимает шесть минут в 02:00 и двадцать пять минут в 17:30. Продакшен-системы, которым важны ETA, запрашивают продолжительности с учётом трафика и передают время отправления, чтобы routing-движок корректно моделировал заторы.
Для ранжирования и диспетчеризации продолжительность почти всегда побеждает расстояние. Водителю всё равно, что более близкое задание на 800 метров дальше, если это сокращает четыре минуты езды.
Где применяются матрицы расстояний
Матрицы расстояний тихо работают под большинством логистических и завязанных на местоположение функций.
- Назначение водителей доставки: каждый ожидающий заказ сопоставляется с каждым доступным водителем. Диспетчер выбирает ячейку с наименьшей продолжительностью, удовлетворяющую ограничениям по вместимости транспорта и графику смен
- Диспетчеризация и перебалансировка автопарков: платформы такси и last-mile вычисляют матрицы между транспортом и зонами спроса каждые несколько секунд, чтобы машины оставались близко к пассажирам
- Ранжирование локаторов магазинов и заведений: вместо возврата пяти ближайших магазинов по гаверсинусу локатор вычисляет небольшую матрицу от позиции пользователя до кандидатов и ранжирует по времени поездки
- Расчёт ETA при масштабе: маркетплейсы с множеством одновременных заказов пакуют ETA в матричные вызовы, а не отправляют тысячи одиночных routing-запросов
- Решатели VRP: решатели задачи маршрутизации транспорта (OR-Tools, jsprit, коммерческие оптимизаторы) требуют полную матрицу стоимостей на входе. Качество решения маршрутизации ограничено качеством матрицы, которую вы в него передаёте
- Выбор площадок и территориальное планирование: аналитики вычисляют матрицы между кандидатными локациями и кластерами клиентов, чтобы выбрать склад, минимизирующий суммарное время в пути
Во всех этих случаях матрица, это примитив пакетных вычислений. Именно она позволяет системе рассуждать о «лучшем из множества» без необходимости платить за N на M отдельных routing-вызовов.
Подводные камни в продакшене
Матрицы расстояний просты в первый день и быстро становятся сложнее.
Асимметрия по умолчанию. В реальных дорожных сетях есть улицы с односторонним движением, разделённые полосы и асимметричные стоимости поворотов. Ячейка (A, B) редко равна ячейке (B, A). Считать матрицу симметричной ради экономии памяти, это одна из классических причин маршрутизации в неверном направлении в диспетчерских системах.
Стоимость N на M. Матрица 100 на 100, это 10 000 ячеек. Матрица 500 на 500, это 250 000 ячеек. Стоимость и задержка растут квадратично. Большинство продакшен-систем разбивают матрицы на чанки (50 на 50 или 100 на 100), параллелят запросы и кэшируют результаты, которые меняются нечасто, например матрицу между фиксированным набором складов и фиксированным набором магазинов.
Изменчивость по времени суток. Матрица, вычисленная в 03:00, недействительна в 17:00. Если ваша логика диспетчеризации зависит от трафика, либо запрашивайте матрицу с учётом трафика в момент принятия решения, либо предварительно вычисляйте небольшой набор матриц по временным интервалам (утренний пик, межпиковое время, вечерний пик) и выбирайте подходящую.
Пакетирование и rate limit'ы. API матриц расстояний тарифицируют поэлементно, а не по запросу, и большинство провайдеров ограничивают размер одного вызова. Планируйте чанкование и back-pressure с первого дня, а не открывайте это для себя при масштабировании.
Качество координат на входе, мусор на выходе. Матрица настолько хороша, насколько хороши координаты, которые в неё подаются. Геокод, попавший на не ту сторону разделённой автомагистрали, выдаст совершенно неверную продолжительность. Валидируйте входные координаты до того, как они попадут в запрос матрицы.
Матрицы расстояний в MapAtlas
MapAtlas Distance Matrix API вычисляет полные матрицы N на M по времени и расстоянию в пути на реальной европейской и глобальной дорожной сети. Он поддерживает профили легкового автомобиля, грузовика, велосипеда и пешехода, принимает запросы с учётом трафика и временем отправления и построен под размеры пакетов, которые нужны реальным нагрузкам диспетчеризации и оптимизации.
Для нагрузок, выходящих за пределы ранжирования, Distance Matrix API естественно сочетается с Optimize Route API, который принимает матрицу и набор остановок и возвращает упорядоченный маршрут, минимизирующий общее время в пути, и с Isochrone API для фильтров «всё, до чего можно добраться за X минут», предварительно сужающих набор кандидатов перед матричным вызовом.
Матрица расстояний не блестящая. Это просто сетка чисел. Но это та сетка чисел, которая превращает «найти лучшего из множества» из кошмара маршрутизации N на M в один пакетный запрос, и правильное обращение с этим куском данных, это то, что отличает реальный логистический продукт от демо с пятью булавками на карте.
Часто задаваемые вопросы
Что такое матрица расстояний?
Матрица расстояний, это сетка размером N на M из времён и расстояний в пути между набором точек отправления и набором точек назначения. Каждая ячейка отвечает на один вопрос: сколько времени занимает путь из точки i в точку j и какое расстояние. Современные API матриц расстояний вычисляют значения по реальной дорожной сети, а не как расстояния по прямой, поэтому результаты учитывают улицы с односторонним движением, ограничения поворотов и реальную геометрию дорог.
В чём разница между расстоянием и продолжительностью?
Расстояние, это длина пути по дорожной сети в метрах или километрах. Продолжительность, это время в секундах с учётом ограничений скорости, трафика и класса дороги. Это не взаимозаменяемые величины. У двух маршрутов может быть одинаковое расстояние и совершенно разная продолжительность, и большинству продакшен-сценариев (ETA, диспетчеризация, ранжирование) важна именно продолжительность. Хороший API матрицы расстояний возвращает оба значения для каждой ячейки.
Когда стоит использовать матрицу расстояний вместо отдельных маршрутов?
Используйте матрицу расстояний, когда нужно сравнивать множество кандидатов: ранжировать пять ближайших магазинов из пятидесяти, назначить доставку ближайшему доступному водителю из двадцати или подать данные в решатель задачи маршрутизации транспорта. Вызывать единичный routing-эндпоинт N на M раз медленно и дорого. Эндпоинт матрицы возвращает те же данные за один запрос, оптимизированный под пакетные вычисления.
Симметричны ли матрицы расстояний?
Почти никогда в реальных дорожных сетях. Поездка из A в B редко равна поездке из B в A из-за улиц с односторонним движением, разделённых полос, ограничений поворотов и асимметричного трафика. Продакшен-API матрицы расстояний возвращает полную сетку N на M, а не треугольную половину. Если вы свернёте матрицу ради экономии памяти, вы будете отправлять водителей по встречной полосе.
