Задача коммивояжера. Цель работы: построить маршрут через 6 городов с минимальными транспортными затратами при том, что каждый город можно посетить только один раз и в конце

Цель работы: построить маршрут через 6 городов с минимальными транспортными затратами при том, что каждый город можно посетить только один раз и в конце необходимо вернуться к начальному пункту (нахождение гауссова цикла минимального веса на взвешенном ориентированном графе).

Условие:

Стоимость проезда из города i в город j задана матрицей:

По заданию, к ограничениям, заданным условием задачи (C_ii=∞, т.е. движение из города i в этот же город невозможно), добавляется еще один невозможный переезд. Он обозначены ∞.

Ограничения:

где x_ij = 0, если нет движения из i в j и x_ij = 1, если такое движение есть. Первая строка означает, что число выездов из i в j = 1, а вторая – что в j можно въехать только один раз. Еще одно ограничение – маршрут должен быть циклическим.

Целевая функция:

,

где c_ij – стоимость переезда из города i в j.

Порядок выполнения работы:

Задача решается методом ветвей и границ. Множество возможных циклов (маршрутов) обхода городов последовательно разбивается (ветвится) на уменьшающиеся подмножества, образуя дерево подмножеств. Любое подмножество можно ветвить до тех пор, пока оно не будет состоять из одного цикла. Чтобы не порождать все возможные маршруты коммивояжера, для каждого из подмножеств вычисляется "граница" – оценка, которая не больше стоимости любого маршрута из подмножества.

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

Если стоимость какого-либо маршрута не больше оценок всех неразветвленных подмножеств (листьев), то этот маршрут является оптимальным и задача решена.

Данный метод является итерационным. Каждая итерация включает следующие действия:

1. Выполняется приведение по строкам текущей матрицы (из каждого элемента строки вычитается значение наименьшего элемента данной строки).
2. Аналогично выполняется приведение по столбцам.
3. Вычисляется оценка подмножества (сумма вычтенных в пп.1 и 2 элементов). В данном случае – 13:

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

1. Вычисляется оценка подмножества, в котором дуга запрещается (первоначальная оценка плюс оценка нуля, соответствующего выбранной дуге).
2. Строка и столбец с выбранным нулем выкидываются:

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

Далее начинается новая итерация, т.е. возврат к п.1 с усеченной матрицей. Итерации производятся до тех пор, пока в матрице не останется две строки и два столбца. К графу добавляются оставшиеся две дуги. В результате итераций граф и дерево принимают следующий вид:

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

Оптимальный маршрут коммивояжера: 1→6→4→5→2→3→1.

Поиск по сайту: