научная статья по теме ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ В ЗАДАЧЕ МАРШРУТИЗАЦИИ СО СЛОЖНОЙ ЗАВИСИМОСТЬЮ СТОИМОСТЕЙ ОТ СПИСКА ЗАДАНИЙ Кибернетика

Текст научной статьи на тему «ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ В ЗАДАЧЕ МАРШРУТИЗАЦИИ СО СЛОЖНОЙ ЗАВИСИМОСТЬЮ СТОИМОСТЕЙ ОТ СПИСКА ЗАДАНИЙ»

ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2014, № 2, с. 26-40

СИСТЕМНЫЙ АНАЛИЗ И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ

УДК 519.6.

ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ В ЗАДАЧЕ МАРШРУТИЗАЦИИ СО СЛОЖНОЙ ЗАВИСИМОСТЬЮ СТОИМОСТЕЙ ОТ СПИСКА ЗАДАНИЙ* © 2014 г. А. А. Ченцов, А. Г. Ченцов

Екатеринбург, Институт математики и механики им. Н.Н. Красовского УрО РАН, Уральский федеральный ун-т Поступила в редакцию 16.10.12 г., после доработки 19.11.13 г.

Рассматривается задача о посещении мегаполисов, осложненная условиями предшествования и зависимостью функций стоимости (внешних перемещений и внутренних работ) от списка последующих заданий. Построена модификация метода динамического программирования и на ее основе — алгоритм, реализованный на персональном компьютере.

DOI: 10.7868/S000233881402005X

Введение. Исследуемая задача маршрутизации восходит на идейном уровне к известной труд-норешаемой задаче — задаче коммивояжера (ЗК) [1—3], но содержит целый ряд существенных особенностей, связанных с прикладными задачами. В частности, это касается "многозначной версии" — задачи обхода мегаполисов, условий предшествования, формализующих различные ограничения инженерных задач. Особо стоит отметить (в этом ряду) ситуацию, в которой стоимости перемещений и работ, выполняемых в пределах мегаполисов, явным образом зависят от списка еще не выполненных заданий. Эта ситуация является, однако, естественной для одной важной задачи, возникающей в современной атомной энергетике; речь идет об организации демонтажа оборудования энергоблока атомной электростанции (АЭС), выведенного из эксплуатации: демонтированные на текущий момент фрагменты оборудования исключатся из числа действующих источников излучения. Таким образом, сам процесс демонтажа можно рассматривать как процедуру последовательного "выключения" упомянутых источников; эту процедуру можно осуществлять в различной очередности, что будет, в конечном итоге, влиять на величину суммарной дозы, полученной исполнителем на всем протяжении работ. Возникающей при этом задаче оптимизации (в обобщенной постановке) посвящена целая серия работ; см., например, [4, гл. 5; 5]. В этих публикациях обсуждалась проблема посещения мегаполисов, в которой каждое решение определялось соответствующей парой маршрут—трасса. При этом предполагалось, что пункты прибытия и отправления для каждого из мегаполисов совпадают, что ограничивало возможности в части задания тех или иных внутренних (т.е. осуществляемых в пределах мегаполиса) работ. В настоящем исследовании это ограничение снимается, а сама схема исследования становится более общей и подобной в логическом отношении работам [6—10], в которых, однако, не рассматривался случай, когда стоимости перемещений зависят от списка заданий ([6—10] были ориентированы на другую актуальную инженерную задачу, а именно на задачу минимизации дозовой нагрузки при выполнении комплекса работ в помещениях АЭС; см., в частности, [11, 12]). Предлагаемое исследование обобщает, следовательно, также и положения [6—10], распространяя последние на постановки, в которых упомянутая зависимость имеет место. В то же время и для задач, рассматриваемых в [4, гл. 5; 5], здесь достигается известное обобщение: для каждого из посещаемых мегаполисов пункт прибытия и пункт отправления совпадать уже не обязаны, что может оказаться полезным при моделировании вышеупомянутой задачи о демонтаже (см. в этой связи [13, 14]).

В статье рассматривается построение решения на основе широко понимаемого метода динамического программирования (МДП); отметим, что, как и в [4—10], здесь используется конструкция, не предусматривающая построения всего массива значений функции Беллмана (на-

* Работа выполнена в рамках программ Президиума РАН (проекты № 12-П-1-1012; 12-П-1-1019) и при финансовой поддержке РФФИ (проекты № 13-01-90414 Укр_ф_а; 12-01-00537).

помним, что модификация МДП для решения ЗК построена в [15, 16]). Ниже используются положения [17].

1. Общие определения и обозначения. Используем кванторы, пропозициональные связки; А обозначает равенство по определению, def заменяет фразу "по определению". Через 9( X) (через 9 '(X)) обозначаем семейство всех (всех непустых) подмножеств множества X, а через Fin(X) — семейство всех конечных множеств из 9 '(X). В дальнейшем [R — вещественная прямая, N = {1;2;...} е 9'([), N0{0} u N = {0;1;2;...}; при p е N0 и q е N0

pq 4 {i е N0|(p < i) & (i < q)} e 9(4)

есть диапазон изменения целых чисел отp до q. Если K— непустое конечное множество, то |Kl е N есть def мощность (количество элементов) множества K; тогда (bi) [K ] — множество всех биекций

"отрезка" 1, |K| на K [18, с. 86]. Напомним, что [18, с. 87] перестановкой непустого множества A называется (всякая) биекция A на себя. Полагаем, кроме того, что 10| = 0. Итак, всякому конечному множеству Kсопоставлено число |K| е N0.

Если х и y — объекты, то {x; y} есть def множество, содержащее х, y и не содержащее никаких других элементов. Тогда {z} = {z; z} — одноэлементное множество, содержащее z, где z — произвольный объект. Множества являются объектами, а потому для любых двух объектов u и v определена [19] упорядоченная пара (УП) (u, v) = {{u};{u; v}} с первым элементом u и вторым элементом v. Зачастую для обозначения той или иной УП используем одну букву. Если z — какая-либо УП, то pr1(z) и pr2(z) — первый и второй элементы z, однозначно определяемые условием z = = (pr1(z), pr2(z)) (pr1(z) и pr2(z) имеют смысл проекций УП z и реализуют ее расщепление на элементы); разумеется, в случае z е A х B, где A и B — множества, непременно pr^z) е A и pr2(z) е B. Если a, b и c — объекты, то (a,b,c) = ((a,b),c). Напомним, что [20, с. 17] для всяких трех множеств P, Q и R P х Q х R = (P х Q) х R

Используем обычные правила экономии скобок для значений функций нескольких переменных. Так, если A, B и C — непустые множества, D е 9 '(A х B), f : D ^ C, a е A, b е B и z = (a, b) е D, то f(a, b) = f(z). Аналогичным образом полагаем, что для всяких непустых множеств A, B, C и D, функции g : A х B х C ^ D и элементов a е A, b е B и c е Cg(a, b, c) = g(h), где h = (a, b, c).

Всюду в дальнейшем [0,<x>[= {£, e [|0 < t} и для всякого множества Sв дальнейшем Ш+[S] есть def множество всех функций из S в [0, да[. Далее используем индексную форму записи функций [21];

в частности, для всяких множества S и числа m е N отображение из 1, m в S рассматриваем как кортеж в S: при s1 е S,...,sm е S

(si)i.Tm: 1 m ^ S

есть отображение s из 1, m в S, для которого s(k) = sk У к е 1, m. В аналогичном смысле понимаем отображения из 0, m в S, также интерпретируя их как кортежи в S(при s0 е S, s1 е S,..., sm е Sрассматриваем (si)ie0m как отображение из 0, m в S).

2. Постановка задачи. Фиксируем непустое множество X, точку х0 е X, натуральное число N е N, 2 < N, и кортеж множеств

(M,)^: 1N ^ Fin(X), именуемых мегаполисами; полагаем при этом, что

(Mp n Mq = 0Vp е 1N Vq е 1N\{p}) & (x0 £ MjVj e 1N). (2.1)

Мы рассматриваем задачу организации перемещений

x0 ^ (pr1(z1) e Maiy)^ pr2(z1) e Maa)) ^ ... ^ (pr1(zN) e Ma{N)^ pr2(zN) e M^n)), (2.2)

где a — перестановка множества 1,N (т. е. перестановка индексов из 1,N). Здесь прямые стрелки обозначают внешние перемещения, а волнистые — перемещения при выполнении внутренних

работ. При этом а есть правило нумерации (строго говоря, отображение), а а(у), где у е 1,N, есть результат применения этого правила к аргументу], имеющему смысл дискретного времени. Введем в рассмотрение множество

( N \

X ±

и *

V'- = 1

и {х0}. (2.3)

С учетом (2.3) процессы вида (2.2) можно трактовать как движения в X х X. Мы полагаем при этом, что выбор перестановки в (2.2) может быть стеснен условиями предшествования. В этой

связи считаем заданным множество К е Р(1, N х 1, N) (случай К = 0 не исключается и соответствует отсутствию ограничений на выбор а). При этом выполнено следующее условие.

Ус л о в и е. УК0 е 9'(К)3 г0 е К0 : рг^г0) Ф рг2(г) Уг е К0.

Полагая Р = (Ы)[1, Щ, получаем множество всех перестановок в 1, N. Если ае Р, то ёеГа-1 е Р:

а -1(а(к)) = а(а-1(к)) = к У к е lЩ

(введена перестановка, обратная к а). Далее перестановки из Р называем маршрутами. Множество всех маршрутов, допустимых по предшествованию, определяется условиями [17, ч. 2]

А = {ае Р| а-1(рг1(г)) < а-1(рг2(г)) Уг е К}. (2.4)

В рассматриваемом случае (см. условие) А Ф 0, т.е. А е 9 '(Р). Введем трассы — "движения" в пространстве УП из X х X, следуя (2.2). Полагаем в этой связи, что Z — множество всех кортежей

(г-)iEoщ ■ 0, N ^ X X X, а также

^ = {(гд^ е 2|(г0 = (х0,х0)) &(гу е иа0) X иа0) У] е МО} Уае Р. (2.5)

Если ае А, то %а — множество всех кортежей (г0,г1,• ZN), таких, что (г1,...,zN) соответствует

(2.2), а г 0 = (х0, х0). Ясно, что (см. (2.5)) % а е Fin(Z) Уа е Р. Каждая УП (а, г), где ае А и г е % а, есть допустимое решение. Для оценивания таких решений будут введены три типа функций стоимости; пусть далее 9 '(1, N. Итак, фиксируем функции

с е Шх X х ЭД], с е^+[М1 х М1 х ЭД], ..., cN е 9ft+[MN х MN х ЭД], / еЖ+

N

и м,

1

(2.6)

В (2.6) c используется для оценки внешних перемещений в (2.2), с1, ..., cN — для оценивания внутренних перемещений в мегаполисах, связанных с работами, а / — для оценки терминального состояния. Итак, в связи с (2.2) величины стоимостей имеют следующий вид (полагаем здесь, что 2 <

с(х0,ргх(г1), 1,ЩФ^),рг^Л,N\{а(1)}),

c(pг2(ZN-1), pГl(ZN), 1, N \ {а(,') : 1е 1, N -1}), с^, 1, (2.7)

cal2)(Z2,\N \ {а(1)}), с^щ^ХЙ \ {а(,') : , е 1,N -1}), Дрг^))•

Значения (2.7) оценивают все этапы перемещений вида (2.2). С учетом биективности а (2.7) преобразуется к системе значений

с(х0, рг^),{а(,'): ,' е 1, Щ),ф^Ы, рг^),{а(,'): ,' е 2, N), ...,

Ср^^Хрг^Х{«(Ю}),Са(1)(г1,{а(,'): ,'е 1,N1), (2.8)

Са(2)(г2,М) : , е 2,N1), с^^,{а^В/(pг2(ZN))■

В (2.7) учтено то обстоятельство, что по мере продвижения по мегаполисам (см. (2.2)) осуществляется "выключение" источников вредных воздействий (в случае задачи о демонтаже энергоблока АЭС речь идет о разборке излучающих фрагментов оборудования). Для оценивания решения

(а, (г,);-еощ), где а е А и (г,);-еощ е

Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.

Показать целиком