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

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

Емельянова Татьяна Сергеевна

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

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

АВТОРЕФЕРАТ

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

Таганрог - 2009

003472943

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

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

Курейчик Виктор Михайлович

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

Ковалев Сергей Михайлович (РГУПС, г.Ростов-на-Дону)

кандидат технических наук, доцент Родзин Сергей Иванович (Технологический институт Южного федерального университета в г.Таганроге)

Ведущая организация: Российский научно-исследовательский

институт управления на железнодорожно транспорте МПС России Ростовский филиал

Защита состоится «25» июня 2009 г. в 14:20 на заседани диссертационного совета Д 212.208.22 при Южном федерально университете по адресу: 347928, г. Таганрог, пер. Некрасовский, 44, ауд. Д 406.

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

Автореферат разослан «23» мая 2009 г.

Ученый секретарь

диссертационного совета Д 212.208.22, доктор технических наук, профессор

Ж

Целых А.Н.

АКТУАЛЬНОСТЬ РАБОТЫ

Логистика важная область жизнедеятельности человека. Перевозка людей и грузов (от пищевых до промышленных) - это неотъемлемая часть жизни современного человека. Необходимость решения транспортных задач, с минимизацией издержек на перевозку, >пределяется экономическим эффектом при нахождении лучшего решения, т.к. это увеличивает прибыль предприятия. Применение компьютерных методов решения задач позволяет увеличить скорость принятия решений и повысить эффективность найденных решений. Поэтому требуются алгоритмы способные исполняться на массово доступных вычислительных средствах (персональных компьютерах и малых серверах). Разработка новых методов должна учитывать структуру вычислительных средств, на которых будут исполняться программы, реализующие данные алгоритмы. В настоящее время основные тенденции развития компьютерной техники таковы: за последние несколько лет резко снизился рост частоты процессоров, появилась возможность хранить в памяти огромные объемы информации. Снижение роста быстродействия процессоров произошло из-за достижения ехнологического предела нанометровых технологий, однако появилась возможность разместить на одном кристалле большее количество вычислительных элементов (процессорных ядер). Польза от использования этих ядер будет только в том случае, если исполняемая программа (и её алгоритм) является параллельным, в противном случае будет ^пользоваться (работать) только одно ядро, а остальные будут простаивать. Известно, что классические алгоритмы не имеют возможности распараллеливания и имеют кспоненциальный рост времени выполнения от размерности задачи. Т.е. количество гатематических действий (команд) растет экспоненциально, а развитие процессорных лементов (увеличение тактовой частоты, уменьшение количества тактов выполнения команд, адержка на выборку данных из памяти) не компенсируют растущие (с увеличением размерности задачи) потребности классических алгоритмов. Точные методы решения транспортных задач (ТЗ), позволяют найти решение только для задач с малым количеством клиентов (т.е. до 50-ти клиентов). Для решения задач большой размерности точные методы вляются не эффективными в связи с их большими временными затратами. Однако, именно ейчас, требуется эффективные алгоритмы решения задач большой размерности, т.к. в [астоящее время наблюдается процессы глобализации в экономике. Это приводит к [еобходимости планирования транспортных операций с большим количеством клиентов, т.е. к ГЗ большой размерности. Таким образом, решение ТЗ большой размерности является ктуальной задачей. Одним из классов ТЗ является ТЗ с ограничением по времени. Данный класс задач является сложным для решения, но необходимым и широко применяемым на практике. Моделью ТЗ с ограничением по времени описываются: банковские и почтовые юставки, перевозка людей, сбор промышленных и бытовых отходов, доставка продуктов, [оставка топлива и материалов на предприятия. На настоящий момент в литературе предложено множество алгоритмов решения данного класса задач. Практическим алгоритмам по решению ТЗ с ограничением посвящено множество работ следующих ученых: Solomon, Tompson, Psaraftis, Russell, Antes, Derigs, Cordone, Wolfer-Calv, Caseau, Laburthe, Braysy, Rochat, Taillard, Chiang, Cordeau, Thangiah, Homberger, Gehring, Mester, Barkaoui, Csiszär, Van Hentenryck и др.

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

\

ЦЕЛЬ ДИССЕРТАЦИИ

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

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

1. Проведение сравнительного анализа эффективности существующих методов решени ТЗ.

2. Разработка специального комбинированного генетического алгоритма (ГА) дл решения статической ТЗ с ограничением по времени.

3. Построение генетических операторов отражающих специфику решаемой ТЗ (линейно или с ограничением по времени).

4. Разработка модифицированного ГА для решения динамической ТЗ.

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

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

1. Разработаны новые модификации ГА для решения статической и динамически транспортной задачи с ограничением по времени.

2. Предложены новые принципы построения генетических операторов для применения ГА решения транспортных задач. На основе этих принципов разработаны новые схемь операторов инициализации и мутации.

3. Предложен метод распараллеливания ГА для применения его в многоядерных системах что позволило получить увеличение быстродействия.

РЕЗУЛЬТАТЫ ВЫНОСИМЫЕ НА ЗАЩИТУ

1. Генетические операторы для решения линейной транспортной задачи большо размерности (порядка 100 х 100 ).

2. Новый ГА и генетические операторы для решения транспортных задач с ограничение] по времени.

3. Модифицированный ГА для решения динамической транспортной задачи позволяющий реагировать на изменение (появление/удаление) запросов от клиенте при исполнении полученного решения, т. е. изменять решение в процессе ег выполнения с целью уменьшения транспортных затрат.

4. Метод распараллеливания ГА ориентированный на выполнение разработанны алгоритмов на многоядерной вычислительной базе.

ПРАКТИЧЕСКАЯ ЗНАЧИМОСТЬ

На основе разработанных методов и алгоритмов создан программно алгоритмический комплекс для решения транспортных задач с ограничением по времени. При построении программного комплекса использовался объектно-ориентированный язык С++ и среда разработки Microsoft Visual С++ 6.0. Отладка и тестирование проводилось на ЭВМ типа IBM PC, с процессором AMD Athlon 64 Х2 5400+, 2.8 ГГц, ОЗУ 3ГБ. Отличительная особенность разработанного программного комплекса - это эффективное использование многоядерной вычислительной системы, что позволило сократить время решения транспортных задач в два раза по сравнению с одноядерной системой.

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

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

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

МЕТОДЫ ИССЛЕДОВАНИЯ

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

АПРОБАЦИЯ РАБОТЫ

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

(AIS'08) и «Интеллектуальные САПР» (CAD02008), Геленджик, 2008. Я. IX Всероссийской научной конференции «Техническая кибернетика, радиоэлектроника

и системы управления», Таганрог, 2008. к Второй Всероссийской научной конференции с международным участием «Нечеткие

системы и мягкие вычисления» (НСМВ-2008), Ульяновск, 2008. 5. XI Национальной конференции по искусственному интеллекту с международным участием (КИИ-08), Дубна 2008.

ПУБЛИКАЦИИ

Основные положения и результаты диссертационной работы опубликованы в 14 источниках, включающих 6 статей, 6 материалов конференций и семинаров, 2 свидетельства о >егистрации программ. Две работы из них опубликованы в рецензируемом журнале из списка JAK.

ОБЪЕМ И СТРУКТУРА ДИССЕРТАЦИИ

Диссертация состоит из введения, 4 глав, заключения, списка литературы, включающего 102 наименования и 6 приложений. Основной текст диссертации изложен на 150 траницах, включая 41 рисунок и 6 таблиц.

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

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

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

ТЗ с ограничением по времен, относится к классу № трудных задач, точны методы решения для зада такого вида эффективны пр малом количестве клиенте (т.е. до 50-ти клиентов Основные методы решени данной задачи с больши количеством клиентов - эт эвристические

метаэвристические методь Наилучшие результаты пр решении тестовых задач даю гибридные алгоритмь

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

использует различные метод улучшения маршрут

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

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

Во второй главе представлен разработанный новый ГА для решения линейных Т размерности порядка 100x100. Для данного ГА были разработаны новые ГО кроссинговера инициализации, отражающие специфику матричного представления линейной ТЗ. Применени операторов (в частности оператора кроссинговера), адаптированных к виду ТЗ, позволяв получать готовые допустимые решения-потомки из решений-родителей без дополнительны преобразований, только лишь с непосредственным применением оператора кроссинговера. Эт позволяет сократить вычислительные издержки алгоритма. Применение данных операторе позволяет на каждой итерации алгоритма не ухудшать (а до определенного количеств итераций улучшать) общую целевую функцию (ЦФ) популяции решений, что является главно целью работы ГА. Т.е. среднее значение ЦФ уменьшается на каждой генерации ГА, пока н сходится к определенному значению, которое будет являться наилучшим для данной задачи На рисунке 2 показана динамика изменения ЦФ популяции решений для задачи размерность! 100x100 при размере популяции 800 особей.

Рис. 1. Классификации ТЗ

Исследования показали, что данный оператор кроссинговера эффективен только при больших (более 100) размерах популяции решений; при малых размерах популяции, применение одного оператора мутации, является более эффективным (по качеству получаемого решения и временным затратам). Представленный ГА направлен на решения именно задач большой размерности (матрица стоимостей порядка 100x100), где размер популяции решений достигает 1000; в этом случае применение данного оператора позволяет получить лучшее решение. Т.е. можно сделать вывод, что применения оператора кроссинговера, отражающего специфику представления конкретной ТЗ, является оправданным с точки зрения вычислительной простоты и качества получаемого решения.

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

Результаты решения тестовых задач размера от 5><5 до 18x18 показали, что решение, полученное разработанным алгоритмом, при подборе параметров ГА, совпадает с птимальным решением. При решении тестовых задач порядка 100х 100 решение улучшалось в реднем на 35% от начального решения, при этом время решения задачи увеличивалось [ропорционально размерности задачи и хт.

В третьей главе представлены математическая модель ТЗ с ограничением по ремени и новый ГА решения данной задачи, позволяющий работать как со статическими, так [ с динамическими запросами клиентов.

Математически ТЗ с ограничением по времени можно представить в виде графа

G = (N, А),

где: N— множество вершин, соответствующих набору клиентов (customers) (вершины 1, 2, ..., п) и исходным депо (depot), в которых начинают и заканчивают свой маршрут все автомобили (вершины 0 и п+1);

А - набор дуг, соединяющих вершины графа. Введем обозначения: С - множество клиентов, |С| = «; i,j - i-й и у'-й клиенты, / е С, j € С ;

(г, у) е А - дуга, соединяющая ;-ю и j-ю вершины графа; d, - спрос /'-го клиента;

tij - время перемещения по дуге (/,/), состоящее из времени обслуживания клиента / и времени перемещения автомобиля от клиента / к клиенту/;

Комо

ХОД«

Рис.2. График зависимости ЦФ лучшего решения в популяции от номера итерации.

с,у - стоимость перемещения автомобиля от клиента / к клиенту у; V - количество идентичных автомобилей грузоподъемностью q; к - к-й автомобиль, к е V ;

[ab bj - «временное окно» (time window) - промежуток времени, в течение которог должен быть обслужен /'-й клиент;

S,k - время прибытия ¿-го автомобиля к г-му клиенту; время отправления из деп

для всех автомобилей равно 0 (т.е. = О V к е V);

X * - переменная, принимающая значения {0,1} и характеризующая направлени движения автомобиля: Ху = 1 - от клиента / к клиентуу, Хц = 0 - в обратном направлении.

С учетом этих обозначений математическая формулировка ТЗ с ограничением п времени такова: необходимо минимизировать целевую функцию (1) при ограничениях (2)-(9):

I ЯЛ (о

ksV (I, j)eA

£2X=1,V/6C (2)

ksV jsN

Zd.Zxjiq.Vker (3)

ieC JsN

(4)

jeN

Z Xl-Y,X4 =0 ,VheC,\/keV (5)

jeN jsN

2X,+.=w*6r (6)

j<=N

Z Xl(S> + - SJ) ^ 0 №.j)eA.VkeV (7)

jzN

a, <6, , V/e N, VkeV (8)

X* e {0,1}, V(ij) eA,Vke V. (9)

ЦФ (1) определяет цену всех маршрутов всех транспортных средств (общая цен транспортного плана). Ограничение (2) полагает, что каждый клиент обслуживается тольк одним транспортным средством и только один раз. Ограничение (3) определяет, чт транспортное средство не может обслужить больше клиентов, чем позволяет ег грузоподъемность. Ограничение (4) означает, что каждый автомобиль покидает депо один раз Ограничение (5) показывает, что автомобиль может покинуть вершину /г, только если о прибыл в эту вершину. Аналогично ограничению (4), ограничение (6) означает, что вс транспортные средства возвращаются в депо, причем один раз. Это ограничение следует и ограничений (4) и (5). Ограничение (7) означает что, если автомобиль движется из вершины ; у, то время прибытия автомобиля в у не может быть меньше суммы времени прибыти автомобиля в пункт / (5,*) и времени движения автомобиля из пункта / в пункт у (%) Ограничение (8) - это ограничение по времени, прибытие автомобиля к клиенту должно быть в пределах временного окна.

Основной особенностью разработанного алгоритма является использование дополнительного оператора мутации при «застаивании» процесса поиска, т.е. дополнительный

оператор не используется в регулярном цикле работы алгоритма, а применяется лишь в том случае, когда лучшее значение ЦФ в популяции решений не изменялось в течение определенного (заранее заданного) количества итераций (County). Алгоритм заканчивает свою работу, если выполнено заданное максимальное количество итераций (Nit) или если значение счетчика «застаивания» процесса поиска достигло определенного значения, рассчитываемого исходя из максимального количества итераций. Разработаны и подробно описаны основные ГО алгоритма.

Предложен новый оператор кроссинговера (ОК), который позволяет получать из N решений-родителей одно новое решение. Разработанный ОК построен таким образом, что в качестве строительных блоков используются маршруты транспортных средств. Поскольку для оценки подобия решений-потомков с решениями-родителями (а также подобия решений в популяции) в теории ГА используют понятие шаблон (схема) решения, то для данной ТЗ шаблоном решения будут являться закрепленные в решении маршруты транспортных средств. Согласно теории ГА лучшие маршруты (шаблоны) с точки зрения критерия оптимальности при применении ОК должны выживать с большой вероятностью. Поэтому для ОК определена вероятность выживания схемы Pk/S) при применении данного оператора с вероятностью кроссинговера Рк.

PJS) = 1 -Рк P/S) = \-Рк-(\- P/S)) = 1 -Рк+Рк ■ Р.(S) = = 1 -Рк+Рк -(Pl(S) + P;(S) + Pj(S)).

P'JS) и P;(S) - вероятности, нелинейно зависящие от количества закрепленных лиентов в маршрутах и от временных ограничений, накладываемых на решение задачи. 1ценить вероятности P'(S) и P^(S) возможно только путем экспериментов.

Теоретически оценена нижняя граница выживаемости шаблонов решения в

зависимости от параметров ОК и количества закрепленных маршрутов в шаблоне Pjs(S) .

\

a-J

где a, fi и N - параметры ОК; у - количество закрепленных маршрутов в шаблоне, ксперименты и теоретические расчеты показали, что для выживания, с вероятностью 80%, оротких шаблонов с одним закрепленным маршрутом, нужно применять ОК с вероятностью 0%.

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

Найдена вероятность выживания шаблонов при применении ОМ, ОМ_1 и ОМ_2. Данные вероятности соответственно равны:

PL(S) = 1 -PL -P*(S) = i-pl-a-p^s)) = \ -Pl + Pl ■P!(S) =

= 1-^ +Pl-f\a-~), приm+o(S)<k, k-1

где, Рхт - вероятность применения ОМ_1; тик- параметры ОМ_1; o(S) количество закрепленных маршрутов в шаблоне.

P2JS) = \-Pl-P/S) = \-P2m(\-P2JS)) = 1 -Р2+ PI -P?(S) =

= при К+ o(S)<N,

N0 N~l

где Рт - вероятность применения ОМ_2; К - параметр ОМ_2; N - количеств клиентов в задаче; o(S) - количество закрепленных клиентов в маршрутах в шаблоне. И приведенных выше формул, очевидно, что с увеличением порядка шаблона существенн снижается вероятность его выживания; это подтверждает факт большей вероятност выживания коротких шаблонов решений.

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

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

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

Рис. 3. Алгоритм работы многопоточной Рис. 4.Работа потока

программы

Как видно из рисунка 3, дополнительные потоки не изменяют структуру ГА, а только ополняют ее. Программа автоматически запрашивает у системы количество процессорных дер и запускает, если это возможно, дополнительные потоки. Пример работы потока представлен на рисунке 4. Количество запускаемых при решении задачи потоков равно оличеству ядер процессора. В холе экспериментов при выполнении на 2-ядерном процессоре запуске второго дополнительного потока при создании начальной популяции и при ыполнении главного цикла ГА время выполнения программы практически уменьшалось в два аза. Это подтверждалось теоретическими расчетами, поскольку доля не распараллеленного ода достаточно мала. Согласно формуле Амдала, которая иллюстрирует ограничение роста роизводительности системы с увеличением количества вычислителей (в данном случае роцессорных ядер) полученное увеличение быстродействия вычисляется по формуле

5 =---, где а - доля последовательных вычислений, р - количество

а-(1-а)/р

роцессорных ядер. При а«1, 8р~р. В настоящее время практически все новые

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

В четвертой главе рассмотрена разработка программных модулей и тестовых систем я оценки практической ценности разработанных алгоритмов. Эксперименты проводились я тестовых задач Соломона с различным расположением клиентов: равномерным (Я), сластерным (С) и смешанным (ЯС) и различными по жесткости временными ограничениями асс 1 и 2, общее количество задач 56. В каждой задаче одно депо и 100 клиентов. Для •аждого клиента заданы 7-мь величин: номер клиента, координата X, координата У, запрос оличества товара в условных единицах, нижняя граница временного окна, верхняя граница ременного окна, время, в течение которого, происходит обслуживание клиента. Границы ременного окна показывают промежуток времени, в который может быть обслужен оответствующий клиент. Если транспортное средство пришло к клиенту до начала нижней аницы временного окна, то оно должно ожидать пока не подойдет время обслуживание, что удет вносить задержку (увеличивать время простоя) транспортного средства. При еремещении от одного клиента к другому время перемещения в данных тестовых задачах ерется равным расстоянию между клиентами, т.е. скорость транспортных средств считается остоянной. Первичная цель при решении данных задач - минимизировать общее количество ранспортных средств. Вторичная минимизировать общее пройденное расстояние. Третья цель инимизировать время простоя транспортных средств.

Результаты экспериментов показывают, что разница полученных результатов с учшими решениями в классе С2 составляет 0%; в классе С1 от 0% до 7,3%; в классе от 0% о 2,3%; в классе 112 от 3,7% до 9,4%; в классе ЯС1 от 0,69% до 4,2%; в классе ЯС2 от 5,7% до ,5% в решениях, где количество транспортных средств совпадает с лучшими решениями. В стальных решениях, где транспортных средств на одно больше, общее пройденное асстояние меньше, чем в исторически лучших решениях.

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

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

Автор алгоритма и год Количество машин Общее расстояние

Рассель (Russell), 1995. .65827:;;

Кордон (Cordone), 1998. 422 58481

Касеу (Caseau), 1999. ■■ - 420

Ви Кит (Wee Kit) и др. 2001. 57265

Хомбергер (Homberger) и др. 2001. 406 57641

Цжанг (Jung) и др. 2002. 486 54779

Бент (Bent) и др. 2004. 405 57273

Хомбергер (Homberger) и др. 2005. 405 57308

Босилье (Le Bouthillier) и др. 2005. 407 57412

Цисзар (Csiszär) 2007. 405 58239

Разработанный ГА, 2009 420 55970

Результаты закрашенные серым разработанный алгоритм превосходит как п количеству транспортных средств, так и по общему пройденному расстоянию (т.е. разработанном алгоритме данные величины меньше). Видно, что решение, полученное помощью тестируемого алгоритма, имеет наименьшее пройденное расстояние и опубликованных алгоритмов и хотя количество транспортных средств больше, чем некоторых алгоритмов, однако нет алгоритма, который бы получил меньшее общее расстояни при равном или меньшем количестве транспортных средств. Даже алгоритмы с больши количеством транспортных средств имеют большее суммарное пройденное расстояние, кром алгоритма Джанга (Jung) 2002. Но, если взять за основу алгоритм Бента в котором достигаете оптимальное решение по количеству транспортных средств и общему пройденном расстоянию и сравнить с алгоритмами, в которых пройденное расстояние меньше, количество транспортных средств больше, то видно, что в алгоритме Ви Кита при увеличени транспортных средств на 27 (6%) получаем уменьшение расстояния всего на 0.014%, а алгоритме Джанга при увеличении транспортных средств на 81 (20%) получаем уменьшени расстояния на 4%, в разработанном ГА при увеличении количества машин всего на 15 (3.7% получаем уменьшение расстояния на 2.3%. Следовательно, можно сделать вывод, чт разработанный ГА дает наилучшие решения с точки зрения баланса между количество транспортных средств и общим пройденным расстоянием. Эта особенность данного алгоритм' позволяет использовать его для поддержки принятия решений в интеллектуальных системах На практике выгодно использовать немного больше транспортных средств, если при этом будет сокращаться время их использования (уменьшаться пройденное ими расстояние). Эт позволит уменьшить расходы на горюче-смазочные материалы и на амортизацию автотранспорта.

Описана тестовая система, которая эмулирует динамические запросы в течени выполнения (решения задачи) полученного промежуточного решения. Структура тестово системы представлена на рисунке 5.

Рис.5. Тестовая система для проверки алгоритмов решения динамических ТЗ.

Данная система состоит из следующих подсистем (модулей):

• модуль получения текущего решения (МПТР)- получает запросы клиентов от модулей формирования статических и динамических запросов, текущее положение транспортных средств и формирует решение задачи.

• модуль статических запросов - формирует и передает в МПТР запросы, которые известны заранее, до начала решения задачи в момент времени / = О, этот модуль работает только на начальном этапе;

• модуль формирования динамических запросов - предает в МПТР запросы от клиентов, которые поступают уже в процессе выполнения решения полученного на предыдущем этапе;

• модуль выполнения текущего решения (МВТР) - выполняет текущее решение, полученное от МПТР, формирует и передает в МПТР текущее положение транспортных средств.

Работа системы происходит следующим образом. Некоторое количество запросов от иентов, известно заранее - это статические запросы, на основе данных запросов МПТР ормирует решение, которое передается на исполнение МВТР. Выполнение решения роисходит до тех пор, пока не будут получены новые запросы клиентов или не будут ■ менены старые, как только это происходит, информация об изменении количества запросов ередается в МПТР. МПТР запрашивает из МВТР текущее положение транспортных средств, ри этом считается, что если транспортное средство движется к клиенту номер / то, оно олжно обязательно обслужить данного клиента и начальным условием положения для иного транспортного средства будет являться клиент /. Таким образом, МПТР получает екущие положения для всех транспортных средств, которые будут являться начальными словиями для формирования нового текущего решения. Формируется новое решение и ередается на выполнение МВТР. Это продолжается до тех пор, пока все клиенты не будут служены или не истечет временной период выполнения решения (обслуживания клиентов), ледовательно, решение изменяется по мере изменения числа запросов с учетом текущего оложения транспортных средств.

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

динамических запросов. Для задач с количество динамических запросов 90% общее пройденное расстояние увеличивается на 15% по сравнению со статическими задачами.

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

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

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

1. Разработан ГА для решения транспортной задачи с ограничением по времени Разработаны и модифицированы ГО. Анализ оценки времени работы нового ГА дл решения транспортной задачи с ограничением по времени показал, что зависимост времени работы алгоритма от размерности задачи составляет 0(п3).

2. Разработаны новые ГО отражающие специфику матричного представления линейно ТЗ. Оценка времени работы ГА для решения линейных транспортных задач показал пропорциональную зависимость от размерности задачи О(п).

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

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

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

6. Предложена модификация ГА для решения ТЗ с ограничением по времени динамическими запросами клиентов. Для задач с количество динамических запросо 90% общее пройденное расстояние увеличивается на 15% по сравнению с статическими задачами.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ:

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

ВАК РФ

1. Емельянова Т.С. Об одном генетическом алгоритме решения транспортной задачи. // Известия ТРТУ. Тематический выпуск «Интеллектуальные САПР». - Таганрог: Изд-во ТРТУ, 2007. №1(73). - С. 65-70.

2. Емельянова Т.С. Об одном генетическом алгоритме решения транспортной задачи с ограничением по времени. // Тематический выпуск «Интеллектуальные САПР». -Таганрог: Изд-во ТТИ ЮФУ, 2008. №4(81). - С. 45-50.

II Свидетельства о регистрации программ на ЭВМ

3. Курейчик В.М., Емельянова Т.С. Программа решения линейных транспортных задач с использованием специального генетического алгоритма // свидетельство об официальной регистрации программы для ЭВМ № 2007613932 от 14.09.2007.

4. Курейчик В.М., Емельянова Т.С. Программа решения транспортных задач с ограничением по времени с использованием комбинированного генетического алгоритма И свидетельство о государственной регистрации программы для ЭВМ №2009610013 от 11.01.2009.

III. Публикации в других изданиях

5. Емельянова Т.С. Применение генетических алгоритмов для решения транспортной задачи линейного программирования. // Перспективные информационные технологии и интеллектуальные системы. - Таганрог: Изд-во ТРТУ, 2006. №3(27). - С. 15-29.

6. Емельянова Т.С. Решение транспортных задач с использованием генетических методов. // Сборник трудов Всероссийской научной школы-семинара молодых ученых, аспирантов и студентов «Интеллектуализация информационного поиска, скантехнологии и электронные библиотеки». - 2007. Таганрог: Изд-во ТТИ ЮФУ. С. 82-87.

7. Емельянова Т.С. Анализ методов решения нелинейных транспортных задач. // Перспективные информационные технологии и интеллектуальные системы. -Таганрог: Изд-во ТРТУ, 2007. №1(29). - С. 38-49.

8. Емельянова Т.С. Эвристические и метаэвристические методы решения динамической транспортной задачи. // Перспективные информационные технологии и интеллектуальные системы. - Таганрог: Изд-во ТРТУ, 2007. №3(31). - С. 33-43.

9. Емельянова Т.С. Разработка программы для решения транспортных задач с ограничением по времени на основе генетических алгоритмов. // Сборник трудов Всероссийской научной школы-семинара молодых ученых, аспирантов и студентов «Интеллектуализация информационного поиска, скантехнологии и электронные библиотеки». - 2008. Таганрог: Изд-во ТТИ ЮФУ. С. 76-81.

10. Емельянова Т.С. Генетический алгоритм решения транспортной задачи с ограничением по времени. // Перспективные информационные технологии и интеллектуальные системы. - Таганрог: Изд-во ТРТУ, 2007. №4(32). - С. 43-59.

11. Емельянова Т.С. Модифицированный генетический алгоритм для решения транспортных задач с ограничением по времени. // Труды международных научно-технических конференций «Интеллектуальные системы» (AIS'08) и «Интеллектуальные САПР» (CAD02008) - М.: Физматлит, 2008, Т.1. С. 41-46.

12. Емельянова Т.С. Генетические алгоритмы решения транспортных задач. // Тезись докладов IX Всероссийской научной конференции «Техническая кибернетика радиоэлектроника и системы управления». — Таганрог: Изд-во ЮФУ - 2008. С. 150 151.

13. Емельянова Т.С. Решение эталонных транспортных задач с кластерны расположением клиентов с использованием генетических методов. // Сборни научных трудов второй всероссийской научной конференции с международны участием нечеткие системы и мягкие вычисления (НСМВ-2008): (г. Ульяновск, 27-2 октября, 2008 г.). -Ульяновск: Изд-во УлГТУ, 2008, С. 194-201.

14. Курейчик В.М., Емельянова Т.С. Решение транспортных задач с использование комбинированного генетического алгоритма. // Искусственный интелле) Одиннадцатая национальная конференция по искусственному интеллекту международным участием КИИ-2008 (28 сентября - 3 октября 2008 г., г. Дубн Россия). Труды конференции. Т.1 - М.: Физматлит, 2008. С. 158-164.

Личный вклад автора в работах [3]-[4] состоит в следующем, разработка операторо генетического алгоритма, программирование, отладка и тестирование программы; в работ [14] модификация оператора инициализации, разработка новых операторов кроссинговера мутации.

СОДЕРЖАНИЕ.

ВВЕДЕНИЕ.

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

1.1 Классификация транспортных задач. Транспортные задачи с ограничением по времени.

1.2 Динамическая транспортная задача. Проблема оценки динамической составляющей транспортной задачи.

1.3 Анализ методов решения транспортных задач с ограничением по времени.

1.4 Выводы.

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

2.1 Постановка транспортной задачи линейного программирования.

2.2 Определение и основные свойства генетических алгоритмов.

2.3 Структура генетического алгоритма.

2.4 Конструирование начальной популяции.

2.5 Операторы селекции.

2.6 Оператор кроссинговера.

2.7 Оператор мутации.

2.8 Выводы.

ГЛАВА 3 ГЕНЕТИЧЕСКИЙ АЛГОРИТМ РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ С ОГРАНИЧЕНИЕМ ПО ВРЕМЕНИ.

3.1 Математическая постановка транспортной задачи с ограничением по времени.

3.2 Структура разработанного генетического алгоритма.

3.3 Кодирование решения.

3.4 Оператор инициализации.

3.5 Оператор кроссинговера.

3.6 Операторы мутации.

3.7 Фундаментальная теорема ГА.

3.8 Оценка временной сложности алгоритма.

3.9 Распараллеливание алгоритма для многоядерных систем.

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

3.11 Выводы.

ГЛАВА 4 ТЕСТИРОВАНИЕ И ЭКСПЕРИМЕНТАЛЬНОЕ ОБОСНОВАНИЕ РАЗРАБОТАННЫХ АЛГОРИТМОВ.

4.1 Описание тестовых моделей транспортных задач.

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

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

4.4 Исследование влияния динамической составляющей на решение транспортных задач с ограничением по времени.

4.5 Выводы.

Актуальность работы

Транспортировка важная область жизнедеятельности человека. Перевозка людей и грузов (от пищевых до промышленных) — это неотъемлемая часть жизни современного человека. Так расходы на транспортировку различных видов грузов составляют в Великобритании -15%, во Франции — 9%, в Дании - 15% от общих национальных расходов [1]. Необходимость решения таких транспортных задач, с минимизацией издержек на перевозку, определяется большим экономическим эффектом при нахождении лучшего решения, т.к. это явно увеличивает прибыль предприятия. Применение компьютерных методов решения задач позволяет увеличить скорость принятия решений и повысить эффективность найденных решений. Поэтому требуются алгоритмы способные исполняться на массово доступных вычислительных средствах (персональных компьютерах и малых серверах). Разработка новых алгоритмов должна учитывать структуру вычислительных средств, на которых будут исполняться программы (реализующие данные алгоритмы). В настоящее время основные тенденции развития компьютерной техники таковы: за последние несколько лет резко снизился рост частоты процессоров, появилась возможность хранить в памяти огромные объемы информации. Снижение роста быстродействия процессоров произошло из-за достижения технологического предела нанометровых технологий, однако появилась возможность разместить на одном кристалле большее количество вычислительных элементов (процессорных ядер). Польза от использования этих ядер будет только в том случае, если исполняемая программа (и её алгоритм) является параллельным, в противном случае будет использоваться (работать) только одно ядро, а остальные будут простаивать. Известно, что классические алгоритмы не имеют возможности распараллеливания и имеют экспоненциальный рост времени выполнения от размерности задачи. Т.е. количество математических действий (команд) растет экспоненциально, а развитие процессорных элементов (увеличение тактовой частоты, уменьшение количества тактов выполнения команд, задержка на выборку данных из памяти) не компенсируют растущие (с увеличением размерности задачи) потребности классических алгоритмов. Точные методы решения транспортных задач (ТЗ), позволяют найти решение только для задач с малым количеством клиентов (т.е. до 50-ти клиентов [2]). Для решения задач большой размерности точные методы являются не эффективными в связи с их большими временными затратами. Однако, именно сейчас, требуется эффективные алгоритмы решения задач большой размерности, т.к. в настоящее время наблюдается процессы глобализации в экономике. В частности, это приводит к слиянию множества мелких и средних компаний в крупные корпорации, которые пытаются уменьшить издержки путем сокращения количества однотипных объектов инфраструктуры (складов, ремонтных мастерских и пр.) преобразовывая их в крупные объекты регионального значения. Что приводит к необходимости планирования транспортных операций с большим количеством клиентов, т.е. к ТЗ большой размерности. Таким образом, решение ТЗ большой размерности является актуальной задачей. Одним из классов ТЗ является ТЗ с ограничением по времени. Данный класс задач является сложным для решения, но необходимым и широко применяемым на практике. Моделью ТЗ с ограничением по времени описываются: банковские и почтовые доставки, перевозка людей, сбор промышленных и бытовых отходов, доставка продуктов, доставка топлива и материалов на предприятия. На настоящий момент в иностранной литературе предложено множество алгоритмов решения данного класса задач, к сожалению, в нашей стране методы транспортной логистики только начинают свое развитие. Практическим алгоритмам по решению ТЗ с ограничением посвящено множество работ следующих ученых: Solomon, Tompson, Psaraflis, Russell, Antes, Derigs, Cordone, Wolfer-Calv, Caseau, Laburthe, Braysy, Rochat, Taillard, Chiang,

Cordeau, Thangiah, Homberger, Gehring, Mester, Barkaoui, Csiszar, Van Henlenryck и др.

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

Цель диссертации

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

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

1. Проведение сравнительного анализа эффективности существующих методов решения ТЗ.

2. Построение генетических операторов отражающих специфику решаемой ТЗ (линейной или с ограничением по времени).

3. Разработка специального комбинированного генетического алгоритма (ГА) для решения статической ТЗ с ограничением по времени.

4. Разработка модифицированного ГА для решения динамической ТЗ.

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

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

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

2. Разработаны новые модификации ГА для решения статической и динамической транспортной задачи с ограничением по времени.

3. Предложен метод распараллеливания ГА для применения его в многоядерных системах, что позволило получить увеличение быстродействия.

Результаты выносимые на защиту

1. Генетические операторы для решения линейной транспортной задачи большой размерности (порядка 100x100).

2. Новый ГА и генетические операторы для решения транспортных задач с ограничением по времени.

3. Модифицированный ГА для решения динамической транспортной задачи, позволяющий реагировать на изменение (появление/удаление) запросов от клиентов при исполнении полученного решения, т. е. изменять решение в процессе его выполнения с целью уменьшения транспортных затрат.

4. Метод распараллеливания ГА ориентированный на выполнение разработанных алгоритмов на многоядерной вычислительной базе.

Практическая значимость

На основе разработанных алгоритмов создан программно-алгоритмический комплекс для решения транспортных задач с ограничением по времени. При построении программного комплекса использовался объектно-ориентированный язык С++ и среда разработки Microsoft Visual

С++ 6.0. Отладка и тестирование проводилось на ЭВМ типа IBM PC, с процессором AMD Athlon 64 Х2 5400+, 2.8 ГГц, ОЗУ 3ГБ. Отличительная особенность разработанного программного комплекса — это эффективное использование многоядерной вычислительной системы, что позволило сократить время решения транспортных задач в два раза.

Внедрение результатов работы

Основные результаты диссертационной работы использованы в госбюджетных и хоздоговорных работах, проводимых в Таганрогском технологическом институте Южного федерального университета: в госбюджетной работе «Разработка теории и принципов построения интеллектуальных систем принятия решений при проектировании на основе квантовых вычислений и бионических методов поиска», в гранте РФФИ «Разработка теории и принципов эволюционной оптимизации и принятия решений на основе бионического моделирования». Материалы диссертации также использованы в учебном процессе на кафедре САПР в Таганрогском технологическом институте Южного федерального университета в цикле лекций и практических занятий по курсам «Методы оптимизации», «Эволюционное моделирование и генетические алгоритмы», «Прикладная информатика».

Методы исследования

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

Апробация работы

Основные результаты, полученные в ходе работы, докладывались и обсуждались на:

1. Всероссийских научных школах-семинарах молодых ученых, аспирантов и студентов «Интеллектуализация информационного поиска, скантехнологии и электронные библиотеки», Таганрог, 2007 и 2008 годы.

2. Международной научно-технической конференции «Интеллектуальные системы» (AIS'08) и «Интеллектуальные САПР» (CAD02008), Геленжик, 2008.

3. IX Всероссийской научной конференции «Техническая кибернетика, радиоэлектроника и системы управления», Таганрог, 2008.

4. Второй Всероссийской научной конференции с международным участием «Нечеткие системы и мягкие вычисления» (НСМВ-2008), Ульяновск, 2008.

5. XI Национальной конференции по искусственному интеллекту с международным участием (КИИ-08), Дубна 2008.

Публикации

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

Объем и структура диссертации

Диссертация состоит из введения, 4 глав, заключения, списка литературы, включающего 102 наименования и 6 приложений. Основной текст диссертации изложен на 150 страницах, включая 41 рисунок и 6 таблиц.

В результате проведенной работы можно сделать следующие выводы:

1. Написан программный модуль, реализующий разработанный ГА для решения линейных задач, позволяет решать линейные ТЗ представленные в матричном виде порядка 100x100 за достаточно малое время (время работы пропорционально размерности задачи).2. Результаты решения тестовых задач размера от 5x5 до 18x18 показали, что решение, полученное разработанным алгоритмом, при подборе параметров ГА, совпадает с оптимальным решением. При решении тестовых задач порядка 100x100 решение улучшалось в среднем на 35% от начального решения, при этом время решения задачи увеличивалось пропорционально размерности задачи.3. Написан программный модуль реализующий, разработанный ГА для решения ТЗ с ограничением по времени программный. Программный модуль был разработан для решения, как тестовых задач Соломона, так и для решения расширенных задач Соломона описанных в текстовом виде. Набор тестовых задач отражал различное расположение клиентов (равномерное, кластерное и смешанное) относительно депо и различную жесткость временных ограничений, накладываемых на время прибытия транспортного средства к клиенту.4. Результаты тестов по задачам всех видов показали, что данный алгоритм в отличие от других известных алгоритмов дает решение, в котором количество транспортных средств и общее пройденное расстояние сбалансировано. Это приводит к тому, что на практике добавляя несколько транспортных средств получаем значительное уменьшение общего пройденного расстояния, что приводит к уменьшению затрат на топливо, амортизацию транспортных средств, уменьшению нагрузки на водителя, также можно отметить, что уменьшается вероятность аварии, т.к. эта вероятность тем выше чем больше пройденное расстояние.5. Адаптация разработанного алгоритма для решения динамической ТЗ позволило решать задачи, в которых некоторое количество запросов клиентов известно заранее, а другие запросы появляются по мере выполнения решения (т.е. в течение дня по мере обслуживания

клиентов). Причем, информация о новых запросах клиентов не может быть предопределена. В данном случае каждый раз при поступлении нового запроса решается задача с учетом уже обслуженных и новых клиентов и текущего положения транспортных средств.6. Результаты решения динамических ТЗ с ограничением по времени при имитации появления запросов в процессе выполнения решения показали, что общее пройденное расстояние получаемого решения увеличивается незначительно (на 15%), даже при большом количестве динамических запросов (90%).Следовательно, тестирование и экспериментальное обоснование разработанного комплекса ГА для ТЗ доказали практическую эффективность разработанных ГА и целесообразность применимости теоретических разработок на практике.ЗАКЛЮЧЕНИЕ Проблема транспортировки груза от производителей к потребителям с наименьшими издержками будет актуальна всегда, с развитием человечества понятие издержек меняется, но желание снизить затраты - остается неизменным. Поэтому основой данной работы явилась разработка комплекса алгоритмов для решения ТЗ адаптированных для выполнения на распространенных и широкодоступных многоядерных процессорах. ГА явились удобной основой для разработки такого комплекса алгоритмов.Результатом работы стал комплекс ГА для решения ТЗ с ограничением по времени. В результате проведенной работы были получены следующие результаты:

1. Разработан ГА для решения транспортной задачи с ограничением по времени. Разработаны и модифицированы ГО. Анализ оценки времени работы нового ГА для решения транспортной задачи с ограничением по времени показал, что зависимость времени работы алгоритма от размерности задачи составляет 0(n J).2. Разработаны новые ГО отражающие специфику матричного представления линейной ТЗ. Оценка времени работы ГА для решения линейных транспортных задач показала пропорциональную зависимость от размерности задачи О(п).3. Разработана процедура распараллеливания ГА с учетом применения данного алгоритма на многоядерных системах, которая позволяет значительно сократить время выполнения алгоритма.4. На основе предложенных алгоритмов разработаны программно алгоритмические модули решения транспортных задач, отличающиеся тем, что позволяют эффективно использовать многоядерную вычислительную систему.5. Анализ результатов экспериментов показал, что разработанный ГА дает наилучшие решения с точки зрения баланса между количеством транспортных средств и общим пройденным расстоянием.6. Предложена модификация ГА для решения ТЗ с ограничением по времени с динамическими запросами клиентов. Для задач с количеством динамических запросов 90% общее пройденное расстояние увеличивается на 15% по сравнению со статическими задачами.Полученные теоретические результаты, подтвержденные практическими экспериментами, продемонстрировали эффективность разработанного комплекса ГА, предназначенного для решения ТЗ и ориентированного на выполнение на распространенных и доступных вычислительных системах.

1.Csiszar S. Optimization Approaches for Logistic Problems -Vehicle Routing Problem with Time Windows // PhD Dissertation. - Budapest, Hungary, submitted: August 2006.

2. Cordeau J.-F, Desaulniers G., Gesrosiers J., Solomon M., Soumis F. The VRP with Time Windows. Chapter 7 // Paolo Toth and Daniel Vigo (eds), SIAM, Monographs on Discrete Mathematics and Applications. 2001.

3. Babb T. Pickup and Delivery Problem with Time Windows, CoordinatedTransportation Systems: The State of the Art // Department of Computer Science University of Central Florida Orlando, Florida. 2005.

4. B.H. Иванченко, C.M. Ковалев, A.H. Шабельников. Новыеинформационные технологии: интегрированная информационно-управляющая система автоматизации процесса расформирования-формирования поездов: Учебник. Ростов-на-Дону, РГУПС, 2002.

5. Laporte G. The Vehicle Routing Problem: An overview of exact and approximate algorithms // European Journal of Operation Research. -1992.-Vol. 59-p. 345 -358.

6. Pisinger D., Roplce S. A general heuristic for vehicle routing problems //Computers and Operations Research. 2007. - Vol. 34. - p. 2403-2435.

7. Braysy O., Gendreau M. Route Construction and Local Search Algorithmsfor the Vehicle Routing Problem with Time Windows // Internal Report STF42 AO 1024, SINTEF Applied Mathematics 2001.

8. Kim В., Kim S, Sahoo S. Waste collection vehicle routing problem withtime windows // Computers & Operations Research. 2006. - Vol. 33. -pp. 3624-3642.

9. Flatberg Т., Halse G., Kloster O., Nilssen J., Riise A. Dinamic andStochastic Aspects in Vehicle Routing A Literature Survey // STF90 A05413, SINTEF Applied Mathematics. - 2005.

10. Potvin J.-Y., Xu Y., Benyahia I. Vehicle routing and scheduling whith dynamic trave times // Computer & Operations Research. 2006. - Vol. 33,p. 1129- 1137.

11. Malandraki C., Daskin M.S. Time Dependent Vehicle Routing Problems: Formulations, Properties and Heuristic Algorithms // Transportation Science 1992 - 26(3) - p. 185-200.

12. Haghani A., Jung S. A dynamic vehicle routing problem with time-dependent travel times // Computers & Operations Research 2005 - 32 -p.959-2986, 2005.

13. Ichoua S., Gendreau M., Potvin J.-Y. Vehicle Dispatching with Time-Dependent Travel Times // European Journal of Operational Research -2003- 144(2)-p.379-396.

14. Fleischmann В., Gietz M., Gnutzmann S. Time-Varying Travel Times in Vehicle Routing // Transportation Science 2004 - 38(2) - p. 160-173.

15. Ichoua S., Gendreau M., Potvin J. Y. Vehicle dispatching with time-dependent travel times // European Journal of Operational Research 2003 - 144-p.379-396.

16. Montemanni R., Gambardella L.M. An exact algorithm for the robust shortest path problem with interval data // Computers & Operations Research 2004 - 31(10) - p. 1667-1680.

17. Hall R.W. The fastest path through a network with random time-dependent travel times // Transportation Science 1986 -20(3) - p. 182188.

18. Fu, L. and L.R. Rilett, Expected shortest paths in dynamic and stochastic traffic networks. Transportation Research part B, 32(7): 499-516, 1998.

19. Fu L. Scheduling dial-a-ride paratransit under time-varying, stochastic congestion // Transportation Research 2002 - part B, 36 - p.485-506.

20. Kim S, Lewis M.E., White C.C. Optimal vehicle routing with real-time traffic information. Working paper, College of Engineering, University of Michigan, 2004

21. Larsen A. The dynamic vehicle routing problem // Ph.D. dissertation, Technical University of Denmark, Lyngby, Denmark. — 2000.

22. Montemanni R., Gambardella L.M., Rizzoli A.E., Donati A.V. A new algorithm for a Dynamic Vehicle Routing Problem based on Ant Colony System // Technical Report: 1DSIA-23-02, 2002.

23. Russell W., Bent R., Hentenryck P.V. Scenario-Based Planning for Partially Dynamic Vehicle Routing with Stochastic Customers. // Operation Research 2004 - Vol. 52, No. 6 - pp. 977-987.

24. Zhu K., Ong K. L. A reactive method for real time dynamic vehicle routing problem // 12th ICTAT 2000, Vancouver, Canada 2000.

25. Zhao X., Goncalves G., Dupas R. A genetic approach to solving the vehicle routing problem with time-dependent travel times // 16th Mediterranean Conference on Control and Automation Congress Centre Ajaccio, France June 25-27 2008 - pp.413-418.

26. Blasum U., Hochstattler W. Application of the Branch and Cut Method to the Vehicle Routing Problem // Technical Report zaik2000-386, Centre of Applied Computer Science, University of Cologne, Germany. 2000.

27. Емельянова Т.С. Анализ методов решения нелинейных транспортных задач. // Перспективные информационные технологии и интеллектуальные системы. 2007. №1(29). - С. 38-49,

28. Solomon М. М. Algorithms for the Vehicle Routing and Scheduling Problems with Time Windows Constraints // Operation Research. 1987. -Vol 35-pp. 254-265.35. http://web.cba.neu.edu/-msolomon/problems.htm.

29. Braysy O., endreau M. Genetic Algorithms for the Vehicle Routing Problem with Time Windows // STF42 AO 1021, SINTEF Applied Mathematics, Research Council of Norway. 2001.

30. Gendreau M., Braysy O. Metaheuristic Approaches for the Vehicle Routing Problem with Time Windows: A Survey // MIC2003: The Fifth Metaheuristics International Conference, Kyoto, Japan. August 25-28, 2003.

31. Braysy O., Gendreau M. Tabu Search Heuristics for the Vehicle Routing Problem with Time Windows // Internal Report STF42 AO 1022, SINTEF Applied Mathematics, Department of Optimisation, Oslo, Norway. 2001.

32. Tan К. C., Lee L. H., Zhu Q. L., Ou. K. Heuristic methods for vehicle routing problem with time windows // Artificial Intelligent in Engineering. -2001.-Vol. 15-pp. 281-295.

33. Potvin J.-Y., Rousseau J.-M. A Parallel Route Building Algorithm for the Vehicle Routing and Scheduling Problem with Time Windows // European Journal of Operational Research. 1993. -Vol. 66. - P. 331-340.

34. Ioannou G., Kritikos M., Prastacos G. A Greedy Look-Ahead Heuristic for the Vehicle Routing Problem with Time Windows // Journal of Operational Research Society. 2001. -Vol. 52. - P. 523-537.

35. Potvin J.-Y., Rousseau J.-M. An Exchange Heuristic for Routeing Problems with Time Windows // Journal of the Operational Research Society 1995 - 46 - p.1433-1446.

36. Thompson P. M., Psaraftis H.N. Cyclic Transfer Algorithms for Multivehicle Routing and Scheduling Problems // Operations Research -1993 —41 p.935-946.

37. Laporte G., Gendreau M., Potvin J.-Y., Semet, F. Classical and modern heuristic for the vehicle routing problem // International Transaction in Operational Research. 2000. - Vol. 7. - pp. 285-300.

38. Russell R.A. Hybrid Heuristics for the Vehicle Routing Problem with Time Windows // Transportation Science 1995 - 29 - p. 156-166.

39. Antes J., Derigs U. A New Parallel Tour Construction Algorithm for the Vehicle Routing Problem with Time Windows // Working Paper, Department of Economics and Computer Science, University of Koln, Germany, 1995.

40. Antes J., Derigs U. A new parallel tour construction algorithm for the vehicle routing problem with time window // University of Koln, Germany, Department of Economics and Computer Science. Working paper 1995.

41. Cordone R., Wolfler-Calvo R. A Note on Time Windows Constraints in Routing Problems // Internal Report, Department of Electronics and Information, Polytechnic of Milan, Milan, Italy, 1997.

42. Caseau Y., Laburthe F. Heuristics for Large Constrained Vehicle Routing Problems // Journal of Heuristics 1999 - 5 - p.281-303.

43. Braysy О., Gendreau M. Metaheuristics for the Vehicle Routing Problem with Time Windows // Internal Report STF42 AO 1025, SINTEF Applied Mathematics, Department of Optimisation, Norway, 2001.

44. Braysy O, Gendreau M. Metaheuristics for the Vehicle Routing Problem with Time Windows // Internal Report STF42 AO 1025, SINTEF Applied Mathematics, Department of Optimisation, Oslo, Norway. -2001.

45. Taillard E., Badeau P., Gendreau M, Guertin F., Potvin J.-Y. A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windos //Transportation Science. 1997 - Vol. 31. - pp. 170 - 186.

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

47. Rochat Y., Taillard E. Probabilistic Diversification and Intensification in Local Search for Vehicle Routing // Journal of Heuristics 1995 - 1 — pl47—167.

48. Chiang W.C., Russell R.A. A Reactive Tabu Search Metaheuristic for the Vehicle Routing Problem with Time Windows // INFORMS Journal on Computing 1997 - 9 - p.417-430.

49. Cordeau J.-F., Laporte G., Mercier A. A Unified Tabu Search Heuristic for Vehicle Routing Problems with Time Windows // Journal of the Operational Research Society 2001 - 52 - p. 928-936.

50. Thangiah S. R. Vehicle Routing with Time Windows using Genetic Algorithms // Technical Report SRU-CpSc-TR-93-23, Computer Science. 1993.

51. Chang Y., Chen L. Solve the vehicle routing problem with time windows via a genetic algorithm // Discrete and continuous dynamical systems supplement. 2007. - pp. 240-249.

52. Bjarnadottir A.S. Solving the Vehicle Routing Problem with Genetic Algorithms. Printed by Informatics and Mathematical Modelling, 1MM Technical University of Denmark, DTU. 2004.

53. Jung S., Moon. B.R. A Hybrid Genetic Algorithm for the Vehicle Routing Problem with Time Windows. // In Proceedings of Genetic and Evolutionary Computation Conference. San Francisco: MorganKaufmann Publishers-2002-p. 1309-1316.

54. Braysy O., Gendreau M., Dullaert W. Evolutionary Algorithms for the Vehicle Routing Problem with Time Windows // Journal of Heuristics. -2004.-Vol. 10.-pp. 587-611.

55. Mester D., Braysy O. Active guided evolution strategies for the large scale vehicle routing problem with time windows // Computers & Operations Research. 2005. - Vol.32. - pp. 1593-1614.

56. Berger J., Barkaoui M. A Parallel Hybrid Genetic Algorithm for the Vehicle Routing Problem with Time Windows // Computer and Operation Research. 2004. - Vol. 31. - pp. 2037-2053.

57. Bent R., Hentenryck PV. A Two-Stage Hybrid Local Search for the Vehicle Routing Problem with Time Windows // Transportation Science -2004. Vol. 38 - pp. 515-530.

58. Csiszar S. Two-Phase Heuristic for the Vehicle Routing Problem with Time Windows // Acta Polytechnica Hungarica. 2007. - Vol. 4 - pp. 143-156.

59. Вентцель E. С. Исследование операций: задачи, принципы, методология. М.: Наука. 1988.

60. Вентцель Е. С. Исследование операций. М., «Советское радио», 1972.

61. Таха X. А. Введение в исследование операций. 6-е издание.: Пер. с англ. — М.: Издательский дом «Вильяме», 2001.

62. Емельянова Т.С. Генетические алгоритмы решения транспортных задач. // Тезисы докладов IX Всероссийской научной конференции «Техническая кибернетика, радиоэлектроника и системы управления». Таганрог: Изд-во ЮФУ - 2008. С. 150-151.

63. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы построение и анализ Пер. с англ.- М 2004.

64. Емельянов В. В., Курейчик В. В, Курейчик В. М. Теория и практика эволюционного моделирования. М. : ФИЗМАТ ЛИТ, 2003

65. Генетические алгоритмы: Учебное пособие. Под ред. В.М. Курейчика. Ростов-на-Дону: ООО «Ростиздат», 2004.

66. Курейчик В.М. Генетические алгоритмы и их применение. -Таганрог: Изд-во ТРТУ, 2002.

67. Michalewicz Z. Genetic Algorithms + data structures = evolution programs. Springer-Verlay, New York, 1992.

68. Емельянова Т. С. Применение генетических алгоритмов для решения транспортной задачи линейного программирования. // Перспективные информационные технологии и интеллектуальные системы 2006 -Таганрог, №3(27) - 15-29.

69. Емельянова Т. С. Об одном генетическом алгоритме решения транспортной задачи. // Известия ТРТУ. 2007 - Таганрог, №1(73), 65-70.

70. Емельянова Т.С. Об одном генетическом алгоритме решения транспортной задачи с ограничением по времени. // Известия ЮФУ. Тематический выпуск «Интеллектуальные САПР». 2008. №4(81). -С. 45-50.

71. Емельянова Т.С. Генетический алгоритм решения транспортной задачи с ограничением по времени. // Перспективные информационные технологии и интеллектуальные системы. 2007. №4(32).-С. 43-59.

72. Королюк В.С.,Портенко Н.И., Скороход А.В., Турбин А.Ф. Справочник по теории вероятностей и математической статистике. — М.: Наука, 1985.

73. Glover A., Kochenberger Gary A. Handbook of Metaheuristics. Springer, 2002.

74. Курейчик B.M., Гладков JI.A. Основные положеия теории генетического поиска. Конспект лекций. Таганрог: Изд-во ТРТУ, 2001.

75. Holland J.H. Adaptation in Natural and Artificial System. An Introductory Analysis with Application to Biology, Control, and Artificial Intelligence. University of Michigan. 1975.

76. David A. Coley. An Introduction to Genetic Algorithms for Scientists and Engineers, World Scientific Publishing Co., Inc., River Edge, NJ, 1998.

77. Melanie M. An Introduction to Genetic Algorithms. A Bradford Book The MIT Press Cambridge, Massachusetts • London, England., 1999.

78. Шилд Г. Полный справочник по С++, 4-е издание.: Пер. с англ. М. Издательский дом «Вильяме», 2007.

79. Страуструп Б. Язык программирования С++. Специальное издание.: Пер. с англ. М. ООО «Бином-Пресс», 2006.

80. Емельянова Т. С. Использование библиотеки Direct Draw в MS Visual С++ для улучшения визуализации решений математических задач. // Технологии Microsoft в теории и практике программирования. 2008 - Таганрог - 5-8.

81. Genderau М., Guertin F., Potvin J. Y., Taillard E.Tabu Search for RealTime Vehicle Routing and Dispatching // Technical report CRT-96-47, Centre de recherchesur les transports, Universite' de Montre'al,Montre'al, Canada-1996.

82. Ichoua S., Genderau M, Potvin J. Y. Diversion Issues in Real-Time Vehicle // Dispatching Transportation Science 2000 - Vol. 34, No. 4, November. - pp.427-438.