Випадок 4: збереження існуючих фрагментів

У цьому випадку хоча б одна з перевірних вершин є пасивною вершиною будь-якого раніше сформованого фрагмента або обидві перевірні вершини є активними вершинами деякого раніше сформованого фрагмента.

Процес перевірки вершин r та s провадиться в порядку зменшення значень величин L_kr + L_ks - L_rs і закінчується коли всі пари вершин r та s перевірені, або коли для усіх пар вершин r та s, що залишилися неперевіреними, L_kr + L_ks - L_rs = 0.

При L_kr + L_ks - L_rs = 0 створення нових фрагментів, розширення існуючих фрагментів або об’єднання раніше сформованих фрагментів об’єднаного кільцевого маршруту не призводить до скорочення його загальної протяжності, але все ж таки може бути доцільним, оскільки призводить до зменшення числа кільцевих або радіальних маршрутів, а, разом з цим, – до зменшення числа транспортних засобів, що використовуються для перевезень пошти.

Алгоритм побудови найкоротшого кільцевого маршруту наведено на рис. 2.8.

Алгоритм містить 11 блоків.

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

У блоці 2 виконується розрахунок значень L_kr + L_ks - L_rs для всіх пар вершин r та s за значеннями найкоротших відстаней, введених у блоці 1. В якості вершин r та s виступають всі вершини графа, крім центральної.

 

 

Початок

 

1. Уведення значень

найкоротших відстаней

між вершинами графа

2. Розрахунок значень L_kr + L_ks - L_rs

для всіх пар вершин r та s

 

3. Сортування значень L_kr + L_ks - L_rs

в порядку їх зменшення

4. Формування чергової пари

перевірних вершин r та s

5. Перевірні вершини Так 6. Формування нового фрагмента з

відповідають умовам центральної вершини і обох

випадку 1 перевірних вершин

 

Ні

8. Формування розширеного

7. Перевірні вершини Так фрагмента з раніше

відповідають умовам сформованого фрагмента і

випадку 2 другої перевірної вершини

 

 

Ні

 

9. Перевірні вершини Так 10. Формуванняоб’єднаного

відповідають умовам фрагмента з обох раніше

випадку 3 сформованих фрагментів

 

Ні

 

 

Ні 11. Формування

об’єднаного кільцевого

маршруту закінчено

 

Так

Кінець

 

Рисунок 2.8. Алгоритм побудови кільцевого маршруту

 

У блоці 3 провадиться сортування (упорядкування) отриманих у блоці 2 значень L_kr + L_ks - L_rs в порядку їх зменшення. Рівні значення L_kr + L_ks - L_rs можуть подаватися в довільному порядку.

У блоці 4 формується чергова пара перевірних вершин r та s відповідно до подання значень L_kr + L_ks - L_rs, упорядкованих у блоці 3.

У блоці 5 аналізується, чи відповідають перевірні вершини умовам випадку 1 (жодна з перевірних вершин не є жодною з вершин раніше сформованих фрагментів). Якщо “Так” – перехід до блоку 6, якщо “Ні” – до блоку 7.

У блоці 6 формується новий фрагмент з центральної вершини графа та обох перевірних вершин.

У блоці 7 аналізується, чи відповідають перевірні вершини умовам випадку 2 (перша перевірна вершина є активною вершиною деякого раніше сформованого фрагмента, а друга перевірна вершина не є жодною з вершин раніше сформованих фрагментів). Якщо “Так” – перехід до блоку 8, якщо “Ні” – до блоку 9.

У блоці 8 формується розширений фрагмент з раніше сформованого фрагмента та другої перевірної вершини, визначених у блоці 7.

У блоці 9 аналізується, чи відповідають перевірні вершини умовам випадку 3 (перша перевірна вершина є активною вершиною одного, а друга – активною вершиною іншого раніше сформованих фрагментів). Якщо “Так” – перехід до блоку 10, якщо “Ні” – до блоку 11.

У блоці 10 формується об’єднаний фрагмент з обох раніше сформованих фрагментів, визначених у блоці 9.

У блоці 11 аналізується, чи закінчено формування об’єднаного кільцевого маршруту (всі пари вершин r та s перевірені, або для усіх пар вершин r та s, що залишилися неперевіреними, L_kr + L_ks - L_rs = 0). Якщо “Ні” – повернення до блоку 4, якщо “Так” – закінчення роботи алгоритму.

Зазначимо, що оскільки перевірка будь-якої пари вершин r та s завжди призводить до одного з чотирьох зазначених випадків, достатньо перевірити умови виконання лише трьох з них, тому в наведеному алгоритмі умова виконання випадку 4 не перевіряється.

Наведемо приклад побудови найкоротших кільцевих маршрутів перевезення пошти.

Початковий граф мережі наведено на рис. 2.9. Вершини графа позначені цифрами 0 … 9 (0 – центральна вершина графа). Біля ребер графа зазначені їх протяжності (км).

 

1 2 3

9 7

 

6 6 5 6

4 5

3 4 5

0 6

8 5

4 4

7 8 9

Рисунок 2.9. Початковий граф мережі

Значення найкоротших відстаней між вершинами графа (км) у виді трикутної матриці наведені у табл. 2.20.

Таблиця 2.20. Значення найкоротших відстаней між вершинами графа

-
	-
	-
	-
	-
	-
	-
	-
	-
	-

Значення величин L_kr + L_ks - L_rs (км) у виді трикутної матриці наведені у табл. 2.21.

Таблиця 2.21. Значення величин L_kr + L_ks - L_rs (км)

-
	-
	-
		-
		-
		-
			-
		-
		-

Послідовність кроків побудови найкоротших кільцевих маршрутів (L_kr + L_ks - L_rs > 0) наведено у табл. 2.22.

Таблиця 2.22. Послідовність кроків побудови найкоротших кільцевих маршрутів

Крок	Перевірні вершини	Значення величин Lkr + Lks - Lrs (км)	Фрагмент 1	Фрагмент 2
	7,8		0-7-8-0
	2,3		0-7-8-0	0-2-3-0
	8,9		0-7-8-9-0	0-2-3-0
	1,2		0-7-8-9-0	0-1-2-3-0
	2,5		0-7-8-9-0	0-1-2-3-0
	2,6		0-7-8-9-0	0-1-2-3-0
	3,5		0-7-8-9-0	0-1-2-3-5-0
	3,6		0-7-8-9-0	0-1-2-3-5-0
	5,6		0-7-8-9-0	0-1-2-3-5-6-0
	1,4		0-7-8-9-0	0-4-1-2-3-5-6-0
	2,4		0-7-8-9-0	0-4-1-2-3-5-6-0
	7,9		0-7-8-9-0	0-4-1-2-3-5-6-0
	1,3		0-7-8-9-0	0-4-1-2-3-5-6-0

 

В результаті роботи алгоритму сформовані два кільцевих маршрути: 0-7-8-9-0 протяжністю 21 км і 0-4-1-2-3-5-6-0 протяжністю 45 км.

За наявності достатнього резерву часу проходження маршруту і вантажопідйомності транспортного засобу може бути сформований об’єднаний кільцевий маршрут 0-7-8-9-4-1-2-3-5-6-0 протяжністю 66 км.

За браком часу проходження маршруту або вантажопідйомності транспортного засобу відповідний маршрут (найбільш протяжний або найбільш завантажений) може бути розділений на два маршрути, наприклад, маршрут 0-4-1-2-3-5-6-0 протяжністю 45 км може бути розділений на маршрути 0-4-1-2-0 протяжністю 27 км і 0-3-5-6-0 протяжністю 30 км. Зростання загальної протяжності маршрутів на 12 км обумовлене заміною найкоротшої відстані L ₂₃(7 км) сумою найкоротших відстаней L ₂₀ + L ₀₃ (19 км).

Хоча формально для побудови найкоротших кільцевих маршрутів в наведеному прикладі знадобилось 13 кроків, їх реальне число значно менше, оскільки при виконанні на якомусь кроці умов випадку 4 (хоча б одна з перевірних вершин є пасивною вершиною будь-якого раніше сформованого фрагмента або обидві перевірні вершини є активними вершинами деякого раніше сформованого фрагмента), ніяких дій не провадиться.

У розглянутому прикладі умови випадку 4 виконуються на кроках 5, 6, 8, 11, 12, 13, отже фактично побудова найкоротших кільцевих маршрутів виконується лише на кроках 1, 2, 3, 4, 7, 9, 10, тобто на 7 з 13 кроків.