Содержание к диссертации
Введение
1.1 Анализ предприятия и производственной ситуации 10
1.2 Организационная реструктуризация существующего бизнес-процесса доставки материалов 21
1.3 Анализ методов оптимизации транспортных маршрутов 25
1.3.1 Введение 25
1.3.2 Постановка задачи коммивояжера 26
1.3.3 Жадный алгоритм 29
1.3.4 Деревянный алгоритм 30
1.3.5 Метод ветвей и границ 32
1.3.6 Алгоритм Дейкстры 38
1.3.7 Генетические алгоритмы 41
1.3.7.1 Общие сведения 41
1.3.7.2 Классический генетический алгоритм 42
1.3.7.3 Функция приспособленности и кодирование решений 42
1.3.7.4 Алгоритм работы 44
1.3.7.5 Факторы, создающие сложность для ГА 47
1.3.7.6 Решение задачи коммивояжера генетическими алгоритмами 49
1.3.8 Анализ методов решения задачи коммивояжера 55
1.4 Анализ имеющихся программных средств оптимизации и
планирования транспортных маршрутов 56
1.4.1 Цель и назначение автоматизированного варианта решения задачи.. ..56
1.4.2 Общая характеристика организации решения задачи на ЭВМ 57
1.4.3 Анализ существующих программных разработок 58
1.5 Выводы 61
2 ТЕОРЕТИЧЕСКАЯ МОДЕЛЬ СИСТЕМЫ, РАЗРАБОТКА МОДЕЛИ И АЛГОРИТМА ОПТИМИЗАЦИИ ПРОЕКТИРУЕМОЙ СИСТЕМЫ 63
2.1 Модели маршрутизации -.. 63
2.2 Математическая формулировка метода оптимизации 68
2.3 Обоснование выбора модели маршрутизации 77
№ 2.4 Сравнение эффективности подходов 80
Вывод 83
3 ПРОЕКТИРОВАНИЕ СИСТЕМЫ ОПТИМИЗАЦИИ ВНУТРИЗАВОДСКИХ ТРАНСПОРТНЫХ МАРШРУТОВ 84
3.1 Выбор технологии проектирования „ . 84
3.2 Структура разрабатываемой системы маршрутизации 86
3.3 База данных 87
3.4 Источники данных системы 88
3.5 Проектирование базы данных 90
3.6 Системы оптимизации загрузки 97
Вывод 98
4 РАЗРАБОТКА ПРОГРАММНОГО ПРОДУКТА 99
4.1 Структура программного продукта 99
4.2 Описание работы с программой 99
4.3 Программное обеспечение 102
ЗАКЛЮЧЕНИЕ 106
Список использованных источников 107
Приложение «А» Организационная структура Центра обеспечения материалами 117
Приложение «Б» Функциональные схемы процесса 11.8
Приложение «В» Интерфейсы программных средств маршрутизации 123
Приложение «Г» Проектирование системы и модели маршрутизации 127
Приложение «Д» Системы оптимизации загрузки транспортных средств 129
Приложение «Е» Геоинформационные системы 130
Приложение «Ж» Проектирование базы данных 132
Приложение «И» Интерфейс разработанной программы 139
Список авторских публикаций 142
- Организационная реструктуризация существующего бизнес-процесса доставки материалов
- Модели маршрутизации
- Выбор технологии проектирования „
- Структура программного продукта
Введение к работе
Актуальность работы
В настоящий момент на большинстве крупных машиностроительных предприятий сложилась ситуация нехватки транспорта для осуществления грузоперевозок, из-за того, что транспортные маршруты планируются не оптимально, и как следствие этого, из-за нехватки самого транспорта. Выход может быть найден в принятии оптимальных организационно-технических решений, в частности с использованием информационных технологий, позволяющих освободить человека от рутинных интеллектуальных операций и переключить внимание на творческие задачи принятия решений.
Существующие методы оптимизации транспортных маршрутов преимущественно основаны на полном, либо частичном переборе возможных вариантов решения задачи. В связи с этим, они оказываются неэффективными при большом количестве пунктов транспортных маршрутов. Учитывая то, что ежедневно на крупном машиностроительном предприятии приходится планировать свыше 70 транспортных маршрутов, это повлечет за собой привлечение больших вычислительных ресурсов. Выходом из такой ситуации является использование адаптивных стохастических алгоритмов, успешно преодолевающих указанные трудности.
Таким образом, совершенствование существующих и разработка новых методов и алгоритмов оптимизации транспортных маршрутов является актуальной научной задачей.
Целью диссертационной работы является разработка метода расчета оптимальных внутризаводских транспортных маршрутов с помощью известных оптимизационных алгоритмов. Поставленная цель предопределила необходимость решения следующего комплекса взаимосвязанных задач:
1 Проведения сравнительного анализа эффективности существующих мето
дов оптимизации с целью выявления наиболее перспективного подхода и
направления его совершенствования.
2 Разработки метода решения задач оптимизации и оценки его эф
фективности.
3 Разработки программной системы, реализующей предложенную
методику и исследования ее работоспособности и эффективности на тестовых
задачах.
4 Проведения апробации предложенного метода и программного
обеспечения при решении реальных практических задач планирования
внутризаводских транспортных маршрутов.
Методы исследования. Результаты исследования базируются на применении теории системного анализа, исследования операций, эволюционной оптимизации.
Научная новизна диссертационной работы:
Разработан новый метод решения задач оптимизации с учетом многих переменных, отличающийся от известных секторизациеи пространства поиска и наличием постоптимизационной процедуры.
Предложены модифицированные математические модели оптимизации планирования транспортных маршрутов, отличающиеся от известных наличием многих переменных оптимизации.
3 Разработан метод и алгоритм решения задач оптимизации
транспортных маршрутов на основе генетических алгоритмов.
Практическая значимость. На основе предложенного метода создана программная система планирования внутризаводских транспортных маршрутов. Работоспособность системы продемонстрирована на примере реальных задач. С помощью разработанного программного обеспечения оптимальным образом планируются транспортные маршруты для повышения оперативности обеспечения подразделений предприятия комплектующими и материалами «точно в срок» и в объеме, необходимом для утвержденного плана производства.
Реализация полученных результатов работы.
Предложенные в диссертационной работе метод и алгоритм решения задач оптимизации внутризаводских транспортных маршрутов, являются основой разработанной программной системы, которая используются при планировании транспортных маршрутов на предприятии (Акт внедрения от 10.11.2006г.) и включена в состав автоматизированной системы управления.
На основании анализа и предложенной модели бизнес-процессов
учета выдачи материалов и планирования транспортных маршрутов,
проведенного в диссертационной работе, на ОАО «Красноярский завод
холодильников» Бирюса» (г. Красноярск) создан отдел внутризаводской
логистики.
Защищаемые положения:
1 Метод оптимизации внутризаводских транспортных маршрутов.
Метод позволяет получать решения практических задач с достаточной
точностью при приемлемых временных затратах.
2 Математическая модель планирования транспортных маршрутов
более полно учитывает реальные условия функционирования
производственных предприятий.
3 Алгоритм и методика оптимизации на основе генетических
алгоритмов более эффективно решают задачи оптимизации транспортных
маршрутов, чем с помощью известных программных систем оптимизации
транспортных маршрутов.
Апробация работы. Основные положения и результаты диссертации докладывались и обсуждались на Всероссийской научно-практической конференции «Актуальные проблемы авиации и космонавтики» (2005 г.), Международной научной конференции «Туполевские чтения» (г. Казань, 2005 г.), Международной научно-практической конференции «Решетневские чтения» (2005 г.), Научно-практической конференции «Молодежь Сибири - науке России» (2005 г.), В научном журнале «Вестник СибГАУ» (2006 г.), Международной научной конференции «Методы и алгоритмы прикладной математики в технике, медицине и экономике» (г. Новочеркасск, 2006 г.), Международной научной конференции «Теория, методы проектирования, программно-техническая платформа корпоративных информационных систем» (г. Новочеркасск, 2006 г.).
Публикации. По результатам диссертационного исследования опубликовано 7 печатных работ, список которых приводится в конце автореферата.
Структура и объем работы.
Диссертационная работа состоит из 135 страниц, 59 иллюстраций, 14 таблиц, 8 приложений. При написании диссертации были использованы 117 источников информации.
Структурно диссертация состоит из введения, четырех глав, заключения, списка использованных источников и приложения.
Ключевые слова: планирование транспортных маршрутов, модели маршрутизации, генетические алгоритмы.
Организационная реструктуризация существующего бизнес-процесса доставки материалов
Для решения сложившихся проблем с доставкой материалов необходимо составить новую функциональную схему выдачи материалов со складов, которая будет отвечать следующим требованиям:
1 Алгоритм должен планировать оптимальную загрузку транспортных средств, планировать оптимальные маршруты доставки материалов, вести учет доставки грузов с помощью различных видов транспорта, формировать рабочую и отчетную документацию и накапливать статистику;
2 Выдача материалов со складов должна происходить согласно месячного лимита. Схема должна исключать возможность «подгонки» учетных данных сотрудниками предприятия. Предполагается собирать с подразделений предприятия отчетную информацию, обработку которой осуществлять в автоматическом режиме;
3 Предполагается сформировать базу данных технологической документации, и привести её в соответствие с реальными технологическими процессами, существующими на предприятии. Это позволит программным путем формировать базу данных лимитов, на основании которой будет осуществляться планирование выдачи материалов на месяц. Также база технологической документации должна содержать данные о взаимозаменяемости материалов различных марок, артикулов и модификаций. Таким образом, если на складе закончится определенный материал, не составит труда произвести пересчет лимитов и сформировать новый план по выдаче материалов в производство.
Изменения, связанные с введением нового бизнес процесса Новый бизнес-процесс предполагает следующие изменения: 1 Предлагается передать транспорт, закрепленный за подразделениями завода, в транспортный цех транспортным цехом, За подразделениями предприятия оставить лишь электротранспорт необходимый для технологических нужд;
2 Разработать алгоритмическое обеспечение для планирования маршрутов транспортных средств, контроля грузоперевозок и учета работы водителей и грузчиков;
3 Создать единый Центр обеспечения материалами (ЦОМ) со следующей структурой; менеджеры по планированию транспорта, согласно поданным заявкам на перевозку и графика доставки материалов в цеха предприятия;
- менеджеры по оперативному оформлению документов (требований) для выдачи материалов со складов, согласно месячным лимитам и графика завоза материалов в цеха;
диспетчеры по доставке грузов;
водители электрокар и электропогрузчиков;
- грузчики.
Структура ЦОМ представлена в Приложении А, Рисунок А. 1
4 Водителей и грузчиков перевести па сдельную систему оплаты. Это сделает погрузочно-разгрузочные работы более оперативными. Для расчета оплаты труда можно рассматривать количество заданий, протяженности маршрута движения (заданную диспетчером ЦОМ), объем и вес транспортируемого груза;
5 Для мониторинга выполнения заявок ввести систему микросотовой радиосвязи (либо GPRS систему), что позволит определять местонахождение и вызвать абонента в любое время и в любом месте зон обслуживания.
Построение модели будущего бизнес - процесса «КАК НАДО» Учитывая недостатки существующей схемы и основываясь на методах реинженеринга бизнес-процессов, была разработана новая схема выдачи материалов со склада и их доставки в цеха производства (модель «как надо», Приложение Б, Рисунок Б.2). Получение заявок Представители подразделений предприятия не позднее 12.00 часов дня, предшествующему планируемому, подают заявки менеджеру по планированию транспорта ЦОМ (Центра Обеспечения Материалами) на обеспечение транспортом (осуществление внешних и внутренних перевозок), который заносит их в электронную базу данных.
Менеджер по ввщаче материалов ЦОМ формирует первичный график поставки материалов в цеха. Первичный график поставки материалов в цеха передается экономисту службы планирования и производства для согласования и корректировки. Откорректированный график поставки материалов в цеха передается менеджеру ЦОМ по выдаче материалов и менеджеру ЦОМ по планированию транспорта.
Формирование «Требований» На основании согласованного графика поставки материалов менеджер ЦОМ по выдаче материалов формирует требования, по которым будут выдаваться материалы со складов. Сформированнвте требования передаются диспетчеру по доставке грузов в ЦОМ.
Модели маршрутизации
Существует масса разновидностей обобщённой постановки задачи, в частности геометрическая задача коммивояжера (когда матрица расстояний отражает расстояния между точками на плоскости), треугольная задача коммивояжёра (когда на матрице стоимостей выполняется неравенство треугольника), симметричная и асимметричная задачи коммивояжёра (Приложение Г, Рисунок Г.2-3).
Простейшие методы решения задачи коммивояжёра: полный лексический перебор, жадные алгоритмы (метод ближайшего соседа, метод включения ближайшего города, метод самого дешёвого включения), метод минимального остовного дерева. На практике применяются различные модификации более эффективных методов: метод ветвей и границ и метод генетических алгоритмов.
Все эффективные (сокращающие полный перебор) методы решения задачи коммивояжёра — методы эвристические. В большинстве эвристических методов находится не самый эффективный маршрут, а приближённое решение. Зачастую востребованы так называемые anyime алгоритмы, то есть постепенно улучшающие некоторое текущее приближенное решение Задача коммивояжёра есть NP-полная задача.
В теории алгоритмов NP-полные задачи — это класс задач, лежащих в классе NP (т.е. для которых пока не найдено быстрых алгоритмов решения, но проверка того, является ли данное решение правильным, проходит быстро), к которым сводятся все задачи класса NP. Это означает, что если найдется быстрый алгоритм для решения любой из NP-полных задач, любая задача из класса NP сможет быть решена быстро.
Основная модель вывоза и доставки. GPDP формулируется следующим образом: совокупность маршрутов должны быть составлены таким образом, чтобы удовлетворить все заявки на перевозку. Для перевозок имеется определенное количество автомобилей (или другого транспорта). Каждое транспортное средство характеризуется грузоподъемностью, начальным и конечным местоположением [12]. В каждой заявке на транспортировку указывается место, откуда должен быть доставлен груз, и место, куда он должен быть доставлен. Каждый груз должен быть перевезен одним транспортным средством без передачи его другим транспортным средствам или в места перераспределения. В настоящее время существует различные модификации GPDP.
- PDP (Pickup and Delivery Problem) - каждая транспортировка характеризуется одним источником и одним местом назначения, все транспортные средства отправляются из транспортного депо и туда же возвращаются после выполнения задания.
- DARP (Dial-a-Ride Problem) - здесь речь идет о перевозке людей
- VRP (Vehicle Road Problem) - это разновидность PDP, в которой все пункты загрузки или назначения находятся в одном месте [85].
Существует множество разновидностей этих трех моделей, некоторые из них приведены ниже (Приложение Ґ. Рис. 3-5):
1 Capacitated Vehicle Routing Problem (CVRP) - задача маршрутизации транспорта с ограничениями по грузоподъемности. VRP задача с дополнительными ограничениями заключенными в грузоподъемности транспорта. Вес груза, который нужно перевезти по каждому маршруту не должен превышать грузоподъемности соответствующего транспортного средства.
2 Vehicle Routing Problem with Time Windows (VRPTW) - задача маршрутизации транспорта с временными окнами. VRP с дополнительным ограничением: остановка для загрузки или разгрузки возле каждого клиента должна происходить в строго назначенное время.
Выбор технологии проектирования „
Проектирование экономических информационных систем (ЭИС) - это процесс принятия проектно-конструкторских решений, направленных на получение описания системы (проекта ЭИС), удовлетворяющего требования заказчика [19].
Под проектом ЭИС понимается проектно-конструкторскую и технологическую документацию, в которой представлено описание проектных решений по созданию и эксплуатации ЭИС в конкретной программно-технической среде.
На первой стадии проводился анализ деятельности предприятия. Конкретно анализ такого бизнес процесса, как транспортировка грузов.
Существует множество методик, с помощью которых возможно обследовать предприятие и построить модель его деятельности, существуют различные стандартизованные методологии и инструментальные средства.
Описание схемы процесса доставки грузов на предприятии ОАО КЗХ "Бирюса" составлялось согласно стандарту моделирования бизнес-процессов IDEFO (Integration Definition for Function Modeling). Стандарт IDEF 0 был разработан в начале 90х годов, в США на основе SADT. Стандарт является независимым от частных организаций, и получил чрезвычайно широкое распространение, он принят в качестве стандарта в нескольких международных организациях. В IDEFO система представляется как совокупность взаимодействующих работ или функций. Такая чисто функциональная ориентация является принципиальной - функции системы анализируются независимо от объектов, которыми они оперируют. Это позволяет более четко формулировать логику и взаимодействие процессов организации. Под моделью в IDEFO понимают описание системы (текстовое и графическое), которое должно дать ответ на некоторые заранее определенные вопросы.
Модель в нотации IDEF0 представляет собой совокупности иерархически упорядоченных и взаимосвязанных диаграмм. Каждая диаграмма является единицей описания системы и располагается на одном листе.
На этапе технического проектирования стадии «Технике - рабочего проектирования», т.е. при разработке логики проекта использовалась трехступенчатая методика проектирования баз данных.
В предлагаемой методологии проектирования баз данных весь процесс разработки разделяется на три основные фазы: концептуальное, логическое и физическое проектирование.
Концептуальное проектирование базы данных - это процедура конструирования информационной модели предприятия, не зависящей от каких-либо физических условий реализации.
Фаза концептуального проектирования базы данных начинается с создания концептуальной модели данных предприятия, полностью независимой от любых деталей реализации. К последним относятся: выбранный тип СУБД, состав программ приложения, используемый язык программирования, конкретная вычислительная платформа и любые другие физические особенности реализации. Она включает определение типов важнейших сущностей и существующих между ними связей.
Логическое проектирование базы данных - это процедура конструирования информационной модели предприятия на основе существующих конкретных моделей данных, не зависящей от используемой СУБД и других физических условий реализации.
Структура программного продукта
Главная форма программного продукта предназначена для работы с программой путем внесения заявок формирования маршрутов и при необходимости редактирования ГИС (Приложение И, Рисунок И. 10).
На первой закладке формы «Заявки» происходит заполнение заявок. В заявках указывается место загрузки и место назначения, временные интервалы, в которые груз должен быть погружен и доставлен. Точки маршрута могут быть выбраны как из выпадающего списка, так и занесены непосредственно с карты. Необходимо нажать кнопку JfiJ, а затем выбрать узел на карте, который соответствует необходимому пункту. В нижней части формы находится табличная часть с помощью нее и кнопок «+, -» можно составить список грузов которые необходимо перевезти. Подбор грузов происходит при помощи окна «Подбор грузов». В таблице «Заказы» отображаются уже введенные заказы.
После того как перечень заказов к выполнению сформирован, следует перейти на закладку «Маршруты». Для того чтобы маршруты были сформированы, необходимо нажать кнопку «Рассчитать». На закладке появятся маршруты, сформированные для транспортных средств. Маршруты представлены в виде списка с пиктограммами, а также изображены в виде выделенной цветом линии на карте. ПиктограммаЭ означает пункт загрузки, а Ш соответственно разгрузки. При выборе транспортного средства из выпадающего списка отображаются его маршруты. Маршруты также можно выбрать по отдельности. Может быть отображен один из маршрутов транспортного средства или все его маршруты. Внизу закладки на табличной части представлен перечень перевозимых грузов в рамках маршрута или транспортного средства. В самом низу закладки отображены общее время и продолжительность маршрута.
Информация о заказах может быть "выгружена" в файл формата XML для последующего использования. Для этого находясь на «Заявки» следует выбрать пункт меню Файл - Сохранить. Для сохранения информации о сформированных маршрутах для дальнейшего просмотра следует, находясь на закладке «Маршруты», выбрать меню Файл - Сохранить. Для просмотра сохраненных в файлах информации о маршрутах или заказах следует выбрать меню Файл - Открыть. В диалоге открытия файлов следует выбрать формат файла XML. В зависимости от того файл это с информацией о маршрутах или заявках будет ввібрана соответствующая закладка.
Ввод информации о транспортных средствах происходит при помощи окна «Транспорт». В этом окне можно указать марку транспортного средства, принадлежность его предприятию, и доступность. Изменяя атрибут "доступность" можно регулировать использование определенных транспортиых средств при составлении маршрутов. Для более гибкой настройки работы транспортных средств есть также поля «Начало работы» и «Конец работы».
Похожие диссертации на Исследование и разработка метода оптимизации внутризаводских транспортных маршрутов
