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

Краткое описание

Шамлицкий Ярослав Иванович. Исследование и разработка метода оптимизации внутризаводских транспортных маршрутов : диссертация ... кандидата технических наук : 05.13.01.- Красноярск, 2006.- 144 с.: ил. РГБ ОД, 61 07-5/953

СИБИРСКИЙ ГОСУДАРСТВЕННЫЙ АЭРОКОСМИЧЕСКИЙ
УНИВЕРСИТЕТ имени академика М.Ф. Решетнева
На правах рукописи

ШАМЛИЦКИЙ ЯРОСЛАВ ИВАНОВИЧ
ИССЛЕДОВАНИЕ И РАЗРАБОТКА МЕТОДА ОПТИМИЗАЦИИ ВНУТРИЗАВОДСКИХ ТРАНСПОРТНЫХ МАРШРУТОВ
05.13.01 - Системный анализ, управление и обработка информации
Диссертация на соискание ученой степени кандидата технических наук
Научный руководитель кандидат технических наук, профессор Сорокин В.А.
Красноярск 2006
СОДЕРЖАНИЕ
ВВЕДЕНИЕ 6
1.1 Анализ предприятия и производственной ситуации 10
1.2 Организационная реструктуризация существующего бизнес-процесса 4 доставки материалов 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 Алгоритм Дейкстры 3 8
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
0 2.4 Сравнение эффективности подходов 80
Вывод 83
3 ПРОЕКТИРОВАНИЕ СИСТЕМЫ ОПТИМИЗАЦИИ ВНУТРИЗАВОДСКИХ ТРАНСПОРТНЫХ МАРШРУТОВ 84
3.1 Выбор технологии проектирования !.. 84
3.2 Структура разрабатываемой системы маршрутизации 86
3.3 База данных 87
3.4 Источники данных системы 88
3.5 Проектирование базы данных 90
§ 3.6 Системы оптимизации загрузки 97
Вывод 988
4 РАЗРАБОТКА ПРОГРАММНОГО ПРОДУКТА 99
4.1 Структура программного продукта 99
4.2 Описание работы с программой 99
4.3 Программное обеспечение 102
ЗАКЛЮЧЕНИЕ 106
Список использованных источников 107
Приложение «А» Организационная структура Центра обеспечения материалами 117
Приложение «Б» Функциональные схемы процесса 118
® Приложение «В» Интерфейсы программных средств маршрутизации 123
Приложение «Г» Проектирование системы и модели маршрутизации 127
Приложение «Д» Системы оптимизации загрузки транспортных средств 129
Приложение «Е» Геоинформационные системы 130
Приложение «Ж» Проектирование базы данных 132
Приложение «И» Интерфейс разработанной программы 139
Список авторских публикаций 142

Список литературы

ЗАКЛЮЧЕНИЕ
В результате проведенного исследования был выполнен ряд работ:
1 Проанализирована система планирования потребности в материалах и система планирования внутризаводских транспортных маршрутов.
2 Построены диаграммы процесса в стандарте ГОЕРО. По результатам обследования была составлена существующая схема процесса грузоперевозок и выявлены ее недостатки. С учетом недостатков разработана новая модель бизнес-процесса планирования материалов и транспортных перевозок и его контроля, предложена цовая организационная схема подразделений, занимающихся доставкой и планированием, составлен проект штатных расписаний, разработаны должностные инструкции и личностные спецификации персонала.
3 Проведен сравнительный анализ существующих методов оптимизации транспортных маршрутов. В результате выявлен наиболее перспективный подход и направления его совершенствования.
4 Описана математическая модель общей системы выдачи материалов, разработана математическая модель применительно к решаемой задаче.
5 Разработан метод решения задач оптимизации с учетом многих переменных, сочетающий в себе секторизацию пространства поиска и постоптимизационную процедуру. Показано его преимущество над тра¬диционными методами планирования транспортных маршрутов.
6 Метод реализован в виде интегрированной программной системы, позволяющей эффективно решать тестовые и реальные задачи условной оптимизации.
7 Проведена успешная апробация предложенного программного обеспечения при решении реальных практических задач планирования внутризаводских транспортных маршрутов.