Некоторое время назад я участвовал в разработке приложения для фирмы, работающей в сфере транспортной логистики. Поскольку в тот момент фирма только начинала свою активную деятельность, многие процессы были еще не автоматизированы, и менеджер каждый вечер тратил два часа своего времени на распределение завтрашних заказов по водителям и составление их оптимальных маршрутов. У меня сразу же возникла идея реализовать в приложении инструменты, максимально облегчающие его задачу. Что из этого получилось - под катом.
Интерфейс для создания маршрутов и последующего мониторинга водителей представлен на картинке выше: гугл-карта с маркерами выполненных, зафейленных и оставшихся заданий, траекторией оставшейся части маршрута и маркером текущего положения водителя (обновляется на сервере через мобильное приложение-трекер, подробнее о котором ниже). Выполненные задания зеленые, зафейленные красные, текущее выполняющееся желтое, оставщиеся к выполнению белые. Водители тоже разноцветные - по кому было обновление координат в течение последних 5 минут - светло-желтые, по кому ранее - голубые, по кому еще не было обновления координат - фиолетовые. При выборе конкретного водителя показывается список точек его маршрута, работает драг-н-дроп и можно прямо на лету перестраивать маршрут мышкой. При невыбранном водителе на карте показываются маркеры их положения со статистикой по количеству выполненных/зафейленных задач, времени обновления координат и т.п.
Интерфейс периодически опрашивает сервер и обновляет данные на странице - можно пить кофе и смотреть на экране как маркеры водителей перемещается по карте а задачи из их списков становятся выполненными. Не рокет-сайенс, но удобно как для составления и редактирования маршрутов, так и для мониторинга процесса их выполнения.
Для того, чтобы вся эта красота обновлялась, нужна информация от водителей, которая поступает через мобильное приложение для Андроид (начиная с версии 6). Мобильники служебные, находятся в автомобилях, поэтому нет ни этических проблем с трекингом координат, ни технических проблем с поддержанием заряда аккумулятора при постоянно включенном трекинге в фоновом режиме. Работа с Андроид 6 и выше позволяет использовать дешевые модели устройств предыдущих поколений. Помимо отсылки координат машины, приложение визуализирует список задач с актуальными статусами
По клику на задаче можно посмотреть маршрут до точки на карте и установить задаче новый статус
При закрытии окна приложения процесс отслеживания координат не прекращается, о чем сигнализирует пиктограмма с грузовиком в списке уведомлений устройства (левый верхний угол на скриншотах). Для завершения работы и прекращения отслеживания координат нужно завершить программу через отдельный пункт меню.
Все это дело хорошо и красиво работает, но я бы хотел вернуться к основной теме этой статьи и рассказать об алгоритме составления оптимального маршрута. Для упрощения дальнейшего изложения, считаем, что перечень точек маршрута каждого водителя определен, надо задать оптимальный порядок их посещения. Это широко известная задача коммивояжёра, только мы строим не замкнутый маршрут, а с началом в одной конкретной точке (гараже) и с окончанием в другой (складе-приемнике собранных за рейс заказов).
Алгоритмов решения превеликое множество, но поскольку задача NP-трудная, то на точное решение при реальном объеме точек в маршруте можно не рассчитывать. Радует то, что в случае реальных данных обычно в окрестности точного оптимального решения существует много субоптимальных, которые практически немногим хуже оптимального. И их можно найти гораздо быстрее, использую любой из многичисленных известных эвристических алгоритмов или алгоритмов локальной оптимизации.
В качестве быстрого и дающего вполне подходящие результаты был выбран известный алгоритм 2-opt (который гарантирует отсутствие улучшения целевой функции если поменять любые 2 точки маршрута). Расстояние между любыми двумя точками берем кратчайшее по поверхности Земли - широта и долгота известны, дальше школьная арифметика. И визуально по траектории на карте алгоритм работает отлично!
Только менеджер сказал, что он не может им пользоваться, и вынужден много править (ручным драг-н-дропом) маршрут, предложенный по такой логике. И тут мы сталкиваемся с реальностью, которая влияет на построение оптимального маршрута гораздо больше, чем не точное решение локально оптимизирующего 2-opt. Оказывается, машины ездят по дорогам, а не по кратчайшим траекториям между точками. Тем более, что между точками может оказаться морской залив, и надо пилить до ближайшего моста (как на реальной карте Сан-Франциско в картинках выше). А часть дорог/мостов для грузовиков закрыта. Часть имеет ограничение по максимальному весу транспортного средства. Часть имеет односторонее движение в зависимости от графика по часам дня. А еще бывают пробки - предсказуемые и внезапные. Аварии, прорывы теплотрасс, стройки, временные заборы и объезды. А еще в разных точках маршрута бывают ограниченные временные интервалы, в течение которых надо посетить точку. Да и финальная точка маршрута - склад, тоже имеет ограниченное время работы и надо успеть в нее до закрытия. Существуют ограничения на максимальный вес/объем кузова и многое многое другое.
И если ограничения веса/объема, учет временных интервалов посещения точек и прочие подобные условия можно заложить в весовую функцию и алгоритм продолжит работать, то с выбором дорог перемещения между точками надо было что-то делать. Оказалось, что гугл имеет специальное апи distance matrix, где можно указать до 10 точек и возвращаются данные по времени преодоления расстояний между каждой парой из них, с учетом времени и актуального состояния пробок, аварий и прочего. Но во-первых, это стоит ощутимых денег - каждая пара точек 1 цент, 10 точек (10*10 пар) уже доллар, а надо гораздо больше 10 точек. А во-вторых, излишняя актуальность не нужна - мы планируем маршрут сегодня вечером на завтрашнее утро, и нас вполне устроят усредненные данные о пробках, а внезапные утренние аварии нам и гугл заранее не скажет.
В итоге было принято решение сделать маленький кастомный локальный гугл (в части distance matrix api). Составляется сетка - перечень доступных для наших целей перекрестков и дорог, их соединяющих, в терминах графов вершины и ребра. И наши автомобили могут ездить только по сетке - по ребрам этого графа. Также при наличии органичений для каждого ребра этого графа указываются веса в зависимости от времени дня - таким образом каждый участок дороги может проезжаться со скоростью 60 км/ч во временной интервал без пробок и 3 км/ч во время пробок. Или 0 км/ч в случае одностороннего движения. С помощью такой динамической системы весов ребер мы можем задавать как регулярные пробки в часы пик, так и внезапно возникающие стройки, заборы и прорывы теплотрасс. Степень точности зависит от того, насколько мелко задана сетка и насколько точная и актуальная информация о динамических весах ее ребер. Теперь уже маршрут между двумя произвольными точками зависит от времени в течение дня и вычисляется с помощью методов поиска оптимальных путей на графах - с добавлением в исходную сетку наших произвольных точек и простроением ребер от них к нескольким ближайшим вершинам. На карте сетка и примеры оптимальных маршрутов между парой точек выглядят так
Если же решать задачу поиска оптимального маршрута, то теперь он уже будет включать в себя и узлы сетки в качестве промежуточных точек. На картинке ниже видно, как для посещения точек маршрут приходит в ближайшие к ним узлы сетки и потом нередко возвращается обратно в те же узлы для дальнейшего движения по сетке
Такая "правда жизни" гораздо больше отвечает реальности, но для целей визуализации маршрута при показе менеджеру ее можно скрыть под капотом, оставив только траекторию, соединяющую точки маршрута в нужном порядке, или сделать такую упрощенную визуализацию отключаемой по флажку в пользовательском интерфейсе. Упрощенная визуализация будет менее перегружена деталями, и в ней автомобили будут ездить по прямой и плавать по заливу
С такими доработками алгоритм построения оптимального маршрута уже использовался менеджером, и ему только изредка приходилось руками поправлять пару точек по каким-либо частным соображениям.
P.S. (постскриптум)
Выделил описанную функциональность в отдельный проект. Бэк написан на Clojure, фронт на Clojurescript, мобильное приложение на Java. Открыт к вопросам и предложениям. Можно стучаться в личку на Хабре или в Телеграм https://t.me/IIvana.