Оптимизация маршрутов представляет собой ценную функцию для владельцев автопарков, так как дает возможность компаниям планировать, создавать и анализировать наиболее выгодную и оптимальную стратегию выстраивания маршрутов. Опция интеллектуальной оптимизации маршрутов помогает компаниям с различными размерами автопарка эффективно решать широкий спектр проблем, с которыми они сталкиваются при распределении и планировании маршрутов.
Будучи инновационной компанией, Navixy использует новейшие тенденции в области разработки мобильных и web-приложений, чтобы обеспечить пользователя максимально эффективным и удобным инструментарием. Интеллектуальная оптимизация маршрутов позволяет быстро планировать поездки и мгновенно оптимизировать их. В этой статье мы опишем, почему оптимизация маршрутов важна, как она может быть эффективно осуществлена, и обсудим некоторые примеры.
Постоянно растущий рынок оптимизации маршрутов
Согласно Fortune Business, мировой рынок программного обеспечения для управления автопарком, оцениваемый в 2018 году в $14,046,7 млн, по прогнозам, достигнет $46,584,7 млн к концу 2026 года, при среднегодовом темпе роста в 16,52%. Одной из важных особенностей современных платформ управления автопарком является возможность оптимизации маршрута.
По оценкам Markets and Markets, рынок программного обеспечения для оптимизации маршрутов, оцененный в $2,50 млрд в 2017 году, достигнет $5,07 млрд к 2023 году, при среднегодовом темпе роста в 11,4%. Программное обеспечение для оптимизации маршрутов полезно в системах управления автопарком, расположенных на стороне пользователя. Она часто включает в себя возможности GPS-отслеживания и расширенный функционал отчетности, предоставляя владельцам автопарка возможность планирования маршрутов, учитывая при этом расход топлива, сокращая или предотвращая незапланированные остановки и помогая создать надежную и экономичную сеть доставки.
Оптимизация маршрутов: как это работает?
Много лет назад мореходам приходилось путешествовать из одного порта в другой, доставляя различные товары, и при этом необходимо было посетить ряд городов в течении одного плавания. Наверняка они должны были тщательно планировать свой путь и, очевидно, чем короче был предполагаемый маршрут, тем лучше. Хотя эта задача может поначалу может показаться весьма простой, эта проблема, известная как задача коммивояжера, становится экспоненциально сложной с постепенно увеличивающимся количеством точек, или городов, которые торговец должен был посетить.
Задача коммивояжера может быть визуализирована с помощью графа, который по-сути является абстрактным объектом, содержащим набор точек, или вершин, соединенных линиями, причем образованные ребра графа представляют собой перемещение между местоположениями, представленными точками. Каждое ребро графа имеет связанное с ним числовое значение, называемое весом. Таким образом, задача в итоге может быть сведена к поиску пути с кратчайшей суммой весов. Вес ребра также часто называют "стоимостью". Поэтому в задаче коммивояжера путешествующий торговец фактически нацелен на поиск маршрута с минимальной стоимостью.
Пример полного ориентированного графа и соответствующей матрицы, которая включает в себя расстояния между каждой точкой (портами, городами и т.д.), показан на рисунке выше. Нули в матрице затрат означают, что расстояния 2 → 3 и 3 → 2 одинаковы. Если произвести все возможные расчеты для путей, тогда мы определим, что оптимальный путь в этом случае 1 → 3 → 2 → 4 → 1, и минимальная стоимость при этом будет равна 7. Возникает вопрос - как все это связано с реальной жизнью? В реальной жизни задачу коммивояжёра можно переформулировать и описать следующим образом: предположим, что у ваших клиентов есть набор покупателей и автопарк для поставок. В этом случае необходимо отыскать набор маршрутов, для оптимального обслуживания всех покупателей. Здесь мы сталкиваемся с так называемой задачей маршрутизации транспортных средств, которая впервые была представлена в [6].
На практике часто приходится иметь дело с довольно большими объемами автопарка, и необходимо оптимизировать маршрут для каждой единицы автопарка. Это действительно сложная задача, и для ее решения существуют различные интеллектуальные алгоритмы, методы и парадигмы программирования, которые используются и разрабатываются для обеспечения ряда решений различной степени эффективности.
Кроме того, в реальном сценарии задача маршрутизации транспортных средств, естественным образом включает в себя некоторые ограничения, такие как: ограничения временных окон (период времени, в течение которого должно начаться обслуживание), время между каждой парой клиентов, продолжительность каждого посещения клиента. Кроме того, в идеале решение должно учитывать перерывы в работе водителя, правила для их регулирования и переменное время загрузки/разгрузки. Можно озадачиться вопросом, почему бы не попытаться фактически использовать эти ограничения для установления связей между переменными (интервалы времени начала обслуживания, продолжительность посещения клиента и т.д.). Это дельное замечание, поскольку в нем заключена идея, стоящая за так называемым программированием в ограничениях (или программирование ограничениями).
В парадигме программирования ограничениями, отношения между переменными задаются в виде ограничений. Ограничения определяют свойства решения, которое требуется найти, а не последовательность действий или шагов для выполнения. Поэтому, пользователям нужно просто указать свои ограничения, и специальный "решатель" попытается найти решения, удовлетворяющие всем ограничениям. Программирование ограничениями является хорошим вариантом для поиска решений задачи маршрутизации транспортных средств, так как в реальном времени маршрутизация транспортных средств часто имеет уникальный набор ограничений, и модель программирования ограничениями может быть модифицирована, чтобы включить новые ограничения, сохраняя без изменений ключевой метод решения. В настоящее время существует широкий спектр наборов алгоритмов, библиотек маршрутизации транспортных средств и специально разработанных "решателей", доступных для решения различных задач оптимизации, включая задачу маршрутизации транспортных средств. Однако ни один из решателей не может найти кратчайшие пути для всех проблем или всех возможных случаев. Решение задачи маршрутизации транспортных средств по сути является маршрутной оптимизацией. Оптимизация маршрута в этом сценарии определяет процесс поиска наиболее экономичного маршрута, который учитывает различные релевантные факторы, такие как, например, временные интервалы отправления/прибытия, эффективная загрузка, а также расположение всех остановок на маршруте.
В реальных случаях оптимизация маршрута может быть осуществлена в частности, используя следующие методы:
- нанять для этого эксперта (вопрос баланса время/ресурсы, это не всегда возможно, вопросы точности)
- использование различного программного обеспечения для управления автопарком (не все из них включают в себя эффективную оптимизацию маршрутов)
- использование некоторых из уже имеющихся "решателей" (не все из них достаточно практичны и точны)
- Можно также сочетать эти и другие методы друг с другом (требует навыков, опыта, времени/ресурсов).
В следующей главе мы приведем некоторые примеры и опишем наш подход к оптимизации интеллектуальных маршрутов.
Примеры программного обеспечения для оптимизации маршрутов
Чтобы привести ряд примеров, мы рассмотрим решения от Galileosky, ABIVIN, Rutific, и Telogis (Verizon Connect), а также опишем наше решение - интеллектуальную оптимизацию маршрутов - новую функцию для эффективного планирования. Решения Telogis предлагают инструменты для разделения данных таким образом, чтобы было проще анализировать задачи и соответствующие детали, а также определять оптимальные территории. Можно применять критерии, особые фильтры и бизнес-правила для тестирования сценариев и, в конечном счете, формирования территорий. Есть возможность моделировать сценарии по местоположению и/или потребностям клиента, типу и размеру загрузки, атрибутам водителя или предварительно определенным критериям для создания стратегических территорий и определения местоположения складов. Эта стратегия помогает максимизировать доходы и позиционирование для планирования будущих потребностей в ресурсах.
Abivin vRoute Optimization Software от ABIVIN - программное обеспечение для оптимизации маршрута "все в одном", с современными алгоритмами оптимизации для оптимизированного планирования маршрута, а также интеллектуальным управлением автопарком, с уведомлениями о доставке в реальном времени, утверждающее, что может помочь сэкономить до 40% затрат на логистику. ПО позволяет оптимизировать маршрут с помощью гибкого алгоритма, использующего AI/Machine Learning, который автоматически учится по историческим данным времени сортировки, времени обслуживания или времени в пути, чтобы предсказать будущие действия.
Еще одним примером является решение от Rutific. Rutific обеспечивает решение проблемы маршрутизации транспортных средств и учитывает временные окна, пропускную способность, типы доставки, приоритетные остановки, трафик, скорость водителя, время смены водителя, перерывы в работе водителя и многое другое. Существует возможность импортировать клиентов, настраивать и загружать маршруты или отправлять их прямо на смартфоны водителей с помощью мобильного приложения.
В Navixy наши разработчики используют интеллектуальные алгоритмы в сочетании с усовершенствованными функциями программирования ограничениями и многоцелевыми мета-эвристическими методами для учета повседневных потребностей управления автопарком и решения задачи маршрутизации транспортных средств высокоэффективным и преимущественным для клиента способом. В результате недавно появилась наша новая функция "интеллектуальная оптимизация маршрутов". Простым нажатием кнопки оптимизации маршрута, диспетчер мгновенно получит оптимальную последовательность локаций для посещения на карте. Одним щелчком мыши все точки выстраиваются в наиболее эффективный маршрут. Наши партнеры и клиенты уже могут извлечь из этого выгоду, следуя по оптимизированным маршрутам, ускоряя планирование, сокращая расходы на топливо и обслуживание, делая мобильные группы более эффективными при одновременном снижении общих затрат на автопарк и сохранении высокого качества обслуживания.
Водитель получит уже оптимизированный маршрут на свой смартфон: список мест для посещения в установленной последовательности, а также самый короткий маршрут от точки к точке. Все, что нужно сделать водителю - это следовать маршруту, отображаемому на мобильном устройстве.
Если вы хотите узнать больше об этой функции, посетите наш портал или свяжитесь с нами напрямую sales@navixy.ru.
Другим практическим примером оптимизации маршрута является устройство от Galileosky с эксклюзивной технологией Easy Logic. Мы связались с Дмитрием Красильниковым, менеджером по маркетингу компании Galileosky, и попросили его поделиться с нами соответствующей информацией об их решении.
Трекеры Galileosky в интеллектуальной оптимизации маршрутов
Программируемые устройства GPS-мониторинга нашли свое применение во многих областях: от грузоперевозок до сельского хозяйства. Хотя их основная функция - отслеживание транспортных средств, они могут выполнять и другие функции. Например, можно использовать трекеры для оптимизации маршрута. С помощью программируемых устройств Galileosky с эксклюзивной технологией Easy Logic можно устанавливать уведомления о нарушениях правил дорожного движения и ДТП и делать гибкую систему вознаграждения или штрафа для водителей на основе точных данных. А если часы работы для большегрузных автомобилей ограничены, можно планировать маршруты с учетом этого факта. Давайте рассмотрим все поближе.
Соответствие маршрутам
Допустим, что автопарк компании движется по маршруту, по которому компания тратит оптимальное количество топлива и рабочее время на дорогу. Соответствие этому маршруту может быть достигнуто геозонами. С помощью устройств отслеживания можно настраивать геозоны в определенном порядке. Алгоритм Easy Logic контролирует порядок, в котором транспортное средство входит в ту или иную геозону. При правильной последовательности водитель следует оптимальным маршрутом. Если заказ выполнен некорректно, можно уведомить водителя о его ошибках, и отправить отчет диспетчеру.
Это позволяет компаниям снизить стоимость топлива и транспортных услуг. Особенно выгодным будет построение оптимального маршрута на качественном дорожном покрытии. Кроме того, в зависимости от типа транспортного средства можно задать геозоны, указывающие на то, что неподходящее по размеру или типу транспортное средство оказалось в несоответствующей геозоне.
Время маршрутизации на основе опыта
Водители с разным опытом имеют разное время для прохождения своих маршрутов. Более опытный водитель справляется с задачей быстрее, тогда как начинающим не хватит времени на завершение поездки. Для решения этой проблемы можно настроить систему, которая назначает время в пути на основе работы и опыта вождения. Данные драйвера загружаются в RFID. Когда водитель авторизован, система автоматически вычисляет время, которое нужно дать водителю на маршруте.
Таким образом, компания сможет избежать затрат на простои и задержки, а также позволить новым водителям эффективно набраться опыта.
Контроль времени загрузки
Дополнительное время, необходимое для загрузки или разгрузки, может повлиять на выполнение заказа. Поэтому устройства GPS могут отслеживать эти периоды. Геозона настраивается на складской территории. После этого алгоритм Easy Logic сможет отслеживать, сколько времени водитель тратит на погрузку и разгрузку. Если водитель опоздает, система отправит ему предупреждение по SMS, световым или звуковым сигналом. Такая система не только позволяет оптимизировать маршруты, но и показывает, на каких складах больше всего тратиться времени. Эти данные позволяют реорганизовать и оптимизировать маршруты. Приведенные выше функции не ограничивают круг всех задач, которые могут решить трекеры Galileosky. Контроль скорости в зависимости от погодных условий, а также время работы и отдыха также влияют на оптимизацию маршрута. Поэтому существует возможность создать кастомизированное решение для разных сфер бизнеса. Все зависит от сложности и спецификаций проектов.
Выражение признательности
Мы благодарим все источники информации и помощи. Мы особенно признательны Galileosky, в лице Дмитрия Красильникова (Krasilnikov.d@7gis.ru), за обмен с нами интересной информацией об их продукте, а также за продуктивный и позитивный подход в части подготовки материалов.
Используемые источники
- https://www.fortunebusinessinsights.com/industry-reports/fleet-management-software-market-100893
- https://www.marketsandmarkets.com/Market-Reports/route-optimization-software-market-197501388.html?gclid=EAIaIQobChMIlI7MjOno5AIVTuWaCh1-FAnbEAAYASAAEgLTIPD_BwE
- https://www.abivin.com/post/2017/08/07/how-to-effectively-solve-the-vehicle-routing-problem
- Constraint Programming in a Nutshell by Pierre Flener, Joint ACP and GdR RO Summer School 2017.
- Principles of Constraint Programming by Krzysztof R. Apt, Cambridge University Press 2003.
- The Truck Dispatching Problem, G. B. Dantzig and J. H. Ramser, Management Science, Vol. 6, No. 1 (Oct., 1959), pp. 80-91.
- https://www.verizonconnect.com/telogis
- https://www.abivin.com/vroute
- https://routific.com
- https://www.navixy.ru/blog/smart-route-optimization/
- https://galileosky.com
- https://developers.google.com/optimization/routing/vrp
- https://www.altexsoft.com/blog/business/how-to-solve-vehicle-routing-problems-route-optimization-software-and-their-apis
- https://www.thecrazyprogrammer.com/2017/05/travelling-salesman-problem.html
