Применение метода ветвей и границ для задачи коммивояжера

Алгоритм Литла, Мурти, Суини и Кэрол для решения задачи коммивояжера также хорошо укладывается в указанную выше схему.

Поясним это подробнее, так как алгоритм Литла применяется не к целочисленной линейной модели, а к задаче коммивояжера в ее комбинаторной записи (мы излагаем несколько усовершенствованный вариант алгоритма). Напомним предварительно, что задача коммивояжера тесно связана с задачей о назначении, которая формулируется следующим образом. Задана матрица Применение метода ветвей и границ для задачи коммивояжера - №1 - открытая онлайн библиотека размером ( Применение метода ветвей и границ для задачи коммивояжера - №2 - открытая онлайн библиотека ). Выбрать в ней Применение метода ветвей и границ для задачи коммивояжера - №3 - открытая онлайн библиотека элементов таким образом, чтобы а) никакие два элемента не лежали в одной строке или в одном столбце и б) сумма Применение метода ветвей и границ для задачи коммивояжера - №4 - открытая онлайн библиотека , соответствующая выбранным элементам, была бы минимальной.

Упорядоченные пары Применение метода ветвей и границ для задачи коммивояжера - №5 - открытая онлайн библиотека , соответствующие выбранным элементам Применение метода ветвей и границ для задачи коммивояжера - №6 - открытая онлайн библиотека , можно (в терминах задачи коммивояжера) интерпретировать как «поездки» из города Применение метода ветвей и границ для задачи коммивояжера - №7 - открытая онлайн библиотека непосредственно в город Применение метода ветвей и границ для задачи коммивояжера - №8 - открытая онлайн библиотека . Разница же заключается в том, что в задаче о назначении не исключены петли (назначение элементов Применение метода ветвей и границ для задачи коммивояжера - №9 - открытая онлайн библиотека ) и подциклы. Иначе говоря, здесь не гарантируется связность маршрута. Петли можно устранить, положив Применение метода ветвей и границ для задачи коммивояжера - №10 - открытая онлайн библиотека для всех Применение метода ветвей и границ для задачи коммивояжера - №8 - открытая онлайн библиотека . С устранением же подциклов дело обстоит сложнее. Во всяком случае задачу о назначении можно рассматривать как релаксацию задачи коммивояжера (релаксировано условие связности маршрута). В то же время задача о назначении эффективно решается известными методами.

Теперь мы можем изложить модифицированный алгоритм Литла и др.

Шаг 1. Стандартный.

Шаг 2. Стандартный.

Шаг 3. Стандартный (разные варианты этого шага в разных вариантах алгоритма).

Шаг 4. Релаксация условия связности маршрута (переход от задачи коммивояжера к соответствующей задаче о назначении).

Шаг 5. Решение задачи о назначении, полученной в пункте 4.

Шаги 6, 7, 8 - стандартные.

Шаг 9. Всегда переход к шагу 11.

Шаг 10. Пропускается.

Шаг 11. Дихотомия текущей задачи-кандидата. Выбирается пара Применение метода ветвей и границ для задачи коммивояжера - №5 - открытая онлайн библиотека и разветвляется на две задачи-потомка: задача, в которой из города Применение метода ветвей и границ для задачи коммивояжера - №7 - открытая онлайн библиотека обязательна поездка в город Применение метода ветвей и границ для задачи коммивояжера - №8 - открытая онлайн библиотека . При переходе от матрицы текущей задачи-кандидата к матрице этой задачи-потомка все элементы строки Применение метода ветвей и границ для задачи коммивояжера - №7 - открытая онлайн библиотека и столбца Применение метода ветвей и границ для задачи коммивояжера - №8 - открытая онлайн библиотека , кроме Применение метода ветвей и границ для задачи коммивояжера - №9 - открытая онлайн библиотека , заменяются на +∞; задача, в которой из города Применение метода ветвей и границ для задачи коммивояжера - №7 - открытая онлайн библиотека запрещается поездка в город Применение метода ветвей и границ для задачи коммивояжера - №8 - открытая онлайн библиотека . При переходе от матрицы текущей задачи-кандидата к матрице этой задачи-потомка элемент Применение метода ветвей и границ для задачи коммивояжера - №9 - открытая онлайн библиотека . заменяется на +∞.

Шаг 12. Стандартный.

Пример 6.1. Решение задачи коммивояжера методом ветвей и границ.

Если решать задачу коммивояжера путем полного перебора вариантов, то для нахождения оптимального маршрута объезда Применение метода ветвей и границ для задачи коммивояжера - №21 - открытая онлайн библиотека городов надо перебрать Применение метода ветвей и границ для задачи коммивояжера - №22 - открытая онлайн библиотека вариантов по критерию минимальных стоимости, времени или длины маршрута. При достаточно больших Применение метода ветвей и границ для задачи коммивояжера - №21 - открытая онлайн библиотека на полный перебор вариантов требуется слишком много времени.

Более эффективно задача коммивояжера решается методом ветвей и границ. Множество всевозможных решений представляется в виде дерева – связного графа, не содержащего циклов и петель. Корень дерева объединяет все множество вариантов, а вершины дерева каждого уровня содержат два непересекающихся множества: Применение метода ветвей и границ для задачи коммивояжера - №24 - открытая онлайн библиотека и Применение метода ветвей и границ для задачи коммивояжера - №25 - открытая онлайн библиотека . Вершина Применение метода ветвей и границ для задачи коммивояжера - №26 - открытая онлайн библиотека соответствует подмножеству всех маршрутов, содержащих ребро Применение метода ветвей и границ для задачи коммивояжера - №24 - открытая онлайн библиотека (множество Применение метода ветвей и границ для задачи коммивояжера - №24 - открытая онлайн библиотека неупорядочено); вершина Применение метода ветвей и границ для задачи коммивояжера - №29 - открытая онлайн библиотека - подмножеству всех маршрутов, где это ребро отсутствует. Ветвятся не все вершины дерева. В начале проводится оценка каждой вершины данного уровня (начиная с первого), и ветвится та вершина, которая получает лучшую оценку в соответствии с выбранным критерием.

Поясним изложенный выше метод на примере нахождения оптимального маршрута коммивояжера при объезде четырех городов, в каждый из которых можно попасть из каждого в соответствии с схемой (рис. 6.2).

Применение метода ветвей и границ для задачи коммивояжера - №30 - открытая онлайн библиотека

Рис. 6.2. Схема возможных маршрутов коммивояжера.

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

Расстояния между городами зададим в виде матрицы Применение метода ветвей и границ для задачи коммивояжера - №31 - открытая онлайн библиотека (табл. 6.1). Если ребро отсутствует, то его длина задается равной Применение метода ветвей и границ для задачи коммивояжера - №32 - открытая онлайн библиотека .

На первом этапе решения определим нижнюю границу оценки множества возможных маршрутов. Для этого проведем операцию редукции матрицы по строкам и столбцам. В каждой строке матрицы Применение метода ветвей и границ для задачи коммивояжера - №31 - открытая онлайн библиотека определим минимальный элемент и вычтем его из всех элементов Применение метода ветвей и границ для задачи коммивояжера - №31 - открытая онлайн библиотека (табл. 6.2 – 6.3 ).

Таблица 6.1.

Ребра графа
Применение метода ветвей и границ для задачи коммивояжера - №32 - открытая онлайн библиотека
Применение метода ветвей и границ для задачи коммивояжера - №32 - открытая онлайн библиотека
Применение метода ветвей и границ для задачи коммивояжера - №32 - открытая онлайн библиотека
Применение метода ветвей и границ для задачи коммивояжера - №32 - открытая онлайн библиотека

Таблица 6.2. Таблица 6.3.

  Применение метода ветвей и границ для задачи коммивояжера - №39 - открытая онлайн библиотека    
Применение метода ветвей и границ для задачи коммивояжера - №32 - открытая онлайн библиотека   Применение метода ветвей и границ для задачи коммивояжера - №41 - открытая онлайн библиотека
Применение метода ветвей и границ для задачи коммивояжера - №32 - открытая онлайн библиотека Применение метода ветвей и границ для задачи коммивояжера - №43 - открытая онлайн библиотека Применение метода ветвей и границ для задачи коммивояжера - №41 - открытая онлайн библиотека
Применение метода ветвей и границ для задачи коммивояжера - №32 - открытая онлайн библиотека   Применение метода ветвей и границ для задачи коммивояжера - №41 - открытая онлайн библиотека
Применение метода ветвей и границ для задачи коммивояжера - №32 - открытая онлайн библиотека   Применение метода ветвей и границ для задачи коммивояжера - №41 - открытая онлайн библиотека
              Применение метода ветвей и границ для задачи коммивояжера - №49 - открытая онлайн библиотека

Затем аналогичную процедуру проведем по столбцам (табл. 6.4).

Таблица 6.4.

  Применение метода ветвей и границ для задачи коммивояжера - №39 - открытая онлайн библиотека
Применение метода ветвей и границ для задачи коммивояжера - №41 - открытая онлайн библиотека 0(10)
Применение метода ветвей и границ для задачи коммивояжера - №41 - открытая онлайн библиотека
0(10) Применение метода ветвей и границ для задачи коммивояжера - №41 - открытая онлайн библиотека
Применение метода ветвей и границ для задачи коммивояжера - №41 - открытая онлайн библиотека
Применение метода ветвей и границ для задачи коммивояжера - №49 - открытая онлайн библиотека Применение метода ветвей и границ для задачи коммивояжера - №56 - открытая онлайн библиотека

В результате мы получим полностью редуцированную матрицу (табл. 6.4), где величины Применение метода ветвей и границ для задачи коммивояжера - №39 - открытая онлайн библиотека и Применение метода ветвей и границ для задачи коммивояжера - №58 - открытая онлайн библиотека называют константами приведения. Сумма констант приведения определяет нижнюю границу оценки.

Далее определяем ребро Применение метода ветвей и границ для задачи коммивояжера - №24 - открытая онлайн библиотека , исключение которого максимально увеличит нижнюю границу, и разобьем все множество маршрутов относительно этого ребра на два подмножества Применение метода ветвей и границ для задачи коммивояжера - №24 - открытая онлайн библиотека и Применение метода ветвей и границ для задачи коммивояжера - №61 - открытая онлайн библиотека . С этой целью, для всех клеток матрицы с нулевыми элементами, заменяем поочередно нули на Применение метода ветвей и границ для задачи коммивояжера - №32 - открытая онлайн библиотека и определяем для них сумму констант приведения. Наибольшая сумма констант приведения равна 10 для ребра Применение метода ветвей и границ для задачи коммивояжера - №63 - открытая онлайн библиотека (табл. 6.4). Следовательно, множество всех маршрутов разбивается на подмножества Применение метода ветвей и границ для задачи коммивояжера - №63 - открытая онлайн библиотека и Применение метода ветвей и границ для задачи коммивояжера - №65 - открытая онлайн библиотека (рис. 6.3).

Применение метода ветвей и границ для задачи коммивояжера - №66 - открытая онлайн библиотека

Рис. 6.3. Дерево маршрутов после первого этапа ветвления.

Исключение ребра Применение метода ветвей и границ для задачи коммивояжера - №63 - открытая онлайн библиотека проводим путем замены элемента Применение метода ветвей и границ для задачи коммивояжера - №68 - открытая онлайн библиотека на Применение метода ветвей и границ для задачи коммивояжера - №32 - открытая онлайн библиотека , после чего осуществляем операцию редукции полученной матрицы (табл. 6.5– 6.6).

Таблица 6.5. Таблица 6.6.

  Применение метода ветвей и границ для задачи коммивояжера - №39 - открытая онлайн библиотека     Применение метода ветвей и границ для задачи коммивояжера - №39 - открытая онлайн библиотека
Применение метода ветвей и границ для задачи коммивояжера - №41 - открытая онлайн библиотека Применение метода ветвей и границ для задачи коммивояжера - №41 - открытая онлайн библиотека   Применение метода ветвей и границ для задачи коммивояжера - №41 - открытая онлайн библиотека Применение метода ветвей и границ для задачи коммивояжера - №41 - открытая онлайн библиотека
Применение метода ветвей и границ для задачи коммивояжера - №41 - открытая онлайн библиотека Применение метода ветвей и границ для задачи коммивояжера - №43 - открытая онлайн библиотека Применение метода ветвей и границ для задачи коммивояжера - №41 - открытая онлайн библиотека
0 Применение метода ветвей и границ для задачи коммивояжера - №41 - открытая онлайн библиотека   0 Применение метода ветвей и границ для задачи коммивояжера - №41 - открытая онлайн библиотека
Применение метода ветвей и границ для задачи коммивояжера - №41 - открытая онлайн библиотека   Применение метода ветвей и границ для задачи коммивояжера - №41 - открытая онлайн библиотека
              Применение метода ветвей и границ для задачи коммивояжера - №49 - открытая онлайн библиотека Применение метода ветвей и границ для задачи коммивояжера - №84 - открытая онлайн библиотека

Сумма констант приведения сокращенной матрицы равна 10. Нижняя граница оценки цикла равна 160+10=170.

Включение дуги Применение метода ветвей и границ для задачи коммивояжера - №63 - открытая онлайн библиотека осуществляется путем исключения всех элементов первой строки и третьего столбца из таблицы 6.6. Элемент Применение метода ветвей и границ для задачи коммивояжера - №86 - открытая онлайн библиотека заменяем на Применение метода ветвей и границ для задачи коммивояжера - №32 - открытая онлайн библиотека , для исключения образования негамильтонова цикла. В результате получим сокращенную матрицу Применение метода ветвей и границ для задачи коммивояжера - №88 - открытая онлайн библиотека , которая подлежит редукции.

Таблица 6.7. Таблица 6.8.

  Применение метода ветвей и границ для задачи коммивояжера - №39 - открытая онлайн библиотека     Применение метода ветвей и границ для задачи коммивояжера - №39 - открытая онлайн библиотека
Применение метода ветвей и границ для задачи коммивояжера - №41 - открытая онлайн библиотека Применение метода ветвей и границ для задачи коммивояжера - №43 - открытая онлайн библиотека Применение метода ветвей и границ для задачи коммивояжера - №41 - открытая онлайн библиотека
Применение метода ветвей и границ для задачи коммивояжера - №41 - открытая онлайн библиотека   Применение метода ветвей и границ для задачи коммивояжера - №41 - открытая онлайн библиотека
Применение метода ветвей и границ для задачи коммивояжера - №41 - открытая онлайн библиотека   0(20) Применение метода ветвей и границ для задачи коммивояжера - №41 - открытая онлайн библиотека
Применение метода ветвей и границ для задачи коммивояжера - №49 - открытая онлайн библиотека     Применение метода ветвей и границ для задачи коммивояжера - №49 - открытая онлайн библиотека Применение метода ветвей и границ для задачи коммивояжера - №84 - открытая онлайн библиотека

Нижняя граница оценки цикла при включении дуги Применение метода ветвей и границ для задачи коммивояжера - №63 - открытая онлайн библиотека также равна 160+10=170. Для определенности включим дугу Применение метода ветвей и границ для задачи коммивояжера - №63 - открытая онлайн библиотека и определим следующее ветвление дерева решений. Из табл. 6.8 видно, что максимальное увеличение нижней границы (+20) возможно по ребру Применение метода ветвей и границ для задачи коммивояжера - №103 - открытая онлайн библиотека , по которому и организуем следующее ветвление (рис. 6.4).

 
  Применение метода ветвей и границ для задачи коммивояжера - №104 - открытая онлайн библиотека

Рис. 6.4. Дерево маршрутов после второго этапа ветвления.

Рассмотрим исключение ветви Применение метода ветвей и границ для задачи коммивояжера - №103 - открытая онлайн библиотека (табл. 6.9 – 6.10).

Таблица 6.9. Таблица 6.10.

  Применение метода ветвей и границ для задачи коммивояжера - №106 - открытая онлайн библиотека     Применение метода ветвей и границ для задачи коммивояжера - №106 - открытая онлайн библиотека
Применение метода ветвей и границ для задачи коммивояжера - №108 - открытая онлайн библиотека Применение метода ветвей и границ для задачи коммивояжера - №109 - открытая онлайн библиотека Применение метода ветвей и границ для задачи коммивояжера - №108 - открытая онлайн библиотека
Применение метода ветвей и границ для задачи коммивояжера - №108 - открытая онлайн библиотека   Применение метода ветвей и границ для задачи коммивояжера - №108 - открытая онлайн библиотека
Применение метода ветвей и границ для задачи коммивояжера - №108 - открытая онлайн библиотека Применение метода ветвей и границ для задачи коммивояжера - №108 - открытая онлайн библиотека   0 Применение метода ветвей и границ для задачи коммивояжера - №108 - открытая онлайн библиотека
            Применение метода ветвей и границ для задачи коммивояжера - №116 - открытая онлайн библиотека Применение метода ветвей и границ для задачи коммивояжера - №117 - открытая онлайн библиотека

Нижняя граница оценки цикла равна 160+20=180.

Рассмотрим включение ветви Применение метода ветвей и границ для задачи коммивояжера - №118 - открытая онлайн библиотека (табл. 6.11). Элемент Применение метода ветвей и границ для задачи коммивояжера - №119 - открытая онлайн библиотека заменяем на Применение метода ветвей и границ для задачи коммивояжера - №120 - открытая онлайн библиотека . Редукция полученной матрицы не увеличивает нижнюю границу оценки, которая остается на уровне 170 Применение метода ветвей и границ для задачи коммивояжера - №109 - открытая онлайн библиотека ветвь Применение метода ветвей и границ для задачи коммивояжера - №118 - открытая онлайн библиотека включается в цикл.

Таблица 6.11.

 
Применение метода ветвей и границ для задачи коммивояжера - №108 - открытая онлайн библиотека
Применение метода ветвей и границ для задачи коммивояжера - №108 - открытая онлайн библиотека

В соответствии с последней таблицей включаем в гамильтонов цикл ребра Применение метода ветвей и границ для задачи коммивояжера - №125 - открытая онлайн библиотека и Применение метода ветвей и границ для задачи коммивояжера - №126 - открытая онлайн библиотека . После третьего ветвление дерево маршрутов примет вид (рис. 6.5).

 
  Применение метода ветвей и границ для задачи коммивояжера - №127 - открытая онлайн библиотека

Рис. 6.5. Итоговое дерево маршрутов.

В соответствии с деревом ветвлений гамильтонов контур образуют ребра: Применение метода ветвей и границ для задачи коммивояжера - №128 - открытая онлайн библиотека . Минимальная длина маршрута равна 170 км, что совпадает с нижней границей оценки.