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

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

Истомин Алексей Михайлович

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

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

АВТОРЕФЕРАТ

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

2 е АПР 2019

Новосибирск — 2015

005567777

005567777

Работа выполнена в Федеральном государственном бюджетном учреждении науки Институте математики им. C.JI. Соболева Сибирского отделения Российской академии наук.

Научный руководитель:

Гимади Эдуард Хайрутдинович, доктор физико-математических наук, профессор.

Официальные оппоненты:

Ильев Виктор Петрович, доктор физико-математических наук, Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Омский государственный университет им. Ф.М. Достоевского», математический факультет, кафедра прикладной и вычислительной математики, профессор;

Пащенко Михаил Георгиевич, кандидат физико-математических наук, Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Новосибирский национальный исследовательский государственный университет», механико-математический факультет, кафедра теоретической кибернетики, доцент.

Ведущая организация: Федеральное государственное бюджетное учреждение науки «Институт математики и механики им. H.H. Кра-совского Уральского отделения Российской академии наук».

Защита состоится 20 мая 2015 года в 16 часов 30 минут на заседании диссертационного совета Д 003.015.01 при Федеральном государственном бюджетном учреждении науки Институте математики им. С. Л. Соболева Сибирского отделения Российской академии наук по адресу: 630090, г. Новосибирск, пр. Академика Коптюга, 4.

С диссертацией можно ознакомиться в библиотеке Института математики им. С.Л. Соболева Сибирского отделения Российской академии наук и на сайте math.nsc.ru.

Автореферат разослан " ^ " апреля 2015 г.

Учёный секретарь диссертационного совета

д.ф.-м.н.

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

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

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

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

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

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

Исследованы частные случаи задачи о нескольких коммивояжёрах с ограничениями на число повторений рёбер (m-Capacitated Peripatetic Salesman Problem, m-CPSP): задачи 2-CPSP на минимум и максимум с весами рёбер из целочисленного сегмента {1,д} как с общей, так и с различными весовыми функциями маршрутов. В отличие от классической задачи нескольких коммивояжёров, в ш-CPSP каждое ребро может быть использовано более чем в одном гамильтоновом цикле цикле, однако число использований не должно превосходить величины

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

Рассмотрена задача маршрутизации транспортных средств (Vehicle Routing Problem, VRP). Для решения задачи известна эвристика ITP (Iterated Tour Partitioning). Эта эвристика является 2-приближённым алгоритмом в случае детерминированных входных данных и (2 — с)-приближённым алгоритмом (с > 0) в случае, если координаты вершин графа являются независимыми случайными величинами с равномерным распределением на единичном квадрате. В диссертации оценка точности (2 — с) эвристики ITP была обоснована для равномерного распределения в круге единичной площади.

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

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

Апробация работы. Основные результаты диссертации докладывались на Международных научных студенческих конференциях (Новосибирск, 2008, 2010), на XV Байкальскй международной школе-семинаре "Методы Оптимизации и их Приложения"(Иркутск, 2011), на Всероссийской конференции "Проблемы оптимизации и экономические приложения" (Омск, 2012) на Международном симпозиуме по комбинаторной оптимизации СО-2012 (Великобритания, Оксфорд, 2012), на Европейской конференции по комбинаторной оптимизации ECCO-XXVI (Франция, Париж, 2013), на Международной конференции по Дискретной оптимизации и исследованию операций DOOR-2013 (Новосибирск, 2013), на XVI Байкальскй международной школе-семинаре "Методы Оптимизации и их Приложения" (Иркутск, 2014), на Международной конференция "Интеллектуализация обработки информации"(Греция, о. Крит, 2014), на научных семинарах Института математики им. C.JI.

Соболева.

Публикации. По теме диссертации автором опубликовано 11 работ, в том числе 4 статьи в журналах из списка ВАК.

Структура и объем работы. Диссертация изложена на 101 странице, содержит введение, три главы, заключение, список публикаций автора по теме диссертации, благодарности и список литературы, содержащий 73 наименований.

Основные результаты диссертации.

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

2. Для четырёх модификаций задачи 2-СРЯР впервые получены полиномиальные алгоритмы с гарантированными оценками точности в среднем.

3. Доказано, что ранее известная эвристика 1ТР является (2 — с)-приближённым алгоритмом (с > 0) решения задачи УИР в случае равномерного распределения вершин графа на круге.

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

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

В частности, вводится понятие точности алгоритма: приближенный алгоритм А решения массовой задачи оптимизации называется р-приближенным алгоритмом решения (алгоритмом с гарантированной оценкой точности р) для некоторого р > О, если для произвольного входа I со строго положительным оптимумом верно:

для задачи на минимум и задачи на максимум, соответственно. Здесь А(1) — значение целевой функции на решении, построенном алгоритмам А, Opíp(^) — значение целевой функции на оптимальном решении.

Кроме того, вводится понятие алгоритма с оценками (еп,5п), впервые представленное в [3], которое часто используется при вероятностном анализе алгоритмов. Говорят, что алгоритм А имеет оценки (еп, 5п) в классе экстремальных задач размерности п, если для каждого п выполнены следующие неравенства:

где Pr(S) — вероятность соответствующего'события S, еп — относительная погрешность алгоритма А, 8п — вероятностью несрабатывания алгоритма А. Говорят, что алгоритм с оценками (еп,5п) асимптотически точен, если еп —> 0 и 5п —> 0 при п —» с».

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

В разделе 1.1 приводится постановка задачи. Целью задачи о т бродячих торговцах (m-Peripatetic Salesman Problem with different weight functions, далее m-PSP-DW) является нахождение в графе G таких m реберно-непересекающихся гамильтоновых циклов Hi,..., Нгп с Е, чтобы минимизировать (максимизировать) их суммарный вес

А{1)

<Р

т

w(H1,...,Hm) = Y/ Y, wk(e)-

fc=1 е€Нк

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

В статье [2] представлен приближённый алгоритм А с временной сложностью 0(тп2) для решения задачи т-Р8Р-Б\¥, 1 < т < п/4, на графе, веса ребер которого — независимые случайные величины с функцией равномерного распределения на отрезке [а„, Ьп], ап > 0, найдены условия его асимптотической точности.

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

В разделе 1.2 приводится описание алгоритма А. Основная идея заключается в последовательном построении обхода для каждого коммивояжёра, при этом каждое однажды использованное ребро помечается как запрещённое для использования в дальнейшем. Так, для торговца i, 1 < i < т, алгоритм находит частичный путь (цепь) из п — 4г рёбер, применяя принцип "иди в ближайший непройденный город" тг—4г раза. Затем с помощью вспомогательной процедуры Р# частичный путь достраивается до гамильтонова цикла, при этом пополняется множество запрещенных рёбер для последующих циклов, с тем чтобы получаемые алгоритмом гамильтоновы циклы реберно не пересекались.

В разделе 1.3 приведён вероятностный анализ алгоритма, ключевую роль в котором играет теорема Петрова [5]. Анализ проведён для двух распределений: усечённого нормального, функция плотности которого имеет вид

Г 2 ( {х-ап)2\ , . I —. ехр--—=— , если ап < х < оо,

У 0, иначе

и показательного распределения с плотностью

{1 ( х-ап\

— ехр--, если ап < х < оо,

ап V «п /

О, иначе.

В следующей теореме показаны оценки точности алгоритма А на

графе с весами рёбер, распределёнными согласно усечённому нормальному распределению:

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

1) 2 < т < Inn,

~fcrn/an\ _т ап / п \

2) Inn < т < п1-6

(ап/ап\ —ш2/2 °п / в\

£Ä = 0{—^)> 6Ä = e '' если

где в £ (0,1) — некоторая постоянная, такая что рассматриваемый интервал для т существует.

Аналогично, теорема 2 даёт оценки точности алгоритма А на графе с весами рёбер, распределёнными согласно показательному распределению:

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

1)2<т< Inn,

оГафЛ * -(ЗЛИ.+6/4, если ^ =

\n/lnn J л ап Vinn/

2) Inn < m < п1'9

ед = 0(£фЛ J_ = n-(3/4m+6/4)) если

V 71 / fljj

где в € (0,1) — некоторая постоянная, такая что рассматриваемый интервал для тп существует.

Во второй главе исследуется задача об т коммивояжёрах на минимум и максимум с ограничениями на число повторений рёбер, весами рёбер из целочисленного сегмента {1, q}, с общей и различными весовыми функциями их маршрутов. В англоязычной литературе эта задача известна как m-Capacitated Peripatetic Salesman Problem, мы для её обозначения будем использовать аббревиатуру m-CPSP.

В разделе 2.1 приводится постановка задачи. В задаче m-CPSP на полном неориентированном взвешенном графе G, каждое ребро е которого имеет заданную пропускную способность Се S {1,2,..., т}, требуется найти тп гамильтоновых циклов экстремального суммарного веса, при этом никакое ребро е не может быть использовано более Се раз. Впервые эта задача сформулирована в работе [11]. Очевидно, что если все пропускные способности рёбер единичны, задача m-CPSP совпадет с задачей m-PSP, откуда следует NP-трудность m-CPSP.

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

В диссертации исследуются частные случаи задачи, а именно задача о двух коммивояжёрах с ограничениями на пропускные способности рёбер с общей весовой функцией маршрутов (2-CPSP) и различными весовыми функциями маршрутов (2-CPSP-DW).

Исследование задачи начинается со следующего замечания, демонстрирующего естественную связь задач 2-PSP и 2-CPSP:

Замечание 1 В ряде случаев, результаты, полученные для задачи 2-PSP, могут быть использованы для 2 -CPSP.

Соображения по обоснованию данного замечания в диссертационной работе позволяют утверждать, что представленные в [1] 9/4-приближ-ённый полиномиальный алгоритм решения метрической задачи 2-PSP на минимум и 12/5-приближённый полиномиальный алгоритм решения метрической задачи 2-PSP-DW (с различными весовыми функциями маршрутов) на минимум находят решение соответствующих задач 2-CPSP с сохранением заявленных оценок точности. Очевидно, что всякое решение 2-PSP является решением 2-CPSP и всякий алгоритм, решающий 2-PSP, даст допустимое решение 2-CPSP, но сохранение оценки точности для полученного решения не всегда имеет место, поскольку оптимум задачи 2-CPSP может сильно отличаться от оптимума задачи 2-PSP.

В разделах 2.2 - 2.5 приведены новые алгоритмы решения и обоснованы оценки их точности для четырёх модификаций задачи 2-CPSP

(рассматриваются задачи на минимум и максимум, с общей и различными весовыми функциями маршрутов, веса рёбер графа лежат в целочисленном отрезке {1, д}). Общей чертой всех приведённых алгоритмов является использование решения задачи коммивояжёра (ТЯР) при построении решения задачи 2-СРБР, поэтому приведённые алгоритмы требуют наличия некоторого А-приближённого алгоритма решения задачи коммивояжёра на минимум или максимум.

В разделе 2.2 приводится описание алгоритмов Ап^п{1, и для решения задачи 2-СР8Р (с общей весовой функцией) на минимум и максимум соответственно. На первом этапе алгоритмов строится Д-приближённое решение задачи коммивояжёра. Полученный гамильтонов цикл берётся в качестве Н\ — пути первого коммивояжёра задачи 2-СР8Р. Для построения пути второго коммивояжёра используется вспомогательная процедура 1, которая строит гамильтонов цикл Н2, используя при этом ребра цикла Н\ только с пропускной способностью 2.

Возможность построений процедуры 1, а также необходимые свойства таких построений доказаны в следующей лемме (через П{Н\) обозначается подмножество всех рёбер множества Н\, пропускная способность которых равна двум):

Лемма 1 Процедура 1 по данному гамилътонову циклу II1 строит, гамильтонов цикл Н2, удовлетворяющий следующим условиям:

1. Н2 не содержит ребер Н\ \ О(Нх).

2. Н2 содержит все ребра 0(Н{) за исключением, может быть, одного ребра ё. При этом для веса ребра ё верно следующее:

• Для задачи на минимум: если вес ё меньше <7, то Н2 содержит не более чем 7 рёбер веса д; вес остальных рёбер меньше.

• Для задачи на максимум: если вес ё больше 1, то Ы-2 содержит не более чем 7 рёбер веса 1; вес остальных рёбер больше.

В разделе 2.3 приведён анализ алгоритмов АтгП{ 1,д} и Агпах{1, q\ в среднем. Предполагается, что в графе С пропускные способности рёбер — независимые бернулиевские случайные величины с вероятностью успеха р. То есть, каждое ребро независимо от остальных имеет пропускную способность 2 с вероятностью р и пропускную способность

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

Для дальнейшего анализа полезной оказывается следующая лемма, дающая относительную оценку веса рёбер с пропускной способностью два:

Лемма 2 Пусть Н1 — гамилътонов цикл первого этапа алгоритма Атггп{1, я} или Атах{ 1, ц). Математическое ожидание суммарного веса рёбер Нх с пропускной способностью два составляет рМ^^х).

Величиной х обозначим отношение п/\У{Н*), где Н* — оптимальное решение задачи 2-СРБР на данном графе С?. Если веса рёбер принимают значения из целочисленного сегмента {1,<7}, имеем 1/(25) < х < 1/2. Это соотношение верно как для задачи на минимум, так для задачи на максимум.

Основные результаты раздела для задачи 2-СР8Р с общей весовой функцией представлены следующими двумя теоремами:

Теорема 3 Предположим, что в алгоритме АтгП{ 1,^} используется полиномиальный приближённый алгоритм решения ТЗР„^п{1, ц} с гарантированной оценкой точности А. Тогда в полном п-вершинном графе с весами рёбер из целочисленного сегмента {1,^} алгоритм Атгп{ 1)?} находит приближённое решение задачи 2-СР5Т>ГГи„{1, <7} с гарантированной оценкой точности р в среднем

п > щ; иначе,

если 1 + (А — q)p > 0; в противном случае.

Теорема 4 Предположим, что в алгоритме Атах{1,д} используется полиномиальный приближённый алгоритм решения ТЗРТпах {1, <?} с гарантированной оценкой точности Д. Тогда в полном п-вершинном графе с весами рёбер из целочисленного сегмента {1, д} алгоритм Атах{ 1,9} находит приближённое решение задачи 2-СР8Ртах{1,ц} с гарантированной оценкой точности р в среднем

( (1+р)Д+(1-р)д Р~\ (1+р)А+(21-р)д +'£

где

к 1 -р

1_\

\-д)р / >

р>

д

£(1+р)+ж(1-р), п>п0 (1 + р) + х(1 — р) — £, иначе,

где

е<±, п0 = { 1+г(1-зА)} ' если 1 + р(1 - дА) > О

2п , в противном случае.

В частности, если рассматривать графы с весами рёбер 1 и 2 (то есть положить д = 2), то для решения задачи коммивояжёра на минимум можно использовать 7/6-приближенный алгоритм, представленный в [14], а для решения задачи коммивояжёра на максимум — 8/9-приближенный алгоритм из [4]. В этом случае, теорема 3 даёт алгоритм решения задачи 2-СР8Р на минимум с оценкой точности 191~5р, при п > 1_75р. А теорема 4 даёт алгоритм с оценкой точности 25^7р для решения задачи 2-СРБР на максимум на графах такого вида, при

П > гг^г-.

~ 1-вр _

В разделе 2.4 приводится описание алгоритмов и

^тах{1><?} для решения задачи 2-СР8Р-Б\У (с различными весовыми функциями маршрутов) на минимум и максимум соответственно. Эти алгоритмы строят пару допустимых решений (Н\,Н%) и (//?, из которых затем выбирается лучшее.

На первом этапе алгоритмов строятся два А-приближённых решения для задачи коммивояжёра на графе С — Т\ и Т2, относительно весовой функций первого и второго маршрута соответственно. Гамиль-тонов цикл Т\ берётся в качестве Н\. Построение цикла Н)> ведётся с помощью процедуры 2 при использованием рёбер ТЬ, имеющих пропускную способность 2. Аналогично, гамильтонов цикл берётся в качестве Н$, а поиск цикла Щ ведётся с помощью процедуры 2 при использованием рёбер имеющих пропускную способность 2. На последнем этапе алгоритмов из полученной пары {Н\,Н\) и ) выбираем лучшее решение.

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

В разделе 2.5 приведён вероятностный анализ алгоритмов А.„¿„{1,?} и А^пах{1, д}. Доказываются теоремы, дающие оценки точности построенных в предыдущем разделе алгоритмов решения задачи 2-СР8Р-Б\У:

Теорема 5 Предположим, что в алгоритме 1,д} использует-

ся полиномиальный приближённый алгоритм решения Т8Ртт{1, д} с гарантированной оценкой точности Д. Тогда в полном п-вершинном графе с весами рёбер из целочисленного сегмента {1,д} алгоритм А^п{ 1,д} находит приближённое решение задачи 2-СРБР-с гарантированной оценкой точности р в среднем

где

д_ Г тт{Д±|, 1+(д_д)р} , если 1 + (Д - д)р > 0;

г < —, п0

2п I 3+1

1-я

в противном случае.

Теорема 6 Предположим, что в алгоритме д} использует-

ся полиномиальный приближённый алгоритм решения Т5'Ртот{1, д} с гарантированной оценкой точности Д. Тогда в полном п-вершинном графе с весами рёбер из целочисленного сегмента {1,д} алгоритм ^тах{1><?} находит приближённое решение задачи 2-СРБР-В\¥тах{]-,я} с гарантированной оценкой точности р в среднем

(1 + р) + х{1 — р) — е, иначе,

^(1+р)+х(1-р), п>п0

р-1 #( где

п0 Л . если 1 + р{1 — дД) > 0

2п ) в противном случае.

Если рассматривать графы с весами рёбер 1 и 2, а для решения задачи коммивояжёра на минимум и на максимум применять соответственно 7/6-приближенный алгоритм [14] и 8/9-приближенный алгоритм [4], то из теорем 5 и 6 следует существование приближённых алгоритмов с оценками точности 1Э~5р и 25^7р для решения задачи 2-СР8Р на минимум и максимум, при п > \ и п > 7; соответственно.

1 6? 1 9Р

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

В разделе 3.1 представлена постановка задачи. Рассматривается евклидова задача маршрутизации транспортных средств, в которой клиенты Х\,...,Хп и склад Y представлены точками на плоскости, и для вычисления расстояния между ними используется евклидова метрика. Заявки всех клиентов единичны. Предполагается, что имеется неограниченное количество транспортных средств заданной вместимости Q g N. Маршрут каждого транспортного средства (тур) начинается и заканчивается на складе У, при этом число клиентов, обслуживаемых одним туром, не должно превосходить Q. Стоимость решения полагается равной сумме длин всех туров. Необходимо удовлетворить заявки всех клиентов, минимизируя при этом стоимость решения. В литературе эта задача известна под названием Euclidean Unit Demand Vehicle Routing Problem, и далее мы будем использовать для её обозначения аббревиатуру VRP. Впервые задача была сформулированна в работе [8]. В работе [12] показана NP-трудность задачи VRP.

В той же статье для нахождения приближённого решения задачи VRP предложена эвристика ITP (iterated tour partitioning), также демонстрирующая связь задач VRP и TSP. Данная эвристика получает на вход некоторое решение задачи коммивояжёра на графе с п + 1 вершиной — п клиентов и депо задачи VRP. Решение задачи TSP под-разбивается на участки, содержащие не более Q вершин, которые затем используются при построении маршрутов транспортных средств задачи VRP.

Эта эвристика является 2-приближённым алгоритмом в случае детерминированных входных данных [12] и (2 — с)-приближённым алгоритмом (с > 0) в случае, если координаты вершин графа являются независимыми случайными величинами с равномерным распределением на единичном квадрате [7]. В настоящей работе оценка точности (2 — с) эвристики ITP была обоснована для равномерного распределения в круге единичной площади.

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

В разделе 3.2 приводится сводка результатов из [7] и [6], вводятся определения и обозначения, необходимые для формулировки основных результатов. Далее, через G„(c) будем обозначать количество точек среди Х\,..., Хп, имеющих соседа на расстоянии не более с/^/п.

В разделе 3.3 доказывается ключевой результат для дальнейшего анализа — оценка величины Gn(c) на графе с вершинами, независимо

равномерно распределенными на единичном круге:

Лемма 3 Пусть Х\,... ,Хп,... — последовательность независимых случайных величин, имеющих равномерное распределение на круге единичной площади. Для любого р е (0,1] существует константа с(р) > 0; такая что

причём в качестве с{р) можно выбрать любое число из промежутка

Используя результат леммы 3, на основании результатов из [6] и [7], изложенных в разделе 3.2, доказывается основной результат главы:

Теорема 7 Пусть У, Х\,..., Хп,... — последовательность независимых, одинаково распределённых точек плоскости, имеющих равномерное распределение на круге единичной площади. Тогда

Список литературы

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

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

[3] Гимади Э. X., Глебов Н. И., Перепелица В. А. Алгоритмы с оценками для задач дискретной оптимизации // Проблемы кибернетики.

где с = шах 0<р<1

{i^V^-2?)}« 0-0004.

1975. № 31. С. 35-42.

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

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

[6] BeardwoodJ., HaltonJ.L., Hammersley J.M. The shortest path through many points // Proc. Camb. Phil. Soc. v. 55, 1959, P. 299327.

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

[8] Dantzig G. В., Ramser J. H. The Truck Dispatching Problem // Management Sci., 6:1 (1959), 80-91.

[9] DeKortJ.B.J.M. Lower bounds for symmetric /("-peripatetic salesman problems // Optimization, 22(1), 1991. P. 113-122.

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

[11] DuchenneE., LaporteG., SemetF. The undirected m-Capacitated Peripatetic Salesman Problem. // European Journal of Operational Research, 2012, 223-3, P. 637-643.

[12] HaimovichM. Rinnooy. Kan A. H. G. Bounds and heuristics for capacitated routeing problems // Math. Operat. Res. v. 10, 1985, P. 527-542.

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

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

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

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

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

[2] Гимади Э.Х., Истомин A.M., Рыков И.А., О задаче нескольких коммивояжёров с ограничениями на пропускные способности рёбер графа с различными весовыми функциями // Вестник НГУ: Математика, механика, информатика., 14, No. 3, 3-18 (2014).

[3] Гимади Э.Х., Истомин A.M., Рыков И.А., Цидулко О.Ю. Вероятностный анализ приближённого алгоритма для решения задачи о нескольких коммивояжёрах на случайных входных данных, неограниченных сверху // Тр. Ин-та математики и механики УрО РАН., 20, No. 2, 88-98 (2014).

[4] Истомин А. М. Вероятностный анализ одной задачи маршрутизации // Дискретн. анализ и исслед. опер., 21, No. 4, 41-52 (2014).

Тезисы и труды конференций

[5] Гимади Э.Х., Истомин A.M., Рыков И.А., Цидулко О.Ю. Об асимптотической разрешимости задачи m коммивояжеров на случайных входах, неограниченных сверху // Материалы десятой международной конференции "Интеллектуализация обработки информации". Греция, о. Крит, 6-10 октября 2014 г. с. 78-79

[6] Гимади Э.Х., Истомин A.M., Рыков И.А. Задача о двух коммивояжерах на графе с ограниченными пропускными способностями ребер // Материалы XVI Байкальской международной школы-семинара "Методы оптимизации и их приложения". Иркутск, 30 июня - б июля 2014 г. с. 43 http: / / sei.irk.ru/conferences/mopt2014/disopt.html

[7] Гимади Э.Х., Истомин A.M., Рыков И. А. О задаче нескольких коммивояжёров с ограничениями на пропускные способности рёбер графа // Материалы международной конференции "Дискретная оптимизация и исследование операций". DOOR-2013, Новосибирск, Академгородок, 24 — 28 июня 2013. - Новосибирск: Изд-во Института математики СО РАН, 2013. С. 129.

[8] Gimadi E.Kh., Istomin A.M., Rykov I.A. On Approximation Polynomial Algorithm for the 2-Capacitated Peripatetic Salesman Problem // Proc. of 26th Conference of the European Chapter on Combinatorial Optimization (Paris, France, May 30 - June 1). -France, 2013. - P. 120.

[9] Gimadi E.Kh., Istomin A.M., Rykov I.A. On Approximation Polynomial Algorithm for the Capacitated Peripatetic Salesman Problem // Proc. of International Symposium on Combinatorial Optimization 2012 (University of Oxford, UK, September 17-19, 2012). - United Kingdom, 2012. - P. 62.

[10] Гимади Э.Х., Истомин A.M., Рыков И. А. О задаче маршрутизации с ограничениями на пропускные способности рёбер графа // Материалы V Всероссийской конференции "Проблемы оптимизации и экономические приложения". Омск, 2 — 6 июля 2012. Материалы конференции. - Омск: Изд-во Ом. гос. ун-та. С. 116.

[11] Истомин A.M., Залюбовский В.В. Вероятностный анализ одной задачи маршрутизации // Труды XV Байкальской международной школы-семинара "Методы оптимизации и их приложения". Т. 4: Дискретная оптимизация. Иркутск: РИО ИДСТУ СО РАН, 2011. С.129-133.

Подписано в печать 31.03.2015 г. Печать цифровая. Бумага офсетная. Формат 60x84/16. Усл. печ. л. 2

Тираж 100 экз. Заказ № 255 Отпечатано в типографии «Срочная полиграфия» ИП Малыгин Алексей Михайлович 630090, Новосибирск, пр-т Академика Лаврентьева, 6/1, оф.104 Тел. (383) 217-43-46, 8-913-922-19-07