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

  • Кажаров, Аскер Артурович
  • кандидат науккандидат наук
  • 2013, Таганрог
  • Специальность ВАК РФ05.13.01
  • Количество страниц 173
Кажаров, Аскер Артурович. Разработка и исследование роевых алгоритмов для решения транспортно-логистических задач: дис. кандидат наук: 05.13.01 - Системный анализ, управление и обработка информации (по отраслям). Таганрог. 2013. 173 с.

Оглавление диссертации кандидат наук Кажаров, Аскер Артурович

СОДЕРЖАНИЕ

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

1. АНАЛИЗ И СОСТОЯНИЕ ПРОБЛЕМ РЕШЕНИЯ ТРАНСПОРТНЫХ ЗАДАЧ

1.1 Анализ алгоритмов и методов решения задачи коммивояжера

1.2 Анализ и состояние задачи маршрутизации автотранспорта

1.2.1 Построение математической модели задачи маршрутизации автотран спорта

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

1.3 Анализ и состояние задачи разбиения товаров для упаковки в транспортные средства

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

1.4.1 Анализ последовательных алгоритмов

1.4.2 Ан;шиз итерационных алгоритмов

1.4.3 Обзор вероятностных алгоритмов

1.4.4 Ан;шиз временной сложности алгоритмов решения задач коммивсяжера и маршрутизации автотранспорта

1.5 Выводы

2 РАЗРАБОТКА БИОИНСПИРИРОВАННЫХ АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧ КОММИВОЯЖЕРА И МАРШРУТИЗАЦИИ АВТОТРАНСПОРТА

2.1 Разработка генетического алгоритма для решения задачи маршрутизации автотранспорта

2.1.1 Описание структурной схемы генетического алгоритма

2.1.2 Разработка кодировки хромосомы

2.1.3 Разработка генетических операторов

2.2 Разработка простого муравьиного алгоритма для решения задачи коммивояжера

2.3 Построение модификаций муравьиного алгоритма

2.3.1 Построение модификации «элитных» муравьев

2.3.2 Построение стратегий начального расположения колонии муравьев

2.3.3 Создание шаблонов

2.3.4 Построение модификации выпрямления

2.3.5 Построение модификации «пространственного феромона»

2.3.6 Разработка модифицированного муравьиного алгоритма для решения задачи маршрутизации автотранспорта

2.4 Оценка сложности муравьиного алгоритма

2.5 Разработка пчелиного алгоритма для решения задачи коммивояжера

2.6 Разработка метода роя частиц для решения транспортных задач

2.7 Выводы

3 ПОСТРОЕНИЕ ИНТЕГРИРОВАННОГО АЛГОРИТМА МАРШРУТИЗАЦИИ АВТОТРАНСПОРТА

3.1 Анализ построения интегрированных алгоритмов маршрутизации автотранспорта

3.2 Разработка архитектуры гибридного алгоритма

3.3 Анализ и оценка временной сложности гибридного алгоритма

3.4 Выводы

4 ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ

4.1 Исследования модифицированного муравьиного алгоритма для задачи коммивояхера

4.2 Исследования муравьиного алгоритма для задачи маршрутизации автотранспорта

4.3 Исследования пчелиного алгоритма для задачи разбиения товаров с учетом соБ.местимости

4.4 Приложения

4.5 Выводи

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЯ А

ПРИЛОЖЕНИЯ Б

Рекомендованный список диссертаций по специальности «Системный анализ, управление и обработка информации (по отраслям)», 05.13.01 шифр ВАК

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

ВВЕДЕНИЕ

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

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

Задача данной работы - исследовать и формализовать проблематику транспортной логистики, изучить существующие методы решения задач транспортной логистики, разработать новые математические и программние обеспечения ситем анализа, управления, принятия решений и обработки информации. Для решения задач транспортной логистики необходимо разработать и сформулировать критерии и модели описания и оценки эффективности решения задачи оптимизиации, принятия решений. В работе детально рас сматривается решение задачи маршрутизации автотранспорта (в английской интерпретации «Vehicle Routing Problem» - VRP)[1]. Данная

задача имеет несколько верификаций в зависимости от области применения модели[2]. Поскольку VRP объединяет в себе такие задачи как задача упаковки и коммивояжера, в работе рассматривалось также решение задачи коммивояжера (в англ. интерпретации «Traveling Salesman Problem» - TSP). Если количе :тво автотранспорта в классической задаче VRP свести к одному, а его грузоподъемность к бесконечной или достаточно большой, то решение VRP сводится к решениюболее популярной задачи TSP. Решение TSP имеет множество различных подходов. К ним можно отнести и генетический[3], и муравьиный алгоритмы [4]. Этот класс алгоритмов был разработан в рамках научного направления, которое называется«№Шга1 Computing» («природные вычисления) >). Исследования в направлении муравьиных алгоритмов начались в середине 90-х годов XX века, автором идеи является Марко Дориго из Университета Брюсселя (Université Libre de Bruxelles), Бельгия [5>]. Данный ал т>ритм принято считать более адаптированным к задаче коммивояжера, чем многие другие алгоритмы из класса «роевых»[6]-. Поэтому муравьиные алгоритмы являются одним из популярных методик при решении транспортно-логистических задач.

Логистика - это наука о планировании, управлении и регулировании движения различных материальных и нематериальных потоков в пространство и во времени от их первичного источника до конечного потребителя Транспортная логистика относительно молодая наука, получившая бурное развитие в период второй мировой войны, когда она была применена для решения таких важнейших военно-стратегических задач как снабжение армии, перевозки самых военных объектов[7].

К концу 20 века логистическая наука выступает как дисциплина,

включающая в себя закупочную или снабженческую логистику, логистику

производственных процессов, сбытовую или распределительную логистику,

транспортную логистику, информационную или компьютерную логистику и

ряд других. Каждая из перечисленных областей деятельности человека

достаточно изучена и описана в соответствующей литературе; новизна же

6

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

Быстрое развитие автодорожного транспорта заметно повысило его роль в товар эпотоке и грузоперевозках в целом. Качественно дорог со второй половины XX века перестало быть определяющим; в большей части развитых стэан проложены асфальтированные дороги. Предпочтение стало отдаваться оптимизации перевозок, а не реализации дорогостоящих проектов по постройке новых дорог, мостов. В качестве критерия эффективности оптимизации грузоперевозок выступают минимальный расход на перевозку грузов транспортом общего пользования и минимальные транспортные затраты за перевозку собственным подвижным составом. В связи с этим функцию управления потоками товаров и других грузов сначала выполняли соответствующие специалисты по тарифам и маршрутам, после чего * в их обязанности был включен выбор вариантов транспортного обслуживания и различных дополнительных услуг. Таким образом, возникла необходимость мониторинга перевозок и экспедирования грузов, проверки грузовых счетов, взвешивания, упаковки, погрузочно-разгрузочных работ и т.п.[7]. Перечислен![ые факторы стали хорошим подспорьем для разработки методов получения, снализа и обработки экспертной информации, на основе которой принимается решение.

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

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

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

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

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

Начало 80-х годов ознаменовало новый период в развитии логистики

— период неологистики, или логистики второго поколения. Этот период

8

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

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

Поэтому внимание стало фокусироваться на межфункциональных

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

нелогистические ее подразделения. Критерием такого подхода стала

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

издержек предприятия является многокритериальной, так как приходится

находить бапанс между затратами на запросы и удовлетворением запросов

клиентов. В настоящий момент разрабатываются различные системы

автоматизации информационных потоков. Задачу формирования

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

задачу принятия решения, в которой диспетчер является лицом

принимающим решение (ЛПР). В сфере автоматизации и разработок

алгоритмов для задачи маршрутизации автотранспорта преобладают

алгоритмы, основанные на моделировании природных систем. Этот класс

9

алгоритмов называется биоинспирированный[9]. Разработанный биоинспирированный алгоритм реализует систему поддержки принятия решения (С11ПР), которая выдает для J11 IP несколько решений с условными весами (значениями целевых функций). ЛПР может, как принять одно из предлагаемых решений, так и скорректировать его. Примерами СППР в геоинформационных системах являются веб приложения Google Maps, Yandex Maps, позволяющие пользователю выбирать маршрут из предложенных нескольких.

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

* многопроцессорные ЭВМ, мини- и макро-ЭВМ пятого поколения;

* ка лалы связи;

* оснащение системами навигации тип GPS и ГЛОНАСС транспортнь е средства;

* оснащение персональными компьютерами должностных лиц грузовых станций [10].

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

Актуальность работы обусловлена большой сложностью и

размерностью задач маршрутизации, а также возникновением ее новых

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

методик, алгоритмов для решения данного класса проблем. Рассматриваемые

в диссертационной работе задачикоммивояжера и маршрутизации

автотранспорта являются актуальными. Разработанный интегрированный

10

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

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

Достижение указанной цели предполагает решение следующих основных задач:

1) Построение архитектуры биоинспирированного алгоритма маршрутизации автотранспорта, основанного на методах роевого интеллекта.

2) Разработка биоинспирированного подхода и алгоритмов маршрутизации автотранспорта.

3) Разработка модифицированных алгоритмов роевого интеллекта.

В качестве основных методов решения поставленных задач в данной

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

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

предложены],гх модифицированных алгоритмов, проведении экспериментальных исследований. В работе:

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

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

2) впервые выявлена и доказана зависимость временной сложности муравьиного алгоритма от коэффициента эвристики а;

впервые найдена зависимость аппроксимировано оптим;шьного значения размера колонии от размерности графа для симметричной задачи коммивояжера;

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

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

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

Решение поставленных задач позволяет автору защищать следующие

новые научные результаты:

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

12

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

3) интегрированную архитектуру процесса планирования грузоперевозок, основанную на методах роевого интеллекта, что позволяет находить решения ближе к оптимальному по сравнению с другими методами (стр. 110);

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

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

Разработанный программный комплекс решения задач коммивояжера и маршрутизации автотранспорта реализован с использованием интегральной среды разраЗотки Code Gear Rad Studio 2009 на языке программирования С++ и среды разработки Microsoft Visual Studio 2010 под семейство операционных систем WINDOWS.

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

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

(квазиоптимальных) решений. Данные алгоритмы характеризуются полиномиальной временной сложностью.

Реализация результатов работы. Материалы диссертации использованы в госбюджетных научно-исследовательских работах (НИР) Инженерной технологической академии Южного федерального университета (ИТА ЮФУ), по гранту Министерства образования и науки РФ, а также научно-исследовательских работах, выполненных по грантам Российского фонда фундг ментальных исследований:

1. НИР № 12354 «Разработка теории и принципов построения интеллектуальных систем принятия решений при проектировании на основе квантовых вычислений и бионических методов поиска»;

2. РФФИ 13-01-00596 «Разработка теории и принципов роевого интеллекта на основе моделей адаптивного поведения биологических систем для решения оптимизационных задач»;

3. РФФИ 13-07-12091 «Разработка новых информационно-вычислительных технологий оптимизации структуры региональных транспортных перевозок на основе гибридных интеллектуальных моделей и методов роевого интеллекта».

Результаты этих работ внедрены и используются в учебном процессе на

кафедре САПР ИТА ЮФУ (г. Таганрог). Копии 4 свидетельств о регистрации

программ для ЭВМ прикреплены в приложении А.

Апробация работы. Основные научные и практические результаты

работы докладывались, обсуждались и были одобрены на Международных

научно-техн тческих конференциях «Интеллектуальные САПР» (пос.

Дивноморск, 2008 - 2013 гг.), Всероссийских научных конференциях

молодых ученых и аспирантов (г. Таганрог, г. Ростов-на-Дону, 2008 - 2012

гг.), национальных конференциях по искусственному интеллекту с

международ тым участием (КИИ-08, КИИ-2010), Всероссийской научно-

технической конференции "Проблемы разработки перспективных микро- и

нано-электронных систем" (МЭС-2012), 15-й Всероссийской межвузовской

14

научно-техн оческой конференции студентов и аспирантов «Микроэлектроника и информатика - 2008».Автор является победителем конкурса УМНИК, в рамках которого реализована НИР; также победителем конкурса «Лучший студент ЮФУ в области научно-исследовательских работ» по техническим наукам; победителем «Всероссийского конкурса инновационных проектов среди молодых ученых, аспирантов и студентов»; автору вручена медаль РАН «За лучшую научно-исследовательскую работу в ВУЗах России». Опубликовано более 35 печатных работ по теме диссертационной работы, материалы вошли в отчет по НИР. Опубликована монография «Биоинспирированные алгоритмы. Решение оптимизационных задач».

Структура и объем диссертационной работы. Диссертационная работа состоит из введения, четырех разделов, заключения и использованной литературы, изложенных на 165 страницах, 52 рисунков, 14 таблиц, списка литературы из наименований и приложения.

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

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

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

Во втором разделе приведены принципы решения задач маршрутизации автотранспорта, основные модели биоинспирированных алгоритмов. Разработаны методы поиска решений, основанных на идеях роевого интеллекта (Swarm Intelligence). Определены основные направления биоинспирированных алгоритмов: роевые и генетические алгоритмы. Разработаны биоинспирированные методы поиска решения: модифицированные муравьиный и пчелиный алгоритмы. Разработаны новые операторы муравьиного и пчелиного алгоритмов. Разработаны методы на основе ис тользования модифицированного алгоритма муравьиного алгоритма (Ant Colony Optimization), пчелиного алгоритма (Bee Colony Optimization) и метода роя частиц (Particle Swarm Optimization). Временные сложности разработанных алгоритмов являются полиномиальными.

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

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

Выявлена зависимость значений оптимальных параметров алгоритмов и ЦФ.

16

Предложена формула, показывающая оптимальный размер колонии муравьев в зависимости от числа вершин. Разработанная формула доказана эмпирически экспериментальными исследованиями. Разработан комплекс программ для решения задач коммивояжера, маршрутизации автотранспорта, разбиения графа. Разработаны программы для решения задачи коммивояжера в реальных условиях с использованием геоинформационных систем - Google Maps, Open Street Map.

В_заключении изложены основные выводы и результаты

диссертационной работы, рекомендации к настройкам алгоритмов.

В npnj ожении даны копии свидетельства об официальной регистрации программы для ЭВМ.

1. АНАЛИЗ И СОСТОЯНИЕ ПРОБЛЕМ РЕШЕНИЯТРАНСПОРТНЫХ ЗАДАЧ

Маршрутизация представляет собой процесс определения наилучшего пути при транспортировке груза [11]. Проблема для ЛПР при решении такой задачи заключается в неполноте, неточности информации и многофакторности описания транспортной среды. Качество перемещения груза зависит от большого количества различных факторов, начиная от свойств перевозимого продукта и заканчивая свойствами объектов транспортной среды, влияющих на груз [12]. Однако для решения сложных задач маршрутизации необходима апробация разработанных решений на более простых задач, таких как задача коммивояжера. Данная задача является классической задачей транспортной логистики и теории графов. Ее успешное решение даег понимание о том, насколько адаптирован разработанный метод для задач маршрутизации. Кроме того, данная задача является классическим тестовым полигоном для сравнения алгоритмов.

1.1 Анализ алгоритмов и методов решения задачи коммивояжера

Задача коммивояжера (ЗК) возникает в обширном классе приложений, но в своей классической формулировке не учитывает многих аспектов задач, возникающих на практике. Введение ограничений на количество отображаемых объектов (только города и дороги), использование единственного отношения «находиться на расстоянии ... от ...» и только детерминированных переменных позволяет свести представление системы к реберно-взвешенному неориентированному графу, для которого может быть найден гамильтонов цикл наименьшей длины[2].

Задача о коммивояжере (TSP - Traveling Salesman Problem)

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

относится к NP-трудным. Без каких-либо изменений в постановке она

18

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

1) это NP-сложная задача [14];

2) задача наглядно интерпретируется в терминах поведения муравьев - перемещения муравьев интуитивно сопоставимы;

3) это традиционный тестовый полигон (benchmark problem) для методов комбинаторной оптимизации. Существует обширная библиотека тестовых задач коммивояжера и методов их решения, что позволяет сравнить эффективность муравьиных алгоритмов оптимизации с другими подходами[15] [16];

4) это дидактическая задача, для которой можно без злоупотребления техническими деталями алгоритма объяснить процесс поиска оптимума;

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

Список литературы диссертационного исследования кандидат наук Кажаров, Аскер Артурович, 2013 год

СПИСОКИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ

1.Dantzig G.B., Ramser R.H. The Truck Dispatching Problem. 6th ed. Management Science, 1959. 80-91 pp.

2. Колесников A.B., Кириков И.А. Решение сложных задач коммивояжера методами функциональных гибридных интеллектуальных систем. Москва: ИЛИ РАН, 2007.

3.ГладкоЕ Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы. Ростов-на-Дону: Ростиздат, 2004.

4. Dorigo M., Bonabeau Е., and Theraulaz G. Swarm Intelligence: from Natural to Artificial Systems. New York: Oxford University Press, 1999.

5. Colorni A., Dorigo M., and Maniezzo V. Distributed optimization by ant colonies // Proceedings of the first European conference on artificial life. Paris. 1591. pp. 134-142.

6. Курейчик B.M., Кажаров A.A. Роевой интеллект в решении графовых задач // Сборник трудов XVI Международной конференции по мягким вычислениям и измерениям. Санкт-Петербург. 2013.

7. Аникина Б.А. Логистика: учебное пособие. Москва: ИНФРА-М, 1999.

8. Laplaze M., Meunier J., and Weil J., "Logistique d'entreprises et politique commerciale de la SNCF", Revue générale des chemins de fer, 1984. pp. 515532.

9. Курейчик B.M., "Биоинспирированный поиск с использованием сценарного подхода", Известия ЮФУ. Технические науки, Vol. 108, No. 7, Июль 2010. pp. 7-13.

10. Смехов A.A. Введение в логистику. Москва: Транспорт, 1993. 112 с.

11. Лукинский B.C., Бережной В.И., Бережная Е.В. Логистика автомобильного транспорта. Москва: Финансы и статистика, 2004.

12. Беляков С.Л., Белякова М.Л., Розенберг И.Н., Савельева М.Н.,

"Прецедентный анализ маршрутов на электронных картах", Известия ЮФУ. Технические науки, Т. 130, № 5, Май 2012. С. 47-51.

13.Кажаро)з A.A., Курейчик В.М., "Муравьиные алгоритмы для решения транспортных задач", Теория и системы управления, № 1, 2010.

14. Garey M.R., Johnson D.S. Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: W. H. Freeman and Co., 1979.

15. Kureichick V.M., Miagkikh V.V., and Topchy A.P. Genetic Algorithm for Solution of the Traveling Salesman Problem with New Features against Premature Convergence // In Proc. of 1С on Adaptive Computing In Engineering Design And Control' 96. Plymouth, UK. 1996.

16. Colorni A., Dorigo M., and Maniezzo V. An Investigation of some Properties of an "Ant Algorithm" // Proc of the "Parallel problem solving from nature" conference. Brussels. 1992. pp. 509-520.

17. КристосшдесН. Теорияграфов. London: Academic Press, 1977.

18. Christof des N., Eilon S., "An algorithm for the vehicle-dispatching problem", Operational Research Quarterly, No. 3, September 1969. pp. 309-318.

19. Charlton J.M., Death C.C., "A method of solution for general machine-scheduling problems", Operations research, Vol. 18, No. 4, July/August 1970. P. 189.

20. Burstall R.M., "Tree Searching Methods with an Application to a Network Design Problem", Machine Intelligence, Vol. 1, 1967. pp. 65-85.

21. Haring D.R. Sequential-circuit synthesis. Cambridge: MIT Press, 1966.

22. Курейчик B.M., Кажаров A.A., "О некоторых модификациях муравьиного алгоритма", Известия ЮФУ. Технические науки, № 4, Апрель 2008. С. 7-12.

23. Toth P., Vigo D. The Vehicle Routing Problem. Philadelphia: SIAM, 2001. 29-52 pp.

24. Филин E.A., Dupas R. Маршрутизация автотранспорта (VRP - Vehicle

routing эгоЫет) // Сборник трудов "9 Нижегородской сессии молодых ученых". Нижний Новгород. 2004. С. 56-63.

25.Кажаров А.А. Решение задачи маршрутизации автотранспорта с ограниченной вместимостью муравьиным алгоритмом // Сборник трудов VI Всероссийской конференции студентов, аспирантов и молодых ученых "Технологии Microsoft в теории и практике программирования". Таганрог. 2009.

26. Емельянова Т.С., "Об одном генетическом алгоритме решения транспортной задачи с ограничением по времени", Известия ЮФУ, Т. 81, № 4, Апрель 2008. С. 45-50.

27. Crevier В., Cordeau J.F., and Laporte G., "The multi-depot vehicle routing problem with inter-depot routes", European Journal of Operational Research, No. 176. 2007. pp. 756-773.

28. Zheng Y., Mesghouni K. Vehicle routing problem with unpaired pickups and deliveries // Proc. of the 9th International Conference on Enterprise Systems, Accounting and Logistics (9th ICESAL 2012). Crete. 2012. pp. 359-368.

29. Christof des N., Beasley J.E., "The period routing problem", Networks, No. 14, 1984. pp. 237-256.

30. Kenyon A.S., Morton D.P., "Stochastic Vehicle Routing with Random Travel Times", Transportation Science, No. 1, February 2003. pp. 69-82.

31.0ng J.O., Suprayogi, "Vehicle Routing Problem with Backhaul, Multiple Trips and Time Window", Jurnal Teknik Industri, Vol. 13, No. 1, June 2011. pp. 1-10.

32. Bard J.F., Huang L., Dror M., and Jaillet P., "A branch and cut algorithm for the VRP with satellite facilities", HE Transactions, No. 30, 1998. pp. 821234.

33. Chen S., Golden В., and Wasil E., "The split delivery vehicle routing problem: Applications, algorithms, test problems and computational results",

Networks, Vol. 4, No. 49, 2007. pp. 318-329.

34. Курицкий Б .Я. Оптимизация вокруг нас. Ленинград: Машиностроение, 1989.

35. Кажаров A.A., Курейчик В.М. Классификация и критерии оптимизации задачи маршрутизации автотранспорта // Сборник трудов VII Международной научно-практической конференции "интегрированные модели и мягкие вычисления в искусственном интеллекте". Коломна. 2013.

36. Кажаров A.A., Курейчик В.М. Обзор задач коммивояжера и маршрутизации автотранспорта // Сборник трудов Международной научно-технической конференции по интеллектуальным системам AIS'13. УГосква. 2013.

37. Заде Л. Понятие лингвистической переменной и его применение к принятию приближенных решений. Москва: Мир, 1976.

38. Курейчик В.М., Кажаров A.A. Использование пчелиных алгоритмов для решения комбинаторных задач // Сборник трудов международной научно-технической конференции "Искусственный интеллект-2010. Интеллектуальные системы". Донецк-Таганрог-Минск. 2010. С. 583-389.

39. Кажаров A.A., Курейчик В.М. Биоинспирированные алгоритмы. Решениеоптимизационныхзадач. Saarbrucken: LAP LAMBERT Academic Publishing GmbH & Co. KG, 2011.

40. Смирнов A.A., "Оптимизация доставки готовой продукции и математический аппарат для ее достижения", Известия СПбГУЭФ, № 4, 2009. С. 159-162.

41. Fisher M.L., "Optimal Solution of Vehicle Routing Problems Using Minimum K-trees", Operations Research, No. 42, 1994. pp. 626-642.

42. Mitchell J.E., "Branch-and-Cut Algorithms for Combinatorial Optimization Problems", Handbook of Applied Optimization, January 2002. pp. 65-77.

43. Teitz M.B., Polly B., "Heuristic Methods for Estimating the Generalized Vertex Median of a Weighted Graph", Operations Research, Vol. 5, No. 16, September/October 1968. pp. 955-961.

44. Clarke (3., Wright J., "Scheduling of vehicles from a central depot to a number of delivery points", Operations Research, Vol. 4, No. 12, 1964. pp. 568-581.

45. Shvaiko P., Euzenat J., "A Survey of Schema-Based Matching Approaches", Lecture Notes in Computer Science, Vol. 3730, 2005. pp. 146-171.

46. Prosser ? and Shaw P, "Study of Greedy Search with Multiple Improvement Heuristics for Vehicle Routing Problems," University of Strathclyde, Department of Computer Science, Glasgow, Research Report 96/201, 1996.

47. Fisher M.L., Jaikumar R., "A generalized assignment heuristic for vehicle routing", Networks, Vol. 11, No. 2, Summer 1981. pp. 109-124.

48. Ryan D.M., Hjorring C., and Glover F., "Extensions of the Petal Method for Vehicle Routing", Journal of the Operational Research Society, No. 44, 1993. pp. 289-296.

49. Gillet B.E., Miller L.R., "A Heuristic Algorithm for the Vehicle Dispatch Problem", Operations Research, No. 22, 1974. pp. 340-349.

50. Osman I.H., "Metastrategy Simulated Annealing and Tabu Search Algorithms for the Vehicle Routing Problem", Annals of Operations Research, No. 41, 1993. pp. 421-451.

51. Bullnheimer B., Hard R.F., and Strauss C. Applying the Ant System to the Vehicle Routing Problem // 2nd International Conference on Metaheuristics. Sophia-/Vntipolis. 1997.

52. Shaw P. Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems // Proceedings of the Fourth International Conference on Principles and Practice of Constraint Programming (CP '98). Pisa. 1998. pp. 417-431.

53. Arbelaitz O., Rodriguez C., and Zamakola I. Low Cost Parallel Solutions for the VRPTW Optimization Problem // 2001 International Conference on Parallel Processing Workshops. IEEE Computer Society. Valencia. 2001. pp. 176-181.

54. Alba E., Dorronsoro B. Solving the Vehicle Routing Problem by Using Cellular Genetic Algorithms // Conference on Evolutionary Computation in Combinatorial Optimization, EvoCOP'04. Naples. 2004. Vol. 3004. pp. 1120.

55.Dueck G., Scheurer T., "Threshold Accepting: A General Purpose Optimization Algorithm", Journal of Computational Physics, No. 90, 1990. pp. 161-175.

56. Amberg A., Domschke W., and Voss S., "Multiple Center Capacitated Arc Routing Problems: A Tabu Search Algorithm using Capacitated Trees", European Journal of Operational Research, No. 124, 2000. pp. 360-376.

57. Toth P and Vigo D, "The Granular Tabu Search (and its Application to the Vehicle Routing Problem)," University of Bologna, Bologna, Working Paper 1998.

58. Rochat Y., Taillard E.D., "Probabilistic Diversification and Intensification in Local Search for Vehicle Routing", Journal of Heuristics, No. 1, 1995. pp. 147-167.

59. Kelly J., Xu J.P., "A Network Flow-Based Tabu Search Heuristic for the Vehicle Routing Problem", Transportation Science, No. 30, 1996. pp. 379393.

60. Gutin G., Yeo A., and Zverovich A., "Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP", Basic Researcn in Computer Science, January 2001.

61. Kirkpatrick S., Gellat C.D., and Vecchi M.P., "Optimization by simulated annealing", Science, No. 220, 1983. pp. 671-680.

62. Johnson D.S., Aragón C.R., McGeoch L.A., and Shevon C., "Optimization by simulated annealing: An experimental evaluation part I, graph partitioning", Operation Research, No. 37, 1989. pp. 856-892.

63.Kernigan B.W., Lin S., "An efficient heuristic procedure for partioning graphs", Bell Syst. Tech. Journal, Vol. 2, No. 49, 1970. pp. 291-307.

64. Hollan .Í.H. Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. University of Michigan Press, 1975.

65. Курейчик B.B. Эволюционные методы решения оптимизационных задач. Таганрог: ТРТУ, 1999.

66. ГладкоЕ JT.A., Курейчик В.В., Курейчик В.М. Генетические алгоритмы. Москва ФИЗМАТЛИТ, 2006.

67. Кажаров А.А., Рокотянский А.А., "Исследование генетических алгоритмов на основе тестирующих функций Де Ионга", Перспективные информационные технологии и системы, 2007.

68. Кажаров Х.А., Кажаров А.А. Параллельный криптоанализ RSA при помощи генетических алгоритмов // Сборник трудов XIV Международной научно-практической конференции студентов, аспирантов и молодых ученых "Современные техника и технологии" СТТ-2008. Томск. 2008. Т. II. С. 306-307.

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

70. Bonavear F., Dorigo М. Swarm Intelligence: from Natural to Artificial Systems. Oxford: Oxford university Press, 1999.

71. Dorigo M, "Optimization, Learning and natural Algorithms," Diparimento di Electrónica, Ploitechnico di Milano, Milano, PhD Thesis 1992.

72. Dorigo M., Maniezzo V., and Colorni A., "The Ant System: Optimization by a Colony of Cooperating Agents", IEEE Trans. On Systems, Man and

Cybernetics, Vol. 26, No. 1, 1996. pp. 29-41.

73. Dorigo M., Di Caro G., and Gambardella L.M., "Ant algorithms for discrete optimization", Artificial life, Vol. 5, No. 2, 1999. pp. 137-172.

74. Курейчик B.B., Полупанов E.E., "Эволюционная оптимизация на основе алгоритма колонии пчел", Известия ЮФУ. Технические науки, Т. 101, № 12, Декабрь 2009. С. 41-46.

75.ЛебедеЕ Б.К., Лебедев В.Б., "Размещение на основе метода пчелиной колонии", Известия ЮФУ. Технические науки, Т. 113, № 12, Декабрь 2010. С. 12-19.

76. Кажаров А.А., Курейчик В.М. Реализация конвейерной вычислительной структуры с помощью метода пчелиных колоний // Труды Международной научно-технической конференции «Суперкомпьютерные технологи: разработка, программирование, применение» (СКТ-2010). Таганрог. 2010.

77. Субботин С.А., Олейник А.А., "Мультиагентная оптимизация на основе метода пчелиной колонии", Кибернетика и системный анализ, № 3, 2009. С. 15.

78. Карпенко А.П., Селиверстов Е.Ю., "Глобальная оптимизация методом роя частиц. Обзор", Информационные технологии, № 2, 2010. С. 25-34.

79. Kenned}' J., Eberhart R. Particle Swarm Optimization // Proceedings of IEEE International Conference on Neural Networks IV. Perth. 1995. Vol. 4. pp. 1942-1948.

80. Shi Y., Eberhart R. A modified particle swarm optimizer // Evolutionary Computation Proceedings, 1998. IEEE World Congress on Computational Intelligence. Anchorage. 1998. pp. 69-73.

81.Poli R., "Analysis of the publications on the applications of particle swarm optimisation", Journal of Artificial Evolution and Applications, No. 4, January 2008.

82. Mendes R., Kennedy J., and Neves J. Watch thy neighbor or how the swarm can learn from its environment // Proceedings of Swarm Intelligence Symposium. 2003. pp. 88-94.

83. Kenned}' J., Mendes R. Popultion structure and particle swarm performance // Proceedings of the 2002 Evolutionary Computation Congress. Washington. 2002. pp. 1671-1676.

84. Kureichik V., Kazharov A. Methods inspired by natural systems // Proceeds of The 5-th International Conference on Application of Information and Communication Technologies. Baku. 2011.

85. Кажаров A.A., Лебедев Б.К. Решение некоторых верификаций задачи маршрутизации автотранспорта методами. генетического поиска // Сборник трудов Всероссийской научной конференции студентов, аспирантов и молодых ученых "Технологии Microsoft в теории и практике программирования-2009". Таганрог. 2009.

86. Кажаров А.А., Кажаров Х.А., "Разработка модели криптоанализа RSA при помощи генетических алгоритмов", Информационное противодействие угрозам терроризма, № 10, 2008. С. 155-161.

87. Кажаров А.А., Кажаров Х.А. Применение генетических алгоритмов для повышения эффективности решения переборных задач // Сборник трудов V Всероссийской межвузовской конференции молодых ученых. Санкт-Петербург. 2008.

88. Кажаров А.А. Эволюционные механизмы дотрассировки соединений СБИС на основе жадной стратегии и динамических принципов // Материалы конференции "XV Туполевские чтения". Казань. 2007.

89. Емельянова Т.С., Курейчик В.М. Алгоритмы решения транспортных задач с использованием генетических методов: Монография. Таганрог: ТТИ ЮФУ, 2011.

90. Holland J.H. Adaptation in natural an artificial systems. London: The MIT

Press edition, 1992.

91. Кажаров A.A., Рокотянский A.A. Маршрутизация автотранспорта по городу на основе генетического алгоритма // Труды международной научно-технической конференции "Интеллектуальные системы" AIS'09. Москва. 2009.

92. Goldberg D.E. Genetic Algorithms in Search, Optimization and Machine Learning. 1st ed. Boston: Addison-Wesley Longman Publishing Co., 1989.

93. Кажаров A.A., Кажаров X.A. Генетические методы решения задачи маршрутизации автотранспорта // Сборник трудов VI Всероссийской конференции студентов, аспирантов и молодых ученых. Томск. 2008. С. 239-240.

94. ГладкоЕ JI.A., Кажаров A.A. Гибридный нечетко-генетический алгоритм для решения задачи коммивояжера // Труды IV-й Международной научно-практической конференции "Интегрированные модели и мягкие вычисления в искусственном интеллекте". Коломна. 2009.

95. Джонс 7. Программирование искусственного интеллекта в приложениях. Москва: ДМК-Пресс, 2004.

96. Holldob er В., Wilson Е.О. The Ants. Harvard: Harvard University Press, 1990.

97. Holldob er В., Wilson Е.О. Der Superorganismus. Der Erfolg von Ameisen, Bienen, Wespen und Termitten. Heidelberg: Springer-Verlag, 2010.

98. Kazharov A.A., Kureichik V.M., "Ant colony optimization algorithms for solving transportation problems", Journal of Computer and Systems Sciences International, Vol. 49, No. 1, 2010. pp. 30-43.

99. Dorigo M, Gambardella L.M., "Ant colonies for the travelling salesman problemBioSystems, Vol. 43, No. 2, July 1997. pp. 73-81.

100. White Т., Kaegi S., and Oda Т. Revisiting Elitism in Ant Colony Optimization // Proceedings of Genetic and Evolutionary Computation

Conference. Chicago. 2003. Vol. I. pp. 122-133.

101. Кажаров A.A. Модификации муравьиных алгоритмов и их применение к задаче коммивояжера // Сборник трудов 15-й Всероссийской межвузовской научно-технической конференции студентов и аспирантов «Микроэлектроника и информатика-2008». Зеленоград. 2008.

102. Кажаров A.A., Курейчик В.М. Об одном «муравьином» алгоритме // Сборник трудов 11-й национальной конференции по искусственному интеллекту с международным участием (КИИ-2008). Дубна. 2008. Т. 2.

103. Кажаров A.A., Курейчик В.М., "Использование шаблонных решений в муравьиных алгоритмах", Известия ЮФУ. Технические науки, № 7, Июль 2013. С. 17-22.

104. Gambardella L.M., Dorigo М. Ant-Q: A Reinforcement Learning Approach to the Traveling Salesman Problem // Proceedings of Twelfth International Conference on Machine Learning. Tahoe, California, USA. 1995. pp. 252260.

105. Кажаров A.A. Модифицированный муравьиный алгоритм с применением шаблонов // Труды международной научно-технической конференции "Интеллектуальные системы" AIS'09. 2009.

106. Кажаров A.A., Курейчик В.М. Модификации муравьиного алгоритма для решения задачи коммивояжера // Труды международной научно-технической конференции "Интеллектуальные системы AIS'08". 2008.

107. Кажаров A.A. Использование метода ветвей и границ в муравьиных алгоритмах // Сборник трудов IX Всероссийской научной конференции студентов и аспирантов "Техническая кибернетика, радиоэлектроника и системы управления". Таганрог. 2008.

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

161

ч

ч

109. Кажаров А.А., Курейчик В.М. Применение муравьиных алгоритмов для решения некоторых транспортных задач // Сборник труды 3-его Симпозиума по нейроинформатике и нейрокомпьютерам. Ростов-на-Дону. 2009.

110. Dorigo М., Gambardella L.M., "Ant colony system: A cooperative learning approach to the traveling salesman problem", Evolutionary Computation, IEEE Transactions on, Vol. I, No. 1, April 1997. pp. 53-66.

111. Малько зский С.И., Пересветов B.B. Метод роя частиц в решении нелинейных транспортных задач. Хабаровск: Вычислительный центр Дальнее,осточного отделения РАН, 2011.

112. Курейчик В.М., Кажаров А.А., "Использование роевого интеллекта в решении NP-трудных задач", Известия ЮФУ. Технические науки, Т. 120, №7, Июль 2011.С. 30-36.

113. Кажаров А.А. Применение пчелиного алгоритма для решения задачи коммивояжера // Труды VI-й Международной научно-практической конференции "Интегрированные модели и мягкие вычисления в искусственном интеллекте". Коломна. 2011.

114. Кажаров Х.А., Кажаров А.А. Параллельный криптоанализ при помощи генетических алгоритмов на основе метаэволюции // Труды Всероссийской конференции "Технологии Microsoft в теории и практике применения". Таганрог. 2008.

115.Masum М, Shahjalal М., Faruque F., and Sarker H.I., "Solving the Vehicle Routing Problem using Genetic Algorithm", International Journal oj Advanced Computer Science and Applications, Vol. 2, No. 7, 2011. pp. 126131.

116. Кормен T.X., Лейзерсон Ч.И., Ривест P.Л., Штайн К. Алгоритмы: построение и анализ. 2-е изд. Москва: Вильяме, 2006.

117. Айвазяг С.А., Бухштабер В.М., Енюков И.С., Мешалкин Л.Д.

Прикладная статистика: Классификация и снижение размерности. Москва: Финансы и статистика, 1989.

118. El-Mihoub Т.A., Hopgood A.A., Nolle L., and Battersby A., "Hybrid Genetic Algorithms: A Review", Engineering Letters, Vol. 13, No. 2, August 2006. pp. 124-137.

119. Кажаров X.A., Кажаров А.А. Применение методов генетического поиска в криптоанализе RSA // Сборник трудов VI Всероссийской конференции студентов, аспирантов и молодых ученых "Молодежь и современные информационные технологии". Томск. 2008. С. 241-242.

120. Oliver I М., Smith D.J., and Holland J.R. A study of permutation crossover operators on the traveling salesman problem // Proceedings of the Second International Conference on Genetic Algorithms on Genetic algorithms and their app lication. New Jersey. 1987. pp. 224-230.

121. Whitley D.L., Starkweather Т., and Fuquay D. Scheduling Problems and Traveling Salesmen: The Genetic Edge Recombination Operator // Proceedings of the 3rd International Conference on Genetic Algorithms. San Francisco. 1989. pp. 133-140.

122. Rehab F.A.K., "Fuzzy Particle Swarm Optimization with Simulated Annealing and Neighborhood Information Communication for Solving TSP", International Journal of Advanced Computer Science and Applications, Vol. 2, No. 5: 2011. pp. 15-21.

123. Громыко Г.JI. Статистика. Москва: Московского университета, 1981.

124. Ефимова М.Р., Петрова Е.В., Румянцев В.Н. Общая теория статистики. Москва: Инфа, 1998.

125. Елисеева И.И., Юзбашев М.М. Общая теория статистики. 5-е изд. Москва: Финансы и статистика, 2004.

126. Курейчик В.М., Кажаров А.А. Алгоритмы эволюционного роевого интеллекта в решении задачи разбиения графа // Сборник трудов

Всероссийской научно-технической конференции "Проблемы разработки перспективных микро- и наноэлектронных систем (МЭС)". 2012. Т. 1.С. 237-242.

127.Кажаров A.A. Решение задачи разбиения графа на основе биоинспирированных алгоритмов // Сборник трудов международной научно-технической конференции «Интеллектуальные системы» (AIS'10). Москва. 2010.

128. Курейчик В.М., Кажаров A.A., "Применение пчелиного алгоритма для раскраски графов", Известия ЮФУ. Технические науки, Т. 113, № 12, Декабрь 2010. С. 30-36.

129. Кажаров A.A., "Модификация муравьиного алгоритма и его применение к задаче коммивояжера", Перспективные информационные технологии и интеллектуальные системы, 2007.

130. Кажаров A.A. Построение минимального дерева Штейнера на основе муравьиных алгоритмов // Труды молодежной конференции "Интел1 ектуальные системы-2009". Москва. 2009.

131. Кажаров A.A., Курейчик В.М. Разработка кодировки хромосомы для построения минимального дерева Штейнера на основе генетических алгоритмов // Труды конференции МИФИ-2010. Москва. 2010.

132. Кажаров A.A. Построение минимального дерева штейнера на основе муравьрнх алгоритмов // Сборник трудов Молодежной научно-технической конференция "Интеллектуальные системы". Москва. 2009. Т. I.

133. Кажаров A.A., Рокотянский A.A., "Разработка среды маршрутизации грузоперевозок", Известия ЮФУ. Технические науки, Т. 93, № 4, Апрель 2009. С. 174-181.

134. Кажаров A.A., Курейчик В.М. Решение задачи о назначениях на основе муравькных алгоритмов // Сборник трудов 12-й национальной

конференции по искусственному интеллекту с международным участием (КИИ-2010). Тверь. 2010.

135.Karypis G and Kumar V, "Multilevel k-way hypergraph partitioning.," Department of Computer Science, University of Minnesota, Minnesota, Technical Report TR 98-036 1998.

136. Karypis G., Aggarwal R., Kumar V., and Shekhar S., "Multilevel Hypergraph Partitioning: Applications in VLSI Domain", IEEE Trans. VLSI SySt., Vol. 7, No. 1, March 1999. pp. 69-79.

137. Кажаров А.А., Дедовской А.Д., Рокотянский A.A. Разработка редактора карт для решения задач маршрутизации // Труды молодежной конфере нции "Интеллектуальные системы-2009". Москва. 2009.

138. Nguyen М., Trahan S., Nguyen P., and Handley W. Geospatial Analysis Using SAS and the Google Map API // SAS Global Forum 2009. Applications Development. 2009.

139. Кажаров A.A. Гибридный алгоритм на основе генетического и муравы- ного алгоритмов // Сборник трудов XIV международной научно-практической конференции студентов, аспирантов и молодых ученых "Современные техника и технологии". Томск. 2008. Т. II. С. 304-305.

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