2 Построение кольцевого маршрута

2.1 Метод ветвей границ

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

Множество «S» (0) состоит из (n-1)! Циклов, которые разбиваются на 2 не пересекающихся множества «S» (ij) и «S» (ij) для которых вычисляются их оценки. Далее подмножества с минимальной оценкой разбивается вновь на 2 не пересекающихся подмножества, и вычисляются их оценки. Это разбиение продолжается до тех пор, пока не получится подмножество, содержащее замкнутый маршрут (цикл) удовлетворяющий наложенным ограничениям.

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

Таблица 2.1.1 - Исходные данные

Пункты начала движения	Пункты конца движения
	1	2	3	4	5
1	∞	5	4	5	23
2	8	∞	8	8	5
3	6	8	∞	11	12
4	26	11	11	∞	10
5	14	16	19	16	∞

• Выбираем самый минимальный элемент из каждой строки и записываем в графу константа приведения, вычитаем из каждого элемента константу приведения;

Таблица 2.1.2 - Приведенная матрица (по строкам)

Пункты начала движения	Пункты конца движения					Конст.
	1	2	3	4	5
1	∞	5 1	4 0	5 1	23 19	4
2	8 3	∞	8 3	8 3	5 0	5
3	6 0	8 2	∞	11 5	12 6	6
4	26 16	11 1	11 1	∞	10 0	10
5	14 0	16 2	19 5	16 2	∞	14

Таблица 2.1.3 - Приведенная матрица (по столбцам)

Пункты начала движения	Пункты конца движения
	1	2	3	4	5
1	∞	1 0	0 0	1 0	19 19
2	3 3	∞	3 3	3 2	0 0
3	0 0	2 1	∞	5 4	6 6
4	16 16	1 0	1 1	∞	0 0
5	0 0	2 1	5 5	2 1	∞
Конст.	0	1	0	1	0

• Сумма констант = 41. Так как во всех строках и столбцах есть «0», то рассчитываем для всех нулевых элементов приведенной матрицы значения Q (i и j). Для каждой клетки содержащей «0» приведенной матрицы в правом верхнем углу клетки записываем значения Q (i и j). Определяется как сумма минимального элемента i-строки и минимального элемента j-столбца, исключая «0», находящихся в i-строке и в j-столбце.

Q3.1=0+1=1 Q1.3=0+1=1

Q5.1=0+1=1 Q1.4=1+0=1

Q1.2=0+0=0 Q2.5=0+2=2

Q4.2=0+0=0 Q4.5=0+0=0

• Выбираем наибольшее значение и осуществляем ветвление (множество развивается на 2 непересекающихся множества). Наибольшее значение Q2.5. Столбец и строка данного элемента вычеркивается, в клетке Q5,2 ставится бесконечность и составляется ветвление.

43 41

Рисунок 2.1.1 - Начало ветвления дуги 2.5

Рассчитываем нижние границы подмножества.

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

h 1=4+5+6+10+14+1+1=41 h 1+Q2.5=41+2=43

Далее проводим вторую итерацию:

Так как во всех строках и столбцах есть «0», то константу приведения мы не рассчитываем, а считаем сразу элемент Q (i, j)

Для проведения второй итерации выполняются все те же операции вычисления как при первой итерации.

Таблица 2.1.4 - Приведенная матрица (вторая итерация)

Пункты начала движения	Пункты конца движения
	1	2	3	4
1	∞	0	0	0
3	0	1	∞	4
4	16	0	1	∞
5	0	∞	5	1

• Сумма констант = 0. Так как во всех строках и столбцах есть «0», то рассчитываем для всех нулевых элементов приведенной матрицы значения Q (i и j). Для каждой клетки содержащей «0» приведенной матрицы в правом верхнем углу клетки записываем значения Q (i и j). Определяется как сумма минимального элемента i-строки и минимального элемента j-столбца, исключая «0», находящихся в i-строке и в j-столбце.

Q3.1=0+1=1 (1) Q1.3=0+1=1 (3)

Q5.1=0+1=1 (2) Q1.4=1+0=1 (4)

Q1.2=0+0=0 Q4.2=0+1=1 (5)

• Получилось 5 возможных вариантов.

Выбираем первое наибольшее значение и осуществляем ветвление. Наибольшее значение Q 3.1. Столбец и строка данного элемента вычеркивается, в клетке Q 1.3 ставится бесконечность и составляется ветвление.

43 41

42 41

3.1

3.1

Рисунок 2.1.2 - Начало ветвления дуги 3.1

Рассчитываем нижние границы подмножества.

h 2=0 h1+h2=41+0=41 h1+h2+Q3.1=41+0+1=42

Таблица 2.1.5 – Приведенная матрица (третья итерация)

Пункты начала движения	Пункты конца движения			Конст.
	2	3	4
1	0	∞	0	0
4	0	1	∞	0
5	∞	5 4	1 0	1

• Сумма констант = 1. Сделав нули в необходимой строке, рассчитываем для всех нулевых элементов приведенной матрицы значения Q (i и j). Для каждой клетки содержащей «0» приведенной матрицы в правом верхнем углу клетки записываем значения Q (i и j). Определяется как сумма минимального элемента i-строки и минимального элемента j-столбца, исключая «0» находящихся в i-строке и в j-столбце.

Q1.3=0+1=1 Q4.2=0+1=1

Q5.4=0+4=4 Q1.4=0+0=0

Q1.2=0+0=0

Рассчитываем нижние границы подмножества.

h3=1 h1+h2+h3=41+0+1=42 h1+h2+Q5.4=41+0+4=45

43 41

42 41

3.1

3.1

5.4

45

5.4

42

Рисунок 2.1.3 - Начало ветвления дуги 5.4

Таблица 2.1.6 - Приведенная матрица (четвёртая итерация)

Пункты начала движения	Пункты конца движения
	2	3
1	0	∞
4	0	0

На этом ветвление заканчивается. Включение в варианты дуг Q_4.3 и Q_1.2 образуют дерево.

Полученный вариант: Z (2.5, 3.1, 5.4, 4.3, 1.2)

Затраты времени в первом варианте составили 42 минуты.

1

2

5

3

4

Рисунок 2.1.4 – Схема кольцевого маршрута методом ветвей

Выбираем второе наибольшее значение и осуществляем ветвление. Наибольшее значение Q5.1. Столбец и строка данного элемента вычеркивается, в клетке Q1,5 ставится бесконечность и составляется ветвление.

Таблица 2.1.7 - Приведенная матрица (вторая итерация)

Пункты начала движения	Пункты конца движения
	1	2	3	4
1	∞	0	0	0
3	0	1	∞	4
4	16	0	1	∞
5	0	∞	5	1

• Сумма констант = 0. Так как во всех строках и столбцах есть «0», то рассчитываем для всех нулевых элементов приведенной матрицы значения Q(i и j). Для каждой клетки содержащей «0» записываем значения Q(i и j). Определяется как сумма минимального элемента i-строки и минимального элемента j-столбца.

Q3.1=0+1=1 (1) Q1.3=0+1=1 (3)

Q5.1=0+1=1 (2) Q1.4=1+0=1 (4)

Q1.2=0+0=0 Q4.2=0+1=1 (5)

43 41

5.1

5.1

42 41

Рисунок 2.1.5 - Начало ветвления дуги 5.1

h 2=0 h1+h2=41+0=41 h1+h2+Q5.1=41+0+1=42

Таблица 2.1.8 - Приведенная матрица (третья итерация)

Пункты начала движения	Пункты конца движения
	2	3	4	Конст.
1	0	0	0	0
3	1 0	∞	4 3	1
4	0	1	∞	0

• Сумма констант = 1. Сделав нули в необходимой строке, рассчитываем для всех нулевых элементов приведенной матрицы значения Q(i и j). Для каждой клетки содержащей «0» приведенной матрицы в правом верхнем углу клетки записываем значения Q(i и j). Определяется как сумма минимального элемента i-строки и минимального элемента j-столбца, исключая «0», находящихся в i-строке и в j-столбце.

Q3.2=0+3=3 Q4.2=0+1=1

Q1.3=0+1=1 Q1.4=0+1=1

Q1.2=0+0=0

Рассчитываем нижние границы подмножества.

h 3=1 h1+h2+h3=41+0+1=42 h1+h2+Q3.2=41+0+3=44

• Для каждой клетки содержащей «0» приведенной матрицы записываем значения Q(i и j). Определяется как сумма минимального элемента i-строки и минимального элемента j-столбца, исключая «0», находящихся в i-строке и в j-столбце.

43 41

5.1

42 41

5.1

44 42

3.2

3.2

Рисунок 2.1.6 - Начало ветвления дуги 3.2

Таблица 2.1.9 - Приведенная матрица (четвёртая итерация)

Пункты начала движения	Пункты конца движения
	3	4
1	0	0
4	0	∞

На этом ветвление заканчивается. Включение в варианты дуг Q_4.3 и Q_1.4 образуют дерево.

Полученный вариант: Z (2.5, 5.1, 3.2, 4.3, 1.4)

Затраты времени во втором варианте составили 42 минуты.

1

2

5

3

4

Рисунок 2.1.7 – Схема кольцевого маршрута методом ветвей

Выбираем третье наибольшее значение и осуществляем ветвление. Наибольшее значение Q1.3. Столбец и строка данного элемента вычеркивается, в клетке Q3,1 ставится бесконечность и составляется ветвление.

Таблица 2.1.10 - Приведенная матрица (вторая итерация)

Пункты начала движения	Пункты конца движения
	1	2	3	4
1	∞	0	0	0
3	0	1	∞	4
4	16	0	1	∞
5	0	∞	5	1

• Сумма констант приведения = 0. Для каждой клетки содержащей «0» приведенной матрицы в правом верхнем углу клетки записываем значения Q(i и j). Определяется как сумма минимального элемента i-строки и минимального элемента j-столбца.

Q3.1=0+1=1 (1) Q1.3=0+1=1 (3)

Q5.1=0+1=1 (2) Q1.4=1+0=1 (4)

Q1.2=0+0=0 Q4.2=0+1=1 (5)

42 41

1.3

1.3

42 41

Рисунок 2.1.8 - Начало ветвления дуги 1.3

Рассчитываем нижние границы подмножества.

h 2=0 h1+h2=41+0=41 h1+h2+Q1.3=41+0+1=42

Таблица 2.1.11 - Приведенная матрица (третья итерация)

Пункты начала движения	Пункты конца движения
	1	2	4	Конст.
3	∞	1 0	4 3 2	1
4	16	0	∞	0
5	0	∞	1 0	0
Конст.	0	0	1

Q3.2=0+2=1 Q5.1=0+2=2

Q4.2=0+16=16 Q5.4=0+2=2

Рассчитываем нижние границы подмножества.

h 3=2 h1+h2+h3=41+0+2=43 h1+h2+Q4.2=41+0+16=57

43 41

42 41

1.3

1.3

42

4.2

57 43

4.2

Рисунок 2.1.9 - Начало ветвления дуги 4.2

Таблица 2.1.12 - Приведенная матрица (четвёртая итерация)

Пункты начала движения	Пункты конца движения
	1	4
3	∞	0
5	0	0

На этом ветвление заканчивается. Включение в варианты дуг Q_5.1 и Q_3.4 образуют дерево.

Полученный вариант: Z (2.5, 1.3, 4.2, 5.1, 3.4)

Затраты времени в третьем варианте составили 43 минуты.

1

2

5

3

4

Рисунок 2.1.10 – Схема кольцевого маршрута методом ветвей

Выбираем четвёртое наибольшее значение и осуществляем ветвление. Наибольшее значение Q1.4. Столбец и строка данного элемента вычеркивается, в клетке Q4.1 ставится бесконечность и составляется ветвление.

Таблица 2.1.13 - Приведенная матрица (вторая итерация)

Пункты начала движения	Пункты конца движения
	1	2	3	4
1	∞	0	0	0
3	0	1	∞	4
4	16	0	1	∞
5	0	∞	5	1

Q3.1=0+1=1 (1) Q1.3=0+1=1 (3)

Q5.1=0+1=1 (2) Q1.4=1+0=1 (4)

Q1.2=0+0=0 Q4.2=0+1=1 (5)

1.4

43 41

1.4

42 41

Рисунок 2.1.11 Начало ветвления дуги 1.4

Рассчитываем нижние границы подмножества.

h 2=0 h1+h2=41+0=41 h1+h2+Q1.4=41+0+1=42

Таблица 2.1.14 - Приведенная матрица (третья итерация)

Пункты начала движения	Пункты конца движения
	1	2	3
3	0	1	∞
4	∞	0	1 0
5	0	∞	5 4

• Сумма констант приведения = 0. Сделав нули в необходимой строке, рассчитываем для всех нулевых элементов приведенной матрицы значения Q(i и j). Для каждой клетки содержащей «0» приведенной матрицы в правом верхнем углу клетки записываем значения Q(i и j). Определяется как сумма минимального элемента i-строки и минимального элемента j-столбца, исключая «0» находящихся в i-строке и в j-столбце.

Q3.1=0+1=1 Q4.2=0+1=1

Q5.1=0+4=4 Q4.3=0+1=1

Рассчитываем нижние границы подмножества.

h 3=1 h1+h2+h3=41+0+1=42 h1+h2+Q5.1=41+0+4=45

• Для каждой клетки содержащей «0» приведенной матрицы в правом верхнем углу клетки записываем значения Q(i и j). Определяется как сумма минимального элемента i-строки и минимального элемента j-столбца, исключая «0» находящихся в i-строке и в j-столбце.

43 41

1.4

42 41

1.4

45 42

5.1

5.1

Рисунок 2.1.12 Начало ветвления дуги 5.1

Таблица 2.1.15 - Приведенная матрица (четвёртая итерация)

Пункты начала движения	Пункты конца движения
	2	3
3	0	∞
4	0	0

На этом ветвление заканчивается. Включение в варианты дуг Q_4.3 и Q_3.2 образуют дерево.

Полученный вариант: Z (2.5, 1.4, 5.1, 4.3, 3.2)

Затраты времени в четвёртом варианте составили 45 минут.

1

2

5

3

4

Рисунок 2.1.13 – Схема кольцевого маршрута методом ветвей

Выбираем пятое наибольшее значение и осуществляем ветвление. Наибольшее значение Q4.2. Столбец и строка данного элемента вычеркивается, в клетке Q2.4 ставится бесконечность и составляется ветвление.

Таблица 2.1.16 - Приведенная матрица (вторая итерация)

Пункты начала движения	Пункты конца движения
	1	2	3	4
1	∞	0	0	0
3	0	1	∞	4
4	16	0	1	∞
5	0	∞	5	1

• Сумма констант приведения = 0. Для каждой клетки содержащей «0» приведенной матрицы в правом верхнем углу клетки записываем значения Q(i и j).

Q3.1=0+1=1 (1) Q1.3=0+1=1 (3)

Q5.1=0+1=1 (2) Q1.4=1+0=1 (4)

Q1.2=0+0=0 Q4.2=0+1=1 (5)

4.2

4.2

43 41

42 41

Рисунок 2.1.14 Начало ветвления дуги 4.2

Рассчитываем нижние границы подмножества.

h 2=0 h1+h2=4+0=41 h1+h2+Q4.2=41+0+1=42

Таблица 2.1.17 - Приведенная матрица (третья итерация)

Пункты начала движения	Пункты конца движения
	1	3	4
1	∞	0	0
3	0	∞	4
5	0	5	1

• Сумма констант приведения = 0. Для каждой клетки содержащей «0» приведенной матрицы в правом верхнем углу клетки записываем значения Q(i и j).

Q3.1=0+4=4 Q1.3=0+4=4

Q5.1=0+5=5 Q1.3=0+4=4

Рассчитываем нижние границы подмножества.

h 3=0 h1+h2+h3=41+0+0=41 h1+h2+Q5.1=41+0+5=46

43 41

4.2

4.2

42 41

5.1

5.1

46 41

Рисунок 2.1.15 Начало ветвления дуги 5.1

Таблица 2.1.18 - Приведенная матрица (четвёртая итерация)

Пункты начала движения	Пункты конца движения
	3	4
1	0	0
3	∞	0

На этом ветвление заканчивается. Включение в варианты дуг Q_1.3 и Q_3.4 образуют дерево.

Полученный вариант: Z (2.5, 4.2, 5.1, 1.3, 3.4)

Затраты времени в пятом варианте составили 41 минута.

1

2

5

3

4

Рисунок 2.1.16 – Схема кольцевого маршрута методом ветвей

Вывод: Данный вариант получился наиболее оптимальным из пяти предложенных вариантов. Затраты времени при расчете методом ветвей и границ получились минимальными, и составили 41 минуту. Рассмотренный метод «Ветвей и границ» является точным и обеспечивает возможность получения оптимального маршрута, однако, применение этого метода без электронных средств требует проведения громоздких расчетов.