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

Исходные данные:

Пункты (узлы)	Исх.1
Исх.1	-
		-
			-
				-
					-
						-

 

Решение:

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

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

Тогда F(X₀) = 33 + 22 + 37 + 28 + 13 + 33 = 166

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

d_i = min(j) d_ij

 

i j							di
	M
		M
			M
				M
					M
						M

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

 

 

i j
	M
		M
			M
				M
					M
						M

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

 

d_j = min(i) d_ij

 

i j
	M
		M
			M
				M
					M
						M
dj

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

 

 

i j
	M
		M
			M
				M
					M
						M

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

 

H = ∑d_i + ∑d_j

H = 17+7+8+17+13+7+0+0+0+0+4+0 = 73

Элементы матрицы d_ij соответствуют расстоянию от пункта i до пункта j.

Поскольку в матрице n городов, то D является матрицей nxn с неотрицательными элементами d_ij ≥ 0

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

Длина маршрута определяется выражением:

F(M_k) = ∑d_ij

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

Шаг №1.

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

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

 

i j							di
	M			0(17)
	0(6)	M
			M		0(1)	0(0)
		0(10)		M
					M	0(4)
			0(15)			M
dj

d(1,4) = 15 + 2 = 17; d(2,1) = 2 + 4 = 6; d(3,5) = 0 + 1 = 1; d(3,6) = 0 + 0 = 0; d(4,2) = 5 + 5 = 10; d(5,6) = 4 + 0 = 4; d(6,3) = 1 + 14 = 15;

 

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

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

 

i j							di
	M			M
		M
			M
				M
					M
						M
dj

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

 

H(1*,4*) = 73 + 17 = 90

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

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

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

 

i j						di
		M
			M
	M
				M
					M
dj

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

 

∑d_i + ∑d_j = 0

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

H(1,4) = 73 + 0 = 73 ≤ 90

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

Шаг №2.

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

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

 

i j						di
	0(19)	M
			M	0(1)	0(0)
	M	0(10)
				M	0(4)
			0(15)		M
dj

d(2,1) = 15 + 4 = 19; d(3,5) = 0 + 1 = 1; d(3,6) = 0 + 0 = 0; d(4,2) = 5 + 5 = 10; d(5,6) = 4 + 0 = 4; d(6,3) = 1 + 14 = 15;

 

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

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

 

i j						di
	M	M
			M
	M
				M
					M
dj

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

 

H(2*,1*) = 73 + 19 = 92

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

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

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

 

i j					di
		M
			M
				M
dj

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

 

∑d_i + ∑d_j = 0

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

H(2,1) = 73 + 0 = 73 ≤ 92

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

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

Шаг №3.

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

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

 

i j					di
		M	0(1)	0(0)
	M			0(2)
			M	0(14)
	0(9)	0(11)		M
dj

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

 

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

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

 

i j					di
		M
	M
			M	M
				M
dj

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

 

H(5*,6*) = 73 + 14 = 87

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

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

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

 

i j				di
		M
	M
			M
dj

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

 

∑d_i + ∑d_j = 2

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

H(5,6) = 73 + 2 = 75 ≤ 87

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

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

Шаг №4.

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

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

 

i j				di
		M	0(9)
	M		0(9)
	0(9)	0(9)	M
dj

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

 

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

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

 

i j				di
		M
	M
	M		M
dj

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

 

H(6*,2*) = 75 + 9 = 84

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

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

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

 

i j			di
	M
dj

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

 

∑d_i + ∑d_j = 9

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

H(6,2) = 75 + 9 = 84 ≤ 84

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

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

В результате по дереву ветвлений гамильтонов цикл образуют ребра:

(1,4), (4,3), (3,5), (5,6), (6,2), (2,1),

Длина маршрута равна F(Mk) = 94