Автоматическая маршрутизация доставки (VRP / CVRPTW) на ноутбуке логиста: локальный OSRM, VROOM и временные окна клиентов
Главный кошмар вечерней смены транспортного отдела дистрибьютора воды, стройматериалов, продуктов питания или мебели: в 19:30 закрывается приём заказов на завтра — 650 торговых точек, у каждой своё приёмное окно («строго с 08:00 до 11:00 до прихода покупателей»), свой тоннаж и запрет на въезд грузовиков свыше 3,5 т во двор, а во дворе склада стоит разношёрстный парк из 28 «Газелей», «Валдаев» и 10-тонников! Диспетчер, раскидывающий эти заявки вручную по районам на глаз, закладывает лишние 18–25 % холостого пробега и всё равно получает утренние опоздания и штрафы сетей.
Между тем на обычном производительном ноутбуке с 16–32 ГБ оперативной памяти связка локального дорожного графа OSRM + открытого промышленного оптимизатора VROOM (или Google OR-Tools) рассчитывает близкий к оптимуму маршрутный лист на 650 точек со всеми ограничениями меньше чем за 40 секунд и совершенно бесплатно — без копейки за платные гео-API!
Почему расчёт «по прямой линии с коэффициентом извилистости 1,35» убивает реальную доставку в городе
Новички в аналитике пытаются считать расстояния между клиентами формулой гаверсинуса по воздуху (Haversine × 1,35). В реальном российском городе с рекой, мостами, железнодорожными переездами и развязками МКАД/КАД две точки в 400 метрах по воздуху по разные стороны железной дороги в реальности разделены 14 километрами и 35 минутами объезда!
Поэтому правильная двухшаговая архитектура расчёта на ноутбуке логиста выглядит так:
- Шаг 1 — Честная матрица реального дорожного времени и пробега
N × NвOSRM: скачайте сGeofabrikсвежий дамп дорожной сети OpenStreetMap своего федерального округа (*.osm.pbf, для ЦФО он весит около900 МБ; про юридическую атрибуцию данных OSM мы подробно писали в обзоре картографических подложек и лицензий OSM) и за 3 минуты разверните в Docker на ноутбуке локальный серверProject OSRM (Multi-Level Dijkstra):- запрос
HTTP GET вычисляет полную матрицу реальных времён проезда и дистанций **650 × 650(422 500пар маршрутов!) по реальным односторонним улицам, разворотам и ограничениям скорости за0,8 секунды`**!
- запрос
- Шаг 2 — Решатель задачи маршрутизации транспорта с грузоподъёмностью и окнами (
CVRPTW): передайте JSON с парком машин и точками в движокVROOM(написан на чистомC++, нативно интегрирован с локальнымOSRM) или вGoogle OR-Tools Routing!
Какие реальные физические ограничения склада и транспорта закладываются в JSON-задачу
| Ограничение реальной жизни | Поле в модели VROOM / OR-Tools |
Что будет, если его забыть |
|---|---|---|
Одновременный контроль И веса (кг), И объёма (м³ / паллет) |
Многомерный вектор вместимости capacity: [1500, 12] (например, 1 500 кг и 12 м³ для лёгкого фургона) |
В одну «Газель» попадёт 400 кг пенопласта или туалетной бумаги объёмом 26 кубометров — полмашины останется лежать на пандусе утром! |
Время на парковку, подъём на этаж и сдачу документов (Service Time) |
Индивидуальный service в секундах на точку (900 с = 15 мин для ларька, 2700 с = 45 мин для приёмки гипермаркета!) |
Алгоритм нарисует «идеальный» рейс на 28 точек, в котором водитель телепортируется от двери к двери за 0 минут, и маршрут развалится уже к обеду! |
Совместимость типа кузова / гидроборта / рефрижератора (Skills) |
Массив навыков skills: [1, 4] (например, 1 = рефрижератор +2..+6 °C, 4 = гидроборт или пропуск ТТК) |
Замороженные пельмени уедут в тентованной машине, а паллета весом 800 кг приедет без рохли и гидроборта! |
| Продолжительность смены водителя и перерыв на обед | time_window смены машины + breaks |
Прямая стыковка с законной нормой управления по тахографу и режиму труда водителя и автоматическая выгрузка готовых рейсов в электронные или бумажные путевые листы 2026 года! |
Когда компания вырастает до необходимости учитывать прогноз живых почасовых городских пробок и историческую скорость въезда во дворы, тот же самый математический принцип переносится на коммерческие отечественные TMS-облака (Яндекс Маршрутизация, Veeroute, 1С:ТМС Логистика), но предварительное моделирование тарифов, зон доставки и расчёт оптимального состава собственного и наёмного автопарка аналитик продолжает крутить на своём ноутбуке в связке OSRM + VROOM совершенно бесплатно хоть по 50 сценариев в день!
Требования к ноутбуку транспортного аналитика и логиста маршрутизации
При разворачивании дорожного графа OSRM на всю европейскую часть России или всю РФ целиком граф целиком маппится в оперативную память (RAM) процесса osrm-routed:
- Оперативная память
32 ГБ(на16 ГБотлично помещается любой отдельный регион/федеральный округ, на32 ГБ— вся дорожная сеть РФ целиком!), многоядерный процессор8+ потоков(движокVROOMпараллелит эвристики поиска на все доступные потоки-t 8!) и быстрыйNVMe SSD(как бюджетно расширить память корпоративного ноутбука до 32 ГБ — читайте в руководстве апгрейд оперативной памяти и SSD в ноутбуке).
Чек-лист перед запуском ночного авторасчёта маршрутов доставки
- [ ] Проверено качество геокодирования всех новых адресов клиентов: ни один адрес не упал в «центр города по умолчанию» из-за опечатки в номере корпуса (
accuracy = exact / rooftop, а неlocality!). - [ ] Профиль средних скоростей в локальном
OSRM (car.lua)откалиброван коэффициентом реального городского трафика (например,0,72–0,80от свободной ночной скорости), чтобы плановое время прибытия (ETA) совпадало с GPS-треками прошлых недель! - [ ] В модель добавлен реальный норматив погрузки на воротах собственного склада утром (волна
1, волна2), чтобы 28 машин не пытались одновременно встать к 6 воротам в07:00! - [ ] Визуально проверены треки
.geojsonв QGIS: исключены «перехлёсты» соседних машин из-за неверно вбитого узкого приёмного окна одного клиента.
Частые вопросы
Что делать, если суммарный тоннаж заказов пиковой пятницы превышает вместимость всех 28 машин парка — солвер просто выдаст ошибку Infeasible?
Ни в коем случае не оставляйте задачу без приоритетов: и в VROOM, и в OR-Tools (AddDisjunction) каждой точке назначается приоритет / штраф за невывоз (priority / penalty), а также могут быть добавлены «виртуальные дорогие наёмные машины спотового рынка» с высокой фиксированной стоимостью выхода на рейс (costs.fixed). Тогда солвер на 100 % плотно загрузит весь ваш собственный дешёвый парк самыми кучными точками, а в отдельный чистый список выделит ровно 1–2 готовых рейса для заказа наёмного перевозчика!