Задача маршрутизации с временными окнами

В соседних статьях Задача маршрутизации транспорта, Задача маршрутизации с грузоподъёмностью и Задача маршрутизации с погрузкой и доставкой рассмотрены базовый VRP и два его расширения. Эта статья — третье расширение того же базового кейса: к 17 точкам и 4 ТС добавляются временные окна на каждом узле. У каждого клиента задан целочисленный интервал [начало, конец], в пределах которого ТС обязано прибыть в эту точку. Если ТС приезжает раньше открытия окна — ждёт; если позже закрытия — решение становится недопустимым.

Задача встречается в курьерской доставке с расписанием «принимаем с 10:00 до 13:00», в развозке товаров по магазинам с открытием/закрытием, при обслуживании клиентов с прибытием бригад в согласованные интервалы — везде, где конечный потребитель определяет окно приёма.

Условия задачи

Задан набор из 17 точек. Узел 0 — общее депо: 4 транспортных средства выезжают из него, обслуживают остальные узлы и возвращаются обратно.

Время в пути между узлами задано квадратной матрицей 17 × 17 (в минутах) — это входная характеристика дорожной сети, которая в реальных задачах берётся из картографического сервиса или измерений; в примере она подана как литерал. Для каждого узла задано временное окно — пара целых чисел [начало, конец], в пределах которого ТС обязано прибыть в точку; конкретные значения окон приведены в шаге 3 «Ввод данных».

Дополнительно: каждое ТС может ожидать перед началом окна не более 30 минут, и общее время маршрута каждого ТС ограничено 30 минутами. Требуется минимизировать суммарное время маршрутов всех ТС при выполнении всех временных окон.

Решение задачи

1. Выбор модели

Применяется та же модель маршрутизации, что и в задачах коммивояжера и VRP. Накопление времени по маршруту описывается обычным ресурсом маршрутизации, как в vrp-capacity, только накапливается время в пути. Временные окна выражаются ограничениями вида «значение ресурса в точке маршрута не меньше A и не больше B» — менеджер ограничений модели поддерживает их напрямую.

2. Создание модели

Сборка модели — как в VRP-статье: построитель параметров, 17 узлов, 4 ТС с общим депо в узле 0, фиксация состава.

// Создаём построитель параметров модели маршрутизации
Построитель = О2.Модели()
    .МодельМаршрутизации()
    .СоздатьПостроительПараметровМодели();

// Добавляем 17 узлов
КоличествоУзлов = 17;
Для К = 0 По КоличествоУзлов - 1 Цикл
    Построитель.ДобавитьУзел("Узел" + К);
КонецЦикла;

// Добавляем 4 транспортных средства с общим депо в узле 0
КоличествоТС = 4;
Для К = 1 По КоличествоТС Цикл
    Построитель.ДобавитьТранспортноеСредство(0, 0, "ТС" + К);
КонецЦикла;

// Фиксируем состав модели
Модель = Построитель.СоздатьМодель();

3. Ввод данных

Матрица времени в пути 17 × 17 собирается из 17 строк целых чисел через утилиту МассивЧиселИзСтроки. Результат — массив из 17 массивов, готовый к регистрации как транзит-матрица.

// Матрица времени в пути между узлами (минуты), 17 × 17
Времена = Новый Массив();
Времена.Добавить(О2.Утилиты().МассивЧиселИзСтроки("0,  6,  9,  8,  7,  3,  6,  2,  3,  2,  6,  6,  4,  4,  5,  9,  7"));
Времена.Добавить(О2.Утилиты().МассивЧиселИзСтроки("6,  0,  8,  3,  2,  6,  8,  4,  8,  8, 13,  7,  5,  8, 12, 10, 14"));
Времена.Добавить(О2.Утилиты().МассивЧиселИзСтроки("9,  8,  0, 11, 10,  6,  3,  9,  5,  8,  4, 15, 14, 13,  9, 18,  9"));
Времена.Добавить(О2.Утилиты().МассивЧиселИзСтроки("8,  3, 11,  0,  1,  7, 10,  6, 10, 10, 14,  6,  7,  9, 14,  6, 16"));
Времена.Добавить(О2.Утилиты().МассивЧиселИзСтроки("7,  2, 10,  1,  0,  6,  9,  4,  8,  9, 13,  4,  6,  8, 12,  8, 14"));
Времена.Добавить(О2.Утилиты().МассивЧиселИзСтроки("3,  6,  6,  7,  6,  0,  2,  3,  2,  2,  7,  9,  7,  7,  6, 12,  8"));
Времена.Добавить(О2.Утилиты().МассивЧиселИзСтроки("6,  8,  3, 10,  9,  2,  0,  6,  2,  5,  4, 12, 10, 10,  6, 15,  5"));
Времена.Добавить(О2.Утилиты().МассивЧиселИзСтроки("2,  4,  9,  6,  4,  3,  6,  0,  4,  4,  8,  5,  4,  3,  7,  8, 10"));
Времена.Добавить(О2.Утилиты().МассивЧиселИзСтроки("3,  8,  5, 10,  8,  2,  2,  4,  0,  3,  4,  9,  8,  7,  3, 13,  6"));
Времена.Добавить(О2.Утилиты().МассивЧиселИзСтроки("2,  8,  8, 10,  9,  2,  5,  4,  3,  0,  4,  6,  5,  4,  3,  9,  5"));
Времена.Добавить(О2.Утилиты().МассивЧиселИзСтроки("6, 13,  4, 14, 13,  7,  4,  8,  4,  4,  0, 10,  9,  8,  4, 13,  4"));
Времена.Добавить(О2.Утилиты().МассивЧиселИзСтроки("6,  7, 15,  6,  4,  9, 12,  5,  9,  6, 10,  0,  1,  3,  7,  3, 10"));
Времена.Добавить(О2.Утилиты().МассивЧиселИзСтроки("4,  5, 14,  7,  6,  7, 10,  4,  8,  5,  9,  1,  0,  2,  6,  4,  8"));
Времена.Добавить(О2.Утилиты().МассивЧиселИзСтроки("4,  8, 13,  9,  8,  7, 10,  3,  7,  4,  8,  3,  2,  0,  4,  5,  6"));
Времена.Добавить(О2.Утилиты().МассивЧиселИзСтроки("5, 12,  9, 14, 12,  6,  6,  7,  3,  3,  4,  7,  6,  4,  0,  9,  2"));
Времена.Добавить(О2.Утилиты().МассивЧиселИзСтроки("9, 10, 18,  6,  8, 12, 15,  8, 13,  9, 13,  3,  4,  5,  9,  0,  9"));
Времена.Добавить(О2.Утилиты().МассивЧиселИзСтроки("7, 14,  9, 16, 14,  8,  5, 10,  6,  5,  4, 10,  8,  6,  2,  9,  0"));

// Временные окна узлов: индекс — номер узла, элементы — [начало, конец]
Окна = Новый Массив();
Окна.Добавить(О2.Утилиты().МассивЧиселИзСтроки("0,  5"));  // 0 — депо
Окна.Добавить(О2.Утилиты().МассивЧиселИзСтроки("7, 12"));  // 1
Окна.Добавить(О2.Утилиты().МассивЧиселИзСтроки("10, 15")); // 2
Окна.Добавить(О2.Утилиты().МассивЧиселИзСтроки("16, 18")); // 3
Окна.Добавить(О2.Утилиты().МассивЧиселИзСтроки("10, 13")); // 4
Окна.Добавить(О2.Утилиты().МассивЧиселИзСтроки("0,  5"));  // 5
Окна.Добавить(О2.Утилиты().МассивЧиселИзСтроки("5, 10"));  // 6
Окна.Добавить(О2.Утилиты().МассивЧиселИзСтроки("0,  4"));  // 7
Окна.Добавить(О2.Утилиты().МассивЧиселИзСтроки("5, 10"));  // 8
Окна.Добавить(О2.Утилиты().МассивЧиселИзСтроки("0,  3"));  // 9
Окна.Добавить(О2.Утилиты().МассивЧиселИзСтроки("10, 16")); // 10
Окна.Добавить(О2.Утилиты().МассивЧиселИзСтроки("10, 15")); // 11
Окна.Добавить(О2.Утилиты().МассивЧиселИзСтроки("0,  5"));  // 12
Окна.Добавить(О2.Утилиты().МассивЧиселИзСтроки("5, 10"));  // 13
Окна.Добавить(О2.Утилиты().МассивЧиселИзСтроки("7,  8"));  // 14
Окна.Добавить(О2.Утилиты().МассивЧиселИзСтроки("10, 15")); // 15
Окна.Добавить(О2.Утилиты().МассивЧиселИзСтроки("11, 15")); // 16

4. Регистрация матрицы транзитов

Матрица времён регистрируется в модели как транзит. Ссылка на созданный транзит сохраняется в переменную МатрицаТранзита и используется и при описании ресурса времени, и при описании целевой функции.

// Регистрируем матрицу времён как транзит
МатрицаТранзита = Модель
    .Транзиты()
    .ДобавитьМатрицу(Времена, "Время");

5. Ресурс времени маршрута

Время в пути описывается как ресурс маршрутизации, накапливающий значения матрицы времени по ходу маршрута. Параметры метода Модель.Ресурсы().Добавить(...):

• первый аргумент — МатрицаТранзита (времена между узлами); ресурс растёт на величину пройденной дуги;
• максимальный резерв на узле — 30: разрешённое ожидание перед открытием окна. Если ТС прибыло раньше начала окна, оно «ожидает» — это ожидание добавляется к накопленному времени и ограничено 30 минутами на одной остановке;
• ёмкость — 30: верхний предел накопленного значения для каждого ТС, общий на весь автопарк (общая длительность маршрута не превышает 30 минут);
• признак накопления с нуля — Ложь: стартовое значение ресурса на старте маршрута может быть больше нуля. Это нужно, потому что окно депо [0, 5] допускает старт ТС в любой момент в этих границах, а не строго в момент 0;
• имя ресурса — "Время": метка для доступа к накопленному значению из решения.

Возвращённый объект ресурса сохраняем в переменную РесурсВремени — она потребуется на следующих шагах для установки временных окон.

// Ресурс времени: накапливается по матрице, ожидание ≤ 30 мин, общее время маршрута ≤ 30 мин,
// старт маршрута не привязан к нулю
РесурсВремени = Модель
    .Ресурсы()
    .Добавить(МатрицаТранзита, 30, 30, Ложь, "Время");

6. Временные окна клиентов

Для каждого узла-клиента (узлы 1–16) накладывается пара ограничений на значение ресурса Время в точке маршрута этого узла: оно должно быть не меньше начала окна и не больше конца. Точка маршрута клиента получается через Модель.ТочкиМаршрута().ПолучитьПоУзлу(индекс), ограничения — Модель.Ограничения().РесурсВТочкеМаршрутаНеМенее(...) и РесурсВТочкеМаршрутаНеБолее(...).

// Временные окна клиентов (узлы 1..16)
Ограничения = Модель.Ограничения();
ТочкиМаршрута = Модель.ТочкиМаршрута();
Для УзелКлиента = 1 По КоличествоУзлов - 1 Цикл
    ТочкаКлиента = ТочкиМаршрута.ПолучитьПоУзлу(УзелКлиента);
    Ограничения.РесурсВТочкеМаршрутаНеМенее(РесурсВремени, ТочкаКлиента, Окна[УзелКлиента][0]);
    Ограничения.РесурсВТочкеМаршрутаНеБолее(РесурсВремени, ТочкаКлиента, Окна[УзелКлиента][1]);
КонецЦикла;

7. Временное окно депо на старте маршрута

Окно депо [0, 5] применяется к стартовой точке каждого ТС — это другая сущность, чем «точка узла 0»: у каждого ТС своя стартовая точка, доступная через Модель.ТочкиМаршрута().ПолучитьСтарт(...). Ограничения те же — не меньше начала окна, не больше конца.

// Окно депо [0, 5] на старте каждого ТС
Для ИндексТС = 0 По КоличествоТС - 1 Цикл
    СтартТС = ТочкиМаршрута.ПолучитьСтарт(ИндексТС);
    Ограничения.РесурсВТочкеМаршрутаНеМенее(РесурсВремени, СтартТС, Окна[0][0]);
    Ограничения.РесурсВТочкеМаршрутаНеБолее(РесурсВремени, СтартТС, Окна[0][1]);
КонецЦикла;

8. Описание целевой функции

Целевая функция привязывается к матрице времени — минимизируется суммарное время маршрутов всех ТС. Временные окна и ограничение длительности влияют на множество допустимых маршрутов, а не на саму целевую функцию.

// Минимизируем суммарное время маршрутов всех ТС
Модель
    .ЦелеваяФункция()
    .УстановитьКоэффициентТранзита(МатрицаТранзита);

9. Решение модели

Стандартный вызов Модель.Решить(). Модель сама учтёт временные окна и ограничения длительности — отдельной настройки решателя не требуется.

// Решение модели
Решение = Модель.Решить();

10. Вывод результатов

Помимо имени ТС и пути на каждой остановке выводится время прибытия в эту точку. Его даёт поле Остановка.Ресурсы["Время"] — фиксированное соответствие, ключом которого является имя ресурса (заданное на шаге 5), а значением — накопленное значение ресурса в точке. Формат строки маршрута — 0 (0) → 9 (2) → 14 (7) → 16 (11) → 0 (18); в скобках — время прибытия в точку. После пути выводится суммарное время маршрута ТС. В шапке — общее время по всему автопарку.

// Вывод результатов
Если Решение.РешениеНайдено() Тогда
    ФорматВывода = "ЧДЦ=0; ЧН=0; ЧГ=0";

    Сообщение = СтрШаблон("Задача маршрутизации с временными окнами (%1 ТС, %2 вершин)%3", КоличествоТС, КоличествоУзлов, Символы.ПС);
    Сообщение = Сообщение + Символы.ПС;
    Сообщение = Сообщение + СтрШаблон("Суммарное время маршрутов: %1%2", Формат(Решение.ЗначениеЦелевойФункции(), ФорматВывода), Символы.ПС);
    Сообщение = Сообщение + Символы.ПС;

    Для Каждого Маршрут Из Решение.Маршруты() Цикл
        ПунктыПути = Новый Массив();
        Для Каждого Остановка Из Маршрут.Остановки Цикл
            ВремяПрибытия = Остановка.Ресурсы["Время"];
            ПунктыПути.Добавить(СтрШаблон("%1 (%2)", Остановка.Узел, Формат(ВремяПрибытия, ФорматВывода)));
        КонецЦикла;
        Путь = СтрСоединить(ПунктыПути, " → ");

        Сообщение = Сообщение + СтрШаблон(
            "Маршрут %1 (время %2): %3%4",
            Маршрут.ИмяТранспортногоСредства,
            Формат(Маршрут.Стоимость, ФорматВывода),
            Путь,
            Символы.ПС
        );
    КонецЦикла;

    Сообщить(Сообщение);
Иначе
    Сообщить("Решение не найдено! Статус: " + Решение.Статус());
КонецЕсли;

Полный код решения задачи

Ниже представлен полный код решения. Вы также можете скачать пример в виде готовой обработки.

// Создаём построитель параметров модели маршрутизации
Построитель = О2.Модели()
    .МодельМаршрутизации()
    .СоздатьПостроительПараметровМодели();

// Добавляем 17 узлов
КоличествоУзлов = 17;
Для К = 0 По КоличествоУзлов - 1 Цикл
    Построитель.ДобавитьУзел("Узел" + К);
КонецЦикла;

// Добавляем 4 транспортных средства с общим депо в узле 0
КоличествоТС = 4;
Для К = 1 По КоличествоТС Цикл
    Построитель.ДобавитьТранспортноеСредство(0, 0, "ТС" + К);
КонецЦикла;

// Фиксируем состав модели
Модель = Построитель.СоздатьМодель();

// Матрица времени в пути между узлами (минуты), 17 × 17
Времена = Новый Массив();
Времена.Добавить(О2.Утилиты().МассивЧиселИзСтроки("0,  6,  9,  8,  7,  3,  6,  2,  3,  2,  6,  6,  4,  4,  5,  9,  7"));
Времена.Добавить(О2.Утилиты().МассивЧиселИзСтроки("6,  0,  8,  3,  2,  6,  8,  4,  8,  8, 13,  7,  5,  8, 12, 10, 14"));
Времена.Добавить(О2.Утилиты().МассивЧиселИзСтроки("9,  8,  0, 11, 10,  6,  3,  9,  5,  8,  4, 15, 14, 13,  9, 18,  9"));
Времена.Добавить(О2.Утилиты().МассивЧиселИзСтроки("8,  3, 11,  0,  1,  7, 10,  6, 10, 10, 14,  6,  7,  9, 14,  6, 16"));
Времена.Добавить(О2.Утилиты().МассивЧиселИзСтроки("7,  2, 10,  1,  0,  6,  9,  4,  8,  9, 13,  4,  6,  8, 12,  8, 14"));
Времена.Добавить(О2.Утилиты().МассивЧиселИзСтроки("3,  6,  6,  7,  6,  0,  2,  3,  2,  2,  7,  9,  7,  7,  6, 12,  8"));
Времена.Добавить(О2.Утилиты().МассивЧиселИзСтроки("6,  8,  3, 10,  9,  2,  0,  6,  2,  5,  4, 12, 10, 10,  6, 15,  5"));
Времена.Добавить(О2.Утилиты().МассивЧиселИзСтроки("2,  4,  9,  6,  4,  3,  6,  0,  4,  4,  8,  5,  4,  3,  7,  8, 10"));
Времена.Добавить(О2.Утилиты().МассивЧиселИзСтроки("3,  8,  5, 10,  8,  2,  2,  4,  0,  3,  4,  9,  8,  7,  3, 13,  6"));
Времена.Добавить(О2.Утилиты().МассивЧиселИзСтроки("2,  8,  8, 10,  9,  2,  5,  4,  3,  0,  4,  6,  5,  4,  3,  9,  5"));
Времена.Добавить(О2.Утилиты().МассивЧиселИзСтроки("6, 13,  4, 14, 13,  7,  4,  8,  4,  4,  0, 10,  9,  8,  4, 13,  4"));
Времена.Добавить(О2.Утилиты().МассивЧиселИзСтроки("6,  7, 15,  6,  4,  9, 12,  5,  9,  6, 10,  0,  1,  3,  7,  3, 10"));
Времена.Добавить(О2.Утилиты().МассивЧиселИзСтроки("4,  5, 14,  7,  6,  7, 10,  4,  8,  5,  9,  1,  0,  2,  6,  4,  8"));
Времена.Добавить(О2.Утилиты().МассивЧиселИзСтроки("4,  8, 13,  9,  8,  7, 10,  3,  7,  4,  8,  3,  2,  0,  4,  5,  6"));
Времена.Добавить(О2.Утилиты().МассивЧиселИзСтроки("5, 12,  9, 14, 12,  6,  6,  7,  3,  3,  4,  7,  6,  4,  0,  9,  2"));
Времена.Добавить(О2.Утилиты().МассивЧиселИзСтроки("9, 10, 18,  6,  8, 12, 15,  8, 13,  9, 13,  3,  4,  5,  9,  0,  9"));
Времена.Добавить(О2.Утилиты().МассивЧиселИзСтроки("7, 14,  9, 16, 14,  8,  5, 10,  6,  5,  4, 10,  8,  6,  2,  9,  0"));

// Временные окна узлов: индекс — номер узла, элементы — [начало, конец]
Окна = Новый Массив();
Окна.Добавить(О2.Утилиты().МассивЧиселИзСтроки("0,  5"));  // 0 — депо
Окна.Добавить(О2.Утилиты().МассивЧиселИзСтроки("7, 12"));  // 1
Окна.Добавить(О2.Утилиты().МассивЧиселИзСтроки("10, 15")); // 2
Окна.Добавить(О2.Утилиты().МассивЧиселИзСтроки("16, 18")); // 3
Окна.Добавить(О2.Утилиты().МассивЧиселИзСтроки("10, 13")); // 4
Окна.Добавить(О2.Утилиты().МассивЧиселИзСтроки("0,  5"));  // 5
Окна.Добавить(О2.Утилиты().МассивЧиселИзСтроки("5, 10"));  // 6
Окна.Добавить(О2.Утилиты().МассивЧиселИзСтроки("0,  4"));  // 7
Окна.Добавить(О2.Утилиты().МассивЧиселИзСтроки("5, 10"));  // 8
Окна.Добавить(О2.Утилиты().МассивЧиселИзСтроки("0,  3"));  // 9
Окна.Добавить(О2.Утилиты().МассивЧиселИзСтроки("10, 16")); // 10
Окна.Добавить(О2.Утилиты().МассивЧиселИзСтроки("10, 15")); // 11
Окна.Добавить(О2.Утилиты().МассивЧиселИзСтроки("0,  5"));  // 12
Окна.Добавить(О2.Утилиты().МассивЧиселИзСтроки("5, 10"));  // 13
Окна.Добавить(О2.Утилиты().МассивЧиселИзСтроки("7,  8"));  // 14
Окна.Добавить(О2.Утилиты().МассивЧиселИзСтроки("10, 15")); // 15
Окна.Добавить(О2.Утилиты().МассивЧиселИзСтроки("11, 15")); // 16

// Регистрируем матрицу времён как транзит
МатрицаТранзита = Модель
    .Транзиты()
    .ДобавитьМатрицу(Времена, "Время");

// Ресурс времени: накапливается по матрице, ожидание ≤ 30 мин, общее время маршрута ≤ 30 мин,
// старт маршрута не привязан к нулю
РесурсВремени = Модель
    .Ресурсы()
    .Добавить(МатрицаТранзита, 30, 30, Ложь, "Время");

// Временные окна клиентов (узлы 1..16)
Ограничения = Модель.Ограничения();
ТочкиМаршрута = Модель.ТочкиМаршрута();
Для УзелКлиента = 1 По КоличествоУзлов - 1 Цикл
    ТочкаКлиента = ТочкиМаршрута.ПолучитьПоУзлу(УзелКлиента);
    Ограничения.РесурсВТочкеМаршрутаНеМенее(РесурсВремени, ТочкаКлиента, Окна[УзелКлиента][0]);
    Ограничения.РесурсВТочкеМаршрутаНеБолее(РесурсВремени, ТочкаКлиента, Окна[УзелКлиента][1]);
КонецЦикла;

// Окно депо [0, 5] на старте каждого ТС
Для ИндексТС = 0 По КоличествоТС - 1 Цикл
    СтартТС = ТочкиМаршрута.ПолучитьСтарт(ИндексТС);
    Ограничения.РесурсВТочкеМаршрутаНеМенее(РесурсВремени, СтартТС, Окна[0][0]);
    Ограничения.РесурсВТочкеМаршрутаНеБолее(РесурсВремени, СтартТС, Окна[0][1]);
КонецЦикла;

// Минимизируем суммарное время маршрутов всех ТС
Модель
    .ЦелеваяФункция()
    .УстановитьКоэффициентТранзита(МатрицаТранзита);

// Решение модели
Решение = Модель.Решить();

// Вывод результатов
Если Решение.РешениеНайдено() Тогда
    ФорматВывода = "ЧДЦ=0; ЧН=0; ЧГ=0";

    Сообщение = СтрШаблон("Задача маршрутизации с временными окнами (%1 ТС, %2 вершин)%3", КоличествоТС, КоличествоУзлов, Символы.ПС);
    Сообщение = Сообщение + Символы.ПС;
    Сообщение = Сообщение + СтрШаблон("Суммарное время маршрутов: %1%2", Формат(Решение.ЗначениеЦелевойФункции(), ФорматВывода), Символы.ПС);
    Сообщение = Сообщение + Символы.ПС;

    Для Каждого Маршрут Из Решение.Маршруты() Цикл
        ПунктыПути = Новый Массив();
        Для Каждого Остановка Из Маршрут.Остановки Цикл
            ВремяПрибытия = Остановка.Ресурсы["Время"];
            ПунктыПути.Добавить(СтрШаблон("%1 (%2)", Остановка.Узел, Формат(ВремяПрибытия, ФорматВывода)));
        КонецЦикла;
        Путь = СтрСоединить(ПунктыПути, " → ");

        Сообщение = Сообщение + СтрШаблон(
            "Маршрут %1 (время %2): %3%4",
            Маршрут.ИмяТранспортногоСредства,
            Формат(Маршрут.Стоимость, ФорматВывода),
            Путь,
            Символы.ПС
        );
    КонецЦикла;

    Сообщить(Сообщение);
Иначе
    Сообщить("Решение не найдено! Статус: " + Решение.Статус());
КонецЕсли;

  Скачать пример