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

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

Процес перевірки вершин 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 виступають всі вершини графа, крім центральної.

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

Початок

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

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

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

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

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

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

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

2.Розрахунок значеньLkr + Lks - Lrs

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

3.Сортування значень Lkr + Lks - Lrs

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

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

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

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

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

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

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

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

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

Випадок 4: збереження існуючих фрагментів - student2.ru Випадок 4: збереження існуючих фрагментів - student2.ru Випадок 4: збереження існуючих фрагментів - student2.ru Випадок 4: збереження існуючих фрагментів - student2.ru Випадок 4: збереження існуючих фрагментів - student2.ru Випадок 4: збереження існуючих фрагментів - student2.ru відповідають умовам центральної вершини і обох

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

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

Ні

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

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

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

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

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

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

Ні

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

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

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

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

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

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

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

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

Випадок 4: збереження існуючих фрагментів - student2.ru об’єднаного кільцевого

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

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

Так

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

Кінець

Рисунок 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 – центральна вершина графа). Біля ребер графа зазначені їх протяжності (км).

Випадок 4: збереження існуючих фрагментів - student2.ru Випадок 4: збереження існуючих фрагментів - student2.ru Випадок 4: збереження існуючих фрагментів - student2.ru 1 2 3

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

6 6 5 6

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

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

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

8 5

Випадок 4: збереження існуючих фрагментів - student2.ru Випадок 4: збереження існуючих фрагментів - student2.ru Випадок 4: збереження існуючих фрагментів - student2.ru 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 км обумовлене заміною найкоротшої відстані L23(7 км) сумою найкоротших відстаней L20 + L03 (19 км).

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

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

Наши рекомендации