Введение

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

Да, можно планировать все поездки руками, но с ростом объема работ это делать становиться все труднее и труднее.

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

Маршрутизация, волшебное слово, но с чего начать?

Часть первая. Куда?

Куда везем? Как куда, куда сказал заказчик! Адрес, то он назвал! Адрес есть, но знает ли курьер где находится Третья улица строителей? Или другой случай: я живу в деревне, и номер дома у меня 4/2, как бы логично выглядит что 4/1 находится рядом, но это не так, между нашими домами находятся дома 8, 10, 10а, 10б, 12. Поигрались на почте. Вот как найти адрес доставки в такой ситуации?

Нужно по адресу получить географическую точку, и наоборот, найти адрес по геоточке. Т.е. нам нужен геокодер.

Первое, нужно определиться с поставщиком данных. Во общем-то выбор небольшой: Google и Open Street map. Первый это только платный сервис, второй это из Open Source семейства.

По очевидным причинам выберем OSM.

Далее, давайте посмотрим что есть:

1. Конечно, Яндекс

2. 2Gis

3. Google

4. Nominatim

Общение со всеми геокодерами платное. Это понятно, но хочется же бесплатного! И вот тут Nominatim выходит на лидирующие позиции:

по причинам:

1. использует данные одного из основных поставщиков данных (бесплатного!)  Open Street Map

2. так же находится в доменной зоне OSM

3. есть инструкция для развертывания у себя экземпляра Nominatim.

Выглядит заманчиво, на нем и остановимся.

Итак, нам нужно его развернуть, и загрузить данные из OSM. Данные из OSM можно взять из регулярных выгрузок из бд OSM. http://download.geofabrik.de/ для России http://download.geofabrik.de/russia.html

Все как бы хорошо, можно развернуть у себя в компании инстанс Nominatim, но набор необходимого программного обеспечения для функционирования Nominatim'a достаточно большой, и все это нужно поддерживать. Требуются значительные ресурсы. В общем-то накладно, а можно ли как то сделать с меньшими ресурсами? Оказывается можно! Есть геокодер, который не выходит на первые строчки поиска в Google, но от этого не менее эффективный: Фотон от компании Комоот https://photon.komoot.io/

Фотон основан на данных из бд Номинатим, но использует для своего хранилища Эластик. При этом он еще и Open Source, да еще и написан на java, по которой у нас много компетенций.

(приведу таблицу сравнения возможностей Номинатима и Фотона)

Собираем все рассуждения в единый пул и получаем следующий алгоритм:

Первым пунктом берем бд от Номинатима, грузим туда данные из OSM с помощью ядра номинатима, а вторым пунктом берем код Фотона, адаптируем под свои нужды, грузим данные в Эластик.

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

Подведем первые итоги: у нас есть геокодер, который может дать точку куда мы везем отправление. Но остался второй вопрос: как?

Часть вторая. Как?

Конечно же на автомобиле и по дороге! А может на велосипеде и по тропинкам? Итого нужен инструмент, который бы использовал данные OSM и так же так же учитывал тип транспортного средства, и который умеет строить маршруты, находить путь от одной точки до другой точки с минимальным расстоянием.

Добавим к критериям Open Source.

Тогда из всего многообразия, по указанным критериям можно выбрать:

1. Graphhopper

2. Open Route Service

3. Open Source Routing Machine

Первые два написаны на java, а osrm на c++

Стоит сделать следующие замечания:

а) с теми настройками, которые идут по умолчанию, все трое сильно отстают от Googole Maps, как в части кратчайшего расстояния, так и при расчете времени преодоления маршрута.

б) учет времени Google Maps делает с учетом реальной обстановки движения транспортных средств по своим приложениям, а другие учитывают указанные данные ограничения скорости движения в OSM.

Все трое в предельном случае используют алгоритм ДейкстраА*, но для основного расчета используют различные алгоритмы. Несмотря на это, результаты показывают близкие, отличия в пределах 10%.

Поэтому выбор стоит делать уже по тем компетенциям, которыми вы обладаете.

Итак, у нас есть инструмент, который строит по множеству географических точек оптимальный маршрут. Но только в том порядке, как мы указали. Так же для указания наличия препятствия на дороге требуется пересчитывать граф дорог, который создается из выгрузки из OSM. Что делать если на каком-то участке временно появилось препятствие? Вот тут у Graphhopper появляется преимущество. Для указания какого либо препятствия можно воспользоваться механизмом Custom Model, который позволяет изменять стоимость передвижения по ребру. Но за это нужно платить, скорость расчета кратчайшего маршрута сильно падает, но стоит отметить что стиль учета достаточно гибок, но при этом не учитывает названия ребер, так как при расчете требуется дополнительно обращаться к файлу, содержащий названия ребер. Но так как код открыт, то вполне можно это реализовать.

Но что делать если нужно оптимизировать порядок точек? И по каким критериям? А может быть у Вашей компании в городе несколько депо, а может быть курьер на выезде и приходит заказ забрать отправление и доставить его же в этом же городе? А еще и клиенты не хотят сидеть целыми днями у окошка, и ждать "пришествия" курьера? Вопросы, вопросы.....

Часть третья. А можно ли как-то экономить при доставке?

Что имеем на текущий момент:

1. мы знаем куда везти отправление

2. знаем как доехать до этой точки, и даже если точек несколько.

Теперь нужно учесть интересы своей компании и интересы клиентов. Самое грустное что чистая реализация одних интересов идет за счет других. Но как бы сделать что бы и волки были сыты, и овцы целы?

На помощь приходит - оптимизация.

Что же оптимизировать?

1. порядок посещения точек обслуживания,

2. время приезда на точку обслуживания,

3. время обслуживания,

4. количество отправлений

5. а еще курьер не робот, обед и прочее.

Надо сказать, что данные задачи были решены много лет назад, но алгоритмы совершенствуются и по сей день.

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

1. Grapphopper - по умолчанию отсутствует, можно использовать как отдельную библиотеку расчета матрицы по ДейктраА алгоритму, самый медленный и затратный механизм. Матричный расчет есть, но он только по коммерческой лицензии.

2. Open Route Service - матричный расчет присутствует, при этом использование алгоритма Дейксты только в самом вырожденном случае, для других используются два своих алгоритма на основе алгоритма Флойда-Уоршелла, позволяющие значительно снизить время расчета и используемые ресурсы.

3. Open Source Routing Machine - матричный расчет присутствует, так же Дейкстра используется только в вырожденном случае, основной же рабочий алгоритм так же свой и так же на основе алгоритма Флойда-Уоршелла.

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

1. Open Route Service

2. Open Source Routing Machine

Но следует учесть следующее: Илья Зверев (https://ilya.zverev.info/) написал статью : https://shtosm.ru/all/osrm-vsyo/

Оптимизация это самая коммерциализированая часть в маршрутизации. Ведь тут нужно иметь в штате алгоритмиков, программеров. А они хотят кушать. И по этим причинам на поприще Open Source есть только два инструмента:

1. Vroom https://github.com/VROOM-Project/vroom/tree/master

2. Jsprit https://github.com/graphhopper/jsprit

Заметим, что Jsprit вошел в кодовую базу graphhopper достаточно давно.

Vroom написан на C++ и представляет из себя отдельный бинарный файл, который запускается с параметрами в стиле утилиты юникс. Jsprit написан на java и это не готовый продукт, а библиотека, то есть, для его использования необходимо самому разработать сервис. При старте, для получения быстрого результата, логичнее использовать Vroom. По причине низкого порога вхождения.

Сравнение этих двух инструментов было проведено здесь.

И на данном этапе выбор из этих двух инструментов будет обусловлен только тем, какими компетенциями обладает Ваша компания.

Теперь зададимся вопросом: а как учитывать пробки?

Ответ очевиден: учитываем ее в матрице! Говорим что на каком-то ребре висит гиря в виде сильного ограничения скорости движения и все.

Делаем пробные расчеты:

1. пробка на мосту с 8:30 до 9:30 с ограничением скорости в 3 км/час

2. одна точка доставки находится за этим мостом, все остальные перед ним.

Считаем и получаем: этой точке отказано в обслуживании! (и тут проявилось первое преимущество Jsprit, у него есть реализация ответа почему произошел отказ(AlgorithmEventsRecorder, AlgorithmEventsViewer))

Начинаем разбираться и выясняется, что при матричном учете, эта пробка существует всегда. Без учета времени. С 0:00 по 23:59 и доставлять туда отправление не рентабельно.

И таким образом пробка имеет важный параметр - время! Она существует во времени, а не постоянно! То есть, нам нужно в инструменте иметь возможность учитывать время.

Vroom работает статически, набирает набор параметров и считает результат.

Jsprit имеет в своем багаже инструмент ObjectiveFunction, реализуя который, можно в зависимости от времени менять стоимость движения по ребру.  А это как раз то, что нужно для того, что бы учесть временное ограничения скорости движения.

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

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

Выбор за вами, кто за что платит.