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

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

00345 шиь ТАРАСОВА Виктория Андреевна

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

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

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

О 6 НОЯ 2000

Уфа 2008

003451606

Работа выполнена в ГОУ ВПО «Уфимский государственный авиационный технический университет» на кафедре вычислительной техники и защиты информации

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

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

д-р техн. наук, проф. Гузаиров Мурат Бакеевич

д-р техн. наук, доц. Валеева Аида Фаритовна

д-р техн. наук, доц. Михеева Татьяна Ивановна

Ведущая организация ГОУ ВПО «Воронежский государственный технический университет»

Защита состоится 2008 г. в ^0 часов

на заседании диссертационного совета Д-212.288.03 при Уфимском государственном авиационном техническом университете по адресу: 450000, Уфа - центр, ул. К.Маркса 12, УГАТУ

С диссертацией можно ознакомиться в библиотеке университета Автореферат разослан $ 2008 г.

Ученый секретарь диссертационного совета д-р техн. наук, проф. ' ' I С В.В. Миронов

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

Актуальность темы исследования

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

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

Движение материальных ценностей в интегрированной цепи поставок, осуществляемых в рамках производственно-строительного комплекса, представляет собой один из важных процессов строительства сложных объектов. Интегрированная цепь поставок является основой транспортной логистики. В свою очередь она состоит из внешних и внутренних составляющих. Внешние соответствуют поставкам материальных ресурсов (МР) и комплектующих, а так же готовых изделий от производителя к клиентам (потребителям). Внутренние составляющие отвечают перемещению заделов в производственном цикле. Динамика внутреннего перемещения МР в процессе строительства слаба и может не учитываться. Что касается перемещения готового изделия от производителя к потребителю, то оно реализуется в виртуальном режиме (поставка готового изделия осуществляется документально на месте строительства). В диссертации основное внимание уделено интегрированной цепи поставок сырья и комплектующих от производителей или со складов хранения на строительные объекты. Наряду с поиском оптимальных маршрутов, также важное значение имеют вопросы календарной увязки поставок к началу выполнения строительных работ. Эти вопросы могут решаться в рамках сетевого планирования после выбора оптимальных маршрутов движения транспортных средств.

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

щих в строительной индустрии. Она выпадает из общей концепции интегрированной цепи поставок в связи с особенностью логистических объектов и связей между ними. Уже поэтому логистические системы в строительной индустрии нуждаются в самостоятельной разработке (работы В.Н. Стаханова, Е.П. Жаворонкова и др.). Кроме того, модули логистических систем часто разрабатываются на уровне содержательной постановки, без применения математических моделей и методов оптимизации. Выбор лучших решений делается в настоящее время на основе интуиции. С другой стороны, простое включение неадаптированных оптимизационных моделей и методов не всегда позволяет получить желаемые результаты. Тем самым, разработка логистико-ориентированых методов решения оптимизационных задач с учетом особенностей строительной индустрии является актуальной.

Объект исследования - интегрированная цепь поставок производственно-строительного комплекса. Предмет исследования - логистическая информационная система с оптимизационным ядром.

Цель работы

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

Задачи исследования

Для достижения цели работы поставлены следующие задачи:

1. Предложить концепцию функционирования автоматизированной цепи поставок материальных ресурсов производственно-строительного комплекса, суть которой состоит в разработке моделей и методов решения производственно - ориентированных задач маршрутизации, расписания выполнения поставок и прогнозирования их объема и создания на этой базе оптимизационного ядра (ОЯ) логистической информационной системы (ЛИС) для выбора и решения задач транспортной маршрутизации с использованием экономической информационной системы (ЭИС) промышленно-строительного комплекса.

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

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

4. Оптимизировать функциональную структуру ЛИС с использованием эволюционных метаэвристик.

5. Разработать в структуре ЛИС оптимизационное ядро маршрутов

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

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

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

На защиту выносятся

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

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

3.Метод декомпозиции допустимой сети поставок: представление осговного дерева множеством путей маршрутов.

4. Эволюционные подходы для решения основных задач маршрутизации в процессе поиска лучшего решения: одноточечный и генетический алгоритмы эволюции.

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

Научная новизна результатов

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

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

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

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

5. Разработано оптимизационное ядро ЛИС, в котором происходит управление передвижением материальных ценностей: анализ ситуации на транспортной сети, выбор метода решения и расчет маршрутов.

Практическая значимость и внедрение результатов

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

Апробация работы и публикации

Основные научные и практические результаты диссертационной работы докладывались и обсуждались на следующих конференциях и семинарах: Международной конференции «Computer Science and Information Technologies» (Уфа, 2005, 2007), Зимней школе аспирантов и молодых ученых (Уфа, 2006), Международном форуме Ассоциации строителей России по проблемам автоматизации строительного бизнеса (Москва, 2006), научных семинарах кафедры «вычислительной техники и защиты информации» Уфимского государственного авиационного технического университета. По теме диссертации опубликовало 5 работ, в том числе две из них в рецензируемых журналах из списка ВАК.

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

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

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

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

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

' Пос'татпмкп

Поюк запасов

Логистический —^модуль

Снабжение

Обеспечение

Физическое распределение |

1111ф0рМЛ1|1!0[Ш1.И1

поток

и

11отре6|1тсгш I

Рисунок 1 - Интегрированная цепь поставок ста логистики предприятий строительной индустрии. С одной стороны, она сложна для принятия формальных решений, с другой - обладает спецификой односторонних поставок и комплексного распределения строящихся объектов. Вместе с тем требуются усиления транспортных позиций: выбор оптимальных маршрутов для доставки материалов на строительные площадки. Приобретает чрезвычайно важное значезше требование выполнения работ в заданные сроки, прогнозирование спроса и цены на строительные объекты. Эги факторы порождают появление моделей маршрутизации, расписания и прогнозирования. Наибольшее внимание в работе уделено моделям маршрутизации транспортных средств в рамках одного производственно-строительного комплекса, объекты которого расположены в черте города и его пригородных зон. Она является М'-полной проблемой.

Рассмотрим транспортную сеть, состоящую из т узлов (перекрестков, значимых объектов, тупиков и т.д.) и п звеньев, связывающих пары узлов. Для каждого звена б заданы два вещественных числа: й, и имеющие смысл протяженности звена и времени его прохождения. Для некоторых узлов заданы числа Ь1Ь г=1 ,т, к=1,ц. Если Ьц>(), то в /-ом узле расположен завод или склад, располагающий материалом к-то вида в количестве Ь,к. Если же Ьцс<0, то в /-ом узле расположен строительный объект и его заказ на материал к-го вида составляет Таким образом, для каждого узла г задан ц - мерный вектор. Требуется на сети решить две задачи: составить план перевозки материалов по сети, минимизирующий суммарный пробег транспортного средства и составить лучшее расписание доставки грузов каждому потребителю. Это двухкритериальная многопродуктовая сетевая транспортная модель. Ситуация моделируется на графах Г(У;5). Каждому узлу /=1 ,т сопоставим вершину графа г^ 6 V; звену 5=1,п -ориентированную дугу з-^,). Тогда транспортной сети отвечает ориентированный граф Г (V; У), а дугам приписаны веса с1г и гг Обозначим Т)=((1,,й2, ■■■^г), Т=(1/, 12, ..., Таким образом, задан взвешенный граф Г (V; 5; О; Т). Требуется найти множество маршрутов и количество х5 поставляемого по дугам материала, с минимальными расходами:

= или = (1)

1 я ' I

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

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

У= У„У1,-,Ут> (2)

минимизирующий линейную функцию

У(У)=1Ь<У, (3)

1=1

при ограничениях

= (4)

Переменные у^,г=1,т, названы Л.В. Канторовичем потенциалами. Вначале определяется базисное множество 5 = Известно, что на транспортной сети ему соответствует остовное дерево В с т вершинами и (т—1) дугами. Метод потенциалов опирается на следующее утверждение.

Теорема. Если базисному множеству 5 отвечают одновременно допустимые векторы х(Б) и у (Б), то они являются оптимальными для рассматриваемых двойственных задач, причем значения линейных функций (1) и (3) на этих векторах совпадают.

В главе 2 предложен проект логистической информационной системы (ЛИС). Она предназначена для поддержки управления движением материалопотока по каналам распределения. ЛИС призваны обеспечивать интеграцию различных видов логистической деятельности. Рассматриваются различные уровни информационного обеспечения: цепь операций начинается с поступления генерального заказа в базу данных (БД) системы. Это порождает заказ материалов и комплектующих изделий. Затем следует операция комплектования грузоотправленш. Последняя операция -оформление платежной документации и выставление счетов к оплате.

На рис. 2 изображены потоки логистической информации и схема их движения. Управление и ввод данных - это своего рода интерфейс, через который ЛИС получает информацию из внешних источников. Каналы информационного обмена обеспечивают взаимодействие элементов системы как между собой, так и с внешним миром. Она должна обеспечивать управленческий контроль, анализ решений и интеграцию с другими системами. В том числе с экономической информационной системой (ЭИС). ЭИС делится на подсистемы, они в свою очередь состоят из модулей, в результате выполнения которых формируются те или иные учетные документы. Для описания динамики поступления и перемещения товарно-материальных ценностей (ТМЦ) используются сети Петри. Известны различные ЛИС, ориентированные на конкретные товарно-производственные отношения. Однако даже в крупных системах отсутствуют модули оптимизации. Что касается методов, то они существуют и развиваются, как правило, изолированно от ЛИС. В представленной работе они адаптирова-

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

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

Рисунок 2 - Потоки логистической информации Функциональный цикл физического распределения представлен на рис.3, а. Сплошными стрелками обозначены физические потоки, пунктирными - информационные. Цикл задает структурную основу строительной логистики.

Источник материалов и компонентов

к

Распределительный отдел

Строительный объект

Обработка Передача Заказ

заказа заказа потребителя

к 1 1

Комплект Транспорт Потребитель Строительный объект

заказа

а б

Рисунок 3 - Циклы физического распределения: а - функциональный цикл; б - базовый цикл. Физическое распределение, как основной элемент системы логистики, связывает строительную фирму не только с потребителями, сколько

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

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

Контур управления логистической информационной системой изображен на рис. 4. Он включает оптимизационное ядро, а управляющие воздействия на ЛИС осуществляются менеджером по поставкам.

Маршрутные

л югистичеокая индзормационная сисгема

Оптимизационное ядро

База данньщ.

Логистическии нентр_

Упра ¿г^юидее аоздр^лн"^

Информаци:

1 заказчиков

Иптегрировапная цепь, поставок

Рисунок 4 — Контур управления ЛИС

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

• модуль формирования обобщенного заказа: под обобщенным заказом (о. заказом) понимается набор заявок, подлежащих размещению внутри ТС, он аккумулирует информацию заказчиков об объеме и времени его исполнения;

• модуль выбора транспортных средств (ТС): входные данные уточняются набором имеющихся на данный момент ТС, их геометрическими и техническими параметрами;

• модуль размещения. Учитывая уже выбранное ТС и параметры заказов, рассчитывают карты их размещения в одном или нескольких ТС;

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

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

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

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

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

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

Физическое распределение связано с обслуживанием потребителей и включает в себя обработку заказов каждого из них, формирование обобщенных заказов (о. заказов) с учетом возможностей транспортных средств (ТС) при условии направленности загрузки и выгрузки.

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

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

Базисному допустимому решению задачи отвечает остовное дерево

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

+ р = (5)

где Л^ и - множество дуг, входящих в вершину г и выходящих из нее, а р=(Ъ1,Ьъ..., Ь„) - ассортиментный вектор. Далее требуется вычислить суммарную длину дуг остовного дерева. Однако с учетом количества перевозимого груза по каждой дуге найденное значение целевой функции (1) не всегда является оптимальным. Оптимальному решению соответствует другое покрывающее дерево, которое можно найти с помощью линейного программирования. Если нет особых трудностей в поиске оптимального решения, то они возникают на этапе его реализации. Оказывается необходимым найти совокупность маршрутов, по которым будут передвигаться транспортные средства. Так возникает в сети поставок задача декомпозиции дерева на маршруты. Многие маршруты можно описать с помощью модели коммивояжера. Эта задача представляет поиск дешевого способа обхода множества пунктов с возвращением в исходную вершину. Требуется найти порядок, в котором надо посетить пункты производства и потребления. Эта задача является №>-полной. ТС загружается материалом на складе производителя, затем, следуя по маршруту, оставляет на строительных площадках заказанный материал. После полного обхода клиентов транспорт возвращается на базу.

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

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

Классическая транспортная задача. Постановка задачи приведена выше. При ее решении методом потенциалов осуществляется направленный перебор различных остовных деревьев. Если все компоненты вектора х(3), удовлетворяющего (5), не отрицательные, то оно является допустимым, и переходят ко второму этапу. Если для некоторой компоненты ]о вектора х(8) имеем хк < 0, то дуга ¿-е.? меняет направление на противоположное. Таким образом, получаем остовное дерево £>базисное множество 5" и допустимый вектор х(Б'). Однако полученный план часто оказывается непригодным к реальным условиям и нуждается в корректировке. Мы предлагаем другой путь решения на базе применения эволюционной мета-эвристики. Выше была приведена принципиальная схема двухэтапного

решения этой задачи. Предположим, что на первом этапе получено остов-

ное дерево (О), для которого X достигает минимума. Необходимо

зеВ

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

4

Рисунок 5 - Распределение груза на развилке дорог

На этом рисунке приведен фрагмент решения транспортной задачи. Требуется 180 кг материалов поставить трем потребителям. Из них 30 кг оставить в пункте 2, а остальные 150 кг распределить между пунктами 3 и 4. Без возврата машины это сделать невозможно. Разумнее использовать различные фрагменты 1 —»2—>3 и 1—»2—>4 в двух разных маршрутах.

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

1. Начальный фрагмент. Выбирается дуга одна из вершин которой является исходной. Дуга з0=(и0,]1С) помещается в файл Ф. Вершины 1а]в помещаются в файл В. Если для ^существует дуга у ¡, связывающая ]0= i¡ с некоторой вершиной;'/?Ф, то цепь помещается в файл Ф. Иначе, если такой дуги нет, или весь материал перевезен, то фрагмент является маршрутом и он из Ф перемещается в М.

2. Текущий фрагмент. Фиксируем в Ф первый непустой фрагмент. Пусть это будет: .Уь^+л —Если возможно добавить еще дугу то фрагмент становится как в противном случае он переходит в следующую свободную позицию файла М, а его последняя вершина помещается в файл В.

3. Если В содержит все вершины дерева, то переход на шаг 5, тогда файл Ф содержит все маршруты. Иначе шаг 2 повторяется.

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

5. Конец. Файл М содержит список всех маршрутов. Подсчет суммарного веса маршрутов.

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

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

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

Рисунок 6 - Гистограмма эффективности алгоритма декомпозиции

Эффективность эволюционного метода по сравнению с одноразовым применением декомпозиции остовного дерева составляет 13,6%, а с произвольными маршрутами доходит и до 25%.

В рамках разработки ОЯ системы рассматриваются различные оптимизационные задачи с учетом особенностей строительной индустрии. Задача коммивояжера. На замкнутой сети имеются (п+1) пунктов посещения (п. посещения). В условиях строительной индустрии, это - предприятия, производящие материалы и строительные объекты. Для каждой пары п. посещения i и j задано расстояние dy> О между ними. Коммивояжер находится в п. производства, и возвращается в исходный пункт. Требуется минимизировать транспортные расходы. Маршрут состоит из начального и всех посещаемых пунктов, он может быть задан как z = (0,i),i2,...,i„,0), где г,,г2,...,г'„- перестановка чисел 1,2Длина /(z)

маршрута z равна l{z) = ^ d.^; iQ = = 0.

Пусть Z - множество всех маршрутов. Тогда |Z| = и/. Необходимо найти маршрут z0 £ Z такой, что Z(z0) = min/(z),z е Z. Для решения этой задачи применяется метод ветвей и границ или эволюционная метаэвристика.

Задачи расписания. Строительство крупных объектов требует календарной увязки большого числа взаимосвязанных работ. Составление и анализ соответствующих календарных планов представляет весьма сложную задачу, при решении которой применяются методы сетевого планирования. Получение заказанного материала (комплектующих) «точно в назначенное время назначенного дня» - будущее логистики, которое частично обеспечивается в рамках сетевого графика по системе JIT «точно вовремя» (just in timeJ. Это становится возможным, благодаря решению двойственных задач сетевого планирования на транспортной сети.

Пусть рассматриваемый график перевозок описывается орграфом Г (т, п, S), обладающим заданными свойствами. Кроме того, известно время (его математическое ожидание) гs пробега каждого звена i = 1 ,п.

В этом случае говорят, что имеется сетевой график Г (т, п, S;T), где Т = {rs}, s = Двойственные задачи сетевого планирования формулируются следующим образом.

Задача о кратчайшем сроке (КС). При заданном сетевом графике Г= (т, п, S;Т) определить вектор f=(i/,i2,...im), минимизирующий линейную функцию

А(0 = (6)

при ограничениях

= (7)

Задача о критическом пути (КП). При исходных данных задачи о кратчайшем сроке определить «-мерный вектор х = (хи х2, .... х„), xs >0, 5 = 1 ,и, максимизирующий линейную функцию

= Ьл (8)

при ограничениях:

-1 npui = 1,

(9)

0 при! = 2 ,т-

1 приЫт

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

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

Эти величины удовлетворяют следующим соотношениям:

= '< =шахС = С f = ¿ = ^-1(10)

где Р* и Pi - множества путей, входящих в вершину г и выходящих из вершины 10=1. При этом t,G0 = Что касается остальных вершин i = 2, m -1, то для них имеют место неравенства

(11)

При этом неотрицательные величины

(i2)

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

Событие i сетевого графика T(m,n,S ;Т) называется критическим, если неравенство (11) выполняется как равенство, т.е. резерв времени для этого события равен 0.

Для практического вычисления величины t° и tf' на каждом просмотре применяются соотношения следующего вида:

tjs - тах {tj„ tis + rj; t is = min {tis, tjs - zj, (13)

где t'ß, t^ - ранние и поздние сроки наступления событий при очередном просмотре дуг. Если при просмотре всех дуг не происходит ни одного изменения величин то это означает, что полученные совпадают с искомыми величинами (10).

В конце главы описывается оптимизационное ядро ЛИС. Оно выполняет функции формирования транспортных маршрутов. Его структурное и функциональное наполнение изображены на рис. 7.

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

Рисунок 7 - Оптимизационное ядро ЛИС

В таблице 1 приведены критерии выбора моделей и методов решения

на различных уровнях анализа входной информации.

Таблица 1 - Анализ ситуаций: выбор модели и метода решения в ОЯ

Уровень анализа Назначение анализа Критерии выбора модели (метода решения)

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

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

3 Выбор метода решения (1-ый уровень оптимизации) Критерием выбора точного или эвристического метода являются: размерность задачи (количество узлов сети) и цеца перевозимого продукта. Предпочтение -метаэвристикам.

4 Вычисление рациональных маршрутов (2-ой уровень оптимизации) Анализ выхода на уровне 3: если построено остовное дерево, то его декомпозиция. Если построены маршруты на сети, то выбор лучшего. В случае решения задачи коммивояжера для зональной консолидированной модели - синтез маршрутов и.т.д.

5 Формирование маршрутного листка По требованию

В главе рассмотрены особенности ПО ЛИС в рамках концепции открытых программных систем.

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

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

В ходе работы над диссертацией получены следующие результаты:

1. Предложена концепция автоматизированной цепи поставок материальных ресурсов производственно-строительного комплекса. Она включает разработку «логистической информационной системы» (ЛИС) строительной компании во взаимодействии с «экономической информационной системой» товарно-материальных ценностей (ЭИС ТМЦ), в составе которых функционирует оптимизационное ядро для принятия рациональных решений в рамках сети транспортных маршрутов.

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

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

3. Рассмотрены различные ситуации поставок: один производитель -один клиент, один производитель - несколько клиентов, однородный груз и консолидированный груз, несколько поставщиков - один клиент и несколько клиентов, ситуация «обобщенного заказа», потребности в транспортных средствах (одно или несколько ТС, его габариты) и т.д.. На основе анализа ситуаций модифицированы алгоритмы маршрутизации и принято решение о разработке нового алгоритма декомпозиции маршрутов, отличающегося от известных лучшими показателями эффективности. Алгоритм декомпозиции улучшил показатель протяженности маршрутов и время их расчетов на 15% -25% по сравнению с традиционными методами.

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ Публикации в рецензируемых журналах из списка ВАК:

1. Моделирование транспортной сети поставок в строительной индустрии / М.Б. Гузаиров, В.А.Тарасова // Вестник УГАТУ: науч. журн. Уфимск. гос. авиац. техн. ун-та. Серия Управление, вычислительная техника и информатика. 2008. TIO. № 2(27). С.58-63.

2. Оптимизация транспортных потоков в сети поставок строительных материалов / М.Б. Гузаиров, ВЛ.Тарасова // Системы управления и информационные технологии, 2008. 3.1(33). С. 108-112.

Другие публикации:

3. Автоматизация управления движением товарно-материальных ценностей в строительной компании / В.А. Тарасова // Интеллектуальные системы обработки информации и управления : сб. статей per. зимн. шк.-сем. аспирантов и молодых ученых. Уфа : Технология, 2006. С.246-248.

4. Экономическая информационная система для предприятий строительной индустрии / В.А. Тарасова // Компьютерные науки и информационные технологии (CSIT 2007) : матер. 7-й Междунар. конф. Уфа, Россия, 2007. С.212-214. (Статья на англ. яз.).

5. Экономическая информационная система управления движением товарно-материальных ценностей в строительной компании / В.А.Тарасова // Башкирско-Саксонский форум. Уфа, Россия, 2007. С. 63-67. (Статья на англ. яз.). / /?/

у/ ¿Sf

Диссертант ~~ В.А.Тарасова

ТАРАСОВА Виктория Андреевна

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

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

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

Подписано к печати 20.10.2008. Формат 60x84 1/16. Бумага офсетная. Печать плоская. Гарнитура Тайме. Усл. печ. л. 1,0. Усл. кр. - отг. 1,0. Уч.-изд. л. 0,9. Тираж 100 экз. Заказ № 457.

ГОУ ВПО Уфимский государственный авиационный технический университет Центр оперативной полиграфии 450000, Уфа-центр, ул. К.МарксаД2

ПРИЛОЖЕНИЕ (акты внедрения).

1. ЛОГИСТИКА: УПРАВЛЕНИЕ ЦЕПЬЮ ПОСТАВОК.

1.1. Логистика как научная дисциплина сфер производственно-хозяйственной деятельности.

1.2. Транспортная логистика.

1.2.1. Транспортная инфраструктура.

1.2.2. Управление транспортировкой.

1.2.3. Основная модель транспортной логистики.

2. ЛОГИСТИЧЕСКАЯ ИНФОРМАЦИОННАЯ СИСТЕМА.

2.1. Логистическая информация: назначение и принципы организации.

2.2. Структура логистической информационной системы.

2.3. Система управления движением товарно-материальных ценностей.

2.3.1. Концепция разработки ЭИС.

2.3.2. Динамическая модель процесса поступления и перемещения ТМЦ.

2.4. Концепция функционального цикла поставок в строительной индустрии. Выводы по главе 2.

3. ОСНОВНЫЕ ЗАДАЧИ ЛОГИСТИКИ СТРОИТЕЛЬНОЙ ИНДУСТРИИ.

3.1. Интеграция цепи поставок в строительной индустрии.

3.2. Прогнозирование спроса в логистической среде строительных компаний.

3.3. Оптимизационные проблемы транспортной логистики.

3.3.1. Однопродуктовая сетевая транспортная задача.

3.3.2. Транспортировка консолидированных грузов.

3.3.3. Задача о кратчайшем пути.

3.3.4. Задача коммивояжера.

3.3.5. Максимальные потоки в сети. Выводы по главе 3.

4. ОПТИМИЗАЦИОННЫЕ МОДЕЛИ И МЕТОДЫ ТРАНСПОРТНОЙ ЛОГИСТИКИ В СТРОИТЕЛЬНОЙ ИНДУСТРИИ.

4.1. Управление транспортировкой: основные экономические факторы.

4.2. Оптимизация транспортных потоков в сети поставок строительных материалов.

4.2.1. Постановка основной задачи маршрутизации.

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

4.2.3. Упрощенная модель сетевой транспортной задачи.

4.2.5. Методы решения задачи коммивояжера.

4.3. Задачи сетевого планирования.

4.3.1. Понятие о сетевом графике.

4.3.2. Экстремальные задачи сетевого графика.

4.4. Подсистема управления формированием транспортных маршрутов. Выводы по главе 4.

1. ЛОГИСТИКА: УПРАВЛЕНИЕ ЦЕПЬЮ ПОСТАВОК.12

1.1. Логистика как научная дисциплина сфер производственно-хозяйственной деятельности.12

1.2. Транспортная логистика.17

1.2.1. Транспортная инфраструктура.17

1.2.2. Управление транспортировкой.21

1.2.3. Основная модель транспортной логистики.27

2. ЛОГИСТИЧЕСКАЯ ИНФОРМАЦИОННАЯ СИСТЕМА.34

2.1. Логистическая информация: назначение и принципы организации.34

2.2. Структура логистической информационной системы.37

2.3. Система управления движением товарно-материальных ценностей.42

2.3.1. Концепция разработки ЭИС.43

2.3.2. Динамическая модель процесса поступления и перемещения ТМЦ .44

2.4. Концепция функционального цикла поставок в строительной индустрии.50

Выводы по главе 2.56

3. ОСНОВНЫЕ ЗАДАЧИ ЛОГИСТИКИ СТРОИТЕЛЬНОЙ ИНДУСТРИИ.58

3.1. Интеграция цепи поставок в строительной индустрии.59

3.2. Прогнозирование спроса в логистической среде строительных компаний.62

3.3. Оптимизационные проблемы транспортной логистики.67

3.3.1. Однопродуктовая сетевая транспортная задача.67

3.3.2. Транспортировка консолидированных грузов.71

3.3.3. Задача о кратчайшем пути.73

3.3.4. Задача коммивояжера.75

3.3.5. Максимальные потоки в сети.75

Выводы по главе 3.76

4. ОПТИМИЗАЦИОННЫЕ МОДЕЛИ И МЕТОДЫ ТРАНСПОРТНОЙ ЛОГИСТИКИ В СТРОИТЕЛЬНОЙ ИНДУСТРИИ.77

4.1. Управление транспортировкой: основные экономические факторы.77

4.2. Оптимизация транспортных потоков в сети поставок строительных материалов.79

4.2.1. Постановка основной задачи маршрутизации.80

4.2.2. Метод потенциалов для решения однопродуктовой транспортной задачи.83

4.2.3. Упрощенная модель сетевой транспортной задачи.85

4.2.5. Методы решения задачи коммивояжера.94

4.3. Задачи сетевого планирования.98

4.3.1. Понятие о сетевом графике.99

4.3.2. Экстремальные задачи сетевого графика.99

4.4. Подсистема управления формированием транспортных маршрутов. 104

Выводы по главе 4.108

ЗАКЛЮЧЕНИЕ.110

ЛИТЕРАТУРА.112

ПРИЛОЖЕНИЕ (акты внедрения)

ВВЕДЕНИЕ

Актуальность темы исследования

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

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

Движение материальных ценностей в интегрированной цепи поставок, осуществляемых в рамках производственно-строительного комплекса, представляет собой один из важных процессов строительства сложных объектов. Интегрированная цепь поставок является основой транспортной логистики. В свою очередь она состоит из внешних и внутренних составляющих. Внешние соответствуют поставкам материальных ресурсов (MP) и комплектующих, а так же готовых изделий от производителя к клиентам (потребителям). Внутренние составляющие отвечают перемещению заделов в производственном цикле. Динамика внутреннего перемещения MP в-процессе строительства слаба и может не учитываться. Что касается перемещения готового изделия от производителя к потребителю, то оно реализуется в виртуальном режиме (поставка готового изделия осуществляется документально на месте строительства). В диссертации основное внимание уделено интегрированной цепи поставок сырья и комплектующих от производителей или со складов хранения на строительные объекты. Наряду с поиском оптимальных маршрутов, также важное значение имеют вопросы календарной увязки поставок к началу выполнения строительных работ. Эти вопросы могут решаться в рамках сетевого планирования после выбора оптимальных маршрутов движения транспортных средств.

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

Объект исследования - интегрированная цепь поставок производственно-строительного комплекса. Предмет исследования -логистическая информационная система с оптимизационным ядром.

Цель работы

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

Задачи исследования

Для достижения цели работы поставлены следующие задачи:

1. Предложить концепцию функционирования автоматизированной цепи поставок материальных ресурсов производственно-строительного комплекса, суть которой состоит в разработке моделей и методов решения производственно - ориентированных задач маршрутизации, расписания выполнения поставок и прогнозирования их объема и создания на этой базе оптимизационного ядра (ОЯ) логистической информационной системы (ЛИС) для выбора и решения задач транспортной маршрутизации с использованием экономической информационной системы (ЭИС) промышленно-строительного комплекса.

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

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

4. Оптимизировать функциональную структуру ЛИС с использованием эволюционных метаэвристик.

5. Разработать в структуре ЛИС оптимизационное ядро маршрутов движения товарно-материальных ценностей для обеспечения производственно- строительной компании.

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

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

На защиту выносятся

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

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

3.Метод декомпозиции допустимой сети поставок: представление ос-товного дерева множеством путей маршрутов.

4. Эволюционные подходы для решения основных задач маршрутизации в процессе поиска лучшего решения: одноточечный и генетический алгоритмы эволюции.

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

Научная новизна результатов

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

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

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

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

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

Практическая значимость и внедрение результатов

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

Структура работы

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

Выводы по главе 4

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

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

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

ЗАКЛЮЧЕНИЕ

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

В ходе работы над диссертацией получены следующие результаты:

1. Предложена концепция автоматизированной цепи поставок материальных ресурсов производственно-строительного комплекса. Она включает разработку «логистической информационной системы» (ЛИС) строительной компании во взаимодействии с «экономической; информационной системой» товарно-материальных ценностей (ЭИС ТМЦ), в составе которых функционирует оптимизационное ядро для принятия рациональных решений в рамках сети транспортных маршрутов.

2. Проведен анализ транспортных маршрутов с учетом ситуаций, возi никающих при поставке материальных ресурсов на строящихся объектах. На основании результатов этого анализа предложено несколько логистико-ориентированных моделей оптимизации маршрутов и подходов для решения соответствующих задач. Это общая задача маршрутизации и ее частные случаи: однопродуктовая и многопродуктовая транспортные задачи, задача! коммивояжера, задача о кратчайшем пути и задача о расписании прохождения через пункты потребления.

3. Рассмотрены различные ситуации поставок: один производитель -один клиент, один производитель - несколько клиентов, однородный груз и консолидированный груз, несколько поставщиков - один клиент и несколько клиентов, ситуация «обобщенного заказа», потребности в транспортных средствах (одно или несколько ТС, его габариты) и т.д. На основе анализа ситуаций модифицированы алгоритмы маршрутизации и принято решение о разработке нового алгоритма декомпозиции маршрутов, отличающегося от известных лучшими показателями эффективности. Алгоритм декомпозиции улучшил показатель протяженности маршрутов и время их расчетов на 15% -25% по сравнению с традиционными методами.

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

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

1. Автоматизированные информационные технологии в экономике / под ред. Титоренко Г.А. М.: ЮНИТИ. 2005. 399с.

2. Андреев В.В. Мультиагентный конструктор и планировщик транспортных сетей // Андреев М.В., Батищев С.В. и др. Тр. VI Международной конференции по проблемам управления и моделирования сложных систем. Самара СНЦ РАН. 2004. С.254 259. !

3. Архипов А.В. Обобщенная задача оперативного планирования работ в производственно-логистических сетях // Иванов Д.А. Информационные технологии. 2005. № 3. С.63 69.

4. Бауэрсокс Д. Логистика. Интегрированная цепь поставок / Д.Д. Клосс. М.: Олимп-Бизнес. 2006. 640с.

5. Бизнес и логистика// Сборник материалов Московского логистического форума. Москва. 2001. 202 с.

6. Бочкарев А.А. Планирование и моделирование цепи поставок / М.: Альфа-Пресс. 2008. 192с.

7. Беспалов Р.С. Транспортная логистика / М.: Вершина. 2007. 384с. j

8. Мерфи П.Р. Современная логистика / М.: Вильяме. 2005. 624с.

9. Ветлугин М.Д. Основы логистики производства / М.: ВИПК Госснаба СССР.1991. 387 с.

10. Гордон М.П. Развитие логистики в управлении материально-техническом снабжении / М.:ЦНИИТЭИМС. 1990. 268 с.

11. Гузаиров М.Б. Оптимизация транспортных потоков в сети поставок строительных материалов / Тарасова В. А. // Системы управления и информационные технологии, 2008. 3.1(33). С. 108-112.

12. Гузаиров М.Б. Моделирование транспортной сети поставок в| строительной индустрии // Тарасова В.А. Уфа: Вестник УГАТУ.2008. Т10. №; 2(27). С.111-115.

13. Жаворонков Е.П. Маркетинг и логистика в строительстве/Учебное пособие. Новосибирск СГАПС.1996. 346 с.

14. Жаворонков Е.П. Логистика в строительстве / Щербаков А.И. Учебное пособие. Новосибирск: СГАПС.1996. 288 с.

15. ЗалмановаМ.Е. Производственно-коммерческая логистика/Учебное пособие. Саратов: Саратовский гос. техн. ун-т. 1995. 269 с.

16. Ивушкин К.В. Транспортная логистика на основе мультиагентных систем// Минаков И.А. Системная логистика и центр консолидации грузопотоков на международных трассах: матер. I Междунар. научн. практ. конфер. Самара.;2001. Вып.1.С.120-129.

17. Информационные технологии управления/ Учебное пособие для вузов. Под редакцией Титоренко Г.А. М.: ЮНИТИ-ДАНА.2004.377 с.

18. Информационные проблемы транспортной логистики // Сб. материалов международного семинара. СПб. Хельсинки: Ассоциация Северо-Запад. 1997. 215 с.

19. Канторович Л.В. Математические методы организации и планирования производства/Ленинград: издательство ЛГУ. 1939. 68с.

20. Лебедев Ю.Г. Логистика: Теория гармонизированных цепей поставок/ М.: МГТУ им. Н.Э. Баумана.2005. 159 с.

21. Лучинский B.C. Модели и методы теории логистики/ С.-Петербург: ПИТЕР.2008. 447с.

22. Логистическая организация капитального строительства / под. ред. Стаханова В.Н. Ростов-на-Дону: РГСУ. 1998. 209 с.

23. Минаков И.А. Система нахождения бизнес правил типа «if-then» в задачах транспортной логистики // Вольман С.И. Информационные технологии. 2007. № 12.С.35-43.

24. Мухачева Э.А. Математическое программирование/ Рубинштейн Г.Ш. Новосибирск: Наука. 1987. 226с.

25. Никифоров ' B.C. Мультимодальные перевозки и транспортная логистика/ М:ТрансЛит. 2007. 272с.

26. Никулина Н.О. Применение аппарата сетей Петри для проектирования информационных систем: Лабораторный практикум // Федорова Н.И. Уфа: УГАТУ.2005. 29с.

27. Норенков И.П. Генетический метод структурного синтеза на1 альтернативных деревьях// Информационные технологии. 1996. №1. С.19 30.

28. Норенков И.П. Эвристики и их комбинации в генетических методах дискретной оптимизации// Информационные технологии. 1999.№ 1. С.2 7.

29. Норенков И.П. Методы оптимизации в задачах концептуального проектирования и логистики// Информационные технологии.2000. №9. С.8 15.

30. Отраслевая методика определения экономической эффективности АСУП //М.: НИИ Экономики. 1982.-25с.

31. Панкратьев Е.В. Алгоритмы и методы решения задач составления расписаний и других экстремальных задач на графах больших размерностей// Чеповский A.M. М.: Фундаментальная и прикладная математика.2003. Том 9. №1.С.235 251.

32. Панкратьев Е.В. Нахождение наборов оптимальных маршрутов на больших сетях дорог геоинформационных систем// Чеповский A.M. Проблемы передачи и обработки информации в сетях и системах телекоммуникаций:

33. Материалы 10-й Международной начно-практической конференции. Рязань: Рязанская государственная радио-техническая академия. 2001. С.240 243.

34. Стаханов В.Н. Логистика в строительстве/ Ивакин Е.К. Ростов-на-Дону: РГСУ.1997. 212 с.

35. Тарасова В.А. Экономическая информационная система для предприятий строительной индустрии // Компьютерные науки и информационные технологии (CSIT 2007): матер. 7-й Междунар.конф. Уфа, Россия, 2007. С.212-214. (Статья на англ. яз.).

36. Тарасова В.А. Экономическая информационная система управления движением товарно-материальных ценностей в строительной компании // Башкирско-Саксонский форум. Уфа, Россия, 2007.С. 63 67. (Статья на англ. яз.).

37. Управление цепями поставок/ под ред.В.И.Сергеева. М.: Инфра-М. 2007.704с.

38. Филиппова А.С. Моделирование эволюционных алгоритмов решения задач прямоугольной упаковки на базе блочных структур// Информационные технологии.2006. №6. Приложение. 31с.

39. Филиппова А.С. Мультиметодный генетический алгоритм решения; задач ортогональной упаковки// Валиахметова Ю.И. Информационные технологии.2007. №12. С.50-57.

40. Форд Л.Р. Потоки в сетях. / Фалкерсон В.Р. М.: Мир. 1965. 235 с.

41. Ху. Т.Ч. Комбинаторные алгоритмы/ Шинг М.Т. Нижний Новгород: Нижегород. государ. ун-т. 2004. 330с.

42. Хэссинг К. Информационная логистика и менеджмент потока работ / Арнольд М. www.integprog.ru.

43. Шейхтер Д. Логистика. Искусство управления цепочками поставок /Сандер Г. М.: Претекст.2008. 240с.

44. Aurts Е. Local Search in Combinatorial Optimization // Lenstra J., edit. John Wiley&Sons. 1996. P. 36 43.

45. Anscomble J. The Fourth Wave of Logistics Improvement // Logistics Focus.1994.P.36 — 40.

46. Baptiste P. Disjunctive Constraints for Manufacturing Scheduling Principles and Extensions / ILOG. http://www.ilog.com

47. Browersox D.J. Wold Class Logistics // Daugherty P.J. Oak Brook, IL: Council of Logistics Management. 1995. 345 p.

48. Brown T. Private Trucking Since Deregulation //Private Carrier. 1996. P. 16 -21,32.

49. Cavinato I. A Total Cost/Value Model for Supply Chain Competitiveness// Journal of Business Logistics. 1992. P.255 301.

50. Cooper M.C. Meshing Multiple Alliances // L.M. Ellram and all. Journal of Business Logistics. 1997. P.67 90.

51. Dowe R.L. An Investigation of the Pace and Determinants of information Technology Use in the Manufacturing Materials// Business Logistics, Fall. 1994. P.229 -259.

52. Ferrin B. Planning Just- in- Time Supply Operations: A Multiple-Case Analisis // Journal of Business Logistics. 1994.P.53-69.

53. Gibson B.J. Shipper-Carrier Relationships and Carrier Selection Criteria // H.L. Sink, R.A. Mundy. Logistics and Transportation Review. 1993.P.371 -382.

54. Hymdman R.J. Nonparametric additive regression models for binary time series//MonashUniversity.http://www.personal.buseco.monash.edu.au/ Hyndman/papers/logitar.pdf

55. Jones D.T. Lean Logistics // P.Hines, N.Rich. International Journal of Physical Distribution and Management. 1997. P. 153 173.

56. Kreaton M. Economics of Density and the Less-than-Truckload Motor Carrier Industry Since Deregulation // Journal of the Transportation Research Forum. 1997.P. 269-278.

57. Kent J. Perspectives on the Evolution of Logistics Thought // Journal of Business Logistics. 1997.P. 15 29.

58. Lynagh P.M! Career-Related Perspectives of Women in Logistics: A Comparative Analyses // P.R. Murphy, R.F. Poist. Transportation Journal. 1996. P.35 -42.

59. Murphy P.R. Educational Strategies for Succeeding in Logistics: A Corporative Analysis.// R.F. Poist. Transportation Journal. 1996. P.36 48.

60. Nelson R.S. The traffic manager: How Is He (or She) Doing Today? // D.F. Wood. Proceedings of the 35th Annual Meeting of the Transportation Research Forum. 1997.P. 155 173.i

61. Ogden H.J. Customer Satisfaction with Delivery Scheduling // R.E. Turner. Journal of Marketing Theory and Practice, Spring 1996.P.79 88.

62. Stark T.P. The Impact of Information on Supplier Performance// Journal of Marketing Theory and Practice. Full. 1996. P.94 105.

63. Thorup M. Underected single-source shortest paths with positive integer weights in linear time // Journal of the ACV.1999. Vol.46 №.3. P.362 394.

64. Turner G. Solving the Reverse Logistics Problem: Applying the Symbiotic Logistics Concept // Journal of Marketing Theory and Practice. Spring 1994.P.15 27.

65. Windle R. Productivity Measurement in Transportation Industries A Summary // Produccedings, 35th Meeting of the Transportation Research Forum, 1993.P.141 148.