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

• Истомин, Алексей Михайлович
• кандидат наук
• 2015

Оглавление диссертации кандидат наук Истомин, Алексей Михайлович

Оглавление

Введение

1 Задача нескольких коммивояжёров с входными данными специального вида

1.1 Постановка задачи

1.2 Алгоритм приближенного решения задачи

1.2.1 Вспомогательная процедура построения гамильтоновой цени

1.2.2 Описание алгоритма решения задачи

1.2.3 Описание входных данных

1.3 Вероятностный анализ алгоритма

1.3.1 Входные данные, распределённые по нормальному закону

1.3.2 Входные данные, распределённые по показательному закону

2 Задача двух коммивояжёров с ограничениями на пропускные способности рёбер

2.1 Постановка задачи и предварительные сведения

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

2.2.1 Описание вспомогательной процедуры

2.3 Анализ точности алгоритмов в среднем

2.3.1 Анализ алгоритма для задачи па минимум

2.3.2 Анализ алгоритма для задачи на максимум

2.4 Новые алгоритмы решения задач на минимум и па максимум с различными весовыми функциями маршрутов

2.4.1 Описание вспомогательной процедуры

2.5 Анализ ючнопи алгоритмов в среднем

2.5.1 Анализ алгоритма для задачи па минимум

2.5.2 Анализ алгоритма для задачи па максимум

3 Задача маршрутизации транспортных средств в евклидовом пространстве

3.1 Предварительные сведения

3.2 Случаи равномерного распределения на круге единичной площади

Заключение

Публикации автора по теме диссертации

Благодарности

Литература

Введение диссертации (часть автореферата) на тему «Вероятностный анализ алгоритмов с гарантированными оценками точности для решения некоторых трудных задач маршрутизации»

Введение

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

Для эффективного решения таких проблем возникает необходимость построения математических моделей реальных процессов и алгоритмов решения возникающих при этом задач. Как правило, решение этих задач связано со значительными трудностями вычислительного харакюра. Общее представление о сложности таких задач даёт книга [18]. В этой книге приводится более 500 задач (из самых разных областей, включая теорию графов и сетей, теорию расписаний, теорию автоматов и языков, оптимизацию программ, базы данных, игры и юловоломки и т.п.), для которых построение эффективных алгоритмов их решения в настоящее время считается маловероятным.

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

а для массовой задачи Z, cootbciствующей множеству индивидуальных задач.

Важный класс массовых задач образуют задачи дискретной (комбинаторной) оптимизации. Для оптимизационной постановки задачи Z решением каждой индивидуальной задачи / G Z является такая точка z*(I) G Sz{I), для которой fz{I,z*(I)) = ma.rz£sz(i),fz(I.z) или fz(I.z*(I)) = m'mzeSz(i)Jz{l• z) для задачи па максимум и минимум, соответственно. Здесь SZ(I) область допустимых значений дискретной (целочисленной) переменной fz{I,z) : Sz{I) —> TZ+ ~~ целевая функция индивид} алыюй задачи / оптимизации.

Большинство дискретных задач допускает решение с помощью некоторого процесса перебора вариантов, однако число возможных вариантов зачастую растет экспоненциально в зависимости от размеров задачи (так, в задаче коммивояжера с т городами существует (т — 1)! различных маршрутов). Поэтому переборные алгоритмы решения массовых задач с читаются неэффективными (могут решать лишь индивидуальные задачи небольшой размерности). Эффективными называемся алгоритмы решения массовой задачи, которые решают произвольную I е Z за время, ограниченное полипомом от "размера" / (полиномиальные алгоритмы). Несмотря па определенную условность этого разделения с точки зрения практического счета, оно обьясняется прежде всего тем, что полином растёт медленней, чем экспонента, и лучше отзывается па рост машинной скорости. Массовые задачи, для коюрых существует решающий их полиномиальный алгоритм, называются полиномиальными. Класс всех полиномиальных задач обычно обозначают символом Р.

Далее, в соответствии с работой [38], определим класс NP (от англ. иоп-deterministic polynomial time) - класс задач распознавания свойств (то есть задач, решением которых может быть либо «да», либо «нет»), разрешимых за полпиомиаль-

ное время на недетерминированном вычислительном устройстве. Задача из класса NР называется ЛгР-нолной, если к ней полиномиально сводится любая задача ш класса УР. До сих нор остается 01 крытым вопрос о полиномиальной разрешимости АгР-иолных задач. УР-1\)\дной, согласно |20], называется любая задача (не обязательно пз ктасса ХР). к ко юрой полиномиально сводится любая 5адачл из класса МР.

Алгоритм Л па ¡ывается приближенным алтритмом решения массовой задачи 2 оптимшацип, если для произвольною 1 Z он находиI некоторую точку из допустимой области € Sz(í), принимаемою за приближенное решение. Значение ¡г{1 ^ гл{П) иазывлек'я приближенным значением оптимума и обозначаоюя через

Л{1).

Пнотда при анализе приближенною алюритма удается показать определенные гарашпрованпые оценки качества решения, получаемого в ходе его рабопл для произвольной индивидуальной задачи. Говорить об абсолютной погрешности (\OptziI) — Л(-01) приближенного алюрнгма 1>ешенпя массовой задачи оптимизации (на классе всевозможных индивидуальных задач) обычно не имеет большого смысла, так как для разных индивидуальных задач величина оптимума может быть как скоть угодно большой, так и малой. Поэтому обычно проводится анализ относитель-

ной пот решпости

Qpj zd)-лд) Optz(l)

), либо точности ((jp/^/j) приближенных алюртпмов. Приближенный алгоритм Л решения массовой задачи оптимизации наливается Д-приближенным алгоритмом решения (алторитмом с гарантированной оценкой точное iи Л) для некоторого Л > 0. если для произвольного входа 1 (со строго положи-

тельным ошимумом) верно:

для задачи на минимум п задачи па максимум, cooibcicibchiio.

Приведённое определение ючнопи приближённого алгоритма обычно называют ''оценкой точноеj и атгорп i ма в худшем случае", поскольку такая оценка должна быть выполнена даже на самых неблагоприятных входных данных. Однако часто бываем, что''плохие" примеры составляют малую часть всевозможных входов и редко встречаются на практике. Поэтому широкое распространение получил вероятностный анализ алгоритмов (анализ алгоритмов "в среднем"), при котором качество алгоритмов оценивается с использованием техники теории вероятностей в предположении, что входные данные являются случайными величинами с некоторым известным законом распределения.

При вероятностном анализе алюрпгмов часто используются обозначения и определения, представленные в [8|. Рассмотрим алгоритм Л решения некоторой оптимизационной задачи. Алгоритм Л имеет оценки (сп. 5„) в классе Z„ задач максимизации размерности п, если для каждою п выполнены следующие неравенства:

где Рг{5} — вероятность соответствующего события Б. с„ называется относительной погрешностью. 5„ — вероятностью несрабатывания алгоритма А (доля случаев, в которой алгоритм не удовлетворяет анонсированной точности). Алгоритм называ-

ется асимптотически точным в классе задач Z = UZ„\n € {1,2....}, если для пего

существую г оценки (:п.6„): :„ —> 0. д„ —> 0. при п —> ос.

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

Примером вероятностного анализа алгоритма для задачи поиска регулярного связного подграфа максимального реберного веса может служить результат рабо-

Алгоритм А решения массовой задачи оптимизации будем называть алгоритмом с гарантированной оценкой точиосш А в среднем для некоторого А > 0, если для произвольного входа 1 со строго положительным ожиданием оптимума верно:

для задачи на минимум и задачи па максимум, соответственно. Здесь и далее через М(Л") обозначено магматическое ожидание случайной величины X.

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

Из многочисленных приложении указанных задач можно выделить составление маршрутов патрулирования, где важно держать под надзором как можно большую территорию, [72]. дизайн максимально падёжных сетей передачи данных [41], планирование машинной обработки детален, где важно избежать столкновений различных инструмен гов. обрабат ывающпх одни и те же узлы. [ 11|, а также опт имизацню маршрутов доставки товаров к местам реализации [40].

[22].

ты [52].

В классической постановке задачи коммивояжера в качестве входной информации дан реберпо-взвешеннып граф G = (V., Е) с неотрицательной весовой функцией рёбер w : Е —> 1Z+, а целью является отыскание в нём экстремального по весу гамильтонова цикла. Задача коммивояжера принадлежит к числу известных NP-трудных задач [18]. Наиболее полные обзоры работ по этой задаче можно найти в [53, 62]. Задача коммивояжера, ввиду своей широкой известности, упоминается среди математиков и статистиков под разными названиями.

Работа Менгера [65] считается наиболее ранней, опубликованной по задаче коммивояжера. Менгер рассматривал модификацию TSP, называя ее задачей курьера [32, 65]. Задачи курьера и коммивояжера эквивалентны в том смысле, что любая из них может быть преобразована к другой с использованием простейших преобразований входных данных и результата.

Само название ''задача коммивояжёра", по всей видимости, происходит из США, где в 1919 году была опубликована первая работа |G8] с его использованием. Однако, стоит отметить, что систематическое исследование задачи коммивояжера как задачи комбинаторной оптимизации началось с работы [39]. Обзоры [59, 63, 64[ и книги [67, 62] содержат описание основных достижений в исследованиях данной задачи.

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

Задачу коммивояжёра на минимум будем обозначать TSPmw, задачу на максимум

TSP,,(([.с

Как известно [70], для задачи ТЯР,,«,, в общем виде существует порог пеприбли-жаемостп в классе полиномиальных алгоритмов (в предположении Р ф 1\Р).

Для метрической задачи коммивояжера па минимум (длины рёбер графа удовлетворяют неравенству треугольника) известен полиномиальный 3/2-приближеппый алгоритм Кристофпдеса-Сердюкова [37], [23].

Активно исследуемый частный случаи этой задачи — задача коммивояжера в евклидовом пространстве. Задача коммивояжера называется евклидовой, если вершинам заданною графа сопоставлены точки в евклидовом пространстве Лк, а длины дуг между вершинами определяются как расстояния между точками, соответствующими этим вершинам.

Для евклидовой задачи коммивояжёра па минимум, в случае когда вершины графа являются независимыми одинаково распределёнными точками в единичном квадрате, в работах [71] и [30] исследовалось отношение длины оптимального цикла к квадратному корню из числа вершин графа. Установлено, что такое отношение является константой.

Для задачи коммивояжера на минимум в евклидовом пространстве существует РТАБ [26], позволяющая для любого с > 0 получить (1 + г)-точное решение с полиномиальной трудоёмкостью.

Для другого распространённого частного случая задачи коммивояжёра предполагается, что на входе задан полный д-вершиппый случайный граф, расстояния между вершинами которого независимые одинаково распределённые случайные величины.

В [21] представлен вероятностный анализ алгоритма "Иди в ближайший пеирой-деииый город" для приближённою решения задачи коммивояжёра на минимум в

случае, когда веса рёбер имеют дискретное распределение рк = Pr{cj1 = /,'}, где к =

1,.. ., гп. Получено условие асимптотической точное! и алгоритма: (52 Vi) 1 =

В [13] и [50] рассмотрена задача коммивояжёра па минимум на непрерывных случайных данных в ограниченном интервале [а„,6„], а„ > 0, представлен полиномиальный алгоритм поиска приближённого решения. В случае равномерного распределения расстояний си Е [а„,Ьп] получены оценки относи тельной погрешности

ляется асимптотически точным при bn/a„ = o(n/lmi). В случае /^-распределения с параметрами 7 = 0 и о > 0 асимптотическая точность имеет место при Ь„/аи = о(па '1 niin(l, а)).

В [12] рассмотрен случай задачи TSP,,,,-,,, когда веса рёбер графа являются независимыми одинаково распределёнными случайными величинами, принимающими значения из неограниченной сверху области [а„,сс), а„ > 0 и распределёнными по нормальному пли показательному законам. Установлены оценки относительной погрешности, вероятности несрабатывания, а также условия асимптотической точности алгоритма, являющегося модификацией алгоритма ''Иди в ближайший непройдепиый город".

В [48] для задачи TSP„,7„ в полном ?)-вершинном неориентированном графе с весами рёбер, являющимися независимыми случайными величинами, равномерно распределёнными па отрезке [0. 1]. показано, что | f — f\ = о(1) при п —> оо, где J* ~ — значение целевой функции задачи на оптимальном решении, а / — значение целевой функции на приближенном решении, построенном полиномиальным алгоритмом, основанном на точном решении задачи о цикловом покрытии.

Перейдём к обзору результатов для задачи коммивояжёра па максимум. Для за-

к

/с=1 г—\

несрабатывания алгоритма дп = п 2. Алгоритм яв-

дачи коммивояжёра на максимум А.II. Сердюковым предложен ставший уже классическим 3/4-прпблпжённый полиномиальный алгоритм [24].

В статье [56] предложен полиномиальный рандомизированный алгоршм с оценкой ТОЧ1ЮС1И 25/33. котрый основан па идеях алгоритма Сердюкова [21]. Напомним. что некоторые действия рандомизированных алгоритмов основаны на случайном выборе. Для таких алгоритмов, как правило, под оценкой точности понимают её математическое ожидание. В работе [35] предложена дерандомнзацня этого алгоритма, однако полученный в результате этого детерменировапный алгоритм имеет более скромную оценку точности Gl/81. Кроме того, в статье [36] предложено улучшение алгоритма из |50|. позволяющее дост пгну i ь оценки точности 251/331 для рандомизированном) а. п ори тма. Наконец, в [73] приведены соображения, позволяющие дерандомизировать упомянутые алгоритмы, сохранив при этом оценки точности.

Для метрической задачи коммивояжёра на максимум известны полиномиальные алгоритмы с оценками точности 5/6 [10|. 7/8 — С)(п~1/'2) (рандомизированный) [57|. 7/8- 0(/Г1/3) 13-11 и 7/8 [60].

В работе |25| был представлен асимптотически точный алгоритм А решения задачи коммивояжера па максимум в /.-мерном евклидовом пространстве 7Zk. Трудоемкость алгоритма определялась трудоемкостью отыскания максимального паросо-четания в заданном графе. Получаемый гампльтопов цикл содержал все ребра данного паросочетаппя. В работе- [5[ была представлена модификация этого алгоритма, имеющая такую же опенку точности, но более простая в изложении. Несмотря на сходство подходов,, гампльтопов цикл, получаемый этим алгоритмом, строился иначе и не содержал ребер максимального паросочетаппя. за исключением, бы тт. можег. двух.

Естественным обобщением TSP является задача о двух пли более коммивояжерах. Такую задачу называют также задачей о т бродячих торговцах |61] (in-Peripatetic Salesman Problem, далее ш-PSP). Целью является нахождение в графе G таких т гампльтоновых циклов

Ни - ■■ • Нт с Е: Н, П Hj = 0. при / ф j,

что величина

Т71

к—\ edh

минимальна (максимальна).

Де Корт показал, что задача 2-PSP ЛгР-трудпа |45| сведечшем к пей задачи Га-мнльтонов путь. Аиа.тогпчпые аргументы могут быть применены к случаю ш-PSP при т > 2.

Рассматривают также модификацию задачи ш коммивояжёров с различными весовыми функциями маршрутов: ш\ : Е —> 7Z 1 , .. ., </',„ : Е —> , с целевой функцией

7II

А-—1 ieih

Будем обозначать ш-PSP,,,,,, задачу ш коммивояжёров на минимум, ш-PSP,,,,,.,. — на максимум. В обозначении задачи с различными весовыми функциями будем использовать верхний индекс г/, например ш-PSP'/,,()Т. Задачу на графе с весами рёбер из целочисленного отрезка [1.<у] будем обозначать n;-PSPmm[l, г/], задачу на графе с весами рёбер из множества {1.2} — ш-PSP,„ш{1.2}.

В работе [42] рассмотрены некоторые полиномиально разрешимые случаи задачи 2-PSP на минимум. Работы [43. 44. 45]. посвящены построению и анализу нижних и верхних оценок в задаче 2-PSP на минимум с целыо использования этих оценок в

методе ветвей п границ. В работе 110| применяется полиэдральный подход к решении;

m-PSP.

Для метрической задачи двух коммивояжёров на минимум построены приближённые алгоритмы с точностью 9/4 и временной сложностью О (л3) [1), а также 2-приблнженный алгоритм с временной сложностью О(ri2 log п) [2].

Задача 2-PSPm„,[l, q] может быть решена за 0(/г3) с гарантированной оценкой точности (4 + г/)/5 [6|.

Для задачи 2-PSP,,,,,, {1,2} предложены полиномиальные алгоритмы с оценками точности 1.37 [41]. 5/4 |1|. 11/9 [17|, 6/5 [6].

Для решения задачи 2-PSP,„„.r в работе |1| представлен приближённый полиномиальный алгоритм с оценкой точности 3/4 и временной сложностью 0(пЛ). В работе [17] представлен другой приближённый алгоритм с той же временной сложностью для этой задачи, по с улучшенной оценкой точности 7/9.

В [10] путём комбинирования 3/4-приближёнпого полиномиального алгоритма для 2-PSP,,,,,.,. и 5/(<7 + 4)-приближённого полиномиального алгоритма для 2-PSP;m„{l, </}, описанного в 16], достигается улучшенная оценка точности (3(/+2)/(4<у+ 1). Для q = 2 это даёт 8/9.

Для решения метрической задачи 2-PSP'/nin в работе |4] предложен алгоритм ^112/г, трудоемкости 0(пл).

Для задачи 2-PSP'/„,„{l. 2} с весами ребер 1 и 2 в работе [6] показана возможность получения алгоритма с оценкой точности (1 + ///2), где // является гарантированной точностью для задачи TSP,„,„{1. 2} . Поэтому, используя алгоритм с р' = 7/G из |0G] для решения TSP„„„{1.2} имеем решение задачи 2-Р5Р7',',„{1, 2} с оценкой точности 19/12. В работе [15] дан алгоритм А-/ъ с временной сложностью 0{пл) и гаранти-

ронянной оценкой точности 7/5. В настоящее время лучшим но точности (по не по трудоемкости) является алгоритм Л4/3 с временной сложностью O(ri') [IG] и гарантированной оценкой точности 4/3. Алгоритм использует технику зарядов, продуктивно применяемую для доказательства ряда структурных теорем в теории графов.

Для задачи 2-PSP'/,,,,, {1, 2} в работе [10] представлен полиномиальный алюрптм Ар с точностью р = j^rzт^- зависящей от точности // > 1 алгоритма Ар> (для аналогичной задачи на минимум). Разные оценки точности 19/12 > 7/5 > 4/3, упомянутые выше для задачи 2-PSPf„,„{l. 2}, соответствуют следующим оценкам точности /> дм я задачи 2-PSP'/„„, {1. 2}: 113/101 < 37/51 < 20/27

В случае графов в многомерном евклидовом пространстве, задача ш-PSP на максимум решается асимптотически точно с кубической трудоемкостью [3|.

В статье [7| представлен приближённый алюрптм с временной сложностью 0{тп2) для решения задачи ш-PSP,,,,,,, при 1 < ш < ri/4, на графе, веса ребер которого — независимые случайные величины с функцией равномерного распределения на отрезке [а„,6„], «„ > 0. Этот алгоритм асимптотически точен, если Ьп/а„ = o(n/d(n)), где d(n) = In 7? при 2 < т < Iii п и <!(п) = п° при 1и п < ш < и1'0, 0 < в < 1.

В настоящей работе рассмотрен частый случай задачи ш-PSP с различными весовыми функциями, когда этемеиты матрицы расстояний — независимые одинаково распределённые случайные величины, принимающие значения из неограниченной сверху области [о„,эс). «„ > 0, и распределённые по нормальному или показательному законам. Для решения этой задачи применяется алгоритм из [7[. Показано, что асимптотическая точность этою алгоритма имеет место при выполнении условия /Ww» = °(п/(1(п))- ГД° (1(>>) = 1п" П1)И - ^ 111 < Iй 11 п (Кп) = п° ПРИ Ьт» < ш < н1~°.

15

О < 0 < 1. Здесь 3„ - паралич]) а„ или <т„, соответственно для показательного и нормального распределений.

В [47] предложена постановка задачи т коммивояжёров, с ограничениями пропускной способности рёбер (///-Capacitated Peripatetic Salesman Problem, m-CPSP). являющаяся обобщением задачи ///-PSP. В m-CPSP на полном неориентированном взвешенном графе С, каждое ребро г которого имеет заданную пропускную способность С\ 6 {1.2.....///}. требуется найти /// гамильтоновых циклов экстремального

суммарного веса, при эюм никакое ребро с не может быть использовано более С, раз.

Очевидно, что если все пропускные способности рёбер единичны, задача m-CPSP совпадем' с задачей m-PSl\ отк\да следует NP-трудность ///-CPSP.

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

В диссертации приведены новые полиномиальные ал горит мы решения и обоснованы оценки их точности дли четырёх модификации задачи 2-CPSP (рассматриваются задачи на минимум и максимум, с общей и различными весовыми функциями маршрутов). Предполагаен-м. что каждое ребро с графа имеет пропускную способность С( = 2 с вероятностью р и С, = 1 с вероятностью (1 —])). а веса рёбер графа принимают значении из целочисленного сегмента {1.2,. . . е/} (из отрезка [1. г/]). Общей чертой всех приведённых алгоритмов является использование решения задачи коммивояжёра (TSP) при построении решения задачи 2-CPSP. поэтому приведённые алгоритмы требуют наличия некоторого полиномиального Д-прпб. шжёппого алгоритма решения задачи коммивояжёра на минимум или максимум, в зависимости от типа задачи 2-CPSP.

Алгоритмы решения задач 2-CPSP па минимум с общей и различными весовыми функциями маршрутов, имеют гарантированную оценку точности в среднем (и p)A+(i-p)q Графов (. достаточно большим числом вершин. Алюршмы решения задач 2-CPSP на максимум с общей и различными весовыми функциями марптру-

(1 т«)д + (т~н)/г/ ,

тов имеют гарантированную оценку точности в среднем -———^—-LLJ- для графов с достаточно большим числом вершин.

В частности, с использованием 7/б-прнблпжепного алгоритма решения задачи TSP,„in{l,2} из [60], для задач 2-CPSr„„„{l, 2} и 2-CPSP?„în{l, 2} получены гарап-тироваипые оценки точное!и алгоритмов 1 в среднем. Алгоритмы решения задач 2-CPSP„mr{l, 2} и 2-CPSPfn„f {1, 2}, использующие алюритм решения задачи TSP„mr{1.2} с оценкой 1 очноеги 8/9 из [10], имеют га1)аитироваипую оценку точности в среднем 2']ь'/'-

Также, в диссертации рассматривается другая известная задача маршрутизации - задача маршр\ iизацпи транспортных средств, в которой клиенты A^i,....A„ и склад У представлены вершинами некоторого рёберпо-взвешеппого графа. Заявки всех клиентов единичны. Предполагается, что имеется неограниченное количество транспортных средств заданной вместимости к € N. Маршрут каждою транспортного средства (тур) начинаемся и заканчиваемся на складе У, при чюм число клиентов, обслуживаемых одним ivpoM. не должно превосходить к. Стоимость решения полатается равной сумме весов рёбер в,сеч туров. Необходимо удовлетворить заявки всех клиентов, минимизируя при этом стоимость решения. Впервые задача была сформулирована в работе [10]. В литературе эта задача известна под названием Unit Demand Vehicle Ronting Problem, и далее мы б\дем использовать для её обозначения аббревиатуру VRP. Для обозначения задачи VRP при вместимости транспортных

средств равной к часто используют выражение Á-YRP.

Задача 2-YRP полиномиально разрешима. Для нахождения решения необходимо построить паросочетанпе минимального веса. В работе [54| показана NP-трудность задачи к-УRP при к > 3.

В работе |58| предложен 4-приблпжённыи полиномиальный алгоритм решения 3-YRP(6eis ограничений па веса рёбер).

В работе [551 предложен (5/2 — 3/2Аг)-прнближёиный полиномиальный алгоритм решения метрической к-УRP. В работе |29| для мет])Нческой задачи 3-VRP предложен полиномиальный рандомизированный алгоритм с оценкой точности 197/99 +с. Ve > 0.

В работе [11] рассмотрена вероятностная постановка задачи A-VRP, в ко юрой веса рёбер (дуг) входного графа являются независимыми случайными величинами с общем"! функцией распределения. Предложен полиномиальный алгоритм нахождения приближённого решения и условия его асимптотической точности.

В диссертации исследуется задача маршрутизации транспортных средств па евклидовой плоскости. Для угон задачи в ст;иье [54| исследовалась возможность построения приближенного решения с гарантированной точностью. Была предложена нижняя оценка оптимального решения, использующая естественную связь YRP с соответствующей задачей коммивояжёра (TSP). Па основе этой оценки для случая фиксированного значения к построена полиномиальная аипроксимационпая схема (PTAS). Позже, в [27] предложена PTAS с лучшими характеристиками.

В статье [54] для нахождения приближённого решения задачи YRP (для произвольного к = к(и)) на полном графе предложена эвристика ITP (iterated tonr partitioning). также демонстрирующая связь задач YRP и TSP. Данная эвристика

получает на вход некоторое ренкчше задачи коммивояжера на графе с п + 1 вершиной (// клиентов плюс депо задачи YRP). Решение задачи TSP разбивается па участки, содержащие не более к вершин, которые затем используются при построении маршрутов транспортных средств задачи YRP, трудоёмкость этих построений составляет 0(п2).

В статье [54] проводился вероятностный анализ евклидовой VRP в предположении, что места размещения клиентов определяются случайно расположенными точками на плоскости, и к является функцией от числа клиентов п. Было показано, что предложенная нижняя оценка является асимптотически точной в случае к = o(\fn) или л = о(к2). Прямым следствием этого факта является асимптотическая точность эвристики ГГР в указанных случаях. В общем случае4 алгоритм ITP может приводить к решению, отличающемуся от оптимального в два раза.

В данной работе, также как и в статье [33], рассматривается естественная вероятностная постановка, в которой точки Х\,.. . ,X„,Y соответствуют одинаково распределённым на плоскости случайным величинам с известным законом распределения.

При такой постановке в [331 показано, что эвристика fTP с вероятностью 1 является (2 — с)-приб.тпжёппым алгоритмом решения задачи VHP (с > 0) в том случае, когда склад и клиенты являются независимыми случайными величинами с равномерным распределением на круге единичной площади, если число клиентов стреми гея к бесконечности. Установленное авторами [33] значение константы с составляет 0.015, однако в обосновании есть некоторая неточность, завышающая это значение примерно в три раза.

В диссертации показана (2 — ¿^-приближённость (с % 0.004) эвристики JTP с вероятностью 1 для слу чая равномерного распределения па круге единичной площади

при число клиентов, стремящемся к бесконечности.

Глава 1

Задача нескольких коммивояжёров с входными данными специального вида

1.1 Постановка задачи

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

Список литературы диссертационного исследования кандидат наук Истомин, Алексей Михайлович, 2015 год

Литература

[1] Агеев А. А., Бабурин А. Е., Гимади Э.Х. Полиномиальный алгоритм с оценкой точности 3/4 для отыскания двух непересекающихся гамилыоновых циклов максимального веса // Дискрета, анализ и иселед. онер., 13(2), 2000, С. 11-20.

[2] Агеев А. А., Пяткип А. В. Приближённый алгоритм решения метрической задачи о двух коммивояжёрах с оценкой точности 2 // Дискрета, анализ и исслед. опер., 10(4), 2009, С. 3 20.

[3] Бабурин А.Е., Гимади Э.Х. Об асимпготической точности эффективною алгоритма решения задачи /тг-РЭР на максимум в многомерном евклидовом пространстве // Труды ИММ УрО РАИ 2010, Т. 10. №3. С. 12-24.

[4] Бабурин А. Е., Гимади Э. X. , Коркишко И. М. . Приближенные алгоритмы для нахождения двух реберно непересекающихся гамильтоновых циклов минимального веса // Дискретный анализ и исследование операций, Сер. 2, 11(1), 2001, С. 11-25.

[5] Гимади Э. X. Новая версия асимптотически точного алюритма решения евклидовой задачи коммивояжера па максимум // Труды XII Байкальской между -

народной конференции. Методы оптимизации и их приложения. Т. 1. 2001. С. 117-124.

[G] Гимади Э. X., Глазков 10. В., Глебов А. Н. Приближенные ал1 оритмы решения задачи о двух коммивояжерах в полном графе с весами ребер 1 и 2 // Дискрсч. анализ и исслед. операций. Сер. 2, 14(2), 2007, С. 41—00.

[7] Гимади Э.Х., Глазков Ю.В., Цидулко О.Ю. Вероятностный анализ алгоритма решения трехиндексной m-слойной плапарной задачи о назначениях наодпоцик-личееких подстановках // Дискретный анализ и исследование операций, 2014, Том 21, № 1, С. 10-19.

|8] Гимади Э. X., Глебов II. II., Перепелица В. А. Алгоритмы с оценками для задач дискретной оптимизации // Проблемы кибернетики. 1975. JV" 31. С. 35—42.

[9] Гимади Э. X., Глебов П. И., Сердюков А. И. Об одной задаче выбора циклическою маршрута и загрузки транспортного средства // Дискретн. анализ и исслед. онер., сер. 2, 5:1 (1998), 12-18.

[10] Гимади Э.Х., ПвоиипаЕ. В. Приближённые алгоритмы решения задачи о двух коммивояжёрах па максимум // Дискретн. анализ и исслед. опер., 19(1), 2012, С. 17 32.

[11] Гимади Э X., Истоимн А. М., Рыков И. А., О задаче нескольких коммивояжёров с ограничениями на пропускные способности рёбер графа // Дискретн. анализ и исслед. опер.. 20, No. 5, 13-30 (2013).

[12] Гимади Э.Х., Ле Галл\ А., Шахпшеидер A.B. Вероятностный анализ одною алюритма приближенного решения задачи коммивояжера на неограниченных

сверху входных данных // Дискретный анализ и исследование операций, том 15, Л* 1, С. 23 43, 2008.

[13] Гпмади Э.Х., Перепелица В.А. Асимптотический подход к решению задачи коммивояжёра // Сб. научи, тр. Вып. 12. Новосибирск. Ин-т математики СО АН СССР. 1974. С. 35 45.

[14] Гимади Э. X., Шахшнейдер A.B. Приближенные алгоритмы с оценками для задач маршрутизации на случайных входах с ограниченным числом клиентов в каждом маршруте // Автомат, и телемех., 2012, N° 2, 126-140.

[15[ Глебов А. II., Гордеева А. В., Замбалаева Д. Ж. Алгоритм с оценкой 7/5 для задачи о двух коммивояжерах па минимум с различными весовыми функциями. // Сибирские электронные математические известия. 2011. Т. 8. С. 296-309.

[16] Глебов А. Н., Замбалаева Д. Ж. Приближённый алгоритм решения задачи о двух коммивояжёрах на минимум с различными весовыми функциями // Дискрет, анализ и исслед. онер., 18(5), 2011, С. 11-37.

[17] Глебов А. Н., Замбалаева Д. Ж. Полиномиальный алгоритм с оценкой точности 7/9 для задачи о двух коммивояжёрах на максимум / / Дискретп. анализ и исслед. опер., 18(4), 2011, С. 17-48.

[18] ГэриМ., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 с.

[19] Косточка А. В., Сердюков А.И. Полиномиальные алгоритмы с оценками 3/4 и 5/6 для задачи коммивояжера па максимум // Управляемые системы: Сб. науч. тр. 1985. ?26. С. 55 59.

[20] Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир. 1985. 512 с.

[21] Перепелица В.А., Гимади Э.Х. Задача нахождения минимального гамильтоно-ва цикла в взвешенном графе // Дискретный анализ, Сб. научи, тр. Вып. 15. Новосибирск, Ин-т математики СО АН СССР. 1969. С. 57-65.

[22] Петров В. В. Предельные теоремы для сумм независимых случайных величин. М.: Наука, 1987.

[23] Сердюков А. II. О некоторых экстремальных обходах в графах // Управляемые системы: Сб. науч. тр. - 1984. 17. - С. 76-79.

[24] Сердюков А.И. Алгоритм с оценкой для задачи коммивояжера на максимум // Управляемые системы: Сб. науч. тр. 1984. ? 25. С. 80-86.

[25] Сердюков А. II. Асимптотически точный алгоритм для задачи коммивояжера на максимум в евклидовом пространстве // Методы целочисленной оптимизации (Управляемые системы). 1987. N° 27. С. 79 87.

[26] Arora S. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems // Journal of the ACM (JACM). - 1998. - Vol. 45. -issue 5. - P 753-782.

[27] Asano Т., Katoh N., Tamaki II., Tokuyama T. Covering points in the plane by k-tours: towards a polynomial time approximation scheme for general k // STOC '97 Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, P. 275-283.

[28] BaburinA.E., Delia CroeeF., GimadiE.K., GlazkovY.V., PuschosV.Th. Approximation algorithms for the 2-PSP with edge weights 1 and 2 // Discr. Appl. Math., 157(9), 2009, P. 1988-1992.

[29] Bazgan C., Ilassin R., Monnot J. Approximation algorithms for some vehicle routing problems ,// Discrete Applied Mathematics, Vol. 14G (1), 2005, P. 27- 42.

[30] Beardwood J., Halton J. L., Hammersley J. M. The shortest path through many points // Proc. Camb. Phil. Soc. v. 55, 1959, P. 299-327.

[31] BermanP., KarpinskiM. 8/7-approximation algorithm for (1,2)-TSP // Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm (SODA'OG). Miami, Florida, United States, January 200G. ACM New York, NY, USA, 200G, P. C41 G48.

[32] Bock F. Mathematical programming solution of traveling salesman examples // Recent Advances in Mathematical Programming / Ed. by R. L. Graves, P. Wolfe.New York: McGraw-Hill, 19G3.

[33] BompadreA., DrorM., OrlinJ.B. Probabilistic analysis of unit-demand vehicle routeing problems // J. Appl. Prob. v. 44, 2007, P. 259-278.

[34] Chen Z.-Z., Nagoya T. Iinpro\ed approximation algorithms for metric max TSP // Proc. ESA'05, 2005, pp. 179-190.

[35] Chen, Z.-Z., Okamoto, Y., Wang, L. Improved deterministic approximation algorithms for Max TSP. // Inform. Process. Lett. 95(2), 2005, 333 342.

[36] Chen, Z.-Z., Wang, L. An improved randomized approximation algorithm for Max TSP. // J. Comb. Optim. 9(4), 2005, 401-432.

[37] Christofides N. Worst-case analysis of a new heuristic for the traveling salesman problem: Tech. Rep. Technical Report CS-93-13: Carnegie Mellon University, 1976.

]38] Cook S.A. The complexity of theorem-proving procedures // Proc. 3rd Ann. ACM Symp. on Theory of Computing. 1971. P. 151-158.

[39] Dantzig G. B., Fulkerson D. R., Johnson S. M. Solution of a large scale salesman traveling problem // Oper. Res.1954.Vol. 2.Pp. 393-410.

[40j Dantzig G. B., Ramsel J. 11. The Truck Dispatching Problem // Management Sei., 6:1 (1959), 80-91.

[41] DeilaCroeeF., Paschos V. Th., Wolfler Calvo R. Approximating the 2-Peripatetic Tra\eling Salesman Problem // 7-th Workshop on modeling and algorithms for planning and scheduling problems, MAPSP 2005, Siena, Italy, June 6-10 2005. Brelin: Springer, 2005, P. 114-116.

[42] De Brey M. J. D., Volgenant A. Well-solved cases of the 2-peripatetic salesman problem // Optimization. 1997.Vol. 39, no. 3.Pp. 275-293.

|43] DeKort J.B.J. M. Lower bounds for symmetric A'-peripatetic salesman problems // Optimization, 22(1), 1991. P. 113-122.

[44] DeKort J. B. J. M. Upper bounds for the symmetric 2-peripatetic salesman problem / / Optimization. 1992. V. 23, N 4. P. 357-367.

I

II n f f Ii I Ml " II E!1 II 1EI

[45] De Kort ,1. B. J. M. A branch and bound algorithm for symmetric 2-peripatetic salesman problems // European J. of Oper. Res. 1993. P. 229-243.

[46] Duchenne E., Laporte G., Semet F. Branch-and-cut algorithms for the undirected m-peripatetic salesman problem // European J. of Oper. Res.2005. Vol. 162, no. 3.Pp. 700-712.

[47] Duchenne E., Laporte G., Semet F. The undirected m-Capacitated Peripatetic Salesman Problem. // European Journal of Operational Rcseaich, 2012, 223-3, P. 637-643.

[48| Frieze A.M. On random symmetric travelling salesman problems // Mathematics of Operations Research 2004, V. 29, N 4, P. 878 890.

[49] GabovvILN. An effcient reduction technique for degree-constrained subgraph and bidiiected network flow problems // Proc. 15th annual ACM symposium on theory of computing, (Boston, April 25-27, 1983). New York: ACM, 1983. P. 448-456.

[50] Gimadi Edward Kh. On some probability inequalities for some discrete optimization problems // Operations Research Proceedings 2005, Selected papers. International Conference OR 2005, Bremen, Berlin, Springer, 2006, P. 283 289.

[51] Gimadi Edward Kh. Approximation efficient algorithms with performance guarantees for some hard routing problems // Proc. II Int. Conf. "Optimization and Applications"(OPTIMA-2011), Petrovac / Montenegro, Sept. 25 - Oct. 2, 2011, P. 98-101.

[52] Gimadi E. K., Serdukov A. I. A problem of finding the maximal spanning connected subgraph with given vertex degrees 11 Operations Research Proceedings 2000,

Selected Papers. International Conference OR 2000, Heidelberg / Ed. by F. B. at al.Springer, Berlin, 2001.Pp. 55-59.

[53] GutinG., PunnenA.P. (eds.) The Traveling Salesman Problem and its Variations // Kluwcr Academic Publishers. Dortrecht, Boston, London. 2002. 830 pp.

[54] Haimovich AL, Rinnooy Kan A. II. G. Bounds and heuristics for capacitated routeing problems // Math. Operat. Res. v. 10, 1985, P. 527-542.

[55] Ilaimovich M., Rinnooy Kan A. II. G., StougieL. Analysis of heuristics for vehicle routing problems //B.L. Golden, A.A.Assad Vehicle Routing Methods and Studies. Elsevier, Amsterdam, 1988. P. 47 01.

[5G| Hassin, R., Rubinstein, S. Better approximations for max TSP. // Inform. Process. Lett. 75(4), 181-186 (2000).

[57] Ilassin R., Rubinstein S. A 7/8-Approximatron Approximations for Metric Max TSP. // Information Processing Letters, 81 (2002) 247-251.

[58] Hassin R., Rubinstein S. On the complexity of the k-customer vehicle routing problem // Operation Research Lett. 2010. V. 33. P. 71 76.

[59] Junger M., Reinelt G., Rinaldi G. The Traveling Salesman Problem // Handbook on Operations Research and Management Sciences. Network Models / Ed. by M. Ball, T. Magnanti, C. L. Monma, G. L. Nemhauser.Amsterdam: North Holland, 1995.Vol. 7.Pp. 225 330.

[60] Kowalik L., Mucha M. Deterministic 7/8-approximation for the metric maximum TSP // Theoretical Computer Science v.410, i. 47-49, 2009, P. 5000- 5009.

[61] KrarupJ. The peripatetic salesman and some related unsolved problems // Combinatorial programming: methods and applications (Proc. NATO Advanced Study Inst., Versailles, 1974). 1975. P. 173 178.

[62] LawlerE. L„ Lenstra.J. K., Rinnoy Kan A. II. G., ShrnoysD. B. (eds.) The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization // Wiley, Chichester, 1985. 463 pp.

[63] Melamed I. I., Sergeev S. I., Sigal I. K. The traveling salsinan problem - i. thoretical issues // Automat. Remote Control. 1989.Pp. 1147—1173.

[64] Melamed I. I., Sergeev S. I., Sigal I. K. The traveling salsman problem, approximation algorithms // Automat. Remote Control.1990.Pp. 1159—1479.

[65] Menger K. Das botenproblem // Ergebnisse Eines Viathematischen Kolloquiums.1932.no. 2.Pp. 11 12.

[66] PapadimitriuC.il., YannakakisM. The travelling salesman problem with distance One and Two // Math. Oper, lies., 18(1), 1993. P. 1-11.

[67] Reinelt G. The Traveling Salesman: Computational Solutions for TSP Applica tions.Berlin: Springer-Verlag, 1994.

[G8] Robinson J. B. On the hamiltonian game: a traveling salesman problem: Tech. rep.: RAND Research Memorandum RM-303, 1949.

[69] Roskind J., TarjanR. E. A note on Piding minimum-cost edge-disjoint spanning trees // Math. Oper. Res., 10(4). 1985. P. 701-708. ACM New York, NY. USA, 200G. P. 641-648.

[70] Sahni S., Gonzalez T. P-complete approximation problems // ,J. ACM, 23: P. 555565,1970.

[71] Verblnnsky S. On the Shortest Path through a Number of Points. // Proe. Amer. Math. Soc. v. 2, 1951, P. 904-913.

[72] WolfterC.R., CordoneR. A Heuristic Approach to the Overnight Security Service Problem // Computers and Operations Research 30 (2003), 1269-1287.

[73] van Zuylen A. Multiplying Pessimistic Estimators: Deterministic Approximation of Max TSP and Maximum Triangle Packing. // Discrete Applied Mathematics 161(13-14), 2013, 2142-2157.