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

• Фомичёв Михаил Игоревич
• кандидат наук
• 2022

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

Глава 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.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. Справка об использовании результатов диссертационной работы в учебном процессе НИУ ВШЭ

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

ВВЕДЕНИЕ

Задача коммивояжера в общей постановке заключается в поиске гамильтонова цикла с минимальной суммой весов дуг в полном ориентированном асимметричном графе. Несмотря на простую постановку, задача коммивояжёра является ЫР - трудной [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. и Karel C.) непосредственно для решения задачи коммивояжера [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. Разработка специального математического и программного обеспечения систем анализа, оптимизации, управления, принятия решений и обработки информации.

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

Экспериментальное исследование проводилось с использованием программно - аппаратного комплекса, разработанного автором. Программное обеспечение реализовано на языках С и С++ с использованием стандартных библиотек.

Научная новизна диссертационной работы заключается в следующем:

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 таблиц.

ГЛАВА 1. СОВРЕМЕННОЕ СОСТОЯНИЕ ЗАДАЧИ КОММИВОЯЖЁРА И АЛГОРИТМОВ ЕЁ РЕШЕНИЯ

1.1. Постановка задачи коммивояжёра

Первое упоминание задачи коммивояжера в научных трудах встречается на Венской конференции 1930 году в тезисах работы Karl Menger [54].

Содержательная постановка задачи состоит в том, что торговому агенту (он же коммивояжер) необходимо посетить определенное количество городов с целью продажи или доставки товаров. Доподлинно известно, что в любой момент времени можно добраться из одного города в любой другой по дороге, проложенной между этими городами. Любой допустимый порядок посещения городов, при котором каждый город коммивояжёром посещается только один раз (за исключением начального, в которой надо вернуться), называется туром. Стоимости проезда между городами известны. Стоит заметить, что стоимость проезда туда и обратно, в общем случае, может различаться. Сама задача состоит в том, чтобы найти такой тур коммивояжера, чтобы его затраты на дорогу были минимальны. Так как количество городов ограничено, то и число туров конечно, поэтому задача может быть решена прямым перебором. Однако, такое множество всех допустимых туров будет содержать (п — 1)! тур, и время работы переборного алгоритма решения задачи становится для реальных размерностей задачи совершенно неприемлемым.

Постановка задачи в терминах теории графов строится путем ассоциации городов с вершинами графа, а путей сообщения между городами и стоимостей проезда — с нагруженными дугами. Таким образом, мы получаем полный ориентированный асимметричный граф (G) на n вершинах без собственных петель, заданный матрицей стоимостей А = (a^j). Отсутствие собственных петель

формализуется как а.ц = x>Vi = 1, п. Тогда задача формулируется как задача поиска гамильтонового цикла (покрывающего полного цикла) наименьшей

стоимости (который и называется туром) на полном ориентированном графе, заданном несимметричной (в общем случае) матрицей стоимостей А [55].

Размерностью задачи коммивояжёра п является число вершин исходного графа (изначальное количество городов, которые должен посетить торговый агент).

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

формализуется, как а^ = ^¿Л = 1,п\1 ф у. В процессе решения симметричной задачи коммивояжёра, исследователи разработали значительное количество приближенных алгоритмов её решения (например, алгоритм Ып-Кегт§Ьап [6], который будет рассматриваться далее по ходу работы). В связи с этим А. Допкег К и Уо^епап Т. в 1983 предложили алгоритм, с помощью которого любую асимметричную задачу можно трансформировать в симметричную (с увеличением размерности задачи в два раза) [21]. Это позволяет использовать любые наработки по симметричной задачи коммивояжёра для любой асимметричной задачи.

Если относительно весов рёбер симметричной задачи коммивояжёра выполняется неравенство треугольника (другими словами, в таких задачах «обходные» пути длиннее «прямых», что формализуется как

а^ < а.1к + ак^1,], к = 1,п\Ь ф ], к ф Ь,к ф у), то такую задачу называют метрической задачей коммивояжёра. Неравенство треугольника имеет естественный характер и, как следствие, метрическая задача чаще асимметричной задачи находит свое применение. В простейшем случае, если стоимость перехода от одной вершины к другой (вес рёбра) является евклидовым расстоянием между этими вершинами, то неравенство треугольника выполняется и, как следствие, данная задача является метрической, более того, если в качестве весов ребер используется евклидово расстояние, то такая задача называется

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

Изучение отдельных типов задач коммивояжёра позволило, на основе учета их особенностей, ускорить время их решения. Arora S. [16] и Mitchell J. S. B. [56] существенно продвинулись в изучении метрической и евклидовой задачи, что, в конце концов, позволило им разработать приближенную схему полиномиального времени (PTAS) для евклидовой задачи коммивояжёра.

1.2. Обзор алгоритмов решения асимметричной задачи коммивояжёра

1.2.1. Точные алгоритмы решения асимметричной задачи коммивояжёра

В 1954 году Dantzig G., Fulkerson R. и Johnson S. предложили первый универсальный алгоритм для решения задачи коммивояжёра [57]. Позднее данная работа легла в основу алгоритма Гомори для решения задач целочисленного программирования [58]. Однако, время работы данного алгоритма было крайне высоким.

В 1962 году Held M. и Karp R. M. [10] и, независимо от них, Bellman R. [59] предложили использовать метод динамического программирования для решения задачи коммивояжера (в последствии этот алгоритм стал называться «Held-Karp алгоритм»). Этот алгоритм работает быстрее алгоритма, предложенного ранее Dantzig G., Fulkerson R. и Johnson S., но требует большего объема оперативной памяти.

В аспекте точного решения этой задачи в 1963 Little J. D. C., Murty K. G., Sweeney D. W. и Karel C. [13] реализовали метод ветвей и границ (который в свою очередь был предложен Land A.H., Doig A.G. в 1960 году [7]) для решения

асимметричной задачи коммивояжера. В 1987 году Padberg M. и Rinaldi G. [60] продемонстрировали реализацию метода ветвей и отсечений (который применяется для решения задач целочисленного программирования) для решения задач коммивояжера большой размерности. Кроме того, неоднократно принимались попытки по распараллеливанию метода ветвей и границ для решения задачи коммивояжера. Интересные результаты в этом направлении принадлежат Сигалу И.Х., Бабинской Я.Л. и Посыпкину М.А. ( [31], [61]).

В 1970-х годах Held M. и Karp R. M. ( [62], [63]) спроектировали алгоритм, основанный на построении минимальных остовных деревьев для подграфов графа решаемой задачи коммивояжёра, однако, для общего случая время решения задачи не удалось сократить (хотя в последствии, алгоритм хорошо себя зарекомендовал для решения евклидовой задачи коммивояжёра [64]).

1.2.2. Приближенные алгоритмы решения задачи коммивояжёра

Так как асимметричная задача коммивояжёра является NP-трудной, то это означает, что если гипотеза о неравенстве классов Р и NP верна, то не существует точного полиноминального алгоритма для решения задачи коммивояжёра (как и для любой другой NP-трудной задачи) [1]. В связи с этим, большого внимания удостоились приближенные (они же эвристические и метаэвристические) алгоритмы решения задачи коммивояжёра, которые не гарантируют точного решения, однако позволяют найти решение, достаточно близкое (например, в понимании эпсилон полиномиальных приближений) к точному за приемлемое время (с точки зрения лица принимающего решения).

Основываясь на литературных источниках, приближенные алгоритмы можно разделить на три семейства [6], [18], [30], [65]:

- жадные алгоритмы

- роевые алгоритмы

- алгоритмы, направленные на улучшения решения.

Наиболее известным и простым типичным представителем жадных алгоритмов является алгоритм ближайших по расстоянию соседей. Однако точность большинства жадных алгоритмов крайне низкая.

Особый вклад в развитие роевых алгоритмов внесли работы Dorigo M., Stützle T., Hoos H. H. по муравьиным системам [17], [19]. Известны также такие роевые алгоритмы, как «Капли дождя», предложенный Hamed Shah-Hosseini [66] и «Пчелиные системы», основанный на работе Sato T. и Hagiwara M. [67].

К третьему семейству приближенных алгоритмов относятся такие алгоритмы как «^-opt» (предложенный Lin. S в 1965 году [68]), «Tabu search» (разработанный Gamboa D., Rego C., Glover F. в 2005 [69]) и «Lin - Kernighan» (сформулированный Lin S., Kernighan B.W. в 1973 [6]) и его модификации, предложенные Helsgaun в 2000 и 2017 годах [18].

1.3. Описание алгоритма метода ветвей и границ для решения асимметричной задачи коммивояжёра

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

Процедура ветвления, разработанная авторами классического алгоритма [13], предполагает следующие действия. Построение поискового дерева решений

начинается с корня, который будет соответствовать множеству «всех возможных туров», т. е. корень дерева представляет множество Я всех (п-1)! возможных туров в задаче с п городами. Ветви, выходящие из корня, определяются выбором одной дуги, например, дуги (к, I). Идея авторов алгоритма состоит в том, чтобы разделить текущее множество туров на два множества: одно — которое, весьма вероятно, содержит оптимальный тур, и другое — которое, вероятно, этого тура не содержит. Для этого предлагается специальный алгоритм выбора такой дуги (к, I), которая, вполне вероятно, входит в оптимальный тур. Множество Я разделяется на два множества [к, 1} и [к, I}. Во множество [к, 1} входят все туры из Я, содержащие

это ребро, т.е. проходящие через него, а во множество [к, 1} — туры, не содержащие это ребро. Обратим внимание, что идея авторов алгоритма очень перспективна — если организовать процесс ветвления таким образом, чтобы на каждом шаге выбиралось «правильное» ребро, то весь процесс завершится за п шагов. Пример фрагмента такого дерева приведен на рисунке 1. Число 15 в корне поискового дерева означает нижнюю границу стоимости всех туров. Далее алгоритм выбирает дугу (1,4) в качестве дуги ветвления, и множество всех туров разделяется на множество туров, которые содержат дугу (1,4) (обозначение дуги дерева решений 1^4) и которые не содержат дугу (1,4) (обозначение дуги дерева решений 1^4). На следующем этапе работы алгоритма выбирается множество туров, которое соответствует вершине с нижней границей 15. Это множество туров уже делится на два подмножества: подмножество туров, которые содержат дугу (2,3), и подмножество туров, которые не содержат дугу (2,3).

Рисунок 1 - Фрагмент поискового дерева решений

С каждой вершиной дерева связывается нижняя граница стоимости любого тура из этого множества. Очевидно, что задача состоит в получении как можно более точных нижних границ. Причина этого следующая. Предположим, что уже получен конкретный полный тур Т, со стоимостью Cost( Т). Если нижняя граница, связанная с множеством туров, представленных некоторой вершиной поискового дерева, больше, чемСоя^ Т), то до конца процесса поиска не нужно рассматривать эту и все следующие за ней вершины. В реализации это приводит к усечению поискового дерева решений путем отбрасывания всех текущих листьев поискового дерева, имеющих стоимость большую, чем Cost(T).

На листинге 1 представлена схема работы алгоритма метода ветвей и границ для задачи коммивояжёра, в которой приняты следующие обозначения. Пусть X— текущая вершина поискового дерева, а (к, I) — дуга, по которой происходит ветвление. Обозначим вершины, непосредственно следующие за X, через Y и Y. Множество Y есть подмножество туров из X, проходящих через дугу (к, I), а множество Y — подмножество туров из X, не проходящих через дугу (к,1). Вычисленные нижние границы для множеств Y и Y обозначим через w(Y) и w(Y) соответственно. Самый дешевый тур, известный алгоритму в данный момент, обозначим через z0, причем в момент инициализации примем, что z0 = да.

С детальным описанием всех этапов данного алгоритма можно ознакомиться в [11], [32] и [47].

1. Инициализация.

2. Приведение матрицы стоимостей A.

3. Установка корня поискового дерева решений X=R

приведение исходной матрицы - вычисление w(X).

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

СПИСОК ЛИТЕРАТУРЫ

1. Korte, B. Combinatorial optimization. Theory and Algorithms [Text] / B. Korte, J. Vygen. - Berlin: Springer-Verlag, 2018. - P. 698.

2. Ульянов, М.В. Вероятностный прогноз сложности индивидуальных задач коммивояжера на основе идентификации распределения сложности по экспериментальным данным [Текст] / М.В. Ульянов, Г.Н. Жукова, М.И. Фомичёв, В.А. Головешкин // Автоматика и телемеханика: № 7. - Москва, 2018. - С. 149-166.

3. Жукова, Г. Н. Использование квантильных коэффициентов асимметрии и эксцесса для оценки сложности решения задачи коммивояжера [Текст] / Г.Н. Жукова, М.В. Ульянов, М.И. Фомичёв, В.А. Головешкин // International Journal of Open Information Technologies: т. 4, № 12. - Москва, 2016. - С. 131137.

4. Бородин, В.В., Экспериментальное исследование эффективности эвристических алгоритмов решения задачи коммивояжёра [Текст] / В.В. Бородин, С.Е. Ловецкий, И.И. Меламед, Ю.М. Плотинский // Автоматика и телемеханика, №. 11. - Москва, 1980. - С. 76-84.

5. Колесников, А.В., Решение сложных задач коммивояжера методами функциональных гибридных интеллектуальных систем [Текст] / А.В. Колесников, И.А. Кириков, С.В. Листопад, С.Б. Румовская, А.А. Доманицкий // Москва: ИПУ РАН. - 2011. - С. 295.

6. Lin, S. An Effective Heuristic Algorithm for the Traveling-Salesman Problem [Text] / S. Lin, B.W. Kernighan // Operations Res., vol. 21. - 1973. - P. 498-516.

7. Land, A.H. An automatic method of solving discrete programming problems [Text] / A.H. Land, A.G. Doig // Econometrica, vol. 28, no. 3. - 1960. - P. 497-520.

8. Bellman, R. Combinatorial processes and dynamic programming [Text] / R. Bellman // American Mathematical Society. Providence - 1960. - P. 217-249.

9. Gonzales, R.H. Solution to the traveling salesman problem by dynamic programming on the hypercube [Text] / R.H. Gonzales // Technical Report Number 18, Operations Research Center, Massachusetts Institute of Technology. Cambridge - 1962.

10.Held, M.R. A dynamic programming approach to sequencing problems [Text] / M.R. Held, R.M. Karp // Journal of the Society of Industrial and Applied Mathematics, no. 10. - 1962. - P. 196-210.

11.Kruskal, J.B. On the shortest spanning subtree of a graph and the traveling salesman problem [Text] / J.B. Kruskal // Proceedings of the American Mathematical Society, no. 7. - 1956. - P. 48-50.

12.Lawler, E.L. Branch-and-bound methods: A survey [Text] / E.L. Lawler, D.E. Wood // Operations Research, no. 14. - 1966. - P. 699-719.

13.Little, J.D.C. An algorithm for the traveling salesman problem [Text] / J.D.C. Little, K.G. Murty, D.W. Sweeney, C. Karel // Operations Research, no. 11. - 1963. - P. 972989.

14.Alvim, A.C.F POPMUSIC for the world location-routing problem [Text] / A.C.F Alvim, E.D. Taill // EURO Journal on Transportation and Logistics, vol. 2, no. 3. -2013. P. 231-254.

15.Applegate, D.L. The Traveling Salesman Problem [Text] / D.L. Applegate, R.E. Bixby, V. Chvatal, W. Cook. // Princeton University Press, 2011. - P. 608.

16.Arora, S. Polynomial-time approximation schemes for Euclidean TSP and other geometric problems [Text] / S. Arora // Journal of the ACM, no. 45. - 1998. - P. 753782.

17.Dorigo, M. Distributed Optimization by Ant Colonies [Text] / A. Colorni, M. Dorigo, V. Maniezzo // Proceedings of the First European Conference on Artificial Life. Paris. - 1991. - P. 134-142.

18.Helsgaun, K. An effective implementation of the Lin-Kernighan traveling salesman heuristic [Text] / K. Helsgaun // European Journal of Operational Research, vol. 126, no. 1. - 2000. - P. 106-130.

19.Stützle, T. MAX-MIN ant system [Text] / T. Stützle, H.H. Hoos // Future generation computer systems, vol. 16. - 2000. - P. 889-914.

20.Johnson, D.S. Local optimization and the traveling salesman problem [Text] / D.S. Johnson // Lecture Notes in Computer Science. - 1990. - P. 446-461.

21.Jonker, R. Transforming asymmetric into symmetric traveling salesman problem [Text] / R. Jonker, T. Volgenant // Operations Research, vol. letters 2. - 1983. - P. 161-163.

22.Mitchell, J.E. Computational experience with an interior point cutting [Text] / J.E. Mitchell // SIAM Journal on Optimization, vol. 10. - 2000. - P. 1212-1227.

23.Taillard, E. A user's guide to tabu search [Text] / E. Taillard, B. Taillard, F. Glover // Annals of Operations Research, no. 41. - 1993. - P. 1-28.

24.Tinos, R. Efficient Recombination in the Lin-Kernighan-Helsgaun Traveling Salesman Heuristic [Text] / R. Tinos, K. Helsgaun, D. Whitley // 15th International Conference on Parallel Problem Solving from Nature - University of Coimbra, Coimbra, Portugal, Sep 2018.

25.Корбут, А.А. Метод ветвей и границ (обзор теории алгоритмов, программ и приложений) [Текст] / А.А. Корбут , И.Х. Сигал, Ю.Ю. Финкельштейн // Math. Operationsforsch. Statist., Ser. Optimization, vol. 20, № 2. - 1977. - С. 253-280.

26.Курейчик, В.В. Генетический Алгоритм определения пути коммивояжера [Текст] / В.В. Курейчик, В.М. Курейчик // Известия РАН. Теория и система управления, № 1. - 2006. - C. 94-100.

27. Леонтьев, В.К. Исследование одного алгоритма решения задачи коммивояжера [Текст] / В.К. Леонтьев // ЖВМиМФ, т. 13, № 5. - 1973. - С. 1228-1236.

28.Меламед, И.И. Задача коммивояжера. Вопросы теории [Текст] / И.И. Меламед, С.И. Сергеев, И.Х. Сигал // Автоматика и телемеханика, № 9. - 1989. - С. 3-33.

29.Мудров, В.И. Задача коммивояжера [Текст] / В.И. Мудров // Москва: Знание. -1969. - С. 64.

30.Пантелев, А.В. Метаэвристические алгоритмы поиска глобального экстремума [Текст] / А.В. Пантелев // Москва: МАИ-ПРИНТ. - 2009. - С. 160.

31.Посыпкин, М.А. Оценки ускорения для некоторых вариантов параллельной реализации метода ветвей и границ [Текст] / М.А. Посыпкин, И.Х. Сигал // ЖВМиМФ, т. 26, № 12. - 2006. - С. 2291-2307.

32.Штовба, С.Д. Муравьиные алгоритмы [Текст] / С.Д. Штовба // Exponenta Pro. Математика в приложениях, т. 4. - 2003. - С. 70-75.

33.Ульянов, М.В. Исследования особенностей применения комбинированного алгоритма для решения асимметричной задачи коммивояжера [Текст] / М.В. Ульянов, М.И. Фомичёв // Информационные технологии: т. 27, № 1. -Москва, 2021. - С. 3-8

34.Жукова, Г.Н. Комбинированный точный алгоритм для асимметричной задачи коммивояжера: построение и статистическое исследование временной эффективности [Текст]./ Г.Н. Жукова, М.В. Ульянов, М.И. Фомичёв // Автоматика и телемеханика:№ 11.- Москва, 2019. - С. 155-172.

35.Ульянов, М.В. Сравнительный анализ комбинаций метода ветвей и границ с метаэвристическими алгоритмами для решения асимметричной задачи коммивояжёра [Текст] / М.В. Ульянов, М.И Фомичёв // Информационные технологии: т. 25, № 10.- Москва, 2019. - С. 590-595.

36. Фомичёв, М.И. Подходы к организации поискового дерева решений в методе ветвей и границ для асимметричной задачи коммивояжера [Текст] / М.И. Фомичёв, М.В. Ульянов // Информационные технологии: т. 24, № 11. -Москва, 2018. - С. 698-704.

37. Фомичёв, М. И. Сравнительный анализ метаэвристических алгоритмов решения несимметричной задачи коммивояжёра [Текст] / М.И. Фомичёв // Системы управления и информационные технологии: № 3. - Воронеж, 2017. - С. 88-92.

38.Жукова, Г.Н. Об одном обобщённом представлении классов индивидуальных задач коммивояжёра [Текст] / Г.Н. Жукова, М.В. Ульянов, М.И. Фомичёв, В.А. Головешкин // Автоматизация. Современные технологии: № 10. - Москва, 2016. - С. 22-29.

39.Жукова, Г.Н. Эффективный по времени точный комбинированный алгоритм для асимметричной задачи коммивояжера [Текст] / Г.Н. Жукова, М.В. Ульянов, М.И. Фомичёв, // Бизнес-информатика: № 3(45). - Москва, 2018. - С. 20-28.

40.Ульянов, М.В. Оценка параметров распределения логарифма сложности задачи коммивояжера [Текст] / М.В. Ульянов, М.И. Фомичёв, В.А. Головешкин,

Г.Н. Жукова // Современные информационные технологии и ИТ-образование: т. 13. № 1. - Москва, 2017. - С. 19-24.

41.Жукова, Г.Н. Распределение логарифма сложности индивидуальных задач коммивояжера при фиксированной длине входа [Текст] / Г.Н. Жукова, М.В. Ульянов, М.И. Фомичёв, В.А. Головешкин // Современные информационные технологии и ИТ-образование: т. 12, № 3-2. - Москва, 2016. - С. 131-137.

42.Ульянов, М.В. Ресурсные характеристики способов организации дерева решений в методе ветвей и границ для задачи коммивояжера [Текст] / М.В. Ульянов, М.И. Фомичёв // Бизнес-информатика: № 4 (35). - Москва, 2015. - С. 38-46.

[Англ. версия] Ulyanov, M.V. Resource characteristics of ways to organize a decision tree in the branch-and-boundmethod for the traveling salesmen problem / M.V. Ulyanov, M.I. Fomichev // Business Informatics: No. 4 (34). - Moscow, 2015. - P. 38-46.

43.Головешкин, В.А Сравнение ресурсных характеристик традиционного и модифицированного метода ветвей и границ для TSP [Текст] / В.А. Головешкин, Г.Н. Жукова, М.В. Ульянов, М.И. Фомичёв // Современные информационные технологии и ИТ-образование: т. 2, № 11. - Москва, 2015. - С. 151-159.

44. Фомичёв, М.И. Интеграция метаэвристических алгоритмов решения несимметричной задачи коммивояжёра с методом ветвей и границ [Текст] / М.И. Фомичёв // Информационные технологии моделирования и управления: т. 109, № 1. - Воронеж, 2018. - С. 47-54.

45.Головешкин, В.А. Корреляция сложности и времени решения TSP [Текст] / Г.Н. Жукова, М.В. Ульянов, В.А. Головешкин, М.И. Фомичёв // Системы компьютерной математики и их приложения: № 18. - Смоленск, 2017. - С. 136138.

46.Фомичёв, М. И. Особый случай классического метода ветвей и границ для задачи коммивояжёра [Текст] / М.И. Фомичёв // Вестник Волжский государственной академии водного транспорта: № 49. - Н.Новгород, 2016. - С. 68-77.

47. Фомичёв, М.И. Применение модификации метода ветвей и границ для решения задачи коммивояжера [Текст]. / М.И. Фомичёв // Сборник трудов Международной научно-технической конференции «Информационные системы и технологии» ИСТ-2021. - 22 апреля 2021 г. - Н. Новгород: НГТУ. - С. 650652.

48.Фомичёв, М.И. Об искусственном ограничении числа вершин поискового дерева решений для решения задачи коммивояжёра методом ветвей и границ [Текст]. / М.И. Фомичёв // Сборник трудов Международной научно-технической конференции «Информационные системы и технологии» ИСТ-2020. - 24 апреля 2020 г. - Н. Новгород: НГТУ. - С. 804-808.

49.Фомичёв, М.И. Об одной оценке индивидуальной задачи коммивояжёра [Текст]. / М.И. Фомичёв // Сборник трудов всероссийской научно-технической конференции «XX всероссийская конференция молодых учёных по математическому моделированию и информационным технологиям». - 28 октября 2019 г. - Новосибирск - С. 86-87.

50.Фомичёв, М.И. Об одной оценке индивидуальной задачи коммивояжёра [Текст]. / М.И. Фомичёв // Сборник трудов Международной научно-технической конференции «Информационные системы и технологии» ИСТ-2019. - 19 апреля 2019 г. - Н. Новгород: НГТУ. - С. 694-698.

51. Фомичёв, М.И. Сравнительный анализ метаэвристических алгоритмов решения несимметричной задачи коммивояжера [Текст]. / М.И. Фомичёв // Сборник трудов Международной научно-технической конференции «Информационные системы и технологии» ИСТ-2017. - 21 апреля 2017 г. - Н. Новгород: НГТУ. -С. 770-774.

52.Головешкин, В.А. Статический подход к определению сложности задачи коммивояжера [Текст]. / В.А. Головешкин, Г.Н. Жукова, М.В. Ульянов, М.И. Фомичёв // Сборник трудов Международной научно-технической конференции «Информационные системы и технологии» ИСТ-2017. - 21 апреля 2017 г. - Н. Новгород: НГТУ. - С. 650-655.

53. Фомичёв, М.И. Об одной особенности классического метода ветвей и границ для задачи коммивояжёра [Текст]. / М.И. Фомичёв // Сборник трудов Международной научно-технической конференции «Информационные системы и технологии» ИСТ-2016. - 22 апреля 2016 г. - Н. Новгород: НГТУ. - С. 348.

54.Menger, K. Bericht uber ein mathematisches Kolloquium [Text] / K. Menger // Monatshefte fur Mathematik und Physik, no. 38. - 1930. - P. 17-38.

55.Гудман, С. Введение в разработку и анализ алгоритмов [Текст] / С. Гудман // Москва: Мир. - 1981. - С. 368.

56.Mitchell, J.S.B. Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems [Text] / J.S.B. Mitchell // SIAM Journal on Computing, vol. 28, no. 4. - 1999. - P. 1298-1309.

57.Dantzig, G. Solution of a large-scale traveling-salesman problem [Text] / G. Dantzig, R. Fulkerson, S. Johnson // Operations Research, no. 2. - 1954. - P. 393-410.

58.Gomory, R.E. Outline of an algorithm for integer solutions to linear programs [Text] / R.E. Gomory // Bull. Amer. Math. Soc., vol. 64, №. 5. - 1958. - P. 275-278.

59.Bellman, R. Dynamic programming treatment of the travelling salesman [Text] / R. Bellman // Journal of the Association for Computing Machinery, vol. 9. - 1962. - P. 61-63.

60.Padberg, M. Optimization of a 532-city symmetric traveling salesman problem by branch and cut [Text] / M. Padberg, G. Rinaldi // Operations Research Letters, vol. 6. - 1987. - P. 1-7.

61. Сигал, И.Х. Параллельная реализация метода ветвей и границ в задаче коммивояжёра на базе бибилиотеки BNB-Solver [Текст] / И.Х. Сигал, Я.Л. Бабинская, М.А. Посыпкин // Труды института системного анализа Российской Академии Наук, т. 25. - 2006. - С. 26-36.

62.Held, M.R. The traveling-salesman problem and minimum spanning trees [Text] / M.R. Held, R.M. Karp // Operations Research, vol. 18. - 1970. - P. 1138-1162.

64.Camerini, P.M. On improving relaxation methods by modified gradient techniques [Text] / P.M. Camerini, L. Fratta, F. Maffioli // Mathematical Programming Study, vol. 3. - 2009. - P. 26-34.

65.Cormen, T.H. Introduction to Algorithm. [Text] / T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein // Cambridge: MIT Press. - 2009. - P.1328.

66.Shah-Hosseini, H. The intelligent water drops algorithm: a nature-inspired swarm-based optimization algorithm [Text] / H. Shah-Hosseini // International Journal of Bio-inspired computation, vol. 1, no. 1-2. - 2009. - P. 71-79.

67.Sato, T. Bee System: Finding solution by a concentrated search [Text] / T. Sato, M. Hagiwara // Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, vol. 4. - 1997. - P. 3954-3959.

68.Lin, S. Computer solutions of the traveling salesman problem [Text] / S. Lin // Bell System Technical Journal, no. 44. - 1965. - P. 2245-2269.

69.Gamboa, D. Data structures and ejection chains for solving large-scale traveling salesman problems [Text] / D. Gamboa, C. Rego, F. Glover // European Journal of Operations Research, no. 160. - 2005 - P. 151-171.

70. Ульянов, М.В. Ресурсно-эффективные компьютерные алгоритмы. Разработка и анализ [Текст] / М.В. Ульянов // Москва: ФИЗМАТЛИТ. - 2008. - C. 304.

71.Knuth, D.E. Estimating the efficiency of backtracking programs [Text] / D.E. Knuth // Mathematics of Computing, no. 29. - 1975. - P. 121-136.

72.Макконелл, Д. Основы современных алгоритмов. [Текст] / Д. Макконелл // Москва: Техносфера. - 2004. - C. 368.

73.Вирт, Н. Алгоритмы и структуры данных. Новая версия для Оберона [Текст] / Н. Вирт // Москва: ДМК Пресс. - 2010. - С. 272.

74.Helsgaun, K. An Extension of the Lin-Kernighan-Helsgaun TSP Solver for Constrained Traveling Salesman and Vehicle Routing Problems: Technical report. [Text] / K. Helsgaun // Roskilde: Roskilde Universitet. - 2017. - P. 60.

СПРАВКА

об использовании в научных проектах РФФИ результатов диссертационной работы Фомичева Михаила Игоревича

«Модифицированная реализация алгоритма метода ветвей и границ для решения асимметричной задачи коммивояжера», представленной на соискание ученой степени кандидата технических наук по специальности 05.13.01 -«Системный анализ, управление и обработка информации (в науке и промышленности)»

Результаты диссертационной работы Фомичева М. И. «Модифицированная реализация алгоритма метода ветвей и границ для решения асимметричной задачи коммивояжера» составляют основу содержания самостоятельной части (блока) проекта по гранту Российского фонда фундаментальных исследований 18-07-00656 а «Разработка эффективных алгоритмов решения задач транспортной и производственной логистики», а именно блока «Исследование и разработка точного ресурсно-эффективного комбинированного алгоритма для решения несимметричной задачи коммивояжера (ATSP)» (руководитель работ по данному блоку проекта — д.т.н. Ульянов М.В.). В результате исследования построен комбинированный алгоритм, в котором рациональный метаэвристический алгоритм применен на первом этапе, а точный метод ветвей и границ с хранением усеченных матриц в вершинах поискового дерева — на втором. На основе статистически значимого экспериментального исследования получены конкретные показатели временной эффективности в сравнении с классическим алгоритмом метода ветвей и границ.

Результаты данного исследования опубликованы в трех статьях в журнале «Информационные технологии» (в 2018, 2019 и 2021 гг.), входящем в перечень ВАК.

Кроме того, проведенное М. И. Фомичевым масштабное экспериментальное исследование классического алгоритма метода ветвей и границ по определению сложности индивидуальных задач коммивояжера легло в основу статистического исследования, на основе которого была решена задача вероятностного прогнозирования сложности. Эти работы были выполнены в рамках проекта по гранту Российского фонда фундаментальных исследований 16-07-00160 а «Прогнозирование временных характеристик эффективных реализаций метода ветвей и границ для задачи коммивояжера на основе характеристик случайных матриц и идентификации порожденного распределения времен» (руководитель проекта — д.т.н. Ульянов М.В.).

Результаты данного исследования опубликованы в журнале «Автоматика и телемеханика» (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. Zhu-kova, M. Fomichev, V.A. Goloveshkin // Automation and Remote Control: Vol. 79. No. 7. - Moscow, 2018.-P. 1296-1310.), индексируемом в Scopus.

Руководитель проекта РФФИ 16-07-00160 а и руководитель работ по блоку проекта РФФИ 18-07-00656 а, ведущий научный сотрудник лаборатории теории расписаний и дискретной оптимизации Института проблем управления им. В.А. Трапезникова РАН

«УТВЕРЖДАЮ» Первый проректор - проректор по образовательной деятельности

гБроЯского государственною хничёского з?йЕтерситета

ева к.т.н., доцент г^ЕИвашкин Е.Г.

2021 г.

АКТ

о внедрении результатов диссертационной работы Фомичева Михаила Игоревича

" МОДИФИЦИРОВАННАЯ РЕАЛИЗАЦИЯ АЛГОРИТМА МЕТОДА ВЕТВЕЙ И ГРАНИЦ ДЛЯ РЕШЕНИЯАСИММЕТРИЧНОЙ ЗАДАЧИ

КОММИВОЯЖЁРА ",

представленной на соискание ученой степени кандидата технических наук по специальности 05.13.01 - "Системный анализ, управление и обработка информации

(в науке и промышленности)"

Комиссия в составе: директора Института радиоэлектроники и информационных технологий, профессора Мякинькова А.В. - председателя; профессора, зав. кафедрой "Компьютерные технологии в проектировании и производстве" Моруги-на С.Л. - члена комиссии; профессора кафедры Ивлева М.А. - члена комиссии, составила настоящий Акт о том, что на кафедре "Компьютерные технологии в проектировании и производстве" в лекционном курсе и лабораторных работах для студентов бакалавриата и магистратуры по направлениям 09.03.02 и 09.04.02 «Информационные системы и технологии» по дисциплинам: «Дискретная математика», «Методы оптимизации», «Теория принятия решений», «Основы CALS технологий» используются следующие результаты диссертационной работы Фомичева М.И.:

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

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

Директор ИРИТ, профессор Зав. кафедрой KTlill, профессор Профессор кафедры КТПП

А.В. Мякиньков С.Л. Моругин М.А. Ивлев

работы в учебном процессе НИУ ВШЭ

01

Федеральное государственное автономное образовательное учреждение высшего профессионального образования

НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ

ВЫСШАЯ ШКОАА ЭКОНОМИКИ

109028, Россия, Моова. Гкжрооский бульвар, д 11.

8 (496) S31 0000 '27254. е mari с

ж@*тев.ги. www-cs.tao.ru

Факультет компьютерных наук

«УТВЕРЖДАЮ»

Декан факультета «Компьютерных наук» Национального исследовательского университета «Высшая школа экономики» д-р физ.-м/г. наук профессор

Аржанцев И.В. « ¿У-» ^ _2021 г.

АКТ

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

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

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

представленной на соискание ученой степени кандидата технических наук по специальности 05.13.01 -«Системный анализ, управление и обработка информации (в науке и промышленности)»

Комиссия в составе: руководителя департамента «Программной инженерии» факультета «Компьютерных наук», доцента Лебедева С.А. - председателя; академического руководителя образовательной программы «Программная инженерия» факультета «Компьютерных наук», профессора Шилова В.В. - члена комиссии; заместителя заведующего базовой кафедрой «Системное программирование» Института системного программирования им. В.П. Иванникова РАН (ИСП РАН), профессора Гринкруга Е.М. - члена комиссии, составила настоящий Акт о том, что на департаменте «Программная инженерия» факультета «Компьютерных наук» в лекционном курсе и на практических занятиях для студентов бакалавриата по направлению 09.03.04 «Программная инженерия» по дисциплине «Конструирование программного обеспечения» использоватись следующие результаты диссертационной работы Фомичёва М.И.

1. Учебный программно-алгоритмический комплекс «Решение задачи коммивояжёра методом ветвей и границ», демонстрирующий принципы применения объектно-ориентированного программирование при реализации алгоритмов.

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

Л

Рук. ДПИ ФКН, доцент ^ Лебедев С.А.

Акад. рук. ДПИ ФКН, профессор

Зам. зав. баз. каф. «Системное программирование» ИСП РАН, профессор

Шилов В.В.

Гринкруг Е.М.

Faculty of Computer Science, National Research University Higher School of Economics

11. Pokrovsky boulevard. Moscow. 109028. Russia, tel.: [phone] "27254. e-mail [e-mail]. vww.cs.hse.ru