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

На правах рукописи

1иг

Кажаров Аскер Артурович

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

Специальность:

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Таганрог -2013

005545630

005545630

Работа выполнена в Южном федеральном университете в г. Таганроге.

Научный руководитель: заслуженный деятель науки РФ,

доктор технических наук, профессор Курейчик В.М.

Официальные оппоненты: д.т.н., проф., профессор кафедры

«Автоматика и телемеханика на ж.-д. транспорте» Ростовского государственного университета путей сообщения, г Ростпи-ня-Дону КОВАЛЕВ Сергей Михайлович

д.т.н., проф., профессор кафедры информатики Таганрогского государственного педагогического института имени А.П. Чехова ВИТИСКА Николай Иванович

Ведущая организация: Открытое акционерное общество

«Научно-исследовательский и проектно-конструкторский институт информатизации, автоматизации и связи на железнодорожном транспорте» (ОАО «НИИАС»), Ростовский филиал, г. Ростов-на-Дону

Защита состоится« 5 » декабря_2013 г. в 16:00 на заседании

диссертационного совета Д 212.208.22 при Южном федеральном университете по адресу: 347928, Таганрог, пер. Некрасовский, 44, ауд. Д-406.

С диссертацией можно ознакомиться в Зональной научной библиотеке Южного федерального университета по адресу: 344000, Ростов-на-Дону, ул. Пушкинская, 148.

Автореферат разослан « 29ЖоХ.и г.

Ученый секретарь диссертационного совета доктор технических наук,

Целых А.Н.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

Основные положения, выносимые на защиту.

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

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

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

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

Научная новизна работы.

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

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

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

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

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

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

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

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

Реализация результатов работы. Результаты работы внедрены в научно-исследовательских работах, грантах РФФИИ, выполняемых на кафедре САПР ИТА ЮФУ.

Апробация работы. Основные научные и практические результаты работы докладывались, обсуждались и были одобрены на Международных научно-технических конференциях «Интеллектуальные САПР» (г. Геленджик, 2008 - 2013 гг.), Всероссийских научных конференциях молодых ученых и аспирантов (г. Таганрог, г. Ростов-на-Дону, 2008 - 2012 гг.), национальных конференциях по искусственному интеллекту с международным участием (КИИ-08, КИИ-2010), Всероссийской научно-технической конференции (МЭС-2012), 15-й Всероссийской научно-технической конференции МИЭТ-2008. Опубликовано более 40 печатных работ, материалы вошли в отчет по НИР. Опубликована монография «Биоинспирированные алгоритмы. Решение оптимизационных задач».

Публикации. Результаты диссертации отражены в 35 печатных работах, в числе которых 8 - в изданиях, рекомендованных ВАК, и в 4 свидетельствах об официальной регистрации программ для ЭВМ.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы. Работа содержит 165 страниц, включая 52 рисунка, 14 таблиц, список литературы из 139 наименований, 4 страницы приложений со свидетельствами об официальной регистрации программ для ЭВМ, 4 страницы приложений актов внедрения результатов диссертационной работы в научно-исследовательские работы.

СОДЕРЖАНИЕ РАБОТЫ

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

В ПЕРВОЙ ГЛАВЕ приведены постановки задач транспортной логистики: задач коммивояжера и маршрутизации автотранспорта. Задача маршрутизации автотранспорта сводится к решению задач коммивояжера и упаковки. Приведены

5

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

Выбор задачи коммивояжера (ЗК) для иллюстрации идеи муравьиного алгоритма обусловлен следующими причинами:

1. имеется возможность наглядно интерпретировать задачу в терминах муравьиного алгоритма:

2. ЗК является NP-полной;

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

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

5. ЗК является первой комбинаторной задачей, решенной муравьиными апгоритмами.

В неформальной постановке ЗК представлена следующим образом: коммивояжеру необходимо посетить W городов, не заезжая в один и тот же город дважды, и вернуться в исходный пункт по маршруту с минимальной стоимостью. Более строго имеем: дан граф G=(X,U), где \Х\ - г. - множество вершин (города), \U\ = т — множество ребер (возможные пути между городами). Дана матрица чисел D(i, j), где i,j е /, 2,..., п, представляющих собой стоимость переезда из вершины х( в Xj.

Требуется найти перестановку q> из элементов множества X, такую, что значение целевой функции равно:

F{<p) = + + 1))} -> min.

i

Таким образом, критерием является кратчайший путь. Эффективное решение данной задачи позволяет разработать алгоритмы и для более сложных задач транспортной логистики, в т. ч. для задачи маршрутизации автотранспорта. Задача маршрутизации автотранспорта (Vehicle Routing Problem - VRP) остается одной из актуальных проблем в транспортной логистике. Данная задача имеет несколько верификаций в зависимости от области применения модели. Фактически, решение классической задачи маршрутизации сводится к построению непересекающихся гамильтоновых циклов для связного взвешенного графа, в вершинах которого находятся клиенты, а ребра показывают стоимость (время, расстояние) маршрута. Данная задача относится к NP-полным. На рисунке 1 представлен пример решения классической задачи маршрутизации автотранспорта.

маршрут 1

маршрут 2

депо

, ,0 маршрут 3

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

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

1. каждое транспортное средство имеет фиксированную грузоподъемность (Capacitated VRP - CVRP);

2. каждый клиент должен быть обслужен в определенный срок, т.н. «временное окно» (VRP with Time Windows — VRPTW);

3. предприятие использует транспортное средство из нескольких транспортных депо для обслуживания заказчиков (Multiple Depot VRP -MDVRP);

4. клиент может отказаться от части заказанных товаров (VRP with PickUps and Deliveries - VRPPD);

5. доставка может осуществляться в течение длительного периода (Periodic VRP - PVRP);

6. любой клиент или транспортное средство может иметь случайное поведение (Stochastic VRP - SVRP);

7. некоторое транспортное средство должно забрать товар у клиента после того, как обслужил всех остальных (VRP with Backhauls -VRPB);

8. существует возможность дополнительной загрузки транспортного средства по ходу следования маршруту (VRP with Satellite Facilities -VRPSF);

9. клиент может быть обслужен различными транспортными средствами (Split Delivery VRP - SDVRP).

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

сокращение этого числа. Обозначим количество задействованного автотранспорта переменной т'.

¥ =

т.'

¿=1

1,].П,)+1 + СгЦгДМ I'

т' < т

¡=1

I

^ с1г. < и/(Д < г < т',

N

I

у=1

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

"-©••О*

О < а, Ь Р<<2

где т' - размер задействованного автопарка, т - размер всего автопарка, ¥ -суммарная длина маршрутов, <2 — суммарная длина маршрутов начального решения, а - коэффициент, характеризующий «важность» или «цену» критерия числа задействованных транспортов, Ь - коэффициент, характеризующий «важность» или «цену» критерия суммарной длины маршрутов.

Цель оптимизации — минимизация функции /Л Веса а и Ь являются входными параметрами для разработанного алгоритма и должны регулироваться диспетчером. Это позволит изменять оценку эффективности решения задач для одного и того же алгоритма без серьезных изменений в модели описания.

ВО ВТОРОЙ ГЛАВЕ описаны разработанные биоинспирированные алгоритмы: генетический (ГА), муравьиный, пчелиный. Среди методов и алгоритмов поддержки при принятии управленческих решений в технических и экономических системах распространены ГА. ГА получили применение в самых разных областях науки: логистики, безопасности информации, финансовый трейдинг и др. ГА являются одним из популярных направлений

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

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

1 < Н, < п; 1 < / < и,

где НI - значение гена в локусе г, п - количество клиентов. Декодировка хромосомы происходит следующим образом. Стартовой позицией для 1-го

он может вести еще {т, - с1,п), где а\т - вес груза под номером НДалее обслуживает клиента Н2, Н3 и т.д., пока выполняется следующее условие:

т, - 1Мв) > 0.

Структурная схема декодировки хромосомы приведена на рисунке 2. На выходе после декодировки имеем количество автотранспорта - /, суммарная длина маршрута-5. К примеру, пусть имеются 2 автотранспорта грузоподъемностью по

/ 1 2 3 4 5 6

кг) 150 530 350 480 600 450

Пусть задана хромосома Н:

1 2 3 4 5 6

н, 5 3 2 4 6 1

Тогда, согласно декодировке хромосомы маршруты формируются следующим образом: _ ____

Транспорт \клиент 5 3 2 4 6 1

1 транспорт 600 950 (600+350) 1480 (950+530)

2 транспорт 480 930 (480+450) 1080 (930+150)

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

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

Рисунок 2. Структурная схема декодировки хромосомы

Использование ГА обусловлено его гибкостью при решении многих комбинаторных задач. Для адаптации ГА к различным задачам необходимо лишь разработать кодировку. Дальнейшие модификации (операторов кроссинговера, мутации, отбора) относятся к улучшению временной сложности алгоритма (ВСА) и качества решения. Также интерес представляют алгоритмы роевого интеллекта. Проведен глубокий анализ муравьиного алгоритма для решения различных модификаций задачи коммивояжера. В рамках роевых алгоритмов исследован метод роя частиц (МРЧ). Экспериментальные результаты показали, что МРЧ является наименее привлекательным из вышеперечисленных алгоритмов ввиду своей высокой стохастичности.

Результатами исследований, представленных во второй главе, являются:

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

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

3. Разработка стратегии построения «шаблонов» в муравьином алгоритме, позволяющий снижать ВСА. Предложены 2 стратегии: статическая —

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

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

5. Разработка новой модели модифицированного муравьиного алгоритма для решения задачи маршрутизации автотранспорта со следующими верификациями: CVRP, VRPTW, MDVRP, SDVRP.

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

В ТРЕТЬЕЙ ГЛАВЕ описана гибридная архитектура поиска, позволяющая эффективно использовать разработанные генетические и роевые алгоритмы.

Отличительной особенностью данного гибридного алгоритма является использование в муравьином алгоритме оператора кроссинговера. На основе этого оператора генерируются дополнительные решения, но при этом размерность колонии не меняется. Муравьи исследует дополнительные маршруты, полученные оператором кроссинговера, и откладывают на них дополнительные феромоны. Это позволит лучше избегать локального оптимума без увеличения ВСА. Структурная схема данного алгоритма представлена на рисунке 3.

Рисунок 3. Использование оператора кроссинговера в муравьином алгоритме

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

8«ж®

*1Ш

ПА

МА

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

На рисунке 4 изображены пчелиный алгоритм (ПА), муравьиный (МА) и генетический (ГА). В данной главе исследованы различные подходы к гибридизации биоинспирированных алгоритмов: генетического, муравьиного и пчелиного. Разработана последовательно-вложенная модель гибридного алгоритма. Проведены анализ и оценка временной сложности гибридного алгоритма. Использование операторов ГА позволит избежать преждевременной сходимости муравьиного апгоритма.

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

В ЧЕТВЕРТОЙ ГЛАВЕ определены теоретические оценки временной и пространственной сложности разработанных алгоритмов, подтвержденные экспериментальными результатами. Экспериментальные исследования проводились на тестовых примерах Оливера, Эйлона и др. Известные лучшие решения найдены в следующих тестах: оНЗО, ei!50, eiI75, eil98, berlin52, st70. Испытания проводились на ЭВМ со следующей характеристикой: Intel(R) Core(TM)2 Quad CPU Q8400 2.67 GHz, 6 ГБ ОЗУ.

Экспериментальные исследования показали эффективность разработанных алгоритмов по сравнению с существующими. Основные исследования проводились для задачи коммивояжера. Это связано с тем, что эта задача является неофициальным полигоном для тестирования алгоритмов, а также она является одним важных составляющих транспортно-логистических задач. Разработанные модификации муравьиного алгоритма позволили найти лучшие решения на тестовых задачах Оливера, Эйлона, а также на тестах berlin52, st70. Были предложены и реализованы различные биоинспирированные алгоритмы для задачи разбиения графа. На графах малой размерности до 100 вершин наиболее эффективным является муравьиный. На графах большей размерности лучшие решения получаются с помощью пчелиного алгоритма. Проведенный анализ выявил наилучшие параметры муравьиного алгоритма. Проведенные экспериментальные исследования показали характер зависимости

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

Экспериментальные исследования разработанного алгоритма показали, что ее впеменная сложность близка к ПСп2). гле и — число иепшин R графе

В ЗАКЛЮЧЕНИИ изложены основные выводы и результаты диссертационной работы.

В приложении А даны копии свидетельств об официальной регистрации программ для ЭВМ. В приложении В даны копии актов внедрения результатов диссертационной работы в научно-исследовательские работы, финансируемые РФФИ.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

3. Разработка стратегии построения «шаблонов» в муравьином алгоритме, позволяющий снижать ВСА. Предложены 2 стратегии: статическая -шаблон создается до запуска основного цикла «жизни» колонии, динамическая -шаблон создается и меняется по ходу работы муравьиного алгоритма.

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

5. Разработка новой модели модифицированного муравьиного алгоритма для решения задачи маршрутизации автотранспорта со следующими верификациями: CVRP, VRPTW, MDVRP, SDVRP.

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

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

8. Определение зависимости оптимального количества муравьев от количества вершин в графе.

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

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

1. «Ant Colony Optimization» - поиск минимального гамильтонова

цикла в графе;

7. Репяктоп карт — программа ппя перехода от реальных моделей к

графовым;

3. «Маршрутизатор» - маршрутизация в карте по дорогам;

4. «Google Maps Router» - маршрутизация автотранспорта по всему миру на основе Google Maps Api;

5. «ACO solution of VRP» - решение задачи маршрутизации автотранспорта в графовой модели.

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

1. 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. (по списку ВАК РФ)

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

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

(по fniipirv RA К" PrtV)

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

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

6. Курейчик В.М., Кажаров A.A. Алгоритмы эволюционного роевого интеллекта в решении задачи разбиения графа // Сборник трудов Всероссийской научно-технической конференции "Проблемы разработки перспективных микро- и наноэлектронных систем (МЭС)". 2012. Т. 1. С. 237242. (по списку ВАК РФ)

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

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

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

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

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

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

13. Кажаров A.A., Курейчик В.М. Реализация конвейерной вычислительной структуры с помощью метода пчелиных колоний // Труды Международной

научно-технической конференции «Суперкомпьютерные технологи: разработка, программирование, применение» (СКТ-2010). Таганрог. 2010.

14. 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Личный вклад автора в работах, опубликованных в соавторстве:

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

маршрутизации автотранспорта с дополнительными ограничениями [1, 2, 8, 26];

разработка модификаций муравьиного алгоритма [3, 4, 11, 14, 20, 23, 30];

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

роя частиц [5, 6, 7, 10, 13, 27, 33]; разработка программного обеспечения и

проведение экспериментальных исследований [12, 18]; разработка кодировки хромосомы в генетическом алгоритме для решения задачи маршрутизации автотранспорта [15, 16, 17]; обзор стандартных форматов карт [31]; обзор и исследование задач маршрутизации автотранспорта [34].

Соискатель ш Кажаров А.А.

Формат 60x84 1/16. Бумага офсетная. Печать ризограф. Печ. Л. 1. Тираж 100 экз., Заказ №301

Типография ЮФУ в г. Таганроге 347928, г. Таганрог, пер. Некрасовский

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

04201454577

На ппавах рукописи

КАЖАРОВ АСКЕР АРТУРОВИЧ

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

Специальность: 05Л3.01 - Системный анализ, управление и обработка информации (вычислительная техника и информатика),

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель: д-р техн. наук, профессор Курейчик В.М.

Таганрог 2013 г.

СОДЕРЖАНИЕ

СОДЕРЖАНИЕ........................................................................................................2

ВВЕДЕНИЕ..............................................................................................................5

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

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

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

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

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

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

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

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

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

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

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

1.5 Выводы..........................................................................................................50

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

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

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

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

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

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

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

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

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

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

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

ПРИЛОЖЕНИЯ А...............................................................................................166

ПРИЛОЖЕНИЯ Б................................................................................................170

ВВЕДЕНИЕ

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

Развитие рыночных отношений и рост цен на продукты нефтяной промышленности дали импульс транспортной логистике, в частности, решению 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

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