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

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

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

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

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

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

• Обзор и анализ задач маршрутизации и методов их решения;

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

• Проектирование модуля для формирования маршрутов

транспортных средств;

• Реализация программного модуля;

• Проведение вычислительных экспериментов и анализ результатов.

• Traveling Salesman Problem (Задача коммивояжера) — задача коммивояжера относится к разряду известных задач комбинаторной оптимизации, главной целью которой является поиск наилучшего маршрута путем прохождения всех указанных пунктов минимум один раз и обязательным возвратом в начальный пункт. Если грузоподъёмность С транспортного средства не ограничена (является достаточной), то задачу VRP сводят к множественной задаче коммивояжера — Multiple Traveling Salesman Problem. Задача решается путем добавления к исходному графу k-1 (k-количество маршрутов) копий нулевой вершины и её рёбер (между этими копиями рёбра отсутствуют) [2].

• Bin Pacing Problem (Задача о рюкзаке) — задача о рюкзаке является NP-полной задачей комбинаторной оптимизации. Своё название получила от главной цели — упаковать как можно больше вещей в рюкзак с учётом ограничения вместимости. Решение задачи равнозначно решению задачи VRP, однако расстояния принимаются равными нулю. Таким образом, эффективность решений будет равнозначна [3].

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

• Задача маршрутизации с ограниченной грузоподъёмностью — условием задачи является ограниченность грузоподъёмности транспортных средств;

• Задачи маршрутизации с ограничением по времени — условием задачи является обслуживание заказчиков в определенное время («временное окно»);

• Задача маршрутизации с нескольким депо — задача основана на наличии нескольких «депо» для обслуживания заказчиков;

• Задача маршрутизации с возвратом товара — данная задача основана на преимуществе возвратов некоторых товаров в депо;

• Задача маршрутизации с возвратом товаров — задача построена подобно предшествующей, однако возврат товаров осуществляется только после того как все товары из депо будут доставлены заказчикам;

• Задача маршрутизации с разным транспортом — в данной задаче обслуживание заказчиков может осуществляться одновременно несколькими машинами;

• Периодическая маршрутизация — условием является доставка товара в течение нескольких дней;

• Задача маршрутизации со случайными данными — в данной задаче компоненты могут иметь случайное поведение;

• Задача маршрутизации с возможностью дозагрузки — в задаче есть вероятность дозагрузки транспортного средства на маршруте.

• Разобраны основные операторы и процедуры эволюционного алгоритма;

• Разработан и исследован эволюционный алгоритм для задачи маршрутизации;

• Разработан модуль расчетов для логистической информационной системы с целью планирования маршрутов доставки товаров;

• Проведён анализ эффективности разработанного алгоритма на базе вычислительного эксперимента.

6. Иванов, М.Ю. Логистика: учеб. пособие [Текст] / М.Ю. Иванов, М.Б. Иванова; РИОР: 2006. - 97 с.

7. Киршина, М.В. Коммерческая логистика [Текст] / М.В. Киршина; Центр экономики и маркетинга, 2008. - 129 с.

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

9. Семенов, В.А. Эффективность логистических систем [Текст] / В.А. Семенов, Е.А. Володина; Маркетинг: - 2000, № 2.

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

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

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

13. 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. - 90с.