Применение методов решения задачи коммивояжера на практике

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

Фирма по производству новогодних игрушек должна доставить заказ в 6 городов: Кирсанов (1); Котовск (2); Рассказово (3); Мичуринск (4) Инжавино (5); Уварово (6). Нужно найти кротчайший путь, объездив все города точно по одному разу и вернуться в исходный с минимумом затрат. Исходный город 1.

Расстояния между городами заданы следующей матрицей. (Таблица 1).

Таблица 1.

Исходные данные, матрица размерностью 66.

Математическая модель:

Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы С найти минимальный элемент: d_i = min (j) d_ij. (Таблица 2).

Таблица 2.

Приведение матрицы по строкам, матрица размерностью 66.

Затем вычитаем d_i из элементов рассматриваемой строки. Во вновь полученной матрице в каждой строке будет как минимум один ноль. (Таблица 3).

Таблица 3.

Результат вычитания минимальных элементов рассматриваемой строки, матрица размерностью 66.

Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент: d_j = min (i) d_ij. (Таблица 4).

Таблица 4.

Приведение матрицы по столбцам, матрица размерностью 66.

После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины d_i и d_j называются константами приведения. (Таблица 5).

Таблица 5.

Результат вычитания минимальных элементов рассматриваемого столбца, матрица размерностью 66.

Сумма констант приведения определяет нижнюю границу H: H = ?d_i + ?d_j

H = 1+1+2+1+1+1+0+0+1+0+0+0 = 8.

Элементы матрицы d_ij соответствуют расстоянию от пункта i до пункта j. Поскольку в матрице n городов, то С является матрицей nxn с неотрицательными элементами d_ij >=0.

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

Длина маршрута определяется выражением: F (M_k) = ?d_ij

Причем каждая строка и столбец входят в маршрут только один раз с элементом d_ij.

Шаг № 1. Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i, j) и (i*, j*).

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

Таблица 6.

Определение ребра ветвления, матрица размерностью 66.

d (1,6) = 1 + 0 = 1; d (2,1) = 0 + 1 = 1; d (2,3) = 0 + 0 = 0; d (3,5) = 2 + 0 = 2; d (4,6) = 1 + 0 = 1; d (5,2) = 1 + 3 = 4; d (6,3) = 0 + 0 = 0; d (6,4) = 0 + 1 = 1; d (6,5) = 0 + 0 = 0;

Наибольшая сумма констант приведения равна (1 + 3) = 4 для ребра (5,2), следовательно, множество разбивается на два подмножества (5,2) и (5*, 2*). Нижняя граница этого подмножества:

H (5*, 2*) = 8 + 4 = 12.

Исключение ребра (5,2) проводим путем замены элемента d₅₂ = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (5*, 2*), в результате получим редуцированную матрицу. (Таблица 7).

Таблица 7.

Приведение матрицы расстояний для подмножества (5*, 2*), матрица размерностью 66.

Включение ребра (5,2) проводится путем исключения всех элементов 5-ой строки и 2-го столбца, в которой элемент d₂₅ заменяем на М, для исключения образования негамильтонова цикла.

В результате получим другую сокращенную матрицу (5×5), которая подлежит операции приведения.

Сумма констант приведения сокращенной матрицы:

?d_i + ?d_j = 0.

После операции приведения сокращенная матрица будет иметь вид: (Таблица 8).

Таблица 8.

Сокращённая матрица, матрица размерностью 55.

Нижняя граница подмножества (5,2) равна:

H (5,2) = 8 + 0 = 8? 12.

Поскольку нижняя граница этого подмножества (5,2) меньше, чем подмножества (5*, 2*), то ребро (5,2) включаем в маршрут с новой границей H = 8.

Шаг № 2. Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i, j) и (i*, j*).

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

Таблица 9.

Определение ребра ветвления (5,2), матрица размерностью 55.

d (1,6) = 1 + 0 = 1; d (2,1) = 0 + 3 = 3; d (2,3) = 0 + 0 = 0; d (3,5) = 2 + 0 = 2; d (4,6) = 1 + 0 = 1; d (6,3) = 0 + 0 = 0; d (6,4) = 0 + 1 = 1; d (6,5) = 0 + 0 = 0;

Наибольшая сумма констант приведения равна (0 + 3) = 3 для ребра (2,1), следовательно, множество разбивается на два подмножества (2,1) и (2*, 1*).

Нижняя граница гамильтоновых циклов этого подмножества:

H (2*, 1*) = 8 + 3 = 11.

Исключение ребра (2,1) проводим путем замены элемента d₂₁ = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (2*, 1*), в результате получим редуцированную матрицу. (Таблица 10).

Таблица 10.

Приведение матрицы расстояний для подмножества (2*, 1*) матрица размерностью 55.

Включение ребра (2,1) проводится путем исключения всех элементов 2-ой строки и 1-го столбца, в которой элемент d₁₂ заменяем на М, для исключения образования негамильтонова цикла.

В результате получим другую сокращенную матрицу (4×4), которая подлежит операции приведения.

Сумма констант приведения сокращенной матрицы:

?d_i + ?d_j = 0.

После операции приведения сокращенная матрица будет иметь вид (Таблица 11):

Таблица 11.

Сокращённая матрица, матрица размерностью 44.

Нижняя граница подмножества (2,1) равна:

H (2,1) = 8 + 0 = 8? 11.

Чтобы исключить подциклы, запретим следующие переходы: (1,5),.

Поскольку нижняя граница этого подмножества (2,1) меньше, чем подмножества (2*, 1*), то ребро (2,1) включаем в маршрут с новой границей H = 8.

Шаг № 3. Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i, j) и (i*, j*).

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

Таблица 12.

Определение ребра ветвления (2,1) матрица размерностью 44.

d (1,6) = 1 + 0 = 1; d (3,5) = 2 + 0 = 2; d (4,6) = 1 + 0 = 1; d (6,3) = 0 + 2 = 2; d (6,4) = 0 + 1 = 1; d (6,5) = 0 + 0 = 0;

Наибольшая сумма констант приведения равна (0 + 2) = 2 для ребра (6,3), следовательно, множество разбивается на два подмножества (6,3) и (6*, 3*).

Нижняя граница гамильтоновых циклов этого подмножества:

H (6*, 3*) = 8 + 2 = 10.

Исключение ребра (6,3) проводим путем замены элемента d₆₃ = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (6*, 3*), в результате получим редуцированную матрицу. (Таблица 13).

Таблица 13.

Приведение матрицы расстояний для подмножества (6*, 3*), матрица размерностью 44.

Включение ребра (6,3) проводится путем исключения всех элементов 6-ой строки и 3-го столбца, в которой элемент d₃₆ заменяем на М, для исключения образования негамильтонова цикла.

В результате получим другую сокращенную матрицу (3×3), которая подлежит операции приведения.

Сумма констант приведения сокращенной матрицы:

?d_i + ?d_j = 1.

После операции приведения сокращенная матрица будет иметь вид: (Таблица 14).

Таблица 14.

Сокращённая матрица размерностью 33.

Нижняя граница подмножества (6,3) равна:

H (6,3) = 8 + 1 = 9? 10.

Чтобы исключить подциклы, запретим следующие переходы: (1,5),.

Поскольку нижняя граница этого подмножества (6,3) меньше, чем подмножества (6*, 3*), то ребро (6,3) включаем в маршрут с новой границей H = 9.

Шаг № 4. Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i, j) и (i*, j*).

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

Таблица 15.

Определение ребра ветвления (6,3) матрица размерностью 33.

d (1,4) = 0 + 1 = 1; d (1,6) = 0 + 0 = 0; d (3,5) = 1 + 1 = 2; d (4,6) = 1 + 0 = 1;

Наибольшая сумма констант приведения равна (1 + 1) = 2 для ребра (3,5), следовательно, множество разбивается на два подмножества (3,5) и (3*, 5*).

Нижняя граница гамильтоновых циклов этого подмножества:

H (3*, 5*) = 9 + 2 = 11.

Исключение ребра (3,5) проводим путем замены элемента d₃₅ = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (3*, 5*), в результате получим редуцированную матрицу. (Таблица 16).

Таблица 16.

Приведение матрицы расстояний для подмножества (3*, 5*) матрица размерностью 33.

Включение ребра (3,5) проводится путем исключения всех элементов 3-ой строки и 5-го столбца, в которой элемент d₅₃ заменяем на М, для исключения образования негамильтонова цикла.

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

Сумма констант приведения сокращенной матрицы:

?d_i + ?d_j = 0.

После операции приведения сокращенная матрица будет иметь вид: (Таблица 17).

Таблица 17.

Сокращённая матрица размерностью 22.

Нижняя граница подмножества (3,5) равна:

H (3,5) = 9 + 0 = 9? 11.

Поскольку нижняя граница этого подмножества (3,5) меньше, чем подмножества (3*, 5*), то ребро (3,5) включаем в маршрут с новой границей H = 9.

В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (1,4) и (4,6).

Cmin = 2+1+2+2+1+1=9.

Путь: (1,4); (4,6); (6;3); (3,5); (5,2); (2,1).

1>4>6>3>5>2>1.

Оптимальный путь Дерево ветвлений (Приложение А).