Разработка AI-системы оптимизации маршрутов доставки
Vehicle Routing Problem — задача, которую каждый логистический оператор решает ежедневно заново. При 50 точках доставки и 10 машинах число возможных маршрутов превышает 10⁶⁴. AI находит near-optimal решение за секунды с учётом временных окон, грузоподъёмности и пробок.
Постановка задачи маршрутизации
Разновидности VRP в логистике:
- CVRP (Capacitated): ограничение по грузоподъёмности
- VRPTW (Time Windows): клиент принимает только в определённые часы
- VRPPD (Pickup & Delivery): забрать груз в точке А, доставить в точку Б
- MDVRP (Multi-Depot): несколько складов
- DVRP (Dynamic): новые заказы поступают в процессе выполнения маршрутов
Алгоритмы оптимизации
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: вставка с учётом «сожаления» о потере альтернативных вариантов
Учёт реального трафика
Матрица расстояний и времени в пути:
- OSRM (Open Source Routing Machine): self-hosted, ~50ms на запрос 100×100 матрицы
- HERE Routing API / Google Maps Platform: более точные данные о пробках, платно
- Исторические данные пробок: час → средняя скорость по каждому сегменту дороги
Прогноз времени доставки:
GBDT (LightGBM) на признаках:
- Час, день недели, праздники
- Текущая загруженность дорог (API Яндекс.Карт / 2GIS)
- Погода (скорость и вес машины влияют на время)
- Тип зоны (центр города vs. промзона)
MAPE прогноза времени прибытия: 8–12% для внутригородской доставки.
Экономический эффект
| Метрика | Изменение |
|---|---|
| Общий пробег | -15 до -25% |
| Стоимость топлива | -12 до -20% |
| Кол-во рейсов | -8 до -15% |
| OTIF | +10 до +20 пп |
| Водителей для того же объёма | -5 до -15% |
Real-time мониторинг:
Трекинг GPS-координат водителей → сравнение с плановым маршрутом → alert при отклонении >500м или отставании >15 мин. Автоматический пересчёт оставшегося маршрута при существенных отклонениях.
Интеграция
- TMS (1С:Транспортное предприятие, Manhattan TMS): двусторонний обмен заказами и маршрутами
- Мобильное приложение водителя: turn-by-turn навигация, подтверждение доставки, ЭПД (электронная транспортная накладная)
- Клиентские уведомления: SMS/push с ETA, возможность переноса доставки
- BI-дашборд: KPI по водителям, зонам, клиентам
Срок разработки: 3–5 месяцев для системы с VRPTW и динамическим перепланированием, интеграцией с TMS и мобильным приложением водителя.