4.5. Задача про комівояжера

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

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

Алгоритм методу гілок та границь для розв’язування задачі про комівояжера.

Крок 1. Побудова деякого довільного припустимого розв’язку задачі та розрахунок значення критерію для нього.

Крок 2. Послідовне розбиття біжучої множини маршрутів, що залишилися, на все менші підмножини. Розбиття здійснюється шляхом вибору дуги та розбиття біжучої множини маршрутів на дві підмножини:

• таку, в яку включається ланка ;

• таку, в яку ланка не включається.

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

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

Крок 4. Якщо активних вузлів в дереві немає — стоп. Біжучий найкращий розв’язок є оптимальним. В іншому випадку обираємо вузол з найменшим значенням нижньої границі та переходимо до кроку 2.

Розглянемо деталі реалізації окремих кроків алгоритму.

Обчислення нижніх границь.

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

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

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

Реалізація розгалуження (розбиття біжучої підмножини маршрутів).

Нехай підмножина маршрутів, що має в своєму складі ланку , розбивається на дві підмножини: , до якої ланка не входить, (на дереві розгалужень їй відповідає вузол з позначенням ); — до якої входить ланка , . В тому випадку, коли обрана ланка , забороняється вибір ланки , тобто відповідна віддаль в матриці віддалей . Здійснюючи таким чином розбиття, ми врешті-решт побудуємо повний розв’язок. Встановити побудований маршрут можна, рухаючись від листа дерева до кореня.

Вибір ланки маршруту, по якій здійснюється розбиття.

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

Розрахунок нижніх границь для маршрутів з .

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

Нова нижня границя не повинна перевищувати довжину ні одного маршруту, до яких ланка не входить, тобто для вузла з позначкою значення нижньої границі . Для визначення максимального значення лише елементи , тому що для (якщо замінити і зробити редукцію -го рядка та стовпчика, то то сума становитиме . Таким чином — це додаткова віддаль, яку проїжджатиме комівояжер в випадку, коли в маршрут не вклюючено ланку , що відповідає редукованої біжучої матриці віддалей.

Розрахунок нижніх границь для маршрутів з .

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

Приклад 5. Знайти маршрут комівояжера мінімальної довжини, якщо задана наступна матриця віддалей:

Оберемо довільний маршрут (1-4-5-3-6-2-1). Довжину маршруту розрахуємо, виходячи з матриці віддалей. Це значення B=73 й буде верхньою границею для множини можливих маршрутів.

Редукуємо матрицю віддалей

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

(i;j)	1;4	2;4	3;6	4;1	4;2	5;6	6;2	6;3	6;5
Fij	10	1	5	1	0	2	0	9	2

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

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

Ланку (1,4) включаємо

Матриця віддалей для , коли ланку (1,4) не включаємо має наступний вигляд

Матриця віддалей для , коли ланку (2,1) не включаємо має наступний вигляд

2-1-4 5-6 , , оскільки в цих випадках утворюються локальні цикли.

2-1-4 3-5-6

Таким чином досягнутий перший припустимий розв’язок задачі, проходячи до кореня дерева, читаємо його: (6,2), (4,3), (3,5), (5,6), (2,1), (1,4), тобто маршрут (1-4-3-5-6-2-1) довжиною 63.

Відтинаємо всі неперспективні вузли, і активним залишиться лише вузол . Розгалужуємо його, і відтинаємо нащадки як неперспективні вузли. Таким чином знайдений розв’язок, тобто маршрут (1-4-3-5-6-2-1) довжиною 63 є оптимальним. Процес розв’язування у вигляді дерева наведений нижче.