Узагальнена задача комівояжера

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

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

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

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

Точні методи

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

У 2002 році показано, що узагальнена задача комівояжера може бути зведена до звичайної задачі комівояжера тієї ж розмірності заміною матриці ваг^{[джерело?]}.

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

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

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

Зокрема, часто використовуються такі види локального пошуку:

• 2-opt, широко застосовуваний у багатьох задачах комбінаторної оптимізації, зводиться до видалення двох ребер з туру і вставлення двох нових ребер, що не порушують коректності розв'язку (у разі 2-opt вставляються ребра визначені однозначно). Тур вважається локальним мінімумом, якщо в ньому не існує жодної пари ребер, заміна яких привела б до поліпшення рішення. Таким чином, і розмір околу, і складність евристики складають $O(m^{2})$, де $m$ — це число кластерів.
• 3-opt подібний до 2-opt, проте на кожному турі видаляється не два, а три ребра. У разі 3-opt, для відновлення коректності туру існує вісім нетривіальних способів вставлення нових ребер. Один із цих способів зберігає напрямок кожного з фрагментів туру, що є важливою властивістю для асиметричних задач. Розмір околу, і складність евристики складають $O(m^{3})$.
• Існують природні модифікації 2-opt і 3-opt алгоритмів, які додатково включають пошук оптимальних вершин всередині змінюваних кластерів.
• Insertion є окремим випадком 3-opt. На кожній ітерації алгоритм видаляє вершину і намагається знайти більш вигідну для неї позицію. Складність алгоритму становить $O(m^{2})$. Широко застосовується модифікація, яка розглядає вставлення не тільки видаленої вершини, але й будь-якої іншої вершини відповідного кластера.
• Кластерна оптимізація — локальний пошук, специфічний для узагальненої задачі комівояжера. Суть алгоритму полягає в знаходженні найкоротшого шляху через задану послідовність кластерів. Іншими словами, окіл алгоритму включає всі тури, що відрізняються від вихідного не більше ніж вибором вершин всередині кожного з кластерів. Розмір досліджуваного околу становить:

$\prod _{i=1}^{m}|C_{i}|\,,$ де $C_{i}$ — це кластер під номером $i$. Застосовуючи пошук найкоротшого шляху в спеціально побудованому графі, алгоритм знаходить локальний мінімум за $O(ms^{3})$, де $s=\max _{i}|C_{i}|$. Таким чином, кластерна оптимізація відноситься до класу локальних пошуків з дуже великим околом, тобто досліджує експонентний окіл за поліноміальний час.

Метаевристики

Добре досліджена галузь генетичних алгоритмів, які показали свою ефективність для даної задачі. Перша робота в цій області належить Снайдеру і Даскіну, надалі важливі результати отримали Зільбергольц і Голден, Гютен і Карапетян.