Определение оптимального замкнутого маршрута

Общие теоретические положения

Имеется n пунктов, соединенных между собой дорогами так, что из любого транспортного узла можно проехать в любой другой пункт (рисунок 2.1).

Рисунок 2.1 Схема размещения транспортных узлов, посещаемых коммивояжерами Задана матрица lij транспортных расстояний между этими пунктами (время перевозки или поездки из пункта i в пункт j). Выезжая из одного пункта, коммивояжер должен побывать в других пунктах по одному разу и вернуться в исходный пункт. Поэтому маршрут коммивояжера образует замкнутый цикл без петель. Требуется найти такой маршрут, проходящий через все пункты и заканчивающийся в пункте выезда, чтобы пройденное расстояние (время поездки) было минимальным.

Дня решения этой задачи необходимо составить математическую модель. Введем обозначения: i и j — номера пунктов выезда и въезда, lij — расстояние от пункта i до пункта j. Из таблицы 2.1 видно, что lij в общем случае может быть не равно расстоянию в обратном направлении lij? lji.

Таблица 2.1 Расстояния между пунктами.

Построим математическую модель задачи, введя булевы переменные:

xij={.

• 1, если коммивояжер из пункта i переезжает в пункт j,
• 0, если не поедет,

где i, j — 1, 2, …, n. Требуется минимизировать выражение:

(2.1).

при следующих ограничениях:

.

где Ui и Uj — произвольные вещественные значения.

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

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

вычисление нижней границы (оценки);

разбиение на подмножества, т. е. ветвление;

пересчет оценок;

нахождение решений;

определение признака оптимальности;

оценка точности приближенного решения.

Для реализации метода ветвей и границ применительно к задаче о коммивояжере необходимо конкретизировать правила ветвления, вычисления оценок и нахождения решений.

Сущность метода ветвей и границ применительно к задаче коммивояжера состоит в следующем.

1. Обозначим через G0 множество всех циклов, среди которых отыскивается кратчайший цикл t*: l (t*)=min l (t). При этом под циклом будем понимать набор из n упорядоченных пар городов, образующих замкнутый маршрут, который проходит через каждый город только один раз:

t=[(i1,i2),(i2,i3),…,(in-1,in),(in, i1)].

Длина цикла равна.

(2.2).

2. Вычислим оценку для множества G0. Для этого введем понятие приведенной матрицы и процесса приведения.

Пусть hi=minj Сij, тогда Cij'=Сij-hi0 и l (t)=.

Пусть Hj=mini Cij', тогда Cij''=Cij'-Hj0 и l (t)=.

Полученная матрица С" называется приведенной. Она обладает тем свойством, что в каждой ее строке и столбце имеется по крайней мере один нуль. Процесс, позволяющий из неотрицательной матрицы С получить приведенную неотрицательную матрицу С", называется приведением. Сумма вычитаемых в процессе приведения элементов называется приводящими константами и обозначается hУ. Оптимальный план задачи о коммивояжере с матрицей С" является оптимальным и для задачи о коммивояжере с матрицей С. Длина цикла l (t) на приведенной матрице будет меньше длины цикла l (t) на исходной матрице на сумму приводящих констант: l (t)=l (t)+hУ.

Так как приведенная матрица содержит только неотрицательные элементы, то сумма приводящих констант может служить нижней границей длины цикла при исходной матрице С, т. е. является оценкой исходного множества G0: о (G0)=hУ.

3. Произведем ветвление множества G0 на два непересекающихся подмножества G1 и G2:

подмножество G1 получается из множества G0 при добавлении следующего условия: из пункта r следует непосредственно идти в пункт s;

подмножество G2 получается из множества G0 при добавлении условия: из пункта r запрещается непосредственный переход в пункт s.

При этом пару городов (r, s) выбирают так, чтобы множество G1 с наибольшей вероятностью содержало оптимальный цикл, а множество G2 — не содержало. Следовательно, пара (r, s) выбирается из множества пар претендентов (i, j), которым соответствуют нулевые элементы матрицы С, то есть Сij=0, таким образом, чтобы циклам, входящим в подмножество G2, соответствовали как можно более длинные пути. Так как по определению подмножества G2 путь по любому из этих циклов переходит из города r в некоторый промежуточный пункт j (js), а в город s коммивояжер приезжает из некоторого пункта i (ir), длина этого пути будет не меньше чем И (r, s)=.

Поэтому необходимо выбрать пару (r, s) так, чтобы И (r, s) было максимально, т. е.

И (r, s)= (2.3).

при условии, что Сij=0.

4. Выполним преобразование матрицы расстояний при ветвлении и пересчитаем оценки. Каждому подмножеству, полученному в результате ветвление, будет соответствовать своя приведенная матрица и своя оценка. Матрица С2, соответствующая подмножеству G2, получается из матрицы С в результате следующих преобразований:

запрещается переезд из города r в город s: Сrs>;

проводится процедура приведения матрицы. Оценка подмножества G2 равна оценке исходного множества G0 и И (r, s):

о (G2)=о (G0)+И (r, s).

Для построения матрицы С1 соответствующей подмножеству G1 выполняются следующие преобразования матрицы С:

вычеркивается строка r и столбец s из матрицы С, так как из каждого города можно выезжать только один раз и в каждый город можно въезжать только один раз;

запрещается переезд из города s в город r (Сsr>), а также все другие переезды, которые приводят к образованию замкнутых подциклов;

выполняется процесс приведения матрицы С.

Оценка подмножества G1 равна оценке исходного множества G0 и сумме приводящих констант:

о (G1)=о (G0) +.

Для дальнейшего ветвления на следующем шаге выбирается то из двух полученных подмножеств G1 и G2, которое имеет наименьшую оценку. Процесс построения и оценивания подмножеств продолжается до тех пор, пока не будет получена матрица размерности 22, которая содержит только две допустимые пары городов. Эти пары являются замыкающими для некоторого маршрута без петель.

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

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