Содержание к диссертации
Введение
1. Анализ и состояние проблем решения транспортных задач 18
1.1 Анали: алгоритмов и методов решения задачи коммивояжера 18
1.2 Анализ и состояние задачи маршрутизации автотранспорта
1.2.1 Построение математической модели задачи маршрутизации автотранспорта 32
1.2.2 Построение критерия оптимизации задачи маршрутизации автотранспорта
1.3 Анализ и состояние задачи разбиения товаров для упаковки в транспортные средства 37
1.4 Анализ алгоритмов и методов решения задач коммивояжера и маршрутизации автотранспорта
1.4.1 Анализ последовательных алгоритмов 41
1.4.2 Анализ итерационных алгоритмов 42
1.4.3 Обзор вероятностных алгоритмов 43
1.4.4 Анализ временной сложности алгоритмов решения задач коммивсяжера и маршрутизации автотранспорта 49
1.5 Выводы 50
2 Разработка биоинспирированных алгоритмов решения задач коммивояжера и маршрутизации автотранспорта 5 2
2.1 Разработка генетического алгоритма для решения задачи маршрутизации автотранспорта 52
2.1.1 Описание структурной схемы генетического алгоритма 52
2.1.2 Разработка кодировки хромосомы 54
2.1.3 Разработка генетических операторов
2.2 Разработка простого муравьиного алгоритма для решения задачи коммивояжера 59
2.3 Построение модификаций муравьиного алгоритма 68
2.3.1 Построение модификации «элитных» муравьев 68
2.3.2 Построение стратегий начального расположения колонии муравьев 2.3.3 Сосдание шаблонов 71
2.3.4 Построение модификации выпрямления 77
2.3.5 Построение модификации «пространственного феромона» 82
2.3.6 Разработка модифицированного муравьиного алгоритма для
решения задачи маршрутизации автотранспорта 83
2.4 Оценке сложности муравьиного алгоритма 89
2.5 Разработка пчелиного алгоритма для решения задачи коммивояжера.. 93
2.6 Разработка метода роя частиц для решения транспортных задач 102
2.7 Выводы 103
3 Построение интегрированного алгоритма маршрутизации автотранспорта 105
3.1 Анали:- построения интегрированных алгоритмов маршрутизации автотранспорта 105
3.2 Разработка архитектуры гибридного алгоритма 105
3.3 Анали; и оценка временной сложности гибридного алгоритма 114
3.4 Выводы 115
4 Экспериментальные исследования 116
4.1 Исследования модифицированного муравьиного алгоритма для задачи коммивояхера 116
4.2 Исследования муравьиного алгоритма для задачи маршрутизации автотранспорта 133
4.3 Исследования пчелиного алгоритма для задачи разбиения товаров с учетом совместимости 137
4.4 Приложения 144
4.5 Выводи 146
Заключение 148
Список используемой литературы
- Анализ и состояние задачи маршрутизации автотранспорта
- Разработка кодировки хромосомы
- Разработка архитектуры гибридного алгоритма
- Исследования муравьиного алгоритма для задачи маршрутизации автотранспорта
Введение к работе
Актуальность темы. В условиях современного развития
информационных технологий, существующие алгоритмы
автоматизированного планирования грузоперевозок не способны найти точное решение или требуют неоправданно большое время работы алгоритма для поиска эффективных решений. Актуальность работы обусловлена большой сложностью и размерностью задач маршрутизации, а также возникновением ее новых верификаций. В связи с этим возникает необходимость разработки новых методик, направлений, алгоритмов для решения задач данного класса. Рассматриваемые в диссертационной работе задачи коммивояжера и маршрутизации автотранспорта являются актуальными. Разработанные роевые алгоритмы позволяют сократить время поиска решений в задачах большой размерности, и в то же время повысить качество получаемых решений. Предложенный интегрированный алгоритм на основе генетического, муравьиного и пчелиного алгоритмов для решения задачи планирования грузоперевозок позволяет найти множество «хороших» решений и выдать рекомендационные решения для лица, принимающего решение (ЛПР). Объектом исследования являются транспортно-логистические процессы. Основным содержанием работы являются теоретические и прикладные исследования транспортных задач и их решения, ориентированные на повышение эффективности управления ими, принятия решения с использованием современных методов обработки информации.
С целью повышения эффективности и качества решения задачи маршрутизации автотранспорта предлагаются новые подходы и алгоритмы, основанные на использовании биоинспирированных методов. К таким методам относятся генетические и роевые алгоритмы. Разработанные модификации алгоритмов позволят повысить качество получаемых решений. Качество решения задачи маршрутизации автотранспорта влияет непосредственно на ценообразование товара. В связи с этим, тема работы связана с разработкой новых методов и алгоритмов решения задач системного анализа, управления, оптимизации, обработки информации решения и принятия решений, к которым относятся транспортно-логистические задачи и задача коммивояжера, также различные верификации задачи маршрутизации автотранспорта.
Цель диссертационной работы. Цель данной работы состоит в разработке и исследовании различных подходов к планированию транспортных грузоперевозок, основанных на методах роевого интеллекта.
Методы исследования. Выполненная работа характеризуется комплексным подходом. Основу для проведения исследований составляют: теория принятия решений, графов, алгоритмов, математической статистики, эволюционного моделирования, коллективной адаптации. Исследование эффективности разработанных алгоритмов проводилось на основе вычислительных экспериментов.
Достоверность результатов. Достоверность результатов подтверждается корректным использованием методов математической статистики, положительными результатами применения разработанных алгоритмов, а также анализом результатов проведенных экспериментальных исследований.
Основные положения, выносимые на защиту.
-
модифицированный муравьиный алгоритм для решения задачи коммивояжера, позволяющего находить решения за меньшее время, чем стандартный муравьиный алгоритм, на стандартных тестах Оливера, Эйлона и др. (стр. 119);
-
модифицированную архитектуру муравьиного алгоритма для решения задач маршрутизации, позволяющего находить решения за меньшее время, чем стандартный муравьиный алгоритм (стр. 84);
-
интегрированную архитектуру процесса планирования грузоперевозок, основанную на методах роевого интеллекта, что позволяет находить решения ближе к оптимальному по сравнению с другими методами (стр. ПО);
-
модифицированную архитектуру биоинспирированных алгоритмов для решения задач коммивояжера и маршрутизации автотранспорта, сочетающую в себе как быстродействие, так и точность при поиске оптимального решения (стр. 113).
Научная новизна работы.
Научная новизна работы заключается в решении задачи маршрутизации автотранспорта на основе модифицированных биоинспирированных алгоритмов, позволяющих получать близкие к оптимуму решения за короткое время в пределах 10 минут. Личный вклад автора заключается в разработке модификаций муравьиного и пчелиного алгоритмов, кодировке хромосомы в генетическом алгоритме, реализации предложенных модифицированных алгоритмов, проведении экспериментальных исследований. В работе:
1.разработаны новые модификации муравьиного алгоритма, позволяющие
ускорить работу алгоритма, а также улучшить качество решения; 2.представлена зависимость временной сложности муравьиного алгоритма от коэффициента эвристики а, зависимость оптимального значения размера колонии от размерности графа для симметричной задачи коммивояжера; 3.разработаны новые и модифицированные алгоритмы маршрутизации автотранспорта на основе методов эволюционного моделирования, позволяющие получать множество квазиоптимальных решений; 4.разработан модифицированный пчелиный алгоритм для решения задачи разбиения, позволяющий находить более качественные разбиения товаров на совместимые множества, чем генетический и муравьиный алгоритмы; 5.разработана стратегия интегрированного поиска на основе заданных критериев оптимизации, позволяющие решать усложненную задачу маршрутизации автотранспорта с учетом временных рамок, множественного депо.
Практическая ценность. Практическая ценность результатов диссертационной работы определяется созданием программного комплекса (ПК) алгоритмов маршрутизации автотранспорта, поиска оптимального пути коммивояжера, разбиения графа, позволяющего использовать разработанные алгоритмы, стратегии и эвристики, проводить сравнительный анализ с существующими аналогами.
Разработанный программный комплекс решения задач коммивояжера и маршрутизации автотранспорта реализован с использованием интегральной среды разработки Code Gear RadStudio 2009 на языке программирования C++ и среды разработки Microsoft Visual Studio 2010 под семейство операционных систем WINDOWS.
Реализация результатов работы. Результаты работы внедрены в научно-исследовательских работах, грантах РФФИИ, выполняемых на кафедре САПР ИТАЮФУ.
Апробация работы. Основные научные и практические результаты работы докладывались, обсуждались и были одобрены на Международных научно-технических конференциях «Интеллектуальные САПР» (г. Геленджик, 2008 - 2013 гг.), Всероссийских научных конференциях молодых ученых и аспирантов (г. Таганрог, г. Ростов-на-Дону, 2008 - 2012 гг.), национальных конференциях по искусственному интеллекту с международным участием (КИИ-08, КИИ-2010), Всероссийской научно-технической конференции (МЭС-2012), 15-й Всероссийской научно-технической конференции МИЭТ-2008. Опубликовано более 40 печатных работ, материалы вошли в отчет по НИР. Опубликована монография «Биоинспирированные алгоритмы. Решение оптимизационных задач».
Публикации. Результаты диссертации отражены в 35 печатных работах, в числе которых 8 - в изданиях, рекомендованных ВАК, и в 4 свидетельствах об официальной регистрации программ для ЭВМ.
Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы. Работа содержит 165 страниц, включая 52 рисунка, 14 таблиц, список литературы из 139 наименований, 4 страницы приложений со свидетельствами об официальной регистрации программ для ЭВМ, 4 страниц приложений актов внедрения результатов диссертационной работы в научно-исследовательские работы.
Анализ и состояние задачи маршрутизации автотранспорта
Задача коммивояжера (ЗК) возникает в обширном классе приложений, но в своей классической формулировке не учитывает многих аспектов задач, возникающих на практике. Введение ограничений на количество отображаемых объектов (только города и дороги), использование единственного отношения «находиться на расстоянии ... от ...» и только детерминированных переменных позволяет свести представление системы к реберно-взвешенному неориентированному графу, для которого может быть найден гамильтонов цикл наименьшей длины[2].
Задача о коммивояжере (TSP - Traveling Salesman Problem) заключается в нахождении кратчайшего гамильтонова цикла в графе. Она относится к NP-трудным. Без каких-либо изменений в постановке она используется для разработки архитектуры вычислительных сетей, проектирования разводки коммуникаций, маршрутизации авто- и авиатранспо эта и др. [13]. Выбор данной задачи для иллюстрации основных положений муравьиных алгоритмов обусловлен следующим: 1) это HP-сложная задача [14]; 2) :-адача наглядно интерпретируется в терминах поведения муравьев - перемещения муравьев интуитивно сопоставимы; 3) это традиционный тестовый полигон (benchmark problem) для методов комбинаторной оптимизации. Существует обширная библиотека тестовых задач коммивояжера и методов их решения, что позволяет сравнить эффективность муравьиных алгоритмов оптимизации с другими подходами[15] [16]; 4) это дидактическая задача, для которой можно без злоупотребления техническими деталями алгоритма объяснить процесс поиска оптимума; 5) это первая комбинаторная задача, решенная муравьиными алгоритмами. В неформальной форме задача о коммивояжере трактуется следующим образом: коммивояжеру необходимо посетить Огородов, не заезжая в один и тот же город дважды, и вернуться в исходный пункт по маршруту с минимальной стоимостью. Более строго имеем: дан граф G=(X,U), где \Х\ = п - множестве1 вершин (города), \U\ = т — множество ребер (возможные пути между городами). Дана матрица чисел D(i, j), где і, je 1, 2,..., п, представляющих собой стоимость переезда из вершины х, в Xj.
Требуется найти перестановку ср из элементов множества X, такую, что значение целевой функции равно:
F(cp) = D{(px,(pn) +?=i1D((Pi, pi+1) -» min. Таким образом, критерием является кратчайший путь. Если граф не полносвязный, то в матрице D, в ячейках соответствующих отсутствующим ребрам в гоафе, ставится бесконечность, в результате чего проход по данному ребру будет исключен [17].
Кратчайший обход выделен жирными стрелками: 1-2-3-4-5-6-7-8-1.Существуют различные типы задач о коммивояжере: геометрическая, симметричная, несимметричная и др. Однако вне зависимости от типа задачи пространство поиска остается порядка п! гдеи—число городов. Это объясняется тем, что решение представляет собой некоторую перестановку длиной п, соэтветственно количество перестановок равное/.
Алгоритмы решения задачи коммивояжера имеют большое число практических приложений в различных областях науки и техники[18]. Рассмотрим, например, задачу, в которой поставщик выезжает с ресторана для доставки пиццы некоторому числу заказчиков и возвращается назад в ресторан. Расходы на перевозки пиццы пропорциональны пройденному поставщиком расстоянию, и при заданной матрице расстояний между потребителями и рестораном маршрут с наименьшими транспортными затратами является решением соответствующей задачи коммивояжера. Подобные задачи могут возникать при сборе почтовых отправлений в почтовых ящиках, составления графика движений школьных автобусов по заданным остановкам и т.д. Задача обобщается и на тот случай, когда доставкой (сбором) занимаются несколько грузовиков, хотя эту задачу можно переформулировать также как задачу коммивояжера большей размерности [18] или задачей маршрутизации автотранспорта. Другие приложения включают проектирование электрических сетей [20], составление расписания выполнения операций на машинах [19], управление автоматическими линиями [21] и т.д.
Особый интерес эта задача представляет и тем, что сводится к другим графовым задачам. На ее основе можно решить следующие задачи[22]: поиск гамильтонова цикла, задача поиска эйлерова цикла, планирования, составление кратчайшего остова, о назначениях и др.
Разработка кодировки хромосомы
Среди методов и алгоритмов поддержки при принятии управленческих решений в технических и экономических системах распространены ГА[66]. ГА получили применение в самых разных областях науки: логистики [85], безопасности информации [86] [87], финансовый трейдинг, проектирование СБИС [88]р др. ГА являются одним из популярных направлений при решении различных верификаций задачи маршрутизации автотранспорта [89]. ГА представляет собой модель развития информации, которая позаимствована у природы, и предназначена для оптимизации технических систем[90]. На рисунке 4 приведена структурная схема работы ГА. Оператор «разнообразия» уничтожает схожие решения и заменяет их новыми случайными решениями. Эта процедура позволяет избежать преждевременной сходимости. Начало
Модифицированная структурная схема работы генетического алгоритма Отличием предложенной модифицированной схемы работы ГА от стандартного является использование оператора разнообразия и «жадного» оператора ь россинговера. Оператор разнообразия уничтожает «схожие» хромосомы, заменяя их на случайно сгенерированные. Тем самым ГА избегает попадания в локальный оптимум. Схожесть хромосом определяется через использование расстояния Хемминга, т.е. определением числа различных ген в одинаковых локусах. «Жадный» оператор кроссинговера использует «жадную» стратегию при скрещивании двух хромосом, тем самым ускоряя процесс передачи наиболее качественных генов. Условием останова является время работы, так как при решении задачи маршрутизации автотранспорта в реальных системах необходимо учитывать временной фактор. Поскольку это динамическая задача, то условия могут изменяться несколько раз в течение дня, в то время как ЛПР (диспетчер, логист) должен реагировать относительно быстро. Время пересчета решения и поиска нового маршрута является временем простоя для транспорта. Соответственно, время работы алгоритма для решения задачи маршрутизации автотранспорта является заранее заданным ограничением.
Информация о решении в ГА хранится в «хромосомах», которые представленії различными структурами данных. Единицей генетической информации является «ген». Разделяют различные виды хромосом по содержанию и по форме. Достоинством разработанного ГА[91] для решения задачи маршрутизации является использование негомологичной хромосомы с одним стрингом [92], представленной вектором Н: \ Н, п; 1 і п, где Н, - значение гена в локусе і, п - количество клиентов. Декодировка хромосомы происходит следующим образом. Стартовой позицией для 1-го автотранспорта является депо а,]. Оттуда он посещает клиента Н/, соответственно он может вести еще (mi-dHl), где dHi - вес груза под номером НІ. Далее обслуживает клиента Н2, Н3 и т.д., пока выполняется следующее условие: т, - Шнд 0. Структурная схема декодировки хромосомы приведена на рисунке 5 [93].На выходе после декодировки имеем количество автотранспорта - г, суммарная длина маршрута - s. К примеру, пусть имеются 2 автотранспорта грузоподъемностью по 1500 кг и вектор запросов а?[93]:
При оценке приспособленности более перспективными в популяции могут считаться индивиды, которые при декодировке хромосомы дают меньшее количество автотранспорта, а при их равенстве - меньшее суммарное расстояние. Если при принятии решения ЛПР делает мультипликативную оценку, то целевая функция рассчитывается по формуле (1.2). 2.1.3 Разработка генетических операторов
В разработанном ГА используется случайная селекция. Такой выбор обоснован ограниченностью размерности задачи. Как правило, количество заказчиков в день в условиях грузоперевозок по городу не превышает 30. Это позволяет не использовать направленную селекцию (элитная, «колесо рулетки»), чтобы избежать попадания в локальный оптимум.
Тип используемой мутации - обмен. На рисункеб приведен пример мутации хромосомы, где выделены два гена в локусах 2 и 4 для обмена значениями. С учетом специфики задачи и кодировки хромосомы в предложенном ГА используется «жадный» оператор кроссинговера (ОК) [66]. «Жадный» ОК был предложен в 1988 году Грифенстеттом в соавторстве с другими учеными для решения задачи коммивояжера. Это эвристический оператор кроссингове за, ориентированный на использование знаний об объекте. Данный оператор с модификациями успешно использовался для решения задачи ком\ и вояжера [15][94] и применена в данной работе для решения задачи маршрутизации автотранспорта.
Идея построения «жадного» алгоритма заключается в следующем. На каждом шаг; последовательно выбираются лучшие элементы из множества имеющихся, т.е. решения, улучшающие целевую функцию, причем таким образом, чтобы не нарушать действующих ограничений. Генерация потомков происходит за счет выбора лучших участков родительских хромосом и их последующего сопряжения. В то же время схема работы «жадного» ОК может измеьяться в зависимости от характера решаемых задач [3].
Разработка архитектуры гибридного алгоритма
Предложенные модификации и новые модели алгоритмов решают отдельные самостоятельные задачи. Однако для ЛПР при принятии решения о доставке товаров клиентам необходимо комплексное решение, учитывающее все или наиболее значимые аспекты задачи маршрутизации грузоперевозок. В связи с этим в третьей главе представлены методы гибридизации, позволяющие совместить преимущества биоинспирированных алгоритмов и решать комплексно транспортно-логистическую задачу принятия решения о грузоперевозке товаров.
Как известно, задача маршрутизации автотранспорта объединяет в себе задачи коммивояжера и упаковки рюкзака [115]. Одним из подходов к решению задачи маршрутизации автотранспорта является двухфазное последовательное решение этих задач: сначала упаковки рюкзака [116], а затем коммивояжера. Задача упаковки, как правило, сводится к задаче геометрической кластеризации [117]. Как было указано в 1-й главе логист (ЛПР) вынужден также решать задачу разбиения графа в связи несовместимостью некоторых товаров. Решение этого комплекса задач с помощью одного метода представляется нецелесообразным, так как экспериментальные исследования показывают, что различные методы решения могут быть как эффективными, так и неэффективными в зависимости от области применения. В связи с этим в 3-й главе предлагается использовать гибридный алгоритм на основе биоинспирированных алгоритмов.
Существуют различные виды гибридных алгоритмов, но все они могут быть описаны несколькими обобщенными схемами [118]. В работе исследованы следующие подходы к гибридизации алгоритмов: последовательные, параллельные, вложенные.
Общие структурные схемы гибридных алгоритмов на примере ГА и МА представлены на рисунке 30.
На входе каждой схемы имеется математическая модель задачи и граничные условия. На выходе - лучшее решение из множества полученных. В последовательной гибридизации алгоритмы применяются последовательно. Полученные с помощью ГА решения передаются МА для дальнейшей обработки. При этом основная задача состоит в том, чтобы сконвертировать полученные ГА решения в удобную для МА информацию. Результатом работы ГА является множество квазиоптимальных хромосом, кодирующих решение. МА не включает в себя понятие хромосомы или некой кодировки. Введем понятие конвертера - оператор, конвертирующий решения ГА в удобный вид для интерфейса МА.
Рассмотрим работу конвертера на примере задачи коммивояжера с 5 вершинами. Кодировка хромосом ГА - прямая. В таблице 2 представлен пример тре хромосом и значения их целевых функций. Пусть ЦФ равна суммарной длине всех ребер цикла. Также в таблице указано значение концентрации феромона, которое соответствует предложенному маршруту, согласно формуле 2.2, где Q = 100.
Результатом работы конвертера является получение матрицы феромонов кТу(у) .На рисунке 31 представлены распределения феромонов для всех трех хромосом. Толщина ребра прямо пропорциональна уровню феромонов. Итоговый граф 31 -г получен путем наложения трех предыдущих и суммирования значения уровня феромонов. Также на ребрах 1-3, 2-3, 3-5 задано начальное значение уровня феромонов равное 1 для инициализации ребер с ненулевым значением концентрации феромона.
Исследования муравьиного алгоритма для задачи маршрутизации автотранспорта
Максимальное время работы муравьиного (МА) и пчелиного алгоритмов (ПА) на данных тестах 750 секунд. Максимальное время работы алгоритма hMetis значительно ниже - 15 секунд. На графах большей размерности (более 10000 вершин) лучшие результаты ожидаемо выдает hMetis. Это связано с низкой временной сложностью алгоритма (ВСА), в то время как ПА и МА имеют большую ВСА. Из-за высокой ВСА предложенные алгоритмы едва ли успеют провести несколько итераций для больших графов. Для увеличения скорости работы алгоритмов необходимо снизить такие параметры как размер колонии, другие эвристические параметры, что влечет за собой снижение качества решения. Таким образом, предложенные алгоритмы следуют использовать для укрупненных графов при решении задачи компоновки блоков ЭВА большой численности. Для укрупнения графа можно использовать такие рекурсивные алгоритмы как Кернигана-Іина, hMetis[136].
Разработана компьютерная программа для поиска минимального гамильтонова цикла в условиях города Таганрога [137]. Для решения ЗК в реальных условиях города, когда путь может быть проложен только по дорогам улицы, был создан специальный формат векторной карты. Это было сделано для того, чтобы получить графовую модель города, где перекрестки и концы улиц - вершины графа, а дороги между перекрестками - ребра. На рисунке 51 приведен кратчайший обход 10 точек на карте г.Таганрога.
Экспериментальные исследования показали эффективность разработанных алгоритмов по сравнению с существующими. Основные исследования проводились для задачи коммивояжера. Это связано с тем, что эта задача является неофициальным полигоном для тестирования алгоритмов, а также она является одним важных составляющих транспортно-логистическ їх задач. Разработанные модификации муравьиного алгоритма позволили найти лучшие решения на тестовых задачах Оливера, Эйлона, а также на тестах berlin52, st70. Были предложены и реализованы различные биоинспирированные алгоритмы для задачи разбиения графа. На графах малой размерности до 100 вершин наиболее эффективным является муравьиный На графах большей размерности лучшие решения получаются с помощью п4елиного алгоритма. Проведенный анализ выявил наилучшие параметры муравьиного алгоритма. Проведенные экспериментальные исследования показали характер зависимости параметров муравьиного и пчелиного алгоритмов от размерности задачи. Выявлена зависимость значений оптимальных параметров алгоритмов и ЦФ. В частности, выявлена формула (4.1), показывающая оптимальный размер колонии муравьев в зависимости от числа вершин. Разработанная формула доказана эмпирически экспериментальными исследованиями. Разработан комплекс программ для решения задач коммивояжера, маршрутизации автотранспорта, разбиения графа. Разработаны программы для решения задачи коммивояжера в реальных условиях с использованием геоинформационных систем - Google Maps, Open Street Map.
В ходе проделанной работы был разработан комплекс алгоритмов, реализующие все предложенные модификации муравьиного, пчелиного, роевого алгоритмов на ЭВМ. Испытания проводились на ЭВМ со следующей характеристикой: Intel(R) Соге(ТМ) 2 Quad CPU Q8400 2.67 GHz, 6 ГБ ОЗУ. Полученные результаты позволяют судить об оптимальном выборе параметров алгоритмов. Преимущество модифицированного муравьиного алгоритма с модификациями перед ГА и стандартным муравьиным алгоритмом при решении различных графовых задач подтверждено экспериментальными исследованиями. Проведенный анализ выявил наилучшие параметры муравьиного алгоритма. Проведенные экспериментальные исследования показали характер зависимости параметров муравьиного и пчелиного алгоритмов от размерности задачи. На нескольких международных тестах получены наилучшие известные решения. Выявлена зависимость значений оптимальных параметров алгоритмов и ЦФ. В частности, выявлена формула (4.1), показывающая оптимальный размер колонии муравьев в зависимости от числа вершин. При настройке параметров алгоритма, данная формула может служить рекомендательным значением в СППР для ЛПР. Эффективность разработанной формулы доказана эмпирически экспериментальными исследованиями. Разработан комплекс программ для решения задач коммивояжера, маршрутизации автотранспорта, разбиения графа. Разработаны программы для решения задачи коммивояжера в реальных условиях с использованием геоинформационных систем - Google Maps, Open Street Map.
