Задача маршрутизации с грузоподъёмностью

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

Задача распространена в логистике с ограниченным «карманом» каждого ресурса: развозка по объёму или весу кузова, разнос корреспонденции с ограниченной вместимостью сумки, доставка от центрального склада с учётом грузоподъёмности машины.

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

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

У каждого клиента (узлы 1–16) задан целочисленный спрос: 1, 1, 2, 4, 2, 4, 8, 8, 1, 2, 1, 2, 4, 4, 8, 8. Суммарный спрос всех клиентов — 60. У каждого ТС грузоподъёмность кузова — 15 единиц спроса; суммарная грузоподъёмность автопарка — 60: автопарк ровно покрывает суммарный спрос, ни одного клиента нельзя пропустить.

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

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

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

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

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. Регистрация матрицы транзитов

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

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

6. Вектор спроса

Спрос на узлах задаётся массивом целых чисел длины 17 — нулевой элемент равен 0 (в депо никого не обслуживают), остальные — спрос клиентов. Массив компактно собирается из строки через утилиту МассивЧиселИзСтроки. Затем спрос регистрируется в модели как транзит-вектор: затрата на дуге (i → j) зависит только от исходящего узла i (на нём «погружается» спрос клиента i). Возвращённую ссылку сохраняем в переменную ТранзитСпроса.

// Вектор спроса: 0 — депо (никого не обслуживает), далее — спрос клиентов 1..16
Спрос = О2.Утилиты().МассивЧиселИзСтроки("0, 1, 1, 2, 4, 2, 4, 8, 8, 1, 2, 1, 2, 4, 4, 8, 8");

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

7. Ограничение грузоподъёмности

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

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

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

Ограничение не добавляется в Ограничения() отдельно — оно уже встроено в семантику ресурса. Модель сама исключит маршруты, на которых накопленный спрос в любой точке превысил бы 15.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

// Создаём построитель параметров модели маршрутизации
Построитель = О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)
        );
    КонецЦикла;
КонецЦикла;

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

// Вектор спроса: 0 — депо (никого не обслуживает), далее — спрос клиентов 1..16
Спрос = О2.Утилиты().МассивЧиселИзСтроки("0, 1, 1, 2, 4, 2, 4, 8, 8, 1, 2, 1, 2, 4, 4, 8, 8");

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

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

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

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

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

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

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

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

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

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