Рассматривается задача обхода мегаполисов с фиксированным числом городов и специальным образом заданными отношениями предшествования, известная также как асимметрическая обобщенная задача коммивояжера (AGTSP). Для поиска оптимального решения задачи приводится схема динамического программирования, развивающая схему Хелда-Карпа, разработанную для классической постановки задачи коммивояжера; обосновываются условия, при которых трудоемкость предложенного алгоритма полиномиально, в частности, линейно зависит от числа мегаполисов.
В рамках третьего подхода изучаются нетривиальные полиномиально разрешимые подклассы исследуемой задачи. В то время как для классической постановки задачи коммивояжера известно большое количество таких подклассов (см., например, [8]), для задачи GTSP подобные результаты нам не известны.
Данная работа посвящена описанию полиномиально разрешимого подкласса задачи GTSP, отягощенного дополнительными ограничениями предшествования специального вида. Полученные результаты являются естественным обобщением результатов, представленных в [2] для классической TSP.
Рассмотрим наиболее общий случай задачи GTSP. В данной постановке для любой пары смежных узлов u и v, стоимости прямых и обратных перемещений не одинаковы. Чтобы подчеркнуть данную асимметрию, будем называть такую постановку Асимметрической Обобщенной Задачей Коммивояжера (AGTSP).
Ограничения предшествования естественны для AGTSP и восходят к конкретным прикладным задачам. В нашем случае эти ограничения определяют порядок посещения мегаполисов и могут быть легко интерпретированы.
Рис. 1: Задача фигурной резки металла Например, в задаче высокоточной резки металла из исходного стандартного листа требуется вырезать детали различной формы. В соответствующей постановке AGTSP, каждой детали сопоставляется конечный мегаполис, состоящий из точек врезки и выключения инструмента, размещенных по ее контуру (рис. 1). Как видно, на исходном листе одни детали могут оказаться вложенными в другие. Технология резки, согласно которой вложенные детали должны быть вырезаны раньше объемлющих, задает естественные ограничения предшествования (рис. 2).
Наша работа структурирована следующим образом. В разделе 2 мы остановимся на математической постановке асимметрической обобщенной задачи коммивояжера. Далее, в разделе 3 мы напомним известную схему динамического программирования Хелда–Карпа (ДП), используемую для нахождения точного решения нашей задачи. В рассматриваемой нами постановке стоимости перемещения и посещения городов предполагаются зависящими от частичных маршрутов, но процедура ДП успешно справляется с этими затруднениями. В разделе 4 мы приведем эквивалентное описание этой процедуры в терминах нахождения кратчайших s-t путей в соответствующем взвешенном ациклическом ориентированном графе (известном как орграф состояний), поскольку обоснование наших результатов, представленных в разделе 5, удобно проводить именно в этих терминах. Наконец, в разделе 6 мы остановимся на одном содержательном примере, иллюстрирующем проведенные рассуждения. 2
Постановка задачи Рассмотрим постановку расширенной асимметрической обобщенной задачи коммивояжера (AGTSP) (рис. 3). Пусть заданы конечные дизъюнктные множества M1; : : : ; Mn, называемые мегаполисами, и стартовая точка x0, не принадлежащая ни одному из них. Без ограничения общности, полагаем множества Mj равномощными и определяемыми равенствами
Mj = fgj1; : : : ; gjpg: j 6= l 2 Nn = f1; : : : ; ng и ; 2 Np; Вместе с транспортными издержками c(gl ; gj ) для произвольных индексов заданы стоимости c^(x0; gj ) и c(gj ; x0) перемещения из точки x0 в каждую из точек gj (и обратно). Далее, фиксируется стоимость посещения (внутренних работ) c0(gj ) каждого из мегаполисов. Задача состоит в нахождении маршрута наименьшей стоимости, начинающегося и заканчивающегося в точке x0 и посещающего все мегаполисы (в точности по одному разу).
С математической точки зрения требуется найти перестановку
: Nn ! Nn; задающую порядок посещения мегаполисов, называемую далее маршрутом, и конечную последовательность g (1) (1); : : : ; g (n) (n), именуемую трассой, так, чтобы
n 1 c^(x0; g (1) (1)) + X i=1 c0(g (i) (i)) + c(g (i) (i); g (i+1) (i+1)) + c(g (n) (n); x0) ! min : (1) Основные отличия между стандартной постановкой AGTSP и рассматриваемой нами в работе состоят в следующем: 1) для любых вершин gl and gj стоимости перехода c(gl ; gj ) и стоимость посещения мегаполиса c0(gj ) зависят от выбранной трассы, соединяющей x0 и вершину gl ; 2) на множестве мегаполисов определен один из двух типов ограничений предшествования (по аналогии с приведенными в работе [2] для классической TSP): Тип I. Для натурального числа k 6 n, любая допустимая перестановка удовлетворяет ограничению 8i; j 2 Nn (j > i + k) ) ( (i) < (j)): (2) Тип II. Для любых натуральных значений 1 6 k(1); : : : ; k(n) 6 n и произвольной допустимой перестановки справедливо соотношение 8i; j 2 Nn (j > i + k(i)) ) ( (i) < (j)): (3) (4) (5) (6) 3
Схема динамического программирования Традиционный подход к решению задачи (1) восходит к классическим работам Беллмана [3] и Хелда и Карпа [11] и опирается на метод динамического программирования.
Пусть оптимальная трасса, выйдя из точки x0, посетив за первые i 1 шагов мегаполисы с номерами из подмножества J Nn, в i-й позиции посещает мегаполис Mj в точке gj (i) 2 Mj. Обозначим стоимость этой части трассы через C(J; i; j; gj (i)). Справедливы следующие рекуррентные соотношения
C(?; 1; j; gj (1)) = c^(x0; gj (1)); C(J; i; j; gj (i)) = min min l2J gl (i 1)2Ml
C(J n flg; i 1; l; gl (i 1)) + c(gl (i 1); gj (i)) + c0(gj (i)) ; причем оптимальное значение задачи (1) может быть вычислено по формуле
C = min (C(Nn n fjg; n; j; gj (n)) + c(gj (n); x0)):
j2Nn Оптимальная трасса восстанавливается с помощью процедуры обратного поиска. 4 Граф состояний
Рекуррентная процедура (4)-(6) допускает эквивалентную формулировку в терминах теории графов. В самом деле, пользуясь известным подходом (см., например, [7]), сопоставим исходной задаче задачу поиска кратчайшего s-t пути в подходящем реберно-взвешенном (n + 2)-дольном ориентированном графе G [p] = = (V [p]; A [p]; w [p]). Через Vi [p] обозначим подмножество вершин, составляющих i-ю долю, задаваемое равенствами
V0 [p] = fsg; Vn+1[p] = ftg; Vi [p] = f(J; i; j; ) : j 2 Nn n J; gj 2 Mj; J
Nn; jJj = i 1g (i 2 Nn): (7) При этом вершины s и t соответствуют стартовой точке x0, а произвольная вершина (J; i; j; ) (обычно именуемая состоянием) соответствует части трассы длины i, посещающей мегаполисы с номерами из множества J [ fjg, последним среди которых мегаполис Mj (в точке gj ). Смежными в графе G [p] являются лишь вершины соседних долей Vi [p] и Vi+1[p]. Дуги G [p] соединяют вершину s с произвольной jJ j = i 1; J 0 = J [ flg; j 62 J 0; ; 2 Np: (8) w [p](s; (?; 1; j; )) = c^(x0; gj ); w [p]((Nn n fjg; n; j; ); t) = c(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
jV [p]j > jV2 [p] [ : : : [ Vn [p]j > pn2n 2: При этом входящая степень произвольной вершины (J; m; j; ) 2 Vm[p] при m > 2 удовлетворяет соотношению deg (J; m; j; ) = (m 1)p > p: Следовательно, jA [p]j = (np22n).
Тем не менее, введение в условие задачи дополнительных ограничений, например, ограничений предшествования на множестве мегаполисов, может существенно снизить суммарную трудоемкость процедуры поиска оптимального решения (см., например, [19]). Ниже мы воспользуемся подходом, предложенным Баласом [2] для классической TSP, в рамках которого схема (4)-(6) обладает линейной по n трудоемкостью. 5
Оценки трудоемкости Начнем с описания частного случая графа G [p], соответствующего ограничениям предшествования типа I и типа II, описанным выше. Покажем, что структура графа G [p] определяется структурой графа G [1]. Лемма 1. Для любого p > 1:
Vi [p] = Vi [1]
Np (i 2 Nn) A0;1[p] = A0;1[1]
Np; An;n+1[p] = An;n+1[1]
Np Ai;i+1[p] = Ai;i+1[1]
N2p (i 2 Nn 1)
(9)
(10)
(
jA [p]j 6 jA [1]j p2: В работе [2] была описана структура графа G [1], определяющего динамическую процедуру для классической TSP с дополнительными ограничениями предшествования (2) и (3). Представим эти результаты в Теореме 1. Теорема 1. 1. В случае ограничений предшествования (2) 2. В случае ограничений (3) для
jA [1]j = O(n k22k 2): jA [1]j = O n X k (i)(k (i) + 1)2k (i) 2
! i=1 k (i) = maxfk(j) : i k(j) + 1 6 j 6 ig: Наши основные результаты для оценки вычислительной сложности следуют из Леммы 1 и Теоремы 1. Теорема 2. Пусть для рассматриваемой задачи AGTSP имеют место ограничения предшествования (2). Тогда схема динамического программирования (4)-(6) позволяет получить оптимальное решение (для данной задачи) за время
O(n p2k22k 2): Теорема 3. Если любая любая постановка задачи AGTSP удовлетворяет следующим ограничениям предшествования (3), тогда схема (4)-(6) будет выполнена за время
n !
O p2 X k (i)(k (i) + 1)2k (i) 2 :
i=1
(
Содержательный пример Обсудим применимость ограничений предшествования. На первый взгляд, ограничения (2)-(3) могут показаться излишне строгими. Тем не менее, даже ограничение (2), при k от 1 до n, охватывает все возможные случаи задачи AGTSP.
Рассмотрим следующий содержательный пример. Нужно составить план эвакуации из многоэтажного здания при пожаре. Здание состоит из m этажей. На t-м этаже находится qt комнат. Каждая комната (Mi) имеет несколько дверей (рис. 4). Команда спасателей может начать выполнение своего задания, высадившись на любом этаже (стоимостью доставки на этаж можно пренебречь). После выполнения своего задания команда может быть эвакуирована также с любого этажа. Однако основным ограничением является возможность перехода между этажами только с помощью лифтов: стоимость такого перемещения намного выше, чем стоимость перемещения по этажу. Сформулировав данную задачу математически, мы получим следующие ограничения предшествования. Для комнаты Mi определим 8 q1 + 1 i; при 1 6 i 6 q1; > k(i) = >>< q1 + q2 + 1 i; при q1 + 1 6 i 6 q1 + q2; >> : : : >: Plm=11 ql + 1 i; при Plm=12 ql + 1 6 i 6 Plm=11 ql: Эти ограничения означают, что здание должно быть эвакуировано или сверху вниз, или наоборот. Следовательно, ограничения предшествования (3) являются вполне естественными для данного класса задач. 7 Заключение
В статье предложена процедура динамического программирования для нахождения оптимального решения задачи AGTSP. Для двух типов ограничений предшествования показано, что процедура является эффективной. В этом случае трудоемкость такой процедуры линейна по n для любых фиксированных k и p и полиномиальна при k = O(log n) и p = O(poly(n)). Благодарности Список литературы
Исследования поддержаны Российским научным фондом, грант № 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(
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. [19] George Steiner. On the complexity of dynamic programming for sequencing problems with precedence constraints. Annals of Operations Research, 26(1):103–123, 1990.
solution method for Generalized Travelling with precedence constraints of a special type Salesman Alexander G. Chentsov, Daniel M. Khachay Krasovskii Institute of Mathematics and Mechanics (Yekaterinburg, Russia) Ural Federal University (Yekaterinburg, Russia)