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

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

Для можливості застосування математичного апарату для розв'язання проблеми, її слід представити у вигляді математичної моделі. Проблему комівояжера можна представити у вигляді моделі на графі, тобто, використовуючи вершини та ребра між ними. Таким чином, вершини графу (на мал.: від 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}$ містами, існує ${\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), або нерівностями доміно-парності[3]) та спробувати поділити одиничний куб на менші політопи методом гілок і меж. Повніше описання цих методів можна знайти в статті про дискретну оптимізацію.

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

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

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

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

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

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

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

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