В современном мире маршрутизация транспортных средств стала неотъемлемой частью бизнеса – от доставки продуктов до управления бензовозами. Но с ростом числа заказов маршруты усложняются: появляются различные ограничения – расписания курьеров, время доставки и вместимость транспорта. Наивные подходы становятся недопустимыми для решения.
Задача маршрутизации
Доставка товаров
Перевозка любых грузов от продавцов к покупателям: продуктов, банковских карт, стройматериалов и других товаров. Охватывает все сферы логистики, где нужно доставить заказ в нужное место.
Составление расписания курьеров
Распределение заказов между курьерами с учётом их расписания и загруженности. Помогает равномерно загрузить персонал и избежать простоев.
Оптимизация маршрута
Определение оптимального порядка посещения точек доставки для каждого курьера, чтобы сократить общее время маршрута.
Capacitiated Vehicle Routing Problem with Time Windows (CVRPTW)
Мы решаем задачу маршрутизации, в которой у заказов есть временные окна и вес, а у курьеров – время работы и ограниченная грузоподъёмность
Алгоритмы
Мы используем различные алгоритмы и специальные эвристики для решения задач маршрутизации
Жадный алгоритм
Быстрый, но не всегда находит хороший маршрут
Метод большой окрестности
Улучшаем качество маршрута, сохраняя высокую скорость
Имитация отжига
Используем много бизнес-критериев для поиска самого выгодного маршрута
Этапы работы на программе
Алгоритмы для решения задачи TSP
Изучение и реализация алгоритмов для решения «задачи коммивояжёра»
Инфраструктура для тестирования
Создание инфраструктуры для тестирования алгоритмов с генератором, реализующим репрезентативные сценарии использования, расчётным сервисом и диспетчером задач
Алгоритмы для решения задачи VRP
Реализация алгоритмов для решения задачи с множеством курьеров
Решение задачи CVRPTW
Решение реальной задачи для бизнеса, в которой учитываются временные окна доставки и расписания курьеров, а также вместимость
Визуализация
Разработка сайта для создания и редактирования задач, настройки параметров и отправки на решение, а также для отображения результата – оптимальных маршрутов для курьеров
Сравнительный анализ алгоритмов
Сравнение наших алгоритмов с аналогами по различным бизнес-метрикам (KPI)
Итоговый результат Мы создали сервис для планирования маршрутов, который учитывает временные окна и другие ограничения и использует наши алгоритмы для решения задачи