VRP-Ozon

Реализация многошагового пайплайна для задачи оптимизации маршрутов курьеров (VRP-подобная постановка), выполненная в рамках хакатона. В задаче предполагается порядка 20k заказов и 200 курьеров. В качестве целевой функции выступает суммарное время затраченное всеми курьерами на доставку + 3000 * число неназначенных заказов.

Структура файлов

В папке должны лежать файлы:

• ml_ozon_logistic_dataDurations.json - база данных расстояний между точками
• ml_ozon_logistic_dataSetCouriers.json - данные о курьерах и их сервисных временах
• ml_ozon_logistic_dataSetOrders.json - данные о заказах и их локациях

Скачать их можно по ссылке:

https://storage.codenrock.com/public/companies/codenrock-13/ml_ozon_logistic.zip?response-content-disposition=attachment%3B+filename%3D%22ml_ozon_logistic.zip%22

Основной алгоритм (baseline.py)

Запуск

python baseline.py --orders ml_ozon_logistic_dataSetOrders.json --couriers ml_ozon_logistic_dataSetCouriers.json --durations_json ml_ozon_logistic_dataDurations.json --durations_db durations.sqlite --output solution.json

Что делает baseline.py

1. Загрузка данных

   • Загружает заказы и курьеров из JSON файлов
   • Использует только первые 280 курьеров из доступных

2. Построение SQLite базы расстояний

   • Конвертирует JSON с расстояниями в SQLite для быстрого доступа
   • Создает индексы для оптимизации запросов
   • Обрабатывает файл потоково для экономии памяти

3. Алгоритм маршрутизации

   • Группировка по микро-полигонам: Заказы группируются по MpId (микро-полигон)
   • Внутренняя оптимизация: Внутри каждого полигона используется алгоритм ближайшего соседа (Nearest Neighbor)
   • Назначение курьерам: Полигоны назначаются курьерам жадным алгоритмом с учетом ограничений:
     • Максимальное время работы: 12 часов (43200 секунд)
     • Штраф за неразмещенные заказы: 3000 секунд

4. Оптимизация маршрутов

   • Вычисляет время маршрута с учетом:
     • Расстояний между точками
     • Сервисного времени курьера в каждой точке
     • Возврата на склад
   • Использует fallback через склад для отсутствующих прямых связей

5. Выходные данные

   • Создает файл solution.json с маршрутами для каждого курьера
   • Формат: {"routes": [{"courier_id": X, "route": [0, order1, order2, ..., 0]}]}

Проверка решения (scoring.py)

Запуск

python scoring.py --orders ml_ozon_logistic_dataSetOrders.json --couriers ml_ozon_logistic_dataSetCouriers.json --durations_db durations.sqlite --submission solution.json

Что делает scoring.py

1. Валидация решения

   • Проверяет корректность формата submission.json
   • Валидирует ID курьеров и заказов
   • Проверяет уникальность заказов между маршрутами
   • Убеждается, что заказы из одного микро-полигона не разделены между курьерами

2. Вычисление расстояний

   • Ищет прямые связи между точками
   • При отсутствии прямых связей ищет обратные
   • В крайнем случае использует маршрут через склад (ID=0)

3. Расчет финального скора

   • Суммирует время всех маршрутов
   • Добавляет штраф за неразмещенные закады (3000 сек за заказ)
   • Проверяет ограничение 12 часов на маршрут

4. Выходные данные

   • Выводит статистику по типам связей (прямые, обратные, через склад)
   • Количество неразмещенных заказов
   • Финальный скор в секундах

Алгоритмические особенности

• Жадная стратегия: Полигоны назначаются курьерам по принципу "первый подходящий"
• Fallback маршрутизация: При отсутствии прямых связей используется маршрут через склад
• Оптимизация памяти: Потоковая обработка больших файлов, LRU кэширование
• Балансировка нагрузки: Учет текущего времени работы курьера при назначении новых полигонов

Описание

Проект состоит из нескольких стадий (stage0 ... stage5), каждая из которых постепенно улучшает решение:

• Stage0–Stage3 — предобработка данных, построение карт и полигонов заказов.
• Stage4 — базовое построение маршрутов жадными и DP-подобными методами.
• Stage5 — финальная улучшалка на основе Adaptive Large Neighborhood Search (ALNS) с приёмкой через Late Acceptance Hill Climbing (LAHC).

Ключевые особенности:

• Кэширование вычислений (intra-time, portal-time, service-time).
• Собственная реализация операторов удаления/вставки: Random, Segment, Worst-Route, Shaw, Block, Regret-K Insertion.
• Ограничение длительности маршрута ≤ 12h.
• Поддержка восстановления заказов через «Critical Route Pool».
• Лёгкая отладка через DEBUG-флаг.
• Сохранение результатов в solution.json в формате, совместимом с scoring.py.

Технологии

• Python 3.9+
• Numba можно подключить для ускорения «тяжёлых» циклов

Результаты

• Базовый greedy (Stage4): ~3.96 млн score
• Stage5 (ALNS+LAHC, 1 минута): ~3.83 млн
• Stage5 (ALNS+LAHC, 1 час): ~3.18 млн

Запуск пайплайна

python baseline.py \
   --orders data/ml_ozon_logistic_dataSetOrders.json \
   --couriers data/ml_ozon_logistic_dataSetCouriers.json \
   --durations_db data/durations.sqlite