Автоматика и телемеханика, № 4, 2014
© 2014 г. А.Г. ЧЕНЦОВ, чл.-корр. РАН (Институт математики и механики им. Н.Н. Красовского УрО РАН, Екатеринбург)
ЗАДАЧА ПОСЛЕДОВАТЕЛЬНОГО ОБХОДА МЕГАПОЛИСОВ С УСЛОВИЯМИ ПРЕДШЕСТВОВАНИЯ1
Исследуется задача маршрутизации с ограничениями, связанная с посещением конечной системы мегаполисов и выполнением во время данных посещений тех или иных (внутренних) работ. Стоимости перемещений и выполняемых работ могут зависеть от списка заданий, не выполненных на текущий момент. Предложен вариант метода динамического программирования, не использующий построение всего массива значений функции Беллмана; обсуждаются некоторые варианты эвристических алгоритмов. Возможные приложения могут быть, в частности, связаны с задачей снижения облучаемости работников атомных электростанций и задачей листовой резки деталей на станках с числовым программным управлением.
1. Введение
В статье рассматриваются задачи маршрутизации, связанные с посещением конечной системы мегаполисов в условиях ограничений, определяемых условиями предшествования (имеются также и другие ограничения на систему перемещений). Исследуемая в работе постановка ориентирована на прикладные задачи. В частности, это касается инженерной задачи о снижении облучаемости персонала атомных электростанций (АЭС), а также подобных по смыслу задач, связанных с утилизацией источников излучения в условиях аварийных ситуаций (Чернобыль, Фукусима); можно также иметь в виду задачу демонтажа энергоблока АЭС, выведенного из эксплуатации, в этой связи см., в частности, [1, 2]. Другая важная прикладная задача связана с маршрутизацией процесса листовой резки деталей на станках с числовым программным управлением (ЧПУ); в этой связи см. [3]. Кроме того, проблемы упомянутого типа возникают в задачах о морских и авиационных перевозках, при организации авиапожарного патрулирования лесов.
При всем разнообразии прикладных задач с элементами маршрутизации оказывается возможным предложить весьма общие подходы, идеологически связанные с широко понимаемым динамическим программированием (ДП); в этой связи отметим оригинальные работы [4, 5], связанные с применением ДП в задаче коммивояжера (ЗК). Разумеется, ЗК может рассматриваться в качестве прототипа задач маршрутизации, исследуемых в настоящей работе. В связи с решением ЗК особо отметим метод ветвей и границ [6], который находит широкое применение и в других задачах дискретной оптимизации.
1 Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (проекты № 12-01-00537-а, № 13-04-00847-а, № 13-01-90414_укр_ф_а ).
Конструкции решения маршрутных задач с ограничениями, используемые в настоящей работе, восходят к [7] и в значительной степени отражены в [8]. Сейчас отметим, наряду с условиями предшествования также следующую существенную особенность постановки: в статье рассматривается случай задачи последовательного обхода мегаполисов, когда стоимости перемещений и (внутренних по смыслу) работ в мегаполисах могут зависеть от списка не выполненных на текущий момент заданий. Такая ситуация возникает в известной инженерной задаче о демонтаже энергоблока АЭС, выведенного из эксплуатации: "светят" те фрагменты оборудования, которые не демонтированы на момент перемещения. Возникает постановка задачи с усложненными функциями стоимости.
Подобное усложнение может возникать и по другим причинам. Так, в простейшем варианте задачи обслуживания клиентов в той или иной очередности возможна ситуация, когда у клиентов имеются предпочтения престижного характера (в простейшем случае все хотят "быть первым"), что приводит к стоимостям, включающим зависимость от параметра, имеющего смысл дискретного времени. С помощью простого преобразования (см. [9]) исходная содержательная задача может быть сведена к постановке со стоимостями, зависящими от списка заданий, см. [10, 11].
По поводу моделей, использующих ЗК, отметим [12-14], где (см. [12]) рассматривались задачи маршрутизации с различными особенностями прикладного характера. Сейчас отметим упоминавшиеся в [12] ЗК с выбором и задачу курьера, а также исследования [15, 16], посвященные решению задачи развозки. Важную роль в упомянутых и во многих других задачах играют условия предшествования (условия типа "одно после другого"). В задаче о демонтаже энергоблока АЭС такие условия возникают, в частности, из-за того, что одни фрагменты оборудования могут располагаться на других, а потому "верхние" должны демонтироваться раньше. В задаче листовой резки на станках с ЧПУ источником упомянутых условий является следующее очевидное обстоятельство: нередко вырезаемая деталь имеет один или несколько внутренних контуров (простой пример — шайба), которые должны быть вырезаны раньше внешнего. В результате возникает большое число условий упомянутого типа.
Ограничения такого рода оказалось возможным [7, § 4.9] использовать "в положительном направлении", а точнее, в целях снижения сложности вычислений. Этот прием использовался в [1, 7-10] и во многих других работах. В настоящей статье он также применяется при некоторых особенностях постановки. Рассматриваются также эвристические алгоритмы, конструируемые на основе огрубления уравнения Беллмана.
Отметим, что в рамках общей постановки допускается, что внутренние работы (в мегаполисах) сами могут состоять в решении достаточно трудных задач. Так, например, возможны случаи, когда внутренние работы могут сводиться к посещению всех городов мегаполиса, т.е. к решению внутренней ЗК. Возможно также появление своих (внутренних) условий предшествования, и тогда получаем уже (внутреннюю) задачу курьера [12]. Конечно, реально внутренние работы могут исполняться лучше или хуже, но с точки зрения оптимизации можно полагать, что при заданной системе внешних перемещений они осуществляются оптимально, и потому на уровне макрозадачи стоимости
внутренних работ моделируются соответствующими экстремумами (например, при наличии внутренней ЗК, в макрозадаче каждой паре вход — выход (имеются в виду пункты прибытия в мегаполис и отправления) сопоставляется экстремум упомянутой (внутренней) ЗК с заданными начальным и конечным состояниями). Таким образом, рассматриваемая ниже постановка является, вообще говоря, иерархической, где задачи нижнего уровня связываются с выполнением внутренних работ, а верхний уровень соответствует организации внешних перемещений с учетом внутренних работ посредством упомянутой выше системы их экстремумов.
2. Обозначения общего характера
Далее используем кванторы, пропозициональные связки; через = обозначаем равенство по определению, ёе£ заменяет фразу "по определению", 0 — пустое множество. Семейством называем множество, все элементы которого — множества. Для произвольного объекта Н через {Н} обозначаем одноэлементное множество, содержащее Н. Если г — упорядоченная пара (УП), т.е. г = (ж,у) для каких-либо объектов х и у, то через ргг(г) и рг2(г) обозначаем соответственно первый и второй элементы г : р^(г) = х, р^(г) = у; если г € и х V, где и и V — множества, то р^(г) € и и рг2(г) € V. Для любых трех объектов а, Ь и с триплет (а, Ь, с) есть УП специального вида: (а, Ь, с) = ((а, Ь), с). Если же А, В и С — множества, то Ах В х С = (Ах В) х С; если х € А х В и у € С, то для УП (х, у) имеем включение (х, у) € А х В х С.
Для всякого множества Н через Р(Н) обозначаем семейство всех подмножеств (п/м) Н; тогда Р'(Н) = Р(Н)\{0} есть семейство всех непустых п/м Н, а Ет(Н) — семейство всех конечных множеств из Р'(Н) (элементы Ет(Н) — непустые конечные п/м Н и только они).
В дальнейшем используются обычные правила экономии скобок при записи значений функций нескольких переменных, что согласуется с представлениями для УП и триплетов. В этой связи отметим, что для всяких множеств А, В, С и отображения Н : А х В х С — УП р € А х В и элемента д € С определено значение Н(р, д) € ^ в точке (р, д) € А х В х С. Широко используется индексная форма записи отображений (см. [17]): если 5 и Т — непустые множества, а ^ € Т Уз € 5, то есть ёе£ такое отображение
д : 5 — Т, что д(з) = Уз € 5.
Через М обозначаем вещественную прямую с полуосью [0, {{ € М| 0 ^ < С}, N 4 {1; 2;...}, N0 4 {0}и N = {0,1;2;...} и
(2.1) М 4 {^ € < ;') & И < I)} Ук € N0 У1 € N0
(в (2.1) допускается реализация 0). Далее для всякого непустого множества 5 через Р+[£] обозначаем множество всех функций, действующих из 5 в [0, иными словами Р+[£] есть множество всех неотрицательных веще-ственнозначных (в/з) функций на 5.
Непустому конечному множеству К сопоставляем его мощность |К | € N и непустое множество (Ы)[Л"] всех биекций [18, с. 87] "отрезка" 1,\К\ на К]
пусть |0| = 0. Напомним, что перестановкой непустого множества А называется [18, с. 87] всякая биекция А на себя; каждой перестановке а множества А сопоставляется перестановка а-1 упомянутого множества, обратная к а : а(о;_1(ж)) = а_1(о;(ж)) = х Ух € А. Типичный для настоящей работы вариант перестановок соответствует случаю А = 1 ,т, где т € N.
3. Постановка задачи
В настоящем разделе вводится символика, существенно используемая в постановке рассматриваемой далее маршрутной задачи. Фиксируем непустое множество X, х0 € X (база процесса), число N € N со свойством 2 ^ N, множества М1 € Пп(Х),..., М^ € Пп(Х), а также отношения
(3.1) М1 € Р'(М1 х М1), ..., Мм € Г'(МИ х Ми). Множества М1,..., М^ называем мегаполисами; полагаем, что
(3.2) (Мр П Мд = 0 Ур € МУ Уд € Т^Ы \ {р}) к, (ж0 £ М, У] €
Условия (3.2) типичны для моделей с мегаполисами. Отношения М1,..., М^ определяют наборы пар входов-выходов в мегаполисы, отвечающие каждая за начало и окончание внутренних работ.
Замечание 3.1. В связи с (3.1) отметим некоторые варианты, связанные с задачей листовой резки на станках с ЧПУ. В простейшей модели, отвечающей минимизации общего времени холостого хода, можно считать, что М, = {(ж, ж) : х € М,} при ;) € (каждая деталь вырезается "полностью"). Возможен более точный учет обстоятельств, связанных с началом и завершением резки контуров соответствующей детали: фиксируются пары (^1,^2) в Му х Му, где Ж1 — точка вре
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.