Эффективный метод решения задачи обхода мегаполисов при ограничениях предшествования специального типа А.Г. Ченцов Д.М. Хачай agchentsov@mail.com daniil.khachay@gmail.com ИММ УрО РАН (Екатеринбург) УрФУ (Екатеринбург) Аннотация Рассматривается задача обхода мегаполисов с фиксированным чис- лом городов и специальным образом заданными отношениями предшествования, известная также как асимметрическая обобщен- ная задача коммивояжера (AGTSP). Для поиска оптимального ре- шения задачи приводится схема динамического программирования, развивающая схему Хелда–Карпа, разработанную для классиче- ской постановки задачи коммивояжера; обосновываются условия, при которых трудоемкость предложенного алгоритма полиноми- ально, в частности, линейно зависит от числа мегаполисов. 1 Введение Обобщенная задача коммивояжера (GTSP) является расширением классической задачи коммивояжера (TSP), в которой множество городов разделено на непересекающиеся между собой мегаполисы (класте- ры), причем каждый кластер должен быть посещен искомым маршрутом в точности один раз. Задача обладает широким спектром приложений, например в задачах маршрутизации [9], в задаче демонтажа отработанного реактора на АЭС [5], а также при моделировании высокоточной резки металла [18]. Существует множество подходов для нахождения оптимальных и субоптимальных решений этой зада- чи. На первый взгляд, наиболее естественным представляется подход, состоящий в сведении обобщенной задачи коммивояжера к подходящей постановке обычной TSP. В самом деле, известна [17] полиномиаль- ная сводимость задачи GTSP к подходящей асимметрической задаче TSP, сохраняющая ее стоимость, так что для решения GTSP могут применяться многочисленные алгоритмы и эвристики, разработанные для классической TSP [12, 14]. К сожалению, результирующая задача TSP теряет многие полезные свойства исходной постановки, и для ее аппроксимации не удается применить такие известные эффективные ал- горитмы, как алгоритм Кристофидеса [6] для метрической TSP, полиномиальную приближенную схему (PTAS) Ароры для Евклидовой TSP [1], ее обобщение на случай задачи о нескольких коммивояжерах [15, 16]. Еще один подход связан с адаптированием некоторых эволюционных методов, как, например, генети- ческих алгоритмов [4, 10], эвристик муравьиной колонии [13] и т.д. Результаты численных экспериментов Copyright c by the paper’s authors. Copying permitted for private and academic purposes. In: A.A. Makhnev, S.F. Pravdin (eds.): Proceedings of the 47th International Youth School-conference “Modern Problems in Mathematics and its Applications”, Yekaterinburg, Russia, 02-Feb-2016, published at http://ceur-ws.org 191 показывают, что в некоторых случаях данный подход действительно позволяет эффективно получить ре- шения, близкие к оптимальным. Однако основным его недостатком является отсутствие теоретических оценок точности аппроксимации и вычислительной сложности для всех перечисленных выше алгоритмов. В рамках третьего подхода изучаются нетривиальные полиномиально разрешимые подклассы иссле- дуемой задачи. В то время как для классической постановки задачи коммивояжера известно большое количество таких подклассов (см., например, [8]), для задачи GTSP подобные результаты нам не извест- ны. Данная работа посвящена описанию полиномиально разрешимого подкласса задачи GTSP, отягощенно- го дополнительными ограничениями предшествования специального вида. Полученные результаты явля- ются естественным обобщением результатов, представленных в [2] для классической TSP. Рассмотрим наиболее общий случай задачи GTSP. В данной постановке для любой пары смежных узлов u и v, стоимости прямых и обратных перемещений не одинаковы. Чтобы подчеркнуть данную асимметрию, будем называть такую постановку Асимметрической Обобщенной Задачей Коммивояжера (AGTSP). Ограничения предшествования естественны для AGTSP и восходят к конкретным прикладным зада- чам. В нашем случае эти ограничения определяют порядок посещения мегаполисов и могут быть легко интерпретированы. Рис. 1: Задача фигурной резки металла Например, в задаче высокоточной резки металла из исходного стандартного листа требуется вырезать детали различной формы. В соответствующей постановке AGTSP, каждой детали сопоставляется конечный мегаполис, состоящий из точек врезки и выключения инструмента, размещенных по ее контуру (рис. 1). Как видно, на исходном листе одни детали могут оказаться вложенными в другие. Технология резки, согласно которой вложенные детали должны быть вырезаны раньше объемлющих, задает естественные ограничения предшествования (рис. 2). Наша работа структурирована следующим образом. В разделе 2 мы остановимся на математической постановке асимметрической обобщенной задачи коммивояжера. Далее, в разделе 3 мы напомним извест- ную схему динамического программирования Хелда–Карпа (ДП), используемую для нахождения точного решения нашей задачи. В рассматриваемой нами постановке стоимости перемещения и посещения городов предполагаются зависящими от частичных маршрутов, но процедура ДП успешно справляется с этими за- труднениями. В разделе 4 мы приведем эквивалентное описание этой процедуры в терминах нахождения кратчайших s-t путей в соответствующем взвешенном ациклическом ориентированном графе (известном как орграф состояний), поскольку обоснование наших результатов, представленных в разделе 5, удобно проводить именно в этих терминах. Наконец, в разделе 6 мы остановимся на одном содержательном при- мере, иллюстрирующем проведенные рассуждения. 192 Рис. 2: Порядок резки задает ограничения предшествования 2 Постановка задачи Рассмотрим постановку расширенной асимметрической обобщенной задачи коммивояжера (AGTSP) (рис. 3). Пусть заданы конечные дизъюнктные множества M1 , . . . , Mn , называемые мегаполисами, и стар- товая точка x0 , не принадлежащая ни одному из них. Без ограничения общности, полагаем множества Mj равномощными и определяемыми равенствами Mj = {gj1 , . . . , gjp }. Вместе с транспортными издержками c(glσ , gjτ ) для произвольных индексов j 6= l ∈ Nn = {1, . . . , n} и σ, τ ∈ Np , заданы стоимости ĉ(x0 , gjτ ) и č(gjτ , x0 ) перемещения из точки x0 в каждую из точек gjτ (и обратно). Далее, фиксируется стоимость посещения (внутренних работ) c0 (gjτ ) каждого из мегаполисов. Задача состоит в нахождении маршрута наименьшей стоимости, начинающегося и заканчивающегося в точке x0 и посеща- ющего все мегаполисы (в точности по одному разу). С математической точки зрения требуется найти перестановку π : N n → Nn , задающую порядок посещения мегаполисов, называемую далее маршрутом, и конечную последователь- ность gπ(1)τ (1) , . . . , gπ(n)τ (n) , именуемую трассой, так, чтобы n−1 X c0 (gπ(i)τ (i) ) + c(gπ(i)τ (i) , gπ(i+1)τ (i+1) ) + č(gπ(n)τ (n) , x0 ) → min .  ĉ(x0 , gπ(1)τ (1) ) + (1) i=1 Основные отличия между стандартной постановкой AGTSP и рассматриваемой нами в работе состоят в следующем: 1) для любых вершин glσ and gjτ стоимости перехода c(glσ , gjτ ) и стоимость посещения мегаполиса c0 (gjτ ) зависят от выбранной трассы, соединяющей x0 и вершину glσ ; 2) на множестве мегаполисов определен один из двух типов ограничений предшествования (по аналогии с приведенными в работе [2] для классической TSP): Тип I. Для натурального числа k 6 n, любая допустимая перестановка π удовлетворяет ограничению ∀i, j ∈ Nn (j > i + k) ⇒ (π(i) < π(j)). (2) 193 Рис. 3: Пример AGTSP для n = 6. Тип II. Для любых натуральных значений 1 6 k(1), . . . , k(n) 6 n и произвольной допустимой перестанов- ки π справедливо соотношение ∀i, j ∈ Nn (j > i + k(i)) ⇒ (π(i) < π(j)). (3) 3 Схема динамического программирования Традиционный подход к решению задачи (1) восходит к классическим работам Беллмана [3] и Хелда и Карпа [11] и опирается на метод динамического программирования. Пусть оптимальная трасса, выйдя из точки x0 , посетив за первые i − 1 шагов мегаполисы с номерами из подмножества J ⊂ Nn , в i-й позиции посещает мегаполис Mj в точке gjτ (i) ∈ Mj . Обозначим стоимость этой части трассы через C(J, i, j, gjτ (i) ). Справедливы следующие рекуррентные соотношения C(∅, 1, j, gjτ (1) ) = ĉ(x0 , gjτ (1) ), (4) C(J \ {l}, i − 1, l, glτ (i−1) ) + c(glτ (i−1) , gjτ (i) ) + c0 (gjτ (i) ) ,  C(J, i, j, gjτ (i) ) = min min (5) l∈J glτ (i−1) ∈Ml причем оптимальное значение задачи (1) может быть вычислено по формуле C ∗ = min (C(Nn \ {j}, n, j, gjτ (n) ) + č(gjτ (n) , x0 )). (6) j∈Nn Оптимальная трасса восстанавливается с помощью процедуры обратного поиска. 4 Граф состояний Рекуррентная процедура (4)-(6) допускает эквивалентную формулировку в терминах теории графов. В самом деле, пользуясь известным подходом (см., например, [7]), сопоставим исходной задаче задачу поиска кратчайшего s-t пути в подходящем реберно-взвешенном (n + 2)-дольном ориентированном графе G∗ [p] = = (V ∗ [p], A∗ [p], w∗ [p]). Через Vi∗ [p] обозначим подмножество вершин, составляющих i-ю долю, задаваемое равенствами V0∗ [p] = {s}, Vn+1 ∗ [p] = {t}, Vi∗ [p] = {(J, i, j, τ ) : j ∈ Nn \ J, gjτ ∈ Mj , J ⊂ Nn , |J| = i − 1} (i ∈ Nn ). (7) При этом вершины s и t соответствуют стартовой точке x0 , а произвольная вершина (J, i, j, τ ) (обычно именуемая состоянием) соответствует части трассы длины i, посещающей мегаполисы с номерами из множества J ∪ {j}, последним среди которых — мегаполис Mj (в точке gjτ ). Смежными в графе G∗ [p] являются лишь вершины соседних долей Vi∗ [p] и Vi+1 ∗ [p]. Дуги G∗ [p] соединяют вершину s с произвольной 194 вершиной доли V1∗ [p], произвольную вершину доли Vn∗ [p] с вершиной t, а также произвольные вершины (J, i, l, σ) и (J 0 , i + 1, j, τ ), удовлетворяющие условиям |J| = i − 1, J 0 = J ∪ {l}, j 6∈ J 0 , σ, τ ∈ Np . (8) ∗ Определим множество дуг, соединяющих вершины, принадлежащие Vi∗ [p] и Vi+1 [p], как A∗i,i+1 [p]. Веса дуг определяются соотношениями: w∗ [p](s, (∅, 1, j, τ )) = ĉ(x0 , gjτ ), w∗ [p]((Nn \ {j}, n, j, τ ), t) = č(gjτ , x0 ), w∗ [p]((J, i, l, σ), (J 0 , i + 1, j, τ )) = c(glσ , gjτ ) + c0 (gjτ ). Нетрудно убедиться в том, что множество допустимых трасс в задаче (1) взаимно однозначно отобра- жается на множество s-t путей в графе G∗ [p], следовательно, кратчайшей трассе (оптимальному решению задачи (1)) соответствует s-t путь наименьшего веса. Более того, схема (4)-(6) эквивалентна модификации известного алгоритма Форда–Беллмана для поиска кратчайшего пути в бесконтурной сети (см., например, [7]). К сожалению, для общего случая задачи AGTSP число дуг в орграфе G∗ [p] растет экспоненциально с ростом числа мегаполисов n, что влечет экспоненциальную же оценку трудоемкости метода динамического программирования для задачи (1). В самом деле, для произвольного n > 2 |V ∗ [p]| > |V2∗ [p] ∪ . . . ∪ Vn∗ [p]| > pn2n−2 . При этом входящая степень произвольной вершины (J, m, j, τ ) ∈ Vm∗ [p] при m > 2 удовлетворяет соотно- шению deg− (J, m, j, τ ) = (m − 1)p > p. Следовательно, |A∗ [p]| = Ω(np2 2n ). Тем не менее, введение в условие задачи дополнительных ограничений, например, ограничений пред- шествования на множестве мегаполисов, может существенно снизить суммарную трудоемкость процедуры поиска оптимального решения (см., например, [19]). Ниже мы воспользуемся подходом, предложенным Ба- ласом [2] для классической TSP, в рамках которого схема (4)-(6) обладает линейной по n трудоемкостью. 5 Оценки трудоемкости Начнем с описания частного случая графа G∗ [p], соответствующего ограничениям предшествования типа I и типа II, описанным выше. Покажем, что структура графа G∗ [p] определяется структурой графа G∗ [1]. Лемма 1. Для любого p > 1: Vi∗ [p] = Vi∗ [1] × Np (i ∈ Nn ) (9) A∗0,1 [p] = A∗0,1 [1] × Np , A∗n,n+1 [p] = A∗n,n+1 [1] × Np (10) A∗i,i+1 [p] = A∗i,i+1 [1] × N2p (i ∈ Nn−1 ) (11) В самом деле, задавшись произвольным p > 1, рассмотрим отображение Γ : V ∗ [p] → V ∗ [1], задаваемое соотношениями Γ(s) = s, Γ(t) = t, Γ((J, i, j, gjτ )) = (J, i, j). Поскольку смежность вершин в графе G∗ [p] при произвольном p определяется соотношением (8), отобра- жение Γ является гомоморфизмом. Более того, вершины (J, i, l, glσ ) и (J ∪ {l}, i + 1, j, gjτ ) смежны тогда и только тогда, когда смежны вершины (J, i, l) и (J ∪ {l}, i + 1, j) в графе G∗ [1]. По построению, Γ−1 ((J, i, j)) = {(J, i, j, gj1 ), . . . , (J, i, j, gjp )}, что влечет справедливость соотношений (9)-(11). Лемма доказана. Следствие 1. Для любого p > 1 |A∗ [p]| 6 |A∗ [1]| · p2 . В работе [2] была описана структура графа G∗ [1], определяющего динамическую процедуру для клас- сической TSP с дополнительными ограничениями предшествования (2) и (3). Представим эти результаты в Теореме 1. 195 Теорема 1. 1. В случае ограничений предшествования (2) |A∗ [1]| = O(n · k 2 2k−2 ). 2. В случае ограничений (3) ! n X ∗ |A∗ [1]| = O k ∗ (i)(k ∗ (i) + 1)2k (i)−2 i=1 для k ∗ (i) = max{k(j) : i − k(j) + 1 6 j 6 i}. Наши основные результаты для оценки вычислительной сложности следуют из Леммы 1 и Теоремы 1. Теорема 2. Пусть для рассматриваемой задачи AGTSP имеют место ограничения предшествования (2). Тогда схема динамического программирования (4)-(6) позволяет получить оптимальное решение (для данной задачи) за время O(n · p2 k 2 2k−2 ). (12) Теорема 3. Если любая любая постановка задачи AGTSP удовлетворяет следующим ограничениям пред- шествования (3), тогда схема (4)-(6) будет выполнена за время n ! k∗ (i)−2 X 2 ∗ ∗ O p k (i)(k (i) + 1)2 . (13) i=1 В теоремах 2 и 3 утверждается, что в случае дополнительных ограничений предшествования (2) или (3), решение задачи AGTSP может быть найдено эффективно. В самом деле, легко видеть, что верхняя оценка (12) (в случае оценки (13) аналогично) является линейной по n для любых фиксированных k и p и остается полиномиальной для p = O(poly(n)) и k = O(log(n)). Таким образом, процедура динамического программирования в обоих случаях позволяет найти оптимальное решение за время, линейно зависящее от числа мегаполисов n. 6 Содержательный пример Обсудим применимость ограничений предшествования. На первый взгляд, ограничения (2)-(3) могут показаться излишне строгими. Тем не менее, даже ограничение (2), при k от 1 до n, охватывает все воз- можные случаи задачи AGTSP. Рассмотрим следующий содержательный пример. Нужно составить план эвакуации из многоэтажного здания при пожаре. Здание состоит из m этажей. На t-м этаже находится qt комнат. Каждая комната (Mi ) имеет несколько дверей (рис. 4). Команда спасателей может начать выполнение своего задания, вы- садившись на любом этаже (стоимостью доставки на этаж можно пренебречь). После выполнения своего задания команда может быть эвакуирована также с любого этажа. Однако основным ограничением яв- ляется возможность перехода между этажами только с помощью лифтов: стоимость такого перемещения намного выше, чем стоимость перемещения по этажу. Сформулировав данную задачу математически, мы получим следующие ограничения предшествования. Для комнаты Mi определим q1 + 1 − i, при 1 6 i 6 q1 ,      q + q + 1 − i, при q + 1 6 i 6 q + q , 1 2 1 1 2 k(i) =    . . .  Pm−1 Pm−2 Pm−1 l=1 ql + 1 − i, при l=1 ql + 1 6 i 6 l=1 ql . Эти ограничения означают, что здание должно быть эвакуировано или сверху вниз, или наоборот. Сле- довательно, ограничения предшествования (3) являются вполне естественными для данного класса задач. 7 Заключение В статье предложена процедура динамического программирования для нахождения оптимального ре- шения задачи AGTSP. Для двух типов ограничений предшествования показано, что процедура является эффективной. В этом случае трудоемкость такой процедуры линейна по n для любых фиксированных k и p и полиномиальна при k = O(log n) и p = O(poly(n)). 196 Рис. 4: Иллюстрация эвакуационного плана при пожаре для m = 3, q1 = 4, q2 = 2, q3 = 3 Благодарности Исследования поддержаны Российским научным фондом, грант № 14-11-00109. Список литературы [1] S. Arora. Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems. Journal of the ACM, 45, 1998. [2] E. Balas. New classes of efficiently solvable generalized traveling salesman problems. Annals of Operations Research, 86(0):529–558, 1999. [3] Richard Bellman. Dynamic programming treatment of the travelling salesman problem. J. ACM, 9(1):61–63, 1962. [4] Boris Bontoux, Christian Artigues, and Dominique Feillet. A memetic algorithm with a large neighborhood crossover operator for the generalized traveling salesman problem. Computers & Operations Research, 37(11):1844 – 1852, 2010. [5] A.A. Chentsov and A.G. Chentsov. Dynamic programming method in the generalized traveling salesman problem: The influence of inexact calculations. Mathematical and Computer Modelling, 33(8–9):801 – 819, 2001. [6] N Christofides. Worst-case analysis of a new heuristic for the traveling salesman problem. In Symposium on New Directions and Recent Results in Algorithms and Complexity, page 441, 1975. [7] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. MIT, 3ed. edition, 2009. [8] Vladimir G. Deineko, Bettina Klinz, Alexander Tiskin, and Gerhard J. Woeginger. Four-point conditions for the tsp: The complete complexity classification. Discrete Optimization, 14:147–159, 2014. [9] Emanuele Garone, Jean-Francois Determe, and Roberto Naldi. Generalized traveling salesman problem for carrier-vehicle systems. Journal of Guidance Control and Dynamics, 37:766–774, 2014. [10] Gregory Gutin and Daniel Karapetyan. A memetic algorithm for the generalized traveling salesman problem. 9(1):47–60, 2010. 197 [11] Michael Held and Richard M. Karp. A dynamic programming approach to sequencing problems. In Proceedings of the 1961 16th ACM National Meeting, ACM ’61, pages 71.201–71.204, New York, NY, USA, 1961. ACM. [12] Keld Helsgaun. Solving the equality generalized traveling salesman problem using the lin–kernighan– helsgaun algorithm. Mathematical Programming Computation, pages 1–19, 2015. [13] Kan Jun-man and Zhang Yi. Application of an improved ant colony optimization on generalized traveling salesman problem. Energy Procedia, 17, Part A(0):319 – 325, 2012. [14] D. Karapetyan and G. Gutin. Lin–kernighan heuristic adaptations for the generalized traveling salesman problem. European Journal of Operational Research, 208(3):221 – 232, 2011. [15] M.Yu. Khachai and E.D. Neznakhina. A polynomial-time approximation scheme for the euclidean problem on a cycle cover of a graph. Proceedings of the Steklov Institute of Mathematics, 289(1):111–125, 2015. [16] M. Khachay and K. Neznakhina. Approximability of the minimum-weight k-size cycle cover problem. Journal of Global Optimization, 2015. [17] Gilbert Laporte, Hélène Mercure, and Yves Nobert. Generalized travelling salesman problem through n sets of nodes: the asymmetrical case. Discrete Applied Mathematics, 18(2):185 – 197, 1987. [18] A.A. Petunin, A.G. Chentsov, and P.A. Chentsov. About a routing problem of the tool motion on sheet cutting. Model. Anal. Inform. Sist., 22, 2015. [19] George Steiner. On the complexity of dynamic programming for sequencing problems with precedence constraints. Annals of Operations Research, 26(1):103–123, 1990. 198 Efficient solution method for Generalized Travelling Salesman Problem with precedence constraints of a special type Alexander G. Chentsov, Daniel M. Khachay Krasovskii Institute of Mathematics and Mechanics (Yekaterinburg, Russia) Ural Federal University (Yekaterinburg, Russia) Keywords: Asymmetric Generalized Traveling Salesman Problem (AGTSP), NP-hard problem, dynamic programming. We consider the combinatorial optimization problem of visiting clusters of a fixed number of nodes (cities) under the special type of precedence constraints. This problem is a kind of the Generalized Traveling Salesman Problem (GTSP). To find an optimal solution of the problem, we propose a dynamic programming based on algorithm extending the well known Held and Karp technique. In terms of special type of precedence constraints, we describe subclasses of the problem, with polynomial (or even linear) in n upper bounds of time complexity. 199