Введение 6
1 Постановки исследуемых задач 17
1.1 Задачи комбинаторной оптимизации 17
1.2 Предварительные сведения об исследовании задачи коммивояжера 19
1.3 Задача о цикловом покрытии графа фиксированного размера 25
1.4 Обобщенная задача коммивояжера 28
1.5 Пирамидальные маршруты 32
2 Задача о цикловом покрытии графа 35
2.1 Вычислительная сложность задачи Min-k-SCCP 35
2.2 Принадлежность задачи Metric Min-k-SCCP классу APX 37
2.2.1 Алгоритм построения минимального остовного к-леса 37
2.2.2 2-приближенный алгоритм для задачи Metric Min-k-SCCP 39
2.3 Полиномиальная приближенная схема для задачи Euclidean Min-k-SCCP в Rd 42
2.3.1 Декомпозиция евклидовой задачи о цикловом покрытии графа 43
2.3.2 Округленная задача Euclidean Min-k-SCCP 48
2.3.3 Рекурсивное разбиение объемлющего гиперкуба S 50
2.3.4 Теорема существования 53
2.3.5 Динамическое программирование 55
2.3.6 Дерандомизация 57
3 Обобщенная задача коммивояжера 59
3.1 Квази- и псевдопирамидальные маршруты 59
3.2 Полиномиально разрешимый подкласс 66
3.3 Приближенные схемы для случая медленно растущих значений параметра к . 71
3.3.1 Применение метода динамического программирования при построении
приближенной схемы 72
3.3.2 Обобщение схемы Ароры для задачи коммивояжера на плоскости на
случай EGTSP-k-GC 74
3.4 Приближенная схема для случая быстро растущих значений параметра к ... 80
Заключение 82
Публикации автора по теме диссертации 84
Благодарности 88
Литература 89
Предмет исследования диссертационной работы1 составляют труднорешаемые оптимизационные задачи, являющиеся обобщениями классической задачи
коммивояжера (Traveling Salesman Problem, TSP) [83, 63]. В работе исследуются: задача о цикловом покрытии фиксированной мощности k минимального
веса (Minimum-weight k-Size Cycle Cover Problem, Min-k-SCCP), обобщенная
задача коммивояжера (Generalized Traveling Salesman Problem, GTSP) и её геометрическая постановка евклидова обобщенная задача коммивояжера на сетке
(Euclidean Generalized Traveling Salesman Problem in k Grid Clusters, EGTSP-kGC).
Задача о цикловом покрытии графа фиксированного размера k минимального веса — это задача комбинаторной оптимизации, заключающаяся
в поиске оптимального покрытия полного взвешенного графа k вершиннонепересекающимися циклами. На содержательном уровне каждый цикл в покрытии может трактоваться как маршрут для некоторого транспортного средства, посещающего соответствующее множество клиентов. С этой точки зрения
задача о цикловом покрытии близка к известной задаче маршрутизации транспорта (Vehicle Routing Problem, VRP) [113]. С другой стороны, при фиксированной единичной мощности циклового покрытия задача совпадает с классической
задачей коммивояжера. Кроме того, задача о цикловом покрытии мощности k
1Работа поддержана грантами РНФ 14-11-00109, РФФИ 13-07-00181, 16-07-00266, стипендией Президента
Российской Федерации
6занимает промежуточное положение в сложностной иерархии между эффективно разрешимой задачей о назначениях и труднорешаемой задачей коммивояжера, что индуцирует дополнительный теоретический интерес к исследованию
сложности и аппроксимируемости Min-k-SCCP.
Цикловые покрытия играют важную роль при разработке приближенных
алгоритмов для задачи коммивояжера [27, 26, 32, 34, 36], задачи о кратчайшей
суперстроке [31, 111] и задачи маршрутизации транспорта [64]. В случае задачи
коммивояжера при построении указанных алгоритмов в качестве начального
приближения выступает цикловое покрытие, элементы которого соединяются в
гамильтонов цикл с помощью той или иной техники объединения фрагментов
маршрута.
Помимо выполнения вспогательной роли при построении приближенных алгоритмов, поиск оптимальных цикловых покрытий является интересной независимой задачей. Паросочетания и факторизация графов — это важные разделы
теории графов, наряду с этим поиск циклового покрытия эквивалентен стесненной дополнительным ограничением на количество компонент связности задаче
построения 2-фактора, то есть остовного подграфа, каждая вершина которого
инцидентна в точности двум ребрам.
Все перечисленные выше аргументы обуславливают актуальность алгоритмического анализа Min-k-SCCP и уточнения статуса вычислительной сложности данной задачи при k > 1, то есть в случае, когда Min-k-SCCP отлична от
классической задачи коммивояжера.
Обобщенная задача коммивояжера (Generalized Traveling Salesman Problem,
GTSP), известная в отечественной литературе под названием «задача обхода
мегаполисов», задается полным взвешенным графом, множество вершин которого разбито на k непересекающихся кластеров, и заключается в поиске цикла
минимального веса посещающего каждый кластер.
7Что касается алгоритмов с гарантированными оценками точности, даже для
метрической постановки GTSP известно не так много результатов. В [109] представлен 3ρ/2-приближенный алгоритм, где ρ — это число вершин в наибольшем по мощности кластере (ρ = maxi=1,...,k(|Vi|)). К сожалению, в худшем случае данная оценка точности оказывается очень слабой, и алгоритм неприменим для практических целей. Н. Гарг и Дж. Коньевод построили рандомизированный приближенный алгоритм для обобщенной задачи о штейнеровском
дереве, побочным результатом этой работы стал O(log2(n) log(log(n)) log k)-
приближенный алгоритм для GTSP [58]. Таким образом, исследования в области сложности (в том числе параметрической) и аппроксимируемости задачи
GTSP представляются актуальными.
Кроме того, представляется актуальной задача исследования вычислительной сложности и аппроксимируемости геометрических постановок GTSP. Данные постановки наряду с теоретическим вызывают и большой практический
интерес, обладая рядом приложений, например, в задачах оптимальной доставки почтовых отправлений и задачах о демонтаже отработанных энергоблоков
АЭС.
При фиксированном числе кластеров общая постановка GTSP обладает точным полиномиальным алгоритмом с трудоемкостью O((k − 1)!n3). Задачи построения точного алгоритма меньшей трудоемкости либо обоснование подклассов, в которых GTSP разрешима за полиномиальное по n и k время, также
представляются актуальными.
В диссертационной работе исследованы несколько задач маршрутизации, являющихся обобщениями классической задачи коммивояжера. Основные результаты диссертации заключаются в следующем:
1. Для задачи о цикловом покрытии фиксированного размера k (Min-kSCCP):
(a) обоснована NP-трудность в сильном смысле даже в частной евклидовой
постановке;
(б) для метрической постановки задачи при условии, что значение параметра
k является частью входа, построен 2-приближенный алгоритм c асимптотически
достижимой оценкой точности;
(в) для евклидовой постановки задачи в пространстве произвольной фиксированной размерности d предложена эффективная полиномиальная приближенная схема с трудоемкостью O(nO(d)(log n)(O(√εd))d−1).
Таким образом, исследование сложностного статуса и аппроксимируемости в
классе детерминированных алгоритмов задачи Min-k-SCCP можно считать завершенным. В качестве интересного открытого вопроса отметим вопрос неулучшаемости оценки точности 2 для алгоритма из п. 1(б).
2. Для обобщенной задачи коммивояжера (GTSP):
(а) введены понятия l-квазипирамидального и l-псевдопирамидального
маршрутов;
(б) построен алгоритм поиска оптимального l-квазипирамидального марш-
82рута с трудоемкостью O(4ln3), тем самым показано, что обобщенная задача
коммивояжера с неотрицательной симметричной матрицей весов принадлежит
классу FPT;
(в) предложен FPT-алгоритм (относительно параметров k и l) построения
оптимального l-псевдопирамидального маршрута с трудоемкостью O(2lkl+4n3).
3. Для обобщенной задачи коммивояжера на сетке (EGTSP-k-GC):
(а) показано, что при дополнительном ограничении на высоту сетки H ≤ 2
задача разрешима за время O(n3);
(б) для евклидовой постановки задачи построены три приближенные схемы для случая быстро k = n − O(log n) и медленно k = O(log n) растущих
значений параметра k. Для случая медленно растущего значения k две предложенные схемы являются линейными приближенными схемами с трудоемкостью
O(k2(O(1/ε))2k)+O(n) и 2O(k)k4(log k)O(1/ε)+O(n) соответственно и представляют практический интерес при фиксированном значении параметра, несмотря на
полиномиальную разрешимость задачи в этом случае, так как известный точный алгоритм имеет кубическую трудоемкость. При фиксированном значении
параметра k третья схема является эффективной полиномиальной приближенной схемой с трудоемкостью nk(log k)O(1/ε) и сохраняет полиномиальность при
k = n − O(log n).
Статусы вычислительной сложности обобщенной задачи коммивояжера на
сетке при промежуточных значениях параметра k (между O(log n) и n −
O(log n)) и при высоте сетки H > 2 являются важными открытыми вопросами.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
