Некоторые задачи маршрутизации и распределения заданий: метод динамического программирования и приближенные алгоритмы тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

РОССИЙСКАЯ АКАДЕМИЯ НАУК УРАЛЬСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ И МЕХАНИКИ

На правах рукописи

ЧЕНЦОВ Павел Александрович

НЕКОТОРЫЕ ЗАДАЧИ МАРШРУТИЗАЦИИ И РАСПРЕДЕЛЕНИЯ ЗАДАНИЙ: МЕТОД ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ И ПРИБЛИЖЕННЫЕ АЛГОРИТМЫ

01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Екатеринбург — 2004

Работа выполнена в Институте математики и механики Уральского отделения РАН.

Научный руководитель — доктор физико-математических наук,

профессор Э.Г. Альбрехт Официальные оппоненты - член-корреспондент РАН, доктор

физико-математических наук, А.В. Кряжимский,

кандидат физико-математических наук, старший научный сотрудник В.Б. Костоусов Ведущая организация - Челябинский государственный

университет

Защита состоится " ^ " се^-^с&^^-А-_ 2004 года

s f О О

в "._~> 5 " часов на заседании диссертационного совета К 004.000.01

по защите диссертаций на соискание ученой степени кандидата наук в Институте математики и механики Уральского отделения РАН по адресу: 620219, г. Екатеринбург, ул. Софьи Ковалевской 16.

С диссертацией можно ознакомиться в научной библиотеке Института математики и механики УрО РАН.

Автореферат разослан " " октября 2004 г.

Ученый секретарь диссертационного совета кандидат физ.-мат. наук,

старший научный сотрудник В.Д. Скарин

ZOOM 1BG

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Диссертационная работа посвящена исследованию экстремальных задач, имеющих смысл распределения и упорядочения заданий.

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

Отметим, например, работу4, посвященную построению алгоритма кластеризации, результат применения которого представляется последовательностью, в которой исключаются заведомо неоптимальные разбиения, задачу реализации разбиений множеств булевых наборов асимптотически оптимальными схемами5, задачу распределения ресурсов в АСУ реального

6

времени с элементами неопределенности , исследование асимптотических представлений для характеристик случайных разбиений конечного множества на "блоки"'. Известны также работы, связанные со стохастическими

1 Гирлих, Э. Алгоритм для задачи распределения работ, выполняемых в реальном времени при наличии дополнительной информации / Э. Гирлих, М.М.Ковалев, В.М.Котов // Дискрет, математика. -2003.- Т. 15, № 5- С.133-140.

2Graham, R.L. Bounds for certain multiprocessor anomalies / R.L. Graham // SIAM J. Appl. Math.— 1969.- Vol.17.- P.263-269.

3 Кропанов, ВА Равномерное назначение работ минимальной стоимости / В.А. Кропанов, B.C. Рублев // Дискрет. математика.— 2001.— Т.13, № 4 — С.144-157.

4Двоенко, С.Д. Иерархический дивизимный алгоритм кластеризации / С.Д. Двоенко // Автоматика и телемеханика.— 1999.- № 4.— С.117-124.

3 Вихлянцев, ИА. О реализации разбиений множеств схемами из функциональных элементов / И.А. Вихлянцев // Дискрет, математика.— 1994.— Т.6, № 3.— С.61-72.

6 Фуругян, М.Г. Решение одной задачи распределения ресурсов в АСУ реального времени при наличии неопределенных факторов / М.Г. Фуругян // Автоматика и телемеханика.— 2002.— №11,— С.167-171.

7 Тимашев, А.Н. Случайные разбиения множеств с известным числов блоков / А.Н. Тимашев // Дискретная математика.— 2003.— Т.15, № 2.- С.138-148. I НАЦИОНАЛЬНА]!I

3 1 КИМ ПОТЕКА 1

С 0$

постановками задач о размещении .

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

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

8 Колчин, В.Ф. Случайные размещения / В.Ф. Колчин, Б.А. Севастьянов, В.П. Чистяков. - М.: Наука, 1976- 224 с.

9 Меламед, И.И. Задача коммивояжера. Вопросы теории / И.И. Меламед, С.И. Сергеев, И.Х. Сигал // Автоматика и телемеханика.— 1989.— № 9.— С.3-34; Задача коммивояжера. Точные алгоритмы. -№ 10.— С.3-29; Задача коммивояжера. Приближенные алгоритмы.— № П.~ С.3-26.

дачи, предлагается решать т.н. задачу курьера10111213. В данном случае под задачей курьера понимается незамкнутая задача коммивояжера с заданным набором специальных пар городов, относительно которых сказано, что каждый первый город пары должен быть пройден ранее второго (причем неважно, есть ли между ними другие города или нет). Такая задача может возникать, например, при доставке корреспонденции в фиксированной системе городов, при построении маршрутов различных транспортных средств, перевозящих грузы или пассажиров (например, при построении маршрутов кораблей или грузовиков, для которых зафиксирован набор грузов, порты или города их расположения и назначения). На базе приведенной в работе конструкции решения задачи коммивояжера с ограничениями можно, как показано в диссертации, строить алгоритмы (как точные, так и приближенные) для решения задачи курьера. Последняя допускает естественное развитие до задачи последовательного обхода множеств, осложненной условиями предшествования. В этой связи отметим работы, посвященные решению упомянутой задачи обхода множеств без такого рода ограничений14,15,16,1,,1|!, в которых приводятся модификации метода динамического программирования для задачи коммивояжера, предложенного Р.Беллманом19, М.Хелдом и Р.М.Карпом20. С данными исследования-

10 Меламед, И.И. Эвристический алгоритм решения обобщенной задачи развозки / И.И. Мсламед, Ю.М. Плотинский // Автоматика и телемеханика.— 1979.— №12.— С.167-172.

11 Bodin, L. Classification in vehicle routing and scheduling / L.Bodin, B.Golden // Networks.— 1981.— Vol.11, № 2- P.97-108.

12 Kalantari, B. An algorithms for the traveling salesman problem with pickup and delivery customers / B. Kalantari, A.V. Hill, S.R. Arora // Eur. J. Oper. Res.- 1985- Vol.22, № 3- P.377-386.

13Psaraftis, H.N. K-interchange procedures for local search in a precedence-constrained routing problem / H.N. Psaraftis // Eur. J. Oper. Res.- 1983.- Vol.13, № 4- P.391-402.

14 Коротаева, Л.Н. К вопросу о маршрутизации соединений / Л.Н. Коротаева, М.П. Трухин, А.Г. Ченцов // Автоматика и телемеханика.— 1997.— №12.— С.175-192.

15 Коротаева, Л.Н. Об одной задаче о назначениях / Л.Н. Коротаева, Э.М. Назаров, А.Г. Ченцов // Журн. вычисл. математики и мат. физики.— 1993.— Т.ЗЗ, № 4.— С.483-494.

16 Коротаева, Л.Н. Об одной модификации метода динамического программирования в задаче последовательного сближения / Л.Н.Коротаева, А.Н. Сесекин, А.Г.Ченцов // Журн. вычисл. математики и мат. физики.- 1989.- Т.29, № 8.- С.1107-1113.

17 Коротаева, Л.Н. Об одном обобщении задачи коммивояжера "на узкие места"/ Л.Н. Коротаева, А.Г. Ченцов // Журн. вычисл. математики и мат. физики.— 1995.— Т.35, № 7.- С.1067-1076.

18 Ченцов, А.А О решении задачи маршрутной оптимизации методом динамического программирования / А.А. Ченцов, А.Г. Ченцов // Изв. РАН. Теория и системы упр.- 1999.- № 3.— С.76-87.

19 Беллман, Р. Применение динамического программирования к задаче о коммивояжере / Р. Беллман // Кибернетический сборник.- М.: Мир, 1964- Т.9.- С.219-228.

20 Хелд, М. Применение динамического программирования к задачам упорядочения / М. Хелд, P.M. Карп // Кибернет. сб.- М.:Мир, 1964- Т.9.- С.202-218.

5

ми можно, в свою очередь, связать работы, посвященные решению задач последовательного управления2 1,22,23 , включая игровые постановки24,25,26 . Упомянутые работы лежат в русле исследований школы Н.Н.Красовского, используют элементы теории принципа максимума Л.С.Понтрягипа, двойственность линейных задач управления и выпуклого программирования, установленную Н.Н.Красовским27; в этой связи отметим также исследования А.Б.Куржапского, Ю.С.Осипова, А.И.Субботина. Отметим работу28, в которой для решения задачи последовательного обхода множеств использовались методы теории приближения функций.

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

Цель работы состоит в следующием:

1. Построение методов решения общей задачи оптимизации разбиений в условиях неточных вычислений.

2. Построение эффективных алгоритмов (точных и приближенных) решения частных задач распределения в группы.

3. Построение оценок экстремума.

4. Анализ зависимости времени счета алгоритмов от размерности и характера выборки заданий и количества групп.

5. Построение точного метода решения незамкнутой задачи коммивоя-

21 Бердышев, Ю.И. О некоторых задачах последовательной оптимизации управляемых систем / Ю И. Бердышев, А.Г. Ченцов.— Свердловск, 1982.- 99 с- Деп. в ВИНИТИ 05.01.83, № 109-83Деп.

24 Бердышев, Ю.И. Оптимизация взвешенного критерия в одной задаче управления / Ю.И. Бердышев, А.Г.Ченцов // Кибернетика.— 1986.— №2.— С.59-87.

23 Бердышев, Ю.И. Оптимизация функционала на классе ломаных / Ю.И. Бердышев, А.Г. Ченцов // Некоторые вопр. оптимизации разрывных функций.— Свердловск, 1984.— С.29-42.

24 Красовский, Н.Н. Задача конфликтного управления с наследственной информацией / Н.Н.Красовский, Н.Ю. Лукоянов // Прикл. математика и механика.— 1996.— Т.60, № 6.— С.885-900.

25 Лукоянов, Н.Ю. К вопросу вычисления цены дифференциальной игры для позиционного функционала / Н.Ю. Лукоянов // Прикл. математика и механика.— 1998.- Т.62, № 4.- С.586-597.

26 Krasovskii, A.N. Control under lack of information / A.N. Krasovskii, N.N. Krasovskii.— Berlin etc.: Birkhauser, 1995-322 p.

27 Красовский, Н.Н. Теория управления движением / Н.Н. Красовский. — М.: Наука, 1968.— 476 с.

28 Бердышев, В.И. О наилучшей траектории, соединяющей упорядоченный набор множеств / В И. Бердышев, В.П. Кондратьев.- Свердловск: ИММ УНЦ АН СССР, 1986.- 85 с.

6

жера с ограничениями на основе метода динамического программирования и процедуры решения задачи курьера на его основе.

6. Построение приближенных методов решения незамкнутой задачи коммивояжера с ограничениями и задачи курьера.

8. Реализация методов решения рассматриваемых задач распределения заданий и маршрутизации перемещений в виде программ для ЭВМ.

Методы исследования. Применяются методы теории экстремальных задач и, в частности, метод динамического программирования, а также элементы математического моделирования.

Научная новизна. 1. Построен метод динамического программирования для задачи оптимизации измеримого разбиения пространства, оснащенного алгеброй множеств, в условиях неточных вычислений.

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

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

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

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

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

29 Плотинский, Ю.М. Общая задача развозки / Ю.М. Плотинский // Автоматика и телемеханика.— 1973-№ 6-С. 100-104.

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

Апробация работы.

Результаты диссертации докладывались на второй международной научно-практической конференции Регионального Уральского отделения Академии инженерных наук РФ "На передовых рубежах науки и инженерного творчества" (Екатеринбург, 2000), региональной конференции Управления по делам ГОЧС г. Екатеринбурга "Совершенствование защиты населения и территорий от чрезвычайных ситуаций природного и техногенного характера в условиях Уральского региона. Особенности, проблемы, пути решения" (Екатеринбург, 1998), конференциях молодых научных сотрудников и аспирантов ИММ УрО РАН (2001, 2002, 2003), общеинститутском семинаре ИММ УрО РАН по параллельным вычислениям, семинарах отдела управляемых систем ИММ УрО РАН, кафедры вычислительной техники физико-технического факультета УГТУ-УПИ.

Публикации. По теме диссертации опубликовано 11 работ, список которых приводится в конце автореферата.

Структура и объем работы. Диссертация состоит из введения и двух глав, разбитых на 10 параграфов. Объем диссертации составляет 147 страниц, набранных в текстовом редакторе Latex. Библиография состоит из 78 наименований.

СОДЕРЖАНИЕ РАБОТЫ

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

Первая глава состоит из 5 параграфов и посвящена задаче распределения заданий между участниками. Кратко эту задачу можно интерпретировать следующим образом: имеется набор заданий и некоторое фиксированное количество участников; требуется "раздать" все задания участникам так, чтобы каждое попало только к одному участнику и при этом некоторый критерий принимал минимальное значение.

Во втором параграфе рассматривается более общая постановка. Задано непустое множество Е, оснащенное алгеброй Z подмножеств Е : (Е, Z) есть

измеримое пространство с алгеброй множеств. Фиксируем п € N,n > 2; i £ 1, П — номера участников. Для L £ Z и ш £ N полагаем, что Дт(Ь, Z) есть множество всех кортежей (разбиений)

для которых выполняются свойства:

2) Vp e'fe V9 € Мй\ Ы : = 0-

Пусть (по условиям задачи} сЬикстован набор

Т\ : Z —v [0, оо[,..., Тп : Z —> [0, оо[,

на базе которого формулируется следующая общая задача:

вир({ад): I £ М}) Ы, (¿О.ем 6 2).

Отметим, что в рамках этой постановки могут рассматриваться и задачи с бесконечным множеством Е. Решать приведенную общую задачу предлагается методом динамического программирования. Кроме того, предполагается, что при вычислении слоев функции Беллмана могут возникать ошибки. Для реализации такс™ ™А™ "одятся операторы

Лщ ■ Р -> Р,

где Р — множество всех функций из Z в [0,00[, по следующему правилу: при/бЖиЬб^

М№) = ^ *ир({/(Л);ГЯ1+1(Ь\Л)});

здесь ш £ 1,П- 1. Показано, что функция Беллмана определяется процедурой v1 = Т1; Ут £ 1,71 — 1 : уш +1 = Лш(уш). Здесь Ук,к £ 1,П, слои этой функции, определяемые экстремумами задач о разбиении подмножеств соответствующего порядка.

Введем далее огрубленные варианты действия операторов А1,...,Ап1. Пусть и кортеж удовлетворяет

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

(и>1 = 71)&{Ут £ 1, и — 1 VI £ 2 : |«;те+1(£) - Ат{ют){Ь)\ < €т).

В работе установлено, что для таких функций w1, непременно

Уг 6 УЬ 6 2 : К(Ь) - уг{Ь)\ < £

Пусть V — истинная функция Беллмаиа, а w — какая-либо ее модель, имеющая своими слоями ...^п, и при этом известно, что

Данная модель может быть построена, например, в рамках вышеупомянутого сценария с огрублениями операторов А1,..., Ап1.

Пусть далее разбиение построено с точностью, определяемой на каждом шаге соответствующим элементом кортежа

это означает, что для 1,п - 1 и Ь £ Z ячейка конструируемого разбиения выбирается из множества

£т{шт, Ь,ат) = {Кег\ Ас Ь, зир({и;т(£ \ Л);

В этом случае для полученного, посредством приведенной в работе процедуры на основе метода динамического программирования, разбиения справедлива оценка

вир({71(Ц): к € М» < V + £ о, + 2 ^и;,;

здесь V = И„(Е) — значение задачи.

В третьем параграфе рассматривается более частная постановка — задача распределения индексированного конечного множества заданий в сумму интервалов натурального ряда. Пусть задано число Ы, N > 2, г € 1, N — номера заданий. Как и ранее, число п, п > 2, обозначает количество участников, 1, п — номера участников. Через $ = {р, д '.р £ 1, ТУ, д £

1, ЛТ} будем обозначать семейство всех промежутков N содержащихся в (включая пустой промежуток). Участники ] 6 1,71 должны распределить задания из в промежутки где (»' — Ь+1> Ь = 0, = N. Через Д„(ЛГ) будем обозначать множество всех разбиений в сумму п промежутков из вышеупомянутого типа.

По условию задачи задан набор следующих функций множеств Т1: ,7 -> [0,оо[,...,Т„ : 3 -* [0,оо[.

Рассматривяемяя ъалача имеет ишт:

sup({Ti(A): г € 1~п}) -

min- 6 Д„(ЛГ).

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

Через N будем обозначать семейство всех подмножеств l,N, а через An(l,iV) — множество всех разбиений множества 1,N в сумму п подмножеств. Заметим, что Дп(1,./У) есть множество An(E,Z) в условиях, когда E=l, N, a Z есть алгебра всех подмножеств множества 1, N.

Множество заданий К € N \ {0} оценивается следующим образом: Т*(К) = max и;,- - minWj,

где W{ G R,t £ 1,И, — некоторые числовые характеристики заданий. При этом = 0 по определению. В работе доказано, что задача

эквивалентна приведенной выше задаче о разбиении в сумму интервалов натурального ряда. Это устанавливается посредством предварительной перенумерации wt в порядке возрастания и при выборе затем функций критерия следующими: Т1 = Т2 = ... = Тп определяются условиями 7/(0) = О (il е и

ад = ад = ... = Tn{D) = max < - min< WtJ\ {0}»

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

Также рассматривается применение приведенной "интервальной" версии для частичного распределения заданий в случае векторных выборок. Здесь предлагается производить распределение по каждой из координат для анализа зависимостей между заданиями.

В четвертом параграфе рассматривается другой вариант задачи распределения заданий между участниками. Задан набор заданий, т.е. множество 1, ТУ, которые требуется распределить между п участниками, и набор функций множеств

Т!: N К,..., : N -)- К,

имеющих смысл суммы. Именно, в работе рассматриваются три разных набора таких функций, в двух из которых используются коэффициенты:

где Х{ £хД, > О, г € 1, М, — некоторые характеристики заданий, а

_ п

оч > 0 Уг £ 1,п, а, = 1, — коэффициенты, задающие соотношение, ¿=1

в соответствии с которым требуется распределить набор заданий между участниками (сумма х, } £ К, при К =0 полагается равной 0). Основная задача для каждого из трех случаев имеет вид:

8ир({ВД): X е 1^}) Ы, (К^ е Дп(й\Г).

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

Вторая глава посвящена маршрутным задачам с ограничениями. Во втором параграфе рассматривается незамкнутая задача коммивояжера с ограничениями на переходы из города в город.

Задана база и набор из N городов. Стоимости переходов определяются посредством следующей матрицы:

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

с(а) = Л0,а(1] + £ 4»0>0+1)-

Незамкнутая задача коммивояжера имеет, как известно, следующий вид: с(а) —► min, а £ Р. В работе рассматривается незамкнутая задача коммивояжера с ограничениями, для этого в виде подмножества Р строится новое множество маршрутов, которое согласуется с ограничениями на текущие переходы из города в город.

Через 9t обозначаем семейство всех непустых подмножеств множества

üv _

D={(e. Jflcn /V х ЭТ | s £

Фиксируем отображение I : D —^ ЭТ. Для данного отображения должно выполняться следующее условие:

I(s,K)cK\f{s,K)eB

Таким образом, I(s, К) здесь — подмножество множества городов К, содержащее все города, в которые разрешен переход из города s.

В терминах множеств l(s,K), (s,K) <zD, вводится множество всех перестановок из , согласованных с вышеупомянутым ограничением. Данное множество будем обозначать через . Далее вводится незамкнутая задача коммивояжера с ограничениями на "текущие" переходы, имеющая следующий вид:

с (а) —> min, а е Po

В работе приводится модификация метода динамического программирования, предназначенная для решения таких задач, реализованная в виде алгоритма.

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

Пусть для каждого непустого множества К, К С 1, п, 3l Е К : Pi ф qj Vj е К. Если К £ N, то через £[/f] обозначаем множество всех i £ 1,п таких, что (pi £ K)&c{qi £ К). Для данной (назамкнутой) задачи курьера предложен следующий оператор I, удовлетворяющий всем условиям, приведенным для вышеупомянутой задачи коммивояжера с ограничениями:

I(s,К)^К\ {qj: j £ ВД} V(s,К) £ D.

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

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

В четвертом параграфе предложен приближенный алгоритм решения "обычной" задачи коммивояжера. Данный алгоритм допускает естественные аналогии с приближенным алгоритмом решения задачи распределения с критерием "типа наибольшей суммы", приводимым в первой главе.

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

ЗАКЛЮЧЕНИЕ

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

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

1. Построен вариант метода динамического программирования для задачи оптимизации измеримого разбиения пространства с алгеброй множеств в условиях неточных вычислений и реализации экстремумов.

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

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

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

5. Все предлагаемые в работе алгоритмы реализованы в виде стандартных программ, для которых посредством вычислительного эксперимента построены зависимости времени счета при изменении основных параметров исследуемых задач (количество заданий, количество групп, количество перевозок в задаче курьера и т.п.).

Публикации на тему диссертации

1. Зобнин, Б.Б. Маршрутно-распределительные задачи оптимизации и их применения для целей обнаружения и предупреждения катастрофических явлений / Б.Б. Зобнин, Л.Н. Коротаева, А.Г. Ченцов, ПА Ченцов // Совершенствование защиты насел. и террит. от ЧС природ, и технолог. характера в условиях Урал. региона. Пробл., особен. и пути решения:

Тез. докл. науч.-практ. конф,— Екатеринбург: Управление по делам ГОЧС г.Екатеринбурга, 1998,- С.117-119.

2. Ченцов, А.Г. Динамическое программирование в задаче оптимизации разбиений / А.Г. Ченцов, П.А. Ченцов // Автоматика и телемеханика.— 2002.- № 5.- С. 133-146.

3. Ченцов, А.Г. К вопросу о апостериорной временной кластеризации процесса наблюдения / А.Г. Ченцов, П.А. Ченцов // Интеллект, информ. технол. в управлен. деятельности.— Екатеринбург: ИПК УГТУ, 1999. С.10-13.

4. Ченцов, А.Г. К вопросу о построении процедуры разбиения конечного множества на основе метода динамического программирования / А.Г. Чепцов, П.А. Ченцов // Автоматика и телемеханика.— 2000.— № 4.— С. 129-142.

5. Ченцов, А.Г. Метод динамического программирования в задачах оптимизации разбиений / А.Г. Ченцов, П.А. Ченцов // Тр. 2 Междунар. науч.-техн. конф. Регион. Урал, отд-ния Акад. инженер, наук РФ.— Екатеринбург: УрО РАН, 2 0 00- С. 130-132.

6. Ченцов, А.Г. Метод динамического программирования в некоторых версиях задачи коммивояжера с ограничениями /А.Г. Ченцов, П.А. Ченцов // Алгоритмы и програм. средства параллел. вычислений.— Екатеринбург: УрО РАН, 2003 - №7.- С. 217-234.

7. Ченцов, А.Г. Оптимизация разбиений с использованием метода динамического программирования / А.Г. Ченцов, П.А. Ченцов // Интеллект, информац. технол. в управлен. деятельности.— Екатеринбург: ИПУ УГТУ-УПИ, 2001 - С.239-244.

8. Ченцов, П.А. О некоторых алгоритмах распределения заданий между участниками / П.А. Ченцов // Алгоритмы и програм. средства параллел. вычислений.- Екатеринбург: УрО РАН, 2002.-№ 6- С.231-241.

9. Ченцов, П.А. Об одном алгоритме распределения заданий / П.А. Чен-цов // Актуал. пробл. прикл. математики и механики: Тез. докл. конф., посвящ. 70-летию со дня рожд. акад. А.Ф. Сидорова.— Екатеринбург: УрО РАН, 2003.- С.86.

10. Ченцов, П.А. Об одном приближенном алгоритме распределения объектов / П.А. Ченцов // Интеллект, информац. технол. в управлен. деятельности- Екатеринбург: ИПУ УГТУ-УПИ, 2002.- С. 149-154.

11. Ченцов, П.А. Об одном приближенном алгоритме решения незамкнутой задачи коммивояжера / П.А. Ченцов // Алгоритмы и програм. средства параллел. вычислений.— Екатеринбург: УрО РАН, 2003.— № 7.— С.235-242.

Ченцов Павел Александрович

Некоторые задачи маршрутизации и распределения заданий: метод динамического программирования и приближенные алгоритмы

Автореферат

Подписано в печать 06.10.2004 Формат 60 х 84 1/16. Объем 1.0 п.л. 100 экз. Заказ № 170

Размножение с готового оригинал-макета в типографии УрО РАН 620219, Екатеринбург, ул. С.Ковалевской, 18.

U21893

РНБ Русский фонд

2005-4 21742

Список сокращений и обозначений.

Введение.

Глава I. Задачи распределения в группы.

1. Введение.

2. Оптимизация разбиений измеримого пространства в условиях неточных вычислений

3. Разбиение в сумму интервалов натурального ряда.

4. Оценки и алгоритмы на их основе.

5. Вычислительный эксперимент.

Глава II. Маршрутные задачи с ограничениями.

1. Введение.

2. Задача коммивояжера с ограничениями.

3. Задача курьера.

4. Один приближенный метод решения задачи коммивояжера.

5. Вычислительный эксперимент.

Диссертационная работа посвящена исследованию экстремальных задач, имеющих смысл распределения и упорядочения заданий. В качестве основного используется метод динамического программирования. Кроме того, рассматриваются приближенные методы. Задачи такого рода возникают, например, в приложениях, связанных с распределением потока задач в многопроцессорных вычислительных комплексах, транспортными задачами, распределением товаров и грузов по складам и хранилищам, распределением работ между исполнителями и т.д. При решении такого рода задач возникают, однако, существенные трудности с организацией вычислений. Так, например, в известной задаче коммивояжера с п городами возникает п! вариантов конкретного выбора маршрута. Данная задача является КР-полной (см. в этой связи [16]). Поэтому представляется важным построение быстродействующих приближенных алгоритмов, использующих специфику той или иной конкретной задачи. С другой стороны, представляется важным исследование структуры решения, что может, в частности, осуществляться посредством применения различных модификаций известного метода динамического программирования Р.Беллмана (см. [3], [5], [25], [40]). Отметим, в частности, применение метода динамического программирования для решения задачи коммивояжера [4], [49]. Для решения этой актуальной задачи применялись и другие методы (точные и приближенные). Отметим, в частности, известный метод ветвей и границ [37], а также процедуры сведения замкнутой версии задачи к незамкнутой [37] в связи с конструкциями данной работы. Следует упомянуть о естественных связях задачи коммивояжера со многими другими задачами дискретной оптимизации; см. в этой связи [37]. Исследованию этих задач посвящены работы многих авторов. Сейчас отметим имена только некоторых исследователей, имея в виду работы, близкие в идейном отношении к тематике данной диссертации: Р.Беллман, Е.Я.Габович, А.К.Лейтен, И.И.Меламед, Ю.М. Плотинский, С.И.Сергеев, И.X.Сигал, Г.Г.Сихарулидзе, В.Р.Хачатуров, М.Хелд, D. Applegete, R. Bix-by, V. Chv'atal, W. Cook, A.L. Henry-Labordere, G. Laporte, Y. Nobert.

В задачах маршрутизации и распределения заданий конструкции метода динамического программирования использовались в работах [20], [22], [26], [27], [28], [43], [50], [51], [52], [53], [54], [55], [69], [71], где рассматривались, в частности, дискретно-непрерывные экстремальные задачи последовательного обхода множеств одним или несколькими участниками. С этими постановками можно связать задачи последовательного управления (см., например, [6], [7], [8], [10], [11], [12]), включая игровые постановки (см. [32], [34], [76]); упомянутые работы,лежат в русле исследований школы Н.Н.Красовского, используют элементы теории принципа максимума Л.С.Понтрягина, двойственность линейных задач управления и выпуклого программирования, установленную Н.Н.Красовским [33]; в этой связи отметим также исследования А.Б.Куржанского, Ю.С.Осипова, А.И.Субботина. В связи с задачами о последовательном посещении множеств отметим работу [9], в которой использовались методы теории приближения функций. Идеи маршрутизации, развиваемые в дискретной математике, находят, таким образом, свое применение и во многих задачах управления и оптимизации, включающих как дискретную, так и "непрерывную" компоненты решения.

Обстоятельный обзор методов решения задачи коммивояжера и многих других подобных задач дискретной оптимизации имеется в [37], [38] и [39]; отметим, в частности, задачу нескольких коммивояжеров (см., например, работы [35], [78]) и нескольких курьеров [36], в которых одновременно используются элементы маршрутизации и распределения заданий, а также работы [22] и [26], в которых методы маршрутизации в задачах последовательного обхода множеств сочетались с активным использованием метода динамического программирования для целей разбиения пространства заданий.

В связи с вопросами распределения потока задач в многопроцессорных вычислительных комплексах отметим исследования [15], [73], [74]; решение таких задач осложняется необходимостью в рассмотрении процесса распределения в темпе реального времени и дополнительными ограничениями на порядок поступления заданий, их приоритета и некоторыми другими особенностями.

Задачи о разбиении множеств, элементы которых можно интерпретировать как задания, и подобные им в логическом отношении задачи рассматривались в целом ряде работ как в общетеоретическом плане, так и в плане исследования конкретных задач прикладного характера. Отметим, в частности, направление, связанное с кластеризацией. Так, например, в [13] рассматривались свойства оптимальных разбиений (относительно энергии, метрического потенциала, размера). В [18] исследовался алгоритм кластеризации, результат применения которого представляется последовательностью, в которой исключаются заведомо неоптимальные разбиения. В [14] исследовалась задача реализации разбиений множеств булевых наборов асимптотически оптимальными схемами. В [47] рассматривалась задача распределения ресурсов в АСУ реального времени с элементами неопределенности; использовался игровой подход. В [46] исследовались асимптотические представления для характеристик случайных разбиений конечного множества на "блоки". В связи со стохастическими постановками задач о размещении отметим монографию [24]. В [31] рассматривалась задача о назначении работ, т.е., задача о распределении работ между исполнителями, которая в некотором смысле похожа на приводимые выше постановки задач распределения заданий между процессорами, хотя имеет несколько иную систему ограничений.

Отметим, что многие задачи, рассматриваемые в диссертации, могут быть отнесены к классу ИР-полных задач (см. в этой связи монографию [16] и оригинальную работу [70]). Следуя [16, гл. 3] отметим в числе близких к исследуемым в работе ИР-полных задач задачи "коммивояжер" и "разбиение" ; см. [16, с. 65-67,145]. Известно, что [16, с. 28] ^-полные задачи обычно связывают с проблемой труднорешаемости (заметим, что в теории ЫР-полных задач рассматриваются обычно задачи распознавания, но соответствующие выводы можно распространить и на задачи оптимизации; см. [16, с. 33]). В этой связи уместно напомнить о различии между полиномиальными ("хорошими") и экспоненциальными алгоритмами: см., например, [16, с. 19-21]. Можно, однако, отметить полезное замечание в [16, с. 21] о том, что различие между упомянутыми типами алгоритмов может принимать "совсем иной характер" , когда размеры решаемых задач невелики. Это и ряд других замечаний в [16] показывают, на наш взгляд, что и для труднорешаемых (терминология [16]) задач алгоритмы, имепуемые экспоненциальными (см. [16, с. 19]), могут представлять значительный интерес; в этой связи полезно иметь в виду применимость алгоритма в наихудшем случае и аналогичную применимость для решения той или иной индивидуальной задачи. Эти обстоятельства нашли свое отражение в предлагаемой диссертационной работе, где параллельно с разработкой точных и "трудных" алгоритмов, связываемых с вариантами метода динамического программирования, разрабатываются приближенные (и достаточно быстрые) алгоритмы, включающие в ряде случаев элементы теоретических конструкций.

Общие вопросы, связанные с решением задач дискретной оптимизации, рассматривались в монографии [48] (отметим, в частности, само понятие задачи дискретной оптимизации большой размерности; см. [48, гл. I]). В частности, в [48] приведены некоторые методы решения задачи коммивояжера большой размерности: декомпозиция, включающая разбиение пространства заданий, связанных с посещением городов, решение подзадач, формирование приближенного решения основной задачи и аналогичных решений подзадач. Среди практических применений в [48] рассматривалась, в.частности, задача о трассировке печатных плат (см. в этой связи также работу [28], где обсуждалось применение методов последовательного обхода множеств для решения задачи о размещении компонент радиоаппаратуры на печатных платах).

Заметим, что при использовании моделей, включающих элементы задачи коммивояжера или нескольких коммивояжеров в тех или иных конкретных задачах, зачастую возникают дополнительные ограничения, приводящие к затруднениям как в процессе вычислений, так и в теоретическом отношении; в этой связи отметим известную задачу курьера [36], [42] (Dial-A-Ride Problem: [68], [75], [77]). Эти осложнения связаны с конкретными прикладными задачами.

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

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

Теперь перейдем непосредственно к краткому содержанию диссертации. Первая глава посвящена задаче распределения заданий между участниками. Кратко эту задачу можно проинтерпретировать следующим образом: пусть имеется набор заданий и некоторое фиксированное количество участников. Требуется "раздать" все задания участникам так, чтобы каждое задание попало только к одному участнику и при этом некоторый критерий имел минимальное значение.

Рассматривается и более общая постановка. Пусть задано непустое множество Е, оснащенное алгеброй Z подмножеств Е : (Е, Z) есть измеримое пространство с алгеброй множеств. Фиксируем п € Л/", п > 2; г 6 1, п — номера участников. Для L G Z и т Е Л/" полагаем, что Am(L, Z) есть def множество всех кортежей (разбиений) iLi)ieТЛ Мп —► Z, со свойствами: тп

1)ь=[]и. i=1

2) Vpe l.mVge l,m\{p} :Lpf[Lq = Q.

Если зафиксирован набор Т\ : Z —> [0, оо[,Тп : Z —У [0, оо[, то рассматриваемая общая задача выглядит следующим образом: sup{{Ti(Li) : i е М}) —> inf, (Li)ieщ в &п(Е, Z).

В рамках этой более общей постановки могут рассматриваться задачи с бесконечным множеством Е. Решать вышеупомянутую общую задачу предлагается методом ДП, причем предполагается, что при вычислении слоев функции Беллмана могут возникать ошибки. Для реализации такого подхода предлагается ввести операторы:

Am F —У ¥, где F множество всех функций из Z в [0, оо[, по следующему правилу: при G F и L G Z

Am(f)(L)= inf sup({/(A); Tm+i(L \ A)});

AeZ,AcL здесь m G 1, n — 1. На основе этих операторов функция Беллмана строится итерационным способом: i>i = Ti; Vm G l,n — 1 : = Am(vm).

Пусть 6i > 0,., 6ni > 0 и кортеж : 1) 71 —^ ^ удовлетворяет следующим условиям: wi = Ti)&(Vm G 1,72 — 1 VLe Z : \wm+i(L) - Am(wm)(L)| < em). Легко видеть, что в данном случае вводятся огрубленные варианты действия операторов А\,An-i. Устанавливается, что г-1

Vr G \/L е Z : \wr(L) - vr(L)\ < s.

S = 1

Пусть г; — истинная функция Беллмана, a w — какая-либо ее модель, имеющая своими слоями w\,.,wn, и при этом известно, что У s G 1, n — 1 VL G Z: ws(L) - ve(L)| <

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

Msel^T : М - 1 —> [0, оо[, именно, если m G 1, n — 1 и L G Z, то полагаем, что ячейка конструируемого разбиения выбирается из множества m(wm, L, ат) = {A G Z I А С L, sup({ium(L \ A); Tm+i(A)}) < Am{wm){L) + am}.

Тогда для полученного, посредством приведенной в работе процедуры на основе метода ДП, разбиения (]Ц-£ Аn(E,Z) справедлива оценка (V = vn(E) — значение задачи) п—1 п—1 sup({Tfc(Lfc) : к Е T~n}) < V + + 2 г—1 i=1

Далее рассматривается более частная постановка. Пусть задано число N, N > 2; г € 1, N — номера заданий. Также задано число n, п > 2, где г 6 1,п — номера участников. Пусть J = {рГЗ : р 6 1Д,? 6 1, А^} — семейство всех промежутков Л/*, содержащихся в 1, N, включая пустой промежуток. Будем полагать, что участники г 6 1,п распределяют задания из 1, iV по промежуткам l\ + 1,12, h + 1? ¿з> ¿п + Wi> гДе U < ¿¿+1, ¿1 = 0, ln+1 = iV. Кроме того, задан набор функций множеств

Ti : J [0, оо[,., Tn : J [0, оо[.

Пусть An(iV) — множество всех разбиений 1, IV в сумму п промежутков из вышеупомянутого типа. Рассмотрим задачу: sup({Ti(A) : г в М}) —> min, (Д)геТ^ € Аn(N).

В работе предложена быстродействующая процедура на основе метода ДП, позволяющая получать оптимальное решение такой задачи.

Кроме того, рассмотрена постановка, в которой требуется строить произвольное разбиение 1, N. Пусть N — семейство всех подмножеств 1, N, An(l,N) — множество всех разбиений множества 1, N в сумму п подмножеств. Итак, Дп(1, N) есть множество An(E,Z) в условиях, когда Е = 1, АГ, а Z есть алгебра всех п/м множества 1, N. Пусть V К Е N \ {0}

Т*(К) = max W[ — min Wj, ieК jeк где 6 М, I Е 1, п, — некоторые числовые характеристики заданий; Т*(0) = 0. В работе доказано, что задача эквивалентна приведенной выше "интервальной" постановке с условием предварительной перенумерации в порядке возрастания и набором функций критерия вида: Т\ = Т2 = ••• =Тп = Т*, т.е. где — зависимость после перенумерации. Это позволяет использовать быстродействующий алгоритм на основе метода ДП (для задачи о разбиении ^Д7" в сумму промежутков) для решения задачи оптимизации произвольных разбиений 1,ЛГ с критерием, формируемым на основе Т*. Рассмотрено применение этой процедуры к векторным выборкам по каждой из координат в отдельности для анализа зависимостей между заданиями.

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

8ир({Г(Щ : г 6 1, #}) —► ппп, (Я&да 6 Д„(1,#)

Т1(£>) = Т2(£>) = . = Т„(£>) = тах< - тт«£ VDeJ\ {0},

Тх : N —> М,Тп :М->Е, г € 1,п,Л' € М; зек N gn, jeK 1=1 где Xi £ M, X{ > 0, г £ 1,N, — некоторые характеристики заданий, a Tl a.{ > 0 Vi £ l,n, Oii — 1? — коэффициенты, задающие соотношение, i=l в соответствии с которым требуется распределить набор заданий между участниками (сумма Xj,j £ К, при К = 0 полагается равной 0). Основная задача для каждого из трех случаев имеет вид:

8Ир({7К^г) : г £ М}) —> inf, (tfj)ieT* € An(hN).

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

Вторая глава посвящена маршрутным задачам с ограничениями. Задана база и набор из N городов. Стоимости переходов заданы при помощи следующей матрицы:

А = {Aij GR]i£ £ IjV)

Пусть P — множество всех перестановок чисел из 1, N, т.е. множество всех биекций 1, N на себя. Для а £ Р стоимость вычисляется следующим образом:

N-1

С(а) = Л,а(1) + XI A*(j),a(j+1)

3=1

Незамкнутая задача коммивояжера имеет вид: c(a) —> min, a £ Р.

Через обозначаем семейство всех непустых п/м множества 1, N,

Ю> = {(s, К) £ Ojf х at I s<£K}. 14

Фиксируем отображение для которого выполняется следующее условие:

I(s,K) С К V(s, К) е Ю>.

Смысл данного отображения состоит в следующем. Пусть имеется некоторый набор городов К, который требуется обойти, выйдя из города с номером s. В задаче коммивояжера без ограничений можно было совершить переход из s в любой город из К. В данном случае на выбор маршрута наложены ограничения, реализуемые следующим образом: I(s, К) — это множество тех городов из К, в которые переход разрешен.

Через Ро обозначаем множество всех перестановок из Р, согласованных с приведенным ограничением. Теперь можно ввести незамкнутую задачу коммивояжера с ограничениями: с(а) —> min, а € Po

В работе построена модификация метода динамического программирования, предназначенная для решения таких задач. Эта модификация используется для решения известной [37] задачи курьера. Упомянутая задача курьера есть аналог задачи коммивояжера с ограничениями в виде условий предшествования. Для ее решения применяется приведенная выше конструкция решения задачи коммивояжера с "текущими" ограничениями. В задаче курьера фиксированы некоторые пары (Pi,qi) городов, причем для каждой такой пары посещение первого города (для этой пары) должно предшествовать посещению второго (между посещением первого города и посещением второго возможно посещение каких-то других городов). В литературе такие пары называются перевозками (см. [36]). Фиксируем два упорядоченных набора городов:

Pi)ieüi : Мг —1, N, Ыгем : —> T7N.

Пусть для каждого непустого множества К, К С 1, п, Зг G К : р^ ф qj Vj G К. Если К G N, то через £[/С] обозначаем множество всех г G 1, п таких, что (pi G K)Sz(qi G К). Для данной задачи предложен конкретный оператор /, удовлетворяющий всем условиям, приведенным для вышеупомянутой задачи коммивояжера с ограничениями:

J(s, К)йК\ {Qj : j G ЦК}} V(s, tf) G D.

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

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

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

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

Основные результаты диссертации опубликованы в следующих работах: [21], [56], [57], [58], [59], [60], [61], [62], [63], [64], [65].

Часть I

Задачи распределения в группы

1 Введение

Метод динамического программирования (ДП) широко используется в задачах дискретной оптимизации различной природы, в том числе в задачах по смыслу статических (см. [40]). В [4], [49] метод ДП применялся для решения задачи коммивояжера (ЗК). Развитием этих исследований стали работы [20], [26], [27], [28], [29], [53], [71], касающиеся маршрутизации с одновременным выбором некоторой "трассы". В задачах этого типа комбинаторная и "непрерывная" компоненты тесно переплетаются и при использовании декомпозиций зачастую наблюдается проигрыш в качестве. В то же время интересы решения "больших" задач заставляют подчас прибегать и к некоторым "распараллеливаниям" процесса, что связано нередко с необходимостью более быстрых реализаций приемлемых решений. Так, в связи с ЗК естественно появляется задача нескольких коммивояжеров. Аналогичная ситуация возникает и при решении задач последовательного обхода множеств, см., например, [20], [26], [28], [29], [43], [53], [54], [71]. Речь идет об активном использовании задач распределения тех или иных заданий между несколькими участниками. Представляется, что, как и в задаче [26], целесообразно сочетать маршрутизацию с процедурами распределения, получая в итоге комплекс маршрутно-распределительных задач. В то же время задачи распределения в духе решаемых в [20], [26], [28], [29], [43], [53], [54], [71] обладают известной спецификой: это — задачи оптимизации на пространствах функций множества. Данная линия, затронутая в [43], допускает естественное развитие на круг задач о разбиении бесконечных, вообще говоря, множеств. Мы рассматриваем здесь некоторые естественные обобщения работы [58] в этом направлении, используя, в частности, определенные аналогии с "маршрутными" версиями ДП в [53].

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

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

Четвертый раздел содержит построение некоторых полезных оценок. Рассматривается несколько постановок задачи распределения заданий между участниками, которые, в частности, можно интерпретировать как распределение задач по процессорам в многопроцессорных вычислительных комплексах, распределение товаров по складам, распределение жидких или сыпучих грузов по хранилищам, распределение работ между исполнителями. Упомянутые содержательные постановки приводят к задачам оптимизации разбиений конечных множеств. Для этих задач приводится ряд нижних оценок экстремума, а также предлагается один приближенный алгоритм решения этих задач, использующий данные оценки.

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

1. Александрии, P.A. Общая топология / P.A. Александрян, Э.А. Мирзаханян.— М.: Высшая школа, 1979.— 336 с.

2. Артынов, А.П. Автоматизация управления транспортными процессами / А.П. Артынов и др.— М.: Наука, 1984 — 272 с.

3. Беллман, Р. Динамическое программирование / Р. Беллман,— М.: ИЛ, i960 400 с.

4. Беллман, Р. Применение динамического программирования к задаче о коммивояжере / Р. Беллман // Кибернетический сборник.— М.: Мир, 1964.- Т.9.— С.219-228.

5. Беллман, Р. Динамическое программирование и основы современной теории управления / Р. Беллман, Р. Калаба.— М.: Наука, 1969.— 118 с.

6. Бердышев, Ю.И. О задаче последовательного обхода нелинейным управляемым объектом совокупности гладких многообразий / Ю.И. Бердышев // Дифференц. уравнения.— 2002.— Т.38, JY2 П.— С.1451-1461.

7. Бердышев, Ю.И. Об одной задаче последовательного сближения нелинейной управляемой системы третьего порядка с группой движущихся точек / Ю.И. Бердышев // Прикл. математика и механика.— 2002.— Т. 66, № 5.- С.742-753.

8. Бердышев, Ю.И. Об оптимальном по быстродействию последовательном обходе нелинейной управляемой системой третьего порядка совокупности точек / Ю.И. Бердышев // Изв. РАН. Теория и системы упр.- 2002.- № 3.- С.41-48.

9. Бердышев, В.И. О наилучшей траектории, соединяющей упорядоченный набор множеств / В.И. Бердышев, В.П. Кондратьев.— Свердловск: ИММ УНЦ АН СССР, 1986.- 85 с.

10. Бердышев, Ю.И. О некоторых задачах последовательной оптимизации управляемых систем / Ю.И. Бердышев, А.Г. Ченцов.— Свердловск, 1982.- 99 е.- Деп. в ВИНИТИ 05.01.83, № 109-83Деп.

11. Бердышев, Ю.И. Оптимизация взвешенного критерия в одной задаче управления / Ю.И. Бердышев, А.Г.Ченцов // Кибернетика.— 1986.— № 2.- С.59-87.

12. Бердышев, Ю.И. Оптимизация функционала на классе ломаных / Ю.И. Бердышев, А.Г. Ченцов // Некоторые вопри оптимизации разрывных функций.— Свердловск, 1984.— С.29-42.

13. Болотов, A.A. О метрической кластеризации / А.А.Болотов // Дискрет. математика.— 1996 Т.8, Ш - С.62-78.

14. Вихлянцев, И.А. О реализации разбиений множеств схемами из функциональных элементов / И.А. Вихлянцев // Дискрет, математика.— 1994.- Т.6, № 3.- С.61-72.

15. Гирл их, Э. Алгоритм для задачи распределения работ, выполняемых в реальном времени при наличии дополнительной информации / Э. Гирлих, М.М.Ковалев, В.М.Котов // Дискрет, математика.— 2003.— Т. 15, № 5.— С.133-140.

16. Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон ; пер. с англ. Е.В. Левнера и М.А. Фрумкина.— М.: Мир, 1982.- 416 с.

17. Данфорд, Н. Линейные операторы. Общая теория / Н. Данфорд, Дж.Т.Шварц. М.: ИЛ, 1962.- 895 с.

18. Двоенко, С.Д. Иерархический дивизимный алгоритм кластеризации / С.Д. Двоенко // Автоматика и телемеханика.— 1999.— № 4.— С.117-124.

19. Дьедонне, Ж. Основы современного анализа / Ж. Дьемонне.— М.: Мир, 1964 430 с.

20. Зобнин, Б.Б. Об одной задаче маршрутной оптимизации и ее приложениях / Б.Б. Зобнин, Л.Н. Коротаева, А.Г. Ченцов // Проблемы передачи информации 1997 — Т.ЗЗ, № 4 - С.1-18.

21. Келли, Дж.Л. Общая топология / Дж.Л. Келли.— М.: Наука, 1981.— 431 с.

22. Колчин, В.Ф. Случайные размещения / В.Ф. Колчин, Б.А. Севастьянов, В.П. Чистяков. — М.: Наука, 1976 — 224 с.

23. Кормен, Т. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзер-сон, Р. Ривест. М.: МЦНМО,,1999 — 960 с.

24. Коротаева, Л.Н. Об одной задаче о назначениях / Л.Н. Коротаева, Э.М. Назаров, А.Г. Ченцов // Журн. вычисл. математики и мат. физики.- 1993.- Т.ЗЗ, № 4.- С.483-494.

25. Коротаева, Л.Н. Об одной модификации метода динамического программирования в задаче последовательного сближения / Л.Н.Коротаева, А.Н. Сесекин, А.Г. Ченцов // Журн. вычисл. математики и мат. физики 1989 - Т.29, № 8.- С.1107-1113.

26. Коротаева, Л.Н. К вопросу о маршрутизации соединений / Л.Н. Коротаева, М.П. Трухин, А.Г. Ченцов // Автоматика и телемеханика.— 1997.-№ 12,- С.175-192.

27. Коротаева, Л.Н. Об одном обобщении задачи коммивояжера "на узкие места"/ Л.Н. Коротаева, А.Г. Ченцов // Журн. вычисл. математики и мат. физики.- 1995.- Т.35, № 7.- С.1067-1076. •

28. Костюк, Ю.Л. Метрическая задача коммивояжера для отрезков / Ю.Л. Костюк // Автоматика и телемеханика.— 2000.— № 3.— С.142-148.

29. Кропанов, В.А. Равномерное назначение работ минимальной стоимости / В.А. Кропанов, B.C. Рублев // Дискрет, математика.— 2001.— Т.13, № 4.- С.144-157.

30. Красовский, H.H. Задача конфликтного управления с наследственной информацией / H.H.Красовский, Н.Ю. Лукоянов // Прикл. математика и механика 1996.- Т.60, № 6.- С.885-900.

31. Красовский, H.H. Теория управления движением / H.H. Красовский.- М.: Наука, 1968 — 476 с.

32. Лукоянов, Н.Ю. К вопросу вычисления цены дифференциальной игры для позиционного функционала / Н.Ю. Лукоянов // Прикл. математика и механика — 1998 Т.62, № 4 — С.586-597.

33. Меламед, И.И. К задаче нескольких коммивояжеров / И.И. Меламед // Межвуз. сб.- М.: МИИТ, 1981.- № 647.- С.117-119.

34. Меламед, И.И. Эвристический алгоритм решения обобщенной задачи развозки / И.И. Меламед, Ю.М. Плотинский // Автоматика и телемеханика.— 1979 № 12 - С.167-172.

35. Меламед, И.И. Задача коммивояжера. Вопросы теории / И.И. Меламед, С.И. Сергеев, И.Х. Сигал // Автоматика и телемеханика.— 1989.— № 9.- С.3-34.

36. Меламед, И.И. Задача коммивояжера. Точные алгоритмы / И.И. Меламед, С.И. Сергеев, И.Х. Сигал // Автоматика и телемеханика.— 1989.— № 10.- С.3-29.

37. Меламед, И.И. Задача коммивояжера. Приближенные алгоритмы / И.И. Меламед, С.И. Сергеев, И.Х. Сигал // Автоматика и телемеханика — 1989 — № 11 — С.3-26.

38. Мину, М. Математическое программирование / М. Мину.— М.: Наука, 1990.- 468 с.

39. Неве, Ж. Математические основы теории вероятностей / Ж. Неве.— М.: Мир, 1969.- 309 с.

40. Плотинский, Ю.М. Общая задача развозки / Ю.М. Плотинский // Автоматика и телемеханика.— 1973.— № 6.— С. 100-104.

41. Сабирянова, К.Г. Динамическое программирование в задаче оптимизации покрытия / К.Г. Сабирянова, А.Г. Ченцов // Автоматика и телемеханика.— 1994.— № 3.— С.54-64.

42. Сергеев С.И. Вычислительные алгоритмы решения задачи коммивояжера. I // Автоматика и телемеханика. — 1994. — № 5. — С. 66-78.

43. Сергеев, С.И. Вычислительные алгоритмы решения задачи коммивояжера. II / С.И. Сергеев // Автоматика и телемеханика.— 1994.— № 6,- С.106-114.

44. Тимашев, А.Н. Случайные разбиения множеств с известным числов блоков / А.Н. Тимашев // Дискретная математика.— 2003.— Т.15, № 2.- С.138-148.

45. Фуругян, М.Г. Решение одной задачи распределения ресурсов в АСУ реального времени при наличии неопределенных факторов / М.Г. Фуругян // Автоматика и телемеханика.— 2002.— № 11.— С.167-171.

46. Хачатуров, В.Р. Комбинаторные методы и алгоритмы решения задач дискретной оптимизации большой размерности / В.Р. Хачатуров и др.- М.: Наука, 2000.— 360 с.

47. Хелд, М. Применение динамического программирования к задачам упорядочения / М. Хелд, P.M. Карп // Кибернет. сб.— М.:Мир, 1964.— Т.9.— С.202-218.

48. Ченцов, A.A. Метод итераций в обобщенной задаче коммивояжера на узкие места / A.A. Ченцов // Алгоритмы и програм. средства парал. вычислений.- Екатеринбург:УрО РАН, 2001 № 5 — С.287-302.

49. Ченцов, A.A. К вопросу о решении задачи последовательного обхода множеств с использованием "незамкнутой" задачи коммивояжера / A.A. Ченцов, А.Г. Ченцов // Автоматика и телемеханика.— 2002,— № 11 С.151-166.

50. Ченцов, A.A. О решении задачи маршрутной оптимизации методом динамического программирования / A.A. Ченцов, А.Г. Ченцов // Автоматика и телемеханика.— 1998.— № 9.— С. 117-129.

51. Ченцов, A.A. О решении задачи маршрутной оптимизации методом динамического программирования / A.A. Ченцов, А.Г. Ченцов // Изв. РАН. Теория и системы упр.- 1999.- № 3 — С.76-87.

52. Ченцов, A.A. Редукция задач маршрутной оптимизации / A.A. Ченцов, А.Г. Ченцов // Автоматика и телемеханика.— 2000.— № 10.— С.136-150.

53. Ченцов, А.Г. Динамическое программирование в задаче оптимизации разбиений / А.Г. Ченцов, П.А. Ченцов // Автоматика и телемеханика.- 2002.— № 5.- С. 133-146.

54. Ченцов, А.Г. К вопросу о апостериорной временной кластеризации процесса наблюдения / А.Г. Ченцов, П.А. Ченцов // Интеллект, информ. технол. в управлен. деятельности.— Екатеринбург: ИПК УГТУ, 1999.— С.10-13.

55. Ченцов, А.Г. К вопросу о построении процедуры разбиения конечного множества на основе метода динамического программирования / А.Г. Ченцов, П.А. Ченцов // Автоматика и телемеханика.— 2000.— № 4.— С.129-142.

56. Ченцов, А.Г. Метод динамического программирования в задачах оптимизации разбиений / А.Г. Ченцов, П.А. Ченцов // Тр. 2 Междунар. науч.-техн. конф. Регион. Урал, отд-ния Акад. инженер, наук РФ.— Екатеринбург: УрО РАН, 2000.- С.130-132.

57. Ченцов, А.Г. Метод динамического программирования в некоторых версиях задачи коммивояжера с ограничениями / А.Г. Ченцов, П.А. Ченцов // Алгоритмы и програм. средства параллел. вычислений.— Екатеринбург: УрО РАН, 2003.- №7.- С. 217-234.

58. Ченцов, А.Г. Оптимизация разбиений с использованием метода динамического программирования / А.Г. Ченцов, П.А. Ченцов // Интеллект. информац. технол. в управлен. деятельности.— Екатеринбург: ИПУ УГТУ-УПИ, 2001.- С.239-244.

59. Ченцов, П.А. О некоторых алгоритмах распределения заданий между участниками / П.А. Ченцов // Алгоритмы и програм. средства парал-лел. вычислений.- Екатеринбург: УрО РАН, 2002 № 6 - С.231-241.

60. Ченцов, П.А. Об одном алгоритме распределения заданий / П.А. Ченцов // Актуал. пробл. прикл. математики и механики: Тез. докл. конф., посвящ. 70-летию со дня рожд. акад. А.Ф. Сидорова.— Екатеринбург: УрО РАН, 2003.- С.86.

61. Ченцов, П.А. Об одном приближенном алгоритме распределения объектов / П.А. Ченцов // Интеллект, информац. технол. в управлен. деятельности.- Екатеринбург: ИПУ УГТУ-УПИ, 2002,- С.149-154.

62. Ченцов, П.А. Об одном приближенном алгоритме решения незамкнутой задачи коммивояжера / П.А. Ченцов // Алгоритмы и програм. средства параллел. вычислений.— Екатеринбург: УрО РАН, 2003.— № 7.- С.235-242.

63. Энгелькинг, Р. Общая топология / Р. Энгелькинг.— М.: Мир, 1986.— 751 с.

64. Applegete, D. On the solution of travelling salesman problems / D. Ap-plegete et al. // Proc. Intern. Congress Math.— Berlin, 1998.— Vol.111.— P.645-656.

65. Bodin, L. Classification in vehicle routing and scheduling / L.Bodin, B.Golden // Networks.- 1981.- Vol.11, № 2.- P.97-108.

66. Chentsov, A.A. Dynamic Programming Method in the Generalized Traveling Salesman Problem: The Influence of Inexact Calculations / A.A. Chentsov, A.G. Chentsov // Math, and Comput. Modelling — 2001 — Vol.33.- P.801-819.

67. Cook, S.A. The complexity of theorem-proving procedures / S.A. Cook // Proc. 3 Symp. on Theory of Computing, Association for Computing Machinery- New York, 1971.- P.151-158.

68. Chentsov, A.G. The Dinamic Programming Method in the Generalized Salesman Problem / A.G. Chentsov, L.N. Korotaeva // Math, and Comput. Modelling 1997 - Vol.25, № 1- P.93-105.

69. Пападимитриу, X. Комбинаторная оптимизация. Алгоритмы и сложность / X. Пападимитриу, К. Стайглиц.— М.: Мир, 1985.— 510 с.

70. Graham, R.L. Bounds for certain multiprocessor anomalies / R.L. Graham // Bell System Tech.- 1966.- Vol.45.- P.1563-1581.

71. Graham, R.L. Bounds for certain multiprocessor anomalies / R.L. Graham // SI AM J. Appl. Math.- 1969.- Vol.17.- P.263-269.

72. Kalantari, B. An algorithms for the traveling salesman problem with pickup and delivery customers / B. Kalantari, A.V. Hill, S.R. Arora // Eur. J. Oper. Res.- 1985.- Vol.22, № 3.- P.377-386.

73. Krasovskii, A.N. Control under lack of information / A.N. Krasovskii, N.N. Krasovskii.— Berlin etc.: Birkhauser, 1995.— 322 p.

74. Psaraftis, H.N. K-interchange procedures for local search in a precedence-constrained routing problem / H.N. Psaraftis // Eur. J. Oper. Res.— 1983,- Vol.13, № 4.- P.391-402.

75. Svestka, J.A. A computational experience with on M-saleman traveling salesman algorithm / J.A. Svestka, V.E. Huckfeldt // Manag. Sei.— 1973.— Vol.19, № 7.- P.790-799.