Задача коммивояжера

9

Задача

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

Решение

Возьмем в качестве произвольного маршрута:

X₀ = (1,2);(2,3);(3,4);(4,5);(5,6);(6,1)

Тогда F(X₀) = 14 + 34 + 24 + 9 + 30 + 1 = 112

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

d_i = min(j) d_ij

i j	1	2	3	4	5	6	di
1	M	14	40	33	16	5	5
2	48	M	34	4	11	24	4
3	57	85	M	24	38	52	24
4	30	50	44	M	9	31	9
5	18	42	24	31	M	30	18
6	1	38	31	19	32	M	1

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

i j	1	2	3	4	5	6
1	M	9	35	28	11	0
2	44	M	30	0	7	20
3	33	61	M	0	14	28
4	21	41	35	M	0	22
5	0	24	6	13	M	12
6	0	37	30	18	31	M

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

i j	1	2	3	4	5	6
1	M	9	35	28	11	0
2	44	M	30	0	7	20
3	33	61	M	0	14	28
4	21	41	35	M	0	22
5	0	24	6	13	M	12
6	0	37	30	18	31	M
dj	0	9	6	0	0	0

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

i j	1	2	3	4	5	6
1	M	0	29	28	11	0
2	44	M	24	0	7	20
3	33	52	M	0	14	28
4	21	32	29	M	0	22
5	0	15	0	13	M	12
6	0	28	24	18	31	M

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

H = 5+4+24+9+18+1+0+9+6+0+0+0 = 76

Элементы матрицы d_ij соответствуют расстоянию от пункта i до пункта j. Поскольку в матрице n городов, то D является матрицей nxn с неотрицательными элементами d_ij >=0. Каждый допустимый маршрут представляет собой цикл, по которому коммивояжер посещает город только один раз и возвращается в исходный город. Длина маршрута определяется выражением: F(M_k) = ∑d_ij Причем каждая строка и столбец входят в маршрут только один раз с элементом d_ij .

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

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

i j	1	2	3	4	5	6	di
1	M	0(15)	29	28	11	0(12)	0
2	44	M	24	0(7)	7	20	7
3	33	52	M	0(14)	14	28	14
4	21	32	29	M	0(28)	22	21
5	0(0)	15	0(24)	13	M	12	0
6	0(18)	28	24	18	31	M	18
dj	0	15	24	0	7	12	0

d(1,2) = 0 + 15 = 15; d(1,6) = 0 + 12 = 12; d(2,4) = 7 + 0 = 7; d(3,4) = 14 + 0 = 14; d(4,5) = 21 + 7 = 28; d(5,1) = 0 + 0 = 0; d(5,3) = 0 + 24 = 24; d(6,1) = 18 + 0 = 18;

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

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

H(4*,5*) = 76 + 28 = 104

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

i j	1	2	3	4	5	6	di
1	M	0	29	28	11	0	0
2	44	M	24	0	7	20	0
3	33	52	M	0	14	28	0
4	21	32	29	M	M	22	21
5	0	15	0	13	M	12	0
6	0	28	24	18	31	M	0
dj	0	0	0	0	7	0	28

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

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

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

∑d_i + ∑d_j = 0

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

i j	1	2	3	4	6	di
1	M	0	29	28	0	0
2	44	M	24	0	20	0
3	33	52	M	0	28	0
5	0	15	0	M	12	0
6	0	28	24	18	M	0
dj	0	0	0	0	0	0

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

H(4,5) = 76 + 0 = 76 ≤ 104

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

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

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

i j	1	2	3	4	6	di
1	M	0(15)	29	28	0(12)	0
2	44	M	24	0(20)	20	20
3	33	52	M	0(28)	28	28
5	0(0)	15	0(24)	M	12	0
6	0(18)	28	24	18	M	18
dj	0	15	24	0	12	0

d(1,2) = 0 + 15 = 15; d(1,6) = 0 + 12 = 12; d(2,4) = 20 + 0 = 20; d(3,4) = 28 + 0 = 28; d(5,1) = 0 + 0 = 0; d(5,3) = 0 + 24 = 24; d(6,1) = 18 + 0 = 18;

Наибольшая сумма констант приведения равна (28 + 0) = 28 для ребра (3,4), следовательно, множество разбивается на два подмножества (3,4) и (3*,4*). Нижняя граница гамильтоновых циклов этого подмножества: H(3*,4*) = 76 + 28 = 104. Исключение ребра (3,4) проводим путем замены элемента d₃₄ = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (3*,4*), в результате получим редуцированную матрицу.

i j	1	2	3	4	6	di
1	M	0	29	28	0	0
2	44	M	24	0	20	0
3	33	52	M	M	28	28
5	0	15	0	M	12	0
6	0	28	24	18	M	0
dj	0	0	0	0	0	28

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

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

Сумма констант приведения сокращенной матрицы: ∑d_i + ∑d_j = 20

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

i j	1	2	3	6	di
1	M	0	29	0	0
2	44	M	24	20	20
5	0	15	0	12	0
6	0	28	24	M	0
dj	0	0	0	0	20

Нижняя граница подмножества (3,4) равна: H(3,4) = 76 + 20 = 96 ≤ 104

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

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

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

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

i j	1	2	3	6	di
1	M	0(15)	5	0(12)	0
2	44	M	0(20)	20	20
5	0(12)	15	M	12	12
6	0(0)	28	0(0)	M	0
dj	0	15	0	12	0

d(1,2) = 0 + 15 = 15; d(1,6) = 0 + 12 = 12; d(2,3) = 20 + 0 = 20; d(5,1) = 12 + 0 = 12; d(6,1) = 0 + 0 = 0; d(6,3) = 0 + 0 = 0;

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

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

H(2*,3*) = 96 + 20 = 116

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

i j	1	2	3	6	di
1	M	0	5	0	0
2	44	M	M	20	20
5	0	15	M	12	0
6	0	28	0	M	0
dj	0	0	0	0	20