Задача маршрутизации транспорта
В соседней статье Задача коммивояжера (маршрутизация) показан базовый кейс модели маршрутизации: 17 точек на плоскости и одно транспортное средство. Эта статья — естественное продолжение: постановка и входные данные те же, но автопарк состоит из нескольких транспортных средств. Это классическая задача маршрутизации транспорта (VRP, Vehicle Routing Problem).
VRP встречается в развозке заказов курьерами, маршрутах сервисных бригад, доставке с центрального склада. Модель маршрутизации поддерживает любое количество транспортных средств без изменения структуры кода: добавление дополнительных ТС в построитель — единственное отличие от постановки коммивояжера.
Условия задачи
Задан набор из 17 точек на плоскости с целочисленными координатами — те же, что в предыдущей статье. Узел 0 — общее депо: 4 транспортных средства выезжают из него, обслуживают остальные узлы и возвращаются обратно. Каждый узел посещается ровно одним транспортным средством.
Расстояние между узлами — манхэттенское: d = |x₁ − x₂| + |y₁ − y₂|. Требуется минимизировать суммарную длину маршрутов всех транспортных средств автопарка.
Решение задачи
1. Выбор модели
Применяется модель маршрутизации — та же, что и для задачи коммивояжера. Отдельной модели для VRP нет: задачи коммивояжера, маршрутизации транспорта и их расширения (грузоподъёмность, временные окна) описываются одной моделью, отличаясь количеством транспортных средств и набором ограничений.
2. Создание модели
Модель собирается через построитель параметров — как и в задаче коммивояжера, состав модели (количество узлов и транспортных средств) фиксируется на этапе построителя и в готовой модели уже не меняется. Содержательное отличие — цикл добавления 4 транспортных средств вместо одного вызова.
// Создаём построитель параметров модели маршрутизации
Построитель = О2.Модели()
.МодельМаршрутизации()
.СоздатьПостроительПараметровМодели();
// Добавляем 17 узлов
КоличествоУзлов = 17;
Для К = 0 По КоличествоУзлов - 1 Цикл
Построитель.ДобавитьУзел("Узел" + К);
КонецЦикла;
// Добавляем 4 транспортных средства с общим депо в узле 0
КоличествоТС = 4;
Для К = 1 По КоличествоТС Цикл
Построитель.ДобавитьТранспортноеСредство(0, 0, "ТС" + К);
КонецЦикла;
// Фиксируем состав модели
Модель = Построитель.СоздатьМодель();
Все четыре ТС стартуют и финишируют в узле 0, поэтому первая пара аргументов (0, 0) метода ДобавитьТранспортноеСредство одинакова для всех. Имена "ТС1"…"ТС4" нужны как читаемые метки в выводе результатов.
3. Ввод данных
Координаты 17 точек — те же, что в задаче коммивояжера: намеренная параллель, позволяющая увидеть, чем именно VRP отличается от TSP при одинаковых входных данных. Точки оформляются массивом структур через утилитный конструктор Точка2D.
// Координаты точек на плоскости
Координаты = Новый Массив();
Координаты.Добавить(О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. Описание целевой функции
К целевой функции привязывается транзит. Третий параметр УстановитьКоэффициентТранзита — транспортное средство, к которому применяется коэффициент. Если параметр не указан, коэффициент применяется ко всем транспортным средствам автопарка одновременно. Целевая функция в этом случае равна сумме длин маршрутов всех ТС — ровно то, что требуется в задаче.
// Минимизируем суммарную длину маршрутов всех ТС
Модель
.ЦелеваяФункция()
.УстановитьКоэффициентТранзита(МатрицаТранзита);
7. Решение модели
Для получения решения достаточно вызвать метод Решить объекта модели. Модель сама подбирает маршруты для всех 4 транспортных средств одновременно.
// Решение модели
Решение = Модель.Решить();
8. Вывод результатов
В отличие от задачи коммивояжера, где брался единственный маршрут Решение.Маршруты()[0], здесь массив маршрутов итерируется — по одному элементу на ТС, в порядке добавления в построитель. Каждый маршрут — структура с полем ИмяТранспортногоСредства (имя ТС из шага 2), коллекцией остановок Остановки и предрассчитанной длиной Стоимость. Суммарная длина всех маршрутов доступна через Решение.ЗначениеЦелевойФункции().
// Вывод результатов
Если Решение.РешениеНайдено() Тогда
ФорматВывода = "ЧДЦ=0; ЧН=0; ЧГ=0";
Сообщение = СтрШаблон("Задача маршрутизации транспорта (%1 ТС, %2 вершин)%3", КоличествоТС, КоличествоУзлов, Символы.ПС);
Сообщение = Сообщение + Символы.ПС;
Сообщение = Сообщение + СтрШаблон("Суммарная длина маршрутов: %1%2", Формат(Решение.ЗначениеЦелевойФункции(), ФорматВывода), Символы.ПС);
Сообщение = Сообщение + Символы.ПС;
Для Каждого Маршрут Из Решение.Маршруты() Цикл
УзлыПути = Новый Массив();
Для Каждого Остановка Из Маршрут.Остановки Цикл
УзлыПути.Добавить(Остановка.Узел);
КонецЦикла;
Путь = СтрСоединить(УзлыПути, " → ");
Сообщение = Сообщение + СтрШаблон(
"Маршрут %1 (длина %2): %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)
);
КонецЦикла;
КонецЦикла;
// Регистрируем матрицу расстояний как транзит
МатрицаТранзита = Модель
.Транзиты()
.ДобавитьМатрицу(Расстояния, "Расстояние");
// Минимизируем суммарную длину маршрутов всех ТС
Модель
.ЦелеваяФункция()
.УстановитьКоэффициентТранзита(МатрицаТранзита);
// Решение модели
Решение = Модель.Решить();
// Вывод результатов
Если Решение.РешениеНайдено() Тогда
ФорматВывода = "ЧДЦ=0; ЧН=0; ЧГ=0";
Сообщение = СтрШаблон("Задача маршрутизации транспорта (%1 ТС, %2 вершин)%3", КоличествоТС, КоличествоУзлов, Символы.ПС);
Сообщение = Сообщение + Символы.ПС;
Сообщение = Сообщение + СтрШаблон("Суммарная длина маршрутов: %1%2", Формат(Решение.ЗначениеЦелевойФункции(), ФорматВывода), Символы.ПС);
Сообщение = Сообщение + Символы.ПС;
Для Каждого Маршрут Из Решение.Маршруты() Цикл
УзлыПути = Новый Массив();
Для Каждого Остановка Из Маршрут.Остановки Цикл
УзлыПути.Добавить(Остановка.Узел);
КонецЦикла;
Путь = СтрСоединить(УзлыПути, " → ");
Сообщение = Сообщение + СтрШаблон(
"Маршрут %1 (длина %2): %3%4",
Маршрут.ИмяТранспортногоСредства,
Формат(Маршрут.Стоимость, ФорматВывода),
Путь,
Символы.ПС
);
КонецЦикла;
Сообщить(Сообщение);
Иначе
Сообщить("Решение не найдено! Статус: " + Решение.Статус());
КонецЕсли;