ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2010, № 4, с. 63-71
МЕТОДЫ ОПТИМИЗАЦИИ =
УДК 519.6
ОБ ОДНОМ ПОДХОДЕ К РЕШЕНИЮ ЗАДАЧИ МАРШРУТИЗАЦИИ ПЕРЕМЕЩЕНИЙ С НЕСКОЛЬКИМИ УЧАСТНИКАМИ*
© 2010 г. Е. Е. Иванко, А. Г. Ченцов, П. А. Ченцов
Екатеринбург, Институт математики и механики УрО РАН Поступила в редакцию 29.12.09 г., после доработки 15.02.10 г.
Рассматривается задача о посещении конечной системы множеств несколькими участниками. Предлагаемый алгоритм решения комплексной задачи базируется на комбинации жадного алгоритма распределения заданий и метода динамического программирования в задачах маршрутизации каждого из участников. Построена программа для ПЭВМ и проведен обширный вычислительный эксперимент.
Введение. Задачи маршрутизации перемещений и распределения заданий составляют важное направление в дискретной оптимизации и имеют многочисленные и важные приложения, касающиеся, в частности, технологических процессов, транспортных задач, задач распределения вычислительных ресурсов. С точки зрения приложений естественны в ряде случаев постановки, в которых допускается сочетание элементов последовательного решения (маршрутизации) и распределения в группы, реализуемого тем или иным образом. Вышеупомянутые задачи маршрутизации и распределения традиционно относятся к числу труднорешаемых; их прототипами являются известные МР-полные задачи "коммивояжер" и "разбиение" [1]. Возникающие при их решении трудности вычислительного характера заставляют прибегать к построению приближенных методов. В частности, используются жадные алгоритмы [2], обычно обладающие хорошим быстродействием, хотя и проигрывающие в ряде случаев в качестве; так, например, если иметь в виду хорошо известную задачу коммивояжера (ЗК), то часто используется алгоритм, построенный по принципу "иди в ближайшую точку". Общие принципы оптимизации можно в свою очередь связать с методом динамического программирования (МДП); это касается и задачи маршрутизации, и задачи распределения заданий. Конструкция решения на основе МДП для задачи, включающей и маршрутизацию, и распределение заданий, приведена, в частности, в [3, 4]. Отметим, что в [3] в качестве задачи маршрутизации использовалась так называемая обобщенная ЗК (в терминологии [5] ЗК с выбором), когда "города" заменяются "мегаполисами". Тем самым реализуется многозначная версия ЗК [5]. Вместе с тем трудности вычисле-
* Работа выполнена в рамках программы Президиума РАН "Математическая теория управления" и при финансовой поддержке РФФИ (гранты № 09-01-00436; 08-08-00981).
ний делают "сквозную" версию МДП неприемлемой для целей решения задач уже сравнительно небольшой размерности, подобных задаче нескольких коммивояжеров. В частности, для успешной работы "распределительного блока" требуется решение очень большого числа трудоемких маршрутных задач (имеется в виду насчи-тывание функций стоимости, которые затем применяются в варианте МДП, ориентированном на оптимизацию разбиений пространства заданий).
В этой связи в настоящей работе предпринимается попытка совместить логику жадного алгоритма в задаче распределения в группы и оптимального алгоритма на основе МДП в задачах маршрутизации. Особенностью является "не слишком частое" обращение к последним. Взаимодействие жадного и точного алгоритмов регулируется допусками, которые, в принципе, можно изменять в итерационном режиме. Представляется, что предлагаемый комбинированный подход может быть полезен при проведении при-кидочных расчетов, касающихся процесса распределения работ с определенной маршрутной адаптацией. Как и в [3], рассматривается многозначная версия задачи нескольких коммивояжеров с использованием естественных декомпозиций, приводящих к ситуациям, в которых возможно применение аппарата МДП при решении обобщенной ЗК (с одним участником) умеренной размерности.
1. Постановка задачи. Пусть X — непустое множество, в котором выделена точка х0 е X и непустые множества М1, ..., Мм, где М\ с X, N — натуральное число, N > 2. Полагаем, что х0 — точка старта, именуемая также базой, а М1, ..., — целевые множества, подлежащие посещению одним из п участников, стартующих из точки х0; здесь п — натуральное число, п > 2. Участникам следует распределить целевые множества между собой, упорядочить (каждому) процесс посеще-
ния выбранных множеств и выбрать трассу посещений. Предполагается заданной функция
с: Xх Х^ [0,да[, (1.1)
характеризующая затраты на перемещения от одной точки множества X к другой. Полагаем, что у каждого из участников затраты упомянутого типа агрегируются аддитивно. Максимум (по всем участникам) суммарных затрат подлежит минимизации. В том частном случае, когда с (1.1) характеризует время перемещения из точки в точку, данная задача имеет смысл поиска максимального быстродействия в процессе посещения всех множеств. Задачами такого рода рассматриваются в работах [3; 4, ч. 5]. В то же время существенную роль играют задачи маршрутизации с одним участником, восходящие к известной ЗК [5—7]. В связи с использованием МДП отметим [8, 9] (важную роль в решении ЗК играет метод ветвей и границ [10; 11, гл. 7]). В настоящей работе применено естественное развитие процедуры МДП [8, 9], соответствующее публикациям [3, 12—17].
Наконец, отметим некоторые задачи, связанные с обслуживанием атомных электростанций (АЭС); см., в частности, [18], где представлена маршрутная компонента вышеупомянутой задачи, соответствующая процессу оптимизации до-зовой нагрузки ремонтного персонала АЭС. Представляется, что постановка, подобная [18], но допускающая участие нескольких исполнителей, может оказаться полезной в приложениях упомянутого типа. Отметим, что в [3] построена "сквозная" версия МДП, доставляющая глобальный экстремум; подобные процедуры для задач с ограничениями в виде кластеров, не допускающих расщепления, исследовались в [4, ч. 5; 19, 20]). Отметим также приближенные алгоритмы оптимизации разбиений пространства заданий в [21] для задач с функциями затрат типа суммы.
2. Математическая модель. Пусть N = {1, 2, ...};
при к е N и I е N обозначаем, как обычно, через
к, I множество всех / е N, таких, что (к < /)&(/ < I). Полагаем, что М есть непустое конечное подмножество X для любого / е 1, N. Для всякого непустого конечного множества К введем |К| — количество элементов К, |К| е N; полагаем также, что
|0| = 0. Фиксируем функцию (1.1) с: Xх Х^ [0, да[,
значения которой будут использоваться для оценки затрат на перемещение из одной точки множества Xв другую. Полагаем, что V/ е 1, N V/ е 1, N (/ ф/) ^ (М п М/ = 0); пусть, кроме того, х0 £ Мк
Vk е 1, N. В этих условиях будем рассматривать при произвольном выборе множества К, К ф 0,
К с 1, N, всевозможные варианты перемещений
(х0 = /)—-(Х1 е Ма(1)
-«- (хт е Ма(т)) ,
где т = |К| и а — произвольная биекция "отрезка"
1, т на К. Систему перемещений (2.1) оцениваем посредством с, получая
т
£с(х,.-1, х,) е [0, да[. (2.2)
I = 1
В дальнейшем исполнителя, реализующего (2.1) и оцениваемого (при осуществлении (2.1)) суммой (2.2), условимся называть коммивояжером, что несколько отлично от традиционного толкования, но позволяет сохранить нужную смысловую нагрузку. Допустим, что таких коммивояжеров у нас несколько, все они стартуют для простоты из точки х0; пусть они распределяют между
собой все множества М, / е 1, N, что сводится к
разбиению "отрезка" 1, N. Тогда схема (2.1), (2.2) реализуется для каждого из коммивояжеров, а наибольшая из сумм (2.2) определяет качество нашего решения, включающего распределение заданий и маршрутизацию. Можно допустить, что каким-то коммивояжерам заданий не достанется. Затраты этих коммивояжеров оцениваются нулем.
Введем некоторые обозначения и определения, нужные в дальнейшем. Через Ш выделим семейство всех непустых подмножеств 1, N. Обозначим буквой ^ семейство всех подмножеств
; ^ = Ш и {0}. Если К е Ш, то (Ь/)[К] задает множество всех биекций
а: (2.3)
Напомним, что при всяком выборе а (2.3)
К
ПМа(0 (2.4)
, = 1
— множество всех кортежей (х)). е ^ : 1, К —" X,
для каждого из которых X/ е Ма/ V/ е 1, |К| . Разумеется, (2.4) есть непустое конечное множество, которое мы достраиваем точкой из X, выбираемой в качестве начальной, получая отображения из
0, К в X, подобные в идейном отношении определяемым в [4, с. 37]. Итак, точке х е X, множеству К е Ш и биекции а е (Ь/)[К] сопоставляем множество Ж [х; К; а] всех отображений
(X), е 0ЛК: ОТ^ (2.5)
для каждого из которых х0 = х0, а (х,-). е ^ — элемент множества (2.4). Тогда при х е X и К е Ш полагаем
= min
а е (bi)[K]
min
(x) — е £[x; K; а]
v(x, K) =
f m
^ c(Xi- 1, Xi)
где m = jKj. Кроме того, считаем, что
(2.6) [0, ю[,
(2.7)
ф, 0) = 0 Ух е X.
Посредством (2.6) и (2.7) реализуется функция на X х Ж, которую будем обозначать через V. В действительности же для построения решения достаточно использовать сужение этой функции. В этой связи заметим, что без ограничения общности можно полагать, что
X = {x0 }u( uMi).
i = 1
(2.8)
Соглашение (2.8) полагаем в дальнейшем выполненным (см. также в этой связи (2.1)). Введем
Жк = {К е к = К } Ук е 0^.
Отметим, что = {1, N} (одноэлементное множество). Если к е 0, N, то
А. =
(x, K): K 6 Тск, X 6 X\(u м) 1. (2.9)
i е K J
v(X, K) , (X, K) 6 Dm,
m е 0, N
достаточного для получения оптимального решения маршрутной задачи. В самом деле в (2.7) указан тривиальный способ определения массива
значений v(х, К), (х, К) е Б0. Пусть при т е 0, N уже построен массив значений
v(x, К), (х, К) е А; (2.13)
& е 0, т
если при этом т = N, то массив значений (2.12) сформирован. Если же т < N, то т + 1 е 1, Nи
при (х, К) е Бт + 1 находим v(х, К) по правилу (2.11), используя то обстоятельство, что при к е К непременно К\{к} е Жт, а потому для у е Мк имеем, согласно (2.9),
(у, К\{к}) е Вт. (2.14)
В самом деле, справедливо равенство
Мк п( и м) = 0,
I е К\{к}
а тогда с очевидностью выполняется включение у е Х\( и М) ,
¡е К\{к}
из которого, в силу (2.9), вытекает (2.14). Таким образом, насчитывается массив значений ^х, К), (х, К) е Бт + 1. Этим (поскольку уже существует массив значений
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.