Оптимизация маршрутов доставки заказов маркетплейса или как мы победили в E-CUP 2025

Хабр, привет! Недавно завершилось ML-соревнование E-CUP 2025 ^[1]. Наша команда из X5 Tech заняла первое место в треке «Логистика: автопланирование курьеров», где было нужно оптимизировать время, затрачиваемое курьерами на доставку 20 000 заказов. В статье расскажем про подходы, которые использовали для решения этой задачи. Посмотрим, во сколько раз можно сжать JSON с матрицей расстояний. Какой код мы использовали для быстрого решения задачи TSP с помощью LKH-3. Обсудим, на что обращать внимание ^[2] при кластеризации заказов.

Постановка задачи

Требовалось распределить порядка 20 000 заказов между 280 курьерами и построить для каждого из них маршрут так, чтобы минимизировать их суммарное время работы. Оно складывалось из времени перемещения курьеров между заказами и времени выполнения самих заказов (service time). За каждый невыполненный заказ добавлялся штраф 3000 секунд.

Заказы были объединены в микрополигоны — небольшие группы расположенных рядом заказов. Все заказы микрополигона должны назначаться одному курьеру. Время выполнения каждого заказа зависит от микрополигона и курьера, для каждой пары курьер-микрополигон был задан service time.

Ограничения:

• время работы каждого курьера не превышает 12 часов;

• маршруты начинаются и заканчиваются на складе;

• ограничение времени работы алгоритма — 1 час.

Дополнительно давали бонусные баллы за сбалансированность маршрутов, когда максимальное и минимальное время работы курьеров отличается не более чем на 30%.

Данные

Входными данными были три файла:

dataSetOrders.json (~1,3 MB) — информация о 20 160 заказах, включая географические координаты (Lat, Long) и номера микрополигонов (MpId).

{
    "Orders": # список заказов с принадлежностью к МП
    [
        {"ID":20660,"Lat":55.661591,"Long":37.416988,"MpId":9182},
        {"ID":20964,"Lat":55.709435,"Long":37.503283,"MpId":7714},
        {"ID":31295,"Lat":55.680483,"Long":37.524568,"MpId":9411}
    ]
}

dataSetCouriers.json (~29 MB) — данные о 280 курьерах с персональными значениями service time для различных MpId, а также данные  склада (Warehouse ID = 1).

{
  "CourierTimeWork": { # рабочие часы курьеров
    "TSStart": 28800,
    "TSEnd": 72000
  },
  "Warehouse": { # параметры склада
    "ID": 1,
    "Lat": 55.855153,
    "Long": 36.801776,
    "MpId": 0,
    "ServiceTime": 300
  },
  "Couriers": [ # список курьеров
    {
      "ID": 35, # для каждого курьера - список его ServiceTime
      "ServiceTimeInMps": [
        {
          "MpID": 9357,
          "ServiceTime": 60
        },
        {
          "MpID": 9359,
          "ServiceTime": 98
        },
      ]
    }
  ]
}

dataDurations.json (~15,5 GB) — около 400 млн записей с длительностями перемещений между всеми парами точек (в секундах).
Структура:

[
    {'from': 20258, 'to': 1337, 'dist': 3492}, 
    {'from': 20258, 'to': 2231, 'dist': 3363}, 
    {'from': 20258, 'to': 3824, 'dist': 3379}, 
    {'from': 20258, 'to': 4309, 'dist': 3357}, 
    {'from': 20258, 'to': 6013, 'dist': 3200}
]

Одной из подзадач стала эффективная обработка JSON-файла с длительностями перемещений. В сыром виде он занимал много памяти ^[3] и был неудобен для работы.

В базовом решении организаторов этот файл потоково считывался с помощью ijson и сохранялся в SQLite с кэшем. Overhead на построение базы данных занимал около 24 минут, что отняло бы значительное время у основного алгоритма маршрутизации.

В нашем решении JSON-файл однократно преобразовывался в плотную uint16 матрицу расстояний размером 20160 × 20160 (≈ 0.75 ГБ) с использованием потокового чтения JSON и NumPy memmap. Это позволило сократить время загрузки до 8 минут и ускорить доступ к расстояниям между двумя точками в 6 раз.

NumPy memmap

NumPy memmap позволяет работать с массивами, превышающими объём RAM: файл с матрицей хранится на диске и отображается в виртуальную память, а в оперативную память загружаются только реально используемые страницы. Поскольку в нашем случае матрица расстояний плотная и используется многократно, кэширование работает эффективно, при этом вся матрица никогда не хранится целиком в RAM (для sparse матриц такое решение, к сожалению, не подойдёт).

Решение

Наше решение состояло из трёх этапов:

1. Кластеризация. Разбиваем микрополигоны на кластеры и назначаем на них курьеров.

2. Балансировка. Перераспределяем микрополигоны между курьерами так, чтобы разница между маршрутами была не больше 30%.

3. Маршрутизация. Для заказов каждого кластера строим оптимальные маршруты перемещения.

TSP

На всех этапах требовалось оценивать минимальное время, необходимое курьерам для выполнения назначенных им заказов. Это похоже на классическую задачу коммивояжёра (TSP, Travelling Salesman Problem). Применительно к нашему кейсу это ATSP (Asymmetric Travelling Salesman Problem), поскольку время в пути от адреса A до адреса B может не равняться времени от B до A.

TSP — это задача поиска самого короткого замкнутого маршрута, проходящего через все заданные точки ровно один раз. В нашем случае под «самым коротким» понимается самый быстрый маршрут, а каждая точка — это отдельный адрес доставки. TSP относится к классу NP-трудных задач, в которых нет известного алгоритма, способного найти оптимальное решение за полиномиальное время. Сложность растёт факториально: уже для 20 точек количество возможных маршрутов исчисляется квинтиллионами, а сделать полный перебор вообще нереально.

На практике эту задачу решают с помощью эвристических алгоритмов. Мы рассмотрели несколько популярных инструментов. Крупный пакет Google OR-Tools. COIN-OR Branch-and-Cut солвер для Mixed Integer Problem из питоновской библиотеки PuLP. А также хорошо себя зарекомендовавшую в TSP/VRP-соревнованиях на Kaggle эвристику Лина-Кернигана в реализации LKH-3, в рамках которой выполняется итерационное улучшение текущего маршрута.

По результатам наших тестов лучшим по соотношению скорость/качество стал LKH-3. 

Его имплементацию можно скачать отсюда ^[4], на сайте также есть инструкции по компиляции и запуску. Вот пример использования LKH-3 на Python:

import subprocess
import numpy as np

# ряд функций для работы с LKH
def create_tsp_file(distance_matrix: np.ndarray, filename: str) -> None:
    """Создает TSP файл."""
    n = distance_matrix.shape[0]
    # Записываем TSP файл
    with open(filename, 'w') as f:
        f.write(f"NAME: TSP_Problemn")
        f.write(f"TYPE: ATSPn")
        f.write(f"DIMENSION: {n}n")
        f.write(f"EDGE_WEIGHT_TYPE: EXPLICITn")
        f.write(f"EDGE_WEIGHT_FORMAT: FULL_MATRIXn")
        f.write(f"EDGE_WEIGHT_SECTIONn")
        for row in distance_matrix:
            row_str = " ".join(str(v) for v in row)
            f.write(f"{row_str}n")
        f.write("EOFn")

def create_par_file(tsp_filename: str, tour_filename: str,
                    par_filename: str, params: dict[str, list]) -> None:
    """Создает файл параметров."""
    with open(par_filename, 'w') as f:
        f.write(f"PROBLEM_FILE = {tsp_filename}n")
        f.write(f"TOUR_FILE = {tour_filename}n")
        f.write(f"TRACE_LEVEL = 1n")
        # Записываем все параметры
        for param, value in params.items():
            if value == 'default':  # тогда не записываем чтобы использовался дефолт
                continue
            f.write(f"{param} = {value}n")

def parse_tour_file(tour_filename: str, depot: int) -> list[int]:
    """Парсит файл с результатом LKH и возвращает маршрут в виде списка order_id."""
    with open(tour_filename, 'r') as f:
        lines = f.readlines()
    # Находим секцию TOUR_SECTION
    tour_start = -1
    for i, line in enumerate(lines):
        if line.strip() == "TOUR_SECTION":
            tour_start = i + 1
            break
    if tour_start == -1:
        raise ValueError("TOUR_SECTION not found in tour file")
    # Читаем тур до EOF или -1
    tour_positions = []
    for i in range(tour_start, len(lines)):
        line = lines[i].strip()
        if line == "EOF" or line == "-1":
            break
        try:
            # LKH использует 1-based индексацию, переводим в 0-based
            pos = int(line) - 1
            tour_positions.append(pos)
        except ValueError:
            continue
    # Поворачиваем тур так, чтобы он начинался со склада (depot)
    depot_idx_in_tour = tour_positions.index(depot)
    if depot_idx_in_tour != 0:
        tour_positions = tour_positions[depot_idx_in_tour:] + tour_positions[:depot_idx_in_tour]
    # Добавляем склад в конец, если его там нет (замыкаем цикл)
    if tour_positions[-1] != depot:
        tour_positions.append(depot)
    return tour_positions

def calculate_route_time(route: list[int], distance_matrix: np.ndarray) -> float:
    """Вычисляет время маршрута."""
    total_time = 0
    for i in range(len(route) - 1):
        from_pos = route[i]
        to_pos = route[i + 1]
        total_time += distance_matrix[from_pos][to_pos]
    return total_time


np.random.seed(10)
distance_matrix = np.random.randint(1, 10, (5, 5))    # сгенерируем матрицу расстояний
np.fill_diagonal(distance_matrix, 0)                  # заполним диагональ нулями, чтобы не смущало

params = {                         # словарь с параметрами LKH - солвера
    'SEED': 10,
    'RUNS': 1,
    'MAX_CANDIDATES': 10,
    'MOVE_TYPE': 2,
    'INITIAL_TOUR_ALGORITHM': 'GREEDY',
    'MAX_TRIALS': 30,
    'PATCHING_C': 3,
    'PATCHING_A': 2
}

lkh_executable = "./LKH/LKH"       # путь до LKH executable
tsp_file = "./problem.tsp"         # путь до файла с описанием задачи в формате TSPLIB
par_file = "./params.par"          # путь до файла с указанием пути до файла .tsp и описанием параметров LKH - солвера
tour_file = "./solution.tour"      # путь до файла, в которое будет сохраняться решение ATSP задачи солвером
depot = 0                          # id точки начала и конца пути

# Создаем .tsp файл
create_tsp_file(distance_matrix, tsp_file)
# Создаем .par файл
create_par_file(tsp_file, tour_file, par_file, params)

try:
    # Запускаем LKH executable
    result = subprocess.run(
        [lkh_executable, par_file],
        capture_output=True,
        text=True,
    )
    if result.returncode != 0:
        raise ValueError(f"LKH failed with return code {result.returncode}")
except subprocess.TimeoutExpired:
    raise ValueError(f"LKH timed out")

# Парсим результирующий путь
route = parse_tour_file(tour_file, depot)
# Вычисляем objective value - суммарное время пути
total_objective = calculate_route_time(route, distance_matrix)

# ----- результаты -----
print(distance_matrix)  # исходная матрица
#  [[0 1 2 1 2]
#  [9 0 9 7 5]
#  [4 1 0 7 9]
#  [2 9 5 0 4]
#  [7 6 4 7 0]]
print(route)            # найденное решение
#  [0, 4, 2, 1, 3, 0]
print(total_objective)  # итоговое значение целевой функции (времени обхода)
# 16 
# рассчитывается как 2 + 4 + 1 + 7 + 2

У LKH-3 гибкие возможности для настройки алгоритма, более 50 различных параметров. Для контроля времени работы алгоритма и воспроизводимости мы использовали:

• RUNS — количество независимых запусков алгоритма;

• MAX_TRIALS — максимальное число попыток улучшения маршрута в рамках одного запуска;

• TIME_LIMIT — жёсткое ограничение по времени на один запуск;

• SEED — сид для генерации случайных чисел, нужен для воспроизводимости.

Кластеризация

Требовалось распределить микрополигоны по курьерам. Подмножество микрополигонов, на которое назначался курьер, назвали кластером. С одной стороны, кластеры должны быть не слишком большими, чтобы время работы каждого курьера не превышало ограничение в 12 часов. С другой стороны, кластеры должны быть максимально большими, чтобы минимизировать суммарное время работы курьеров. Чем больше средний размер кластера, тем меньше нужно кластеров. Чем меньше кластеров, тем меньше задействуется курьеров. Чем меньше курьеров, тем меньше суммарное время работы. Последнее утверждение верно, если выполняется неравенство треугольника: доехать из А в Б занимает столько же или меньше, чем из А в В и затем из В в Б.

Для формирования кластеров взяли подход, похожий на иерархическую кластеризацию. Сначала каждый микрополигон был отдельным кластером, затем мы объединили кластеры друг с другом, пока они не стали достаточно большими.

Мы заранее оценили суммарный service time заказов и минимальное время обхода заказов для каждого микрополигона, пересчитывали эти статистики и для кластеров. Это позволило быстрее проверять возможность объединения кластеров, чтобы не превысить лимит по времени. Грубо оценивали время обхода объединения кластеров К1 и К2, суммируя компоненты:

• время перемещения со склада до К1 (t₁);

• время на обход и выполнение заказов кластера К1 (t₂);

• время перемещения между K1 и K2 (t₃);

• время на обход и выполнение заказов кластера К2 (t₄);

• время перемещения от К2 до склада (t₅).

Если время было немного больше 12 часов, мы запускали LKH для объединённого множества заказов обоих кластеров и получали более точную оценку, которая, как правило, оказывалась меньше. Если итоговое время было меньше 12 часов, то кластеры можно объединять.

Любимые микрополигоны

Первое, на что мы обратили внимание при подборе пар кластеров для объединения — это микрополигоны, на которых один или два курьера выполняли заказы быстрее остальных. Например, один курьер в «любимом» микрополигоне тратил на каждый заказ 1 минуту, а остальные курьеры на те же заказы – по 5 минут. Если микрополигон содержал 15 заказов, то, назначив правильного курьера, мы экономили час времени.

Но из этого правила было исключение: если выигрыш от добавления в кластер очередного «любимого» полигона был меньше дополнительных затрат на перемещение курьера, то добавлять его не было смысла. Такое случалось, когда «любимые» микрополигоны находились в противоположных направлениях от склада.

Объединение кластеров на основе «любимых»  микрополигонов привело к уменьшению кластеров с 1393 до 1311.

В дальнейшем при объединении кластеров мы проверяли информацию о «любимых» и «нелюбимых» микрополигонах для избежания конфликтов двух типов:

• в одном кластере любимые микрополигоны разных курьеров;

• в одном кластере есть и любимые, и нелюбимые микрополигоны одного курьера.

Ближайшие соседи

Вторая идея: объединять ближайшие друг к другу кластеры, чтобы тратить минимум времени на перемещения между заказами. Для этого нужно перебирать пары кластеров, отсортированные по возрастанию расстояния между ними, и объединять их, если это возможно. Такой подход работает быстро и даёт неплохой результат.

При разбиении мы заметили, что на периферии есть микрополигоны, которые долго не объединяются, так как находятся сравнительно далеко от соседей. Когда до них доходит очередь, их уже нельзя объединить с ближайшими кластерами, так как они близки к лимиту в 12 часов. Приходится посылать отдельного курьера в самую даль, чтобы доставить небольшое количество заказов, что явно неэффективно.

Так появилась третья идея: объединять кластеры, начиная с самых удалённых, чтобы не оставлять дальние микрополигоны напоследок. Мы брали самый дальний микрополигон, определяли его кластер, и пробовали объединить с ближайшими кластерами, затем переходили к следующему по удалённости микрополигону и так далее. Такой подход гарантировал, что курьер, который едет на дальний микрополигон, выполнит там много заказов, и другому курьеру не придётся ехать туда повторно.

Численные эксперименты показали, что лучше всего работает комбинация обоих подходов. Сначала объединяем кластеры, которые очень близки друг к другу (расстояние меньше 14 секунд). Эта процедура уменьшила количество кластеров с 1311 до 1102.

Затем объединяем кластеры, начиная с самых удалённых от склада микрополигонов. Количество кластеров уменьшилось с 1102 до 67-69. Но тут на результат начал влиять фактор случайности ^[5]. Для оценки времени выполнения заказов в кластере иногда использовался LKH, который может давать разные результаты в зависимости от инициализации. Этот разброс влияет на оценку времени работы курьера и принятие решения об объединении кластеров.

Балансировка

За сбалансированность, когда самый длинный маршрут отличается от самого короткого не более чем на 30%, давали дополнительные баллы. Наш алгоритм кластеризации жадно наращивал кластеры, поэтому большинство из них были заполнены по максимуму, с временем выполнения, близким к 12 часам. Однако оставалось несколько маленьких кластеров из заказов недалеко от склада, из-за которых общее условие балансировки нарушалось. Чтобы это исправить, мы передали в маленькие кластеры ближайшие микрополигоны больших кластеров.

Маршрутизация

После получения итоговых кластеров мы сделали дополнительную итерацию построения оптимального пути внутри каждого конкретного кластера. Решали задачу ATSP с помощью солвера LKH-3. С учётом ограничения на суммарное время работы пайплайна мы сформулировали следующие требования:

1. Воспроизводимость результатов. Важно как для соответствия онлайн и офлайн скоров, так и для дальнейшего потенциального масштабирования решения при его выкатке в продакшн. 

2. Контролируемое время исполнения.

Выполнение требований делали через настройку гиперпараметров солвера LKH. На первый взгляд казалось, что убить «двух зайцев» можно с помощью установки двух параметров LKH-3: SEED и TIME_LIMIT (жёсткого ограничения времени на один запуск). Но эксперименты показали, что такая конфигурация возвращала маршруты, которые не были воспроизводимы. Поэтому мы отказались от жёсткого ограничения времени запуска в пользу установки менее требовательной ко времени комбинации параметров. Как итог, для воспроизводимости зафиксировали параметры SEED, а также PATCHING_C и PATCHING_A, аналогично исследованию самих создателей инструмента (ссылка ^[6]). Мы также  настроили параметры MAX_CANDIDATES, MOVE_TYPE, RUNS, INITIAL_TOUR_ALGORITHM, которые сильно влияют на длительность поиска оптимального решения. В итоге получили комбинацию значений параметров, с которыми солвер стабильно возвращал оптимальный маршрут в пределах ~30 секунд на кластер.

Чтобы ускорить вычисления, мы распараллелили расчёт оптимальных маршрутов по кластерам. В рамках соревнования была доступна машина с четырьмя ядрами. Один из них мы оставили под работу системы, остальные три ядра LKH использовал для параллельного поиска маршрутов в трёх кластерах. Поскольку LKH-3 в рамках запуска работал с несколькими файлами (.tsp, .par, .tour), мы выделяли каждому из трёх параллельных запусков отдельную временную директорию. Распараллеливание снизило время работы в ~2,5 раза.

Итоги

В результате наше решение выдавало скор в диапазоне 2790-2830 тысяч секунд, распределяя все заказы по курьерам и соблюдая условие балансировки. На лидерборде получили скор ~2823 тысяч секунд, который позволил занять первое место. У команд на втором и третьем местах скор оказался порядка 2841 тысяч секунд, что примерно на 5 часов больше нашего.

Состав команды победителей: Близнюков Владимир, Глухов Игорь, Назаров Николай, Сахнов Александр, Филиппова Ольга.