avangard-pressa.ru

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

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

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

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

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

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

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

Оскільки Lkr + Lks - Lrs ³ 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. Об’єднання радіальних та кільцевих поштових маршрутів

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

k – r – s – k.

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

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

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

Якщо, наприклад, у третьому варіанті найкоротший шлях між вершинами r та s проходить через вершини p та q, то загальна протяжність об’єднаного кільцевого маршруту скоротиться на Lkr + Lks і збільшиться на Lrs, тобто на Lrp + Lpq+ Lqs, внаслідок чого протяжності ділянок Lrp та Lqs увійдуть в об’єднаний кільцевий маршрут по два рази, а об’єднаний кільцевий маршрут прийме вид k – p – r – p – q – s – q – k.

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

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

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

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

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

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

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

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

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

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