ИЗВЕСТИЯ РАИ. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2008, № 3, с. 143-153
СИСТЕМНЫЙ АНАЛИЗ И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
УДК 519.6.
О РЕАЛИЗАЦИИ МЕТОДА ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ В ОБОБЩЕННОЙ ЗАДАЧЕ КУРЬЕРА*
© 2008 г. А. А. Ченцов, А. Г. Ченцов
Екатеринбург, Институт математики и механики УрО РАН Поступила в редакцию 13.03.07 г.
Исследуется задача последовательного обхода множеств с ограничениями в виде условий предшествования, именуемая далее обобщенной задачей курьера, для ее решения используется метод динамического программирования, который реализуется в усеченном варианте с учетом специфики обобщенной задачи курьера. Функция Беллмана определяется не для всех позиций; последнее позволяет экономить память ЭВМ и повышает эффективность процедуры на основе метода динамического программирования. Возможные приложения связаны, в частности, с транспортными задачами (морские и авиационные перевозки с посещением многих пунктов и многовариантностью перемещений из одного пункта в другой).
Введение. Статья посвящена исследованию экстремальной задачи маршрутизации перемещений, осложненной ограничениями. Последние связаны с необходимостью осуществления некоторого числа адресных перемещений от "отправителя" к "получателю". Допускается, однако, посещение по пути от "отправителя" к "получателю" и каких-то других пунктов из общего набора, определяемого постановкой задачи. Итак, адресные перемещения формируют только набор "направлений", в пределах которых можно выбирать варианты с целью минимизации совокупных затрат. В связи с задачей такого рода отметим обстоятельный обзор [1-3], где выделена ([1, с. 7]) задача курьера, в которой присутствуют упомянутые ограничения, именуемые условиями предшествования; см. также [4-6]. Особенность постановки, рассматриваемой в настоящей работе, состоит в том, что пункты, по которым осуществляются перемещения, сами являются множествами, что порождает многовариантность перемещений уже на каждом шаге рассматриваемого процесса. Будем в этой связи использовать термин обобщенной задачи курьера (ОЗК), имея в виду "многозначный аналог" задачи курьера [1].
Исследуем оптимальное решение ОЗК, привлекая нужную версию метода динамического программирования (МДП). В связи с использованием МДП в задачах маршрутизации отметим [7, 8], где рассматривалось решение задачи коммивояжера. В задаче курьера (и, тем более, в ОЗК) возникают новые особенности, обсуждение которых будет проведено позднее. Сейчас отметим только наиболее важную особенность настоящей работы в плане использования МДП. Именно с учетом ограни-
*Работа выполнена при финансовой поддержке РФФИ (гранты < 03-01-00415, 04-01-96093).
чений в форме условий предшествования будет осуществляться построение не всей функции Беллмана (в статье конструируются слои этой функции), а некоторого ее сужения, что позволяет организовать более экономную процедуру вычислений и последующего построения оптимального решения в виде пары маршрут-трасса; при этом маршрут отождествляется с перестановкой индексов, а трасса - с набором точек на множествах, подлежащих посещению.
Говоря о гипотетических применениях развиваемого в статье подхода, можно отметить, в частности, задачу о посещении островов архипелага с целью транспортировки грузов, имея в виду транспортировку грузов не только из начального пункта (базы), но и перемещения грузов между некоторыми из островов, в большей степени связанными в смысле хозяйственной деятельности их населения. Для таких выделенных островов по прибытии транспортного средства в точку отправления осуществляется погрузка с последующим перемещением в точку прибытия. Данное перемещение делается "по пути"; допускается, если это выгодно с точки зрения эффективности решения полной задачи, посещение и других островов, уже без соблюдения для последних какой-то обязательной очередности. Посещение таких "обычных" островов может иметь своей целью доставку на них грузов только с базы, а поэтому и посещать их можно когда угодно. Наконец, предполагаем в рамках данной модели, что посещение каждого пункта сводится к прибытию в любую точку соответствующего острова, т.е. что дальнейшая доставка груза - дело самих жителей острова. Данная интерпретация (задача о посещении островов архипелага) вполне соответствует рассматриваемой ниже ОЗК. Условимся также о том, что кри-
терий, используемый в ОЗК, является аддитивным, т.е. затраты на перемещения суммируются.
Итак, рассмотрим ниже задачу последовательного обхода множеств (это и есть острова) в условиях ограничений на выбор маршрута; наша цель состоит в построении оптимального решения в виде пары маршрут-трасса с критерием, определяемым в виде суммы затрат на элементарные перемещения.
1. Постановка задачи. Фиксируем непустое множество X произвольной природы, именуя его пространством состояний. В этом пространстве задано конечное число подмножеств (п/м) X, подлежащих посещению из фиксированного начального состояния х0 е X. Процесс посещения множеств осложняется условиями предшествования, типичными для задачи курьера [1].
Всюду в дальнейшем Л А {1; 2; ...}; при p е Л
и q е Л, как обычно, p, q А {i е Л|(р < i) & (i < q)};
допускаем возможность того, что p, q = 0 (при q < < p). Во избежание двусмысленности в традиционных обозначениях постулируем, что элементы Л не являются множествами. Для обозначения промежутков вещественной прямой [ используем только квадратные скобки. Условимся о некоторых общих соглашениях теоретико-множественного характера. Если х - объект, то {х} - одноэлементное множество, содержащее х; если же х и y - два объекта, то {х; y} А {х} u {y} (здесь и ниже А - равенство по определению). Тем самым определена неупорядоченная пара (двоеточие). Как обычно, (х, y) А {{х}; {х; y}} - упорядоченная пара [9, с. 67] объектов х и y. Иногда будем обозначать упорядоченную пару одной буквой; если z -упорядоченная пара, то через pr1(z) и pr2(z) обозначаем ее компоненты: pr1(z) и pr2(z) - суть такие объекты (определяемые [9, с. 67] единственным образом), что z = (pr1(z); pr2(z)). Следуем традиционному правилу экономии скобок при обозначении значений функции двух переменных: если A и B - непустые множества, C - непустое п/м декартова произведения A х B, f C —► [, х е A, y е B и при этом (х, y) е C, то Д(х, y) А Д(х, y)). Если S -множество, то через Fin(S) обозначаем семейство всех непустых конечных п/м множества S; (FIN) [S] А Fin(S) u {0 }.
Будем следовать постановке и конструкции решения ОЗК, приведенным в [10, 11]. Напомним, что множество X, X Ф 0 фиксировано. Пусть, кроме того, х0 е X, N е Л, N > 2, и
( И,; ). е — : hN — Fin( X ) (1.1)
- кортеж целевых множеств; эти множества подлежат посещению из начального состояния (базы) х0 посредством выбора системы перемещений
(Хо = х0) — (Х1 е Ма(1)) 2)
*" ••• " (ХЫ е Ма(¿V)),
где а - перестановка в 1, V. Выбор а также находится в нашем распоряжении. Имеются, однако, ограничения, которым должна удовлетворять перестановка а. Что касается х0 и кортежа (1.1), используемого в (1.2), то постулируем как и в ([10, с. 181]), что
Х0 е им) & (м.ПМ1 = 0
V/ е V] е г}).
Посредством (1.1) и (1.3) определены параметры задачи. Рассмотрим систему ограничений; пусть
К е (ИЩх ; (1.4)
интерпретируем (1.4) как заданное множество индексных пар "отправитель-получатель". Будем полагать всюду в дальнейшем выполненным следующее условие.
Условие 1. VK е нп(К) Зг е К: ргх(г) ф рг2(г) Vz е К. Через Р обозначаем множество всех перестановок в 1, V, т.е. множество всех биекций
1, V на себя. Если X е Р, то X-1 - перестановка из Р (т.е. X-1 е Р), обратная к X;
Х(Х-1 (к)) = X-1 (Х(к)) = к Vk е . (1.5)
В терминах (1.4), (1.5) определяем в согласии с [10, 11] множество допустимых перестановок, именуемых далее маршрутами
А а {ае Р|а-1(рг1(г))<
(1.6)
< а-1 (рг2(г)) Vг е К }.
Ограничение, используемое в (1.6), имеет следующий содержательный смысл: перестановка (маршрут) а е Р допустима, если при всяком выборе пары г = (рГх(г), рг2(г)) е К для индексов г е 1, V иу е е 1, V, обладающих свойствами
(а( г) = рг1 (г)) & (а( у) = рг2 (г)),
выполняется неравенство г < у. Иными словами, множество с индексом ргх(г) должно посещаться раньше, чем множество с индексом рг2(г). Данные ограничения именуем условиями предшествования.
Если к е Я, то через Хк обозначаем множество поненты совокупного решения удовлетворяет усло-всех кортежей в X длины к; каждый такой кортеж виям предшествования. Итак, пусть
(XI). е — - отображение 1, к в X. Если а е А, то
8 А X..).е ^^) е АхХА
ПМа(.) = {(X.).. е е Х'
(1.11)
1 = 1
(1.7)
XI е Ма() V; е 1, N }
( ^) . е ^ е
ПМ
МО
1 = 1
есть множество всех возможных (при выборе а) тогда 8, 8 с 8о, есть допустимое множество следу-трасс. Полагаем в связи с (1.7), что в нашем рас- ющей (°сн°вн°й) задачи
поряжении находится выбор любой пары (а, (X..)Iе ^), где а е А, а (х1).е ^ - трасса из
W(г) —-ш1п, г е 8.
(1.12)
мно-
Решение (1.12), включая нахождение экстремума и оптимальной пары маршрут-трасса, составляет
рут-трасса. Итак, решения суть пары маршрут- цель настоящей Работы.
2. Метод динамического программирования: общие конструкции. При решении задачи (1.12) используем вариант МДП [10, 11], предусматривающий редукцию задачи в духе [12, 13]. Совсем Отображения (1.8) используем для оценивания цепо- кратко рассмотрим эту редукцию, отсылая к [10, чек перемещений (1.2), получая при этом критерий 11] за подробными сведениями. 4<грез Я обозна-качества. Удобно, однако, ввести для целей агрегирования "индивидуальных" затрат отображение
жества (1.7). Именуем (а, (X.). е ^) парой маршрут-трасса. Итак, решения суть пары марш трасса. Фиксируем следующие отображения:
с: X х X — [0,~[, f: X —- [ 0,~[. (1.8)
XN—- [0,~[ по следующему правилу: V(X.). е ^
®((X.);е Тм) А с(X0, X!) +
е XN
^ -1
+
X с (^ X + 1)
V; = 1
+ f ( XN ).
(1.9)
Множество (1.7) определено для всех перестановок а е Р; на непустом множестве
чаем семейство всех непустых п/м 1, N; Я = = Ип(). Тогда N А Я и {0 } = (БШ)[П^]. Если К е N то |К|, |К| е 1, N, - количество элементов множества К, а (Ы)[К], К е
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.