Оптимальный маршрут доставочной машины — задача коммивояжера

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

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

При этом скрытые ресурсы для оптимизации весьма значительны: делает одна машина в смену 22 доставки или 24 — это большая разница.
Особенно если таких машин десятки и сотни.

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

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


Антор — довольно мощная софтина с разветвленными возможностями.
Обратной стороной являются относительно высокая стоимость и геморройность настройки/эксплуатации — чрезмерные для использования применительно к ограниченным задачам автоматизации городской дистрибуции.

Плюс к тому, отсутствие автоматического обмена данными (на тот момент API в Анторе реализовано не было) требовало ручного участия оператора для загрузки-выгрузки.
Со всеми вытекающими.
Неспособность софтины обрабатывать адреса вне формата КЛАДР также добавляла мало позитива к user experience.
Короче говоря, не менее трех эксплуатантов Ultimate, поработав некоторое время с Антором, от него отказались.

Для них мы разработали собственный сервис расчета оптимального маршрута, естественным образом интегрированный в IEM-систему Ultimate.

Для расчетов маршрутов используются API Яндекса и Google, которые предоставляют удобные и эффективные инструменты геокодирования и геолокации.
ИЧСХ, совершенно бесплатные.

Через гуглояндексное API вытягиваются координаты точек доставки и реальные автомобильные дистанции между парами адресов.
Оптимальный маршрут вычисляется внутри Ultimate с учетом временных интервалов, массогабаритов груза, etc.

Маршрутный лист водителя
В интерфейсе Ultimate можно посмотреть готовый маршрут на Яндекс-картах

Все, естественно, работает полностью автоматом и вмешательства (в основном, кривых) человеческих рук требует только в случае форс-мажора.

Материалы из библиотеки атеиста Powered by Ultima Consulting


Оптимальный маршрут доставочной машины — задача коммивояжера

Powered by Сон разума