Задача маршрутизации с погрузкой и доставкой

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

Задача встречается в курьерской доставке с попутным сбором посылок, перевозке пассажиров (такси, dial-a-ride), внутрискладской транспортировке между парами стеллажей — везде, где в одном маршруте чередуются цепочки «pickup → drop-off».

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

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

Заданы 8 пар «забор → доставка» — индексы узлов с нуля: (1, 6), (2, 10), (4, 3), (5, 9), (7, 8), (15, 11), (13, 12), (16, 14). Все 16 не-депошных узлов задействованы в парах ровно по одному разу. По условию каждая пара обслуживается одной и той же ТС, причём узел забора посещается раньше узла доставки.

Длина любого маршрута не должна превышать 3000 единиц. Расстояние между узлами — манхэттенское: d = |x₁ − x₂| + |y₁ − y₂|. Требуется минимизировать суммарную длину маршрутов всех ТС при выполнении ограничений на пары и длину.

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

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

Применяется та же модель маршрутизации, что и в задачах коммивояжера и VRP. Парные ограничения «погрузка-доставка» — встроенная возможность менеджера ограничений модели: один вызов Модель.Ограничения().ПогрузкаИДоставка(...) сразу описывает и «обе точки пары обслуживает одна ТС», и (при передаче упорядочивающего ресурса) «забор раньше доставки». Ограничение длины маршрута — частный случай накопленного ресурса, как в vrp-capacity, только накапливается расстояние, а не спрос.

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

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

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

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

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

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

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

Координаты 17 точек оформляются массивом структур через утилитный конструктор Точка2D — точно так же, как в VRP-статье.

// Координаты точек на плоскости
Координаты = Новый Массив();
Координаты.Добавить(О2.Утилиты().Точка2D(4, 4));
Координаты.Добавить(О2.Утилиты().Точка2D(2, 0));
Координаты.Добавить(О2.Утилиты().Точка2D(8, 0));
Координаты.Добавить(О2.Утилиты().Точка2D(0, 1));
Координаты.Добавить(О2.Утилиты().Точка2D(1, 1));
Координаты.Добавить(О2.Утилиты().Точка2D(5, 2));
Координаты.Добавить(О2.Утилиты().Точка2D(7, 2));
Координаты.Добавить(О2.Утилиты().Точка2D(3, 3));
Координаты.Добавить(О2.Утилиты().Точка2D(6, 3));
Координаты.Добавить(О2.Утилиты().Точка2D(5, 5));
Координаты.Добавить(О2.Утилиты().Точка2D(8, 5));
Координаты.Добавить(О2.Утилиты().Точка2D(1, 6));
Координаты.Добавить(О2.Утилиты().Точка2D(2, 6));
Координаты.Добавить(О2.Утилиты().Точка2D(3, 7));
Координаты.Добавить(О2.Утилиты().Точка2D(6, 7));
Координаты.Добавить(О2.Утилиты().Точка2D(0, 8));
Координаты.Добавить(О2.Утилиты().Точка2D(7, 8));

4. Вычисление матрицы расстояний

Двумерный массив фиксированных размеров создаётся через утилиту Массив2DИзвестногоРазмера. Модуль разности координат вычисляется через утилиту МодульЧисла. Матрица — КоличествоУзлов × КоличествоУзлов, симметричная, с нулями по диагонали.

// Матрица расстояний 17 × 17, заполняется манхэттенской метрикой
Расстояния = О2.Утилиты().Массив2DИзвестногоРазмера(КоличествоУзлов, КоличествоУзлов);
Для К = 0 По КоличествоУзлов - 1 Цикл
    Для К1 = 0 По КоличествоУзлов - 1 Цикл
        Расстояния[К][К1] = ?(
            К = К1,
            0,
            О2.Утилиты().МодульЧисла(Координаты[К1].X - Координаты[К].X)
                + О2.Утилиты().МодульЧисла(Координаты[К1].Y - Координаты[К].Y)
        );
    КонецЦикла;
КонецЦикла;

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

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

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

6. Ограничение длины маршрута

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

• первый аргумент — МатрицаТранзита (расстояния между узлами); ресурс растёт на величину пройденной дуги;
• максимальный резерв на узле — 0: ресурс растёт ровно на длину дуги, без запаса;
• ёмкость — 3000: верхний предел накопленного значения ресурса для каждого ТС, общий на весь автопарк;
• признак накопления с нуля — Истина: на стартовой точке маршрута пройденное расстояние равно нулю;
• имя ресурса — "Расстояние": метка для доступа к накопленному значению из решения.

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

// Ограничение длины маршрута: каждое ТС проходит не более 3000 единиц расстояния
РесурсРасстояния = Модель
    .Ресурсы()
    .Добавить(МатрицаТранзита, 0, 3000, Истина, "Расстояние");

7. Пары «погрузка → доставка»

Каждая пара регистрируется одним вызовом Модель.Ограничения().ПогрузкаИДоставка(УзелПогрузки, УзелДоставки, УпорядочивающийРесурс). Метод выполняет сразу две работы:

• привязывает обе точки пары к одной и той же ТС — УзелПогрузки и УзелДоставки всегда оказываются в одном маршруте;
• если передан упорядочивающий ресурс, накладывает на него ограничение значение_в_УзлеПогрузки ≤ значение_в_УзлеДоставки — то есть погрузка идёт раньше доставки в порядке обхода.

В качестве упорядочивающего ресурса передаётся РесурсРасстояния из предыдущего шага: накопленное расстояние монотонно растёт по ходу маршрута, поэтому сравнение «расстояние в узле погрузки ≤ расстояние в узле доставки» эквивалентно «погрузка раньше доставки». Отдельных ограничений «один ТС на пару» или «забор раньше доставки» в Ограничения() дописывать не нужно — обе семантики уже встроены в ПогрузкаИДоставка(...).

// 8 пар «погрузка → доставка»; упорядочивающий ресурс — расстояние
Ограничения = Модель.Ограничения();
Ограничения.ПогрузкаИДоставка(1,  6,  РесурсРасстояния);
Ограничения.ПогрузкаИДоставка(2,  10, РесурсРасстояния);
Ограничения.ПогрузкаИДоставка(4,  3,  РесурсРасстояния);
Ограничения.ПогрузкаИДоставка(5,  9,  РесурсРасстояния);
Ограничения.ПогрузкаИДоставка(7,  8,  РесурсРасстояния);
Ограничения.ПогрузкаИДоставка(15, 11, РесурсРасстояния);
Ограничения.ПогрузкаИДоставка(13, 12, РесурсРасстояния);
Ограничения.ПогрузкаИДоставка(16, 14, РесурсРасстояния);

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

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

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

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

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

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

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

Помимо имени ТС, пути и длины маршрута на каждой остановке выводится накопленное расстояние — пройденный ТС путь к моменту прибытия в точку. Его даёт поле Остановка.Ресурсы["Расстояние"] — фиксированное соответствие, ключом которого является имя ресурса (заданное на шаге 6), а значением — накопленное значение ресурса в этой точке маршрута. Формат строки маршрута — 0 (0) → 13 (388) → 15 (816) → 11 (1144) → 12 (1364) → 0 (1780); в скобках — текущее накопленное расстояние. Этот формат наглядно показывает работу парных ограничений: у узла погрузки накопленное расстояние меньше, чем у узла доставки той же пары.

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

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

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

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

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

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

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

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

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

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

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

// Координаты точек на плоскости
Координаты = Новый Массив();
Координаты.Добавить(О2.Утилиты().Точка2D(4, 4));
Координаты.Добавить(О2.Утилиты().Точка2D(2, 0));
Координаты.Добавить(О2.Утилиты().Точка2D(8, 0));
Координаты.Добавить(О2.Утилиты().Точка2D(0, 1));
Координаты.Добавить(О2.Утилиты().Точка2D(1, 1));
Координаты.Добавить(О2.Утилиты().Точка2D(5, 2));
Координаты.Добавить(О2.Утилиты().Точка2D(7, 2));
Координаты.Добавить(О2.Утилиты().Точка2D(3, 3));
Координаты.Добавить(О2.Утилиты().Точка2D(6, 3));
Координаты.Добавить(О2.Утилиты().Точка2D(5, 5));
Координаты.Добавить(О2.Утилиты().Точка2D(8, 5));
Координаты.Добавить(О2.Утилиты().Точка2D(1, 6));
Координаты.Добавить(О2.Утилиты().Точка2D(2, 6));
Координаты.Добавить(О2.Утилиты().Точка2D(3, 7));
Координаты.Добавить(О2.Утилиты().Точка2D(6, 7));
Координаты.Добавить(О2.Утилиты().Точка2D(0, 8));
Координаты.Добавить(О2.Утилиты().Точка2D(7, 8));

// Матрица расстояний 17 × 17, заполняется манхэттенской метрикой
Расстояния = О2.Утилиты().Массив2DИзвестногоРазмера(КоличествоУзлов, КоличествоУзлов);
Для К = 0 По КоличествоУзлов - 1 Цикл
    Для К1 = 0 По КоличествоУзлов - 1 Цикл
        Расстояния[К][К1] = ?(
            К = К1,
            0,
            О2.Утилиты().МодульЧисла(Координаты[К1].X - Координаты[К].X)
                + О2.Утилиты().МодульЧисла(Координаты[К1].Y - Координаты[К].Y)
        );
    КонецЦикла;
КонецЦикла;

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

// Ограничение длины маршрута: каждое ТС проходит не более 3000 единиц расстояния
РесурсРасстояния = Модель
    .Ресурсы()
    .Добавить(МатрицаТранзита, 0, 3000, Истина, "Расстояние");

// 8 пар «погрузка → доставка»; упорядочивающий ресурс — расстояние
Ограничения = Модель.Ограничения();
Ограничения.ПогрузкаИДоставка(1,  6,  РесурсРасстояния);
Ограничения.ПогрузкаИДоставка(2,  10, РесурсРасстояния);
Ограничения.ПогрузкаИДоставка(4,  3,  РесурсРасстояния);
Ограничения.ПогрузкаИДоставка(5,  9,  РесурсРасстояния);
Ограничения.ПогрузкаИДоставка(7,  8,  РесурсРасстояния);
Ограничения.ПогрузкаИДоставка(15, 11, РесурсРасстояния);
Ограничения.ПогрузкаИДоставка(13, 12, РесурсРасстояния);
Ограничения.ПогрузкаИДоставка(16, 14, РесурсРасстояния);

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

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

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

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

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

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

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

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