Ежедневно тысячи грузовиков выезжают со складов, но ручное планирование маршрутов приводит к перепробегу в 15–20%. Алгоритмы VRP (Vehicle Routing Problem) — не панацея: NP-трудная задача требует комбинации точных методов (OR-Tools) и эвристик. Мы реализуем гибридные системы, которые за секунды строят near-optimal маршруты для сотен точек с учётом временных окон, грузоподъёмности, пробок и динамических заказов. AI-оптимизация маршрутов доставки — ключ к сокращению издержек. Наш опыт — более 50 проектов для ритейла, доставки еды и field service. Результаты: пробег сокращается на 15–25%, OTIF (on-time in-full) растёт на 10–20 пп., затраты на топливо падают на 12–20%.
Классическая VRP имеет множество разновидностей: CVRP (грузоподъёмность), VRPTW (временные окна), VRPPD (pickup & delivery), MDVRP (несколько складов), DVRP (динамика). Каждая усложняет задачу, но гибридные модели позволяют обрабатывать до 500 точек за 30 секунд — в 100 раз быстрее ручного планирования. Согласно определению из Wikipedia, задача маршрутизации транспорта (VRP) формулируется как нахождение оптимального набора маршрутов. Мы используем метаэвристики Large Neighborhood Search и машинное обучение (LightGBM) для прогноза времени доставки.
Почему VRP сложнее, чем кажется?
Разновидности VRP в логистике:
- CVRP (Capacitated) — ограничение по грузоподъёмности
- VRPTW (Time Windows) — клиент принимает только в определённые часы
- VRPPD (Pickup & Delivery) — забрать груз в точке А, доставить в точку Б
- MDVRP (Multi-Depot) — несколько складов
- DVRP (Dynamic) — новые заказы поступают в процессе выполнения маршрутов
Каждый тип добавляет свои ограничения, и комбинация нескольких делает задачу ещё более ресурсоёмкой. OR-Tools обрабатывает 500 точек за 30 секунд — в 100 раз быстрее ручного планирования.
Как AI находит оптимальные маршруты?
Google OR-Tools (для задач до 500 точек):
from ortools.constraint_solver import routing_enums_pb2 from ortools.constraint_solver import pywrapcp def solve_vrptw(distance_matrix, time_windows, demands, vehicle_capacities, depot=0): manager = pywrapcp.RoutingIndexManager( len(distance_matrix), len(vehicle_capacities), depot ) routing = pywrapcp.RoutingModel(manager) # Callback матрицы расстояний def distance_callback(from_idx, to_idx): from_node = manager.IndexToNode(from_idx) to_node = manager.IndexToNode(to_idx) return distance_matrix[from_node][to_node] transit_callback_index = routing.RegisterTransitCallback(distance_callback) routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index) # Временные окна time_dimension = routing.AddDimension( transit_callback_index, slack_max=30, capacity=480, fix_start_cumul_to_zero=False, name='Time' ) time_dim = routing.GetDimensionOrDie('Time') for location_idx, (start, end) in enumerate(time_windows): index = manager.NodeToIndex(location_idx) time_dim.CumulVar(index).SetRange(start, end) # Грузоподъёмность def demand_callback(from_idx): return demands[manager.IndexToNode(from_idx)] demand_idx = routing.RegisterUnaryTransitCallback(demand_callback) routing.AddDimensionWithVehicleCapacity( demand_idx, 0, vehicle_capacities, True, 'Capacity' ) search_params = pywrapcp.DefaultRoutingSearchParameters() search_params.first_solution_strategy = ( routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC ) search_params.local_search_metaheuristic = ( routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH ) search_params.time_limit.seconds = 30 solution = routing.SolveWithParameters(search_params) return solution, routing, manager Динамическая маршрутизация: Заказы поступают в течение дня. Large Neighborhood Search с adaptive destroy/repair операторами:
- При новом заказе: найти оптимальную позицию вставки без полного пересчёта
- Regret insertion: вставка с учётом «сожаления» о потере альтернативных вариантов
Сравнение методов решения VRP:
| Метод | Точность | Время решения | Размер задачи |
|---|---|---|---|
| OR-Tools (точное) | Высокая | 5-60 с | до 500 точек |
| Metaheuristic (LNS) | Приближённое | 1-10 с | до 5000 точек |
| LightGBM (прогноз) | 8-12% MAPE | <1 с | любое число |
Учёт реального трафика
Матрица расстояний и времени в пути формируется через OSRM (self-hosted, ~50ms на запрос 100×100 матрицы) или коммерческие API — HERE, Google Maps, Яндекс.Карты. Исторические данные о пробках усредняются по сегментам дорог с разбивкой по часам.
Прогноз времени доставки: GBDT (LightGBM) на признаках:
- Час, день недели, праздники
- Текущая загруженность дорог (API Яндекс.Карт / 2GIS)
- Погода (скорость и вес машины влияют на время)
- Тип зоны (центр города vs. промзона)
MAPE прогноза времени прибытия: 8–12% для внутригородской доставки.
Экономический эффект
| Метрика | Изменение |
|---|---|
| Общий пробег | -15 до -25% |
| Стоимость топлива | -12 до -20% |
| Кол-во рейсов | -8 до -15% |
| OTIF | +10 до +20 пп |
| Водителей для того же объёма | -5 до -15% |
Для парка из 50 грузовиков это даёт экономию топлива до нескольких миллионов долларов в год. Дополнительно снижаются штрафы за опоздания — экономия до 300 тыс. руб. в год. Срок окупаемости системы — менее 12 месяцев. Закажите аудит вашей логистики, чтобы оценить потенциальную экономию.
Как обеспечивается real-time мониторинг?
Трекинг GPS-координат водителей → сравнение с плановым маршрутом → alert при отклонении >500м или отставании >15 мин. Автоматический пересчёт оставшегося маршрута при существенных отклонениях. Система поддерживает интеграцию с любыми GPS-трекерами через API.
Что входит в работу
- Аудит текущей логистики и сбор данных
- Проектирование модели VRP с учётом всех ограничений
- Разработка алгоритмов (OR-Tools, LNS, LightGBM)
- Интеграция с TMS (1С, Manhattan, SAP)
- Мобильное приложение водителя с навигацией и ЭПД
- BI-дашборд с KPI по водителям и зонам
- Обучение команды и документация
- Поддержка на 3 месяца после запуска
Процесс работы
- Аналитика — изучение маршрутов, загрузка истории заказов
- Проектирование — определение метрик, выбор алгоритмов
- Разработка — реализация на Python, интеграция с картами
- Тестирование — A/B-тест на исторических данных, пилот на 10% маршрутов
- Деплой — rollout на весь парк, мониторинг отклонений
Сроки и стоимость
Срок разработки: 3–5 месяцев для системы с VRPTW и динамическим перепланированием, интеграцией с TMS и мобильным приложением водителя. Стоимость рассчитывается индивидуально после аудита. Чтобы обсудить вашу задачу, свяжитесь с нашими инженерами. Получите консультацию бесплатно.
Для задач CVRP указываем max_weight для каждого транспортного средства. В OR-Tools это реализуется через AddDimensionWithVehicleCapacity с массивом vehicle_capacities. Например, для 3 машин: [1000, 1500, 2000] кг.