Программные продукты и системы

Программное обеспечение для решения многих задач дискретной оптимизации основано на математической модели обобщенной задачи коммивояжера (Generalized Traveling Salesman Problem, GTSP), одной из самых известных задач комбинаторной оптимизации, впервые сформулированной в [1] и заинтересовавшей многих исследователей (например [2]). В GTSP для заданного взвешенного орграфа  G = (V, E, c) и разбиения V1 È … È Vm набора узлов V графа G на непустые взаимно непересекающиеся кластеры требуется найти замкнутый тур с минимальной стоимостью, который посещает каждый кластер Vi точно один раз.

В данной статье рассматривается обобщенная задача коммивояжера с ограничениями предшествования (Precedence Constrained Ge- neralized Traveling Salesman Problem, PCGTSP), каждому допустимому маршруту которой необходимо посещать кластеры в соответствии с заданным частичным порядком. Эта модификация задачи GTSP имеет множество практических применений, среди которых следующие: оптимизация траектории инструмента для станков с ЧПУ [3], минимизация времени и стоимости резки в процессе раскроя листового  металла [4, 5], настройка координатно-измерительного оборудования [6], оптимизация траектории при множественном сверлении отверстий [7].

Обзор текущего состояния  исследований

Задача GTSP является обобщением классической задачи коммивояжера (Traveling Sales- man Problem, TSP). Как следствие, она остается NP-трудной даже на евклидовой плоскости всякий раз, когда число кластеров m является частью ее условия [8]. С другой стороны, хорошо известная схема динамического программирования Хелда–Карпа [9], адаптированная к GTSP, имеет трудоемкость O(n3m22m). Таким образом, задача принадлежит классу FPT (Fixed Parameter Tractability) относительно параметризации количеством кластеров. Более того, при m = O(logn) оптимальное решение GTSP может быть найдено за полиномиальное время. Как следует из приведенного далее обзора литературы, исследования в области алгоритмического анализа задачи GTSP развивались по нескольким основным направлениям.

Первый подход основан на сведении исходной задачи к подходящей постановке асимметричной задачи коммивояжера (Asymmetric Traveling Salesman Problem, ATSP) и к последующему решению полученной вспомогательной задачи [10, 11]. Несмотря на математическое изящество, этот подход не свободен от недостатков:

-     получаемые задачи ATSP обладают специфической структурой, затрудняющей их численное решение и на современных MIP-решателях, таких как Gurobi и CPLEX;

-     даже близкие по функционалу к оптимальным приближенные решения вспомогательной задачи ATSP могут соответствовать недопустимым решениям исходной зада- чи [12].

Другой известный подход связан с разработкой точных алгоритмов для частных случаев задачи GTSP и приближенных алгоритмов с теоретическими оценками, включая алгоритмы ветвей и границ [13, 14] и полиномиальные приближенные схемы (Polynomial-time Appro­ximation Scheme, PTAS) [15, 16].

Третий подход заключается в разработке новых и адаптации известных эвристик и метаэвристик. В этом направлении среди известных результатов выделяются гибридный алгоритм Гутина и Карапетяна [17], адаптация известного солвера Лина–Кернигана–Хельсгауна [18] и метаэвристика адаптивного поиска в больших окрестностях (Adaptive Large Neighbor­hood Search, ALNS) [19], обладающая рекордной на сегодняшний день практической производительностью.

Однако алгоритмические результаты для рассматриваемой в статье задачи PCGTSP до сих пор остаются немногочисленными и, по мнению авторов, исчерпываются следующими:

-     эффективные алгоритмы для специаль- ных ограничений предшествования типа Баласа [20–22] и ограничений предшествования, приводящих к квази- и псевдопирамидальным оптимальным маршрутам [23, 24];

-     общий подход к выводу нижних оценок в методе ветвей и границ [25];

-     метаэвристический солвер PCGLNS, развивающий результаты [26, 27], полученные в [19] для GTSP.

В данной статье предлагаются два новых точных алгоритма для общей постановки задачи PCGTSP, практическая эффективность которых подтверждается сравнительными численными экспериментами.

  Постановка задачи

Рассмотрим общую постановку задачи PCGTSP. Условие ее определяется тройкой  (G, C, Π), где G = (V, E, c) – взвешенный ориентированный граф, вес произвольной дуги  (u, v) Î E которого задается соотношением  c(u, v); C = {V1, …, Vm} – разбиение множества V вершин графа G на m непустых попарно непересекающихся кластеров; Π = (C, A) – ориентированный ациклический граф, задающий частичный порядок (ограничения предшествования) на множестве кластеров C.

Каждой вершине v Î V графа G сопоставим (единственный) кластер V(v), содержащий данную вершину. Далее без ограничения общ- ности полагаем орграф Π транзитивно зам- кнутым (в котором соотношения (Vi, Vj) Î A и  (Vj, Vk) Î A влекут (Vi, Vk) Î A для произвольных индексов i, j и k) и верным включение  (V1, Vp) Î A для каждого p Î {2, …, m}.

Замкнутый маршрут T = v1, v2, …, vm будет допустимым решением задачи PCGTSP при следующих условиях:

-     маршрут T начинается и заканчивается в произвольной вершине v1 Î V1;

-     произвольный кластер Vp Î C посещается маршрутом T точно один раз;

-     маршрут T соответствует частичному порядку Π, то есть любой кластер Vq посещается маршрутом T только после всех кластеров, предшествующих ему в Π.

Стоимость решения T определяется соотношением .

Цель задачи состоит в построении допустимого решения T минимальной стоимости.

Предлагаемые в данной статье алгоритмы опираются на следующие общие основные идеи.

Декомпозиция задачи. В каждой вершине дерева поиска сопоставим исходной задаче две вспомогательные подзадачи следующим образом:

-     рассмотрим подмножество C' Ì C, такое что V1 Î C', зафиксируем некоторый кластер  Vl Î C' и вершины v Î V1 и u Î Vl соответственно;

-     пусть cmin – нижняя граница стоимости  v-u-путей, проходящих через все кластеры C' и удовлетворяющих ограничениям предшествования (в рассматриваемом варианте динамического программирования эта граница будет точной);

-     исключая из C' все внутренние кластеры и соединяя V1 с Vl непосредственно ребром нулевого (0) веса, тем самым создаем подзадачу P, наследующую у исходной задачи веса остальных дуг, разбиение на кластеры и ограничения предшествования;

-     используя соотношение

                               (1)

в качестве нижней границы, отсекаем теку- щий узел всякий раз, когда LB > UB; здесь  OPT(Prel) – вес некоторого эффективно найденного решения релаксации Prel задачи P, UB – стоимость наилучшего найденного допустимого решения исходной задачи.

Нижние границы. Сравним нижние оценки, получаемые применением различных релаксаций вспомогательной задачи P. Для построения релаксации P используем двухэтапный подход, предложенный в [25]. На первом этапе сведем задачу P к подходящей постановке задачи ATSP одним из следующих способов.

1. Ослабляя исходные ограничения предшествования, исключаем ребра (v', v'') Î E, для которых (V(v''), V(v')) Î A. Затем сведем полученную задачу к ATSP, используя классическое преобразование Нуна и Бина [11].

2. Ослабляя аналогичным способом исходные ограничения предшествования, сведем полученную задачу к ATSP, определенной на вспомогательном графе кластеров

 где

3. Сведем исходную задачу к ATSP, определенной на ориентированном графе

 где

то есть для любого  упорядоченная пара (Vi, Vk) Î A, если существует  и вершины v¢ Î Vi, v² Î Vj, v¢² Î Vk такие, что путь  π = v¢, v², v¢² согласован с исходными ограничениями предшествования.

Далее c2(V1, Vl) = 0, c2(V1, Vl) = min{c(v¢, v²) + + c(v², v¢²)}: путь π = v¢, v², v¢² – допустимый}.

На втором этапе повторно релаксируем полученную задачу ATSP путем либо нахождения минимального остовного дерева (Minimum Spanning Arborescence Problem, MSAP), либо решения подходящей задачи о назначениях (Assignment Problem, AP). Тем самым находим искомую нижнюю границу по формуле (1). Кроме того, в некоторых случаях для уточнения нижних оценок находим оптимальное значение вспомогательной задачи ATSP, применяя солвер Gurobi. Для удобства все способы получения нижних оценок приведены в таблице 1, столбцы которой соответствуют способам релаксации исходной задачи на первом этапе предлагаемой процедуры, а строки – способам построения оценок на втором.

Таблица 1

Нижние границы

Table 1

Lower bounds

Опираясь на результаты численных экспериментов, сократим список используемых методов построения нижних оценок. По наблюдениям, оценки L1–L3 оказывались наиболее точными с доверительной вероятностью 95 %. На тестовых задачах L1 в среднем оказывается в интервале 0.91±0.02 по отношению к оценке L3, оценка L2 соответственно 0.97±0.02, а оценки E1–E4 систематически ниже: E1 0.48±0.03, E2 и E3 0.54±0.01, E4 0.60±0.002. Кроме того, не используются оценки E5 и E6 в силу повышенной трудоемкости их вычисления. Таким образом, далее ограничиваемся оценками LBi = cmin + Li, i Î {1, 2, 3}.

  Алгоритм ветвей и границ

Для обхода дерева поиска в процессе решения задачи PCGTSP (G, C, Π) используем ме- тод поиска в ширину (алгоритм 1). Каждый узел этого дерева связан с префиксом  σ = (Vi1, Vi2, …, Vir), где Vij Î C, Vi1 = V1 и  r Î {1, …, m}. Кластеры Vij посещаются в порядке, задаваемом последовательностью σ, все остальные – произвольно (с соблюдением ограничений предшествования Π), тем самым образуя вспомогательную задачу P.

Алгоритм 1. BnB :: Главная процедура

Вход: орграф G, кластеры G, частичный порядок Π

Выход: маршрут и его стоимость

1. Инициализация Q = empty queue

2. Начинаем с Root = V1

3. Q.push(Root)

4. while not Q.empty()

5.         Берем следующий префикс для обработки σ = Q.pop()

6.         process=Bound(σ)

7.         if not process then

8.               Префикс отсекается; continue

9.         end if

10.       UpdateLowerBound(σ)

11.       for all child Î Branch(σ) do

12.       Помещаем префикс в очередь на обработку Q.push(child)

13.       end for

14. end while

К каждому узлу дерева поиска применяем процедуру построения нижней оценки Bound (алгоритм 2), заключающуюся в выполнении следующих действий:

-     для префикса σ сопоставляем кортеж T(σ) = (Vi1, {Vi1, Vi2, …, Vir}, Vir);

-     на шаге 4 вычисляем матрицу D(σ) минимальных попарных расстояний по формуле

(эта матрица легко вычисляется инкрементально с использованием матрицы D(σ¢) родительского узла дерева поиска);

-     если для некоторого σ1, T(σ) = T(σ1) и D(σ)uv ³ D(σ1)uv, v Î Vi1, u Î Vir, то префикс σ доминируется префиксом σ1 и подлежит отсечению;

-     на шаге 11 вычисляем оценки L1 и L2 (табл. 1) и сохраняем их в глобальной переменной OptT, используя формулу

-     для текущего узла σ на шаге 13 рассчитываем нижнюю границу по формуле

-     наконец, узел σ отсекается, если  LB > UB; префиксы, избежавшие отсечения, обрабатываются процедурой ветвления Branch (алгоритм 3), которая пытается удлинить префикс σ на один кластер с соблюдением ограничений предшествования.

Алгоритм 2. BnB :: Bound

Вход: префикс σ

Выход: признак того, что префикс подлежит обработке

1. global DTij

2. global OptT

3. вычисляем кортеж T = (Vi1, {Vi1, Vi2, …, Vir}, Vir)

4. Dij=MinCosts(σ)

5. if Dij ⩾ DTij [T], "i, j then

6.    return false

7. end if

8. обновляем веса маршрутов DTij [T] =  = min(DTij [T], Dij), "i, j

9. cmin = minij Dij

10. if T Ï OptT then

11.       вычисляем нижнюю границу  OptT[T] = max(L1(σ), L2(σ))

12. end if

13. LB = cmin + OptT[T]

14. if LB > UB then

15.      return false

16. end if

17. return true

  Динамическое программирование

Основная идея алгоритма ветвей и границ представляется близкой к классической схеме динамического программирования (Dynamic Programming, DP) Хелда–Карпа [9], адаптированной к учету ограничений предшествования и дополненной стратегией оценивания, представленной в [28].

В данной работе реализуется усовершенствованная версия этой схемы для численной оценки производительности описанного выше алгоритма ветвей и границ. Подобно классической схеме представленный алгоритм состоит из двух этапов.

1.    Строится таблица динамического программирования в прямом направлении инкрементально, слой за слоем. Оптимальное значение решаемой задачи находится после построения последнего, m-го слоя.

2.    Оптимальный маршрут восстанавливается обратным ходом по таблице, построенной на первом этапе.

Каждое состояние DP соответствует частичному v-u-пути и индексируется кортежем (C¢, Vl, v, u), где C¢ Ì C представляет собой идеал частично упорядоченного множества кластеров C, то есть " (V Î C¢, V¢ Î C, (V¢, V) Î A) Þ  Þ (V¢ Î C¢); очевидно, в предлагаемых условиях V1 принадлежит произвольному идеалу  C¢ Ì C; Vl Ì C¢, для которого нет такого V Î C¢, что (Vl, V) Î A; v Î V1, u Î Vl.

Значение каждой ячейки DP S содержит ссылку S[pred] на предшествующее состояние, локальное значение нижней оценки S[LB] и стоимость S[cost] соответствующего частичного v-u-пути.

Пусть Ák – подмножество идеалов размера  k Î {1, …, m}. Очевидно, что Á1 = {{V1}}, поэтому первый слой L1 таблицы динамического программирования строится тривиально. Индуктивное построение остальных слоев описано в алгоритме 4.

Алгоритм 3. BnB :: Branch

Вход: префикс σ

Выход: список потомков префикса для обработки

1. Инициализация R = empty queue

2. for all V Î C do

3.         valid = true

4.         for all W Î C do

5.               if W=V or (V, W) Î Π then

6.                     valid = false

7.                     break

8.               end if

9.         end for

10.       if valid then

11.             добавляем новый префикс R.push(σ+V)

12.             end if

13.       end for

14.       return R

Замечания. Оптимум для решаемой задачи дается классическим уравнением Беллмана:

По построению таблица DP имеет размер O(n2m|Á|), значит, время работы алгоритма O(n3m2|Á|), в частности, для частичного поряд­ка фиксированной ширины w |Á| = O(mw) [29]. Следовательно, оптимальное решение PCGTSP может быть найдено за полиномиальное время даже без применения нижних оценок на ша- гах 10–12.

После построения произвольного слоя Lk обновляется глобальное значение нижней оценки, что улучшает точность аппроксимации.

В данной реализации для повышения быстродействия вычисляется оценка L3 на шаге 9 только для небольшого количества состояний с наименьшей нижней оценкой.

Алгоритм 4. DP :: индуктивное построение таблицы динамического программирования

Вход: орграф G, частичный порядок , слой таблицы DP Lk, верхняя граница UB

Выход: (k+1)-й слой Lk+1

1. Инициализация Lk+1 = Æ

2. for all C¢ Î Ák do

3.         for all кластер Vl ÎC \ C¢ s.t.  C¢ È{Vl} Î Ák+1 do

4.               for all v Î V1 и u Î Vl do

5.                     if есть состояние

            S = (C¢, U, v, w) Î Lk s.t.

(w, u) Î E then

6.                          создаем новое состояние

                              S¢ = (C¢ È {Vl}, Vl, v, u)

7.                          S¢[cost] = min{S[cost] + c(w, u):

                              S = (C¢, U, v, w) Î Lk}

8.                          S¢[pred] = argmin{S[cost] +

                              + c(w, u): S = (C¢, U, v, w) Î Lk}

9.                          S¢[LB] = S¢[cost] +

                              + max{L1, L2, L3}

10.                        if S’[LB] ⩽ UB then

11.                               Добавляем S¢ к Lk+1

12.                        end if

13.                   end if

14.             end for

15.       end for

16. end for

17. return Lk+1

  Численные эксперименты

Все алгоритмы тестировались на общедоступной библиотеке PCGTSPLIB [25]. В качестве начального приближения им задавалось одно и то же допустимое решение, полученное эвристикой PCGLNS [27]. Вычисления проводились на одном и том же оборудовании  (16-ядерный Intel Xeon, 128G RAM) с предельным временем счета 10 часов. Для оценки точности вычислений использовалась верхняя оценка относительной погрешности, вычисляемая по формуле

                                       (2)

Критерием остановки является условие  gap < 5 %. Разработанные в данном исследовании алгоритмы реализованы на кроссплатформенном языке Python и могут исполняться на всех современных операционных системах, включая Linux, MacOS и Microsoft Windows. Код оптимизирован за счет использования биб- лиотек NumPy и SciPy для обработки матриц  и NetworkX для работы с графами, для па- раллельного исполнения использован модуль multiprocessing стандартной библиотеки Python. Исходный код доступен в [30].

  Обсуждение

Результаты экспериментов иллюстрирует таблица 2, которая организована следующим образом: первая группа столбцов описывает задачу, включая ее обозначение ID, количество вершин n и кластеров m, а также стоимость стартового решения UB0, полученного эвристикой PCGLNS. Затем следуют три группы столбцов для решателя Gurobi и двух предлагаемых алгоритмов. Каждая группа содержит время счета в секундах, наилучшее значение нижней границы LB и оценку погрешности, заданную в процентах. Задачи, в которых один из предлагаемых алгоритмов превосходит Gurobi по производительности, выделены жирным шрифтом. Следует отметить, что для 13 из 39 задач (33 %) один из построенных авторами алгоритмов показал рекордную производительность, в том числе в 12 случаях по быстродействию и в 7 по точности.

Предложенные алгоритмы смогли найти оптимальное решение в 6 из 39 случаев (хотя такая цель не ставилась). Для 10 (15) постановок, включая одни из самых больших – rbg323a и rbg358a (1 825 и 1 967 вершин соответственно), было получено решение с точностью 5 % (10 %). С другой стороны, для некоторых задач (например, p43.1, p43.2 и p43.3) результаты предлагаемых алгоритмов значительно уступают Gurobi, что, по-видимому, объясняется недостаточно точными нижними оценками.  В то же время для задач p43.4 и ry48p.4 алгоритмы значительно превзошли Gurobi. В целом, хотя Gurobi демонстрирует в среднем чуть лучшую производительность, почти все предложенные алгоритмы показывают вполне сопоставимые результаты. Необходимо добавить, что в проводимых экспериментах солверу Gurobi, как и тестируемым алгоритмам, было предоставлено хорошее стартовое решение, полученное эвристикой, что не является обязательным при организации подобных сравнительных экспериментов.

Заключение

В данной работе описан разработанный первый специализированный алгоритм ветвей и границ для обобщенной задачи коммивояжера с ограничениями предшествования. Он развивает идеи классической схемы динамического программирования Хелда–Карпа и подход Салмана к построению нижних оценок. Предложенные авторами алгоритмы реализованы в виде ПО на языке программирования Python, что обеспечивает мультиплатформенность программного продукта.

Для оценки производительности алгоритмов проведены численные эксперименты, в которых для сравнения использовался передовой коммерческий солвер Gurobi, продемонстрирована их конкурентоспособность.

В качестве направления дальнейших исследований предполагается разработка более точных нижних оценок. Кроме того, по мнению  авторов, дальнейшая оптимизация и распараллеливание могут существенно улучшить производительность представленных алгоритмов.

В настоящее время разработанное ПО интегрируется с САПР СИРИУС [31], предназначенной для оптимизации раскроя листового материала на фигурные заготовки и подготовки управляющих программ для машин листовой резки с ЧПУ.

Численные эксперименты проводились на суперкомпьютере «Уран» Института математики и механики им. Н.Н. Красовского Уральского отделения Российской академии наук.

Работа выполнена при финансовой поддержке Министерства науки и высшего образования РФ, соглашение № 075-02-2021-1383.

Литература

1.    Srivastava S., Kumar S., Garg R., Sen P. Generalized traveling salesman problem through n sets of nodes. CORS J., 1969, vol. 7, no. 2, pp. 97–101.

2.    Gutin G., Punnen A.P. The Traveling Salesman Problem and Its Variations. Boston, MA: Springer US, 2007, 38 p.

3.    Castelino K., D’Souza R., Wright P.K. Toolpath optimization for minimizing airtime during machining. J. of Manufacturing Systems, 2003, vol. 22, no. 3, pp. 173–180. DOI: 10.1016/S0278-6125(03)90018-5.

4.    Chentsov A.G., Chentsov P.A., Petunin A.A., Sesekin A.N. Model of megalopolises in the tool path optimisation for CNC plate cutting machines. Int. J. of Production Research, 2018, vol. 56, no. 14,  pp. 4819–4830. DOI: 10.1080/00207543.2017.1421784.

5.    Makarovskikh T., Panyukov A., Savitskiy E. Mathematical models and routing algorithms for economical cutting tool paths. Int. J. of Production Research, 2018, vol. 56, no. 3, pp. 1171–1188. DOI: 10.1080/ 00207543.2017.1401746.

6.    Salman R., Carlson J.S., Ekstedt F., Spensieri D., Torstensson J., Söderberg R. An industrially validated CMM inspection process with sequence constraints. Procedia CIRP, 2016, vol. 44, pp. 138–143. DOI: 10.1016/j.procir.2016.02.136.

7.    Dewil R., Küçükoğlu ̇I., Luteyn C., Cattrysse D. A critical review of multi-hole drilling path optimization. Archives of Computational Methods in Engineering, 2019, vol. 26, no. 2, pp. 449–459. DOI: 10.1007/ s11831-018-9251-x.

8.    Papadimitriou C. The Euclidean travelling salesman problem is NP-complete. Theoretical Computer Science, 1977, vol. 4, no. 3, pp. 237–244. DOI: 10.1016/0304-3975(77)90012-3.

9.    Held M., Karp R.M. A dynamic programming approach to sequencing problems. J. Soc. Indust. Appl. Math., 1962, vol. 10, no. 1, pp. 196–210. URL: http://www.jstor.org/stable/2098806 (дата обращения: 16.09.2021).

10. Laporte G., Semet F. Computational evaluation of a transformation procedure for the symmetric generalized traveling salesman problem. INFOR: Information Systems and Operational Research, 1999, vol. 37,  no. 2, pp. 114–120. DOI: 10.1080/03155986.1999.11732374.

11. Noon C.E., Bean J.C. An efficient transformation of the generalized traveling salesman problem. INFOR: Information Systems and Operational Research, 1993, vol. 31, no. 1, pp. 39–44. DOI: 10.1080/ 03155986.1993.11732212.

12. Karapetyan D., Gutin G. Efficient local search algorithms for known and new neighborhoods for the generalized traveling salesman problem. EJOR, 2012, vol. 219, no. 2, pp. 234–251. DOI: 10.1016/j.ejor. 2012.01.011.

13. Fischetti M., González J.J.S., Toth P. A branch-and-cut algorithm for the symmetric generalized traveling salesman problem. Operations Research, 1997, vol. 45, no. 3, pp. 378–394. DOI: 10.1287/opre.45.3.378.

14. Yuan Y., Cattaruzza D., Ogier M., Semet F. A branch-and-cut algorithm for the generalized traveling salesman problem with time windows. EJOR, 2020, vol. 286, no. 3, pp. 849–866. DOI: 10.1016/ j.ejor.2020.04.024.

15. Feremans C., Grigoriev A., Sitters R. The geometric generalized minimum spanning tree problem with grid clustering. 4OR, 2006, vol. 4, no. 4, pp. 319–329. DOI: 10.1007/s10288-006-0012-6.

16. Khachai M.Y., Neznakhina E.D. Approximation schemes for the generalized traveling salesman problem. Proc. Steklov Inst. Math, 2017, vol. 299, no. 1, pp. 97–105. DOI: 10.1134/S0081543817090127.

17. Gutin G., Karapetyan D. A memetic algorithm for the generalized traveling salesman problem. Natural Computing, 2010, vol. 9, no. 1, pp. 47–60. DOI: 10.1007/s11047-009-9111-6.

18. Helsgaun K. Solving the equality generalized traveling salesman problem using the Lin–Kernighan–Helsgaun algorithm. Mathematical Programming Computation, 2015, vol. 7, no. 3, pp. 269–287. DOI: 10.1007/s12532-015-0080-8.

19. Smith S.L., Imeson F. GLNS: An effective large neighborhood search heuristic for the generalized traveling salesman problem. Computers and Operations Research, 2017, vol. 87, pp. 1–19. DOI: 10.1016/ j.cor.2017.05.010.

20. Balas E., Simonetti N. Linear time dynamic-programming algorithms for new classes of restricted TSPs: A computational study. INFORMS J. on Computing, 2001, vol. 13, no. 1, pp. 56–75. DOI: 10.1287/ijoc. 13.1.56.9748.

21. Chentsov A.G., Khachai M.Y., Khachai D.M. An exact algorithm with linear complexity for a problem of visiting megalopolises. Proc. Steklov Inst. Math, 2016, vol. 295, no. 1, pp. 38–46. DOI: 10.1134/ S0081543816090054.

22. Chentsov A., Khachay M., Khachay D. Linear time algorithm for precedence constrained asymmetric generalized traveling salesman problem. IFAC-PapersOnLine, 2016, vol. 49, no. 12, pp. 651–655. DOI: 10.1016/j.ifacol.2016.07.767.

23. Khachay M., Neznakhina K. Towards tractability of the Euclidean generalized traveling salesman problem in grid clusters defined by a grid of bounded height. In: Communications in Computer and Information Science, 2018, vol. 871, pp. 68–77. DOI: 10.1007/978-3-319-93800-4_6.

24. Khachay M., Neznakhina K. Complexity and approximability of the euclidean generalized traveling salesman problem in grid clusters. Annals of Mathematics and Artificial Intelligence, 2020, vol. 88, no. 1,  pp. 53–69. DOI: 10.1007/s10472-019-09626-w.

25. Salman R., Ekstedt F., Damaschke P. Branch-and-bound for the precedence constrained generalized traveling salesman problem. Operations Research Letters, 2020, vol. 48, no. 2, pp. 163–166. DOI: 10.1016/ j.orl.2020.01.009.

26. Khachay M., Kudriavtsev A., Petunin A. PCGLNS: A heuristic solver for the precedence constrained generalized traveling salesman problem. In: Optimization and Applications, 2020, pp. 196–208. DOI: 10.1007/978-3-030-62867-3_15.

27. GitHub. AndreiKud. PCGLNS. URL: https://github.com/AndreiKud/PCGLNS/ (дата обращения: 16.09.2021).

28. Morin T.L., Marsten R.E. Branch-and-bound strategies for dynamic programming. Operations Research, 1976, vol. 24, no. 4, pp. 611–627. URL: http://www.jstor.org/stable/169764 (дата обращения: 16.09.2021).

29. Steiner G. On the complexity of dynamic programming for sequencing problems with precedence constraints. Annals of Operations Research, 1990, vol. 26, no. 1-4, pp. 103–123. DOI: 10.1007/BF02248587.

30. GitHub. Ukoloff. PCGTSP-BnB. URL: https://github.com/ukoloff/PCGTSP-BnB (дата обращения: 16.09.2021).

31. Tavaeva A., Petunin A., Ukolov S., Krotov V. A cost minimizing at laser cutting of sheet parts on CNC machines. In: Mathematical Optimization Theory and Operations Research, pp. 422–437. DOI: 10.1007/978-3-030-33394-2_33.

References

1. Srivastava S., Kumar S., Garg R., Sen P. Generalized traveling salesman problem through n sets of nodes. CORS J., 1969, vol. 7, no. 2, pp. 97–101.
2. Gutin G., Punnen A.P. The Traveling Salesman Problem and Its Variations. Boston, MA: Springer US, 2007, 38 p.
3. Castelino K., D’Souza R., Wright P.K. Toolpath optimization for minimizing airtime during machining. J. of Manufacturing Systems, 2003, vol. 22, no. 3, pp. 173–180. DOI: 10.1016/S0278-6125(03)90018-5.
4. Chentsov A.G., Chentsov P.A., Petunin A.A., Sesekin A.N. Model of megalopolises in the tool path optimisation for CNC plate cutting machines. Int. J. of Production Research, 2018, vol. 56, no. 14, pp. 4819–4830. DOI: 10.1080/00207543.2017.1421784.
5. Makarovskikh T., Panyukov A., Savitskiy E. Mathematical models and routing algorithms for economical cutting tool paths. Int. J. of Production Research, 2018, vol. 56, no. 3, pp. 1171–1188. DOI: 10.1080/00207543.2017.1401746.
6. Salman R., Carlson J.S., Ekstedt F., Spensieri D., Torstensson J., Söderberg R. An industrially validated CMM inspection process with sequence constraints. Procedia CIRP, 2016, vol. 44, pp. 138–143. DOI: 10.1016/j.procir.2016.02.136.
7. Dewil R., Küçükoğlu ̇I., Luteyn C., Cattrysse D. A critical review of multi-hole drilling path optimization. Archives of Computational Methods in Engineering, 2019, vol. 26, no. 2, pp. 449–459. DOI: 10.1007/s11831-018-9251-x.
8. Papadimitriou C. The Euclidean travelling salesman problem is NP-complete. Theoretical Computer Science, 1977, vol. 4, no. 3, pp. 237–244. DOI: 10.1016/0304-3975(77)90012-3.
9. Held M., Karp R.M. A dynamic programming approach to sequencing problems. J. Soc. Indust. Appl. Math., 1962, vol. 10, no. 1, pp. 196–210. Available at: http://www.jstor.org/stable/2098806 (accessed September 16, 2021).
10. Laporte G., Semet F. Computational evaluation of a transformation procedure for the symmetric generalized traveling salesman problem. INFOR: Information Systems and Operational Research, 1999, vol. 37, no. 2, pp. 114–120. DOI: 10.1080/03155986.1999.11732374.
11. Noon C.E., Bean J.C. An efficient transformation of the generalized traveling salesman problem. INFOR: Information Systems and Operational Research, 1993, vol. 31, no. 1, pp. 39–44. DOI: 10.1080/03155986.1993.11732212.
12. Karapetyan D., Gutin G. Efficient local search algorithms for known and new neighborhoods for the generalized traveling salesman problem. EJOR, 2012, vol. 219, no. 2, pp. 234–251. DOI: 10.1016/j.ejor.2012.01.011.
13. Fischetti M., González J.J.S., Toth P. A branch-and-cut algorithm for the symmetric generalized traveling salesman problem. Operations Research, 1997, vol. 45, no. 3, pp. 378–394. DOI: 10.1287/opre.45.3.378.
14. Yuan Y., Cattaruzza D., Ogier M., Semet F. A branch-and-cut algorithm for the generalized traveling salesman problem with time windows. EJOR, 2020, vol. 286, no. 3, pp. 849–866. DOI: 10.1016/j.ejor.2020.04.024.
15. Feremans C., Grigoriev A., Sitters R. The geometric generalized minimum spanning tree problem with grid clustering. 4OR, 2006, vol. 4, no. 4, pp. 319–329. DOI: 10.1007/s10288-006-0012-6.
16. Khachai M.Y., Neznakhina E.D. Approximation schemes for the generalized traveling salesman problem. Proc. Steklov Inst. Math., 2017, vol. 299, no. 1, pp. 97–105. DOI: 10.1134/S0081543817090127.
17. Gutin G., Karapetyan D. A memetic algorithm for the generalized traveling salesman problem. Natural Computing, 2010, vol. 9, no. 1, pp. 47–60. DOI: 10.1007/s11047-009-9111-6.
18. Helsgaun K. Solving the equality generalized traveling salesman problem using the Lin–Kernighan–Helsgaun algorithm. Mathematical Programming Computation, 2015, vol. 7, no. 3, pp. 269–287. DOI: 10.1007/s12532-015-0080-8.
19. Smith S.L., Imeson F. GLNS: An effective large neighborhood search heuristic for the generalized traveling salesman problem. Computers and Operations Research, 2017, vol. 87, pp. 1–19. DOI: 10.1016/j.cor.2017.05.010.
20. Balas E., Simonetti N. Linear time dynamic-programming algorithms for new classes of restricted TSPs: A computational study. INFORMS J. on Computing, 2001, vol. 13, no. 1, pp. 56–75. DOI: 10.1287/ijoc.13.1.56.9748.
21. Chentsov A.G., Khachai M.Y., Khachai D.M. An exact algorithm with linear complexity for a problem of visiting megalopolises. Proc. Steklov Inst. Math., 2016, vol. 295, no. 1, pp. 38–46. DOI: 10.1134/S0081543816090054.
22. Chentsov A., Khachay M., Khachay D. Linear time algorithm for precedence constrained asymmetric generalized traveling salesman problem. IFAC-PapersOnLine, 2016, vol. 49, no. 12, pp. 651–655. DOI: 10.1016/j.ifacol.2016.07.767.
23. Khachay M., Neznakhina K. Towards tractability of the Euclidean generalized traveling salesman problem in grid clusters defined by a grid of bounded height. In: Communications in Computer and Information Science, 2018, vol. 871, pp. 68–77. DOI: 10.1007/978-3-319-93800-4_6.
24. Khachay M., Neznakhina K. Complexity and approximability of the Euclidean generalized traveling salesman problem in grid clusters. Annals of Mathematics and Artificial Intelligence, 2020, vol. 88, no. 1, pp. 53–69. DOI: 10.1007/s10472-019-09626-w.
25. Salman R., Ekstedt F., Damaschke P. Branch-and-bound for the precedence constrained generalized traveling salesman problem. Operations Research Letters, 2020, vol. 48, no. 2, pp. 163–166. DOI: 10.1016/j.orl.2020.01.009.
26. Khachay M., Kudriavtsev A., Petunin A. PCGLNS: A heuristic solver for the precedence constrained generalized traveling salesman problem. In: Optimization and Applications, 2020, pp. 196–208. DOI: 10.1007/978-3-030-62867-3_15.
27. GitHub. AndreiKud. PCGLNS. Available at: https://github.com/AndreiKud/PCGLNS/ (accessed September 16, 2021).
28. Morin T.L., Marsten R.E. Branch-and-bound strategies for dynamic programming. Operations Research, 1976, vol. 24, no. 4, pp. 611–627. Available at: http://www.jstor.org/stable/169764 (accessed September 16, 2021).
29. Steiner G. On the complexity of dynamic programming for sequencing problems with precedence constraints. Annals of Operations Research, 1990, vol. 26, no. 1-4, pp. 103–123. DOI: 10.1007/BF02248587.
30. GitHub. Ukoloff. PCGTSP-BnB. Available at: https://github.com/ukoloff/PCGTSP-BnB (accessed September 16, 2021).
31. Tavaeva A., Petunin A., Ukolov S., Krotov V. A cost minimizing at laser cutting of sheet parts on CNC machines. In: Mathematical Optimization Theory and Operations Research, pp. 422–437. DOI: 10.1007/978-3-030-33394-2_33.