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

• Ченцов, Павел Александрович
• кандидат физико-математических наук
• 2004

Оглавление диссертации кандидат физико-математических наук Ченцов, Павел Александрович

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

Введение.

Глава 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].

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

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Ченцов, Павел Александрович, 2004 год

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.