1- Уральский федеральный университет (Екатеринбург) 2- Институт математики и механики им. Н. Н. Красовского УрО РАН (Екатеринбург) Рассматриваются задачи маршрутизации, возникающие на объектах использования ядерной энергии и в машиностроении при фигурной резке листового металла на станках с ЧПУ. Общей составляющей у этих задач является проблема выбора очередности выполнения заданных работ при наличии нестандартных ограничений на очередность выполнения работ и нетрадиционные варианты формирования функционала, описывающего качество работы. Описана процедура построения оптимального решения задачи на основе метода динамического программирования. Ключевые слова: маршрутизация, динамическое программирование, условия предшествования, доза облучения, станки с ЧПУ.
объектов. В [1, c. 99] приведен пример задачи демонтажа четырех объектов. Там просчитаны все возможные 24 варианта очередности демонтажа объектов, и показано, что наименьшая суммарная доза оказалась в два раза меньше наибольшей. Этот пример демонстрирует значимость маршрутной составляющей при минимизации суммарной дозы облучения персонала.
Вторым важным примером задач последовательного обхода мегаполисов является задача
маршрутизации режущего инструмента [
Постановка задачи Пусть X
непустое множество, x0 ∈ X (база процесса), N ∈ N := {1; 2; . . .}, N ≥ 2; конечные множества именуем мегаполисами и полагаем, что заданы непустые отношения Mf1, . . . , MfN : Требуется организовать перемещения
M1 ∈ Fin(X), . . . , MN ∈ Fin(X) x0 ∈/ Mj ∀ j ∈ 1, N
& (Mp ∩ Mq = ∅, p 6= q); Mf1 ⊂ M1 × M1, . . . , MfN ⊂ MN × MN . (1) (2) (3) x0 → x1,1 ∈ Mα(1) −→ x1,2 ∈ Mα(1) → . . . → xN,1 ∈ Mα(N) −→ xN,2 ∈ Mα(N) , для которых z1 = (x1,1, x1,2) ∈ Mfα(1), . . . , zN = (xN,1, xN,2) ∈ Mfα(N); объекты выбора: α перестановка 1, N , z1, . . . , zN .
Характерный пример отношений (1): в задаче управления инструментом при листовой резке на станках с ЧПУ каждое отношение Mfj ¾составлено¿ из упорядоченных пар (x∗, x∗), где x∗ точка врезки, а x∗ точка выключения инструмента, соответствующая точке x∗.
Условия предшествования. Пусть P множество всех перестановок 1, N (т.е. маршрутов). Допускаем, что выбор α ∈ P может быть стеснен условиями предшествования.
Итак, фиксируем множество K, K ⊂ 1, N × 1, N упорядоченных пар z, именуемых адресными; pr1(z) индекс ¾отправителя¿, pr2(z) индекс ¾получателя¿. Каждый ¾отправитель¿ должен посещаться ранее соответствующего ¾получателя¿. Постулируем, что для всякого непустого множества K0, K0 ⊂ K, непременно ∃ z0 ∈ K0 : pr1(z0) 6= pr2(z) ∀ z ∈ K0. В практических задачах условие (3), как правило, выполняется.
Пусть A множество всех маршрутов α ∈ P, обладающих K-допустимостью (по предшествованию): ∀ z ∈ K ∀ t1 ∈ 1, N ∀ t2 ∈ 1, N ((α(t1) = pr1(z)) & (α(t2) = pr2(z))) ⇒ (t1 < t2). Тогда (при условии (3)) A 6= ∅, (¾сокращаем¿ фазовое пространство);
A = {α ∈ P | α−1(pr1(z)) < α−1(pr2(z)) ∀ z ∈ K}.
Xe := {x0} ∪ X := {x0} ∪
N ! [ Mi ∈ Fin(X) i=1 N ! [ Mi ∈ Fin(Xe), i=1 где Mj := {pr2(z) : z ∈ Mj} ∀ j ∈ 1, N .
Через Z обозначаем множество всех кортежей (zi)i∈0,N → Xe × X. Трассы (траектории), согласованные с маршрутом: если α ∈ P, то в соответствии с (2)
Zα := {(zi)i∈0,N ∈ Z | (z0 = (x0, x0)) & (zt ∈ Mfα(t) ∀ t ∈ 1, N )} ∈ Fin(Z) (движения в пространстве упорядоченных пар).
В виде D := {(α, z) ∈ A × Z | z ∈ Zα} ∈ Fin(A × Z) имеем (непустое) множество допустимых решений (ДР), определенных каждое в виде пары маршрут-трасса.
Функции стоимости, формирующие аддитивный критерий Через Ne обозначаем семейство всех непустых п/м 1, N : Ne := P0(1, N ). Фиксируем c : Xe × Xe × Ne → [0, ∞[, c1 : Xe × Xe × Ne, . . . , cN : Xe × Xe × Ne, f : Xe → [0, ∞[. Здесь c оценивает внешние перемещения; cj ¾внутренние¿ работы, связанные с посещением Mj, где j ∈ 1, N , а f терминальное состояние (элемент xN,2 в (2)).
Значения c(x, y, K) функции c содержательны в одном из двух случаев: 1. x = x0, y ∈ Mj, где j ∈ K при K ∈ Ne (т.е. K 6= ∅, K ⊂ 1, N ); 2. x ∈ Mfi, y ∈ Mfj, i 6= j, j ∈ K, где K ∈ Ne.
Затем используется произвольное продолжение данных содержательных зависимостей до функции на Xe × Xe × Ne.
При j ∈ 1, N значения cj(x, y, K) содержательны при (x, y) ∈ Mfj и K ∈ Ne со свойством j ∈ K. Значения f (x) существенны при x ∈ X \ {x0}.
Продолжение этих содержательных зависимостей до функций на Xe × Xe × Ne и на Xe соответственно может быть произвольным.
При α ∈ P и (zi)i∈0,N ∈ Ze полагаем, что
N Ceα[(zi)i∈0,N ] := X[c(pr2(zt−1), pr1(zt), {α(l) : l ∈ t, N }) + cα(t)(zt, {α(l) : l ∈ t, N })] + f (pr2(zN )) t=1 (4) (учитываем стандартное правило A × B × C = (A × B) × C; поэтому cα(t)(zt, {α(l) : l ∈ t, N }) = cα(t)((xt, yt), {α(l) : l ∈ t, N }) = cα(t)(xt, yt, {α(l) : l ∈ t, N }), где xt = pr1(zt) и yt = pr2(zt); t ∈ 1, N ). Используем (4) при α ∈ A и (zi)i∈0,N ∈ Zα, получая аддитивный критерий качества.
Ceα[(zi)i∈0,N ] → min, α ∈ A, (zi)i∈0,N ∈ Zα (5) (минимизировать (4) на непустом конечном множестве D всевозможных ДР). Задаче (5) соответствует значение (глобальный экстремум) и (непустое) множество Цель: найти V и какое-либо решение (α0, z0) ∈ Dopt.
Для достижения этой цели используют аппарат ДП. 3
Динамическое программирование Введем (см. [2, ч. 2]) в рассмотрение отображение посредством соглашения: если K ∈ Ne, то
V := min min α∈A (zi)i∈0,N ∈Zα
Ceα[(zi)i∈0,N ] ∈ [0, ∞[ Dopt := {(α0, z0) ∈ D|Ceα0 [z0] = V } 6= ∅.
I : Ne → Ne,
I(K) := K \ {pr2(z) : z ∈ Ξ[K]}, где Ξ[K] = {z ∈ K | (pr1(z) ∈ K) & (pr2(z) ∈ K)}. Выражения (6), (7) определяют оператор вычеркивания (заданий из списка). Действие его таково, что из списка удаляем ¾получателей¿ адресных пар, ¾полностью¿ укладывающихся в список.
Пусть G := {K ∈ Ne | ∀z ∈ K (pr1(z) ∈ K) ⇒ (pr2(z) ∈ K)} и
Gs := {K ∈ G | s = |K|} ∀s ∈ 1, N .
При этом G1 = {{t} : t ∈ 1, N \K1}, где K1 := {pr1(z) : x ∈ K}; ясно, что GN = {1, N }. Наконец (см. [
(GN = {1, N }) −→ GN−1 −→ ... −→ G1.
На основе (8) конструируются слои пространства позиций: D0, D1, . . . , DN (см. подробнее [
При этом DN := {(x0, 1, N )} (синглетон, содержащий позицию (x0, 1, N )), D0 := {(x, ∅) : x ∈ F}, где D0 и DN крайние слои пространства позиций.
Теперь построим регулярные слои пространства позиций. Пусть Тогда при K ∈ Gs последовательно определяем
F :=
[ i∈1,N\K1
Mi; s ∈ 1, N − 1. (клетка пространства позиций). Наконец, при условии (9) полагаем
Js(K) := {j ∈ 1, N \ K | {j} ∪ K ∈ Gs+1}, Φs[K] =
[ j∈Js(K)
Mj, Ds[K] := {(x, K) : x ∈ Φs[K]}
Ds :=
a Ds[K] 6= ∅ K∈Gs (имеется ввиду дизъюнктная сумма клеток). Таким образом, построена система слоев: D0, D1, . . . , DN (все слои непустые множества). Ключевыми свойством системы слоев является следующее: если s ∈ 1, N , (x, K) ∈ Ds, j ∈ I(K) и z ∈ Mfj, то
(pr2(z), K \ {j}) ∈ Ds−1.
Слои функции Беллмана: v0, v1, . . . , vN определяются посредством рекуррентной процедуры на основе представления: при s ∈ 1, N vs(x, K) := min min [c(x, pr1(z), K) + cj(z, K) + vs−1(pr2(z), K\{j})] ∀(x, K) ∈ Ds.
j∈I(K) z∈Mej
Функция v0 ∈ R+[D0] определяется явным образом v0(x, ∅) := f (x) ∀x ∈ F, а дальнейшее построение
v1, ..., vN осуществляется по рекуррентной схеме: если s ∈ 1, N и функция vs−1 ∈ R+[Ds−1] нам известна,
то vs ∈ R+[Ds] определяем с помощью (10). При этом [
V = vN (x0, 1, N ) = min min [c(x0, pr1(z), 1, N ) + cj(z, 1, N ) + v(pr2(z), 1, N \ {j})].
j∈I(K) z∈Mej (10) (11) Теперь рассмотрим процедуру построения оптимального решения. Полагаем z(0) := (x0, x0) и строим решение в виде пары маршрут-трасса.
С учетом (11) выбираем j1 ∈ I(1, N ) и z(1) ∈ Mfj1 так, что
V = c(x0, pr1(z(1)), 1, N ) + cj1 (z(1), 1, N ) + vN−1(pr2(z(1)), 1, N \ {j1}), где (pr2(z(1)), 1, N \ {j1}) ∈ DN−1. Тогда vN−1(pr2(z(1)), 1, N \ {j1}) =
min min [c(pr2(z(1)), pr1(z), 1, N \ {j1})+ j∈I(1,N\{j1}) z∈Mej cj(z, 1, N \ {j1}) + vN−2(pr2(z), 1, N \ {j1; j})]. С учетом этого выбираем j2 ∈ I(1, N \ {j1}) и z(2) ∈ Mfj2 , для которых vN−1(pr2(z(1)), 1, N \ {j1}) = c(pr2(z(1)), pr1(z(2)), 1, N \ {j1})+
+cj2 (z(2), 1, N \ {j1}) + vN−2(pr2(z(2)), 1, N \ {j1; j2}), где (pr2(z(2)), 1, N \ {j1; j2}) ∈ DN−2.
С учетом представления V в терминах vN−1 имеем
V = c(pr2(z(0)), pr1(z(1)), 1, N ) + c(pr2(z(1)), pr1(z(2)), 1, N \ {j1})+ +cj1 (z(1), 1, N ) + cj2 (z(2), 1, N \ {j1}) + vN−2(pr2(z(2)), 1, N \ {j1; j2}). Если N = 2, то оптимальное решение построено. Если N > 2, то процедуру следует продолжать вплоть до исчерпывания 1, N . В итоге будут построены маршрут η := (js)s∈1,N ∈ A
(z(t))t∈0,N ∈ Zη Ceη[(z(t))t∈0,N ] = V. Итак, (η, (z(t))t∈0,N )
допустимое оптимальное решение.
Вставки на основе динамического программирования
Известные трудности вычислительной реализации (ЗК одна из классических NP – полных задач)
вынуждают к использованию эвристик при решении практических задач большой размерности. При этом,
как правило, упомянутые эвристики должны обеспечивать безусловное соблюдение всех ограничений
соответствующей задачи. Значение критерия может при этом существенно отличаться от оптимального. В этих
условиях представляется, однако, естественным подход, связанный с локальным улучшением ДР
посредством применения оптимизирующих вставок с возможной реализацией последних в итерационном режиме.
Данный подход отражен в [
Пусть заданы n ∈ N, n ≥ 3, x0 ∈ X, L1 ∈ Fin(X), ..., Ln ∈ Fin(X), Le1 ∈ P0(L1 × L1), ..., Len ∈ P0(Ln × Ln), причем Lj, j ∈ 1, n, попарно дизъюнктны; x0 ∈/ Lt ∀t ∈ 1, n. Предполагается, что n достаточно большое число. Предметом исследования являются процессы
x0 −→ (x1,1 ∈ Lα(1) −→ x1,2 ∈ Lα(1)) −→ ... −→ (xn,1 ∈ Lα(n) −→ (xn,2 ∈ Lα(n)), где α перестановка 1, n; требуется при этом, чтобы
(x1,1, x1,2) ∈ Leα(1), ..., (xn,1, x1,2) ∈ Leα(n). Объектом нашего выбора являются перестановка α и кортеж ((x1,1, x1,2), ..., (xn,1, xn,2)). Ситуация вполне соответствует постановке, связанной с (2). Полагаем, однако, что N ∈ 2, n − 1, т.е. задача раздела 2 "меньше"в смысле размерности. Реально значение n значительно больше, чем N . С процессами (12), (13) связывается "аддитивная"задача маршрутизации, в идейном отношении подобная задаче (5) (мы полагаем, что в "большой"задаче имеются условия предшествования, а стоимости перемещений, как и в разделе 2, зависят от списка заданий). Разумеется при точном определении "большой"задачи используются замены x0 −→ x0, N −→ n, Mj −→ Lj, Mfj −→ Lej, K также заменяется некоторым отношением в 1, n (в связи с точной постановкой см. [12, п. 2]). Соответствующим образом модифицируются функции стоимости раздела 2.
Предположим, что в "большой"задаче удалось каким-то образом найти ДР (λ, h); здесь λ : 1, n −→ 1, n маршрут, допустимый по предшествованию, а h трасса, согласованная с λ: (12) (13) (14) h(1) ∈ Leλ(1), ..., h(n) ∈ Leλ(n). Мы стремимся улучшить качество, доставляемое ДР (λ, h) посредством оптимизирующей вставки "длины"N. Иными словами, мы создаем задачу раздела 2, привязанную к (λ, h). Для этого выбираем ν ∈ 0, n − N в качестве "начала"вставки, полагаем x0 = pr2(h(ν)) и ∀s ∈ 1, N
(Ms := Lλ(ν+s))&(Mfs := Leλ(ν+s)).
Прочие построения см. в [12, п. 3]) (в частности, функции c, c1, ..., cN и f конструируются по функциям
стоимости "большой"задачи). Полученный таким образом вариант задачи (5) "обрабатывается"процедурой
ДП, после чего получившееся локально оптимальное ДР задачи (5) вклеивается в исходное ДР (λ0, h0) :=
(λ, h), порождая новую эвристику (λ1, h1), для которой ν0 := ν изменяем затем до ν1 ∈ 0, n − N
(конкретные способы получения нового "начала"ν1 см. в [
Приложения к прикладным задачам
Предстоящие масштабные работы по выводу из эксплуатации объектов использования атомной энергии
(ОИАЭ) определяют важность решения задачи минимизации дозовых затрат при демонтаже
радиоактивного оборудования. При этом одновременно с автоматизацией и роботизацией демонтажных работ,
требующими значительных материальных затрат, значительный потенциал в сокращении дозовых затрат
имеет маршрутная оптимизация работ [
Рис. 3: Раскройный план и маршрут режущего инструмента Реализация рассмотренных алгоритмов применительно к задаче фигурной резки металла на станках с ЧПУ приведена,например, в [17]. На рис. 3 показан пример раскройного плана, построенные вдоль контуров мегаполисы и оптимальный маршрут режущего инструмента, полученный с помощью динамического программирования. Благодарности Работа выполнена при финансовой поддержке РФФИ, грант № 16-01-00649, и при финансовой поддержке Правительства Российской федерации, постановление № 211, контракт № 02.A03.21.0006. . Список литературы [1] V. V. Korobkin, A. N. Sesekin, O. L. Tashlykov, A. G. Chentsov. Metody marshrutizatsii i ih primenenie v zadachah povyshenia bezopastnosti b effektivnosti ekspluatazii atomnih stanzii [Routing methods and their applications in the tasks of increasing the safety and efficiency of operation of nuclear power plants]. Moscow, “New Technologies”, 2012. (in Russian) = В. В. Коробкин, А. Н. Сесекин, О. Л. Ташлыков, А. Г. Ченцов. Методы маршрутизации и их приложения в задачах повышения безопасности и эффективности эксплуатации атомных станций.. М.: Издательство “Новые технологии”. 2012. [2] A. G. Chentsov. Ekstremalnie zadachi marshrutizatsii i raspredelenia zalaybq: voprosy teorii [Extreme tasks of routing and distribution of tasks: theory questions]. Moscow – Izhevsk, SIC Regular and chaotic dynamics, 2008. (in Russian) = А. Г. Ченцов. Экстремальные задачи маршрутизации и распределения заданий: вопросы теории. Москва – Ижевск.: НИЦ “Регулярная и хаотическая динамика”, 2008. [3] G. Gutin, A. Punnen. The Traveling Salesman Problem and Its Variations. Berlin: Springer, 2002. [4] W. J. Cook. In pursuit of traveling salesman. Mathematics at the limits of computation. N.J. Princeton
Univer. Press., 2012. [5] A. A. Petunin Modelling of Tool Path for the CNC Sheet Cutting Machines. AIP Conference Proceedings,1690: 060002(1)–060002(7). 2015.
Route optimization engineering
Ural Federal University (Yekaterinburg, Russia)
Ural Federal University (Yekaterinburg, Russia) Institute of Mathematics and Mechanics (Yekaterinburg, Russia)
Ural Federal University (Yekaterinburg, Russia)
Ural Federal University (Yekaterinburg, Russia) Institute of Mathematics and Mechanics (Yekaterinburg, Russia) the nuclear ob jects and mechanical
Abstract. The article is devoted to the routing problems at the nuclear objects and in mechanical engineering (the task of cutting sheet metal on CNC machines). The problem of choosing the sequence of work is present in these two tasks. The presence of non-traditional constraints on the order of assignments and unconventional view of the quality functional is also a common feature of these tasks. We describe the process of constructing an optimal solution based on dynamic programming method.
Keywords: routing, dynamic programming, precedence constraints, exposure dose, CNC cutting machines.