У цьому випадку хоча б одна з перевірних вершин є пасивною вершиною будь-якого раніше сформованого фрагмента або обидві перевірні вершини є активними вершинами деякого раніше сформованого фрагмента.
Процес перевірки вершин r та s провадиться в порядку зменшення значень величин Lkr + Lks - Lrs і закінчується коли всі пари вершин r та s перевірені, або коли для усіх пар вершин r та s, що залишилися неперевіреними, Lkr + Lks - Lrs = 0.
При Lkr + Lks - Lrs = 0 створення нових фрагментів, розширення існуючих фрагментів або об’єднання раніше сформованих фрагментів об’єднаного кільцевого маршруту не призводить до скорочення його загальної протяжності, але все ж таки може бути доцільним, оскільки призводить до зменшення числа кільцевих або радіальних маршрутів, а, разом з цим, – до зменшення числа транспортних засобів, що використовуються для перевезень пошти.
Алгоритм побудови найкоротшого кільцевого маршруту наведено на рис. 2.8.
Алгоритм містить 11 блоків.
У блоці 1 уводяться значення найкоротших відстаней між вершинами графа, отримані за допомогою будь-якого алгоритму побудови найкоротших радіальних шляхів між вершинами графа.
У блоці 2 виконується розрахунок значень Lkr + Lks - Lrs для всіх пар вершин r та s за значеннями найкоротших відстаней, введених у блоці 1. В якості вершин r та s виступають всі вершини графа, крім центральної.
Початок
 |
1. Уведення значень
найкоротших відстаней
між вершинами графа
 | ||||
 | ||||
|
2. Розрахунок значень Lkr + Lks - Lrs
для всіх пар вершин r та s
3. Сортування значень Lkr + Lks - Lrs
в порядку їх зменшення
4. Формування чергової пари
перевірних вершин r та s
 |
5. Перевірні вершини Так 6. Формування нового фрагмента з
відповідають умовам центральної вершини і обох
випадку 1 перевірних вершин
 | |||
 | |||
 |
Ні
8. Формування розширеного
7. Перевірні вершини Так фрагмента з раніше
відповідають умовам сформованого фрагмента і
випадку 2 другої перевірної вершини
Ні
9. Перевірні вершини Так 10. Формуванняоб’єднаного
відповідають умовам фрагмента з обох раніше
випадку 3 сформованих фрагментів
Ні
Ні 11. Формування
об’єднаного кільцевого
маршруту закінчено
 |
Так
Кінець
Рисунок 2.8. Алгоритм побудови кільцевого маршруту
У блоці 3 провадиться сортування (упорядкування) отриманих у блоці 2 значень Lkr + Lks - Lrs в порядку їх зменшення. Рівні значення Lkr + Lks - Lrs можуть подаватися в довільному порядку.
У блоці 4 формується чергова пара перевірних вершин r та s відповідно до подання значень Lkr + Lks - Lrs, упорядкованих у блоці 3.
У блоці 5 аналізується, чи відповідають перевірні вершини умовам випадку 1 (жодна з перевірних вершин не є жодною з вершин раніше сформованих фрагментів). Якщо “Так” – перехід до блоку 6, якщо “Ні” – до блоку 7.
У блоці 6 формується новий фрагмент з центральної вершини графа та обох перевірних вершин.
У блоці 7 аналізується, чи відповідають перевірні вершини умовам випадку 2 (перша перевірна вершина є активною вершиною деякого раніше сформованого фрагмента, а друга перевірна вершина не є жодною з вершин раніше сформованих фрагментів). Якщо “Так” – перехід до блоку 8, якщо “Ні” – до блоку 9.
У блоці 8 формується розширений фрагмент з раніше сформованого фрагмента та другої перевірної вершини, визначених у блоці 7.
У блоці 9 аналізується, чи відповідають перевірні вершини умовам випадку 3 (перша перевірна вершина є активною вершиною одного, а друга – активною вершиною іншого раніше сформованих фрагментів). Якщо “Так” – перехід до блоку 10, якщо “Ні” – до блоку 11.
У блоці 10 формується об’єднаний фрагмент з обох раніше сформованих фрагментів, визначених у блоці 9.
У блоці 11 аналізується, чи закінчено формування об’єднаного кільцевого маршруту (всі пари вершин r та s перевірені, або для усіх пар вершин r та s, що залишилися неперевіреними, Lkr + Lks - Lrs = 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. Значення найкоротших відстаней між вершинами графа
| - | ||||||||||
| - | ||||||||||
| - | ||||||||||
| - | ||||||||||
| - | ||||||||||
| - | ||||||||||
| - | ||||||||||
| - | ||||||||||
| - | ||||||||||
| - |
Значення величин Lkr + Lks - Lrs (км) у виді трикутної матриці наведені у табл. 2.21.
Таблиця 2.21. Значення величин Lkr + Lks - Lrs (км)
| - | |||||||||
| - | |||||||||
| - | |||||||||
| - | |||||||||
| - | |||||||||
| - | |||||||||
| - | |||||||||
| - | |||||||||
| - |
Послідовність кроків побудови найкоротших кільцевих маршрутів (Lkr + Lks - Lrs > 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 23(7 км) сумою найкоротших відстаней L 20 + L 03 (19 км).
Хоча формально для побудови найкоротших кільцевих маршрутів в наведеному прикладі знадобилось 13 кроків, їх реальне число значно менше, оскільки при виконанні на якомусь кроці умов випадку 4 (хоча б одна з перевірних вершин є пасивною вершиною будь-якого раніше сформованого фрагмента або обидві перевірні вершини є активними вершинами деякого раніше сформованого фрагмента), ніяких дій не провадиться.
У розглянутому прикладі умови випадку 4 виконуються на кроках 5, 6, 8, 11, 12, 13, отже фактично побудова найкоротших кільцевих маршрутів виконується лише на кроках 1, 2, 3, 4, 7, 9, 10, тобто на 7 з 13 кроків.
