Задача коммивояжера (асимметричная)

Данный вариант рассматривает асимметричную версию задачи коммивояжёра (Asymmetric Traveling Salesman Problem, ATSP), где стоимость расстояния от города A до города B может отличаться от расстояния от B до A. Для полного ознакомления с задачей коммивояжёра, её теоретическими основами, понятием графов и гамильтоновых циклов настоятельно рекомендуем сначала прочитать статью о симметричной задаче коммивояжёра.

Асимметричная задача коммивояжёра отражает множество практических ситуаций, где стоимость или время перемещения зависит от направления движения:

• Городская логистика: Односторонние улицы, светофоры с неравномерными циклами, пробки в час пик, которые различаются по направлениям;
• Авиаперевозки: Влияние ветра и воздушных течений делает полёт в одну сторону быстрее, чем обратно;
• Морская навигация: Течения и приливы влияют на скорость судна в зависимости от направления;
• Горная местность: Подъём в гору занимает больше времени и расходует больше топлива, чем спуск;
• Железнодорожный транспорт: Разные тарифы на перевозку грузов в зависимости от направления;
• Производственные процессы: Время переналадки оборудования может зависеть от последовательности операций.

Асимметричная задача сложнее симметричной: количество возможных маршрутов увеличивается до (n-1)!, в отличие от (n-1)!/2 в симметричной, так как направление обхода становится критичным.

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

Дан набор из 100 точек на плоскости со случайными координатами. Необходимо найти кратчайший замкнутый маршрут, проходящий через все точки ровно один раз, при условии, что расстояние от точки i к точке j отличается от расстояния от j к i.

В данном примере асимметрия моделируется следующим образом: при движении от вершины с меньшим номером к вершине с большим номером расстояние увеличивается на 10%. Это можно интерпретировать как движение "против течения" или "в гору".

• Каждая вершина должна быть посещена ровно один раз;
• Маршрут должен быть замкнутым (возврат в начальную точку);
• Матрица расстояний асимметрична: d(i,j) ≠ d(j,i);
• Требуется минимизировать общую длину маршрута.

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

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

Используется модель ограничений с ограничением ЦиклГрафа, которое одинаково хорошо работает как для симметричных, так и для асимметричных графов. Ключевое отличие — для асимметричного случая важно различать дуги (i→j) и (j→i), так как они имеют разные веса.

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

Создаётся экземпляр модели ограничений.

// Создаем модель ограничений
Модель = О2.Модели()
    .МодельОграничений()
    .СоздатьМодель();

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

Создаются 100 точек со случайными координатами на плоскост аналогично симметричному случаю.

// Вводим данные
КоличествоВершин = 100;
Множитель        = 1000;

// Генерируем случайные координаты точек
Точки = Новый Массив();
ГСЧ   = Новый ГенераторСлучайныхЧисел();

Для К = 0 По КоличествоВершин - 1 Цикл
    X = ГСЧ.СлучайноеЧисло(0, 1000);
    Y = ГСЧ.СлучайноеЧисло(0, 1000);
    Точки.Добавить(Новый Структура("X, Y", X, Y));
КонецЦикла;

Вычисление асимметричной матрицы расстояний. Здесь проявляется ключевое отличие асимметричной задачи. Базовое евклидово расстояние вычисляется одинаково, но затем применяется модификатор, зависящий от направления движения.

// Вычисляем асимметричную матрицу расстояний между точками
Расстояния = Новый Массив(КоличествоВершин);
Для К = 0 По КоличествоВершин - 1 Цикл
    Расстояния[К] = Новый Массив(КоличествоВершин);
    Для К1 = 0 По КоличествоВершин - 1 Цикл
        Если К = К1 Тогда
            Расстояния[К][К1] = 0;
        Иначе
            РазностьX         = Точки[К1].X - Точки[К].X;
            РазностьY         = Точки[К1].Y - Точки[К].Y;
            БазовоеРасстояние = Sqrt(РазностьX * РазностьX + РазностьY * РазностьY);
            
            // Асимметрия: движение от меньшего индекса к большему дороже на 10%
            Если К < К1 Тогда
                ИтоговоеРасстояние = БазовоеРасстояние * 1.1;
            Иначе
                ИтоговоеРасстояние = БазовоеРасстояние;
            КонецЕсли;
            
            Расстояния[К][К1] = Цел(ИтоговоеРасстояние * Множитель);
        КонецЕсли;
    КонецЦикла;
КонецЦикла;

Условие Если К < К1 создаёт разные расстояния для дуг (К→К1) и (К1→К). Например:

• Расстояние от вершины 5 к вершине 10: базовое расстояние × 1.1 (движение "вверх");
• Расстояние от вершины 10 к вершине 5: базовое расстояние × 1.0 (движение "вниз");

Таким образом, матрица расстояний становится несимметричной: Расстояния(i)(j) ≠ Расстояния(j)(i).

4. Регистрация переменных

Регистрация переменных идентична симметричному случаю, но важно понимать, что теперь переменные Дуги[К][К1] и Дуги[К1][К] представляют разные дуги с разными весами.

// Регистрируем булевы переменные для дуг графа
Дуги      = Новый Массив(КоличествоВершин);
ДугиГрафа = Новый Массив();

Для К = 0 По КоличествоВершин - 1 Цикл
    Дуги[К] = Новый Массив(КоличествоВершин);
    Для К1 = 0 По КоличествоВершин - 1 Цикл
        Если К <> К1 Тогда
            Дуги[К][К1] = Модель.Переменные().ДобавитьБулеву();
            Дуга = Модель.Дуги().Добавить(К, К1, Дуги[К][К1]);
            ДугиГрафа.Добавить(Дуга);
        КонецЕсли;
    КонецЦикла;
КонецЦикла;

5. Описание ограничений

Ограничение на гамильтонов цикл остаётся неизменным — оно корректно работает как для симметричных, так и для асимметричных графов.

// Ограничение: единственный гамильтонов цикл
Модель.Ограничения().ЦиклГрафа(ДугиГрафа);

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

Здесь также проявляется асимметрия. Каждая дуга (К→К1) имеет свой уникальный вес Расстояния[К][К1], который отличается от веса обратной дуги Расстояния[К1][К].

// Целевая функция: минимизируем общую длину маршрута
Для К = 0 По КоличествоВершин - 1 Цикл
    Для К1 = 0 По КоличествоВершин - 1 Цикл
        Если К <> К1 Тогда
            // Вес дуги К→К1 может отличаться от веса дуги К1→К
            Модель.ЦелеваяФункция().ДобавитьТерм(Дуги[К][К1], Расстояния[К][К1]);
        КонецЕсли;
    КонецЦикла;
КонецЦикла;
Модель.ЦелеваяФункция().Минимизировать();

Решатель будет стремиться выбирать дуги с меньшими весами, что в асимметричном случае может привести к предпочтению определённого направления обхода графа.

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

Выполняется поиск оптимального решения.

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

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

Вывод результатов идентичен симметричному случаю. Важное следствие асимметрии: направление обхода маршрута теперь критично для итоговой длины. Обход в обратном направлении даст другую длину.

// Вывод результатов
Если Решение.РешениеНайдено() Тогда
    ФорматВывода = "ЧДЦ=2; ЧН=0; ЧГ=0";
    
    Потомки = Новый Массив(КоличествоВершин);
    Для К = 0 По КоличествоВершин - 1 Цикл
        Потомки[К] = -1;
        Для К1 = 0 По КоличествоВершин - 1 Цикл
            Если К <> К1 И Решение.ЗначениеПеременной(Дуги[К][К1]) = 1 Тогда
                Потомки[К] = К1;
                Прервать;
            КонецЕсли;
        КонецЦикла;
    КонецЦикла;
    
    Маршрут = Новый Массив();
    ТекущаяВершина = 0;
    Для Счетчик = 0 По КоличествоВершин - 1 Цикл
        Маршрут.Добавить(ТекущаяВершина);
        ТекущаяВершина = Потомки[ТекущаяВершина];
        Если ТекущаяВершина = -1 Тогда
            Прервать;
        КонецЕсли;
    КонецЦикла;
    
    ДлинаМаршрута = 0;
    Для К = 0 По Маршрут.Количество() - 1 Цикл
        Начало        = Маршрут[К];
        Конец         = Маршрут[(К + 1) % Маршрут.Количество()];
        ДлинаМаршрута = ДлинаМаршрута + Расстояния[Начало][Конец];
    КонецЦикла;
    ДлинаМаршрута = ДлинаМаршрута / Множитель;
    
    Путь = "";
    Для К = 0 По Маршрут.Количество() - 1 Цикл
        Путь = Путь + Маршрут[К];
        Если К < Маршрут.Количество() - 1 Тогда
            Путь = Путь + " → ";
        КонецЕсли;
    КонецЦикла;
    Путь = Путь + " → " + Маршрут[0];
    
    Сообщение = СтрШаблон("Асимметричная задача коммивояжера (%1 вершин)%2", КоличествоВершин, Символы.ПС);
    Сообщение = Сообщение + Символы.ПС;
    Сообщение = Сообщение + СтрШаблон("Общая длина маршрута: %1%2", Формат(ДлинаМаршрута, ФорматВывода), Символы.ПС);
    Сообщение = Сообщение + СтрШаблон("Маршрут: %1%2", Путь, Символы.ПС);
    
    Сообщить(Сообщение);
Иначе
    Сообщить("Решение не найдено! Статус: " + Решение.Статус());
КонецЕсли;

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

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

// Создаем модель ограничений
Модель = О2.Модели()
    .МодельОграничений()
    .СоздатьМодель();

// Вводим данные
КоличествоВершин = 100;
Множитель        = 1000;

// Генерируем случайные координаты точек
Точки = Новый Массив();
ГСЧ   = Новый ГенераторСлучайныхЧисел();

Для К = 0 По КоличествоВершин - 1 Цикл
    X = ГСЧ.СлучайноеЧисло(0, 1000);
    Y = ГСЧ.СлучайноеЧисло(0, 1000);
    Точки.Добавить(Новый Структура("X, Y", X, Y));
КонецЦикла;

// Вычисляем асимметричную матрицу расстояний между точками
Расстояния = Новый Массив(КоличествоВершин);
Для К = 0 По КоличествоВершин - 1 Цикл
    Расстояния[К] = Новый Массив(КоличествоВершин);
    Для К1 = 0 По КоличествоВершин - 1 Цикл
        Если К = К1 Тогда
            Расстояния[К][К1] = 0;
        Иначе
            РазностьX         = Точки[К1].X - Точки[К].X;
            РазностьY         = Точки[К1].Y - Точки[К].Y;
            БазовоеРасстояние = Sqrt(РазностьX * РазностьX + РазностьY * РазностьY);
            
            // Асимметрия: движение от меньшего индекса к большему дороже на 10%
            Если К < К1 Тогда
                ИтоговоеРасстояние = БазовоеРасстояние * 1.1;
            Иначе
                ИтоговоеРасстояние = БазовоеРасстояние;
            КонецЕсли;
            
            Расстояния[К][К1] = Цел(ИтоговоеРасстояние * Множитель);
        КонецЕсли;
    КонецЦикла;
КонецЦикла;

// Регистрируем булевы переменные для дуг графа
Дуги      = Новый Массив(КоличествоВершин);
ДугиГрафа = Новый Массив();

Для К = 0 По КоличествоВершин - 1 Цикл
    Дуги[К] = Новый Массив(КоличествоВершин);
    Для К1 = 0 По КоличествоВершин - 1 Цикл
        Если К <> К1 Тогда
            Дуги[К][К1] = Модель.Переменные().ДобавитьБулеву();
            Дуга = Модель.Дуги().Добавить(К, К1, Дуги[К][К1]);
            ДугиГрафа.Добавить(Дуга);
        КонецЕсли;
    КонецЦикла;
КонецЦикла;

// Ограничение: единственный гамильтонов цикл
Модель.Ограничения().ЦиклГрафа(ДугиГрафа);

// Целевая функция: минимизируем общую длину маршрута
Для К = 0 По КоличествоВершин - 1 Цикл
    Для К1 = 0 По КоличествоВершин - 1 Цикл
        Если К <> К1 Тогда
            // Вес дуги К→К1 может отличаться от веса дуги К1→К
            Модель.ЦелеваяФункция().ДобавитьТерм(Дуги[К][К1], Расстояния[К][К1]);
        КонецЕсли;
    КонецЦикла;
КонецЦикла;
Модель.ЦелеваяФункция().Минимизировать();

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

// Вывод результатов
Если Решение.РешениеНайдено() Тогда
    ФорматВывода = "ЧДЦ=2; ЧН=0; ЧГ=0";
    
    Потомки = Новый Массив(КоличествоВершин);
    Для К = 0 По КоличествоВершин - 1 Цикл
        Потомки[К] = -1;
        Для К1 = 0 По КоличествоВершин - 1 Цикл
            Если К <> К1 И Решение.ЗначениеПеременной(Дуги[К][К1]) = 1 Тогда
                Потомки[К] = К1;
                Прервать;
            КонецЕсли;
        КонецЦикла;
    КонецЦикла;
    
    Маршрут = Новый Массив();
    ТекущаяВершина = 0;
    Для Счетчик = 0 По КоличествоВершин - 1 Цикл
        Маршрут.Добавить(ТекущаяВершина);
        ТекущаяВершина = Потомки[ТекущаяВершина];
        Если ТекущаяВершина = -1 Тогда
            Прервать;
        КонецЕсли;
    КонецЦикла;
    
    ДлинаМаршрута = 0;
    Для К = 0 По Маршрут.Количество() - 1 Цикл
        Начало        = Маршрут[К];
        Конец         = Маршрут[(К + 1) % Маршрут.Количество()];
        ДлинаМаршрута = ДлинаМаршрута + Расстояния[Начало][Конец];
    КонецЦикла;
    ДлинаМаршрута = ДлинаМаршрута / Множитель;
    
    Путь = "";
    Для К = 0 По Маршрут.Количество() - 1 Цикл
        Путь = Путь + Маршрут[К];
        Если К < Маршрут.Количество() - 1 Тогда
            Путь = Путь + " → ";
        КонецЕсли;
    КонецЦикла;
    Путь = Путь + " → " + Маршрут[0];
    
    Сообщение = СтрШаблон("Асимметричная задача коммивояжера (%1 вершин)%2", КоличествоВершин, Символы.ПС);
    Сообщение = Сообщение + Символы.ПС;
    Сообщение = Сообщение + СтрШаблон("Общая длина маршрута: %1%2", Формат(ДлинаМаршрута, ФорматВывода), Символы.ПС);
    Сообщение = Сообщение + СтрШаблон("Маршрут: %1%2", Путь, Символы.ПС);
    
    Сообщить(Сообщение);
Иначе
    Сообщить("Решение не найдено! Статус: " + Решение.Статус());
КонецЕсли;

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