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

Зада́ча комівояже́ра (комівояжер — бродячий торговець; англ. Travelling Salesman Problem, TSP; нім. Problem des Handlungsreisenden) полягає у знаходженні найвигіднішого маршруту, що проходить через вказані міста хоча б по одному разу. В умовах завдання вказуються критерій вигідності маршруту (найкоротший, найдешевший, сукупний критерій тощо) і відповідні матриці відстаней, вартості тощо. Зазвичай задано, що маршрут повинен проходити через кожне місто тільки один раз, в такому випадку розв'язок знаходиться серед гамільтонових циклів.

Наведено найкоротший шлях комівояжера через 15 міст Німеччини. Всього існує 43589145600 різних шляхів.

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

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

Всі ефективні (такі, що скорочують повний перебір) методи розв'язання задачі комівояжера — евристичні. У більшості евристичних методів знаходиться не найефективніший маршрут, а наближений розв'язок. Користуються популярністю так звані any-time алгоритми, тобто алгоритми, що поступово покращують деякий поточний наближений розв'язок.

Задача комівояжера — NP-повна. Часто на ній проводять випробування нових підходів до евристичного скорочення повного перебору.

Історія

Невідомо, коли проблему комівояжера було досліджено вперше. Однак, відома видана в 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), в якій описано проблему, але математичний апарат для її розв'язання не застосовується. Натомість, в ній запропоновано приклади маршрутів для деяких регіонів Німеччини та Швейцарії.

Вільям Роуен Гамільтон

Гаслер Вітні, 1973

Раннім варіантом задачі є гра «Ікосіан» Вільяма Гамільтона XIX століття, яка полягала в тому, щоб знайти маршрути на графі з 20 вузлами. Перші згадки як математичної задачі на оптимізацію належать ^[en] (нім. Karl Menger), який сформулював її в математичному колоквіумі в 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.

Невдовзі з'явилась відома зараз назва задача мандруючого продавця (англ. Traveling Salesman Problem), яку запропонував ^[en] з Принстонського Університету.

Разом із простотою визначення та порівняною простотою знаходження гарних розв'язків задача комівояжера відрізняється тим, що визначення насправді оптимального шляху є досить складним завданням. Зважаючи на ці властивості, починаючи з другої половини 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), Вашек Хватал та Вільям Кук (англ. William Cook) встановили рекорди з програмою . Ґерхард Райнельт (нім. Gerhard Reinelt) створив TSPLIB — набір стандартизованих екземплярів задачі комівояжера різного ступеня складності для порівняння результатів роботи різних груп дослідників. В березні 2005 року задачу з 33 810 вузлами було розв'язано програмою Конкорд: було обчислено шлях завдовжки 66 048 945 та доведено відсутність коротших шляхів. В квітні 2006 було знайдено розв'язок для екземпляру з 85 900 вузлами. Використовуючи методи декомпозиції можливо обчислити розв'язки для екземплярів задачі з мільйонами вузлів довжина яких менш ніж на 1 % більша за оптимальний.

Формальне визначення

Подання у вигляді графа

Симетрична задача для чотирьох міст.

Для можливості застосування математичного апарату для розв'язання проблеми, її слід представити у вигляді математичної моделі. Проблему комівояжера можна представити у вигляді моделі на графі, тобто, використовуючи вершини та ребра між ними. Таким чином, вершини графа (на мал.: від A до D) відповідають містам, а ребра ${\displaystyle \left(i,j\right)}$ між вершинами ${\displaystyle i}$ та ${\displaystyle j}$ сполучення між цими містами. У відповідність кожному ребру ${\displaystyle \left(i,j\right)}$ можна зіставити вагу ${\displaystyle c_{ij}\geqslant 0}$ (на мал.: 20, 42, …), яку можна розуміти як, наприклад, відстань між містами, час або вартість подорожі. Маршрутом (також гамільтоновим маршрутом) називається маршрут на цьому графі до якого входить по одному разу кожна вершина графа. Задача полягає у відшуканні найкоротшого маршруту.

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

В залежності від того, що зіставляється вазі ребер, розрізняють різні варіанти задачі, найважливішими з яких є симетрична та метрична задачі.

Асиметрична та симетрична задачі

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

У випадку симетричної задачі всі пари ребер між одними й тими самими вершинами мають однакову вагу, тобто, для ребра ${\displaystyle \left(i,j\right)}$ ваги однакові ${\displaystyle c_{ij}=c_{ji}}$. Як наслідок, всі маршрути мають однакову довжину в обидва напрямки. В симетричному випадку кількість можливих маршрутів вдвічі менша за асиметричний випадок. Симетрична задача моделюється (неорієнтованим графом) (як показано на малюнку).

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

Метрична задача

Симетричну задачу комівояжера називають метричною, якщо відносно довжин ребер виконується нерівність трикутника. Умовно кажучи, в таких задачах обхідні шляхи довші за прямі, тобто, ребро від вершини ${\displaystyle i}$ до вершини j ніколи не довше за шлях через проміжну вершину k:

${\displaystyle c_{ij}\leqslant c_{ik}+c_{kj}}$

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

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

• Евклідова відстань в евклідовій задачі комівояжера,
• Манхеттенська метрика (також квартальна метрика) прямокутної задачі комівояжера, в якій відстань між вершинами на ґратці дорівнює сумі відстаней вздовж осі ординат та абсцис,
• Відстань Чебишова, яка визначає віддаль між вершинами решітчастого графа як максимальне значення відстані вздовж осі ординат та абсцис.

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

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

Якщо, на практиці, в умовах задачі дозволяється відвідувати міста декілька раз, то симетричну задачу можна звести до метричної. Для цього задачу розглядають на так званому графі відстаней. Цей граф має таку саму множину вершин як і вихідний та, на доданок, є повністю зв'язним. Вага ребер ${\displaystyle c_{ij}}$ між вершинами ${\displaystyle i}$ та ${\displaystyle j}$ на графі відстаней відповідає вазі найліпшого сполучення між вершинами ${\displaystyle i}$ та ${\displaystyle j}$ у вихідному графі. Для визначених в такий спосіб ваг ${\displaystyle c_{ij}}$ виконується нерівність трикутника, і кожному маршруту на графі відстаней завжди відповідає маршрут з можливими повтореннями вершин у вихідному графі.

Формулювання у вигляді задачі дискретної оптимізації

Одним з підходів до розв'язання задачі є формулювання її у вигляді задачі дискретної оптимізації, при цьому розв'язки представляються у вигляді змінних, а зв'язки у вигляді відношень нерівності між ними. Таким чином, можливо декілька варіантів. Наприклад, симетричну задачу можна представити у вигляді множини ребер ${\displaystyle V}$. Кожному ребру ${\displaystyle \{i,j\}}$ зіставляється двійкова змінна ${\displaystyle x_{ij}\in \{0,1\}}$, яка дорівнює 1 якщо ребро належить маршруту та 0 в протилежному випадку. Довільний маршрут можна представити у вигляді значень множини змінних приналежності, але не кожна така множина визначає маршрут. Умовою того, що значення множини змінних визначають маршрут є описані далі лінійні нерівності.

Умова кратності: кожна вершина повинна мати одне вхідне та одне вихідне ребро маршруту.

Кожна вершина має сполучатись через пару ребер з рештою вершин, тобто, через вхідне та вихідне ребро:

${\displaystyle \forall i\in V,\;\sum _{j\in V\setminus \{i\}}x_{ij}=2\qquad (1)}$

В сумі кожний доданок ${\displaystyle x_{ij}}$ дорівнює або 1 (належить маршруту) або 0 (не належить). Тобто, отримана сума дорівнює кількості ребер в маршруті, таких що мають вершину ${\displaystyle i}$ на одному з кінців. Вона дорівнює 2, оскільки кожна вершина має вхідне та вихідне ребро. У наведеному поруч малюнку вершина ${\displaystyle i}$ показана з вхідним та вихідними ребрами, а ребра маршруту відмічено товстішими лініями. Поруч з ребрами вказано ваги ${\displaystyle x_{ij}}$ що додаються до вказаної вище суми.

Цикли: змінні задовольняють умові кратності, але не визначають маршрут.

Описані раніше умови кратності виконуються не лише маршрутами, а й значеннями змінних, що відповідають відокремленим циклам, де кожна вершина належить лише одному циклу (див. малюнок). Аби уникнути подібні випадки, мають виконуватись так звані нерівності циклів (або умови усунення підмаршрутів), які було визначено Данциґом, Фалкерсоном та Джонсоном в 1954 році під назвою умови петель (англ. loop conditions). Цими нерівностями визначалась додаткова умова того, що кожна множина вершин ${\displaystyle S\subset V}$, є або порожньою, або містить всі вершини, що сполучається з рештою вершин через щонайменше два ребра:

${\displaystyle \sum _{i\in S,\;j\notin S}x_{ij}\geq 2\qquad (2)}$

для всіх множин вершин ${\displaystyle S}$ де ${\displaystyle 1\leq |S|\leq |V|-1}$. Ця сума дорівнює сумі ваг ребер маршруту між вершиною ${\displaystyle i\in S}$ та вершиною ${\displaystyle j\notin S}$. Аби усунути зайві нерівності, можна обмежитись множинами вершин ${\displaystyle S}$ з щонайменше двома та щонайбільше ${\displaystyle |V|-2}$ вершинами. На малюнку поруч ребра ${\displaystyle \{i,j\}}$ з вагами ${\displaystyle x_{ij}=1}$ відмічено товстішими лініями а решта ребер має вагу ${\displaystyle x_{ij}=0}$. Введення додаткових умов (2) для множини вершин ${\displaystyle S}$, що складається з трьох лівих вершин, буде гарантувати, щоб ${\displaystyle S}$ сполучалась через щонайменше два ребра маршруту з трьома вершинами справа, аби усунути обидва цикли. Кількість нерівностей усунення циклів відповідно до Данциґа, Фалкерсона та Джонсона дорівнює ${\displaystyle 2^{n}-2(n-1)}$.

В 1960 році Міллєр (англ. Miller), Такер (англ. Tucker) та Землін (англ. Zemlin) винайшли альтернативні умови усунення підшляхів шляхом введення ${\displaystyle n}$ нових змінних, що визначають порядок відвіданих міст, що потребує лише ${\displaystyle n^{2}-n+1}$ додаткових нерівностей. Більше того, через двійковість ${\displaystyle x_{ij}}$ у формулюванні Міллєра, Такера та Земліна задача комівояжера залишається NP-складною.

Так, кожен вектор ${\displaystyle x=(x_{ij})_{i,j\in V}}$ з елементами, що дорівнюють 0 та 1, що задовольняє всім нерівностям визначає коректний маршрут, що є розв'язком переформульованої задачі комівояжера: обчислити

${\displaystyle \min \;\left\{\sum _{i\in V}\sum _{j\in V\setminus \{i\}}c_{ij}x_{ij}\;|\;x{\mbox{ valid (1) (2),}}\;x_{ij}\in \{0,1\}\right\}.\qquad (3)}$

Оскільки змінні ${\displaystyle x_{ij}}$ мають значення лише 0 та 1, сума дорівнює загальній довжині ${\displaystyle c_{ij}}$ ребер ${\displaystyle \{i,j\}}$ що належать маршруту.

Кількість нерівностей типу (2) зростає експоненційно разом зі збільшенням кількості міст, оскільки майже кожна з ${\displaystyle 2^{|V|}}$ підмножин вузлів визначає одну нерівність. Цю проблему можна вирішити застосуванням методу відсічення площиною завдяки якому нерівності додаються лише тоді, коли ці нерівності дійсно необхідні. З геометричної точки зору, лінійні нерівності можна представити як гіперплощину в просторі змінних. Множина векторів, що задовольняють цим нерівностям утворюють в такому просторі політоп (багатовимірний багатогранник), або багатовимірний багатокутник, точна форма визначається вагами ${\displaystyle c_{ij}}$ і є в основному невідомим. Однак, можна показати, що умови (1) та (2) визначають грані (фацети) політопа, тобто, бічні поверхні політопа з найвищою розмірністю. Тому вони належать до найсильніших лінійних нерівностей, що можуть описувати маршрут. Також існує багато різних граней, що визначаються нерівностями, відомими лише у небагатьох випадках. Хоча (1) та (2) разом з обмеженнями повністю моделюють проблему лише для двійкових векторів, ці нерівності можуть використовуватись в методі гілок і меж аби відкинути розв'язки методами лінійної оптимізації з не цілими координатами (див. розділ точні методи нижче).

Алгоритмічна складність

Оскільки комівояжер в кожному з міст постає перед вибором наступного міста з тих, що він ще не відвідав, існує ${\displaystyle (n-1)!}$ маршрутів для асиметричної та ${\displaystyle (n-1)!/2}$ маршрутів для симетричної задачі комівояжера. Таким чином, розмір простору пошуку залежить над-експоненційно від кількості міст.

Різні варіанти задачі комівояжера (метричний, симетричний та асиметричний) є . Відповідно до поширеної але недоведеної гіпотези про нерівність класів складності P та NP не існує детермінованої машини Тюринга, здатної знаходити розв'язки екземплярів задачі за поліноміальний час в залежності від кількості міст.

Також відомо, що за умови ${\displaystyle P\neq NP}$ не існує алгоритму, що для деякого поліному ${\displaystyle p}$ обчислював би такі розв'язки задачі комівояжера, що відрізнялись би від оптимального щонайбільше на коефіцієнт ${\displaystyle 2^{p(n)}}$.^[]

Однак, існують алгоритми пошуку наближених розв'язків для метричної задачі за поліноміальний час, і знайдений маршрут щонайбільше вдвічі (наприклад, 1.5 для алгоритму Христофіда, нім. Christofides) довший за оптимальний. Досі не відомий жоден алгоритм з поліноміальним часом, який би гарантував точність кращу за 1.5 від оптимального. За припущенням ${\displaystyle P\neq NP}$, існує (невідома) константа ${\displaystyle c>0}$, така, що жоден алгоритм з поліноміальним часом не може гарантувати точність ${\displaystyle 1+c}$. Як було показано Арора, для евклідової задачі комівояжера існує схема пошуку приблизних розв'язків задачі (PTAS).

Методи розв'язання

Відомі методи розв'язання поділяють на дві групи, що можна комбінувати. Точні методи знаходять, маючи достатньо часу, гарантовано оптимальний шлях. Евристичні методи знаходять, часто за коротший час, гарні розв'язки, що, в загальному випадку, можуть бути гіршими за оптимальні. Для метричної задачі існують евристики, що знаходять за поліноміальний час розв'язки гірші за оптимальні у 1.5—2 рази.^[]

Точні методи

Докладніше: Метод гілок і меж

Можна знайти точний розв'язок задачі комівояжера, тобто, обчислити довжини всіх можливих маршрутів та обрати маршрут з найменшою довжиною. Однак, навіть для невеликої кількості міст в такий спосіб задача практично нерозв'язна. Для простого варіанта, симетричної задачі з ${\displaystyle n}$ містами, існує ${\displaystyle (n-1)!/2}$ можливих маршрутів, тобто, для 15 міст існує 43 мільярдів маршрутів та для 18 міст вже 177 більйонів. Те, як стрімко зростає тривалість обчислень можна показати в наступному прикладі. Якщо існував би пристрій, що знаходив би розв'язок для 30 міст за годину, то для двох додаткових міст в тисячу раз більше часу; тобто, більш ніж 40 діб.

Задача комівояжера для трьох міст: червона площина ${\displaystyle x_{1}+x_{2}+x_{3}\geqslant 2}$ відкидає всі неприпустимі розв'язки з щонайбільше одним ребром. Всі точки в червоному політопі задовільняють цій нерівності, і єдина припустима точка це (1, 1, 1).

Методи дискретної оптимізації, зокрема гілок і меж дозволяють знаходити оптимальні або приблизні розв'язки для достатньо великих задач.

В геометричній інтерпретації, ці методи розглядають задачу як опуклий політоп, тобто, багатовимірний багатокутник в ${\displaystyle m}$-вимірному одиничному кубі ${\displaystyle [0,1]^{m}}$, де ${\displaystyle m}$ дорівнює кількості ребер в графі. Кожне ребро цього одиничного куба відповідає маршруту, тобто, вектору з елементами 0/1, що задовольняє описаним вище лінійним нерівностям. Гіперплощини, що описуються цими нерівностями відсікають такі ребра одиничного куба, що не відповідають жодному маршруту.

На малюнку поруч показано застосування методу для задачі з трьома вузлами. У відповідність трьом можливим ребрам між вершинами зіставляються бінарні змінні ${\displaystyle x_{1},\,x_{2}}$ та ${\displaystyle x_{3}}$. В цьому випадку існує лише один можливий маршрут, а саме той, що проходить через три вершини. Цей маршрут задовольняє нерівності ${\displaystyle x_{1}+x_{2}+x_{3}\geqslant 2}$, що стверджує, що маршрут повинен проходити через щонайменше дві вершини. Окрім цього маршруту, що відповідає вектору (1,1,1), задовольняють нерівності також всі точки у відміченому червоним регіоні цієї нерівності. Площини, що проходять через червоні лінії відсікають всі кути, що відповідають неіснуючим маршрутам із щонайбільше одним ребром, а саме, нуль-вектор (0, 0, 0), одиничні вектори (1, 0, 0), (0, 1, 0) та (0, 0, 1). Сильніша нерівність ${\displaystyle x_{1}+x_{2}+x_{3}\geqslant 3}$ відсіче від одиничного куба все, окрім єдиної припустимої точки (1, 1, 1). В цьому окремому випадку можна досягти трьома нерівностями типу (1).

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

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

Маючи нижню границю для оптимальних розв'язків можна оцінити те, наскільки відрізняється знайдений маршрут від оптимального. Наприклад, маючи нижню границю на рівні 100, та після знаходження маршруту вартістю 102, оптимальний маршрут може знаходитись в межах від 100 до 102. Так званий інтервал оптимальності, або максимальна відносна відстань між вартістю оптимального маршруту та найдешевшим відомим маршрутом становитиме (102—100)/100 = 2 %, тобто вартість знайденого маршруту 102 щонайбільше на 2 % відрізняється від оптимальної. Коли вартість обчисленого маршруту дорівнює вартості попереднього, вважається, що знайдений розв'язок є оптимальним. Для пошуку маршрутів прийнятної довжини точні методи можуть комбінуватись з евристичними, деякі з них описано нижче.

Евристичні методи

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

Конструктивні евристики

Ітеративні евристики

Ітеративні евристики (також після оптимізаційні евристики) намагаються шляхом деяких змін скоротити вже обчислений маршрут. Прикладом такої евристики є , що систематично видаляють з маршруту групи з ${\displaystyle k}$ ребер і замінюють їх іншими ${\displaystyle k}$ ребрами отримуючи новий маршрут. Оскільки повний перебір можливих варіантів дорівнює кількості можливих маршрутів, на практиці обмежують ${\displaystyle k}$ щонайбільше до 5. При цьому, випробовуються всі варіанти заміни двох та трьох ребер, уникаючи перебору з більшою кількістю ребер через значні витрати часу.

На практиці, ефективність k-opt-евристики сильно залежить від вибору ребер для заміни та параметру ${\displaystyle k}$, для вибору яких існують різні евристичні критерії. Однією з відомих, основаних на принципах k-opt, евристик є розроблена в 1973 році Брайаном Керніганом та С. Ліном евристика Ліна-Кернігана. Реалізація Кельда Гельсгауна серед іншого була використана для пошуку оптимального розв'язку задачі комівояжера з 24 978 містами Швеції в 2004 році. Ця евристика полягає в тому, щоб перебрати можливі заміни з двома ребрами, потім з трьома, і так далі, поки не буде виконано один із багатьох критеріїв зупинки.

Метаевристичні методи

Метаевристичні методи комбінують методи пошуку локальних та глобальних розв'язків у абстрактні стратегії евристичної оптимізації задач. Багато методів цього типу базуються на методах пошуку локальних розв'язків, тобто, вони обчислюють деякий початковий розв'язок (наприклад, застосовуючи метод найближчого сусіда) та покращують його іншими методами, наприклад, методом k-opt-евристики, доти, поки неможливо буде знайти кращий маршрут. Використовуючи різні стратегії, такі, як, наприклад, або симуляції відпалу, можна спробувати уникнути глухих кутів під час пошуку локальних мінімумів. Інші методи, такі як мурашиний алгоритм, генетичні алгоритми або штучні нейронні мережі (перш за все мережа Хопфілда) використовують як шаблон природні процеси. В принципі, цими методами можна знаходити як досить якісні розв'язки так і досить віддалені від оптимального. Якість результатів та тривалість обчислення залежать від визначення та реалізації окремих елементів.

Дуальні евристики

Огляд

Практичні методи обчислення

Варіанти та застосування

Петльові антенні вібратори формату 10×10, синтезовані на основі розв'язку задачі комівояжера

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

Прикладами задач в яких доцільне застосування даного методу є:

1. В ході планування робіт для кур'єра з доставки товарів. Планування маршруту проходження кур'єром пунктів доставки товару.
2. В ході планування робіт для однієї машини. Планування маршруту від пункту початку(автостоянки) до пункту з запасами(складом) та подальше проходження всіх пунктів з потребами, з поверненням машини в кінці зміни на місце початку робіт.

Прикладом застосування розв'язку задачі комівояжера для 100 міст є синтез петльових та непетльових антенних вібраторів формату 10x10 за допомогою мурашиного алгоритму оптимізації.

Декілька комівояжерів

Кластери міст

Варіанти критеріїв оптимальності

Додаткові умови

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

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

Примітки

1. ${\displaystyle {\frac {14!}{2}}=43\,589\,145\,600}$
2. 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
3. William Cook, Daniel Espinoza, Marcos Goycoolea: Computing with Domino-Parity Inequalities for the TSP. [ 20 лютого 2012 у Wayback Machine.] 2005. (Preprint, pdf)
4. Keld Helsgaun: An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic. [ 28 вересня 2009 у Wayback Machine.] In: European Journal of Operational Research. Amsterdam 126.2000, Nr. 1, S.106-130. ISSN 0377-2217
5. Ермолаев С.Ю., Слюсар В.И. Синтез антенн на основе муравьиных алгоритмов оптимизации. // 19-я Международная Крымская конференция «СВЧ-техника и телекоммуникационные технологии» (КрыМиКо’2009). Материалы конференции.- Севастополь, 14-18 сентября. — 2009. — С. 431 - 432.
6. Ermolaev S.Y., Slyusar V.I. Antenna synthesis based on the ant colony optimization algorithm.// 7-я Международная конференция по теории и технике антенн (ICATT’09), Львов, Украина, 6 - 9 октября 2009 г.. — 2009. — С. 298 - 300.

Література

• Ананий В. Левитин (2006). Глава 3. Метод грубой силы: Задача коммивояжера. . М.: «Вильямс». с. 159—160. ISBN . Архів оригіналу за 2 жовтня 2011. Процитовано 18 листопада 2007.
• А. Ахо, Дж. Хопкрофт, Дж. Ульман (1979). Построение и анализ вычислительных алгоритмов. Москва: «Мир».
• Bernhard Korte, Jens Vygen (2006). Combinatorial Optimization (вид. 3-тє). Springer. ISBN .

Див. також

• Узагальнена задача комівояжера
• Дослідження операцій,
• Задача листоноші,
• Задача пакування рюкзака.

Посилання

• The Traveling Salesman Problem Home [ 7 лютого 2006 у Wayback Machine.] — вичерпна інформація про задачу комівояжера(англ.)
• The VRP Web [ 13 жовтня 2008 у Wayback Machine.] — вичерпна інформація про задачу пошуку шляхів для машин(англ.)
• Дослідження ефективності існуючих алгоритмів для розв'язання задачі комівояжера
• Візуалізація різних стратегій розв'язання задачі комівояжера [ 16 березня 2016 у Wayback Machine.]