Привет жителям Хабра! Меня зовут Андрей, я разработчик облачного сервиса по планированию маршрутов Муравьиная логистика. В этой статье я хочу поделиться опытом использования алгоритма, который может пригодиться любой компании, выполняющей анализ данных доставки.

За 9 лет работы в сервисе я участвовал в разработке большого количества функционала, в том числе такого, как построение фактического маршрута движения автомобиля на основании данных GPS-трекера. Но нашим клиентам было недостаточно просто видеть на карте траекторию движения автомобиля. Сервис должен предоставить в удобном формате уже проанализированные данные - каждой плановой точке маршрута автомобиля необходимо присвоить соответствующую фактическую стоянку.

В чем сложность задачи?

Изначально задача показалось достаточно простой. Для определения соответствия плановых точек фактическим мы решили использовать незамысловатый алгоритм – к плановой точке «привязывались» ближайшие фактические точки. Но на практике этот метод оказался не всегда верным – данные часто указывались некорректно.

Всплыли многие проблемные моменты, которые выбранный алгоритм не учитывал:

Посещение автомобилем одной и той же точки несколько раз (например, если автомобиль приехал в точку доставки, но клиент временно отсутствовал, поэтому пришлось заезжать позже);
Внеплановые стоянки автомобиля (в случае поломки или по другим обстоятельствам);
Остановки на светофорах или в заторах, которые могут быть приняты сервисом за остановки в точках доставки;
Расположение нескольких плановых (а соответственно, и фактических) стоянок в одном месте;
Несколько выполненных подряд фактических стоянок, которые попадают в радиус плановой точки (например, если водитель, не сразу нашел нужный адрес точки доставки и ошибочно останавливался в соседнем дворе).

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

Тогда перед командой разработчиков и математиков сервиса была поставлена задача – разработать и внедрить новый алгоритм, который бы учитывал все вышеизложенные проблемы. Он должен максимально точно выполнять привязку к каждой плановой точке соответствующей фактической точки (или группы точек), зафиксированной GPS-трекером.

Небольшой ликбез в мир терминов

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

План - запланированная стоянка автомобиля в точке доставки (время и координаты стоянки принимаются из рассчитанного сервисом маршрута);
Факт - остановка, зафиксированная GPS-трекером автомобиля (трекер фиксирует координаты, начало остановки и её длительность).
Минимальное время стоянки - минимальное время фактической остановки (в секундах), при котором она засчитывается как стоянка. Данный параметр определяется пользователем на сервисе.
Радиус посещения (R) - минимальное расстояние между положением точки доставки на карте и фактической стоянкой, при котором фиксируется посещение этой точки. Данный параметр определяется пользователем на сервисе. Как правило, это 100-200 метров.

Подготовка данных

Исходные данные для анализа мы разделили на два списка:

Плановые стоянки в точках доставки – принимаются из рассчитанных сервисом маршрутов.
Фактические стоянки (остановки, соответствующие минимальному времени стоянки) – принимаются на основании данных GPS-трекера.

Далее все фактические стоянки поделили на 3 группы:

“крупные и близкие” - стоянки длительностью 150 сек и более, находящиеся в радиусе до 100 м хотя бы от одной плановой точки;
“крупные, но далекие” - стоянки длительностью 150 сек и более, находящиеся далее радиуса 100 м от плановых точек.
остальные фактические стоянки.

Алгоритм привязки планов и фактов

Наша команда разработала новый, более тщательный алгоритм идентификации данных с поэтапной привязкой пар план-факт. Суть его состоит в сравнении точек из 1-го списка (плановые стоянки) со стоянками из 2-го списка (фактические стоянки) с целью выявления правильных пар план-факт. Действия выполняются в следующем порядке:

1. Однозначные пары план-факт. На первом этапе алгоритм определяет факты, которые относятся только к одному плану, и у такого плана тоже нет других фактов в радиусе посещения.

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

3. Конкурирующие планы. Третий этап - если есть факт, относящийся к нескольким одиночным планам (не имеют других фактов в радиусе посещения), привязываем к нему все планы.

4. Цепочки планов и фактов. Четвертый этап. Часто плану соответствуют факты, находящиеся в радиусе посещения других планов, которые в свою очередь имеют другие факты в радиусе посещения и т.д. Такие цепочки рассматриваются как единое целое. Здесь возможны несколько вариантов:

вариант 1 - количество плановых стоянок меньше или равно количеству фактических стоянок. В таком случае привязываем планы к подходящим фактам по принципу минимального суммарного расстояния (один план – один факт). Лишние факты остаются непривязанными.

вариант 2 - количество плановых стоянок больше количества фактических стоянок. Тогда привязываем каждый план к ближайшему факту. У некоторых фактов при этом могут оказаться два и более плана. Непривязанных планов оставаться не должно.

Описанный алгоритм «прогоняется» 3 раза: изначально в расчет из 2-го списка (фактические стоянки) берутся только точки 1-ой группы - «крупные и близкие», далее добавляются точки 2-ой группы - «крупные, но далекие», и в последнюю очередь 3-я группа - остальные. Для каждой группы выполняется несколько циклов до тех пор, пока новый «прогон» не даст ни одной новой привязки. И только потом добавляются точки из новой группы фактов. Все привязанные пары план-факт исключаются из дальнейшего анализа.

В результате многоэтапного «прогона» алгоритма мы получаем:

привязанные пары - список плановых стоянок и соответствующих им фактических;
непосещенные точки доставки - планы, у которых нет фактов в радиусе посещения;
внеплановые факты - факты, которые не попадают в радиус посещения плановых стоянок;
проигравшие факты - не привязанные факты, которые проиграли другим фактам конкуренцию за планы.

Укрупнение фактов

Когда все плановые точки привязаны, мы ещё раз рассматриваем проигравшие факты. Если проигравший факт идет подряд (по времени) с привязанным ранее фактом (т.е. между ними нет других фактов), а также имеет с ним общий план в радиусе посещения, мы объединяем эти два факта. Такие сателлиты могут возникать, если водитель в поисках точки переезжал с места на место или из-за погрешности GPS-трекера.

Бывают случаи, когда два факта попали в радиус посещения плановой точки. Один привязан, так как оказался ближе к точке. Второй не подойдет, если разорван с привязанным фактом по времени. Это значит, что водитель заезжал в точку два раза (например, один раз не попал, так как было закрыто, поэтому заехал в конце маршрута). В этой ситуации проигравший факт так и остается не привязанным.

Заключение

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

Предоставленный алгоритм используется в нашем сервисе уже более 2 лет. Его результаты значительно превосходят по точности ранее использованные методы привязки фактической стоянки к плановой точке. И самое главное – за время работы алгоритм был успешно «проверен в бою» сотнями клиентов, тысячами маршрутов и десятками тысяч точек.

Решаем логистическую задачу: алгоритм привязки фактической и плановой стоянок автомобилей