Задача побудови найкоротших кільцевих маршрутів між вузлами мережі перевезень пошти

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

Задача формулюється так: побудувати найкоротший кільцевий маршрут, що розпочинається і закінчується у деякому центральному вузлі та, як найменше, один раз проходить через кожний з решти вузлів мережі.

Сформульована задача називається задачею комівояжера і має надто складне розв’язання.

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

Алгоритм заснований на тому, що дві довільні вершини графа r та s, розташовані на відстанях L_kr та L_ks від центральної вершини k і на відстані L_rs одна від одної, при використанні радіальних маршрутів k – r – k та k – s – k обумовлюють їх загальну протяжність 2 L_kr + 2 L_ks, а при використанні кільцевого маршруту k – r – s – k – загальну протяжність L_kr + L_ks + L_rs.

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

Оскільки L_kr + L_ks - L_rs ³ 0 (рівність має місце, коли найкоротший шлях між вершинами r та s проходить через центральну вершину k), протяжність об’єднаного кільцевого маршруту ніколи не перевищує загальної протяжності радіальних маршрутів, з яких він складається.

При об’єднанні двох радіальних маршрутів в кільцевий маршрут в якості вершин r та s виступають кінцеві вершини радіальних маршрутів.

При об’єднанні радіального і кільцевого маршрутів в якості вершини r виступає кінцева вершина радіального маршруту, а в якості вершини s – перша після центральної або остання перед нею за напрямом руху вершина кільцевого маршруту.

При об’єднанні двох кільцевих маршрутів в якості вершин r та s виступають перші або останні за напрямами руху вершини кільцевих маршрутів.

На рис. 2.7 наведено ілюстрацію об’єднання радіальних та кільцевих поштових маршрутів (верхній ряд – початкові маршрути, нижній – об’єднані кільцеві маршрути).

 

r s r s r s

q p q

k k k

 

r s r s r s

q p q

k k k

 

Варіант 1 Варіант 2 Варіант 3

 

Рисунок 2.7. Об’єднання радіальних та кільцевих поштових маршрутів

У першому варіанті протяжності L_kr та L_ks входили у загальну протяжність обох радіальних маршрутів по два рази (в прямому та в зворотному напрямі), отже у протяжність об’єднаного кільцевого маршруту вони увійдуть по одному разу, внаслідок чого об’єднаний кільцевий маршрут прийме вид

k – r – s – k.

У другому варіанті протяжність L_kr входила у загальну протяжність обох маршрутів два рази, а протяжність L_ks – один раз, отже у протяжність об’єднаного кільцевого маршруту протяжність L_kr увійде один раз, а протяжність L_ks – не увійде жодного разу, внаслідок чого об’єднаний кільцевий маршрут прийме вид k – r – s – q – k.

У третьому варіанті протяжності L_kr та L_ks входили у загальну протяжність обох кільцевих маршрутів по одному разу, отже у протяжність об’єднаного кільцевого маршруту вони не увійдуть жодного разу, внаслідок чого об’єднаний кільцевий маршрут прийме вид k – p – r – s – q – k.

Підкреслимо, що визначена протяжність об’єднаного кільцевого маршруту не залежить від того, як фактично проходить найкоротший шлях між вершинами r та s.

Якщо, наприклад, у третьому варіанті найкоротший шлях між вершинами r та s проходить через вершини p та q, то загальна протяжність об’єднаного кільцевого маршруту скоротиться на L_kr + L_ks і збільшиться на L_rs, тобто на L_rp + L_pq + L_qs, внаслідок чого протяжності ділянок L_rp та L_qs увійдуть в об’єднаний кільцевий маршрут по два рази, а об’єднаний кільцевий маршрут прийме вид k – p – r – p – q – s – q – k.

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

Як обмеження при об’єднанні поштових маршрутів виступають час проходження об’єднаного кільцевого маршруту (з урахуванням часу, що витрачається на обмінювання пошти в проміжних вузлах маршруту) і вантажопідйомність транспортного засобу, що використовується для перевезень пошти на цьому маршруті.

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

Алгоритм об’єднання радіальних маршрутів в кільцевий заснований на послідовному формуванні фрагментів, що являють собою частини об’єднаного кільцевого маршруту.

В кожному фрагменті розглядаються три типи вершин:

- центральна вершина, з якої розпочинається і якою закінчується кільцевий маршрут;

- активні вершини, в якості яких виступають перша після центральної вершини і остання перед нею за напрямом руху вершини кільцевого маршруту;

- пасивні вершини, в якості яких виступають вершини, розташовані між активними вершинами кільцевих маршрутів.

В якості перевірних вершин виступають пари кінцевих вершин радіальних маршрутів.

У залежності від співвідношення перевірних вершин і вершин раніше сформованих фрагментів кільцевого об’єднаного маршруту можливі 4 випадки.