Создание алгоритма маршрутизации для сервиса доставки воды

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

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

В первую очередь была решена проблема с заполнением матрицы дистанций между заказами. Все дело в объемах данных. Для 150 заказов – это 150*149 = 22 350 расстояний между заказами и еще 150 расстояний от склада до каждого заказа. Итого 22 500 расстояний. Можно было бы использовать расстояния между координатами, но, очевидно, доехать по прямой линии из точки А в точку В невозможно. (Вариант с расстояниями между географическими координатами используется в случае сбоев при заполнении матрицы дистанций). Каждый бесплатный картографический сервис имеет ограничения, не больше 10 000 – 15 000 бесплатных запросов в день. В сервисах уровня Yandex, нужно платить за запросы.  Мы выбрали вариант развернуть свой сервер OpenStreetMap. Он менее точный чем, к примеру, Yandex, но всегда существуют ограничения, в том числе финансовые.

Получив матрицу дистанций, все заказы разбивают на кластеры (заказы, которые находятся близко друг к другу) с использованием алгоритма кластеризации.  Количество кластеров равно количеству машин, для которых идет распределение. Затем для каждого кластера назначается своя машина. После этого мы получаем набор машин, к которым привязаны ближайшие заказы. Далее мы должны учесть загрузку машин, а также требование о равномерной их загрузке.

Некоторые машины имеют недогруз, мы назвали их «голодными», некоторые имеют перегруз – «переевшие».

На последнем этапе «переевшие» начинают отдавать заказы другим машин. Важно, что перед тем как передать заказ выстраивается направление к самой «голодной» машине, чтобы в итоге «переевшие» машины отдали лишние заказы в пользу «голодных». Эти лишние заказы передаются другим машинам, которые наиболее близки. Количество таких передач заказов ограничивается, чтобы ускорить работу алгоритма.

Ниже приведен пример результата работы алгоритма. Расчет производился для 163 заказов и 8 машин.

Полученный результат:

Потраченное время – 8 секунд, без учета генерации матрицы дистанции. Время заполнения матрицы зависит от количества точек, для 180 точек (заказов) в среднем – 5 минут.

Александр Шибанов

Александр Шибанов IT - предприниматель с более чем 15 летним стажем в индустрии. Принимал участие в различных по сложности проектах, на позициях программиста и руководителя проектов.
CEO Виртуум Лаб.

Популярные посты