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

Історія

Невідомо, коли проблему комівояжера було досліджено вперше. Однак, відома видана в 1832 році книжка з назвою «Комівояжер — як він має поводитись і що має робити для того, аби доставляти товар та мати успіх в своїх справах — поради старого Кур'єра» (нім. Der Handlungsreisende – wie er sein soll und was er zu thun hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiß zu sein – von einem alten Commis-Voyageur), в якій описано проблему, але математичний апарат для її розв'язання не застосовується. Натомість, в ній запропоновано приклади маршрутів для деяких регіонів Німеччини та Швейцарії.

Гамільтон Вільям Роуен. Раннім варіантом задачі може розглядатись англ. Icosian Game Вільяма Гамільтона 19 століття, яка полягала в тому, щоб знайти маршрути на графі з 20 вузлами. Перші згадки в якості математичної задачі на оптимізацію належать Карлу Менґеру (нім. Karl Menger), який сформулював її в математичному колоквіумі в 1930 році так: «Ми називаємо проблемою женця (оскільки це питання виникає в кожного листоноші, зокрема, її вирішують багато мандрівників) завдання віднайти найкоротший шлях між скінченною множиною місць, відстань між якими відома.» Невдовзі з'явилась відома зараз назва задача мандруючого продавця (англ. Traveling Salesman Problem), яку запропонував Гаслер Вітні (англ. Hassler Whitney) з Принстонського Університету Разом із простотою визначення та порівняною простотою знаходження гарних розв'язків задача комівояжера відрізняється тим, що визначення насправді оптимального шляху є досить складним завданням. Зважаючи на ці властивості, починаючи з другої половини 20-го століття, дослідження задачі комівояжера, має не так практичний сенс, як теоретичний в якості моделі для розробки нових алгоритмів оптимізації. Багато сучасних поширених методів дискретної оптимізації, таких як метод діленням площиною, гілок та границь та різноманітні варіанти евристичних алгоритмів було розроблено на прикладі задачі комівояжера.

В 1950-ті та 1960-ті роки задача комівояжера привернула увагу науковців в США та Європі. Важливий внесок в дослідження задачі належить Джорджу Данцігу (англ. George Dantzig), Делберту Рею Фалкерсону (англ. Delbert Ray Fulkerson) та Селмеру Джонсону (англ. Selmer M. Johnson), котрі в 1954 році в інституті RAND Corportation сформулювали задачу у вигляді задачі дискретної оптимізації та розробили метод відсікаючої площини для її розв'язання. Використовуючи новий метод вони обчислили шлях для окремого набору вузлів (екземпляру проблеми) з 49 міст та довели, що не існує коротшого шляху.

В 1960-ті та 1970-ті роки численні групи дослідників вивчали задачу з точки зору математики та її застосування, наприклад, в інформатиці, економіці, хімії та біології. Річард Карп (англ. Richard M. Karp) в 1972 році довів NP-повноту задачі пошуку гамільтонових шляхів, із чого, через поліноміальну зводимість, випливала NP-повнота задачі комівояжера. На основі цих властивостей ним було наведено теоретичне обґрунтування складності пошуку розв'язків задачі на практиці.

Більших успіхів вдалося досягнути наприкінці 1970-тих та 1980-тих років, коли Мартін Ґрьотчел (нім. Martin Grötschel), Манфред Падберґ (нім. Manfred Padberg) та Ґіованні Рінальді (нім. Giovanni Rinaldi) та інші, із застосуванням нових методів відсікаючої площини, гілок та границь обчислили розв'язок для окремого екземпляру задачі з 2393 містами.

В 1990-ті роки Девід Аплгейт (англ. David Applegate), Роберт Біксбі (англ. Robert Bixby), Вашек Шватал (англ. Vašek Chvátal) та Вільям Кук (англ. William Cook) встановили рекорди з програмою Конкорд. Ґерхард Райнельт (нім. Gerhard Reinelt) створив TSPLIB — набір стандартизованих екземплярів задачі комівояжера різного ступеня складності для порівняння результатів роботи різних груп дослідників.

В березні 2005 року задачу з 33 810 вузлами було розв'язано програмою Конкорд: було обчислено шлях довжиною в 66 048 945 та доведено відсутність коротших шляхів. В квітні 2006 було знайдено розв'язок для екземпляру з 85 900 вузлами. Використовуючи методи декомпозиції можливо обчислити розв'язки для екземплярів задачі з мільйонами вузлів довжина яких менш ніж на 1 % більша за оптимальний.

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

Розглядається Неможливо розібрати вираз (невідома помилка): n~

міст Неможливо розібрати вираз (невідома помилка): {А}1, {А}2,..., {Аn},~
що пов'язані між собою транспортною мережею. Відома матриця відстаней від кожного міста до усіх інших:

Неможливо розібрати вираз (невідома помилка): c_{ij} =\left(\begin{array}{cccc} {0} & {c_{12} } & {...} & {c_{1n} } \\ {c_{21} } & {0} & {...} & {c_{2n} } \\ {....} & {....} & {...} & {.....} \\ {c_{n1} } & {c_{n2} } & {...} & {0} \end{array}\right),~

причому в загальному випадку не завжди Неможливо розібрати вираз (невідома помилка): c_{ij} =c_{ji}.~

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

Неможливо розібрати вираз (невідома помилка): x_{ij}~

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

Неможливо розібрати вираз (невідома помилка): \min \, \, Z=\sum _{i=1}^{n}\sum _{j=1}^{n}c_{ij} x_{ij},~

Обмеження щодо одноразового в'їзду в кожне місто:

Неможливо розібрати вираз (невідома помилка): \sum _{i=1}^{n}x_{ij} =1 \left(j=\overline{1,n;}\; i\ne j\right).~

Обмеження щодо одноразового виїзду з кожного міста:

Неможливо розібрати вираз (невідома помилка): \sum _{j=1}^{n}x_{ij} =1 \left(i=\overline{1,n};\, i\ne j\right).~

Неможливо розібрати вираз (невідома помилка): c_{ij}~

- відстань між містами. 

Зазначені обмеження не повністю описують допустимі маршрути і не виключають можливості розриву маршруту. Щоб усунути цей недолік, введемо невід'ємні цілочислові змінні Неможливо розібрати вираз (невідома помилка): u_{i} (u_{j} ) \left(i=\overline{1,n;}\; j=\overline{1,n;}\; \; i\ne j\right),~

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

Неможливо розібрати вираз (невідома помилка): u_{i} -u_{j} +nx_{ij} \le n-1\left(i=\overline{1,n;}\; j=\overline{1,n;}\; \; i\ne j\right).~

Доведемо, що для довільного маршруту, який починається в пункті Неможливо розібрати вираз (невідома помилка): ~\Alpha_1,

можна знайти такі Неможливо розібрати вираз (невідома помилка): \textit{ui}(\textit{uj})~
що задовольняють наведену нерівність. 

Нехай комівояжер переїжджає з міста Неможливо розібрати вираз (невідома помилка): ~\Alpha_i

до міста Неможливо розібрати вираз (невідома помилка): ~\Alpha_j
на Неможливо розібрати вираз (невідома помилка): ~\textit{p}~
- му кроці і допустимо також, що Неможливо розібрати вираз (невідома помилка): ~u_{i}\textit {= p},~
тоді з міста Неможливо розібрати вираз (невідома помилка): ~\Alpha_j
комівояжер вирушить на наступному, Неможливо розібрати вираз (невідома помилка): \textit{p+1}~
- му кроці і Неможливо розібрати вираз (невідома помилка): ~u_j \textit{= p+1}.
Звідси випливає, що:

Неможливо розібрати вираз (невідома помилка): ~u_{i} -u_{j} +nx_{ij} =p-(p+1)+nx_{ij} =-1+nx_{ij} \le n-1.

Така нерівність виконується для будь-яких значень Неможливо розібрати вираз (невідома помилка): \textit{i}~

та Неможливо розібрати вираз (невідома помилка): \textit{j}~
у разі, коли Неможливо розібрати вираз (невідома помилка): x_{ij} =0,~
а при Неможливо розібрати вираз (невідома помилка): x_{ij} =1~
нерівність виконується як строге рівняння. Отже, якщо вибрано маршрут пересування з Неможливо розібрати вираз (невідома помилка): \textit{i}~

-го міста до Неможливо розібрати вираз (невідома помилка): \textit{j}~ -го, то згадана нерівність фіксує два підряд порядкових номери цих міст.

Отже, маємо таку математичну модель:

Неможливо розібрати вираз (невідома помилка): \min \, \, Z=\sum _{i=1}^{n}\sum _{j=1}^{n}c_{ij} x_{ij} Неможливо розібрати вираз (невідома помилка): \left\{\begin{array}{l} {\sum _{i=1}^{n}x_{ij} =1 \; \, \, (j=\overline{1,n};\; \, \, i\ne j);} \\ {\sum _{j=1}^{n}x_{ij} =1\; \, (i=\overline{1,n};\; \, \, i\ne j);} \\ {u_{i} -u_{j} +nx_{ij} \le n-1\; (i=\overline{1,n};\, \; j=\overline{1,n};\, \; i\ne j),} \end{array}\right.
Неможливо розібрати вираз (невідома помилка): x_{ij} \in \left\{0;\, 1\right\}\; \, (i=\overline{1,n};j=\overline{1,n}).

Приклад

В економічному регіоні розміщено 6 пунктів (міст). Комівояжер, який виїжджає з міста 1, має побувати в кожному місті один раз і повернутися до вихідного пункту. Знайти найкоротший маршрут, якщо відстані між містами відомі (наведені в км на рис.1).

Розв'язання. Маємо 6 пунктів, де має побувати комівояжер.

Отже, Неможливо розібрати вираз (невідома помилка): x_{ij}~

- бульові (цілочислові) змінні. Запишемо числову економіко-математичну модель задачі комівояжера за даних умов.

Виходячи з рис.1, висновуємо, що всіх можливих маршрутів є 12. З першого міста можна потрапити до кожного з інших п'яти, відповідні маршрути позначимо змінними Неможливо розібрати вираз (невідома помилка): x_{12} , x_{13} , x_{14} , x_{15} , x_{16}.~

Друге місто пов'язане лише з трьома іншими, а саме, з першим, четвертим та п'ятим, отже, маємо такі три змінні: Неможливо розібрати вираз (невідома помилка): x_{21} , x_{24} , x_{25}.~
Аналогічно позначаємо змінні, що відповідають можливим маршрутам пересувань з третього, четвертого, п'ятого та шостого міст:

з третього - Неможливо розібрати вираз (невідома помилка): x_{31} , x_{34} , x_{36},~

з четвертого - Неможливо розібрати вираз (невідома помилка): x_{41} , x_{42} , x_{43} , x_{45} ,x_{46},~

з п'ятого - Неможливо розібрати вираз (невідома помилка): x_{51} , x_{52} , x_{54} , x_{56},~

з шостого - Неможливо розібрати вираз (невідома помилка): x_{61} , x_{63} , x_{64} , x_{65}.~

Загалом отримали 24 змінні. Однак деякі змінні, наприклад, Неможливо розібрати вираз (невідома помилка): x_{12}~

 та Неможливо розібрати вираз (невідома помилка): x_{21}~
, Неможливо розібрати вираз (невідома помилка): x_{13}~
 та Неможливо розібрати вираз (невідома помилка): x_{31}~
описують один маршрут, довжина якого за умовою задачі не змінюється залежно від напрямку пересування (у разі переїзду з першого міста до другого чи з другого до першого необхідно подолати 50 км). Отже, коефіцієнт у цільовій функції при таких змінних буде однаковим.

Критерій оптимальності - мінімізація довжини всього маршруту комівояжера:

Неможливо розібрати вираз (невідома помилка): \min \, \, Z=50x_{12} +75x_{13} +40x_{14} +70x_{15} +100x_{16} +30x_{24} +40x_{25} +50x_{34} + +70x_{36} +60x_{45} +80x_{46} +50x_{56};

а)обмеження щодо одноразового в'їзду в кожне місто:

Неможливо розібрати вираз (невідома помилка): x_{21} +x_{_{31} } +x_{41} +x_{51} +x_{61} =1;~

Неможливо розібрати вираз (невідома помилка): x_{12} +x_{42} +x_{52} =1;~

Неможливо розібрати вираз (невідома помилка): x_{13} +x_{43} +x_{63} =1;~

Неможливо розібрати вираз (невідома помилка): x_{14} +x_{24} +x_{34} +x_{54} +x_{64} =1;~

Неможливо розібрати вираз (невідома помилка): x_{15} +x_{25} +x_{45} +x_{65} =1;~

Неможливо розібрати вираз (невідома помилка): x_{16} +x_{36} +x_{46} +x_{56} =1;~

б)обмеження щодо одноразового виїзду з кожного міста:

Неможливо розібрати вираз (невідома помилка): x_{12} +x_{13} +x_{14} +x_{15} +x_{16} =1;~

Неможливо розібрати вираз (невідома помилка): x_{21} +x_{24} +x_{25} =1;~

Неможливо розібрати вираз (невідома помилка): x_{31} +x_{34} +x_{36} =1;~

Неможливо розібрати вираз (невідома помилка): x_{41} +x_{42} +x_{43} +x_{45} +x_{46} =1;~

Неможливо розібрати вираз (невідома помилка): x_{51} +x_{52} +x_{54} +x_{56} =1;~

Неможливо розібрати вираз (невідома помилка): x_{61} +x_{63} +x_{64} +x_{65} =1;~

в)обмеження щодо усунення підмаршрутів:

Неможливо розібрати вираз (невідома помилка): u_{2} -u_{4} +6x_{24} \le 5;~

Неможливо розібрати вираз (невідома помилка): u_{2} -u_{5} +6x_{25} \le 5;~

Неможливо розібрати вираз (невідома помилка): u_{3} -u_{4} +6x_{34} \le 5;~

Неможливо розібрати вираз (невідома помилка): u_{3} -u_{6} +6x_{36} \le 5;~

Неможливо розібрати вираз (невідома помилка): u_{4} -u_{2} +6x_{42} \le 5;~

Неможливо розібрати вираз (невідома помилка): u_{4} -u_{3} +6x_{43} \le 5;~

Неможливо розібрати вираз (невідома помилка): u_{4} -u_{5} +6x_{45} \le 5;~

Неможливо розібрати вираз (невідома помилка): u_{4} -u_{6} +6x_{46} \le 5;~

Неможливо розібрати вираз (невідома помилка): u_{5} -u_{2} +6x_{52} \le 5;~

Неможливо розібрати вираз (невідома помилка): u_{5} -u_{4} +6x_{54} \le 5;~

Неможливо розібрати вираз (невідома помилка): u_{5} -u_{6} +6x_{56} \le 5;~

Неможливо розібрати вираз (невідома помилка): u_{6} -u_{3} +6x_{63} \le 5;~

Неможливо розібрати вираз (невідома помилка): u_{6} -u_{4} +6x_{64} \le 5;~

Неможливо розібрати вираз (невідома помилка): u_{6} -u_{5} +6x_{65} \le 5;~

Неможливо розібрати вираз (невідома помилка): x_{ij} \in \left\{0;1\right\}\, \, \; (i=\overline{1,6};\; \, j=\overline{1,6});~

Неможливо розібрати вираз (невідома помилка): \textit{ui}(\textit{uj})~

- цілі числа Неможливо розібрати вираз (невідома помилка): \left(i=\overline{2,6;}\; j=\overline{2,6;}\; \; i\ne j\right).

Такі задачі розв'язуються спеціальними методами.

У результаті отримуємо оптимальний варіант пересування таким маршрутом (рис.2).

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

Зауважимо, що аналогічні задачі нерідко виникають на практиці, особливо у дрібному бізнесі. Типовим може бути, наприклад, таке завдання: «Фірма у місті має 25 кіосків, які торгують безалкогольними напоями. Щоденно з бази автомобілем розвозять до них товар. Як оптимально організувати розвезення певного обсягу товару?».

Література

1.ua.wiki
2.Математичне програмування - Наконечний С.І.