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

Диссертационная работа посвящена исследованию экстремальных задач, имеющих смысл распределения и упорядочения заданий. В качестве основного используется метод динамического программирования. Кроме того, рассматриваются приближенные методы. Задачи такого рода возникают, например, в приложениях, связанных с распределением потока задач в многопроцессорных вычислительных комплексах, транспортными задачами, распределением товаров и грузов по складам и хранилищам, распределением работ между исполнителями и т. д. При решении такого рода задач возникают, однако, существенные трудности с организацией вычислений. Так, например, в известной задаче коммивояжера с п городами возникает п! вариантов конкретного выбора маршрута. Данная задача является КР-полной (см. в этой связи [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 = TiVm 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 Д&bdquo-(1,#).

Т1(£>) = Т2(£>) =. = Т&bdquo-(£>) = тах< - тт"£ 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.

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

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

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

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

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

Pi)ieui: Мг —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 MachineryNew 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.