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

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

ШАМЛИЦКИЙ ЯРОСЛАВ ИВАНОВИЧ

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

05.13.ОХ — Системный анализ, управление и обработка информации

АВТОРЕФЕРАТ

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

Красноярск - 2006

Работа выполнена в Государственном образовательном учреждении высшего профессионального образования «Сибирский государственный аэрокосмический университет имени академика М.Ф. Решетнева», г. Красноярск

Научный руководитель:

кандидат технических наук, профессор Сорокин Владимир Афанасьевич

Официальные оппоненты:

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

кандидат технических наук, профессор Вейсов Евгений Алексеевич

Ведущая организация: Федеральное государственное

унитарное предприятие Научно-производственное объединение прикладной механики имени академика М.Ф. Решетнёва, г. Железногорск

Защита состоится "28" декабря 2006 года в 11 часов на заседании диссертационного совета Д 212.249.02 при Сибирском государственном аэрокосмическом университете имени академика М.Ф. Решетнева по адресу: 660014, г. Красноярск, пр. им. газеты «Красноярский рабочий», 31

С диссертацией можно ознакомиться В научной библиотеке Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнева

Автореферат разослан "27" ноября 2006 г.

Ученый секретарь Ц И.В. Ковалев

диссертационного совета

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

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

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

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

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

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

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

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

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

Методы исследования. Результаты исследования базируются на применении теории системного анализа, исследования операций, эволюционной оптимизации.

Научная новизна диссертационной работы:

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

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

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

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

Реализация полученных результатов работы.

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

На основании анализа и предложенной модели бизнес-процессов учета выдачи материалов и планирования транспортных маршрутов, проведенного в диссертационной работе, на ОАО «Красноярский завод холодильников» Бирюса» (г, Красноярск) создан отдел внутризаводской логистики.

Защищаемые положения:

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

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

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

Апробация работы. Основные положения и результаты диссертации докладывались и обсуждались на Всероссийской научно-практической конференции «Актуальные проблемы авиации и космонавтики» (2005 г.), Международной научной конференции «Туполевские чтения» (г. Казань, 2005 г.), Международной научно-практической конференции «Решетневские чтения» (2005 г.), Научно-практической конференции «{Молодежь Сибири — пауке России» (2005 г.), В научном журнале «Вестник СибГАУ» (2006 г.), Международной научной конференции «Методы и алгоритмы прикладной математики в технике, медицине и экономике» (г. Новочеркасск, 2006 г.), Международной научной конференции «Теория, методы проектирования, программно-техническая платформа корпоративных информационных систем» (г. Новочеркасск, 2006 г.).

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

Структура и объем работы.

Диссертационная работа состоит из 135 страниц, 59 иллюстраций, 14 таблиц, 8 приложений. При написании диссертации были использованы 117 источников информации.

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

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

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

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

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

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

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

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

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

- Отсутствует мониторинг выполнения перевозок.

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

1 Выдача материалов со складов происходит согласно месячного лимита. Схема исключает возможность «подгонки» учетных данных сотрудниками предприятия.

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

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

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

Система маршрутизации «Деловая карта» «Деловая карта)) обеспечивает автоматическую прокладку маршрутов автомобилей, от точки начала до точки окончания через все пункты объезда, с учетом точек запрета проезда на автомобиле. Расчет маршрута производится с учетом организации дорожного движения, ограничений для грузового транспорта, весогабаритных 01раничениЙ при проезде участков улиц (дорог), ограничения на возможность проезда в конкретное время - разведенные мосты, время действия дорожных знаков.

PTV

PTV transport mobility logistics - Германия, Карлсруэ (Karlsruhe), немецкая организация, область деятельности которой транспортная логистика. Этот пакет специально предназначен для транспортных предприятий или организаций предоставляющих услуги в области логистики, в составе которых имеются собственные 1Т-подразделения.

ArcLogistics Route

Гораздо менее известной программой в России является ArcLogistics Route, заявляемое как завершенное программное обеспечение для решения задач маршрутизации и составления расписаний.

К сожалению, ArcLogistics Route имеет существенное для наших условий ограничение. Он работает только с дорожной сетью США, хранящейся в закрытом формате, и не позволяет использовать карты дорожных сетей других стран.

Можно подытожить, что в настоящее время имеется ряд программных продуктов предназначенных для маршрутизации и составления оптимальных расписаний. Некоторые из этих программ доступны по цене, но оставляют желать лучшего по качеству исполнения. Яркий пример на отечественном рынке - «Деловая карта». Явным преимуществом ее перед западными аналогами является цена, однако качество исполнения значительно отстает от западного и европейского. Другие же вместе с высоким качеством И мировой популярностью имеют столь же высокую цену. Наиболее ярким примером популярных разработок является «ArcLogistics Route». Качество программы, завоевавшее ей мировую популярность, оборачивается, с другой стороны, высокой ценой. Такие расходы в настоящее время могут позволить себе далеко не все организации. Очевидным является то, что необходимо исследовать эту область, изучить теоретические основы и механизмы маршрутизации, создавать собственные программы, отвечающие мировым стандартам.

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

Пусть N совокупность заявок на перевозку. Для каждой заявки

I б N груз размером q, должен быть доставлен из пунктов загрузки N* в пункты назначения

Ï.-24—S"*/«

JtM, JfH,

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

К* ~\JN'

ItN

как совокупность пунктов загрузки и

лг^ид;

ли

как совокупность пунктов разгрузки. Пусть Г^ЛГиЛГ.

Кроме того, пусть М будет совокупностью транспортных средств. Каждое транспортное средство к е М обладает грузоподъемностью & € N, начальным положением к* и конечным к~. Определим ЛГ := {Г | к е м}

как совокупность исходных пунктов, а

М~ {¡Г | к е м) как совокупность конечных пунктов. Пусть

Для всех ^еУиФ пусть означают расстояния, ^время поездки, а с^ ее стоимость. К тому же время задержки в пунктах загрузки и назначения не рассматривается отдельно, а включается во время переезда между этими пунктами.

Определение 1:

Маршрут вывоза и доставки Д*для транспортного средства к - это направленный маршрут через подмножество пунктов К,сК, таким образом, что;

. 1 Л( берет начало в ;

3 Если Л/иЛ^с*»! тогда все пункты Л^должны быть посещены, прежде чем пункты Л^;

4 Транспортное средство к посещает каждый пункт Г1 только однажды;

5 Загрузка транспорта никогда не превышает £)к;

6 л, заканчиваются в к~.

Определение 2:

1 /^ является маршрутом вывоза и доставки для каждого транспортного средства к, для каждого к е М',

2 | к е М} есть часть V.

Среди рассмотренных моделей маршрутизации многие отвечают тем или иным требованиям к планированию перевозок на крупном машиностроительном предприятии, в частности, на ОАО «Красноярский завод холодильников» Бирюса». Обусловлено это тем, что процессы перевозки могут существенно различаться при выполнении различных задач: доставки материалов со складов в производственные цеха, транспортировки грузов между цехами, также нельзя исключать и возможность перевозок из

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

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

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

На большинстве крупных машиностроительных предприятий имеется централизованный склад, перевозки начинаются на складе, и по завершению процесса перевозок транспортное средство возвращается на склад, поэтому в данном случае целесообразно рассматривать за основу модель VRP с временными окнами. Эта модель позволяет решить основную задачу процесса перевозок - своевременную доставку материалов и комплектующих в цеха предприятия.

Математическая модель, которая исследована и модифицирована под условия крупного машиностроительного предприятия, называется Vehicle Routing Problem with Time Windows (маршрутизации транспорта с временными окнами). Моделью VRPTW рассматривается работа группы транспортных средств с ограниченной грузоподъемностью по доставке грузов из центрального склада пространственно удаленным клиентам в определенный промежуток времени. Временное окно двустороннее, это значит, что клиент должен быть обслужен не прежде раннего времени и не после позднего времени обслуживания. Если транспортное средство достигает клиента быстрее, чем наступает ранняя граница, то оно переходит в режим ожидания. Транспортное средство, которое достигает клиента после позднего срока, считается опоздавшим. Время обслуживания включает непосредственное время обслуживания клиента. Стоимость маршрута складывается из времени затрачиваемого непосредственно на дорогу, время ожидания и время обслуживания каждого клиента. Если одного рейса

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

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

Математическая формулировка базируется на модели представленной Marius Solomon и Paul Thompson в 1987 году описывающей проблему маршрутизации транспортных средств с временными окнами. i,j = l,...,NKk = Параметры:

1 К - количество транспортных средств;

2 N - число клиентов (0 означает центральный склад);

3 Т - максимальное время работы транспорта;

4 С, - клиент

5 Со - центральный склад;

6 г„ - маршрут транспортного средства (ТС) к,

7 0„ - общая перегрузка ТС на маршруте Ь,

8 п - общее опоздание ТСна маршруте к;

9 Dt - общая длина маршрута А;

10 - общее время пребывания ТС на маршруте;

II е* • общее опоздание ТС на маршруте Ь,

12 - время переезда между клиентами / и

13 ' ■ п - 1рузоподьемаость ТС ч ■

14 1) - время прибытия к клиенту

15 Ii - время обслуживания клиента (;

16 щ • время ожидания перед обслуживанием клиента г.

17 е, - раннее время доставки к клиенту

18 h - позднее время доставка к клиенту г,

19 Чл - величина груза для доставки к клиенту 1 ТС-ом

20 г л - время необходимое для обслуживания ¿-то клиента к-м ТС (включая

время ожидания);

21 Pi - угол в полярной системе координат клиента 1;

22 ii - угол в псевдополярной системе координат клиента

23 F - фиксированный угол дня определения секторов обслуживания

{ Шх[р,р„ ]/2К,гдеп = 1,..., N );

24 В - длина битовой строки в хромосоме представляющей потомка, В — Э;

25 Р - размер популяции ГА, Р = 50;

26 G - число поколений ГА, в = 1000;

27 S* ■ - начальный угол сектора к\

28 So - начальный угол кластеризации, 5^-0;

29 Ok - коэффициент значимости дня дистанции для к-го ТС;

30 3 - коэффициент значимости для времени маршрутов;

31 - штрафной коэффициент за перегрузку ТС;

32 у - штрафной коэффициент за превышение допустимого времени работы ТС;

33 к - штрафной коэффициент за опоздание ТС на маршрутах. Переменные, добавленные для адаптации алгоритма:

Рск - коэффициент потребления топлива транспортными средствами; Я \ - общее время работы ТС на предыдущих итерациях алгоритма;

Г,' - максимальное время пребывания ТС на маршруте, если алгоритм проходит не первую

итерацию: Т«Т- Л^.

Переменные:

{1, если I обслужен ТС к О, в другом случае

{I, если ТС направляется непосредственно от г к} О, в другом случае

Математическая формулировка задачи выглядит следующим образом:

(\ТУТ\\0 ^¿¿¿с,^ (1)

1»1 1 ¿"1

При условии:

(2)

1-0

(з)

= ■ . (4)

хе„ = 0илы 1; I,} = = 1,,..,К (5)

^ = ° ■ (6) ,

>0

-Л.'-О.....N (8)

>0

1=1,-..,^ (10) ^>0,/ = !,...,^ (11) Целью является минимизация общего времени на транспортировку (1), при условиях ограниченной грузоподъемности, ограниченного времени на выполнение транспортировки и временных рамок накладываемых на прибытие транспортного средства к клиентам. Решение задачи УЯРТ\У достигается тогда, когда обслужены все клиенты без превышения грузоподъемности (2) транспортного средства (ТС) и без превышения временных ограничений (3).

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

В дополнение каждый клиент может быть обслужен только одним ТС и только однажды при каждой итерации алгоритма(б). Время передвижений для ТС - это общая сумма времени затрачиваемого на передвижение от одного клиента к другому плюс время, затраченное на ожидание и на сервисные операции непосредственно у клиента. Время ожидания для ТС -это количество времени, которое ТС затрачивает на ожидание, если прибывает к клиенту раньше величины левого ограничения временного окна. Ограничения, накладываемые временным окном, определены в (9), (10) и (11). Ограничение (9) гарантирует, что значения времени прибытия к ' клиентам совместимы. Ограничение (10), принуждает время прибытия ТС находиться в рамках временного окна, а ограничение (11) гарантирует, что время прибытия ТС к клиенту всегда положительное.

Методика, применяемая в работе - это так называемый cluster-first route-second эвристический алгоритм, применяемый для решения-математической модели (1).

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

СШш) (12)

ill •

где

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

Целевая функция включает компоненты с весовыми коэффициентами а* для дистанции, р для превышения времени маршрута, т) для перегрузки ТС, 7 для преждевременного обслуживания, к за опоздание. Весовые

коэффициенты были вычислены методом экспертных оценок и были установлены равными: ак = 0.09, (3 = 0.01, т] = 0.35, у - 0.35 и к = 0.2. Таким образом, коэффициенты придают большее значение уменьшению опозданий и перегрузок транспорта, так чтобы при этом не было превышено время, отведенное на обслуживание клиентов. Если решение не приводит к перегрузке транспорта, не нарушены временные ограничения, тогда коэффициенты работают на уменьшение общего времени маршрута. Эксперименты с другими весовыми коэффициентами приводили либо к невыполнимым решениям, либо к худшим решениям.

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

Для решения задачи с N клиентами и одним складом, углы между

клиентами в полярной системе координат р1.....ри заменяются

псевдополярными $......... Углы в псевдополярной системе координат

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

С, назначается Уь если где А™ 0, ...,К-1

Клиент С, назначается на маршрут Ук, если его псевдополярный угол ^ больше чем и меньше чем Фиксированный угол вычислен путем деления максимального полярного угла между клиентами на К,

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

Число поколений, размер популяции, уровень кроссовера и мутации для процесса генетической маршрутизации установлены равными 1000, 50, 0.8 и 0.001 соответственно. Решение, полученное ГА улучшается с использованием

локального постоптимизационного метода.

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

S-{я,.....лг,...,Я1,...,Лк}, где каждый маршрут это перечень клиентов

предназначенных для обслуживания. Х-обмен между парой маршрутов это замена подмножества клиентов S, с Д^, размера ¡5,] <Х другим подмножеством S2 с Л,размера ^¡(¿Я с тем, чтобы получить два новых маршрута R'p -(R^-SJ^S^, R'4 =(if, -5,)ui,n новое соседнее решение = Область N^S)решения S, это совокупность соседних

решений S' полученных методом Х-обмена.

К ■ (1С—

При этом, —^—-; (при к < 20), различных - пар маршрутов

подвергаются процессу обмена. Существует два варианта, когда А, = 1 и X = 2, когда один или два клиента перемещаются из одного маршрута в другой в первом случае или обмениваются между двумя маршрутами во втором случае. Операторы применяются в следующем порядке (0,1), (1,0), (1,1), (0,2), (2,0), (2,1), (1,2) и (2,2). Оператор (ОД) означает перемещение одного клиента из' маршрута q в маршрут р. Операторы (1,0), (2,0) и (0,2) означают перемещение одного или двух клиентов из одного маршрута в другой. Оператор (1,1) означает обмен одним клиентом между двумя маршрутами и Т.д.

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

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

Порядок работы алгоритма выглядит следующим образом: Шаг 1: Установить число итераций: itermax = 3.

Установить номер текущей итерации: iter = 0. Шаг 2: Сортировать клиентов в соответствии с их углами системы полярных

. координат и назначить псевдополярные координаты клиентам.

Установить минимальную общую стоимость маршрута: g = со.

Установить минимальную стоимость отдельного маршрута: 1 = оо. Шаг 2: Увеличить число итераций: iter = iter -К 1;

Если iter > itermax, перейти к Шаг 6; Шаг 3: Если ГА остановлен, перейти к Шаг 4.

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

Установить 1 равной текущей стоимости маршрута,

Сохранить набор секторов в 1г;

Если стоимость текущего распределения по

секторам меньше ё,

Установить g равным текущей стоимости маршрута,

Сохранить набор секторов в Произвести селекцию, кроссовер, мутацию.

Шаг 4: Провести операции локальной постоптимизации, используя маршрут 1г.

Если улучшений маршрута 1г сделать нельзя, Перейти к Шаг 5.

Если текущий улучшенный маршрут имеет меньшую стоимость, чем 1,

Установить 1 равной текущей стоимости. Сохранить набор секторов в 1г. Если текущий улучшенный маршрут имеет меньшую стоимость, чем g, установить е равной текущей стоимости. Сохранить набор секторов в Перейти к Шаг 4.

Шаг 5: Проранжировать клиентов маршрута 1г согласно их секторам, и в пределах секторов согласно порядку их посещения.

Сортировать клиентов согласно их рангу. Назначить псевдополярные координаты клиентам, согласно их ранговой сортировке. Шаг 6: Остановить кластеризацию и локальную

постоптимизационную процедуру.

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

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

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

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

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

Система маршрутизации и составления оптимальных расписаний является системой поддержки принятия решений. Базовая архитектура для подобных систем была предложена врга^е в 198бгоду;

Обновление

данных

База дандых

h==iil

База моделей

Г" —1-

Г " 1—

Г 1-

1-i—

СУБД

СУЕМ

гис

Графический интерфейс пользователя

- База данных (DB), для хранения., данных, необходимых для применяемых моделей: расположение распределительных центров (складов) и клиентов, стоимость транспортировки, информация о транспорте и т.д.

- Система управления базой данных (DBMS), для обновления информации в БД.

- База моделей (MB), содержащая семейство моделей и алгоритмов для решения задач маршрутизации, составления расписаний и т.д.

- Система управления базой моделей (MBMS), для обновления изменения добавления и удаления моделей из базы моделей.

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

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

реализаций функций ГИС для решения транспортных задач.

Для системы маршрутизации использована реляционная база данных, реализованная в СУБД MS Access. Данные о транспортной сети, хранящиеся в ней, привязаны к соответствующему слою. Также в ней хранится информация о подвижном составе, характере груза и других параметрах маршрутов. Данная СУБД обеспечивает: необходимый уровень надежности хранения данных, несложную базу данных, широкий набором инструментов и параметров настройки, простой и дружелюбный интерфейс для проектирования базы данных, что в нашем случае также характеризует эту СУБД с положительной стороны.

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

Описаны компоненты, входящие в состав программного продукта, рассмотрены вопросы проектирования базы данных.

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

Главная форма программного продукта предназначена для работы с программой путем внесения заявок формирования маршрутов и при необходимости редактирования ГИС.

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

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

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

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

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

Таким образом, разработашгая программная система характеризуется рядом особенностей, благодаря которым в одном приложении становится возможным:

- решать задачи оптимизации генетическим алгоритмом, меняя при необходимости значения параметров оптимизации;

■ — решать как тестовые, так и практические задачи условной оптимизации;

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

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

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

На основании предложенного и описанного в диссертации бизнес-процесса планирования транспортных перевозок на ОАО «Красноярский завод холодильников» Бирюса» был создан отдел внутризаводской логистики. Основная задача работы отдела, и как основной принцип логистики - обеспечение производства требуемыми материалами, в требуемом количестве, в требуемое время.

Апробация разработанного в диссертации метода решения сложных задач оптимизации проводилась при планировании транспортных маршрутов в отделе внутризаводской логистики на ОАО «КЗХ» Бирюса».

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

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

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

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

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

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

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

1 Шамлицкий, Л. И. / Внедрение новой системы управления транспортными перевозками на предприятиях крупносерийного производства / Я.И. Шамлицкий // Актуальные проблемы авиации и космонавтики: мат. всерос. науч.-практ. конф. — Красноярск: СибГАУ, 2005. С.З15-316.

2 Шамлицкий, Я.И, / Разработка программного обеспечения системы производственной логистики на предприятии машиностроения / Я.И. Шамлицкий // Туполевские чтения: мат. межд. науч. конф. - Казань: Ю ТУ, 2005. С.114-115.

3 Шамлицкий, Я.И, / Внедрение системы планирования потребности в материалах на предприятии крупносерийного производства / Я.И. Шамлицкий К Решетневские чтения: мат. межд. науч.-практ. конф. -Красноярск: СибГАУ, 2005 .С.305-306.

4 Шамлицкий, Я.И. ! Организация транспортных потоков и системы выдачи материалов с помощью генетических алгоритмов на предприятиях крупносерийного производства / Я.И, Шамлицкий Н Молодежь Сибири — науке России: мат. науч.-практ. конф. — Красноярск: СИБУП, 2005. С.132-137.

5 Шамлицкий, ЯЖ / Разработка программного обеспечения по организации транспортных потоков на предприятиях крупносерийного производства / Я.И. Шамлицкий И Вестник Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнева: Сб. науч. тр. /- Красноярск: СибГАУ, 2006. - Вып. 1(8). С.67-70.

6 Шамлицкий, Я.И. / Анализ применения генетических алгоритмов для оптимизации планирования транспортных потоков/ Я.И. Шамлицкий //Методы и алгоритмы прикладной математики в технике, медицине и экономике: мат. межд. науч. конф. - Новочеркасск:ЮРГТУ(НПИ),2006.С.40-42.

7 Шамлицкий, Я.И. / Оптимизация затрат предприятия крупносерийного производства при применении информационной системы планирования транспортных потоков/ Я.И. Шамлицкий //Теория, методы проектирования, программно-техническая платформа корпоративных информационных систем: мат. межд. науч. конф. - Новочеркасск: ЮРГТУ (НПИ),2006.С.25.

Шамлицкий Ярослав Иванович

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

Автореферат

Подписано к печати 24.11.2006 Формат 60x84/16. Бумага писчая, Печ. л. 1,0 Тираж 100 экз. Заказ N3 /г^

Отпечатано в отделе копировальной н множительной техники СибГАУ 660014 г. Красноярск, пр. им. газеты «Красноярский рабочий», 31

ВВЕДЕНИЕ.

1.1 Анализ предприятия и производственной ситуации.

1.2 Организационная реструктуризация существующего бизнес-процесса 4 доставки материалов.

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

1.3.1 Введение.

1.3.2 Постановка задачи коммивояжера.

1.3.3 Жадный алгоритм.

1.3.4 Деревянный алгоритм.

1.3.5 Метод ветвей и границ.

1.3.6 Алгоритм Дейкстры.

1.3.7 Генетические алгоритмы.

Ф 1.3.7.1 Общие сведения.

1.3.7.2 Классический генетический алгоритм.

1.3.7.3 Функция приспособленности и кодирование решений.

1.3.7.4 Алгоритм работы.

1.3.7.5 Факторы, создающие сложность для ГА.

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

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

1.4 Анализ имеющихся программных средств оптимизации и планирования транспортных маршрутов.

1.4.1 Цель и назначение автоматизированного варианта решения задачи.

1.4.2 Общая характеристика организации решения задачи на ЭВМ.

1.4.3 Анализ существующих программных разработок.

1.5 Выводы.

2 ТЕОРЕТИЧЕСКАЯ МОДЕЛЬ СИСТЕМЫ, РАЗРАБОТКА МОДЕЛИ

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

2.1 Модели маршрутизации.

2.2 Математическая формулировка метода оптимизации.

2.3 Обоснование выбора модели маршрутизации.

0 2.4 Сравнение эффективности подходов.

Вывод.

3 ПРОЕКТИРОВАНИЕ СИСТЕМЫ ОПТИМИЗАЦИИ ВНУТРИЗАВОДСКИХ ТРАНСПОРТНЫХ МАРШРУТОВ.

3.1 Выбор технологии проектирования.!.

3.2 Структура разрабатываемой системы маршрутизации.

3.3 База данных.

3.4 Источники данных системы.

3.5 Проектирование базы данных.

§ 3.6 Системы оптимизации загрузки.

Вывод.

4 РАЗРАБОТКА ПРОГРАММНОГО ПРОДУКТА.

4.1 Структура программного продукта.

4.2 Описание работы с программой.

4.3 Программное обеспечение.

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

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

Логистические задачи, которые возникают в практической деятельности простейшими арифметическими действиями решить невозможно. Для -этой цели необходимо построить математическую модель. Математическая модель включает условия задачи и подлежащий оптимизации критерий (или совокупность критериев). Математическая модель решается исходя из входных данных, которые несет в себе конкретная задача [33].

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

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

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

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

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

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

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

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

Научная новизна диссертационной работы:

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

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

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

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

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

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

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

Защищаемые положения

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

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

3 Алгоритм и методика оптимизации на основе генетических алгоритмов более эффективно решают задачи оптимизации транспортных

4 маршрутов, чем с помощью известных программных систем оптимизации транспортных маршрутов.

Цель исследования

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

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

Объект исследования

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

Поскольку при работе конвейера простои или задержки недопустимы, то необходимо четкое и согласованное взаимодействие всех служб предприятия по обеспечению непрерывности конвейерного производства [34]. Одну из главных ролей здесь играет служба МТО, которая должна обеспечить бесперебойное снабжение всех цехов завода необходимыми комплектующими.

На предприятии формируется Центр Обеспечения Материалами (ЦОМ) основная задача которого будет составление графиков потребности и планирования оптимальных маршрутов доставки материалов производственным подразделениям ОАО "КЗХ "Бирюса".

Вывод

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

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

Разработан технический проект на создание информационной системы.

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

- выходные данные;

- ввод данных;

- диалоговые процедуры;

- процедуры контроля вводимых данных;

- проъ^едуры обработки данных;

- проблемы защиты;

- потоки данных.

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

- Графический интерфейс пользователя на базе ГИС;

- База данных информационной системы связанная с модулем оптимальной загрузки транспорта;.

- Алгоритм маршрутизации на базе ГА.

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

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

Интерес к подобным системам со стороны других организаций действительно велик. Опрос, проводившийся 1 - 3 марта в г. Красноярске на выставке «Сибирский промышленный форум. Транспорт и логистика» фирмой Рус-Аналит * (официальный партнер компании «ИНГИТ» Санкт-Петербург) подтверждает заинтересованность бизнеса в подобных разработках. В то же время программа обладает высокой гибкостью и масштабируемостью, которая обеспечивается возможностью использования различных карт дорожной сети, а также возможность изменения математической модели. Изменение этих модулей не требует изменений в других модулях программы. Спрос на продукцию такого класса плюс высокая гибкость программы, позволяет предлагать разработанную систему широкому кругу организаций, которые ставят перед собой целью снижение транспортных расходов.

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

ЗАКЛЮЧЕНИЕ

В результате проведенного исследования был выполнен ряд работ:

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

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

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

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

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

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

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

1. Авилов, A.B. Рефлексивное управление: Методологические основания/ A.B. Авилов. М., 2003.

2. Графы и их применение: Пер. с англ. под ред. И.М. Яглома. М., «Мир», 1965, 174 с.

3. Бардаченко, В.В. Меркурьев, Ю.А. Соломенников A.B. Экономические риски транспортной логистики.- Riga, Computer Modelling & New Technologies, 2002, т. 6, стр. 100-107.

4. Беспалов, Р. Маршрут к сотням ежедневных заказов: Журнал о практической логистике / Р. Беспалов. -2005. -№6

5. Бондарев, В. М. Рублинецкий, В. И. Качко, Е. Г. Основы программирования Харьков, Фолио; Рн/Д., Феникс, 1998, 368 с.

6. Бурцев, М.С. Эволюция кооперации в многоагентной системе :Науч. сес. МИФИ-2005, сб. науч. тр. В 2 ч. 4.1. М.: МИФИ, 2005 -с.217-224

7. Бэстенс, Д.Э. Ван Ден Берг, В.М. Вуд, Д. Нейронные сети и финансовые рынки -М.: ТВП. 1997.

8. Вентцель, Е.С. Исследование операций / Е.С Вентцель.- М.: Высшая школа, 2001.

9. Виноградов, И.М. Математическая энциклопедия / Гл. ред. И.М. Виноградов, т.4. -М.: Советская Энциклопедия, 1984.

10. Галушкин, А. И. Нейрокомпьютеры и их применение / кн.1. Теория нейронных сетей.- М.: Радиотехника, 2000.

11. Друкер, П.Ф. Задачи менеджмента в XXI веке / П.Ф. Друкер М., 2001.

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

13. Змитрович, А. И. Интеллектуальные информационные системы / Минск.: НТООО "Тетра Системе", 1997. 368с.

14. Калянов, Г.Н. Консалтинг при автоматизации предприятий/Подходы, методы, средства / Г.Н. Калянов- М., СИНТЕГ, 1997. 316 с.107

15. Калянов, Г.Н. Теория и практика реорганизации бизнес-процессов / Г.Н. Калянов.- М.: СИНТЕГ, 2000.

16. Карабанов, Б.М. Бизнес-инжиниринг не роскошь, а средство управления / "Конкуренция и Рынок" №6, 2001.

17. Киселев, В.В. Обучение в системах нечеткого управления / В.В. Киселев // Математические структуры и моделирование, вып.6, 2000. с.78-90.

18. Кололопулос, Т. Необходимость workflow . М.: Весть-Метатехнология, 2000.

19. Корнеев, В. В. Гареев, А. Ф, Васютин, С. В. Райх, В. В. Базы данных / Интеллектуальная обработка информации. М.: "Нолидж", 2000. -352с.

20. Котлер, Ф. Основы маркетинга.- СПб.: КОРУНА, 1994.

21. Коуз, Р. Природа фирмы / Под ред. О. Уильямсона и С.Уинтера.- М.: Дело, 2001.

22. Кохонен, Т. Дебок, Г. Анализ финансовых данных с помощью самоорганизующихся карт. -М.: Альпина., 2001

23. Кузнецов, Ю. Н. Кузубов, В. И., Волощенко, А. Б. Математическое программирование: учебное пособие. 2-е изд. перераб. и доп. М.; Высшая школа, 1980, 300 е., ил.

24. Леоненков, A.B. Самоучитель UML СПб.: БХВ-Петербург, 2001. -304 с.

25. Леонтьев, В. Проблема качества и количества в экономике /В.Леонтьев //Экономические эссе. М, 1990. С.80.

26. Липатов, Е. П. Теория графов и её применения. М., Знание, 1986, 32 с.

27. Лукинский, B.C. Бережной, В.И. Бережная, Е.В. Цвиринько, И.А. Логистика автомобильного транспорта. Концепция, методы, модели. М., Фин. и стат.,2004, 277с.

28. Маклаков, С. В. Моделирование бизнес-процессов с AllFusion Process Modeler.-M.:ДИАЛОГ-МИФИ, 2003 240с.

29. Маркова, Е. В. Лисенков, А. Н. Комбинаторные планы в задачах многофакторного эксперимента. -М.: Наука, 1979, 345 с.

30. Месарович, М. Теория иерархических многоуровневых систем. -М.: Мир, 1973.

31. Мескон, М. Альберт, М. Хедоури, Ф. Основы менеджмента. -М.:1995. С.21.

32. Мильнер, 3. Системный подход к организации управления. -М.: Экономика, 1983

33. Миротин, Л.Б. Тышбаев, Ы.Э. Системный анализ в логистике.- М.: Экзамен, 2004.

34. Неруш, Ю. М. Логистика. -М.: Юнити, 2003.

35. Нив, Г.Р. Пространство доктора Деминга. Н. Новгород, Центр Деминга, 2000.

36. Новиков, Ф. А. Дискретная математика для программистов. СПб.: Питер, 2001,304 с, ил.

37. Норт, Д. Институты, институциональные изменения и функционирование экономики.-М., 1997.

38. Ойхман, Е.Г. Попов, Э.В. Реинженеринг бизнеса: Реинженеринг организаций и информационные технологии.- М. .'Финансы и статистика, 1997. -336 е.: ил.

39. Олейник, А. Институциональная экономика. -М., Инфра-М, 2000.

40. Оссовский, С. Нейронные сети для обработки информации/ Пер. с польского И.Д. Рудинского. -М.: Финансы и статистика, 2002. 344 с.

41. Парсонс, Т. О социальных системах Талкотт Парсонс.- М., 2002. С.20.

42. Парсонс, Т. О структуре социального действия. -М., 2000. С. 157158.

43. Редько, В.Г. Эволюционная кибернетика. -М. Наука, 2003. - 156с.

44. Робсон, М. Уллах, Ф. Практическое руководство по реинжинирингу бизнес-процессов /Пер. с англ. под ред. Н. Д. Эриашвили. М.: Аудит, ЮНИТИ, 1997.-224 с.

45. Рубцов, C.B. Взаимодействие открытых систем старая концепция для новых идей / Новые рынки, 2001, № 4.

46. Рубцов, C.B. Уточнение понятия 'бизнес-процесс' / Менеджмент в России и за рубежом, 2001, № 6.

47. Рубцов, C.B. Опыт использования стандарта IDEF0 при проектировании If процессов / Открытые системы, — 2003. — № 1. — С. 53—56.

48. Садовский, В.Н. Системные исследования: некоторые принципиальные проблемы построения общей теории систем. -М.: Наука, 1971.

49. Семенкин, Е.С. Семенкина, О.Э., Терсков, В.А. Методы оптимизации в управлении сложными системами / Учебное пособие. Красноярск: СибЮИ МВД РФ, 2000.-254 с.

50. Сигорский, В. П. Математический аппарат инженера / К., «Технша», 1975, 768 с.

51. Уильямсон, О. И. Экономические институты капитализма: фирмы, рынки, отношенческая контрактация.- Спб., Лениздат, 1996.

52. Уоссерман, Ф. Нейрокомпьютерная техника / Теория и практика. -М.: Мир, 1984.

53. Фаворская, М.Н. Проектирование баз данных в среде Delphi: Лабораторный практикум по дисциплине "Проектирование баз данных" для студентов спец. 552800 и 220200 дневной формы обучения. Красноярск: CAA, 2001. 150 с.

54. Фаворская, М.Н. Интегрированная среда разработки Delphi: В 2 кн. Кн. 1. Проектирование программных средств: Лаб. Практикум по дисциплине "Проектирование программных средств" / CAA. Красноярск, 2001. - 144 с.

55. Ф) 55 Фогель, Л. Оуэне, А. Уолш, М. Искусственный интеллект иэволюционное моделирование.- М.: Мир, 1969.-230 с.

56. Хаммер, М. Чампи, Дж. Реинжиниринг корпорации: Манифест революции в бизнесе /Пер. с англ. — СПб.: Изд-во СПбУ, 1997. — 332 с.

57. Шеер, А.В. Бизнес процессы /Основные понятия, теория, методы -М., Весть-Метатехнология, 1999. 156 с.

58. Шеннон, К. Работы по теории информации и кибернетике.- М., 1963. С.278.

59. Шумский, С. А. Нейрокомпьютинг и его применение в экономике и бизнесе.-М.: МИФИ, 1998.

60. Эшби, У.Р. Введение в кибернетику. М., 1959. С.293-302.

61. Юдицкий, С. А. Вукович, И.Ю. Динамическое экспресс-моделирование организационных систем/ С.А.Юдицкий, И.Ю. Вукович.- М.: ИЛУ, 1998.

62. Barcelo J., Grzybowslca Н. and Pardo S. Vehicle Routing and Scheduling Models, Simulation and City Logisics. Twenty-eighth conference on the mathematics of operations research January, 2003

63. Beyer H.-G., Schwefel H.-P., Wegener I How to analyse Evolutionary Algorithms . Technical Report No.CI-139/02. University of Dortmund, Germany, 2002

64. Bodin, L.D., 1990, "Twenty Years of Routing and Scheduling", Operations Research, 38(4), pp 571 579.

65. Campbell A. M., M. W. P. Savelsbergh Efficient Insertion Heuristics for Vehicle Routing and Scheduling Problems.

66. Chipperfield, A., Fleming, P., Pohlheim, H. and Fonseca, C., 1993, Genetic Algorithm TOOLBOX for Use with MATLAB, Department of Automatic Control and Systems Engineering, University of Sheffield, U.K.

67. De Jong K. An analysis of the behavior of a class of genetic adaptive systems Doctoral dissertation. University of Michigan, Ann Arbor. - University Microfilms No. 76-9381. - 1975

68. Desrochers, M., Lenstra, J.K., Savelsbergh, M.W.P., and Soumis, F., 1988, "Vehicle Routing with Time Windows: Optimization and Approximation", in B.L.

69. Golden and A.A. Assad, (eds.), Vehicle Routing: Methods and Studies, Studies in Management Science and Systems, North Holland, Amsterdam, 16, pp 65 -- 84.

70. Gamma E., Helm R., Johnson R., Vlissides J. Elements of Reusable Object-Oriented Software , Massachusetts: Addison-Wesley, 1995.

71. Goldberg D.E. Genetic algorithms in search, optimization and machine learning. / Reading, MA: Addison-Wesley, 1989.

72. Hoffman Karla. Traveling Salesman Problem. George Mason University, Manfred Padberg. New York University.

73. Holland J.H. Adaptation in Natural and Artificial Systems. The University of Michigan Press, 1975.

74. Holtham C. A groupware-based framework for learning organizations: theP

75. BFS project // IT Support in the Productive Workplace. Stanley Thomms in Association with Unicom, 1996.

76. Koskosidis, Y., Powell, W., and Solomon, M., 1992, "An Optimization-based Heuristic for Vehicle Routing and Scheduling with Soft Time Window Constraints", Transportation Science, 26, pp 69 ~ 85.

77. Koza J. Genetic programming: a paradigm for genetically breeding computer population of computer programs to solve problems. MIT Press, Cambridge, MA, 1992.

78. Lance Chambers (Ed.) Application Handbook of Genetic Algorithms: New

79. Frontiers, Volume II, CRC Press, 253-277.

80. Mayer R. J., Menzel C. P., Painter M. K., de Witte P. S., et al. Information Integration For Concurrent Engineering (IICE). IDEF3 Process Description Capture Method Report. Wright

81. Patterson Air Force Base, Ohio: Air Force Materiel Command, 1995.

82. National Institute of Standards and Technology Integration Definition For Function Modeling (IDEFO). Washington: Draft Federal Information, 1993

83. Potvin, J.-Y., and Rousseau, J.-M., 1995, "An Exchange Heuristic for Routeing Problems with Time Windows", Journal of Operational Research Society, 46(12), pp 1433 1446.

84. Pullen, H., and Webb, M., 1967, "A Computer Application to a Transport Scheduling Problem", Journal of Computing, 10, pp 10 — 13.

85. Rechenberg I. Evolutionsstrategie: Optimierung Technischer Systeme nach Prinzipien der Biologischen Evolution. Werkstatt Bionik und Evolutionstechnik, Stuttgart: Frommann-Holzboog, 1973.

86. Rice Michael. Computational Intelligence Algorithms for Optimized Vehicle Routing Applications in Geographic Information Systems.

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

88. Savelsbergh, M.W.P., 1984, "Local Search for Routing Problem with Time Windows", Annals of Operations Research, 4, pp 285 ~ 305.

89. Savelsbergh M. W. P. The General Pickup and Delivery Poblem.

90. Savelsbergh M. W. P. Vehicle Routing and Sheduling.

91. Savelsbergh M. W. P. Decision Support for Vendor Managed Inventory Replenishment.

92. Schwefel H. P. Numerische Optimierung von Computer-Modellen mittels der Evolutionsstrategie II Interdisciplinary Systems Research 1977. Vol.26.

93. Shaw, K.J., and Fleming, P.J., 1996, "An Initial Study of Practical Multi-Objective Production Scheduling using Genetic Algorithm", Proceedings of International Conference on Control, 1, pp 479 484.

94. Solomon, M.M., 1987, "Algorithm for the Vehicle Routing and Scheduling Problems with Time Window Constraints", Operations Research, 3-5(2), pp 254 --265.

95. Solomon, M.M., and Desrosiers, J., 1988, "Time Window Constrained Routing and Scheduling Problem"s", Transportation Science, 22(1), pp 1 — 13.

96. Sprague Ralph H., Jr. A Framework for the Development of Decision Support Systems

97. Thangiah, S.R., 1995, "Vehicle Routing with Time Windows using Genetic Algorithms", in L. Chambers, (ed), Practical Handbook of Genetic Algorithms: New Frontiers, II, pp 253 — 277.

98. Thangiah, S.R., Osman, I.H, and Sun, Т., 1995, "Metaheuristics for the Vehicle Routing Problems with Time Windows", Research Report No:UKC/IMS/OR94/8, Institute of Mathematics and Statistics, University of Kent, Canterbury.

99. Vacca J., Andrews D. BPR tools help you work smarter // BYTE, Oct. 1994.

100. Whitley D.L. Genetic Algorithms and Evolutionary Computing. Van Nostrand's Scientific Encyclopedia 2002.

101. Адлер Ю. Восемь принципов, которые меняют мир. /Электронный ресурс. / Режим доступа: http://www.bizoffice.ru, свободный. — Загл. с экрана. — Яз. рус.

102. Балахонова И., Волчков С. Современные стандарты управления в России. /Электронный ресурс. / Режим доступа: http://www.e-xecutive.ru, свободный. — Загл. с экрана. — Яз. рус.

103. Булат Яминов. Генетические алгоритмы. /Электронный ресурс. / -Режим доступа: http://rain.ifmo.ru/cat/view.php/theory, свободный. — Загл. с экрана. —Яз. рус.

104. Гиматов М. "Пирамида сущностей реинжиниринга". /Электронный ресурс. / Режим доступа: http://www.executive.ru/publications/aspects/article1601, свободный. — Загл. с экрана. — Яз. рус.

105. Гончару к В. А. Реинжиниринг: бизнес-процессы или зоны ответственности? /Электронный ресурс. / Режим доступа: http://www.goncharuk.ru/process.htm, свободный. — Загл. с экрана. — Яз. рус.

106. Григорьев Л.Ю. Шкала зрелости» и совершенствование проце'ссов компании. /Электронный ресурс. / Режим доступа: http://www.big.spb.rn, свободный. — Загл. с экрана. — Яз. рус.

107. Григорьев Л.Ю. "Orgware" новый класс программ для управления организацией. /Электронный ресурс. / - Режим доступа: http://www.big.spb.ru, свободный. — Загл. с экрана. — Яз. рус.

108. Ковалев С.М. Применение технологий бизнес-моделирования повышает эффективность совершенствования деятельности организации. /Электронный ресурс. / Режим доступа: http://www.betec.ru/index.php?id:=6&sid=02, свободный. — Загл. с экрана. — Яз. рус.

109. Новиков М.В. IDEF0 в моделировании бизнес-процессов управления. /Электронный ресурс. / Режим доступа: http://www.bkg.ru/cgi-bin/articledetail.pl?id=500, свободный. — Загл. с экрана. — Яз. рус.

110. Рубцов С. В. Какой CASE-инструмент нанесет наименьший вред организации? /Электронный ресурс. / Режим доступа: http://www.osp.ru/text/302/172005, свободный. — Загл. с экрана. — Яз. рус.

111. Рубцов, C.B. Сравнительный анализ и выбор средств инструментальной поддержки организационного проектирования и реинжиниринга бизнес процессов. /Электронный ресурс. / Режим доступа: http://or-rsv.narod.ru, свободный. — Загл. с экрана. — Яз. рус.

112. David Applegate, Robert Bixby, Vaselc Chvâtal, and William Cook. Traveling Salesman Problem. /Электронный ресурс. / Режим доступа: http://www.tsp.gatech.edu, свободный. — Загл. с экрана. — Яз. англ.

113. Konstantin Boukreev. Genetic Algorithms and the Traveling Salesman Problem by Konstantin Boukreev. /Электронный ресурс. / Режим доступа: http://lib.training.ru/Lib, свободный. —Загл. с экрана. —Яз. англ.

114. Traveling salesman problem. Программа решения задачи коммивояжера. /Электронный ресурс. / Режим доступа: http://www-neos.mcs.anl.gov/neos/solvers/CO:CONCORDE, свободный. — Загл. с экрана. — Яз. англ.

115. Yuri Burger. Эволюционные вычисления. /Электронный ресурс. / -Режим доступа: http://www.codenet.ru, свободный. — Загл. с экрана. —Яз. англ.