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

Задача маршрутизации транспортных средств (ТС) с временными окнами и ограничением по грузоподъёмности (Capacitated Vehicle Routing Problem with Time Windows, CVRPTW) — классическая задача, которая лежит в основе нашей постановки. Модификация CVRPTW заключается в добавлении дополнительного объекта маршрутизации — грузчиков, которые необходимы для выполнения некоторых заявок по отгрузке.

Задача призвана как оптимизировать движение ТС, так и повысить эффективность работы грузчиков. Грузчик посещает только те заказы, где он требуется, а у ТС снимается ограничение максимальной комплектации заказов с требованием грузчика/ов. Решение задачи отвечает на вопрос, где взять грузчиков, если требуется более одного грузчика на заявке (ТС позволяет взять только 1 грузчика).

Предполагается, что грузчики имеют свой транспорт (например, электровелосипед) для перемещения между заявками. Место начала и окончания работы грузчика — первый выполняемый заказ. Это правило обусловлено тем, что в дальнейшем маршруты грузчиков назначаются с учетом локации их проживания. Время на выполнение разгрузочных работ по заявке у грузчика может отличаться от времени ТС на заявке. Смена грузчика начинается в момент начала работы на первом заказе.

Разберём базовые понятия и ограничения задачи:

Routing Period — период планирования. Время начала планирования всегда 0. Время окончания планирования маршрутов зависит от времени последней операции (возврат последней ТС на depot (склад) или возврат последнего грузчика в точку начала работы).

Depot — точка старта маршрутов ТС (склад отгрузки). Задаётся с помощью координат (x, y). Предполагается, что в этой точке происходит загрузка ТС. В каждом сценарии есть только одна такая точка.

Vehicle — транспортное средство (ТС) с водителем, рассматриваемое как единый ресурс. Имеет ограничение по длительности смены. Отсчёт смены начинается с времени первого выезда из depot. Смена начинается и заканчивается в depot. Для всех vehicle указываются общие параметры вместимости (capacity) и длительность смены (vehicle_shift_size), а также скорость перемещения (vehicle_speed). Если vehicle успевает выполнить несколько маршрутов за смену (маршрут начинается и заканчивается в depot), то каждый новый маршрут должен учитывать время погрузки в depot (load_time). Первый маршрут освобождается от load_time. Предполагаем, что все объекты типа vehicle являются гомогенными.

Loader — грузчик. Грузчики имеют отличную от ТС скорость перемещения (loader_speed) и длительность смены (loader_shift_size). Предполагаем, что все грузчики имеют одинаковую квалификацию и скорость работы. Место и время начала работы грузчика совпадает с местом его первого заказа и началом разгрузки на этом заказе. В конце смены грузчик должен вернуться в начальную точку. Предполагаем, что все объекты типа loader являются гомогенными.

Order — заказ. Имеет набор параметров:

Решение

Решение задачи BIA_CVRPTW включает в себя следующие данные:

Предполагаем, что все маршруты связные и попадают в окна доставки заказа, т.е. vehicle и loader (при необходимости) прибыли в указанное окно. Операции (выгрузка) по заказам начинаются с момента прибытия последнего из участников vehicle и loader (при необходимости). Завершение операции на заказе у каждого участника своё.

Данные содержат координаты заказов на плоскости, расстояние между точками — евклидово расстояние, рассчитанное с точностью до 0.01:

где — математическое округление до второго знака после запятой. Время прохождения расстояния вычисляется по формуле: , где speed — скорость передвижения ТС или грузчика. Скорости у vehicle и loader отличаются. Матрица расстояний — полная, симметричная и обеспечивает выполнение неравенства треугольника.

Ограничения

Разделим ограничения на блоки: ограничения связанные с vehicle, ограничения связанные с loader, ограничения связанные с order, общие ограничения. Кроме этого, введём классификацию ограничений на жёсткие (H) и мягкие (S). Первые должны выполняться полностью, в то время как вторые участвуют в целевой функции. Нарушения мягких ограничений умножаются на соответствующий вес и добавляются в целевую функцию минимизации.

Ограничения типа vehicle:

Ограничения типа loader:

Ограничения типа order:

Общие ограничения:

Формат данных

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

Сценарии входных данных представлены в формате json. Структура файла содержит блоки, которые описаны ниже. Первый блок — общая информация: вместимость vehicle задаётся параметром vehicle_capacity; vehicle_speed и loader_speed — скорости движения (расстояние/время) vehicle и loader соответственно; длительности смен vehicle_shift_size и loader_shift_size для одного vehicle и loader соответственно.

  "vehicle_capacity": 1000,
  "vehicle_speed": 3,
  "loader_speed": 1,
  "vehicle_shift_size": 720,
  "loader_shift_size": 720,

Следующий раздел описывает расположение склада depot двумя координатами (x, y), load_time — время на погрузку второго и последующих маршрутов у vehicle.

  "depot": {
    "id": 0,
    "x": 100,
    "y": 100,
    "load_time": 40
  }

Список заказов указывается в разделе orders. У каждого заказа есть свой уникальный идентификатор id; координаты (x, y) клиента; volume — объём заказа, занимаемый в vehicle; окно приёмки заказа в виде интервала time_window; кол-во требуемых грузчиков на разгрузку loader_cnt; время на разгрузку по заявке vehicle_service_time и loader_service_time для vehicle и loader соответственно; обязательность заказа задается параметром optional (1 если заказ необязательный, 0 в противном случае).

"orders": [
{
      "id": 1,
      "x": 134,
      "y": 6,
      "volume": 20,
      "time_window": [
        988,
        1031
      ],
      "vehicle_service_time": 10,
      "loader_cnt": 0,
      "loader_service_time": 0,
      "optional": 0
    },
    {
      "id": 2,
      "x": 63,
      "y": 58,
      "volume": 20,
      "time_window": [
        55,
        589
      ],
      "vehicle_service_time": 10,
      "loader_cnt": 2,
      "loader_service_time": 20,
      "optional": 1
    },
    ...
]

Веса целевой функции указаны в блоке weights: vehicle_salary, loader_salary — стоимости аренды в смену единицы vehicle и loader соответственно; fuel_cost — цена топлива за единицу пройденного расстояния; loader_work — дополнительная стоимость работы грузчика за единицу времени; optional_order_penalty — эквивалент штрафа за невыполнение необязательного заказа.

  "weights": {
    "order_penalty": 250,
    "take_vehicle": 200,
    "add_loader": 200,
    "fuel_cost": 2,
    "loader_work": 1
  }

Файл с решением

Аналогично входному файлу, выходной файл имеет формат json. В выходном файле два блока: маршруты vehicles и маршруты loaders. В vehicles указывается id vehicle, маршрут route и time — времена начала выполнения разгрузки на заказах и начала загрузки в депо, если ТС делает несколько “кругов”. Аналогично для loader. Отличие указания маршрутов для vehicles и loaders заключается в том, что для vehicle начало и окончание маршрутов всегда depot с id=0, для loaders нет такого требования. Маршрут — это последовательное посещение заявок, т.е. последовательность заказов важна. При проверке начало операции по заявкам будет рассчитываться как максимальное время прибытие vehicle и loaders на заявку.

{
    "vehicles": [
        {
            "id": 1,
            "route": [
                0, 5, 7, 15, 28, 4, 0
            ],
            "time": [
                38.0, 65.04, 113.69, 169.94, 206.0
            ]
        },
        {
            "id": 2,
            "route": [
                0, 2, 4, 8, 9, 0, 34, 39, 29, 0
            ],
            "time": [
                46.0, 66.0, 112.17, 154.0, 189.52, 195.7, 230.14, 270.05
            ]
        },
        ...
    ],
    "loaders": [
        {
            "id": 1,
            "route": [
                2, 7, 15, 21, 29
            ]
        },
        {
            "id": 2,
            "route": [
                2, 4, 10, 23, 28, 30, 37
            ]
        },
        ...
    ]
}

Полезные ссылки

Правилами соревнования допускается использование сторонних open source пакетов, в том числе и готовых пакетов решения задач VRP. Готовых решателей конкурсной задачи нет, но вы можете положить в основу своего решения готовый солвер. Ниже приведены некоторые варианты таких решателей. Этот список не обязывает использовать решатель из приведенного списка.

Benchmark решателей задач VRP можно посмотреть здесь.