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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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