Обобщённая задача коммивояжёра
Обобщённая задача коммивояжёра — задача комбинаторной оптимизации, являющаяся обобщением хорошо известной задачи коммивояжёра. Исходными данными для задачи является множество вершин, разбиение этого множества на так называемые кластеры, а также матрица стоимостей перехода из одной вершины в другую. Задача заключается в нахождении кратчайшего замкнутого пути, который бы посетил по одной вершине в каждом кластере (существует также модификация, когда путь должен посетить хотя бы по одной вершине в каждом кластере).
В зависимости от свойств матрицы стоимостей, задача может быть симметричной, если матрица симметричная, или асимметричной в противном случае. Одним из наиболее часто рассматриваемых частных случаев симметричной задачи является евклидова или планарная задача, когда каждая вершина имеет свои координаты в пространстве, и стоимость перехода между вершинами соответствует евклидову расстоянию между соответствующими точками в пространстве.
Как и задача коммивояжёра, обобщённая задача коммивояжёра относится к классу NP-трудных задач. Для доказательства достаточно рассмотреть частный случай задачи, когда каждый кластер содержит ровно одну вершину, и задача сводится к простой задаче коммивояжёра, которая является NP-трудной.
Методы решения
правитьТочные методы
правитьИзвестно два эффективных метода точного решения обобщённой задачи коммивояжёра: Brunch-and-Cut[1], а также метод приведения обобщённой задачи к обычной задаче коммивояжёра, способы решения которой хорошо изучены[2].
В 2002 году показано[3], что обобщённая задача коммивояжера может быть сведена к обыкновенной задаче коммивояжера той же размерности заменой матрицы весов[источник не указан 3408 дней].
Эвристические методы
правитьПростые эвристические методы
правитьК простейшим эвристическим методам решения обобщённой задачи коммивояжёра следует отнести жадный алгоритм, на каждом шаге выбирающий ребро наименьшей стоимости из множества рёбер, не нарушающих корректности решения, а также более эффективный метод ближайшего соседа (Nearest Neighbour), начинающий с произвольной вершины и на каждом шаге добавляющий к решению вершину, наиболее близкую к последней добавленной. Существуют также и другие эвристики, являющиеся модификациями известных эвристик для обычной задачи коммивояжёра.
В частности, часто используются следующие виды локального поиска:
- 2-opt, широко применяемый во многих задачах комбинаторной оптимизации, сводится к удалению двух рёбер из тура и вставке двух новых рёбер, не нарушающих корректности решения (в случае 2-opt вставляемые рёбра определены однозначно). Тур считается локальным минимумом, если в нём не существует ни одной пары рёбер, замена которых привела бы к улучшению решения. Таким образом, и размер окрестности, и сложность эвристики составляют , где — это число кластеров.
- 3-opt подобен 2-opt, однако на каждом удаляется не два, а три ребра. В случае 3-opt, для восстановления корректности тура существует восемь нетривиальных способов вставки новых рёбер. Один из этих способов сохраняет направление каждого из фрагментов тура, что является важным свойством для асимметричных задач. Размер окрестности, и сложность эвристики составляют .
- Существуют естественные модификации 2-opt и 3-opt алгоритмов, дополнительно включающие поиск оптимальных вершин внутри изменяемых кластеров.
- «Insertion» является частным случаем 3-opt. На каждой итерации алгоритм удаляет вершину и пытается найти более выгодную для неё позицию. Сложность алгоритма составляет . Широко применяется модификация, рассматривающая вставку не только удалённой вершины, но и любой другой вершины соответствующего кластера.
- Кластерная оптимизация — локальный поиск, специфичный для обобщённой задачи коммивояжёра. Суть алгоритма заключается в нахождении кратчайшего пути через заданную последовательность кластеров. Иными словами, окрестность алгоритма включает в себя все туры, отличающиеся от исходного не более чем выбором вершин внутри каждого из кластеров. Размер исследуемой окрестности составляет:
где — это кластер под номером . Применяя поиск кратчайшего пути в специально построенном графе, алгоритм находит локальный минимум за , где . Таким образом, Cluster Optimization относится к классу локальных поисков с очень большой окрестностью, то есть исследует экспоненциальную окрестность за полиномиальное время.
Метаэвристики
правитьХорошо исследована область генетических алгоритмов, показавших свою эффективность для данной задачи. Первая работа в этой области принадлежит Снайдеру и Даскину[4], в дальнейшем важные результаты получены Зильбергольцем и Голденом[5], Гютеном и Карапетяном[6].
Примечания
править- ↑ 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.
- ↑ 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.
- ↑ 6. Arash Behzad, Mohammad Modarres (2002). A New Efficient Transformation of Generalized Traveling Salesman Problem into Traveling Salesman Problem
- ↑ 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.
- ↑ 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.
- ↑ 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. (недоступная ссылка)
Для улучшения этой статьи желательно:
|