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

• Макаров Олег Олегович
• кандидат наук
• 2024

Оглавление диссертации кандидат наук Макаров Олег Олегович

Введение

Глава 1. Многоагентный подход в задачах прикладной

маршрутизации на сложных сетях

1.1 Обзор результатов по многоагентной маршрутизации

1.2 Постановка задач маршрутизации в сети

1.2.1 Многоагентная задача коммивояжера

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

1.3 Многоуровневая многоагентная задача маршрутизации с временными окнами

1.3.1 Иерархические маршруты с временными окнами

1.3.2 Модель многоуровневой многоагентной задачи маршрутизации

1.3.3 Интегрирование кластеров нижнего уровня

1.3.4 Иерархическая многоагентная задача маршрутизации

1.4 Модель задачи маршрутизации с временными окнами и учетом

грузоподъемности

1.4.1 Псевдобулевая модель многоагентной задачи

маршрутизации

1.5 Модель задачи нахождения маршрутов доставки товаров

1.6 Модель маршрутизации в условиях чрезвычайных ситуаций

1.7 Выводы по первой главе

Глава 2. Алгоритмы прикладной многоагентной маршрутизации

2.1 Подходы к решению МР-трудных задач

2.2 Алгоритмы решения задач маршрутизации с временными окнами

2.2.1 Эвристические алгоритмы решения задачи коммивояжера

2.2.2 Алгоритмы маршрутизации с временными ограничениями

2.3 Алгоритмы модели иерархической маршрутизации

2.4 Близость задач дискретной оптимизации

2.4.1 Специфика ЖР-трудных задач

2.4.2 Метрические характеристики графа

Стр.

2.4.3 Интеллектуализированный выбор метаэвристик (нейросетевой подход)

2.4.4 Решение задач маршрутизации по близкой задаче

2.5 Выводы по второй главе

Глава 3. Реализация алгоритмов в разработке программных

комплексов

3.1 Реализация вычисления метрических характеристик

3.2 Реализация алгоритмов кластеризации

3.3 Реализация и тестирование метаэвристик локальных агентов

3.4 Реализация алгоритмов многоагентной маршрутизации с временными окнами

3.5 Программный комплекс многоагентной инфраструктурной маршрутизации

3.6 Программа построения иерархических маршрутов в задачах маршрутизации на сложных сетях

3.7 Программная реализация задачи по доставке грузов

3.8 Выводы по третьей главе

Заключение

Словарь терминов

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

Список рисунков

Список таблиц

Приложение А. Метаэвристические алгоритмы

Приложение Б. Свидетельства о регистрации программных

продуктов

Приложение В. Акт о внедрении

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

Введение

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

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

Объект исследования. Задачи прикладной маршрутизации на сложных сетях.

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

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

оптимизации работы исполнителей (агентов-коммивояжеров). Такими задачами являются: задача коммивояжера (TSP — Traveling Salesman Problem), многих коммивояжеров (MTSP — Multiple Traveling Salesman Problem), иерархическая задача многих коммивояжеров (HMTSP — Hierarchical Multiple Traveling Salesman Problem), иерархическая задача многих коммивояжеров с временными окнами (HMTSPTW — Hierarchical Multiple Traveling Salesman Problem with Time Windows); и более общие: задача маршрутизации транспортных средств (VRP — Vehicle Routing Problem), задача маршрутизации транспортных средств с временными окнами (VRPTW — Vehicle Routing Problem with Time Windows), задача маршрутизации транспортных средств с временными окнами с учетом грузоподъемности (CVRPTW — Capacitated Vehicle Routing Problem with Time Windows). Разработка и исследование алгоритмов решения задач маршрутизации изложены в работах: Г. Андерссона, В. В. Бурховецкого, Й. Вигена, Я. К. Гуревича, Г. Данцига, Е. Е. Иванко, А. С. Каверина, Р. Кёнига, Д. Кнута, А. В. Кузнецова, И. И. Меламеда, А. Б. Муравника, Е. Д. Незнахи-ной, Д. В. Поспелова, К. В. Рыженко, О. Свенссона, И. Х. Сигал, Я. Тарнавски, В. Трауба, А. В. Федотова, М. Ю. Хачая, Б. Я. Штейнберга, R. Bellman, J. F. Cordeau, T. Cormen, T. Crainic, B. Golden, D. Johnson, L. Jourdan, M. Labbe, M. Laguna, G. Laporte, C. Leiserson, W. Lin, A. Lokketangen, D. Pisinger, C. Prins, W. Rei, R. Rivest , M. Rothkopf, E. Silver, C. Stein, P. Toth, L. Vegh, D. Vigo, D. Woodruff, Z. Wu и многих др.

Задачи типа TSP, MTSP (в литературе также принято обозначение mTSP), MTSPTW и VRPTW исследовались ранее, но многие аспекты требуют более детальной и глубокой разработки.

Поиск решений на сетях большой размерности является сложным в силу ЖР-полноты таких задач. На данный момент для решения подобных задач используются метаэвристические алгоритмы. Но большие сети (размерности 1O OOO вершин и более) требуют адаптации таких алгоритмов, так как возникает необходимость разработки технологии снижения размерности сети, например, путем согласованной кластеризации. При этом необходимо для каждой сети определенного типа выбрать свой, оптимальный алгоритм. После проведения кластеризации появляется необходимость выбора метаэвристических алгоритмов, которые корректно, достаточно быстро и точно обрабатывают структуры данных в кластере. Отметим, что для разных кластеров требуются различные метаэвристические подходы построения решений; при этом отдельной задачей

является нахождение параметров для выбранного метаэвристического алгоритма, что существенно влияет на его успешное применение.

Если не учитывать специфику транспортных средств в задачах типа УЯР и поставить требование нахождения замкнутых маршрутов, то класс ТБР содержится в классе УЯР. Аналогичное вложение справедливо для класса модификаций МТБРТ"^ который содержится в классе VRPTW и так далее, так как агентам в ТБР соответствуют транспортные средства в VRP. Таким образом, далее в работе задачи типа ТБР и VRP будут рассматриваться как эквивалентные в смысле многоагентности и замкнутости маршрутов.

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

Такая целевая установка предполагает решение следующих задач:

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

2) предложить подход решения многоагентных задач на сетях большой размерности с применением численных методов;

3) разработать программный комплекс для решения многоагентных задач прикладной маршрутизации на сложных сетях; реализовать последовательное снижение размерности путем кластеризации с последующим применением разработанных подходов маршрутизации; провести квазиреальные эксперименты для анализа используемых алгоритмов;

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

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

Теоретическая и практическая значимость. В работе дается теоретическое обоснование методов и алгоритмов решения задач многоагентной маршрутизации с иерархическим распределением вершин и временными ограничениями, которые соответствуют задачам псевдобулевой оптимизации с ограничениями по агентам, уровням иерархии и временным окнам. Рассматриваются классы задач прикладной маршрутизации, для которых выбор алгоритмов (метаэвристик) обосновывается близостью задач из класса и возможностью кластеризации по уровням иерархии и локальным маршрутам агентов. Работа имеет практическую значимость при решении реальных задач многоагентной прикладной маршрутизации на современных транспортных сетях. Примерами таких задач являются построение маршрутов доставки воды в чрезвычайных ситуациях на территории Большой Ялты, технология построения маршрутов доставки товаров со склада в Симферополе потребителям в различных городах Крыма (с учетом времени работы склада и потребителей). При решении данных задач были разработаны программные комплексы и получены свидетельства о регистрации программ для ЭВМ: «Программа мно-гоагентной инфраструктурной маршрутизации» № 2022614174 от 17.03.2022 г. и «Программа построения иерархических маршрутов в задачах маршрутизации на сложных сетях» № 2024615891 от 13.03.2024 г. с актом о внедрении. Разработан программный комплекс «Маршрутизатор доставки товаров», включающий эти программы в качестве модулей.

Положения, выносимые на защиту, и их научная новизна: В области математического моделирования:

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

2. Алгоритмическое наполнение и методика решения задач типа МТБР, ИМТЯР, HMTSPTW и УЯРТ1^ сочетающая кластеризацию, согласованную с маршрутами коммивояжеров на каждом кластере, и минимизацию общего пути, синтез вершин различного уровня иерархии и их обхода.

В области численных методов:

3. Разработка численных алгоритмов и технологии решения иерархических задач HMTSP с временными окнами.

4. Разработка способа вычисления метрических характеристик для определения близости многоагентных задач маршрутизации и анализ мета-эвристик в близких задачах маршрутизации.

В области программного обеспечения:

5. Программная реализация алгоритмов согласованной кластеризации и выбора метаэвристик для задач многоагентной маршрутизации: TSP, MTSP, HMTSP, VRPTW и их тестирование.

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

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

Апробация работы. Результаты исследования были представлены на следующих конференциях: Всероссийская конференция «Математические методы распознавания образов» (ММРО-21) (г. Москва, 2023 г.), Международная конференция «Наукоёмкие технологии - как основа современного цифрового промышленного производства» (г. Симферополь, 2023 г.), семинар лаборатории цифровых систем управления Института проблем управления РАН (г. Москва, 2023 г.), XIX Всероссийская школа-конференция молодых ученых «Управление большими системами» совместно с ИПУ РАН (г. Воронеж, 2023 г.), The international scientific conference «Modern Methods, Problems and Applications of Operator Theory and Harmonic Analysis, 20-25 august 2023» (0THA-2023) (г. Ростов-на-Дону, 2023 г.), XXXIV Крымская Осенняя Математическая Школа-симпозиум Н. Д. Копачевского по спектральным и эволюционным задачам (КР0МШ-2023) (п. Кача, 2023 г.), 14-я Международная конференция «Интеллектуализация обработки информации» (ИОИ-2022) (г. Москва, 2022 г.),

XXXIII Крымская осенняя математическая школа-симпозиум по спектральным и эволюционным задачам (КР0МШ-2022) (п. Сатера, 2022 г.), Международная научно-техническая конференция «Актуальные проблемы прикладной математики, информатики и механики» (г. Воронеж, 2022 г.), Научно-практическая конференция «Математика, информатика, компьютерные науки, моделирование, образование» и Таврическая научная конференция студентов и молодых специалистов по математике и информатике (г. Симферополь, 2022 г.), Всероссийская конференция «Математические методы распознавания образов» (ММР0-20) (г. Москва, 2021 г.), VI Международная научно-практическая конференция «Дистанционные образовательные технологии» (г. Ялта, 2021 г.), научные семинары кафедры информатики Крымского федерального университета (г. Симферополь, 2020-2023 г.).

Личный вклад. Автором совместно с научным руководителем проводилась постановка задач, обсуждались полученные основные результаты и формулировки выводов. Лично автором предложены теоретически обоснованные модели двухуровневой иерархической многоагентной маршрутизации, а также модели с временными окнами для сетей сложной структуры с выбором алгоритмов кластеризации и метаэвристик локальных агентов на кластерах, произведена программная реализация предложенных алгоритмов. В силу сложности инфраструктурных сетей автором разработана схема снижения размерности задачи. Предложена методика формирования базы данных для обучения разработанной интеллектуализированной системы выбора эвристических алгоритмов. Выбор основан на близости задач маршрутизации по метаинформации. Проведен анализ метаэвристик для решения близких задач маршрутизации, представлена их программная реализация. Разработанные и апробированные в работе алгоритмы применены при реализации программных комплексов: «Программа многоагентной инфраструктурной маршрутизации», «Программа построения иерархических маршрутов в задачах маршрутизации на сложных сетях», «Маршрутизатор доставки товаров».

Область исследования соответствует следующим пунктам паспорта специальности 1.2.2 — «Математическое моделирование, численные методы и комплексы программ» (физико-математические науки):

1. Разработка новых математических методов моделирования объектов и явлений.

2. Разработка, обоснование и тестирование эффективных вычислительных методов с применением современных компьютерных технологий.

3. Реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента.

Публикации. Основные результаты работы опубликованы в рекомендуемых ВАК РФ рецензируемых научных изданиях [22; 29; 30; 38; 48] и других научных изданиях [20; 21; 23; 28; 32—34; 44]. Работы [22; 38] индексируются в Scopus и Web of Science.

Объем и структура работы. Диссертация состоит из введения, 3 глав, заключения и 3 приложений. Полный объём диссертации составляет 188 страниц, включая 33 рисунка и 10 таблиц. Список литературы содержит 158 наименований.

Глава 1. Многоагентный подход в задачах прикладной маршрутизации на сложных сетях

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

1.1 Обзор результатов по многоагентной маршрутизации

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

Одно из первых упоминаний задачи маршрутизации транспортных средств (VRP) встречается в работе G. Dantzig и J. Ramser [74] в 1959 году. Здесь решалась проблема формирования маршрутов доставки продукта от магистрального трубопровода до обслуживающих терминалов, доставку осуществляют бензовозы. Первые эвристические подходы к решению VRP появились в 1964 году в работах G. Clarke и J. Wright [70]. Следующий значительный этап в изучении VRP произошел в 1981 году, тогда J. Lenstra и A. Kan [113] показали, что задачи такого вида являются NP-трудными.

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

Таким образом, VRP можно рассматривать как многоагентную задачу коммивояжеров (агентов) с одним депо (MTSP), которая является NP-трудной задачей дискретной оптимизации.

В работе P. Toth и D. Vigo [149] предложена классификация VRP:

1. Задача маршрутизации транспортных средств с временными окнами (VRPTW).

2. Задача маршрутизации транспортных средств с временными окнами с учетом грузоподъемности (CVRPTW).

3. Задача маршрутизации транспортных средств со случайными данными (SVRP — Stochastic Vehicle Routing Problem), когда количество клиентов и расстояние могут меняться случайно. Впервые предложена в [74].

4. Задача маршрутизации транспортных средств с возвратом товаров (VRPB — Vehicle Routing Problem with Backhauls), в которой клиенты могут возвращать некоторые товары после того, как весь товар будет доставлен клиентам [69].

5. Задача маршрутизации транспортных средств с немедленным возвратом товара (VRPPD — Vehicle Routing Problem with Pick-up and Delivery), в которой клиенты могут возвращать некоторые товары на склад [69].

6. Задача маршрутизации транспортных средств с раздельной доставкой (SDVRP — Split Delivery VRP), в которой каждый клиент может быть обслужен одновременно несколькими ТС [77].

7. Задача маршрутизации транспортных средств с множеством депо (MDVRP — Multiple Depot Vehicle Routing Problem [111]).

8. Задача маршрутизации транспортных средств с возможностью доза-грузки (VRPSF — Vehicle Routing Problem with Satellite Facilities), в которой предусмотрена дозагрузка в промежуточных складах (впервые предложена J. Bard, L. Huang, M. Dror, P. Jaillet [51]).

9. Периодическая задача маршрутизации транспортных средств (PVRP — Periodic VRP) [65].

Существуют и другие разновидности моделей VRP, например, иерархические и кластерные, — именно они представляют научный и практический интерес.

Задачи маршрутизации включают в себя широкий спектр проблем, таких как нахождение кратчайшего маршрута от точки до точки, построение кольцевых маршрутов, выделение узких мест, нахождение кратчайших замкнутых маршрутов и многие другие. Особый интерес представляют задачи нахождения множества кратчайших кольцевых маршрутов на сложной сети с дополнительными ограничениями в каждой из вершин. Такая VRP является задачей MTSP и может быть решена многоагентным поиском, что, в свою очередь, сочетается с проблемой снижения размерности. MTSPTW (Multiple Traveling Salesman

Problem with Time Windows — задача многих коммивояжеров с временными окнами) является частным случаем VRPTW, в котором требуется найти кратчайшие маршруты для агентов-коммивояжеров с учетом дополнительных временных ограничений в каждой из вершин.

Для анализа классов задач маршрутизации ТС, с учетом ряда ограничений в разрабатываемых многоагентных моделях маршрутизации типа MTSP, необходимо учитывать модели задач CVRP, VRPTW, MDVRP, SDVRP, VRPPD и другие.

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

В работе [49] обосновываются алгоритмы с постоянными гарантированными оценками точности для серии асимметричных маршрутных задач комбинаторной оптимизации. Рассматриваются задачи о штейнеровском цикле, обобщенная задача коммивояжера, задача маршрутизации транспорта с неделимым потребительским спросом и задачи коммивояжера с призами. Интерес представляет доказательство сводимости этих задач к подходящим постановкам ассиметричной задачи коммивояжера на основе алгоритма, предложенного О. Свенссоном [146] и В. Траубом [151].

В [87] представлен новый гибридный алгоритм для решения MTSP — GELS-GA (Gravitational Emulation Local Search Genetic Algorithm — гравитационная эмуляция генетического алгоритм с локальным поиском). Произведен сравнительный анализ предложенного алгоритма с генетическим алгоритмом и муравьиной колонией. Показано, что несмотря на простоту предлагаемого алгоритма, он достаточно эффективен и оптимальность достигается даже в очень сложных сценариях. Данные для сравнительного анализа брались из TSPLIB (Traveling Salesman Problem Library — библиотека задач коммивояжера) [152].

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

В статье [95] рассматривается проблема получения эффективного решения задачи коммивояжера (TSP) с использованием нейронной сети HNN

(Hopfield Neural Network — нейронная сеть Хопфилда) и метода штрафов. Такой подход имеет особенность попадания в локальный минимум, как следствие, алгоритм не может сойтись к эффективному решению. В работе описана модификация, использующая для решения этой проблемы расширенную и ускоренную лагранжеву нейронной сеть Хопфилда (AALHNN — Accelerated Augmented Lagrangian Hopfield Neural Network — ускоренная расширенная лагранжева нейронная сеть Хопфилда). В основе AALHNN лежит метод множителей Лагранжа, что обеспечивает получение эффективного решения задачи коммивояжера. Помимо этого, для стабилизиции динамической модели AALHNN, в реализацию включаются факторы второго порядка. Авторы предложили модифицированный вид модели TSP, предложенной Хопфилдом и Танком. Множители Лагранжа и усиленные множители Лагранжа перемножаются с ограничениями модели задачи коммивояжера. Применение функции расширенного лагранжиана, учитывающей цену маршрута, позволяет избежать локального минимума и обеспечивает сходимость алгоритма. Множители Лагранжа обновляются с использованием техники ускорения Нестерова [102]. В работе доказано, что экстремум, полученный с помощью этого улучшенного алгоритма, является оптимальным решением исходной задачи. В ходе эксперимента успешно получено приближенное оптимальное решение TSP. По сравнению с традиционной HNN, данный метод обеспечивает эффективное решение задачи коммивояжера и достижение более качественных результатов. В разделе 2.4.3 приведены результаты по созданию собственной нейронной сети для рекомендации метаэвристики, основанной на метаданных графа.

Похожий подход, основанный на нейронных сетях, описан в работах [39; 40], где предложено использовать функционал Ляпунова, построенный на основе TSP, в качестве основы для искусственной нейронной сети. В работе показано, что данный подход применим и в многоагентных задачах маршрутизации. Основная сложность заключается в процессе обучения, поскольку часть ресурсов уходит на выбор корректных параметров для нейронной сети.

В работе [156] исследован случай VRPTW с неопределенным количеством ТС и одновременным обслуживанием доставки и самовывоза VRPTW-SDP (Vehicle Routing Problem with Time Windows and Simultaneous Delivery and Pickup service — задача маршрутизации ТС с временными окнами с неопределенным количеством ТС и одновременным обслуживанием доставки и самовывоза). Задача VRPTW-SDP является расширением VRPTW с целью минимизации

транспортных расходов. Утверждается, что классические подходы для решения VRP и VRPTW, такие как, например, k-деревья [82] или метод ветвей и границ, малоэффективны при решении сложных задач. Предложен эволюционный алгоритм EA (Evolutionary Algorithm — эволюционный алгоритм) роя частиц. Оптимизация роя частиц PSO (Particle Swarm Optimization — оптимизации роя частиц) — это эффективный алгоритм для решения различных задач оптимизации. Как и многие метаэвристические подходы, в некоторых случаях PSO может попасть в локальный минимум, что накладывает ограничения на точность получаемого решения. Для решения данной проблемы предлагается многороевая кооперативная модификация MCPSO (Multi-swarm Cooperative Particle Swarm Optimization — многороевая кооперативная оптимизация роя частиц). В основе предложенного алгоритма лежит эволюционная кооперативная многороевая стратегия, здесь вводится понятие главного роя (агента), который преобразует собственные частицы, основываясь на внутренней информации и знаниях, полученных от подчиненных роев (агентов). Каждый из подчиненных роев (агентов) применяет алгоритм PSO. Данная идея похожа на подход муравьиных колоний, подробно описанный в разделе 2.2.2. Сравнительный анализ алгоритма PSO с алгоритмом GA (Genetic Algorithm — генетический алгоритм) показывает, что простой и надежный алгоритм MCPSO более эффективен для решения предложенной VRPTW-SDP.

В статье [155] представлена разработка новых методов решения VRPTW. Обсуждаются два основных направления развития точных методов: общий подход к декомпозиции и решение определенных двойственных к VRPTW задач, и более современное направление, связанное с анализом полиэдральной структуры VRPTW. Рассмотрена лагранжева релаксация набора ограничений, требующих, чтобы каждый клиент был обслужен ровно одним ТС, что приводит к ограничениям в подпроблеме кратчайшего пути. Представлен регуляризированный алгоритм секущих плоскостей в рамках линейного программирования для решения соответствующей двойственной задачи Лагранжа. Этот алгоритм приводит к более простым подзадачам нахождения кратчайшего пути с ограничениями, поскольку из-за сокращения отрицательных циклов, благодаря стабилизации двойственных переменных, множители сходятся быстрее. Авторами встроен устойчивый алгоритм секущей плоскости в методе ветвей и границ, введены сильные допустимые неравенства на уровне главной задачи с помощью релаксации Лагранжа. В результате получен алгоритм Лагранжа

с ветвлением, отсечением и оценкой целевой функции (LBCP — Lagrangian Branch-and-Cut-and-Price — алгоритм Лагранжа с ветвлением, отсечением и оценкой целевой функции) для VRPTW. Показано, что использование этой стратегии на уровне главной задачи дает значительное ускорение по сравнению с другими алгоритмами. Решены две тестовые задачи, представленные в 2001 году Герингом и Хомбергером [86], с 400 и 1000 клиентами соответственно, которые на сегодняшний день являются самыми большими задачами, когда-либо решенными оптимально. В реализации алгоритма LBCP используется фреймворк ABACUS [98] с открытым исходным кодом для решения смешанных задач целочисленного линейного программирования методом ветвления, отсечения и оценки цели. В работе [155] представлена новая формулировка VRPTW, включающая только псевдобулевые переменные дискретной оптимизации (ДО), связанные с дугами в базовом диграфе. Этот же подход используется в работе [7]. Новая формулировка основана на модели асимметричной задачи коммивояжера с временными окнами и имеет преимущество в том, что позволяет избежать дополнительных переменных и связывающих ограничений. В новой формулировке VRPTW временные окна (TW) моделируются с помощью неравенств путей, которые устраняют невыполнимые по времени и пропускной способности маршруты. Представлен новый класс усиленных неравенств, основанный на полиэдральных результатах, полученных в контексте асимметричной задачи коммивояжера с дугами пополнения запасов. Изучен политоп VRPTW и определена его размерность. Показано, что при определенных предположениях неравенства путей являются гранеопределяющими.

Список литературы диссертационного исследования кандидат наук Макаров Олег Олегович, 2024 год

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

1. Алгоритмы управления движением БПЛА и наземной станции в задачах мониторинга протяженных объектов / С. А. Диане, А. В. Кузнецов, Д. В. Степанов, Д. В. Акуловский // Перспективные системы и задачи управления : Материалы XVIII Всероссийской научно-практической конференции и XIV молодежной школы-семинара. Посвящается памяти Почетного члена Оргкомитета Конференции, водителя первого лунохода, генерал-майора В.Г. Довганя, п. Домбай, Карачево-Черкесская Республика, 03-07 апреля 2023 года. — 2023. — С. 63—72.

2. Бондаренко, В. А. Геометрические конструкции и сложность в комбинаторной оптимизации / В. А. Бондаренко, А. Н. Максименко. — М. : Изд-во ЛКИ, 2008. — 184 с.

3. Бурховецкий, В. В. Оптимизация и распараллеливание упрощенного алгоритма Балаша-Кристофидеса для задачи коммивояжера / В. В. Бурховецкий // Программные системы: теория и приложения. — 2020. — Т. 11, 4(47). — С. 3—16. — DOI: 10.25209/2079-3316-2020-11-4-3-16.

4. Бурховецкий, В. В. Исследование возможности распараллеливания алгоритма Литтла с модификацией Костюка для решения задачи коммивояжера / В. В. Бурховецкий, Б. Я. Штейнберг // конференция «НСКФ-2016», Переславль-Залеский с 29 ноября по 1 декабря 2016. — 2016.

5. Гахов, Ф. Д. Уравнения типа свертки / Ф. Д. Гахов, Ю. И. Черский. — М. : Наука, 1976. — 296 с.

6. Гейл, Д. Соседние вершины на выпуклом многограннике / Д. Гейл // Линейные неравенства и смежные вопросы; М.: ИЛ. — 1959. — С. 355—362.

7. Германчук, М. С. Знаниеориентированные модели многоагентной маршрутизации, : специальность 05.13.18 "Математическое моделирование, численные методы и комплексы программ": диссертация на соискание ученой степени кандидата физико-математических наук / М. С. Германчук. — ВГУ, Воронеж, 2022. — 150 с.

8. Германчук, М. С. Использование дополнительной информации в задачах дискретной оптимизации типа многих коммивояжеров / М. С. Герман-

чук // Таврический вестник информатики и математики. — 2016. — Т. 33, № 4. — С. 68—82.

9. Германчук, М. С. Модели обобщенных задач коммивояжера в интеллектуализации поддержки принятия решений для геоинформационных систем / М. С. Германчук // Географические и геоэкологические исследования в Украине и сопредельных территориях: сборник научных статей / под общ. ред. Б.А. Вахрушева. — 2013. — С. 413—415.

10. Германчук, М. С. Разрешимость задач псевдобулевой условной оптимизации типа многих коммивояжеров / М. С. Германчук // Таврический вестник информатики и математики. — 2020. — Т. 49, № 4. — С. 30—55.

11. Германчук, М. С. Задачи практической маршрутизации / М. С. Гер-манчук, М. Г. Козлова, В. А. Лукьяненко // Анализ, моделирование, управление, развитие социально-экономических систем. Сборник научных трудов XI Международной школы-симпозиума АМУР-2017. — 2017. — С. 116—120.

12. Германчук, М. С. Псевдобулевые модели условной оптимизации для класса задач многих коммивояжеров / М. С. Германчук, М. Г. Козлова,

B. А. Лукьяненко // Автоматика и телемеханика. — 2021. — № 10. —

C. 25—45. — Э01: 10.31857/80005231021100044.

13. Германчук, М. С. Метаэвристические алгоритмы для многоагентных задач маршрутизации / М. С. Германчук, Д. В. Лемтюжникова, В. А. Лукьяненко // Проблемы управления. — 2020. — № 6. — С. 3—13.

14. Гомотопии экстремальных задач / С. В. Емельянов, С. К. Коровин, Н. А. Бобылев, А. В. Булатов. — М. : Наука, 2001. — 350 с.

15. Деза, М. М. Геометрия разрезов и метрик / М. М. Деза, М. Лоран. — М. : МЦНМО, 2001. — 736 с.

16. Донской, В. И. Задачи псевдобулевой оптимизации с дизъюнктивным ограничением / В. И. Донской // Журнал выч. математики и матем. физики. — 1994. — № 4. — С. 461—472.

17. Журавлев, Ю. И. Избранные научные труды / Ю. И. Журавлев. — М. : Магистр, 1998. — 420 с.

18. Иванко, Е. Е. Адаптивная устойчивость в задачах комбинаторной опти-мизаци / Е. Е. Иванко // Труды Института математики и механики УрО РАН. — 2014. — № 1. — С. 106—108.

19. Иванко, Е. Е. Устойчивость и неустойчивость в дискретных задачах / Е. Е. Иванко. — Екатеринбург : Издательство УрО РАН, 2013. — 208 с.

20. Кластеризация сети с иерархической структурой в задаче многоагент-ной маршрутизации / М. Г. Козлова, В. А. Лукьяненко, О. О. Макаров, М. С. Германчук // Актуальные проблемы прикладной математики, информатики и механики : сборник трудов Международной научной конференции, Воронеж, 12-14 декабря 2022 г. / Министерство науки и высшего образования Российской Федерации, Воронежский государственный университет. — Воронеж : Научно-исследовательские публикации. — 2023. — С. 445—452.

21. Козлова, М. Г. Многоагентная иерархическая маршрутизация с временными окнами / М. Г. Козлова, В. А. Лукьяненко, О. О. Макаров // Интеллектуализация обработки информации : 14-я Международная конференция : тезисы докладов. — Москва : Российская академия наук. — 2022. — С. 427—432. — Режим доступа: http://machinelearning.ru/wiki/images/f/ff/Idp22.pdf (дата обращения 27.04.2024).

22. Козлова, М. Г. Построение многоагентных маршрутов в сети с иерархией вершин / М. Г. Козлова, В. А. Лукьяненко, О. О. Макаров // Вестник Воронежского государственного университета. Серия: Системный анализ и информационные технологии. — 2023. — № 3. — С. 32—50. — DOI: 10. 17308/sait/1995-5499/2023/3/32-50.

23. Козлова, М. Г. Система интеллектуализированного анализа и мониторинга распространения и влияния политических интернет-мемов / М. Г. Козлова, В. А. Лукьяненко, О. О. Макаров // Дистанционные образовательные технологии : сборник трудов VI Международной научно-практической конференции, 20-22 сентября 2021, Гуманитарно-педагогическая академия (филиал) Крымского федерального университета им. В.И. Вернадского в г. Ялте : ДОТ-2021. — Симферополь : Ариал. — 2021. — С. 244—251.

24. Кузнецов, А. В. Мера несходства на множестве графов и ее приложения / А. В. Кузнецов // Вестник Воронежского государственного университета. Серия: Системный анализ и информационные технологии. — 2017. — № 1. — С. 125—131.

25. Кузнецов, А. В. Модели движения, взаимодействия и сети связи мобильных агентов в иерархических системах на основе клеточных автоматов

: специальность 05.13.01 "Системный анализ, управление и обработка информации (по отраслям)": диссертация на соискание ученой степени доктора физико-математических наук / А. В. Кузнецов. — ВГУ, Воронеж, 2019. — 268 с.

26. Левитин, А. Алгоритмы: введение в разработку и анализ / А. Левитин. — М.: Вильямс, 2006. — 575 с.

27. Лемтюжникова, Д. В. Проблематика исследования труднорешаемых задач / Д. В. Лемтюжникова, В. А. Лукьяненко // Интеллектуализация обработки информации: Тезисы докладов 14-й Международной конференции; М.: Российская академия наук. — 2022. — С. 437—442.

28. Лукьяненко, В. А. Специфика задач маршрутизации в условиях локальных преобразований сети / В. А. Лукьяненко, О. О. Макаров, М. С. Германчук // Математические методы распознавания образов : 20-я Всероссийская конференция с международным участием : тезисы докладов. — Москва : Российская академия наук. — 2021. — С. 460—462.

29. Макаров, О. О. Анализ метаэвристик для задач многоагентной маршрутизации / О. О. Макаров // Таврический вестник информатики и математики. — 2023. — №1(58). — С. 62—87.

30. Макаров, О. О. Метаэвристики в близких задачах маршрутизации типа многих коммивояжеров / О. О. Макаров // Таврический вестник информатики и математики. — 2022. — №3(56). — С. 80—102.

31. Макаров, О. О. Разработка алгоритмов маршрутизации в сложных сетях / О. О. Макаров, М. С. Германчук // Математика, информатика, компьютерные науки, моде лирование, образование : сборник научных трудов научно-практической конференции МИКМО-2018 и Таврической научной конференции студентов и молодых специали стов по математике и информатике / Под ред. В. А. Лукьяненко. — 2018. — Т. 2. — С. 127—135.

32. Макаров, О. О. Выбор метаэвристик для близких задач многоагентной маршрутизации / О. О. Макаров, М. Г. Козлова // Управление большими системами : сборник научных трудов XIX Всероссийской школы-конференции молодых ученых, Воронеж, 5-8 сентября 2023 года. — Воронеж

: Воронежский государственный технический университет. — 2023. — С. 525—532.

33. Макаров, О. О. Многоагентный подход в задачах прикладной маршрутизации на сложных сетях / О. О. Макаров, М. Г. Козлова // XXXIV Крымская Осенняя Математическая Школа-симпозиум Н.Д. Копачев-ского по спектральным и эволюционным задачам, Кача (Севастополь), Российская Федерация, 8-17 сентября 2023 г. : сборник материалов международной конференции КРОМШ-2023. — Симферополь : Ариал. — 2023. — С. 36—38.

34. Макаров, О. О. Близкие задачи маршрутизации типа многих коммивояжеров / О. О. Макаров, М. Г. Козлова, В. А. Лукьяненко // Математические методы распознавания образов : 21-я Всероссийская конференция с международным участием : тезисы докладов. — Москва : Российская академия наук. — 2023. — С. 102—104.

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

36. Меламед, И. И. Задача коммивояжера. Приближенные алгоритмы / И. И. Меламед, С. И. Сергеев, И. Х. Сигал // Автомат. и телемех. — 1989. — № 11. — С. 3—26.

37. Меламед, И. И. Задача коммивояжера. Точные алгоритмы / И. И. Меламед, С. И. Сергеев, И. Х. Сигал // Автомат. и телемех. — 1989. — № 10. — С. 3—29.

38. Модели и алгоритмы многоагентной иерархической маршрутизации с временными окнами / М. Г. Козлова, Д. В. Лемтюжникова, В. А. Лукьяненко, О. О. Макаров // Известия Российской академии наук. Теория и системы управления. — 2023. — № 5. — С. 103—126. — DOI: 10.31857/ S0002338823050098. — [Переводная версия : Models and Algorithms for Multiagent Hierarchical Routing with Time Windows / M. G. Kozlova, D. V. Lemtyuzhnikova, V. A. Lukianenko, O. O. Makarov // Journal of Computer and Systems Sciences International. - 2023. - No. 62. - P. 862-883. - DOI 10.1134/S106423072305009X].

39. Муравник, А. Б. Функции Ляпунова в задаче нейросетевого моделирования: сравнительный анализ / А. Б. Муравник // Радиолокация, навигация, связь: сб. трудов XXVI Международной научно-технической конференции г. Воронеж 29 сентября - 1 октября 2020 г., в 6 т. / Воронеж-

ский государственный университет; Воронеж : Изд. Дом ВГУ. — 2020. — С. 49—55.

40. Муравник, А. Б. Нейросетевой подход к построению маршрута в автоматизированной системе управления специального назначения / А. Б. Муравник, М. Н. Данильченко. — 2021.

41. Новиков, Ф. А. Дискретная математика для программистов / Ф. А. Новиков. — СПб. : Питер, 2000. — 119 с.

42. Олифер, В. Г. Компьютерные сети. Принципы, технологии, протоколы /

B. Г. Олифер, Н. А. Олифер. — Санкт-Петербург: Питер, 2006. — 958 с.

43. Петровский, А. Б. Пространства множеств и мультимножеств / А. Б. Петровский. — М. : Едиториал УРСС, 2003. — 248 с.

44. Разработка алгоритмов многоагентной иерархической маршрутизации / М. Г. Козлова, В. А. Лукьяненко, О. О. Макаров, В. А. Матков-ский // Управление большими системами : труды XVIII Всероссийской школы-конференции молодых ученых, (5-8 сентября 2022 г., Челябинск) / Министерство науки и высшего образования Российской Федерации Южно-Уральский государственный университет Институт проблем управления им. В.А. Трапезникова Российской академии наук ; под общей редакцией академика РАН Д.А. Новикова и заслуженного деятеля науки РФ О.В. Логиновского. — Челябинск : Издательский центр ЮУрГУ. — 2022. — С. 469—475.

45. Сапоженко, А. А. О поиске максимального верхнего нуля монотонных функций на ранжированных множествах / А. А. Сапоженко // Ж. вы-числ. матем. и матем. физ. — 1991. — Т. 31, № 12. — С. 1871—1884.

46. Сигал, И. Х. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы / И. Х. Сигал. — 2003. — 240 с.

47. Солнцева, М. О. Применение методов кластеризации узлов на графах с разреженными матрицами смежности в задачах логистики / М. О. Солнцева, Б. Г. Кухаренко // Труды МФТИ. — 2013. — Т. 5, № 3. — С. 75—83.

48. Специфика построения многоагентных маршрутов в иерархических сетях / М. Г. Козлова, В. А. Лукьяненко, О. О. Макаров, Л. И. Руденко // Таврический вестник информатики и математики. — 2022. — №2(55). —

C. 7—29.

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

асимметричной задаче коммивояжера / М. Ю. Хачай, Е. Д. Незнахина, К. В. Рыженко // Тр. ИММ УрО РАН. — 2022. — Т. 28, № 3. — С. 241—258.

50. Штовба, С. Д. Муравьиные алгоритмы / С. Д. Штовба // Exponenta Pro. Математика в приложениях. — 2003. — № 4. — С. 70—75.

51. A branch and cut algorithm for the VRP with satellite facilities / J. Bard, L. Huang, M. Dror, P. Jaillet // IIE Transactions. — 1998. — Vol. 30. — P. 821—834. — DOI: 10.1023/A:1007500200749.

52. A Chaotic Genetic Algorithm with Variable Neighborhood Search for Solving Time-Dependent Green VRPTW with Fuzzy Demand / H. Fan, R. Xiaoxue, Z. Yueguang, Z. Zimo, F. Houming // Symmetry. — 2022. — Vol. 14, no. 10. — DOI: 10.3390/sym14102115.

53. A Comprehensive Review on Scatter Search: Techniques, Applications, and Challenges / M. Kalra, S. Tyagi, V. Kumar, M. Kaur, W. Mashwani, H. Shah, K. Shah // Mathematical Problems in Engineering. — 2021.

54. A Parallel Tabu Search Heuristic for the Vehicle Routing Problem with Time Windows / P. Badeau, M. Gendreau, F. Guertin, J. Potvin, D. Taillard // Transportation Research-C. — 1997. — Vol. 5. — P. 109—122.

55. A Proposed Solution to Travelling Salesman Problem using Branch and Bound / A. Rastogi, K. Shrivastava, N. Payal, R. Singh // International Journal of Computer Applications. — 2013. — Vol. 65(5). — P. 44—49.

56. A survey on new generation metaheuristic algorithms / T. Dokeroglu, E. Sevin, T. Kucukyilmaz, A. Cosar // Comput. Ind. Eng. — 2019. — Vol. 137, no. 5. — P. 6101—6167.

57. A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows / D. Taillard, P. Badeau, M. Gendreau, F. Guertin, J. Potvin // Transportation Science. — 1997. — Vol. 31, no. 2. — P. 170—186.

58. Alipour, M. A new local search heuristic based on nearest insertion into the convex hull for solving Euclidean TSP / M. Alipour, S. Razavi // International Journal of Operational Research. — 2019. — P. 409—429.

59. An iterated local search for the Traveling Salesman Problem with release dates and completion time minimization / C. Archetti, D. Feillet, A. Mor, G. Speranza // Computers & Operations Research. — 2018. — Vol. 98. — P. 24—37.

60. Azzi, A. Drug inventory management and distribution: outsourcing logistics to third-party providers / A. Azzi, F. Sgarbossa, M. Bonin // Strategic Outsourcing: An International Journal. — 2013. — Vol. 6, no. 1. — P. 48—64.

61. Bartholdi, J. A routing system based on spacefilling curves / J. Bartholdi // Georgia Institute of Technology. — 1995. — P. 1—22.

62. Basel, J. Random Tours in the Traveling Salesman Problem: Analysis and Application / J. Basel, T. Willemain // Computational Optimization and Applications. — 2001. — Vol. 20. — P. 211—217.

63. Baum, E. Towards practical neural computation for combinatorial optimization problems / E. Baum // AIP Conference Proceedings. — 1986. — Vol. 151. — P. 53—58.

64. Bektas, T. The multiple traveling salesman problem: an overview of formulations and solution procedures / T. Bektas // Omega. — 2006. — Vol. 34, no. 3. — P. 209—219.

65. Beltrami, E. J. Networks and vehicle routing for municipal waste collection / E. J. Beltrami, L. D. Bodin // Networks. — 1974. — Vol. 4, no. 1. — P. 65—94. — DOI: https://doi.org/10.1002/net.3230040106.

66. Boettcher, S. Optimization with Extremal Dynamics / S. Boettcher, A. Per-cus // Physical Review Letters, American Physical Society (APS). — 2001. — Vol. 86, no. 23. — P. 5211—5214.

67. Boettcher, S. Extremal Optimization: Methods derived from Co-Evolution / S. Boettcher, G. Percus // Proceedings of the 1st Annual Conference on Genetic and Evolutionary Computatione. — 1999. — Vol. 1. — P. 825—832.

68. Bouridah, A. A scatter search algorithm to configure service function chaining / A. Bouridah, H. Belhadef // International Journal of Internet Technology and Secured Transactions. — 2020. — Vol. 10, no. 6. — P. 654—674.

69. Casco, D. Vehicle routing with backhauls: models, algorithms, and case studies / D. Casco, B. Golden, E. Wasil. — 1988.

70. Clarke, G. Scheduling of Vehicles from a Central Depot to a Number of Delivery Points / G. Clarke, J. Wright // Operations Research. — 1964. — Vol. 12(4). — P. 568—581.

71. Concorde TSP Solver. — URL: https://www.math.uwaterloo.ca/tsp/ concorde.html (visited on 06/11/2023).

72. Construction heuristics for the asymmetric TSP / F. Glover, G. Gutin, A. Yeo, A. Zverovich // European Journal of Operational Research. — 2001. — Vol. 129, no. 3. — P. 555—568.

73. Croes, G. A Method for Solving Traveling-Salesman Problems / G. Croes // Operations Research. — 1958. — Vol. 6, no. 6. — P. 791—812.

74. Dantzig, G. B. The Truck Dispatching Problem / G. B. Dantzig, J. H. Ramser // Management Science. — 1959. — Vol. 6, no. 1. — P. 80—91.

75. Dorigo, M. Ant Colonies for the Traveling Salesman Problem / M. Dorigo, L. Gambardella. — 1997.

76. Dorigo, M. Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem / M. Dorigo, L. Gambardella. — 1997.

77. Dror, M. Vehicle routing with split deliveries / M. Dror, G. Laporte, P. Trudeau // Discrete Applied Mathematics. — 1994. — Vol. 50, no. 3. — P. 239—254. — DOI: https://doi.org/10.1016/0166-218X(92)00172-I.

78. Durbin, R. An analogue approach to the travelling salesman problem using an elastic net method / R. Durbin, D. Willshaw // Nature. — 1987. — Vol. 326. — P. 689—691.

79. Enhanced Self-Organizing Map Solution for the Traveling Salesman Problem / J. Dantas, A. Maximo, M. Yoneyama, Takashi // In: Encontro Nacional de Inteligencia Artificial e Computacional (ENIAC). — 2021. — Vol. 18. — P. 799—802.

80. Feo, T. Greedy Randomized Adaptive Search Procedures / T. Feo, M. Resende // Journal of Global Optimization. — 1995. — Vol. 6. — P. 109—133.

81. Figliozzi, M. An iterative construction and improvement algorithm for the vehicle routing problem with soft time Windows / M. Figliozzi // Transp. Res. Part C, Emerg Technol. — 2010. — Vol. 18, no. 5. — P. 668—793.

82. Fisher, M. Optimal Solution of Vehicle Routing Problems Using Minimum K-trees / M. Fisher // Operations Research. — 1994. — P. 626—642.

83. Flood, M. The Traveling Salesman Problem / M. Flood // Operations Research. — 1956. — Vol. 4. — P. 61—75.

84. Gathering Strength, Gathering Storms: Knowledge Transfer via Selection for VRPTW / W. Xu, X. Wang, Q. Guo, X. Song, R. Zhao, G. Zhao, Y. Yang, T. Xu, D. He // Mathematics. — 2022. — Vol. 10, no. 16. — P. 2888. — DOI: 10.3390/math10162888.

85. Ge, J. Research on vehicle routing problem with soft time windows based on hybrid tabu search and scatter search algorithm / J. Ge, X. Liu, G. Liang // Computers, Materials & Continua. — 2020. — Vol. 64, no. 3. — P. 1945—1958.

86. Gehring, H. A parallel hybrid volutionary metaheuristic for the vehicle routing problem with time windows / H. Gehring, J. Hornberger // Proc. of EUROGEN99. — 2001. — P. 57—64.

87. GELS-GA: Hybrid metaheuristic algorithm for solving Multiple Travelling Salesman Problem / A. Hosseinabadi, M. Kardgar, M. Shojafar, S. Shamshir-band, A. Abraham // 14th International Conference on Intelligent Systems Design and Applications. — 2014. — P. 76—81.

88. Gillett, B. E. A Heuristic Algorithm for the Vehicle-Dispatch Problem / B. E. Gillett, L. R. Miller // Operations Research. — 1974. — P. 340—349.

89. Glover, F. Heuristics for integer programming using surrogate constraints / F. Glover // Decision Sciences. — 1977. — Vol. 8. — P. 156—166.

90. Glover, F. Tabu Search—Part I / F. Glover // ORSA Journal on Computing. — 1989. — Vol. 1(3). — P. 190—206.

91. Goncalves, J. Biased random-key genetic algorithms for combinatorial optimization / J. Goncalves, M. Resende //J Heuristics. — 2011. —Vol. 17. — P. 487—525.

92. Goodrich, M. The christofides approximation algorithm / M. Goodrich, R. Tamassia // Algorithm Design and Applications, Wiley. — 2015. — P. 513—514.

93. Gutin, G. The traveling salesman problem and its variations / G. Gutin, A. Punnen. — Kluwer Academic Publishers, 2002. — 62 p.

94. Gutin, G. Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP / G. Gutin, A. Yeo, A. Zverovich // Discrete Applied Mathematics. — 2002. — Vol. 117, no. 1. — P. 81—86.

95. Hu, Y. Solving the TSP by the AALHNN algorithm / Y. Hu, Q. Duan // Mathematical biosciences and Engineering : MBE. — 2022. — Vol. 19. — P. 3427—3448. — DOI: 10.3934/mbe.2022158.

96. Hybrid multiobjective evolutionary algorithm with fast sampling strategy-based global search and route sequence difference-based local search for VRPTW / W. Zhang, D. Yang, G. Zhang, M. Gen // Expert Systems with Applications. — 2020. — Vol. 145. — P. 113—151. — DOI: https://doi. org/10.1016/j.eswa.2019.113151.

97. Johnson, D. The Traveling Salesman Problem: A Case Study in Local Optimization / D. Johnson, L. McGeoch. — 2008. — DOI: 10.2307/j.ctv346t9c. 13.

98. Junger, M. The ABACUS system for branch-and-cut-and-price algorithms in integer programming and combinatorial optimization / M. Junger, S. Thienel // Software: Practice and Experience. — 2000. — P. 1325—1352.

99. Jungwirth, A. The vehicle routing problem with time windows, flexible service locations and time-dependent location capacity / A. Jungwirth, R. Frey, R. Kolisch // TUM Technical Report (Operations Management). — 2020.

100. K-Path Cuts for the Vehicle Routing Problem with Time Windows / N. Kohl, J. Desrosiers, O. Madsen, M. Solomon, F. Soumis // Technical Report IM-M-REP-1997-12. Technical University of Denmark. — 1997.

101. Kai, A. A Simple Algorithm for Solving Travelling Salesman Problem / A. Kai, X. Mingrui // Proceedings of the 2012 Second International Conference on Instrumentation, Measurement, Computer, Communication and Control, Harbin, China. — 2012. — P. 931—935.

102. Kang, M. Accelerated bregman method for linearly constrained l\ — l2 minimization / M. Kang, S. Yun, H. Woo //J. Sci. Comput. — 2013. — P. 515—534.

103. Karlin, A. A (slightly) improved approximation algorithm for metric TSP / A. Karlin, N. Klein, O. G. // Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. — 2021. — P. 32—45.

104. Karp, R. A Patching Algorithm for the Nonsymmetric Traveling-Salesman Problem / R. Karp // SIAM J. Comput. — 1979. — Vol. 8. — P. 561—573.

105. Kilby, P. Guided Local Search for the Vehicle Routing Problem with Time Windows / P. Kilby, P. Prosser, P. Shaw // In: Vo, S., Martello, S., Osman, I.H., Roucairol, C. (eds) Meta-Heuristics. Springer, Boston, MA. — 1999.

106. Kilic, I. Concave Hull-Based Heuristic Algorithm For TSP / I. Kilic, K. Mostarda, L. Novel // Operations Research Forum. — 2022. — Vol. 3, no. 2. — P. 1—45.

107. Knox, J. Tabu search performance on the symmetric traveling salesman problem / J. Knox // Computers & Operations Research. — 1994. — Vol. 21, no. 8. — P. 867—876.

108. Konda, V. Actor-Critic Algorithms / V. Konda, J. Tsitsiklis // Advances in Neural Information Processing Systems. MIT Press. — 1999. — Vol. 12. — P. 48—64.

109. Kummer, N. A biased random key genetic algorithm applied to the VRPTW with skill requirements and synchronization constraints / N. Kummer, L. Bu-riol, O. Araujo // Proceedings of the 2020 Genetic and Evolutionary Computation Conference. — 2020. — P. 717—724.

110. Kuznetsov, A. Continuous optimisation problem and game theory for multi-agent pathfinding / A. Kuznetsov, A. Schumann, M. Rataj // International Journal of Game Theory. — 2023. — Vol. 53. — P. 1—41. — DOI: 10.1007/s00182-023-00851-6.

111. Laporte, G. Exact Algorithms for the Vehicle Routing Problem / G. Laporte, Y. Nobert // North-Holland Mathematics Studies. — 1987. — Vol. 132. — P. 147—184.

112. Lazarev, A. A metric approach for scheduling problems with minimizing the maximum penalty / A. Lazarev, D. Lemtyuzhnikova, F. Werner // Applied Mathematical Modelling. — 2021. — Vol. 1902. — P. 1163—1176.

113. Lenstra, J. K. Complexity of vehicle routing and scheduling problems / J. K. Lenstra, A. H. G. R. Kan // Networks. — 1981. — Vol. 11, no. 2. — P. 221—227. — DOI: https://doi.org/10.1002/net.3230110211.

114. Luo, Y. Design and Improvement of Hopfield network for TSP / Y. Luo // Proceedings of the 2019 International Conference on Artificial Intelligence and Computer Science. — 2019. — P. 79—83.

115. Maggioni, F. The Multi-path Traveling Salesman Problem with Stochastic Travel Costs: Building Realistic Instances for City Logistics Applications / F. Maggioni, G. Perboli, R. Tadei // Transportation Research Procedia. — 2014. — Vol. 3. — P. 528—536.

116. Mahmoud, M. Three Strategies Tabu Search for Vehicle Routing Problem with Time Windows / M. Mahmoud, A. Hedar // Computer Science and Information Technology. — 2014. — Vol. 2. — P. 108—119.

117. Mandziuk, J. Solving the travelling salesman problem with a hopfield-type neural network / J. Mandziuk // Demonstratio Mathematica. — 1996. — Vol. 29, no. 1. — P. 219—232.

118. Melnikov, A. Improvement of the Vehicles Fleet Structure of a Specialized Motor Transport Enterprise / A. Melnikov, I. Lyubimov, K. Manayev // Procedia Engineering. — 2016. — Vol. 150. — P. 1200—1208.

119. Misevicius, A. Combining 2-OPT, 3-OPT and 4-OPT with K-SWAP-KICK perturbations for the traveling salesman problem / A. Misevicius // Conference: 17th International Conference on Information and Software TechnologiesAt: Kaunas. — 2011.

120. Mladenovic, N. Variable neighborhood search / N. Mladenovic, P. Hansen // Computers and Operations Research. — 1997. — Vol. 24, no. 11. — P. 1097—1100.

121. Moreira, A. Concave hull: A k-nearest neighbours approach for the computation of the region occupied by a set of points / A. Moreira, M. Santos // Conference: GRAPP 2007, Proceedings of the Second International Conference on Computer Graphics Theory and Applications, Barcelona, Spain. — 2007. — P. 61—68.

122. Morton, G. A Computer Oriented Geodetic Data Base and a New Technique in File Sequencing / G. Morton. — International Business Machines Company, 1966. — 32 p.

123. Multi-objective multi-factorial memetic algorithm based on bone route and large neighborhood local search for VRPTW / Z. Zhou, X. Ma, Z. Liang, Z. Zhu // IEEE Congress on Evolutionary Computation (CEC). — 2020. — P. 1—8. — DOI: 10.1109/CEC48606.2020.9185528.

124. Nasri, M. Multithreading parallel robust approach for the VRPTW with uncertain service and travel times / M. Nasri, I. Hafidi, A. Metrane // Symmetry. — 2021. — Vol. 13, no. 36. — P. 1—16. — DOI: 10.3390/sym13010036.

125. NetworkX. —URL: https://networkx.org/documentation/stable/reference/ algorithms/index.html (visited on 05/24/2023).

126. Neuenfeldt, A. A greedy randomized adaptive search procedure application to solve the travelling salesman problem / A. Neuenfeldt, L. Guimaraes // International Journal of Industrial Engineering and Management. — 2019. — Vol. 10, no. 3. — P. 238—242.

127. Norman, M. The euclidean traveling salesman problem and a space-filling curve / M. Norman, P. Moscato // Chaos Solitons and Fractals. — 1995. — Vol. 6. — P. 389—397.

128. On the Neighborhood Structure of the Traveling Salesman Problem Generated by Local Search Moves / G. Stattenberger, M. Dankesreiter, F. Baumgartner, J. Schneider // Journal of Statistical Physics. — 2007. — Vol. 129. — P. 623—648. — DOI: 10.1007/s10955-007-9382-1.

129. Papadimitriou, C. H. On two geometric problems related to the travelling salesman problem / C. H. Papadimitriou, U. V. Vazirani // Journal of Algorithms. — 1984. — Vol. 5, no. 2. — P. 231—246.

130. Physical Distribution Management / C. French, W. Smykay, D. Bowersox, F. Mossman // American Journal of Agricultural Economics. — 1961. — Vol. 43, no. 3. — P. 728—730.

131. Potvin, J. Genetic algorithms for the traveling salesman problem / J. Potvin // Annals of Operations Research. — 1996. — Vol. 63. — P. 337—370.

132. Poullet, J. Leveraging Machine Learning to Solve the Vehicle Routing Problem with Time Windows / J. Poullet. — Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2020. — 125 p.

133. pyCombinatorial. —URL: https://github.com/Valdecy/pyCombinatorial (visited on 05/24/2023).

134. PyConcorde. —URL: https://github.com/jvkersch/pyconcorde (visited on 06/11/2023).

135. Rakhmangulov, A. Mathematical Model of Optimal Empty Rail Car Distribution at Railway Transport Nodes / A. Rakhmangulov, A. Kolga, N. Osintsev // Transp. Probl. — 2014. — Vol. 9. — P. 19—32.

136. Rosenkrantz, D. An analysis of several heuristics for the traveling salesman problem / D. Rosenkrantz, R. Stearns, P. Lewis // In: Ravi, S.S., Shukla, S.K. (eds) Fundamental Problems in Computing. Springer, Dordrecht. — 2009. — P. 45—69.

137. Russell, S. Artificial Intelligence: A Modern Approach / S. Russell, S. Russell, P. Norvig. — Pearson series in artificial intelligence, University of California at Berkeley, Published by Pearson, 2020. — 1136 p.

138. Sahin, M. Solving TSP by using combinatorial Bees algorithm with nearest neighbor method / M. Sahin // Neural Comput & Applic. — 2023. — Vol. 35. — P. 1863—1879.

139. Scholz, J. Genetic algorithms and the traveling salesman problem a historical review / J. Scholz // Proc. of the MInf Seminar at the Dept. of Computer Science of the Hamburg University of Applied Sciences. — 2019. — P. 1—8.

140. Scipy. — URL: https://scipy.org/ (visited on 06/11/2023).

141. Shaw, P. Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems / P. Shaw. — 1998.

142. Skinderowicz, R. Improving Ant Colony Optimization efficiency for solving large TSP instances / R. Skinderowicz // Applied Soft Computing. — 2022. — Vol. 120. — P. 1—28.

143. Solomon benchmark. — URL: https: / /www.sintef. no/projectweb/top/ vrptw/solomon-benchmark (visited on 05/12/2023).

144. Solving the vehicle routing problem with time windows and multiple routes exactly using a pseudo-polynomial model / R. Macedo, C. Alves, J. Carvalho, F. Clautiaux, S. Hanafi // European Journal of Operational Research. — 2011. — Vol. 214. — P. 536—545.

145. Stutzle, T. Local search algorithms for combinatorial problems - analysis, improvements, and new applications / T. Stutzle. — 1999.

146. Svensson, O. A constant-factor approximation algorithm for the asymmetric Traveling Salesman Problem / O. Svensson, J. Tarnawski, L. Vegh // Proc. of the 50th Annual ACM Symposium on Theory of Computing. — 2018. — P. 204—213.

147. Taillard, D. FANT: Fast Ant System / D. Taillard // Technical Report ID-SIA-46-98. IDSIA, Lugano, Switzerland. — 1998.

148. Thammano, A. Hybrid modified ant system with sweep algorithm and path relinking for the capacitated vehicle routing problem / A. Thammano, P. Rungwachira // Heliyon. — 2021. — Vol. 7, no. 9. — P. 1—15.

149. Toth, P. The vehicle routing problem / P. Toth, D. Vigo. — SIAM Monographs on DiscreteMathematics, Applications, Philadelphia, 2002. — 367 p.

150. Traub, V. Improving on Best-of-Many-Christofides for T-tours / V. Traub // Operations Research Letters. — 2020. — Vol. 48, no. 6. — P. 798—804.

151. Traub, V. An improved approximation algorithm for ATSP / V. Traub, J. Vy-gen // Proc. of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. — 2020. — P. 1—13.

152. TSPLIB. — URL: http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95 (visited on 05/24/2023).

153. Two-Stage Multi-objective Evolutionary Algorithm Based on Classified Population for Tri-objective VRPTW / H. Shu, K. Zhou, Z. He, X. Hu // International Journal of Unconventional Computing. — 2021. — Vol. 16, no. 2. — P. 141—171.

154. Uthayakumar, R. Pharmaceutical supply chain and inventory management strategies: Optimization for a pharmaceutical company and a hospital / R. Uthayakumar, S. Prlyan // Oper. Res. Heal Care. — 2013. — Vol. 2, no. 3. — P. 52—64.

155. Vehicle Routing Problem with Time Windows / B. Kallehauge, J. Larsen, O. Madsen, M. Solomon. — 2006.

156. Vehicle Routing Problem with Time Windows and Simultaneous Delivery and Pick-Up Service Based on MCPSO / X. Gan, Y. Wang, S. Li, B. Niu // Mathematical Problems in Engineering. — 2012.

157. Voudouris, C. Guided local search and its application to the traveling salesman problem / C. Voudouris, E. Tsang // European Journal of Operational Research. — 1999. — Vol. 113, no. 2. — P. 469—499.

158. Yao, X. TSP Solving Utilizing Improved Ant Colony Algorithm / X. Yao, Y. Ou, K. Zhou // Journal of Physics: Conference Series. — 2021. — Vol. 2129. — P. 12—26.

Список рисунков

1.1 Иерархическая MTSP с m кластерами, d РРЦ и РЦ....................31

1.2 Маршрут интегрирования узлов кластеров нижнего уровня..........34

2.1 Схема решения MTSP по близкой задаче................................53

2.2 Схема ИСМЭ................................................................54

2.3 Методы решения задач маршрутизации..................................55

2.4 Блок-схема включения вершин в кластер с учетом временных окон . 68

2.5 Блок-схема расчета статистики распределения весов дуг графа ... 75

2.6 Результаты работы алгоритма 9 для графа a280 из [152] ..............80

2.7 Сравнение маршрутов TSP возмущенного и исходного графа a280

из [152] ......................................................................82

2.8 Результаты работы алгоритма 9..........................................83

3.1 Распределение длин дуг для графа u2319 из [152]......................85

3.2 Распределение длин дуг для графа pla7397 из [152]....................86

3.3 Схема работы модуля кластеризации....................................89

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

3.5 Схема расчетного модуля программного продукта PPTM..............91

3.6 Схема «Алгоритмического блока» PPTM................................92

3.7 Результаты работы алгоритмов............................................93

3.8 Анализ алгоритма типа Кристофидеса и Concorde......................96

3.9 Результаты работы алгоритмов MTSP....................................98

3.10 Результаты работы алгоритмов MTSP....................................99

3.11 Распределение длин дуг графа Большой Ялты..........................99

3.12 Адаптивная иерархическая кластеризация для Ялты.........101

3.13 Построение многоагентных маршрутов в чрезвычайных ситуациях

для данных по Большой Ялте ............................................102

3.14 Построение маршрутов для данных по Большой Ялте.........102

3.15 Маршрут для двух агентов на данных по Большой Ялте.......103

3.16 Маршрут для трех агентов на данных по Большой Ялте.......104

3.17 Маршрут для четырех агентов на данных по Большой Ялте.....104

3.18 Маршрут для пяти агентов на данных по Большой Ялте.......104

3.19 Принципиальная схема программы многоагентной инфраструктурной маршрутизации...................105

3.20 Результаты работы «Программы построения иерархических маршрутов в задачах маршрутизации на сложных сетях» ......107

3.21 Архитектура приложения МДТ.....................109

3.22 Результаты работы МДТ.........................113

3.23 Результаты работы МДТ.........................114

Список таблиц

1 Пример структуры файла данных........................................62

2 Метрические характеристики графа ......................................74

3 Результаты расчетов метрических характеристик......................87

4 Результаты расчетов метрических характеристик. Продолжение таблицы 3 ....................................................................88

5 Результаты расчетов метаэвристик........................................93

6 Результаты расчетов метаэвристик. Продолжение таблицы 5..........94

7 Результаты расчетов метаэвристик. Продолжение таблицы 5 ..........94

8 Результаты расчетов метаэвристик. Продолжение таблицы 5 ..........95

9 Результаты расчетов метаэвристик. Продолжение таблицы 5 ..........95

10 Результаты работы алгоритмов МТБР....................................97

Приложение А Метаэвристические алгоритмы

2-ор1

Алгоритм 2-ор1 — это простой эвристический алгоритм, используемый для улучшения решения ТБР. Основная идея алгоритма заключается в итеративном удалении двух ребер из маршрута ТБР и замене их двумя новыми ребрами, которые соединяют маршрут другим способом, чтобы получить более короткое общее расстояние.

Алгоритм 12. 2-ор1

Вход: Список точек вершин графа. Выход: Найденный оптимальный маршрут.

1. Начать с начального маршрута по вершинам, например, случайно сгенерированного маршрута или простого эвристического решения.

2. Выбрать два ребра в маршруте, которые не имеют общей конечной точки.

3. Удалить эти два ребра из маршрута, создав два пробела в маршруте.

4. Соединить маршрут, выбрав кратчайший путь между двумя разрывами, т.е. найти две конечные точки разрывов и соединить их новым ребром, которое является кратчайшим путем между ними.

5. Повторять шаги 2-4 до тех пор, пока не будет достигнуто дальнейшее улучшение.

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

2.5-ор1

Алгоритм 2.5-ор1 является расширением Алгоритма 12 (2-ор^ для решения задачи коммивояжера (ТБР). Он называется 2.5-ор^ потому что в нем рассматриваются три ребра за один раз, а не два, как в Алгоритме 12 (2-ор^.

Основная идея алгоритма 2.5-ор1 заключается в том, чтобы удалить три ребра из маршрута ТБР, а затем соединить маршрут с помощью трех новых ребер другим способом, чтобы получить меньшее общее расстояние. Алгоритм работает следующим образом:

Алгоритм 13. 2.5-ор1

Вход: Список точек вершин графа. Выход: Найденный оптимальный маршрут.

1. Начать с начального маршрута по вершинам, например, случайно сгенерированного маршрута или простого эвристического решения.

2. Выбрать три ребра в маршруте, которые не имеют общей конечной точки.

3. Удалить эти три ребра из маршрута, создав три пробела в маршруте.

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

5. Повторять шаги 2-4 до тех пор, пока не будет достигнуто дальнейшее улучшение.

Алгоритм 2.5-ор1 исследует большую область пространства решений, чем Алгоритм 12 (2-ор^, что может привести к лучшим решениям. Однако он также требует больше вычислительных ресурсов и может занимать больше времени, чем Алгоритм 12 (2-ор^. Алгоритм 2.5-ор1 также можно комбинировать с другими метаэвристическими алгоритмами для дальнейшего улучшения качества решения.

3-ор1

Алгоритм 3-ор1 является еще одним расширением Алгоритма 12 (2-ор^ для решения задачи коммивояжера (ТБР). Основная идея алгоритма 3-ор1 заключается в том, чтобы удалить три ребра из маршрута ТБР, а затем соединить маршрут с помощью трех новых ребер другим способом, чтобы получить более короткое общее расстояние.

Алгоритм 14. 3-ор1

Вход: Список точек вершин графа. Выход: Найденный оптимальный маршрут.

1. Начать с начального маршрута по вершинам, например, случайно сгенерированного маршрута или простого эвристического решения.

2. Выбрать три ребра в маршруте, которые не имеют общей конечной точки.

3. Удалить эти три ребра из маршрута, создав три пробела в маршруте.

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

5. Повторять шаги 2-4 до тех пор, пока не удастся добиться дальнейших улучшений.

Семь возможных комбинаций трех новых ребер получаются путем рассмотрения всех возможных способов соединения трех разрывов. Алгоритм 3-opt исследует большую область пространства решений, чем Алгоритм 12 (2-opt) и Алгоритм 13 (2.5-opt), что может привести к еще лучшим решениям. Однако он также требует больше вычислительных ресурсов и может быть более трудоемким, чем Алгоритмы 12 (2-opt) и 13 (2.5-opt).

Алгоритм 3-opt также можно комбинировать с другими метаэвристиче-скими алгоритмами для дальнейшего улучшения качества решения.

2-opt stochastic

2-opt stochastic — это вариант Алгоритма 12 (2-opt) для решения задачи коммивояжера (TSP). Основная идея алгоритма заключается в случайном выборе набора ребер в маршруте и последующем применении Алгоритма 12 (2-opt) только к этим ребрам, а не ко всему маршруту. Такой подход может помочь избежать локального оптимума и исследовать большее пространство решений.

Алгоритм 15. 2-opt stochastic

Вход: Список точек вершин графа. Выход: Найденный оптимальный маршрут.

1. Начать с начального маршрута по вершинам, например, случайно сгенерированного маршрута или простого эвристического решения.

2. Выбрать случайное подмножество ребер в маршруте.

3. Применить Алгоритм 12 (2-ор^ только к выбранным ребрам, создав новый подмаршрут.

4. Заменить выбранные ребра в исходном маршруте новым подмаршрутом.

5. Повторять шаги 2-4 в течение определенного количества итераций или до тех пор, пока не будет достигнуто дальнейшее улучшение.

Количество ребер, выбираемых на каждой итерации, может быть фиксированным или случайным. 2-opt stochastic можно рассматривать как гибрид между Алгоритмом 12 (2-opt) и рандомизированным подходом, который исследует большее пространство решений.

Как и другие метаэвристические алгоритмы, 2-opt stochastic не гарантирует нахождения оптимального решения, но часто может находить качественные решения за разумное время. Эффективность алгоритма зависит от выбора параметров и конкретных характеристик решаемого экземпляра TSP.

2.5-opt stochastic

2.5-opt stochastic — это вариант Алгоритма 13 (2.5-opt) для решения задачи коммивояжера (TSP), включающий стохастический элемент. Как и Алгоритм 13 (2.5-opt), он рассматривает три ребра за раз при выполнении оптимизации маршрута TSP.

Основная идея 2.5-opt stochastic заключается в случайном выборе набора из трех ребер в маршруте и последующем применении Алгоритма 13 (2.5-opt) только к этим ребрам, а не ко всему маршруту.

Алгоритм 16. 2.5-opt stochastic

Вход: Список точек вершин графа. Выход: Найденный оптимальный маршрут.

1. Начать с начального маршрута по вершинам, например, случайно сгенерированного маршрута или простого эвристического решения.

2. Выбрать случайный набор из трех ребер в маршруте, которые не имеют общей конечной точки.

3. Применить Алгоритм 13 (2.5-ор^ только к выбранным трем ребрам, создав новый под-маршрут.

4. Заменить три выбранных ребра в исходном маршруте новым подмаршрутом.

5. Повторять шаги 2-4 в течение определенного количества итераций или до тех пор, пока не будет достигнуто дальнейшее улучшение.

Количество наборов из трех ребер для выбора в каждой итерации может быть фиксированным числом или случайным. 2.5-opt stochastic можно рассматривать как гибрид между Алгоритмом 13 (2.5-opt) и рандомизированным подходом, который исследует большее пространство решений.

Как и другие метаэвристические алгоритмы, 2.5-opt stochastic не гарантирует нахождения оптимального решения, но часто может находить качественные решения за разумное время. Эффективность алгоритма зависит от выбора параметров и конкретных характеристик решаемого экземпляра TSP.

3-opt stochastic

3-opt stochastic — это вариант Алгоритма 14 (3-opt) для решения задачи коммивояжера (TSP), включающий стохастический элемент. Как и Алгоритм 14 (3-opt), он рассматривает три ребра за раз при выполнении оптимизации маршрута TSP.

Основная идея 3-opt stochastic заключается в случайном выборе набора из трех ребер в маршруте и последующем применении Алгоритма 14 (3-opt) только к этим ребрам, а не ко всему маршруту. Такой подход может помочь выйти из локального оптимума и исследовать большее пространство решений.

Алгоритм 17. 3-opt stochastic

Вход: Список точек вершин графа. Выход: Найденный оптимальный маршрут.

1. Начать с начального маршрута по вершинам, например, случайно сгенерированного маршрута или простого эвристического решения.

2. Выбрать случайный набор из трех ребер в маршруте, которые не имеют общей конечной точки.

3. Применить Алгоритм 14 (3-ор^ только к выбранным трем ребрам, создав новый подмарш-рут.

4. Заменить три выбранных ребра в исходном маршруте новым подмаршрутом.

5. Повторять шаги 2-4 в течение определенного количества итераций или до тех пор, пока не будет достигнуто дальнейшее улучшение.

Количество наборов из трех ребер для выбора на каждой итерации может быть фиксированным числом или случайным. 3-opt stochastic можно рассматривать как гибрид между Алгоритмом 14 (3-opt) и рандомизированным подходом, который исследует большее пространство решений.

Как и другие метаэвристические алгоритмы, 3-opt stochastic не гарантирует нахождения оптимального решения, но он часто может находить качественные решения за разумное время. Эффективность алгоритма зависит от выбора параметров и конкретных характеристик решаемого экземпляра TSP.

Ant Colony Optimization

Ant Colony Optimization (ACO) — это метаэвристический алгоритм, инспирированный поведением муравьев в поисках пищи. ACO применялся для решения многих задач оптимизации, включая задачу коммивояжера (TSP).

Алгоритм ACO для TSP позволяет находить качественные решения за разумное время, но его эффективность зависит от выбора параметров и конкретных характеристик решаемого экземпляра TSP, он работает следующим образом:

Алгоритм 18. Ant Colony Optimization

Вход: Список точек вершин графа. Выход: Найденный оптимальный маршрут.

1. Инициализировать граф G (ввести матрицу расстояний D или др.).

2. Задать параметры а, в, Q, tmax, т.

3. Задать значение феромона для каждого ребра , £ G.

4. Распределить всех муравьев между вершинами.

5. Задать первоначальный лучший тур Т* и его длину L*.

6. Инициализировать переменную итераций t = 1

7. Пока t < tmax.

7.1. Для каждого муравья к построить путь Т%(t) согласно правилу 2.1 и рассчитать длину Lk (t).

7.2. Для каждого муравья к сравнить Lk(t) с L*.

7.3. Если Lk(t) < L*, то L* = Lk(t) и T* = Tk(t).

7.4. Для каждого ребра графа произвести обновление феромона по формуле 2.2 и 2.3.

7.5. Увеличить итерацию t = t + 1

8. Вернуть Т* и L*.

BRKGA (Biased Random Key Genetic Algorithm)

Biased Random Key Genetic Algorithm (BRKGA) — это метаэвристический алгоритм, который был применен для решения задачи коммивояжера (TSP). Алгоритм был предложен M. G. C. Resende и C. C. Ribeiro в 2003 году.

В алгоритме BRKGA для TSP каждое решение представлено вектором случайных ключей, которые являются действительными числами от 0 до 1. Затем вектор сортируется, и порядок вершин определяется индексами сортировки. Операция сортировки является смещенной, то есть ключи, которые ближе к 1, скорее всего, будут отсортированы раньше, что приводит к смещению в сторону высококачественных решений.

Алгоритм BRKGA для TSP работает следующим образом:

Алгоритм 19. BRKGA (Biased Random Key Genetic Algorithm)

Вход: Список точек вершин графа. Выход: Найденный оптимальный маршрут.

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

2. Оценить пригодность каждого решения, вычислив длину его маршрута.

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

4. Создать новую популяцию, применив к выбранным решениям генетические операторы (например, кроссовер и мутацию).

5. Оценить пригодность новой популяции.

6. Повторять шаги 3-5 в течение определенного количества итераций или до тех пор, пока не будет найдено удовлетворительное решение.

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

Алгоритм BRKGA для ТБР может находить качественные решения за разумное время, и его можно легко распараллелить, чтобы использовать доступные вычислительные ресурсы. Эффективность алгоритма зависит от выбора параметров и конкретных характеристик решаемого экземпляра ТБР.

Cheapest Insertion

Cheapest Insertion — это эвристический алгоритм для решения задачи коммивояжера (TSP). Алгоритм был впервые предложен Данцигом, Фулкерсоном и Джонсоном в 1954 году.

Cheapest Insertion начинается с частичного маршрута, который содержит две вершины. На каждом шаге алгоритм выбирает вершину, который еще не включен в маршрут, и вставляет его в маршрут таким образом, чтобы минимизировать увеличение длины маршрута. Алгоритм продолжается до тех пор, пока все вершины не будут включены в маршрут. Алгоритм можно описать следующим образом:

Алгоритм 20. Cheapest Insertion

Вход: Список точек вершин графа. Выход: Найденный оптимальный маршрут.

1. Выбрать две вершины произвольно и сформировать маршрут, включающий эти две вершины.

2. Для каждой вершины, который еще не включен в маршрут.

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

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

2.3. Вставить вершину в маршрут на выбранной позиции.

3. Вернуться в начальную вершину, завершив маршрут.

Cheapest Insertion имеет временную сложность 0(п2), где n — количество вершин.

Christofides Algorithm

Christofides Algorithm — это эвристический алгоритм решения TSP. Алгоритм был предложен Никосом Христофидесом в 1976 году и основан на комбинации минимального остовного дерева (Minimum Spanning Tree, MST) и идеального соответствия.

Алгоритм 21. Christofides Algorithm

Вход: Список точек вершин графа. Выход: Найденный оптимальный маршрут.

1. Вычислить минимальное остовное дерево полного графа, содержащего все вершины.

2. Найти множество вершин с нечетной степенью в MST.

3. Вычислить минимальное по весу идеальное соответствие на множестве вершин с нечетной степенью (алгоритм Blossom).

4. Объединить ребра MST и минимально-весового идеального соответствия, сформировать мультиграф.

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

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

Christofides Algorithm имеет наихудшую временную сложность 0(п3), где п — количество вершин. Алгоритм гарантированно выдает маршрут, который максимум в 1,5 раза длиннее оптимального маршрута, что делает его одним из самых эффективных эвристических алгоритмов для TSP.

Clarke & Wright (Savings Heuristic)

Clarke & Wright, также известный как Savings Heuristic, является жадным алгоритмом для решения задачи коммивояжера (TSP). Алгоритм был предложен Кларком и Райтом в 1964 году.

Алгоритм начинается с вычисления значения экономии для каждой пары вершин, которое определяется как сокращение общего расстояния, которое получится в результате объединения двух отдельных маршрутов в один маршрут. Значение экономии вычисляется следующим образом:

5(i,j) = d(0,i) + d(0,j) - d(i,j),

где d(i,j) — расстояние между вершинами i и j, а d(0, i) и d(0,j) — расстояния от начальной вершины до вершин i и j, соответственно. Алгоритм можно описать следующим образом:

Алгоритм 22. Clarke & Wright (Savings Heuristic)

Вход: Список точек вершин графа. Выход: Найденный оптимальный маршрут.

1. Вычислить значение экономии для каждой пары вершин и отсортировать пары в порядке убывания значения экономии.

2. Инициализировать набор маршрутов, каждый из которых содержит одну вершину.

3. Для каждой пары вершин г и ] в отсортированном списке.

3.1. Если г и ] принадлежат разным маршрутам и объединение маршрутов не создает цикла, объединить маршруты в один маршрут.

3.2. Если все пары вершин были рассмотрены, остановиться.

4. Пройти по полученному маршруту, начиная и заканчивая в начальной вершине.

Clarke & Wright (Savings Heuristic) имеет временную сложность 0(п2 logп), где n — количество вершин. Алгоритм может находить качественные решения для небольших и средних экземпляров TSP и часто используется в качестве отправной точки для более продвинутых эвристических алгоритмов.

Concave Hull Algorithm

Concave Hull Algorithm не предназначен специально для решения задачи коммивояжера (TSP), но это полезный алгоритм для нахождения вогнутой оболочки набора точек в двумерном пространстве. Вогнутую оболочку можно представить как фигуру, которая охватывает точки, минимизируя количество выпуклостей, или «неровностей», на границе.

Алгоритм 23. Concave Hull Algorithm

Вход: Список точек вершин графа.

Выход: Найденный маршрут.

1. Отсортировать точки в порядке возрастания их ж-координат.

2. Определить две точки с наименьшей и наибольшей ж-координатами. Эти точки всегда будут частью оболочки.

3. Разделить оставшиеся точки на два набора: слева от прямой, соединяющей первые две точки, и справа.

4. Для каждого набора рекурсивно применить алгоритм, чтобы найти точки, которые образуют вогнутую оболочку этого набора.

5. Объединить две оболочки, чтобы получить общую оболочку.

Concave Hull Algorithm имеет временную сложность 0(n log n), где n — количество точек. Этот алгоритм может быть полезен для определения формы кластера точек или для выявления областей карты, имеющих схожие черты.

Convex Hull Algorithm

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

Алгоритм Convex Hull работает следующим образом:

Алгоритм 24. Convex Hull Algorithm

Вход: Список точек вершин графа. Выход: Найденный оптимальный маршрут.

1. Отсортировать точки в порядке возрастания их ж-координат.

2. Создать пустой стек и поместить в него первые две точки.

3. Для каждой оставшейся точки, начиная с третьей.

3.1. Вытащить верхнюю точку из стека.

3.2. Если следующая точка, текущая верхняя точка и предыдущая верхняя точка образуют поворот против часовой стрелки, переместить текущую точку в стек и перейти к следующей точке.

3.3. Если следующая точка, текущая верхняя точка и предыдущая верхняя точка образуют поворот по часовой стрелке, отбросить текущую верхнюю точку и повторить процесс с новой верхней точкой.

4. Оставшиеся точки в стеке образуют выпуклую оболочку.

Convex Hull Algorithm имеет временную сложность 0(п log п), где n — количество точек. Алгоритм может быть полезен для нахождения границы множества точек или для определения областей карты, которые заключены в границу.

Elastic Net

Elastic Net — это алгоритм машинного обучения, который сочетает методы регуляризации L1 и L2 для достижения баланса между разреженностью и корреляцией при выборе признаков. Он не был специально разработан для решения

задачи коммивояжера (TSP), но был применен к TSP в качестве эвристического алгоритма оптимизации.

В Elastic Net для TSP маршрут представлен в виде набора двоичных переменных, которые указывают, посещается ли каждая вершина или нет. Объективная функция представляет собой комбинацию двух условий: условия расстояния, которые наказывают за более длинные маршруты, и условия разреженности, которые поощряют решения с меньшим количеством посещенных вершин. Показатель разреженности контролируется параметром, который уравновешивает методы регуляризации L1 и L2.

Алгоритм Elastic Net для TSP работает следующим образом:

Алгоритм 25. Elastic Net

Вход: Список точек вершин графа. Выход: Найденный оптимальный маршрут.

1. Инициализировать маршрут как случайную последовательность вершин.

2. Определить объективную функцию как комбинацию члена расстояния и члена разреженности.

3. Оптимизировать объективную функцию с помощью алгоритма Elastic Net.

3.1. Применить методы регуляризации L1 и L2 для выбора подмножества вершин для посещения.

3.2. Использовать метод локального поиска, например, Алгоритм 12 (2-opt) или Алгоритм 14 (3-opt), для улучшения маршрута.

4. Повторять шаг 3, пока не будет достигнут критерий остановки, например, максимальное количество итераций или отсутствие улучшения объективной функции.

Elastic Net показал хорошую производительность при решении небольших и средних экземпляров TSP.

Extremal Optimization

Extremal Optimization — это метаэвристический алгоритм, который изначально был разработан для решения задач оптимизации в физике, но был применен к комбинаторным задачам оптимизации, таким как задача коммивояжера (TSP). Алгоритм основан на концепции самоорганизованной критичности, когда система развивается в направлении критического состояния, при котором ландшафт оптимизации становится более доступным.

В Extremal Optimization для TSP маршрут представлен в виде перестановки вершин. Алгоритм работает следующим образом:

Алгоритм 26. Extremal Optimization

Вход: Список точек вершин графа. Выход: Найденный оптимальный маршрут.

1. Инициализировать маршрут как случайную перестановку вершин.

2. Оценить пригодность маршрута, которая представляет собой общее пройденное расстояние.

3. Если критерий остановки не достигнут, повторить следующие шаги.

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

3.2. Удалить идентифицированную вершину из маршрута и снова вставить ее в позицию, которая приводит к наибольшему улучшению пригодности.