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

В введении обосновывается актуальность диссертационной работы, формулируется цель и задачи исследования, аргументируется научная новизна и практическая значимость исследования, а также обозначены основные положения, выносимые на защиту.
Первая глава (Современное состояние задачи коммивояжёра и алгоритмов её решения). Первое упоминание задачи коммивояжера в научных трудах встречается на Венской конференции 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 . Также результаты внедрены в учебный процесс факультета «Компьютерных наук» Национального исследовательского университета «Высшая школа экономики» и института радиоэлектроники и информационных технологий Нижегородского государственного технического университета им. Р.Е. Алексеева.