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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

«Издательство «Научная книга»», 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.