Модифицированная реализация алгоритма метода ветвей и границ для решения асимметричной задачи коммивояжёра

Фомичёв Михаил Игоревич

СОДЕРЖАНИЕ
Введение
Глава 1. Современное состояние задачи коммивояжёра и алгоритмов её решения
1.1. Постановка задачи коммивояжёра
1.2. Обзор алгоритмов решения асимметричной задачи коммивояжёра
1.2.1. Точные алгоритмы решения асимметричной задачи коммивояжёра
1.2.2. Приближенные алгоритмы решения задачи коммивояжёра
1.3. Описание алгоритма метода ветвей и границ для решения асимметричной задачи коммивояжёра
1.4. Краткие выводы по главе
Глава 2. Системный анализ метода ветвей и границ для решения задачи коммивояжёра
2.1. Описание особого случая работы метода ветвей и границ
2.2 Сложность индивидуальной задачи коммивояжёра
2.3 Классификация индивидуальных задач по матрицам номеров порядка
2.4. Программная – аппаратные характеристики тестового окружения
2.5. Результаты исследования матриц номеров порядка
2.6. Количество изменений направлений ветвлений в поисковом дереве решений
2.7. Недостатки алгоритма метода ветвей и границ для решения задачи коммивояжёра
2.8. Краткие выводы по главе
Глава 3. Способы ускорения работы программной реализации метода ветвей и границ
3.1. Подходы к нивелированию недостатков метода ветвей и границ
3.2. Использование дополнительной памяти
3.3. Структуры данных для обслуживания поискового дерева решений
3.4. Предвычисленный тур
3.4.1. Постановка задачи по оптимизации использования предвычисленного тура
3
3.4.2. Оценка рациональности использования предвычисленного тура
3.4.3. Метаэврестические алгоритмы для нахождения предвычисленного тура.
3.5. Краткие выводы по главе
Глава 4. Построение и анализ модифицированной РЕАЛИЗАЦИИ алгоритма метода ветвей и границ для решения задачи коммивояжёра
4.1. Постановка задачи на внедрение
4.2. Сравнение синтетических и реальных данных
4.3. Хранение матриц в листьях поискового дерева
4.4. Организация доступа к листьям поискового дерева решений
4.5. Предвычисленный тур
4.6. Итоговая модифицированная реализация алгоритма метода ветвей и границ
4.7. Краткие выводы по главе
Заключение
Список литературы
Приложение 1. Справка об использовании результатов диссертационной работы компанией ООО «Группа КИТ»
Приложение 2. Справка об использовании результатов диссертационной работы в грантах РФФИ
Приложение 3. Справка об использовании результатов диссертационной работы в учебном процессе НГТУ им. Р.Е. Алексеева
Приложение 4. Справка об использовании результатов диссертационной работы в учебном процессе НИУ ВШЭ

В введении обосновывается актуальность диссертационной работы, формулируется цель и задачи исследования, аргументируется научная новизна и практическая значимость исследования, а также обозначены основные положения, выносимые на защиту.
Первая глава (Современное состояние задачи коммивояжёра и алгоритмов её решения). Первое упоминание задачи коммивояжера в научных трудах встречается на Венской конференции 1930 году в тезисах работы Karl Menger. В 1954 году Dantzig G., Fulkerson R. и Selmer J. предложили первый алгоритм для решения задачи коммивояжёра, позднее данная работа легла в основу алгоритма Гомори. Однако, время работы данного алгоритма было крайне высоким.
В 1962 году Held M. и Karp R.M. и, независимо от них, Bellman R. предложили использовать технику динамического программирования для решения задачи коммивояжёра (в последствии этот алгоритм стал называться «Held–Karp алгоритм»). Этот алгоритм стал работать быстрее алгоритма Dantzig G., Fulkerson R. и Selmer J., однако требовал большего объема потребления оперативной памяти.
В аспекте точного решения этой задачи в 1963 Little J.D.C., Murty K.G., Sweeney D.W. и Karel C. предложили применить метод ветвей и границ (который в свою очередь был предложен Land A.H., Doig A.G. в 1960 году) для решения асимметричной задачи коммивояжёра. В 1987 году Padberg M. и Rinaldi G. продемонстрировали реализацию метода ветвей и отсечений (который применяется для решения задач целочисленного программирования) для решения задач коммивояжёра большой размерности. Кроме того, неоднократно принимались попытки по распараллеливанию метода ветвей и границ для решения задачи коммивояжёра. Большой прогресс в этом направлении внесли Сигал И.Х., Бабинская Я.Л., Посыпкин М.А.
В 1970-х годах Held M. и Karp R.M. спроектировали алгоритм, основанный на построении минимальных остовных деревьев подграфа графа решаемой задачи коммивояжёра, однако, для общего случая время решения задачи не удалось
сократить (хотя впоследствии алгоритм хорошо себя зарекомендовал для решения евклидовой задачи коммивояжёра).
Одновременно с поиском точных алгоритмов решения задачи коммивояжёра, разрабатывались типизации этой задачи. В настоящее время рассматриваются следующие типы задач: симметричная, асимметричная, метрическая, евклидова. Изучение отдельных типов задач коммивояжёра позволило, на основе учета их особенностей, ускорить время их решения. Arora S. и Mitchell J.S.B. существенно продвинулись в изучении метрической и евклидовой задачи, что, в конце концов, позволило им разработать приближенную схему полиномиального времени (PTAS) для евклидовой задачи коммивояжёра. А Jonker R. И Volgenan T. в 1983 предложили алгоритм, с помощью которого любую асимметричную задачу можно трансформировать в симметричную (с увеличением размерности задачи).
Другим направлением исследования задачи коммивояжёра является разработка и анализ приближенных алгоритмов ее решения. Приближенные алгоритмы можно разделить на три семейства — жадные алгоритмы, роевые алгоритмы и алгоритмы, направленные на улучшения решения.
Наиболее известным и простым типичным представителем жадных алгоритмов является алгоритм ближайших соседей. Особый вклад в развитие роевых алгоритмов внесли работы Dorigo M., Stützle T., Hoos H.H. по муравьиным системам. Известны также такие алгоритмы, как «Капли дождя», предложенный Hamed Shah-Hosseini и «Пчелинные системы», основанный на работе Sato T. и Hagiwara M. К третьему семейству приближенных алгоритмов относятся такие алгоритмы как -opt (Lin. S, 1965), tabusearch (Gamboa D., Rego C., Glover F., 2005) и Lin – Kernighan (Lin S., Kernighan B.W., 1973) и его модификация Helsgaun в 2000 и 2017 годах.
Несмотря на обилие различных приближенных алгоритмов, нет причин отказываться от точного решения задачи коммивояжёра, если это возможно и оправдано. Опираясь на известные асимптотические оценки точных методов решения ATSP, в главе сделан вывод о целесообразности дальнейшего исследования метода ветвей и границ, как наиболее перспективного.
Таким образом, возникает задача разработки модифицированной реализации алгоритма метода ветвей и границ для решения асимметричной задачи коммивояжёра, обеспечивающей приемлемое время работы в диапазоне размерностей, актуальных для ряда прикладных задач логистики и бизнес- информатики.
Вторая глава (Системный анализ метода ветвей и границ для решения задачи коммивояжёра) начинается с рассмотрения неописанной авторами классического алгоритма (Little J.D.C., Murty K.G., Sweeney D.W. и Karel C.) ситуации в ходе работы метода ветвей и границ, когда в результате процесса ветвления, невозможно перейти из одной вершины поискового дерева решений в какую-либо другую. Иными словами, классический алгоритм метода ветвей и границ в процессе ветвления может привести к пустому множеству допустимых решений в некоторой вершине поискового дерева. В матрице стоимостей эта ситуация будет представлена строкой или столбцом, состоящим из бесконечных
значений. Эта особая ситуация не была рассмотрена ранее в литературных источниках.
При возникновении такой ситуации, которая может приводить как к зависанию программы, так и к получению некорректного решения, возникают два естественных вопроса: когда необходимо реагировать на такую ситуацию и что делать в случае её возникновения? Предлагается два возможных варианта решения:
1. В процессе приведения матрицы стоимостей проверять, не является ли минимальным значением в столбце или в строке бесконечность. Тогда можно игнорировать данную вершину в дереве решений и переключится на следующую вершину с минимальной стоимостью (вернуться к стандартной схеме работы алгоритма).
2. При каждом запрете перехода проверять, существуют ли в столбце и в строке, на пересечение которых запрещается переход, значения отличные от бесконечности. Если в строке и в столбце будут существовать отличные от бесконечности значения, то запрет возможен. В противном случае — запрет невозможен и эту вершину дерева решений можно больше не учитывать. Более того, если мы нашли такую пару вершин графа, для которых запрет перехода невозможен, то такая дуга обязательно должна быть включена во все допустимые туры данного подмножества решений.
В главе рассматривается машинно-независимая характеристика метода ветвей и границ — «сложность индивидуальной задачи коммивояжера». Характеристика основана на идеях D. Knuth, и содержательно есть количество вершин поискового дерева решений, порожденных алгоритмом метода ветвей и границ в ходе решения индивидуальной задачи. Заметим, что на число порожденных вершин непосредственно влияет метод выбора дуги ветвления. В классической реализации (Little J.D.C., Murty K.G., Sweeney D.W. и Karel C.) выбирается дуга, максимизирующая нижнюю оценку множества решений, в которое эта дуга не включается (далее в работе этот метод выбора дуги будет обозначаться как «ARS»).Другой, реализованный в работе подход к выбору дуги ветвления состоит в поиске первого нулевого элемента последовательным проходом по строкам в текущей приведённой матрице стоимостей (далее — метод «APS»). Введём обозначение С ( ) для сложности индивидуальной задачи, заданной матрицей A, где X – метод выбора дуги ветвления, ∈ ( , ). Т.е. обозначение С ( ) есть сложность индивидуальной задачи коммивояжёра, заданной матрицей стоимостей A, с методом выбора дуги APS. Характеристика С ( ) позволяет абстрагироваться от времени решения задачи на конкретной программно-аппаратной реализации и перейти к машинно-независимой оценке.
Далее в главе вводится новая машинно-независимая характеристика индивидуальной задачи коммивояжера, представляющая собой функционал качества поискового дерева решений — количество изменений направлений ветвлений в поисковом дереве решений в результате выбора следующей вершины для процесса ветвления в ходе работы алгоритма метода ветвей и границ. Обозначим эту характеристику ( ), где ∈ ( , ). Так же, как и С ( ) эта
характеристика зависит от метода выбора дуги ветвления в поисковом дереве решений.
Все эксперименты в работе проводились на персональном компьютере с процессором Intel i7 8700K 4700 МГц и 32 ГБ оперативной памяти под управлением операционной системы Linux Arch.
На рисунке 1 a) показаны результаты экспериментального исследования по
зависимости (полученные по результатам расчетов для 105 индивидуальных
синтетических задач для каждой размерности) корреляции Спирмена ( ) от
размера задачи n, а на рисунке 1 b) – значения корреляции Спирмена ( ) со временем решения задачи.
Предложенная характеристика J ARS ( A) имеет хорошую корреляцию со
временем решения задачи коммивояжёра и будет использоваться далее.
Затем в главе обозначаются ключевые недостатки алгоритма метода ветвей и границ, а именно высоко ресурсозатратная операция по изменению направления обхода поискового дерева решений и отсутствие возможности усекать поисковое дерево решений до нахождения первого кандидата на позицию оптимального
тура.
a) b)
Рисунок 1: а) корреляция (по Спирмену) значений С ( ) и ( ) от размерности задачи n
b) корреляция (по Спирмену) значений ( ) и ( ) от размерности задачи n
В результате, во второй главе на основе использования методов системного анализа, выявлен особый случай метода ветвей и границ, предложена новая машинно-независимая характеристика метода — количество изменений направлений ветвления в поисковом дереве решений и обозначены основные недостатки алгоритма метода ветвей и границ.
В третьей главе (Способы ускорения работы программной реализации метода ветвей и границ) исследуются способы ускорения работы программной реализации метода ветвей и границ, построенные путем нивелирования недостатков, обозначенных во второй главе. Рассмотрение начинается с возможности использования дополнительной памяти для хранения усеченных матриц в вершинах поискового дерева решений, которое строится в ходе работы метода.
Каждая вершина поискового дерева решений соответствует множеству допустимых туров с известной нижней оценкой этого множества. Из каждого листа поискового дерева решений могут порождаться на основе выбора дуги ветвления две новые вершины, соответствующие турам, которые включают дугу

ветвления, и тем циклам, которые не включают эту дугу. Для двух новых листьев необходимо найти нижнюю оценку для каждого множества, что связано с приведением текущей матрицы (со сложностью ( 2)). Классическая реализация метода ветвей и границ предполагает при переходе к другому листу поискового дерева решений усечение матрицы стоимостей, начиная с исходной (со сложностью (h 2), где h — глубина текущего листа).
Уменьшение времени работы программной реализации может быть достигнуто либо путем хранения усеченных матриц во всех вершинах поискового дерева решений (ARSmatrices_in_all_nodes), либо хранением усеченных матриц только в листьях поискового дерева решений (ARSmatrices_in_leaves).
Оба подхода позволяют не перевычислять усеченную матрицу стоимостей, что существенно ускоряет время работы.
На рисунке 2 а) и 2 b) представлены результаты экспериментального исследования на синтетических данных (среднее время решения задачи и требуемая оперативная память соответственно). Экспериментальные данные показали, что при хранении усеченных матриц стоимостей в листьях поискового дерева решений программная реализация работает быстрее, чем при хранении усеченных матриц во всех вершинах. Уже, начиная с размерности 43, наблюдается прирост в производительности по сравнению с классической реализацией более чем в 2 раза. С другой стороны, объём требуемой памяти растёт экспоненциально с ростом размерности задачи.
a) b)
Рисунок 2: а) Экспериментальные результаты по времени работы программной реализации
алгоритмов метода ветвей и границ с хранением усеченных матриц на синтетических данных b) Экспериментальные результаты по затратам оперативной памяти алгоритмов метода ветвей и границ с хранением усеченных матриц на синтетических данных
Далее в работе рассматриваются способы организации доступа к листьям поискового дерева решений. Метод ветвей и границ предполагает после выполнения ветвления поиск листа поискового дерева решений с минимальной нижней границей. Однако, классическая реализация не уточняет алгоритм поиска. Могут быть использованы два подхода:
— осуществлять трассировку всего поискового дерева решений;
— хранить листья в отдельной структуре данных.
Задача трассировки всего поискового дерева решений является весьма
трудоёмкой операцией, и поэтому выглядит малоперспективной, по сравнению со вторым подходом. Для второго подхода возникает вопрос: «В какой структуре данных стоит хранить листья поискового дерева решений?».
Были рассмотрены и исследованы следующие структуры данных, как реализации очереди с приоритетом: упорядоченный список, двоичная (бинарная)

12
куча, самобалансирующиеся двоичные (бинарные) деревья поиска (например, красно − чёрные деревья и АВЛ − деревья).
Эти структуры данных поддерживают все необходимые операции и обладают нужными свойствами. Кроме того, сложность операции по получению минимального элемента может быть сведена к (1), если кэшировать минимальный элемент. Более того, эти структуры данных имеют линейную оценку требуемой памяти ( ), где — количество хранимых элементов. Сложность остальных операций, которые используются в алгоритме метода ветвей и границ, представлены в таблице 1.
Проведенный анализ сложности операций в худших случаях для рассмотренных структур данных не позволил сделать однозначные выводы о том, какая из структур данных является наиболее предпочтительной, поэтому было принято решение о проведении экспериментального исследования.
Таблица 1 – Сложность операций над структурами данных в худшем случае
Операция Упорядоченный список
Удаление наименьшего элемента O(k) Получение наименьшего элемента O(1) Вставка элемента O(k) Удаление элементов, чьи ключи
больше, чем заданное значение
Двоичная куча O(log k)
O(1) O(k)
O(k log k).
Самобалансирующееся двоичное дерево
O(log k) O(1) O(log k)
O(k log k).
O(k)
На рисунке 3 (а, b) показаны результаты экспериментов для метода ветвей и границ с использованием двоичной кучи (ARSheap), упорядоченного списка (ARSordered_vector) и самобалансирующегося двоичного дерева (в качестве представителя данного класса структур данных используется красно-чёрное дерево) (ARSRBT), кроме того, для сравнения представлены результаты работы реализации метода ветвей и границ без хранения списка вершин, при этом поиск вершины дерева решений с минимальной границей осуществляется посредством обхода дерева решений (ARStraverse_tree).
a) b)
Рисунок 3: a) Время работы реализации алгоритма метода ветвей и границ при использовании
разных способов доступа к листьям поискового дерева решений
b) Время работы реализации алгоритма метода ветвей и границ с разными структурами данных при для доступа к листьям поискового дерева решений
Экспериментальные результаты показали, что трассировка дерева решений для поиска листовых элементов является неоправданно сложной модификацией алгоритма. За исключением двоичной кучи, использование которой даёт худший

 ARSeffective
 tARS (n)tARS(n)
результат для всей рассматриваемой выборки, выбор между упорядоченным списком и самобалансирующимся двоичным деревом не оказывает существенного влияния на время работы программной реализации алгоритма. При этом лучший результат до n=29 показывает упорядоченный список, а начиная с n = 30 – самобалансирующееся дерево. Такой результат объясняется тем, что потребность в операции вставки элемента в очередь с приоритетом растёт с размерностью задачи, а сложность этой операции у красно-черного дерева, в худшем случае, минимальная по сравнению с другими рассматриваемыми структурами данных.
Затем в главе рассматривается использование начального приближения для алгоритма метода ветвей и границ. Классический метод ветвей и границ не предполагает наличие какого-либо тура в момент начального запуска, поэтому сначала многократно проводится процедура ветвления, порождаются вершины поискового дерева, а исключение вершин из рассмотрения не ведется. В зависимости от особенностей индивидуальной задачи, число вершин дерева решений может быть довольно большим к моменту, когда будет найден первый тур. Использование тура, найденного заранее каким-либо приближенным методом, позволяет заранее начать исключение вершин из рассмотрения, в результате будет порождено меньшее число вершин дерева решений, что уменьшит сложность задачи и время поиска оптимального тура.
С другой стороны, на получение начального тура затрачивается время, и общее время расчетов будет складываться из времени, затраченного на поиск начального тура, и времени работы метода ветвей и границ с найденным туром (далее такой тур будет называться «предвычисленным туром»). Предвычисленный тур можно найти с помощью эвристического алгоритма. На основе этих рассуждений в работе формализована и поставлена задача оптимизации по критерию уменьшения времени работы модифицированной реализации алгоритма метода ветвей и границ в комбинации с метаэвристическими алгоритмами для решения задачи коммивояжера:
i
метода ветвей и границ с метаэвристическими алгоритмами для решения задачи коммивояжёра.
Сформулированный критерий оптимизации предполагает перебор метаэвристических алгоритмов. В работе, основываясь на известной классификации эвристических алгоритмов по трем семействам — жадные, роевые и улучшающие решения, проведено экспериментальное исследование над каждым типичным представителя каждого семейства, а именно: алгоритм ближайшего соседа, муравьиный алгоритм и алгоритм Lin-Kernighan-Helsgaun.
Обозначим = С ( ) отношение сложности индивидуальной задачи ( )
коммивояжера к сложности индивидуальной задачи
коммивояжераcпредвычисленным туром, где ( ) − сложность
t (n) = min t (n)
i=1,m ARSi
где ARSI ={ARSi |i =1,m} − множество претендующих комбинаций модификаций
,

индивидуальной задачи коммивояжёра, порожденная алгоритмом метода ветвей и границ, при условии, что до начала работы алгоритма известен такой тур (далее будем называть такой тур предвычисленным), стоимость которого в α раз больше оптимального решения. На рисунке 4 (a, b и c) показана экспериментально определенная зависимость  от α для разных размерностей (35, 40 и 45 соответственно).
На основе экспериментальных данных показано, что для существенного сокращения сложности индивидуальной задачи коммивояжёра (и, как следствие, времени работы алгоритма метода ветвей и границ) с использованием предвычисленного тура необходим предвычисленный тур, которой будет отличаться от оптимального не более чем на 2 – 4%.
a) b) c) Рисунок 4: Зависимость  от α для n = 35, 40, 45
Это подтверждает экспериментальное исследование количества изменений направлений обхода поискового дерева решений; если α = 1.025, то количество изменений направлений обхода поискового дерева решений не изменилось для всей экспериментальной выборки (если бы метод ветвей и границ запускали бы без предвычисленного тура).
Экспериментальные результаты показали, что алгоритм ближайшего соседа и муравьиный алгоритм не могут предоставить тур с точностью лучшей, чем 2.5% за допустимое время. Время работы алгоритма метода ветвей и границ в комбинации с Lin-Kernighan-Helsgaun алгоритмом для решения задачи коммивояжёра представлено на рисунке 5. Экспериментальные результаты также демонстрируют, что метод ветвей и границ в среднем работает быстрее с Lin- Kernighan-Helsgaun начиная с размерности n = 42. Кроме того, с ростом размерности доля задач, для которых комбинация с Lin-Kernighan-Helsgaun работает дольше, чем классическая реализация, уменьшается.
Таким образом, для решения задачи по разработке модифицированной реализации алгоритма метода ветвей и грани, которая решает асимметричную задачу коммивояжёра быстрее, чем классическая реализация, в работе предложены следующие подходы:
— хранение усечённых матриц в листьях поискового дерева решений;
— использование различных структур данных для доступа к листьям поискового дерева решений в зависимости от размерности решаемой задачи;
— использование предвычисленного тура, полученного эвристическим алгоритмом Lin-Kernighan-Helsgaun.

Рисунок 5: Экспериментальные результаты времени работы реализации алгоритма метода ветвей и границ в комбинации с алгоритмом LKH на синтетических данных
Четвёртая глава (Построение и анализ модифицированной реализации алгоритма метода ветвей и границ для решения задачи коммивояжёра) посвящена разработке и анализу модифицированной реализации алгоритма метода ветвей и границ для решения задачи коммивояжёра учитывающей особенности массива задач, предоставленных транспортной компанией.
Транспортная компания ООО «Лоял Лоджистикс» специализируется на различных автоперевозках. В ходе решения задачи планирования перевозок и распределения ресурсов, у компании возникает потребность в решении классической асимметрической задачи коммивояжёра размерностью от 25 до 55. На данный момент, для решения классической задачи коммивояжера используется приближенный жадный алгоритм, который показывая хорошие временные характеристики, однако находит решения с > 2.5, что существенно далеко от оптимального. Компания ставит условие по решению задач размерности до 55 в среднем за 3 секунды с максимально возможной точностью. При этом классический алгоритм метода ветвей и границ не обеспечивает такие временные характеристики. Для расчетов компанией был предоставлен набор индивидуальных задач размерностью от 25 до 55 с шагом 1. Для каждой размерности было предоставлено 100 000 различных задач. Элементы матриц стоимостей — целые числа в интервале от (0; 10 000).
На рисунке 6 (a, b, c) представлено сравнение запусков классического метода ветвей и границ по синтетическими данным и по реальным задачам.
a) b) c)
Рисунок 6: a) Время работы программной реализации классического метода ветвей и границ на синтетических и реальных данных
b) Средняя сложность индивидуальных задач для синтетических и реальных данных c) Количество изменений направления обхода для синтетических и реальных данных

Были рассчитаны различные показатели (время решения, сложность индивидуальной задачи и количество изменения направления обхода поискового дерева решений соответственно). Полученные экспериментальные данные позволяют говорить о близости результатов, полученных на синтетических данных к результатам на реальных задачах. Таким образом, предложенные в главе 3 оптимизации метода ветвей и границ для решения асимметричной задачи коммивояжёра, применимы и для реальных данных.
Подбор комбинаций модификаций метода ветвей и границ начнём с использования дополнительной памяти для хранения усеченных матриц. На рисунке 7 представлено время работы модификаций метода ветвей и границ с разными способами хранения усеченных матриц. Хранение усеченных матриц только в листьях поискового дерева решений даёт наилучший результат на всём рассматриваемом диапазоне.
Рисунок 7: Время работы реализации алгоритма метода ветвей и границ при использовании разных способов хранения усеченных матриц на реальных задачах
Следующим этапом работы был проведён экспериментальный анализ по использованию различных структур данных для организации доступа к листовым элементам поискового дерева решений. Эксперименты показали, что отсортированный список предпочтительней других структур данных в диапазоне задачи от n = 25до n = 31, а для диапазона от n = 32 до n = 55 стоит использовать красно-чёрное двоичное дерево. Данную комбинацию будем обозначать ARSeffective_II. На последнем этапе работы рассмотрено использование комбинированного алгоритма в сочетании с предвычисленным туром, полученным с помощью Lin-Kernighan-Helsgaun алгоритма. Результаты представлены на рисунке 8. Экспериментальные результаты показали обоснованность использования предвычисленного тура с помощью Lin-Kernighan- Helsgaun алгоритма начиная с размерности n = 42. Таким образом, на основе экспериментального исследования разработана модифицированная реализация алгоритма метода ветвей и границ для решения асимметричной задачи коммивояжёра (ARSeffective) со следующими свойствами:
− для всех размерностей задачи используется хранение усеченных матриц в листьях поискового дерева;
− в качестве структуры данных для хранения узлов поискового дерева решений следует использовать упорядоченный список до n = 31, а с n = 32− красно-чёрное дерево;
− начиная с n = 42 целесообразно использовать Lin-Kernighan-Helsgaun алгоритм для нахождения предвычисленного тура.

Рисунок 8: Сравнение времени работы программной реализации алгоритма ветвей и границ с расчётом предвычисленного тура с помощью Lin-Kernighan-Helsgaun и без него
Сравнение времени работы программной реализации классического алгоритма метода ветвей и границ и его модифицированной реализации представлено на рисунке 9. Разработанная программная реализация для размерности n = 55 укладывается в ограничение в 3 секунды по времени в среднем.
Рисунок 9: Сравнение времени работы классической и модифицированной реализации алгоритма метода ветвей и границ.
Таким образом, решена задача оптимизации по критерию времени работы программных реализаций алгоритма метода ветвей и границ с метаэвристическими алгоритмами для решения задачи коммивояжера, и предложены подходы для сокращения времени получения точного решения задачи коммивояжера методом ветвей и границ. Разработанное программное обеспечение для решения задачи коммивояжера модифицированным алгоритмом метода ветвей и границ используется в транспортной компании ООО «Лоял Лоджистикс».
В заключении сформулированы основные результаты, полученные в диссертационной работе.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ
В диссертационном исследовании на основе методологии системного анализа разработана и апробирована модифицированная реализация алгоритма метода ветвей и границ для решения асимметричной задачи коммивояжёра, доставляющая точное решение за приемлемое время для задач логистики и бизнес-информатики, и проведено её экспериментальное исследование. В ходе выполнения работы получены следующие основные результаты:
1. Выявлен особый случай метода ветвей и границ, неописанный ранее в научных работах.
2. Предложена новая машинно-независимая характеристика метода ветвей и границ для ATSP — количество изменений направления ветвления в поисковом дереве решений.
3. Формализована, поставлена и решена задача оптимизации по критерию уменьшения времени работы программной реализации алгоритма метода ветвей и границ в комбинации с метаэвристическими алгоритмами для решения задачи коммивояжера.
4. Предложены подходы для сокращения времени получения точного решения задачи коммивояжера алгоритмом метода ветвей и границ, в том числе, с использованием его комбинаций с метаэвристическими алгоритмами.
5. Разработано программное обеспечение модифицированного алгоритма метода ветвей и границ для решения асимметричной задачи коммивояжёра, которое внедрено в транспортную компанию ООО «Лоял Лоджистикс» как компонент решения задачи планирования перевозок и распределения ресурсов, использовалось при выполнении исследований по грантам РФФИ No16-07-00160 и No18-07-00656 . Также результаты внедрены в учебный процесс факультета «Компьютерных наук» Национального исследовательского университета «Высшая школа экономики» и института радиоэлектроники и информационных технологий Нижегородского государственного технического университета им. Р.Е. Алексеева.

Задача коммивояжера в общей постановке заключается в поиске гамильтонова цикла с минимальной суммой весов дуг в полном ориентированном асимметричном графе. Несмотря на простую постановку, задача коммивояжёра является NP – трудной [1]. Её исключительной особенностью является то, что для весьма небольшого, по современным меркам, объёма данных, время получения точного решения не приемлемо для большинства практических задач. Например, при размерности задачи (числе вершин полного графа) порядка 100, время получения точного решения хотя и сильно варьируется по набору весов дуг, но, в худшем случае, может составлять несколько суток. Более того, в настоящее время отсутствуют способы прогнозирования времени решения для конкретной задачи, и приходится довольствоваться только вероятностным прогнозом [2], [3].
Для ряда прикладных задач, таких как задачи о расписаниях, транспортные задачи и задачи планирования перевозок, календарное планирование работы устройств с учетом переналадок, оптимизация работы подъемных кранов, определение очередности прожигания прорезей при изготовлении микросхем, поиск оптимальной схемы прокладки кабелей вычислительных сетей, предсказание функций протеинов, построение черно-белых изображений непрерывной линией без пересечений, асимметричная задача коммивояжёра является подзадачей решаемой задачи [4], [5]. В процессе решения упомянутых задач могут генерироваться десятки и даже сотни вспомогательных частных задач коммивояжёра. Обилие метаэвристических методов решения задачи коммивояжера (например, наиболее известный метаэвристический алгоритм решения задачи — алгоритм Лина – Кернигана [6]) не означает отказа от возможности получения точных решений этой задачи. Наиболее известный точный алгоритм решения задачи коммивояжера основан на методе ветвей и границ [7]. Однако, время работы его программной реализации неприемлемо велико, особенно для случаев, когда дело касается принятия решения или простоя оборудования.
Из точных алгоритмов решения асимметричной задачи коммивояжёра (укажем алгоритмы, основанные на методе динамического программирования [8], [9], [10], остовных деревьях минимального веса [11], [12] и методе ветвей и границ [13]) хорошие временные характеристики имеет алгоритм, основанный на методе ветвей и границ. Метод был предложен в 1960 году Land A. и Doig A. [7], а в 1963 году применен коллективом авторов (Little J. D. C., Murty K. G., Sweeney D. W. и KarelC.) непосредственно для решения задачи коммивояжера [13]. Из иностранных исследователей, изучивших задачу коммивояжера, можно выделить: Alvim A. C. F. [14], Applegate D. L. [15], Arora S. [16], Bixby R. E. [15], Chvatal V. [15], Cook W. J. [15], Dorigo M. [17], Helsgaun K. [18], Hoos H. H. [19], Johnson D. S. [20], Jonker R. [21], Kernighan B. W. [6], Lin S. [6], Mitchell J. S. B. [22], Stützle T. [19], Taillard E. D. [23], Tinos R. [24], Volgenant T. [21], Whitley D. [24] В нашей стране свой вклад в исследование задачи коммивояжера и разработку алгоритмов её решения внесли Корбут А. А. [25], Курейчик В. В. [26], Курейчик В. М. [26], Леонтьев В. К. [27], Меламед И. И. [28], Мудров В. И. [29], Пантелеев А. В. [30], Посыпкин М. А. [31], Сергеев С. И. [28], Сигал И. И. [25] Финкельштейн Ю. Ю. [25], Штовба С. Д. [32] и другие исследователи.
Требование к уменьшению времени, необходимого на нахождения точного решения задачи коммивояжера, делает актуальной задачу системного анализа недостатков метода ветвей и границ и разработки такой его реализации, в частности для применения в асимметричных задачах коммивояжера, которая в диапазоне размерностей, актуальных для ряда прикладных задач логистики и бизнес-информатики, обеспечит нахождение точного решения за приемлемое время.
Целью диссертационной работы является разработка на основе результатов системного анализа модифицированной реализации алгоритма метода ветвей и границ, доставляющего точное решение для задач логистики и бизнес- информатики за приемлемое время, для решения асимметричной задачи коммивояжёра, и его экспериментальное исследование.
В соответствии с поставленной целью в диссертационной работе решены следующие задачи:
1. Обзор и анализ современного состояния задачи коммивояжера.
2. Системный анализ классической реализации метода ветвей и границ для решения задачи коммивояжера и выявление особенностей,
ведущих к его модификации.
3. Разработка модифицированных реализаций алгоритмов для
проведения сравнительного экспериментального исследования.
4. Проведение экспериментального исследования различных модифицируемых реализаций алгоритма метода ветвей и границ на
основе синтетических данных и анализ полученных результатов.
5. Подбор, на основе особенностей реальных задач логистики, рациональной комбинации предложенных модификаций алгоритма
метода ветвей и границ.
Объектом исследования в данной работе являются точные алгоритмы
решения асимметричной задачи коммивояжёра, реализующие метод ветвей и границ и их различные модификации в совокупности с метаэвристическими алгоритмами ее решения.
Предметом исследования является временная и ёмкостная характеристика модификаций точного алгоритма метода ветвей и границ для решения асимметричной задачи коммивояжёра.
Область исследования соответствует следующим пунктам паспорта специальности 05.13.01 — «Системный анализ, управление и обработка информации»:
п.2. Формализация и постановка задач системного анализа, оптимизации, управления, принятия решений и обработки информации. п.3. Разработка критериев и моделей описания и оценки эффективности решения задач системного анализа, оптимизации, управления, принятия решений и обработки информации.
п.4. Разработка методов и алгоритмов решения задач системного анализа, оптимизации, управления, принятия решений и обработки информации.
п.5. Разработка специального математического и программного обеспечения систем анализа, оптимизации, управления, принятия решений и обработки информации.
Методы исследования. Для достижения поставленных задач использовались методы теории графов, методы оптимизации, а также методы математической статистики.
Экспериментальное исследование проводилось с использованием программно – аппаратного комплекса, разработанного автором. Программное обеспечение реализовано на языках C и C++ с использованием стандартных библиотек.
Научная новизна диссертационной работы заключается в следующем:
1. Методами системного анализа разработаны новый критерий и модель оценки эффективности работы алгоритма метода ветвей и границ для решения задачи коммивояжёраоснованные наподсчёте количества изменений направлений ветвления в поисковом дереве решений, позволяющие сравнивать модификации алгоритма, отличающиеся от известных тем, что предложенный критерий является машинно − независимым и обладает высокой по Спирмену корреляцией со временем работы (соответствует областям исследования п. 3 паспорта
специальности).
2. На базе введенных критерия и модели эффективности работы
алгоритма метода ветвей и границ для решения задачи коммивояжёра, идентифицированы критические этапы алгоритма, алгоритмические подходы и эвристические стратегии, а также сформулирована задача структурно-параметрического синтеза оптимальной конфигурации точного алгоритма метода ветвей и границ по критерию уменьшения вычислительных издержек, которая, в отличии от известных, учитывает комплексное влияние различных факторов на общую эффективность работы алгоритма (соответствует областям исследования п. 2 паспорта специальности).
3. Подобрана комбинация модификаций алгоритма метода ветвей и границ для решения задачи коммивояжёра, которая удовлетворяет бизнес требованиям, отличающаяся от известных тем, что её подбор осуществлялся с учетом результатов экспериментального тестирования модификаций на реальных задачах (соответствует областям исследования п. 4 паспорта специальности).
Достоверность результатов диссертационной работы корректным использованием математического аппарата, проведенного экспериментального исследования, а также разработанного алгоритма и соответствующего программного обеспечения.
Практическая значимость работы обуславливается:
1. Разработанным программным обеспечением модифицированного
алгоритма метода ветвей и границ для решения асимметричной задачи
коммивояжера.
2. Возможностью подбора наиболее подходящей комбинации
модификаций алгоритма метода ветвей и границ, исходя из
размерностей реальных задач.
3. Обоснованием полученных экспериментальных результатов как на
синтетических, так и на реальных данных, с использованием предложенной автором оценки сложности индивидуальной задачи коммивояжёра.
4. Сокращением операционных издержек логистической компании при использовании разработанной модифицируемой реализации алгоритма
обеспечена результатами внедрением метода ветвей и границ для решения асимметричной задачи
коммивояжёра.
Сведения о внедрении результатов. Теоретические и прикладные
результаты диссертационной работы внедрены и подтверждаются актами о внедрении:
1. КомпаниейООО«ГруппаКИТ»вкомпаниюООО«ЛоялЛоджистикс» при непосредственном участии автора.
2. В учебный процесс департамента «Программная инженерия» факультета «Компьютерных наук» Национального исследовательского университета «Высшая школа экономики» в дисциплину «Конструирование программного обеспечения», а также при выполнении бакалаврских исследований.
3. В учебном процессе института радиоэлектроники и информационных технологий Нижегородского государственного технического университета им. Р.Е. Алексеева в лекционном курсе и лабораторных работах для студентов бакалавриата и магистратуры по направлениям 09.03.02 и 09.04.02 «Информационные системы и технологии» по дисциплинам: «Дискретная математика», «Методы оптимизации», «Теория принятия решений», «Основы CALS технологий».
Апробация результатов работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на следующих научно – технических семинарах и конференциях: Международная научно – техническая конференция «Современные информационные технологии и ИТ – образование» (Москва, 2015, 2016); Международная научно – техническая конференция «Информационные Системы и Технологии» (Нижний – Новгород, 2016, 2017, 2019, 2020, 2021); Всероссийская конференция молодых учёных по математическому моделированию и информационным технологиям (2019, Новосибирск), научный семинар Департамента программной инженерии факультета компьютерных наук НИУ ВШЭ (Москва, 2016 – 2017). Основные результаты работы были использованы при выполнении проектов, поддержанных РФФИ:
1. 16-07-00160: «Прогнозирование временных характеристик эффективных реализаций метода ветвей и границ для задачи коммивояжёра на основе характеристик случайных матриц и идентификации порожденного распределения времен», 2016 – 2018, под руководством д.т.н. Ульянова М. В.;
2. 18-07-00656: «Разработка эффективных алгоритмов решения задач транспортной и производственной логистики», 2018 – 2020, под руководством д.ф.-м.н. Лазарева А. А.
Основные положения, выносимые на защиту:
1. Новый подход к оценке сложности индивидуальных задач коммивояжёра и впервые выявленный особый случай метода ветвей и границ.
2. Подходы,обеспечивающиеуменьшениевремениработыметодаветвей и границ для решения задачи коммивояжёра.
3. Разработка и анализ модифицируемой реализации алгоритма метода ветвей и границ для решения асимметричной задачи коммивояжёра.
Личный вклад автора. Результаты теоретических и экспериментальных исследований, выносимые на защиту, принадлежат лично соискателю или выполнены непосредственно с научным руководителем. Программная реализация алгоритмов, проведение экспериментального исследования [2], [3], [33-53], обработка, анализ и интерпретация экспериментальных результатов [33], [35-37], [39], [42-51], [53], формализация новой характеристики метода ветвей и границ [48], [49], выявление особого случая работы метода ветвей и границ [44], [53] выполнены автором лично. При участии автора был выполнен статистический анализ задач коммивояжёра [3], [39-41], [43] [45] [52] и предложен способ обобщения задач коммивояжёра [38]. Публикации. По теме диссертации опубликовано 23 печатные работы, в том числе 8 статей в рецензируемых научных журналах из перечня ВАК РФ по специальности 05.13.01 [2], [3], [33-36], 2 статьи в изданиях, входящих в реферативную базу данных Scopus [2], [34], 5 статей в журналах из перечня ВАК РФ по другим специальностям [39-43], 3 статьи в других рецензируемых изданиях [44-46], 7 статей в трудах международных и всероссийских конференций [47-53].
Структура и объём диссертации. Работа состоит из введения, четырёх глав, заключения, списка литературы из 75 наименований и одного приложения. Полный объем диссертации составляет 119 страниц, включая 37 рисунков и 29 таблиц.

Заказать новую

Лучшие эксперты сервиса ждут твоего задания

от 5 000 ₽

Не подошла эта работа?
Закажи новую работу, сделанную по твоим требованиям

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

    Читать «Модифицированная реализация алгоритма метода ветвей и границ для решения асимметричной задачи коммивояжёра»

    Публикации автора в научных журналах

    Вероятностный прогноз сложности индивидуальных задач коммивояжера на основе идентификации распределения сложности по экспериментальным данным
    М.В. Ульянов, Г.Н. Жукова, М.И. Фомичёв, В.А. Головешкин // Автоматика и телемеханика: No – Москва, 2– С. 149-[Англ. версия] Ulyanov, M.V. Probabilistic Prediction of the Complexity of Traveling Salesman Problems Based on Approximating the Complexity Distribution from Experimental Data / M. Ulyanov, G.N. Zhukova, M. Fomichev, V.A. Goloveshkin // Automation and Remote Control: Vol. No. – Moscow, 2– P. 1296-1
    Сравнительный анализ комбинаций метода ветвей и границ с метаэвристическими алгоритмами для решения асимметричной задачи коммивояжёра
    М.В. Ульянов, М.И Фомичёв // Информационные технологии: т. 25, No – Москва, 2– С. 590-Фомичёв, М.И. Подходы к организации поискового дерева решений в методе ветвей и границ для асимметричной задачи коммивояжера [Текст] / М.И. Фомичёв, М.В. Ульянов // Информационные технологии: т. 24, No – Москва, 2– С. 698
    Использование квантильных коэффициентов асимметрии и эксцесса для оценки сложности решения задачи коммивояжера
    Г.Н. Жукова, М.В. Ульянов, М.И.Фомичёв, В.А. Головешкин // International Journal of Open Information Technologies: т. 4, No – Москва, 2– С. 131
    Эффективный по времени точный комбинированный алгоритм для асимметричной задачи коммивояжера
    Г.Н. Жукова, М.В. Ульянов, М.И. Фомичёв, // Бизнес-информатика: No 3(45). – Москва, 2– С. 20-[Англ. версия] Zhukova, G Exact time-efficient combined algorithm for solving the asymmetric traveling salesman problem / G. Zhukova, M. Ulyanov M., M. Fomichev // Business Informatics: No. 3 (45) – Moscow, 2–P. 20
    Оценка параметров распределения логарифма сложности задачи коммивояжера
    М.В. Ульянов, М.И. Фомичёв, В.А. Головешкин, Г.Н. Жукова // Современные информационные технологии и ИТ-образование: т. No – Москва, 2– С. 19-Жукова, Г.Н. Распределение логарифма сложности индивидуальных задач коммивояжера при фиксированной длине входа [Текст] / Г.Н. Жукова, М.В. Ульянов, М.И.Фомичёв, В.А. Головешкин // Современные информационные технологии и ИТ- образование: т. 12, No 3-– Москва, 2– С. 131
    Ресурсные характеристики способов организации дерева решений в методе ветвей и границ для задачи коммивояжера
    М.В. Ульянов, М.И. Фомичёв // Бизнес-информатика: No 4 (35). – Москва, 2– С. 38-[Англ. версия] Ulyanov, M.V. Resource characteristics of ways to organize a decision tree in the branch-and-bound method for the traveling salesmen problem / M.V. Ulyanov, M.I. Fomichev // Business Informatics: No. 4 (34). – Moscow, 2– P. 38-20

    Помогаем с подготовкой сопроводительных документов

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

    Хочешь уникальную работу?

    Больше 3 000 экспертов уже готовы начать работу над твоим проектом!

    Егор В. кандидат наук, доцент
    5 (428 отзывов)
    Здравствуйте. Занимаюсь выполнением работ более 14 лет. Очень большой опыт. Более 400 успешно защищенных дипломов и диссертаций. Берусь только со 100% уверенностью. Ск... Читать все
    Здравствуйте. Занимаюсь выполнением работ более 14 лет. Очень большой опыт. Более 400 успешно защищенных дипломов и диссертаций. Берусь только со 100% уверенностью. Скорее всего Ваш заказ будет выполнен раньше срока.
    #Кандидатские #Магистерские
    694 Выполненных работы
    Глеб С. преподаватель, кандидат наук, доцент
    5 (158 отзывов)
    Стаж педагогической деятельности в вузах Москвы 15 лет, автор свыше 140 публикаций (РИНЦ, ВАК). Большой опыт в подготовке дипломных проектов и диссертаций по научной с... Читать все
    Стаж педагогической деятельности в вузах Москвы 15 лет, автор свыше 140 публикаций (РИНЦ, ВАК). Большой опыт в подготовке дипломных проектов и диссертаций по научной специальности 12.00.14 административное право, административный процесс.
    #Кандидатские #Магистерские
    216 Выполненных работ
    Лидия К.
    4.5 (330 отзывов)
    Образование высшее (2009 год) педагог-психолог (УрГПУ). В 2013 году получено образование магистр психологии. Опыт преподавательской деятельности в области психологии ... Читать все
    Образование высшее (2009 год) педагог-психолог (УрГПУ). В 2013 году получено образование магистр психологии. Опыт преподавательской деятельности в области психологии и педагогики. Написание диссертаций, ВКР, курсовых и иных видов работ.
    #Кандидатские #Магистерские
    592 Выполненных работы
    Екатерина П. студент
    5 (18 отзывов)
    Работы пишу исключительно сама на основании действующих нормативных правовых актов, монографий, канд. и докт. диссертаций, авторефератов, научных статей. Дополнительно... Читать все
    Работы пишу исключительно сама на основании действующих нормативных правовых актов, монографий, канд. и докт. диссертаций, авторефератов, научных статей. Дополнительно занимаюсь английским языком, уровень владения - Upper-Intermediate.
    #Кандидатские #Магистерские
    39 Выполненных работ
    Мария М. УГНТУ 2017, ТФ, преподаватель
    5 (14 отзывов)
    Имею 3 высших образования в сфере Экологии и техносферной безопасности (бакалавриат, магистратура, аспирантура), работаю на кафедре экологии одного из опорных ВУЗов РФ... Читать все
    Имею 3 высших образования в сфере Экологии и техносферной безопасности (бакалавриат, магистратура, аспирантура), работаю на кафедре экологии одного из опорных ВУЗов РФ. Большой опыт в написании курсовых, дипломов, диссертаций.
    #Кандидатские #Магистерские
    27 Выполненных работ
    Ольга Б. кандидат наук, доцент
    4.8 (373 отзыва)
    Работаю на сайте четвертый год. Действующий преподаватель вуза. Основные направления: микробиология, биология и медицина. Написано несколько кандидатских, магистерских... Читать все
    Работаю на сайте четвертый год. Действующий преподаватель вуза. Основные направления: микробиология, биология и медицина. Написано несколько кандидатских, магистерских диссертаций, дипломных и курсовых работ. Слежу за новинками в медицине.
    #Кандидатские #Магистерские
    566 Выполненных работ
    Вики Р.
    5 (44 отзыва)
    Наличие красного диплома УрГЮУ по специальности юрист. Опыт работы в профессии - сфера банкротства. Уровень выполняемых работ - до магистерских диссертаций. Написан... Читать все
    Наличие красного диплома УрГЮУ по специальности юрист. Опыт работы в профессии - сфера банкротства. Уровень выполняемых работ - до магистерских диссертаций. Написание письменных работ для меня в удовольствие.Всегда качественно.
    #Кандидатские #Магистерские
    60 Выполненных работ
    AleksandrAvdiev Южный федеральный университет, 2010, преподаватель, канд...
    4.1 (20 отзывов)
    Пишу качественные выпускные квалификационные работы и магистерские диссертации. Опыт написания работ - более восьми лет. Всегда на связи.
    Пишу качественные выпускные квалификационные работы и магистерские диссертации. Опыт написания работ - более восьми лет. Всегда на связи.
    #Кандидатские #Магистерские
    28 Выполненных работ
    Яна К. ТюмГУ 2004, ГМУ, выпускник
    5 (8 отзывов)
    Помощь в написании магистерских диссертаций, курсовых, контрольных работ, рефератов, статей, повышение уникальности текста(ручной рерайт), качественно и в срок, в соот... Читать все
    Помощь в написании магистерских диссертаций, курсовых, контрольных работ, рефератов, статей, повышение уникальности текста(ручной рерайт), качественно и в срок, в соответствии с Вашими требованиями.
    #Кандидатские #Магистерские
    12 Выполненных работ

    Последние выполненные заказы

    Другие учебные работы по предмету