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