Зада́ча комівояже́ра (комівояжер — бродячий торговець; , TSP; ) полягає у знаходженні найвигіднішого маршруту, що проходить через вказані міста хоча б по одному разу. В умовах завдання вказуються критерій вигідності маршруту (найкоротший, найдешевший, сукупний критерій тощо) і відповідні матриці відстаней, вартості тощо. Зазвичай задано, що маршрут повинен проходити через кожне місто тільки один раз, в такому випадку розв'язок знаходиться серед гамільтонових циклів.
Існує маса різновидів узагальненої постановки задачі, зокрема геометрична задача комівояжера (коли матриця відстаней відображає відстані між точками на площині), трикутна задача комівояжера (коли на матриці вартостей виконується нерівність трикутника), симетрична та асиметрична задачі комівояжера.
Прості методи розв'язання задачі комівояжера: повний лексичний перебір, жадібні алгоритми (метод найближчого сусіда), метод включення найближчого міста, метод найдешевшого включення, метод мінімального кістяка дерева. На практиці застосовують різні модифікації ефективніших методів: метод гілок і меж і метод генетичних алгоритмів, а так само алгоритм мурашиної колонії.
Всі ефективні (такі, що скорочують повний перебір) методи розв'язання задачі комівояжера — евристичні. У більшості евристичних методів знаходиться не найефективніший маршрут, а наближений розв'язок. Користуються популярністю так звані any-time алгоритми, тобто алгоритми, що поступово покращують деякий поточний наближений розв'язок.
Задача комівояжера — NP-повна. Часто на ній проводять випробування нових підходів до евристичного скорочення повного перебору.
Історія
Невідомо, коли проблему комівояжера було досліджено вперше. Однак, відома видана в 1832 році книжка з назвою «Комівояжер — як він має поводитись і що має робити для того, аби доставляти товар та мати успіх в своїх справах — поради старого Кур'єра» (), в якій описано проблему, але математичний апарат для її розв'язання не застосовується. Натомість, в ній запропоновано приклади маршрутів для деяких регіонів Німеччини та Швейцарії.
Раннім варіантом задачі є гра «Ікосіан» Вільяма Гамільтона XIX століття, яка полягала в тому, щоб знайти маршрути на графі з 20 вузлами. Перші згадки як математичної задачі на оптимізацію належать (), який сформулював її в математичному колоквіумі в 1930 році так: Ми називаємо проблемою гінця (оскільки це питання виникає в кожного листоноші, зокрема, її вирішують багато мандрівників) завдання віднайти найкоротший шлях між скінченною множиною місць, відстань між якими відома.
Wir bezeichnen als Botenproblem (weil diese Frage in der Praxis von jedem Postboten, übrigens auch von vielen Reisenden zu lösen ist) die Aufgabe, für endlich viele Punkte, deren paarweise Abstände bekannt sind, den kürzesten die Punkte verbindenden Weg zu finden. Dieses Problem ist natürlich stets durch endlich viele Versuche lösbar. Regeln, welche die Anzahl der Versuche unter die Anzahl der Permutationen der gegebenen Punkte herunterdrücken würden, sind nicht bekannt. Die Regel, man solle vom Ausgangspunkt erst zum nächstgelegenen Punkt, dann zu dem diesem nächstgelegenen Punkt gehen usw., liefert im allgemeinen nicht den kürzesten Weg.Alexander Schrijver. On the history of combinatorial optimization (till 1960). In: Handbook of Discrete Optimization (K. Aardal, G.L. Nemhauser, R. Weismantel, eds.), Elsevier, Amsterdam, 2005, pp. 1–68 |} Невдовзі з'явилась відома зараз назва задача мандруючого продавця (), яку запропонував з Принстонського Університету.
Разом із простотою визначення та порівняною простотою знаходження гарних розв'язків задача комівояжера відрізняється тим, що визначення насправді оптимального шляху є досить складним завданням. Зважаючи на ці властивості, починаючи з другої половини 20-го століття, дослідження задачі комівояжера, має не так практичний сенс, як теоретичний у ролі моделі для розробки нових алгоритмів оптимізації.
Багато сучасних поширених методів дискретної оптимізації, таких як метод діленням площиною, гілок та границь та різноманітні варіанти евристичних алгоритмів було розроблено на прикладі задачі комівояжера.
В 1950-ті та 1960-ті роки задача комівояжера привернула увагу науковців в США та Європі. Важливий внесок в дослідження задачі належить Джорджу Данцігу (), Делберту Рею Фалкерсону () та Селмеру Джонсону (), котрі в 1954 році в інституті RAND Corportation сформулювали задачу у вигляді задачі дискретної оптимізації та розробили метод відсікаючої площини для її розв'язання. Використовуючи новий метод вони обчислили шлях для окремого набору вузлів (екземпляру проблеми) з 49 міст та довели, що не існує коротшого шляху. В 1960-ті та 1970-ті роки численні групи дослідників вивчали задачу з точки зору математики та її застосування, наприклад, в інформатиці, економіці, хімії та біології.
Річард Карп () в 1972 році довів NP-повноту задачі пошуку гамільтонових шляхів, із чого, через поліноміальну зводимість, випливала NP-повнота задачі комівояжера. На основі цих властивостей ним було наведено теоретичне обґрунтування складності пошуку розв'язків задачі на практиці.
Більших успіхів вдалося досягнути наприкінці 1970-х та 1980-х років, коли Мартін Ґрьотчел (), Манфред Падберґ () та Ґіованні Рінальді () та інші, із застосуванням нових методів відсікаючої площини, гілок та границь обчислили розв'язок для окремого екземпляру задачі з 2393 містами.
В 1990-ті роки Девід Аплгейт (), Роберт Біксбі (), Вашек Хватал та Вільям Кук () встановили рекорди з програмою Конкорд. Ґерхард Райнельт () створив TSPLIB — набір стандартизованих екземплярів задачі комівояжера різного ступеня складності для порівняння результатів роботи різних груп дослідників. В березні 2005 року задачу з 33 810 вузлами було розв'язано програмою Конкорд: було обчислено шлях завдовжки 66 048 945 та доведено відсутність коротших шляхів. В квітні 2006 було знайдено розв'язок для екземпляру з 85 900 вузлами. Використовуючи методи декомпозиції можливо обчислити розв'язки для екземплярів задачі з мільйонами вузлів довжина яких менш ніж на 1 % більша за оптимальний.
Формальне визначення
Подання у вигляді графа
Для можливості застосування математичного апарату для розв'язання проблеми, її слід представити у вигляді математичної моделі. Проблему комівояжера можна представити у вигляді моделі на графі, тобто, використовуючи вершини та ребра між ними. Таким чином, вершини графа (на мал.: від A до D) відповідають містам, а ребра між вершинами та сполучення між цими містами. У відповідність кожному ребру можна зіставити вагу (на мал.: 20, 42, …), яку можна розуміти як, наприклад, відстань між містами, час або вартість подорожі. Маршрутом (також гамільтоновим маршрутом) називається маршрут на цьому графі до якого входить по одному разу кожна вершина графа. Задача полягає у відшуканні найкоротшого маршруту.
З метою спрощення задачі та гарантії існування маршруту, зазвичай вважається, що модельний граф задачі є повним, тобто, що між довільною парою вершин існує ребро. Це можна досягти тим, що в тих випадках, коли між окремими містами не існує сполучення, вводити ребра з максимальною вагою (довжиною, вартістю тощо). Через велику довжину таке ребро ніколи не потрапить до оптимального маршруту, якщо він існує.
В залежності від того, що зіставляється вазі ребер, розрізняють різні варіанти задачі, найважливішими з яких є симетрична та метрична задачі.
Асиметрична та симетрична задачі
В загальному випадку, асиметрична задача комівояжера відрізняється тим, що ребра між вершинами можуть мати різну вагу в залежності від напряму, тобто, задача моделюється орієнтованим графом. Таким чином, окрім ваги ребер графа, слід також зважати і на те, в якому напрямку знаходяться ребра.
У випадку симетричної задачі всі пари ребер між одними й тими самими вершинами мають однакову вагу, тобто, для ребра ваги однакові . Як наслідок, всі маршрути мають однакову довжину в обидва напрямки. В симетричному випадку кількість можливих маршрутів вдвічі менша за асиметричний випадок. Симетрична задача моделюється неорієнтованим графом (як показано на малюнку).
Насправді, задача комівояжера у випадку реальних міст може бути як симетричною, так і асиметричною в залежності від тривалості або довжини маршрутів в залежності від напряму руху.
Метрична задача
Симетричну задачу комівояжера називають метричною, якщо відносно довжин ребер виконується нерівність трикутника. Умовно кажучи, в таких задачах обхідні шляхи довші за прямі, тобто, ребро від вершини до вершини j ніколи не довше за шлях через проміжну вершину k:
Така властивість довжини ребер визначає вимірний простір на множині ребер та міру віддалі, що задовольняє інтуїтивне розуміння відстані.
Поширені на практиці функції віддалі є також метриками і задовольняють нерівності трикутника: Евклідова відстань в евклідовій задачі комівояжера, Манхеттенська метрика (також квартальна метрика) прямокутної задачі комівояжера, в якій відстань між вершинами на ґратці дорівнює сумі відстаней вздовж осі ординат та абсцис, Відстань Чебишова, яка визначає віддаль між вершинами решітчастого графа як максимальне значення відстані вздовж осі ординат та абсцис. Дві останні метрики знаходять застосування, наприклад, під час свердління отворів в друкованих платах коли верстат має зробити якнайбільше отворів за найменший час і може пересувати свердло незалежно в обох напрямах для переходу від одного отвору до наступного. Манхеттенська метрика відповідає випадку, коли пересування в обох напрямах відбувається послідовно, а максимальна — випадку коли пересування в обох напрямах відбувається синхронно а загальний час дорівнює максимальному часу пересування вздовж осі ординат або абсцис.
Не-метрична задача комівояжера може виникати, наприклад, у випадку мінімізації тривалості подорожі за наявності вибору транспортних засобів в різних напрямах. В такому випадку обхідний шлях літаком може бути коротший за пряме сполучення автомобілем.
Якщо, на практиці, в умовах задачі дозволяється відвідувати міста декілька раз, то симетричну задачу можна звести до метричної. Для цього задачу розглядають на так званому графі відстаней. Цей граф має таку саму множину вершин як і вихідний та, на доданок, є повністю зв'язним. Вага ребер між вершинами та на графі відстаней відповідає вазі найліпшого сполучення між вершинами та у вихідному графі. Для визначених в такий спосіб ваг виконується нерівність трикутника, і кожному маршруту на графі відстаней завжди відповідає маршрут з можливими повтореннями вершин у вихідному графі.
Формулювання у вигляді задачі дискретної оптимізації
Одним з підходів до розв'язання задачі є формулювання її у вигляді задачі дискретної оптимізації, при цьому розв'язки представляються у вигляді змінних, а зв'язки у вигляді відношень нерівності між ними. Таким чином, можливо декілька варіантів. Наприклад, симетричну задачу можна представити у вигляді множини ребер . Кожному ребру зіставляється двійкова змінна , яка дорівнює 1 якщо ребро належить маршруту та 0 в протилежному випадку. Довільний маршрут можна представити у вигляді значень множини змінних приналежності, але не кожна така множина визначає маршрут. Умовою того, що значення множини змінних визначають маршрут є описані далі лінійні нерівності.
Кожна вершина має сполучатись через пару ребер з рештою вершин, тобто, через вхідне та вихідне ребро:
В сумі кожний доданок дорівнює або 1 (належить маршруту) або 0 (не належить). Тобто, отримана сума дорівнює кількості ребер в маршруті, таких що мають вершину на одному з кінців. Вона дорівнює 2, оскільки кожна вершина має вхідне та вихідне ребро. У наведеному поруч малюнку вершина показана з вхідним та вихідними ребрами, а ребра маршруту відмічено товстішими лініями. Поруч з ребрами вказано ваги що додаються до вказаної вище суми.