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

Допустимый маршрут х представим как множество упорядоченных пар городов:

х = .

Каждый допустимый маршрут представляет собой цикл, проходя по которому коммивояжер посещает каждый город ровно один раз и возвращается в исходный город. Каждая упорядоченная пара (i, j) является дугой маршрута. Длина F (х) маршрута х равна сумме соответствующих элементов C (i, j). Заметим, что множество всех допустимых маршрутов X содержит (n-1)! элементов.

Обозначим через матрицу расстояний. Чтобы запретить переезды вида (i,i) положим C (i, i) = +∞ (i = 1,…, n).

Пусть

.

Тогда – редуцированная матрица.

Пусть d (X) = – сумма констант редуцирования.

Тогда для любого маршрута

F (х) = =

= + d (X) ≥ d (X) (5.20)

Неравенство (5.20) показывает, что d (X) является оценкой снизу для множества Х. Кроме того, после редукции длины всех маршрутов уменьшаются на одну и ту же величину d (X) и, следовательно, оптимальный маршрут, найденный с использованием редуцированной матрицы, оптимален и для исходной задачи.

Ветвление

Процесс ветвления можно представить в виде дерева, каждая вершина которого соответствует некоторому множеству маршрутов, являющемуся подмножеством множества Х. При этом начальная вершина соответствует множеству всех маршрутов Х (см. рис. 5.1.).

Рис. 5.1. Ветвление

На каждом шаге из числа кандидатов на ветвление выбирается множество Х ¹ с наименьшей оценкой. Оно разветвляется на два подмножества и . Подмножество состоит из всех маршрутов множества Х ¹ содержащих некоторую выбранную на данном шаге дугу (r, s), подмножество , – из всех маршрутов множества Х ¹, не содержащих дуги (r,s).

Ребро дерева, соединяющее вершины Х ¹ и , помечается (r, s), а ребро дерева, соединяющее Х ¹ и помечается .

Пусть – редуцированная матрица, соответствующая вершине Х ¹. Опишем способ выбора дуги (r, s). Он основан на стремлении сделать оценку поменьше, а оценку – больше, для того, чтобы увеличить вероятность выбора для дальнейшего ветвления множества . Стремление к уменьшению приводит к выбору такой дуги (m,n), для которой

(m,n) = 0, (5.21)

поскольку все маршруты множества содержат дугу (m,n). Стремление же увеличить приводит к выбору среди дуг, удовлетворяющих условию (5.21), той дуги, для которой значение функции

максимально, т.е.:

Смысл введения функции состоит в том, что величина является оценкой снизу для длины любого маршрута из Х ¹, не содержащего дуги (m,n), так как величина выражает дополнительное расстояние, которое коммивояжер проезжает в случае, когда в маршрут не включена дуга (m,n).

Построение редуцированных матриц и и вычисление оценок снизу

Положим:

Искомая редуцированная матрица получается из с помощью описанной выше процедуры редуцирования. Сумма констант редуцирования равна при этом , а величина

= d (Х ¹) +

является оценкой снизу для целевой функции F (x) на множестве .

Рассмотрим теперь множество . Все маршруты из этого множества содержат дугу (r,s). Найдем максимальный связанный путь, который принадлежит всем маршрутам множества Х ¹ и содержит дугу (r,s). Пусть этот путь начинается в городе m и заканчивается в городе t (может быть, m = r или t = s, или то и другое одновременно). Чтобы запретить подцикл, начинающийся и заканчивающийся в m, положим (t,m) = +∞. Остальные элементы матрицы полагаем равными соответствующим элементам матрицы , при этом строку, соответствующую городу r и столбец, соответствующий городу s, в матрицу не включаем, поскольку все маршруты из содержат дуги (r,s).

Редуцированная матрица расстояний для вершины получается из матрицы с помощью операции редуцирования. При этом оценка снизу для функции F (x) на множестве вычисляется по формуле

= d (Х ¹) + t,

где t – сумма констант редуцирования.