«Программный модуль формирования маршрутов транспортных средств на базе генетического алгоритма» - Дипломная работа

Содержание

ВВЕДЕНИЕ 3

ГЛАВА 1. ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ ДЛЯ ПРОЦЕССА ОПТИМИЗАЦИИ МАРШРУТОВ 5

1.1 Значимость оптимизации маршрутов в логистических системах 5

1.2 Задачи и особенности транспортной логистики 6

1.3 Способы решения задач маршрутизации 7

1.4 Основные понятия генетического алгоритма 12

1.5 Основные принципы работы генетического алгоритма. Операторы и процедуры генетического алгоритма 13

ГЛАВА 2. ПРОЕКТИРОВАНИЕ ПРОГРАММНОГО МОДУЛЯ ДЛЯ ПОСТРОЕНИЯ МАРШРУТОВ ТРАНСПОРТНЫХ СРЕДСТВ 17

2.1 Математическая модель задачи маршрутизации 17

2.2 Применение операторов и процедур генетического алгоритма 18

2.3 Техническое задание 22

2.4 Проектирование программного модуля для решения задачи

2.5 Маршрутизации в программе BPwin 25

ГЛАВА 3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ И ВЫЧИСЛИТЕЛЬНЫЙ ЭКСПЕРИМЕНТ 29

3.1 Выбор языка программирования 29

3.2 Программная реализация 30

3.3 Руководство пользователя 33

3.4 Вычислительный эксперимент 35

3.5 Оценка эффективности работы разработанного алгоритма 36

3.6 Расчет экономической эффективности системы 40

ЗАКЛЮЧЕНИЕ 52

ЛИТЕРАТУРА 55

ПРИЛОЖЕНИЯ 58

Введение

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

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

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

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

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

1. Провести анализ моделей, методов решения задач транспортной логистики и области их применения;

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

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

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

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

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

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

Выдержка из текста работы

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

1.1 Значимость оптимизации маршрутов в логистических системах

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

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

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

1.2 Задачи и особенности транспортной логистики

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

VRP (Vehicle Routing Problems) - это задача целочисленного программирования, относящиеся к классу NP-трудных задач, т.е. к задачам, в которых сложность и трудоемкость решения зависит от размера вводимых данных экспоненциально.

VRP сочетает в себе два хорошо изученные задачи, а именно:

1. Задача упаковки «рюкзака» - задача, в которой из заданного множества предметов со своими свойствами «стоимость» и «вес», требуется отобрать некое число предметов таким образом, чтобы получить максимальную суммарную заполненность при соблюдении ограничений вместимости рюкзака [9].

2. Задача коммивояжера [18]. Задача, в которой грузоподъемность транспортного средства считается достаточной (или бесконечной). Задача заключается в поиске самого выгодного маршрута, при условии, что каждый пункт посещается хотя бы один раз, и после посещения всех маршрутов транспортное средство возвращается на склад.

Заключение

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

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

Все поставленные задачи были выполнены, а именно:

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

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

3. Спроектирован и реализован программный модуль для формирования рациональных маршрутов транспортных средств на базе разработанного генетического алгоритма, который позволяет рассчитывать маршруты по заданным исходным данным (для практического применения), а также формировать случайные наборы исходных данных для проведения теоретических исследований;

4. Проведен вычислительный эксперимент с помощью разработанного программного модуля для анализа эффективности разработанного генетического алгоритма. Определены эффективные настройки алгоритма для решения задач размерности от 50 до 300 пунктов, а именно количество последовательностей - 10, количество мутаций - 5, количество поколений - 10000. Сравнение решений, полученных с помощью алгоритма «ближайшего соседа», эволюционного и разработанного генетического показало, что последний позволяет получать решения в среднем на 5-10% меньшей протяженности, чем решения, полученные алгоритмом «ближайшего соседа». Результат генетического алгоритма в среднем на 4,67% лучше, чем результат эволюционного алгоритма. Генетический более эффективен для матриц размерностью 50, 150, 300 относительно эволюционного алгоритма. А также был определен класс задач (размерность матрицы 1000), для которых генетический алгоритм дает решение лучше (на 0,72%), чем эволюционный, но затрачивает на его нахождение существенно больше времени.

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

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

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

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

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

1. Батищев, Д.И. Генетические алгоритмы решения экстремальных задач [Текст] / Д.И. Батищев. - Нижний Новгород, 1995. - 24 с.

2. Беспалов, Р.С. Транспортная логистика [Текст] / Р.С. Беспалов. - М.: Вершина, 2007. - 384 с.

3. Глущенко Л.Р. Оценка эффективности проекта [Текст]: методические указания к выполнению выпускной квалификационной работы для студентов специальности 080801 «Прикладная информатика в экономике». / Л.Р. Глущенко, З.З. Имашева - Уфа, УГАТУ, 2007. - 47с.

4. Михайлова А.Н. Информационная система формирования маршрутов движения транспорта на основе эволюционного алгоритма с многоточечным кроссинговером [Текст]: Динамика сложных сетей и их применение в интеллектуальной робототехнике. Сборник материалов II Международной школы-конференции молодых ученых. - Саратов, ООО

«Издательство «Научная книга»», 2018. с. 172-174.

5. Михайлова А.Н. Эволюционный алгоритм для маршрутизации транспорта с учетом грузоподъемности // Динамика сложных сетей и их применение в интеллектуальной робототехнике [Текст] : сборник материалов 1 Международной школы-конференции молодых ученых - Саратов, ООО «Издательство «Научная книга»», 2017. - с. 31-32

6. Михайлова А.Н. Информационная система формирования маршрутов движения транспорта на основе генетического алгоритма [Текст]: IT & Transport / ИТ & Транспорт. Сб. науч. статей / под ред. Т.И. Михеевой. - Самара, Интелтранс, 2018. т.10. с. 60-63.

7. Михайлова А.Н. Разработка эволюционного алгоритма для транспортно-логистических информационных систем [Текст]: Сб. науч. статей Актуальные проблемы науки и техники. Информационные и инфокоммуникационные технологии. - Уфа, УГАТУ, 2018. с. 43- 45.

8. Мухачева Э.А. Методы локального поиска в задачах оптимального распределения ресурса [Текст]: учебно-методическое пособие / Э.А. Мухачева. - Уфа: УГАТУ, 2001. - 103с.

9. Никифоров, В.С. Мультимодальные перевозки и транспортная логистика [Текст]: В.С. Никифоров - М : ТрансЛит, 2007. - 272 с.

10. Панченко, Т. В. Генетические алгоритмы [Текст]: учебно-методическое пособие / под ред. Ю. Ю. Тарасевича. — Астрахань: Издательский дом «Астраханский университет», 2007. — 87 [3] с.

11. Филиппов, Д.В. Управление и оптимизация процесса формирования маршрутов поставок потребительских товаров в распределительных центрах [Текст]: диссертация . кандидата

экономических наук : 08.00.05 / Д.В. Филиппов [Место защиты: Гос. ун-т упр.]. - Москва, 2012. - 187 с.

12. Филиппова, А.С. Задачи маршрутизации в транспортных логистических системах: локальный поиск оптимальных решений [Текст] : / А.С. Филиппова, Д.В. Филиппов, Н.А. Гильманова - Уфа : Информационные технологии. №2, 2009. -59-63 с.

13. Филиппова, А.С. Алгоритмическое обеспечение транспортно-логистических информационных систем на базе метаэвристик [Текст] : Перспективные информационные технологии в научных исследованиях, проектировании и обучении (ПИТ 2012): труды научно-технической конференции с международным участием и элементами научной школы для молодежи, посвященной 40-летию кафедры информационных систем и технологий СГАУ / под ред. С.А. Прохорова. / А.С. Филиппова, Ю.И. Валиахметова, Р.В. Фролов - Самара: Издательство Самарского научного центра РАН, 2012. - 257-260с.

14. Филиппова А.С. Использование эволюционного алгоритма для изучения студентами дисциплины «Прикладные методы оптимизации» [Текст]: гуманистическое наследие просветителей в культуре и образовании: материалы XII Международной научно-практической конференции 14 декабря 2017 г. - Уфа, Издательство БГПУ, 2018. - с. 108 -109

15. Филиппова А.С. Алгоритмическое обеспечение транспортно-логистических информационных систем [Текст]: Материалы Всероссийской (с международным участием) студенческая научно-практической конференции «Наука 2020» (20 апреля 2018 г.) / сост. Л.Р. Саитова, Р.Н. Измайлов. - Уфа, Изд-во БГПУ, 2018. с. 215-220

16. Gendreau, M. “Metaheuristics for the vehicle routing problem and its extensions: A categorized bibliography,” The Vehicle Routing Problem: Latest Advances and Challenges, B. L. Golden, S. Raghavan, and E. A. Wasil (Editors) / M. Gendreau, J.-Y. Potvin, O. Braysy, G. Hasle, A. Lokketangen // Springer., 2008 - 78 p.

17. Luke S. Essentials of Metaheuristics. — Lulu, 2009. - 235 p.

18. Punnen A. P. “The traveling salesman problem: applications, formulations and variations”, "The traveling salesman problem and its variations" edited by G. Gutin, A. Punnen - Dordrecht: Kluwer Academic Publishers, 2002 - 1-28 p.

Примечания

Оригинал в pdf