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

Одной из наиболее труднодоступных в транспортном отношении территорий Российской Федерации является Арктическая зона (АЗ), охватывающая 4,8 млн кв. км (28 % от общей площади Российской Федерации). На территории АЗ располагается частично или полностью 9 субъектов Российской Федерации. На основании особенностей природно-климатических условий Арктической зоны Российской Федерации (АЗ РФ) можно разделить на западную и восточную части, граница между которыми условно проходит по Уральским горам (рис. 1). На территории АЗ РФ проживает менее 2 % населения России (около 2,4 млн человек). Для восточной части Российской Арктики характерны более суровые погодные условия со среднегодовым перепадом температур в 100 ℃: от +40 до −60 ℃. Особенностью этих территорий является большая разбросанность населенных пунктов, низкая численность постоянно проживающего населения, сезонные ограничения использования автомобильного транспорта (либо в связи с отсутствием дорог с твердым покрытием, либо из-за особенностей рельефа в горных местностях), частичное или полное отсутствие железнодорожного транспорта, постоянный, но небольшой спрос на транспортные услуги, за исключением случаев освоения новых мест добычи полезных ископаемых.

На территориях АЗ РФ, а также на территориях Крайнего Севера и приравненных к ним местностях можно выделить следующие особенности транспортной системы.

1. Основу транспортной системы составляют сезонные морские и речные пути с береговой инфраструктурой, сезонные автозимники, круглогодично действующие аэропорты и посадочные площадки, что определяет ее полуизолированное состояние.

2. Пассажирские перевозки осуществляются круглогодично действующим авиасообщением. Местные перевозки между населенными пунктами выполняются на нерегулярной основе.

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

4. Сложные долгосрочные (до 365–400 дней) мультимодальные схемы доставки топлива увеличивают его стоимость и затрудняют планирование поставок.

В условиях отсутствия достаточной наземной транспортной связанности арктических территорий возникают сложности нормального жизнеобеспечения этих регионов. Под жизнеобеспечением понимается выполнение транспортной системой четырех основных функций: экономической, социальной, геополитической и экологической. В настоящее время в арктических регионах часть этих функций выполняется воздушным транспортом, однако высокая стоимость его эксплуатации и недостаточность наземной инфраструктуры (действующих аэродромов и посадочных полос) приводит к ограничению объема выполняемых функций. Крайне высокая стоимость эксплуатации воздушного транспорта в регионах АЗ обусловлена отсутствием достаточного количества мест базирования легких многоцелевых самолетов, низкой интенсивностью совершаемых полетов, высокими удельными затратами на содержание аэропортовой сети и поддержание летной годности воздушных судов, высокими затратами на доставку авиационного топлива [1]. Решением данной проблемы может стать встраивание беспилотных авиационных систем (БАС) в существующую транспортную структуру АЗ РФ. С этой целью необходимо определить весь спектр основных функций, которые на этих территориях могут эффективно выполняться БАС с учетом всех действующих ограничений.

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

Прежде всего представляется, что в применяемых методах должны присутствовать (в первом случае) направление, связанное с распределением заданий между участниками воздушного движения, и (во втором случае) направление, связанное с оптимизацией последовательности выполнения заданий этими участниками в пределах выделенных им систем заданий. В отмеченном (втором) случае имеются в виду задачи маршрутизации. В своей совокупности здесь реализуются маршрутно-распределительные задачи, которые вполне обоснованно относятся к категории труднорешаемых [2]. Таковыми являются и «составляющие» компоненты: задача разбиения и задачи, обобщающие известную задачу коммивояжера (ЗК). Мы сосредоточимся здесь на проблеме маршрутизации (вопросам, связанным с распределением заданий, посвящены работы [3][4, часть 5]. В частности, в [4, часть 5] построен общий метод решения на основе динамического программирования и указана его реализация в задаче нескольких курьеров. Будем при этом различать постановки, ориентированные на транспортные задачи, и постановки, отвечающие идейно задачам авиапожарного патрулирования; в первом случае потребуется рассмотрение минимаксной постановки, применяемой в задаче маршрутизации на узкие места, а во втором будет рассматриваться схема решения задачи с аддитивным критерием. Итак, в первом случае мы ориентируемся на вопрос о разрешимости транспортной задачи (при соблюдении ограничений предшествования), а во втором стремимся к осуществлению большей оперативности в реализации мониторинга лесных массивов.

В связи с решением ЗК отметим работы [5–9]. Важный вариант ЗК представляет задача курьера [5], в которой присутствуют ограничения предшествования, которые в [4, раздел 4.9] были использованы в положительном направлении для снижения сложности вычислений при реализации динамического программирования (ДП). Мы рассмотрим данный вариант ДП [10][11] в сочетании со специальной конструкцией на основе декомпозиции для двух вариантов агрегирования затрат: аддитивного и варианта, отвечающего минимаксной постановке; такой подход позволяет в случае «двухкластерной» (в смысле декомпозиции) задачи находить композиционный экстремум за вполне приемлемое время. Мы рассматриваем его применение в модельных задачах, ориентированных на проблемы в малой авиации, как первый шаг в построении методов и алгоритмов решения упомянутых в первой части введения весьма конкретных задач, представляющих интерес для организации работы воздушного транспорта в АЗ и для кардинального улучшения в организации мониторинга лесных пожаров.

В первой части статьи в качестве модельной задачи рассматривается простейший пример маршрутизации движения БАС при выполнении авиапожарного патрулирования на заданной плоскости : . Точками на плоскости являются аэродромы либо вертолетные площадки, с которых возможно осуществить взлет БАС. Мегаполисы представляют собой конечные подмножества (п/м) лесных массивов, которые подлежат мониторингу. При этом предполагается, что каждый из мегаполисов достаточен с точки зрения возможностей наблюдения бортовыми средствами для однозначного ответа на вопрос, есть ли возгорание в данном лесу или нет. Основной задачей является смоделировать маршрутизацию движения БАС, которая позволит скорейшим образом посетить все города мегаполиса, то есть, по существу, решить внутреннюю 3K. Пункты прибытия и отправления (для данного мегаполиса) могут выбираться произвольно, а оставшиеся города должны посещаться последовательно. Внешние перемещения оцениваются временами соответствующих перелетов. Условия предшествования определяются приоритетностью посещения наиболее пожароопасных районов, направлением ветра и другими факторами, действующими в данной местности. Размерность модельной задачи достаточно высока, что требует продолжительного времени счета.

Мы используем модель мегаполисов (непустых конечных множеств), которые должны посещаться некоторым транспортным средством (ТС) с целью выполнения при упомянутых посещениях работ, именуемых внутренними. Полагаем при этом, что у нас имеются ограничения предшествования (условия типа «одно после другого»). Оцениваются внешние перемещения (между мегаполисами, из точки старта к мегаполисам), внутренние работы и терминальное состояние. Значения функций стоимости (ФС) могут агрегироваться по-разному: аддитивно либо стоимостью наиболее затратного этапа перемещений.

Итак, следуя [4][10][11], фиксируем непустое множество X, конечное непустое его подмножество X0 возможных точек старта, мегаполисы , где – натуральное число, , а также отношения [12, гл. 2] , связанные (с мегаполисами) условиями для каждого ; элементами каждого отношения являются упорядоченные пары (у/п) (x, y), где x – пункт прибытия в мегаполис , а y – пункт отправления (из ). Оценка внутренних работ, связанных с посещением , зависит от (x, y). Мы допускаем к рассмотрению ФС, включающие зависимость от списка заданий (удобно использовать список заданий, не выполненных на текущий момент, но к этому варианту легко сводится и зависимость от списка уже выполненных заданий). Для более точного описания рассматриваемых задач потребуется формализация, которая, в свою очередь, будет использовать целый ряд общематематических понятий. Этим вопросам посвящается следующий раздел.

В настоящем разделе будут введены общематематические понятия и некоторые общие обозначения, включая нужные элементы теории множеств. Мы используем стандартную теоретико-множественную символику, включая кванторы и пропозициональные связки; далее через обозначаем пустое множество, – равенство по определению, def заменяет фразу «по определению». Впрочем, используя кванторы, мы имеем в виду просто замену слов: заменяет выражение «для любого», заменяет слово «существует». Выражение , где A – множество, обозначает множество всех со свойством ... (вместо x может использоваться произвольная буква). Если A и B – высказывания, то заменяет здесь фразу «если истинно A, то непременно истинно B». Если же C и D – высказывания, то , где & – связка «и»; кроме того, V используем вместо слова «или». Такие упрощенные толкования в дальнейших построениях вполне соответствуют [12]. Семейством называем множество, все элементы которого – множества; итак, семейство суть множество множеств. Если x и y – какие-либо объекты, то через обозначаем их неупорядоченную пару, то есть (единственное) множество, содержащее (x, y) и не содержащее никаких других элементов. Тогда всякому объекту m в виде сопоставляется синглетон (одноэлементное множество) со свойством . Множества являются объектами, а тогда [12, с. 67] для любых двух объектов p и q в виде (p, q) имеем упорядоченную пару (у/п) с первым элементом p и вторым элементом q. Если же h – любая у/п, то через и обозначаем соответственно первый и второй элементы данной у/п h, однозначно определяемые равенством . Если x, y и z – три объекта, то есть (упорядоченный) триплет с первым элементом x, вторым элементом y и третьим элементом z. Для двух любых множеств A и B в виде имеем их декартово произведение, то есть единственное множество со свойствами: 1) при и ) если , то для некоторых и . Если же A, B и C – три множества, то [13, с. 17].

Если H – множество, то через (через ) обозначаем семейство всех (всех непустых) п/м множества H (здесь, как обычно [13, с. 17], п/м H есть множество, содержащееся в H); через обозначаем семейство всех непустых конечных п/м . Для двух любых непустых множеств A и B через BA обозначаем [13, гл. II] множество всех функций, действующих из A в B; при (это то же самое, что ) и в виде имеем значение в точке . Далее будем использовать понятие образа множества: если A и B – непустые множества, и , то

(2.1)

есть образ C при действии при . Используем обычные соглашения для значений функций нескольких переменных. Так, в частности, для непустых множеств и , функции и точек и , как обычно, есть значение в точке . Если же и непустые множества, и , то с учетом определения получаем значение , где и .

Пусть ( – вещественная прямая), и . При и рассматриваем дискретный интервал (ДИ) . Тогда и при . Если и , то , если сдвиг на (непустого) множества . Непустому конечному множеству сопоставляется его мощность и непустое множество (bi) всех биекций ДИ на [14, с. 87]. Перестановка непустого множества есть [14, с. 87] биекция на себя; перестановке данного множества сопоставляется перестановка этого множества, обратная к , со свойством . Разумеется, при в виде (bi) [ имеем множество всех перестановок ДИ (в самом деле, ). Полагаем также . Кортежами называем функции, определенные на непустых п/м . Используем индексную форму записи функций [15, с.11], семейство с индексом). Если – непустое множество, то (множество всех неотрицательных вещественнозначных (в/з) функций на ). Оношением называем п/м декартова произведения двух множеств.

Вернемся к разделу 1, используя, однако, понятия и обозначения, введенные в предыдущем разделе. Итак (см. раздел 1), далее, – непустое множество и , и при этом (случаи, когда , не представляют интереса, и мы их не обсуждаем, хотя и они могут быть «охвачены» постановочной частью без применения декомпозиции); фиксируем мегаполисы

(3.1)

получая семейство ; относительно (3.1) полагаем, что

(3.2)

(Итак, мегаполисы (3.1) попарно дизъюнктны и не содержат точек из ) Полагаем, что точки и только они могут использоваться в качестве стартовых для нашего ТС. Фиксируем также отношения

(3.3)

элементы которых (а это у/п) соответствуют всякий раз объединению в у/п пункта прибытия в мегаполис и пункта отправления из него. Вообще говоря, возможна ситуация, когда , то есть упомянутые пункты, входят в (3.3) именно «отмеченными» парами. Как уже говорилось, все мегаполисы (3.1) должны посещаться (с выполнением внутренних работ) при старте из . В [13–18] и в ряде других работ приведена процедура построения оптимального решения на основе ДП, восходящая к [4, §4.9]. Эта процедура применима и к задачам маршрутизации раздела 1; структура оптимального решения ясна. Возникают, однако, существенные затруднения на этапе вычислительной реализации. В связи с этим мы, ориентируясь на «диапазонные» (в смысле размерности) задачи управления TC, сразу обратимся к построениям [10][11], в которых ДП сочеталось с декомпозицией основной -задачи путем введения двух кластеров и , реализующих разбиение . Итак, при вводим (частичные) семейства

(3.4)

для которых (см. (3.1), (3.2)) и . Полагаем далее, что сначала решается задача обслуживания мегаполисов из и только после этого можно приступать к обслуживанию . Процедуры ДП будут при этом локализованы в возникающих на основе (3.4) предваряющей -задаче и финальной -задаче; итак, рассматривается раздельное применение ДП в частичных задачах.

В связи с (3.4) отметим, что N выбирается, как правило, с учетом возможностей в части вычислительной реализации (грубо говоря, ДИ следует разбить пополам). В ряде прикладных задач, не связанных с малой авиацией, возникают обстоятельства, требующие выделить часть заданий из общей ‑задачи в число первоочередных; на этой основе может формироваться семейство . Здесь мы отметим задачу управления инструментом при фигурной листовой резке деталей на машинах с ЧПУ, в которой (случай термической резки) в число первоочередных включаются так называемые длинномерные детали [19][20, § 1.3.3]. Если подобное выделение первоочередных заданий затруднительно, для целей кластеризации может применяться подход [21], связанный с применением для построения и жадной эвристики. В [10] построен алгоритм для решения задачи маршрутизации с элементами декомпозиции в ситуации, когда кластеров может быть больше двух, но в настоящей работе мы его не обсуждаем и ограничиваемся случаем двухкластерной (3.4) задачи.

Полагаем, что в предваряющей и финальной задачах имеются условия предшествования (эти условия могут задаваться изначально, а могут [21] конструироваться на основе ограничений предшествования основной ‑задачи). Для их введения фиксируем множества

(3.5)

у/п – элементы и – называем адресными; у каждой адресной пары первый элемент называем отправителем, а второй – получателем. В связи с условиями предшествования напомним о задаче курьера в [5].

В связи с задачами малой авиации отметим один возможный вариант условий предшествования, ориентируясь на случай ‑задачи. Итак, мы полагаем, что обсуждается вопрос о перевозке с использованием ТС пассажиров между городами (для простоты) ; при этом полагаем в данном замечании, что при . Кроме того, в некоторых городах в ТС размещаются грузы с заданными адресами доставки (также в виде упомянутых городов). Итак, в целях доставки пассажиров ТС должно посетить все города, но есть еще план директивных грузоперевозок с заданными адресными парами индексов городов. Аналогичная ситуация складывается в ‑задаче. Мы ограничиваемся сейчас случаем, когда условия предшествования сразу разделены по частичным задачам. В связи с противоположным случаем условий предшествования в -задаче и построением на их основе частичных ограничений предшествования отметим конструкцию [21].

Следуя [4, часть 2], условимся, что всюду в дальнейшем

(3.6)

Условия (3.6) исключают зацикливание маршрутов, допустимых по предшествованию в частичных задачах. Данные маршруты (перестановки индексов заданий) при (bi) и (bi) составляют следующие два множества:

(3.7)

(3.8)

Из (3.7), (3.8) следует, что допустимость каждого частичного маршрута сводится к требованию: для каждой адресной пары соответствующей задачи мегаполис с индексом отправителя посещается раньше, чем мегаполис с индексом получателя. Если и в (3.5) определены исходя из планов грузоперевозок, то (3.7) и (3.8) означают, следовательно, выполнение всех упомянутых планов данных ТС для маршрутов, составляющих эти множества, и только для них. Возвращаясь к основной задаче, вводим склеивание произвольных маршрутов из и : при (bi) имеем, что

(3.9)

сам маршрут (3.9) условимся называть композиционным. Из (3.9) следует, что маршрут обязывает к посещению мегаполисов из в очередности , , а затем к посещению мегаполисов из в очередности ; итак, сначала «работает» , а затем В виде

(3.10)

имеем (непустое) множество всех допустимых композиционных маршрутов основной -задачи. Вообще же, выбор маршрута (перестановки множества ) определяет для ТС лишь «укрупненный план» обслуживания . Требуется еще, при всяком выборе маршрута, детализировать конкретные варианты такого обслуживания – указать варианты посещения занумерованных мегаполисов, то есть задать траектории.

Пусть (множество всех кортежей в ); тогда при и в виде

(3.11)

имеем множество всех траекторий посещения (занумерованных) отношений , , связанных с мегаполисами, и стартом в x. Нас в первую очередь интересует случай . В этой связи при введем в рассмотрение множество

(3.12)

всех композиционных допустимых решений (ДР) со стартом в x, имея в виду уже и выбор маршрута, и выбор траектории, согласованной с маршрутом по правилу (3.11). Наконец, мы допускаем и произвольный выбор старта из а потому

(3.13)

есть множество всех возможных (для исследователя) вариантов поведения в условиях декомпозиции, называемых далее композиционными маршрутными процессами (МП). Наряду с (3.12), (3.13) для оценочных целей полезно ввести при

(3.14)

Кроме того, введем в рассмотрение

(3.15)

получая объемлющую совокупность МП (мы в (3.14), (3.15) рассматриваем не только композиционные решения). Тогда, поскольку (см. (3.10)) , имеем при , что . Как следствие (см. (3.13), (3.15)), . Итак, в виде (3.15) имеем объемлющее множество всех МП. По этой причине, снимая ограничения предшествования и требования предваряющего обслуживания мегаполисов из , мы потенциально можем достигать лучших результатов и, как следствие, получать нижние оценки; однако существенное увеличение размерности за счет привлечения МП из приводит обычно к резкому усложнению вычислительной реализации. Далее, мы отметим, что при

 (3.16)

С помощью (3.16) мы конструируем конечные множества, призванные заменить (потенциально бесконечное) множество X на этапе математической постановки с приведением последней к задаче дискретной оптимизации:

 (3.17)

В виде (семейство всех непустых п/м ДИ ) имеем семейство множеств, именуемых далее списками (заданий). Фиксируем ФС

(3.18)

здесь значения с оценивают внешние перемещения (между мегаполисами, из точек к мегаполисам), значения – внутренние работы при посещении мегаполисов, а значения – терминальное состояние траектории. При этом (см. раздел 2) в (3.18) все ФС суть неотрицательные вещественнозначные (в/з) функции. Заметим, что в (3.18) допускается использование ФС с зависимостью от списка заданий (далее используется всякий раз список заданий, не выполненных «на текущий момент»). В исследованиях, связанных с другими прикладными задачами [18][20][21] и др., это позволило охватить единой постановкой целый ряд практически интересных обстоятельств [20, § 1.3.3]. В настоящем исследовании мы сохраняем упомянутые общие определения, имея целью в дальнейшем отразить на уровне постановки те или иные соображения, связанные с применением ТС (например, можно иметь в виду возможность прогнозирования загрузки ТС по мере полета). В простейшем случае ФС в (3.18) можно определить посредством евклидовых расстояний на плоскости, что и будет отражено в модельных примерах.

В дальнейшем рассматриваются два варианта агрегирования затрат: при , и имеем

, (3.19)

, (3.20)

где (см. раздел 2) есть образ ДИ , при действии перестановки . На основе (3.19) определяется аддитивный критерий, а посредством (3.20) – критерий в минимаксной задаче. Напомним, что обозначение sup используется при рассмотрении (точной) верхней грани числового (непустого мажорируемого) множества [13, разд. 2.3]; однако для любых двух чисел и в виде реализуется наибольшее из них, что и соответствует (3.20). Здесь же заметим, что (3.19) и (3.20) определены в случае ; в этом случае (3.19), (3.20) могут использоваться (см. (3.12)) при построении композиционных решений. В то же время в силу (3.14) значения (3.19), (3.20) определены при , то есть в задаче, где не используется декомпозиция и нет условий предшествования. Мы, однако, сосредоточимся на более реализуемом варианте постановок, где декомпозиция, приводящая к двухкластерной задаче, и ограничения предшествования в частичных задачах имеются и используются в интересах снижения сложности вычислений.

Задача с аддитивным критерием. Учитывая (3.19), при рассматриваем ()-задачу:

(3.21)

которой сопоставляются экстремум и непустое экстремальное множество (sol) :

(3.22)

(3.23)

В связи с основной -задачей отметим, что (3.19) определено при . Упомянутую основную задачу определяем в виде

(3.24)

которой сопоставляется (композиционный) экстремум и непустое множество SOL всех оптимальных композиционных МП:

(3.25)

(3.26)

Мы рассматриваем также задачу оптимизации старта (учитываем (3.25))

(3.27)

которой сопоставляется экстремум (см. (3.25)) и непустое экстремальное множество

(3.28)

Задача (3.27) по смыслу является вспомогательной. В то же время при значение (3.19) определено при , а потому мы получаем (оценочную) задачу

(3.29)

которой, подобно (3.22), (3.23), сопоставляются

(3.30)

(3.31)

Ясно, что . При этом (см. (3.15)) значение (3.19) определено для . Тогда имеем (оценочную по отношению к основной) задачу

(3.32)

которой, подобно (3.25) и (3.26), сопоставляются

(3.33)

(3.34)

С учетом (3.25) и (3.33) получаем неравенство

(3.35)

Итак, получаем нижнюю оценку композиционного экстремума.

В данном случае используем критерий, определяемый в (3.20). Как и в аддитивном случае, сначала рассматриваем при задачу с фиксированным стартом x:

(3.36)

задаче (3.36) сопоставляется экстремум и непустое экстремальное множество sol :

(3.37)

(3.38)

мы получаем минимаксную ()-задачу. Отметим, что (3.20) определено в случае . С учетом этого получаем следующую задачу:

(3.39)

(оптимизации в классе МП), для которой определены экстремум и непустое экстремальное множество :

(3.40)

(3.41)

В (3.39)–(3.41) говорится об оптимизации в классе композиционных МП. Как и в случае аддитивной задачи (см. (3.24)), вводим задачу оптимизации старта:

(3.42)

Задаче (3.42) соответствует экстремум (см. (3.40)) и экстремальное множество

(3.43)

Далее, отметим, что значение (3.20) определено при и . Мы получаем при (оценочную) задачу

(3.44)

задаче (3.44) сопоставляется экстремум и непустое экстремальное множество :

(3.45)

=

(3.46)

Наконец, (3.20) определено и при . Приходим к задаче оптимизации МП

(3.47)

которой сопоставляются экстремум и непустое экстремальное множество :

(3.48)

=

(3.49)

Заметим, что (см. (3.37), (3.45)) имеют место неравенства

(3.50)

Кроме того, с учетом (3.40) и (3.48) реализуется неравенство

(3.51)

Мы можем, конечно, рассматривать (3.35) и (3.51) как верхние оценки экстремумов (3.33) и (3.48) соответственно; данные экстремумы могут быть недоступны для непосредственного вычисления, в то время как (3.25) и (3.40) можно [10][11] (для диапазонных в смысле размерности задач) найти за вполне приемлемое время.

Итак, мы в качестве основных рассматриваем задачи (3.24) и (3.39), которые также представляются весьма сложными, но допускающими теоретическое исследование и построение оптимальных алгоритмов решения. В этом построении главным является специальная связка предваряющей и финальной задач. К постановкам этих двух задач мы сейчас и переходим, учитывая (3.4)–(3.8). Начнем с построения множества точек старта финальной -задачи, полагая сначала и получая в виде множество всех неотправителей предваряющей задачи. Тогда

(4.1)

рассматриваем далее в качестве множества всех возможных точек старта -задачи. Далее, при полагаем, что

(4.2)

получая (в (4.2)) непустые конечные множества. Имеем в силу (3.16), (3.17) и (4.2), что

(4.3)

В виде реализуется множество всех маршрутов -задачи, допустимых по предшествованию. В связи с введением траекторий полагаем (множество всех отображений из ДИ в ). Если (см. (4.1)) и , то

(4.4)

есть пучок траекторий -задачи, стартующих из x и согласованных с маршрутом . Тогда при в виде

(4.5)

имеем множество всех допустимых решений (ДР) -задачи со стартом в x.

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

(4.6)

есть пучок траекторий -задачи, стартующих из и согласованных с маршрутом . При в виде

(4.7)

имеем множество всех ДР ()-задачи, то есть -задачи со стартом в . Легко видеть, что [11]

(4.8)

В связи с введением ФС частичных задач отметим, что

(4.9)

из (3.17) и (4.9) легко следуют вложения и . Кроме того, при и имеем с очевидностью, что

(4.10)

Итак, и суть семейства всех непустых п/м ДИ и соответственно, именуемых далее (как и множества из ) списками в - и -задаче соответственно. Теперь определяем -задачи

(4.11)

для которых полагается, что

(4.12)

(4.13)

конкретизируется позднее. Подобно (4.11), (4.12), (4.13), вводим -задачи:

(4.14)

определяются следующими правилами:

(4.15)

мы дополняем набор () ФС функцией из (3.18). Итак, и в (4.11), (4.12) и в (4.14), (4.15) мы фактически работаем с «частями» ФС (3.18), а точнее, с несущественными преобразованиями сужений ФС (3.18). Введем два варианта критерия в частичных задачах. Полагаем при и

(4.16)

(4.17)

итак, (4.16) и (4.17) соответствуют -задаче в ее аддитивном и минимаксном варианте соответственно. Тогда при имеем следующую аддитивную ()-задачу:

(4.18)

которой сопоставляются экстремум

(4.19)

и непустое экстремальное множество

(4.20)

кроме того (при ), имеем минимаксную ()-задачу

(4.21)

для которой определены экстремум

(4.22)

и соответствующее непустое экстремальное множество

(4.23)

Заметим, что на данном этапе (решения финальной задачи) определены функции (см. (4.19), (4.22))

(4.24)

которые будут использоваться затем для определения в (4.11). Итак, всюду в дальнейшем полагаем, что определяется условиями

(4.25)

в случае аддитивной -задачи и условиями

(4.26)

в случае минимаксной -задачи; учитываем при этом, что (см. (4.1), (4.9))

(4.27)

Вернемся к (4.6)–(4.8). Точнее, рассмотрим постановку предваряющей -задачи, оперируя ФС (4.11), (4.12). Итак, при и имеем

(4.28)

где функция конкретизируется посредством (4.25) (мы начинаем обсуждение с аддитивного варианта -задачи). Разумеется (см. (4.7)), значение (4.28) определено при и . При получаем -задачу

(4.29)

которой сопоставляется экстремум

(4.30)

и непустое экстремальное множество

(4.31)

Мы рассматриваем здесь и проблему оптимизации старта в -задаче:

(4.32)

задаче (4.32) сопоставляется полный экстремум -задачи (в аддитивной версии) и экстремальное множество :

(4.33)

(4.34)

Аналогичные конструкции вводим для случая минимаксной постановки. Напомним в связи с этим (4.17), (4.21)–(4.23), получая конструкцию минимаксной -задачи, после чего формируем функцию по правилу (4.26).

Теперь рассмотрим постановку предваряющей -задачи, оперируя ФС (4.11), (4.12). При и имеем

(4.35)

где соответствует (4.26). В силу (4.7) имеем, что при значение (4.35) определено для ; получаем минимаксную задачу

(4.36)

которой сопоставляется экстремум

(4.37)

и непустое экстремальное множество

(4.38)

Посредством (4.37) определена функция экстремума предваряющей задачи в минимаксной постановке. Допуская вариацию старта, приходим к задаче

(4.39)

которой сопоставляется (полный) экстремум и непустое экстремальное множество:

(4.40)

(4.41)

рассматриваем в качестве полного экстремума минимаксной -задачи.

Теперь мы располагаем двумя вариантами основной задачи и двумя вариантами частичных задач (имеются в виду варианты аддитивной и минимаксной постановок). Важную роль играют правила (4.25), (4.26), реализующие связь предваряющей и финальной (частичных) задач как в аддитивном, так и в минимаксном случаях.

Мы вернемся к (3.19), (3.20) и рассмотрим единую логику решения задач (3.32), (3.39), следуя конструкции [11, раздел 2]. Итак, в дальнейшем мы используем приводимый ниже алгоритм на функциональном уровне.

Шаг 1. По правилу (4.1) построить множество возможных точек старта в финальной -задаче.

Шаг 2. Сформировать финальную -задачу как систему ()-задач, где пробегает .

Шаг 3. Найти функцию экстремума -задачи, определенную на множестве (кроме того, находятся слои функции Беллмана).

Шаг 4. На основе функции экстремума финальной -задачи сформировать терминальную компоненту критерия предваряющей -задачи (используется правило (4.25) в аддитивном случае и правило (4.26) в минимаксном).

Шаг 5. Сформировать предваряющую -задачу как систему -задач, где пробегает .

Шаг 6. Найти функцию экстремума предваряющей -задачи (а также слои функции Беллмана), ее полный экстремум и соответствующее экстремальное множество точек старта из .

Шаг 7. Выбрать произвольно и зафиксировать оптимальный старт в предваряющей -задаче и решить ()-задачу, то есть построить оптимальное решение ()-задачи (-задачи со стартом ) в виде у/п маршрут – траектория; зафиксировать на данной траектории терминальное состояние в виде соответствующей у/п и выбрать в виде второго элемента этой у/п.

Шаг 8. Принять в качестве старта в -задаче и найти оптимальное решение ()-задачи в виде у/п маршрут – траектория.

Шаг 9. Склеить найденные оптимальные решения ()-задачи и ()-задачи (раздельно склеиваются маршруты по правилу (3.9) и траектории [11, (4.4), (4.5), после чего дополнить получившуюся у/п точкой для реализации композиционного МП; данный МП будет оптимален в основной -задаче (то есть будет содержаться в или в в зависимости от того, рассматривается аддитивная версия критерия или минимаксная постановка).

Отметим, что в ряде случаев не требуется построение оптимального композиционного МП, а достаточно найти экстремум основной задачи и оптимальный старт. В этой ситуации достаточно выполнить только этапы 1–6, причем в памяти вычислителя не требуется сохранять все слои функции Беллмана (поэтому в 3 и в 6 о них упоминается в скобках). Саму же реализацию процедур ДП в предваряющей и финальной задаче можно осуществлять с перезаписью слоев [22, замечание 2.1], чем достигается некоторая экономия ресурсов памяти. Знание экстремума в классе композиционных МП может быть полезно для оценивания эвристик в задачах большой размерности.

В связи с 1–9 отметим, что наиболее трудными в вычислительном отношении являются этапы 3, 6. Для выполнения данных этапов в [10][11] использовалось широко понимаемое ДП, реализуемое раздельно в - и в -задаче. При этом ограничения предшествования в данных задачах использовались в положительном направлении (в связи с этим напомним [4, § 4.9]).

Рассмотрим некоторые аналоги построений [4, § 4.9], реализуемые универсально в аддитивной и минимаксной постановках. Речь идет о том, чтобы только подготовиться к введению слоев функций Беллмана.

Начнем с обсуждения конструкций для -задачи, определяя оператор вычеркивания (заданий из списка)

(6.1)

посредством следующего правила [4, § 2.2]: при

(6.2)

где . Итак, располагая списком , мы оставляем в нем (6.2) только индексы заданий, не являющиеся получателями для адресных пар, «полностью укладывающихся» в (имеется в виду, что оба элемента соответствующей адресной пары содержатся в ).

Таким образом, множества – элементы семейства

(6.3)

называем существенными списками в ‑задаче. Эти списки ранжируем по мощности: при полагаем . Ясно, что (одноэлементное семейство); семейство также допускает очень простое описание: при :

(6.4)

(семейство всех синглетонов неотправителей). Наконец [10, (6.3)], [22, (8.15)]

(6.5)

Посредством (6.4), (6.5) определена рекуррентная процедура , в которой начальный элемент соответствует , а регулярный шаг определяется посредством (6.5).

Следующий этап – построение слоев пространства позиций (заметим, что позицией здесь называем каждую у/п (х, К), где и ). Проще всего определяются [11, (3.4)] крайние слои:

(6.6)

Рассмотрим построение промежуточных слоев. Итак, сначала при и последовательно создаем множества

,

(6.7)

(в (6.7) реализуется цепочка ). Теперь промежуточные слои определяем условиями

(6.8)

В связи с (6.6), (6.8) напомним, что [6, предложение 4.9] при . Отметим важное свойство [11, (3.7)] построенных слоев:

(6.9)

Аналогичным образом строятся слои в -задаче. Сначала вводим оператор вычеркивания

(6.10)

а именно: при полагаем

(6.11)

где (в (6.10), (6.11) имеем аналогию с (6.1), (6.2)). В виде

(6.12)

реализуется семейство существенных списков -задачи. Ранжируем их по мощности, получая при в виде семейство всех s-элементных существенных списков; тогда и при

(6.13)

(семейство всех синглетонов неотправителей -задачи). Если же , то

(6.14)

B (6.13), (6.14) имеем очевидную аналогию c (6.4), (6.5). Получили рекуррентную процедуру . Переходим к построению слоев пространства позиций: введем множества . Полагая, что

(6.15)

мы вводим кроме того, . Итак, определены крайние слои. Если и , то полагаем

,

(6.16)

(в (6.16) реализуем цепочку ). Тогда

(6.17)

согласно [4, предложению 4.9.3] при . Итак, (6.17) логически «повторяет» (6.8). Подобно (6.9):

(6.18)

В (6.9) и (6.18) мы имеем фактически конкретные способы продвижения в слоях пространства позиций частичных задач.

Напомним некоторые положения [11, раздел 4], касающиеся склеивания частичных маршрутов и траекторий. Используя общие свойства перестановок [14, с. 87], отметим два следствия (3.9): при и

(7.1)

в связи с (7.1) см. (2.1), а также [11, (4.2), (4.3)]. Итак, в (7.1) мы указываем явное описание образов ДИ, содержащихся в при действии на них склеенных маршрутов.

Переходя к вопросу о склеивании траекторий, напомним (4.8); в силу (4.7)

(7.2)

Итак, если выбрано любое ДР ()-задачи, где , то второй элемент у/п, являющийся финишной точкой траектории данного ДР, может использоваться в качестве старта -задачи. Напомним определения и в разделе 4 (множества кортежей в , определенных на ДИ и соответственно). Тогда при и определяем склеенный кортеж следующими условиями:

(7.3)

При этом (см. [14, (4.5)]) справедливо следующее очевидное свойство склеиваемости: если и , то

(7.4)

В связи с [11, (4.6)] дополним (7.4) полезным свойством сужений траекторий, согласованных со склеенными маршрутами: при и

(7.5)

с учетом (7.2) и (7.5) имеем очевидное следствие [11, (4.7)]: при условиях, обеспечивающих (7.5),

(7.6)

Наконец, еще один вариант сужения «совокупных» траекторий указан в [11, (4.8)]: при и и истинна импликация

(7.7)

в (7.7) неявно говорится о сужении траектории на ДИ . Теперь, комбинируя (3.9) и (7.4), мы получаем свойство раздельной склеиваемости ДР: если и , то [11, (4.9)]

(7.8)

Свойство (7.8) играет основную роль в обоснованиях теоретических положений, обеспечивающих композиционную оптимальность алгоритма 1–9 раздела 5. В настоящем исследовании мы совсем кратко коснемся этих положений, придерживаясь «алгоритмического» варианта изложения материала.

Рассмотрим (более простую в логическом отношении) задачу (3.24). Одно из практических применений данной постановки может быть гипотетически связано с задачей авиапожарного патрулирования, когда БПЛА должен по возможности быстрее осуществить обзор лесных массивов с целью оперативного получения информации о возможных возгораниях для того, чтобы направить для тушения последних десантников и, возможно, необходимую технику. Мегаполисы, связанные с лесами, можно рассматривать в качестве дискретизаций последних, причем выполненных так, чтобы при посещении всех «городов» (это точки лесного массива, указанные заранее) мегаполиса с использованием бортовых средств наблюдения можно было бы однозначно ответить на вопрос, есть ли возгорание или нет (ограничимся сейчас такой упрощенной постановкой). Мы полагаем для простоты, что набор лесов выбран таким, что ограничениями ресурсного характера можно пренебречь. Внутренние работы, связанные с посещением каждого лесного массива, оцениваем временем облета всех «городов» мегаполиса, что при постоянной скорости движения может быть сведено к суммарному расстоянию. В результате внутренние работы всякий раз оцениваются значением возникающей метрической задачи коммивояжера. При этом пункт прибытия и пункт отправления из мегаполиса выбираются произвольно, то есть можно полагать, что при .

Разумеется, данная модель является упрощенной, но мы ей ограничимся сейчас и перейдем к рассмотрению общей постановки «аддитивной» задачи (см. (3.24)). Мы имеем при этом в виду, что уже проведена ()-декомпозиция основной задачи, что может быть связано с ощутимой размерностью последней либо с необходимостью первоочередного посещения наиболее пожароопасных районов (например, тех лесных массивов, в которых пожары могут угрожать населенным пунктам).

Итак, при имеем задачу (3.21); допуская возможность оптимизации точки старта , мы приходим к основной задаче (3.24). В интересах решения последней используем частичные задачи (4.18), (4.29) и (4.32). Важную роль здесь играют положения [11, раздел 5]. Так, согласно [11, предложение 2] при имеем равенство экстремумов предваряющей и основной задач со стартом в . Это свойство, в свою очередь, доставляет равенство [14, (5.28)] соответствующих функций экстремума, заданных на ; здесь функция определяется подобно (4.24), а именно

(8.1)

Из данного равенства функций экстремума вытекает, что [11, (5.29)]. Отметим, наконец, равенство экстремальных множеств в [11, (5.30)]. Данные положения, указанные в [11], используем ниже без дополнительных пояснений (ключевую роль в их обосновании играет (4.25)).

Рассмотрим шаг 3 алгоритма раздела 5, используя определения раздела 6 и следуя [11, раздел 6]. Точнее, мы укажем процедуру построения функций

(8.2)

именуемых слоями функции Беллмана -задачи. Итак, определяем условиями

(8.3)

см. (6.15). Если же и функция уже построена, то определяем, учитывая (6.18), по правилу

(8.4)

Посредством (8.3), (8.4) определена рекуррентная процедура

(8.5)

для которой реализует (см. [14, (6.3)]) функцию экстремума финальной задачи по правилу

(8.6)

грубо говоря, (8.5) переводит терминальную функцию в требуемую функцию (4.24). Используя (4.25), получаем терминальную компоненту критерия предваряющей задачи. Теперь нашей целью является построение слоев

(8.7)

функции Беллмана -задачи. Учитывая (6.6) и (8.6), определяем правилом

(8.8)

Далее, если и функция уже построена, то определяем следующим правилом (учитывающим (6.9)):

(8.9)

Получили рекуррентную процедуру

(8.10)

реализует (см. [14, (6.5)]) функцию экстремума предваряющей задачи:

(8.11)

в (8.11) учитываем (6.6). Итак, процедура (8.10) переводит в . Тем самым реализуется шаг 6 нашего алгоритма в «аддитивном» случае; действительно, располагая функцией , мы можем воспользоваться соотношениями (4.33), (4.34).

Далее, учитывая оговоренную ранее связь функций экстремума основной и предваряющей задач, а также соответствующих экстремальных п/м , мы находим и (здесь, разумеется, надо иметь в виду, что множество (4.34) легко находится по известной уже функции ). Подчеркнем, что при нахождении и мы можем использовать в каждой из частичных задач режим построения с перезаписью слоев функций Беллмана [22, замечание 2.1] с целью экономии ресурсов памяти.

Сейчас мы продолжим работу с процедурами (8.5), (8.10), имея конечной целью реализацию шага 9 алгоритма раздела 5. Это предполагает, конечно, предваряющее построение оптимальных решений в частичных задачах, что было отмечено при описании шагов 7, 8. Здесь мы полагаем, что все функции (8.2), (8.7) построены и находятся в нашем распоряжении (точнее, находятся в памяти вычислителя). Зная множество , выбираем произвольно , получая [11, (6.7)] цепочку равенств

(9.1)

где при и в силу (6.9). Вместе с тем (см. раздел 8) имеем по выбору , что и при этом

(9.2)

С учетом (9.1) и (9.2) выбираем и из условия

(9.3)

получая также включения . С учетом этого рассмотрим представление . С учетом (8.9) получаем равенство

(9.4)

где , при и . С учетом (9.4) выбираем и так, что

(9.5)

получая также включение . Из (9.3), (9.5) получаем, что

(9.6)

Полагаем далее, что . Тогда и согласно (9.6)

(9.7)

Далее операции, подобные (9.3) и (9.5), следует продолжать вплоть до исчерпания индексного множества ; в результате будут построены и со свойством

(9.8)

(при N = 2 равенство (9.8) непосредственно следует из (4.25), (4.28), (8.8) и (9.7)). В связи с подробностями в части проверки (9.8) в общем случае см. [23, §7]. Из свойств, отмеченных в разделе 8, легко следует, что . Итак, мы построили полное решение предваряющей задачи на основе ДП.

Приступим к аналогичному построению для финальной задачи, фиксируя

(9.9)

(см. (4.8)). При этом ; см. (9.9) и определения раздела 6. С учетом (8.6) , а потому согласно (8.4)

(9.10)

где при и . С учетом (9.10) выбираем и из условия

(9.11)

причем , где . Теперь мы имеем согласно (8.4) равенство

(9.12)

где при и (см. (6.18)). С учетом (9.12) выбираем и из условия

(9.13)

при этом, конечно, . Полагаем, что ; тогда в силу (9.11) и (9.13) получаем, что

(9.14)

Далее операции, подобные (9.11), (9.13), следует продолжать вплоть до исчерпания , в результате чего будут построены

со следующим со свойством:

(при последнее равенство легко извлекается из (9.14)). Из (4.20) вытекает, что . Таким образом, в нашем построении

(9.15)

(9.16)

С учетом (9.15), (9.16) и [11, (5.24)] получаем равенство , где (см. раздел 8). Кроме того, из (4.20), (4.31), (7.8) и (9.15) следует, что , где и, как следствие, . Получили равенство . Тогда, коль скоро (см. (3.13))

имеем в силу (3.26) окончательное включение

(9.17)

Итак, композиционно оптимальный МП построен посредством склеивания оптимальных ДР в частичных задачах.

Будем рассматривать ниже простейший пример, ориентированный на задачу АПП (см. обсуждение в разделе 8). В качестве будем использовать плоскость: . В качестве точек будем рассматривать аэродромы либо площадки, с которых возможен старт беспилотных авиационных средств (БАС). Мегаполисы определяются в виде конечных п/м лесных массивов, подлежащих мониторингу. Как уже отмечалось, предполагается, что каждый из мегаполисов достаточен с точки зрения возможностей наблюдения бортовыми средствами для однозначного ответа на вопрос, есть ли возгорание в данном лесу или нет. Это обстоятельство определяет специфику внутренних работ: нам следует скорейшим образом посетить все города мегаполиса, то есть, по существу, решить внутреннюю задачу коммивояжера (3K). При этом пункты прибытия и отправления (для данного мегаполиса) могут в простейшем случае выбираться произвольно, что соответствует случаю при . В этом случае при и мы должны решить ЗК, в которой оставшиеся города должны последовательно посещаться. Предполагаем при этом, что размерность каждого мегаполиса достаточно мала; это позволяет решать всякий раз возникающую ЗК за приемлемое время, применяя аппарат на основе ДП. В рассматриваемом здесь модельном примере предполагается, что зависимость ФС от списка заданий отсутствует; значения определяются всякий раз экстремумами соответствующей «внутренней» ЗК. Внешние перемещения оцениваются временами соответствующих перелетов. Впрочем, предполагая, что движение БАС осуществляется с фиксированной скоростью, можно полагать, что ФС определяются евклидовыми расстояниями, что позволяет рассматривать метрическую задачу (оптимизацию суммарного расстояния). Условия предшествования определяются приоритетностью посещения наиболее пожароопасных районов, направлением ветра и другими факторами, действующими в данной местности. В настоящем разделе мы не будем рассматривать композиционные решения, а сосредоточимся на примере задачи (3.32), осложненной, однако, ограничениями предшествования с тем, чтобы проиллюстрировать возможности оптимизации на основе ДП в духе конструкций, восходящих к [4, §4.9]. Это предполагает, конечно, умеренную размерность основной задачи. В рассматриваемом примере размерность является весьма ощутимой, что приводит к большому времени счета.

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

Полагаем в примере, что . При имеем и . Описание мегаполисов не приводится по соображениям объема. Итак, имеем 35 десятиэлементных мегаполисов. Множество таково, что ; оно имеет вид

любая точка может использоваться в качестве стартовой. Значения функций определяются экстремумами внутренних задач коммивояжера, где стоимость перемещений между городами задается евклидовым расстоянием между плоскими векторами. Полагаем, что совокупные условия предшествования в -задаче задаются множеством, содержащим 49 адресных у/п. Оптимальный результат 2894,40356445313. Выбрана (оптимальная) точка старта (120,40). Время счета 29 ч 24 мин 49 с.

Таким образом, построения на основе ДП в духе [4, § 4.9] требуют больших временных затрат. В связи с этим во второй части будет рассмотрен вариант решения аддитивной задачи с выделением, предваряющей и финальной задач, в котором объектом нашего исследования будет композиционный МП (см. также разделы 8, 9).

Применение аппарата ДП как развития подхода [7] позволило к настоящему времени существенно продвинуться в вопросах решения прикладных задач, для которых ранее доминировали эвристики. Такая ситуация имела место, в частности, в случае задач маршрутизации, связанных с листовой резкой. Отметим ряд исследований в этом направлении [24–34]. В то же время в процессе исследования задач маршрутизации важную роль играют фундаментальные исследования [9][31][32][35]. Все это подчеркивает необходимость в построении строгой математической теории, которая дополняла бы эвристические методы, широко используемые при решении практических задач.