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

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

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

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

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

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

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

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