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

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

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

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

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

Точні методи

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

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

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

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

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

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

• ^[en], широко застосовуваний у багатьох задачах комбінаторної оптимізації, зводиться до видалення двох ребер з туру і вставлення двох нових ребер, що не порушують коректності розв'язку (у разі 2-opt вставляються ребра визначені однозначно). Тур вважається локальним мінімумом, якщо в ньому не існує жодної пари ребер, заміна яких привела б до поліпшення рішення. Таким чином, і розмір околу, і складність евристики складають ${\displaystyle O(m^{2})}$, де ${\displaystyle m}$ — це число кластерів.
• ^[en] подібний до 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}|}$. Таким чином, кластерна оптимізація відноситься до класу локальних пошуків з дуже великим околом, тобто досліджує експонентний окіл за поліноміальний час.

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

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

Примітки

1. M. Fischetti, J.J. Salazar-Gonzalez, and P. Toth. A Branch-and-Cut algorithm for the symmetric generalized traveling salesman problem. Operations Research 45 (3) (1997), 378—394.
2. D. Ben-Arieh, G. Gutin, M. Penn, A. Yeo, and A. Zverovitch. Transformations of generalized ATSP into ATSP, Operations Research Letters 31 (2003), 357—365.
3. 6. Arash Behzad, Mohammad Modarres (2002). A New Efficient Transformation of Generalized Traveling Salesman Problem into Traveling Salesman Problem
4. L.V. Snyder and M.S. Daskin. A random-key genetic algorithm for the generalized traveling salesman problem. European Journal of Operational Research 174 (2006), 38−53.
5. J. Silberholz and B. Golden. The Generalized Traveling Salesman Problem: a new Genetic Algorithm approach. Extending the Horizons: Advances in Computing, Optimization, and Decision Technologies, 2007, 165−181.
6. G. Gutin and D. Karapetyan. Gregory Gutin and Daniel Karapetyan. A Memetic Algorithm for the Generalized Traveling Salesman Problem. Natural Computing 9(1), pages 47-60, Springer 2010.^{[недоступне посилання]}