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

Содержание

ВВЕДЕНИЕ 3

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

1.1 Обзор и анализ существующих задач маршрутизации 5

1.2 Методы решения задач маршрутизации 6

1.3 Основные понятия эволюционного алгоритма 12

ГЛАВА 2. ПРОЕКТИРОВАНИЕ ПРОГРАММНОГО МОДУЛЯ 15

2.1 Постановка задачи маршрутизации 15

2.2 Применение операторов и процедур для эволюционного алгоритма 17

2.3 Проектирование программного модуля в программе BPwin 19

ГЛАВА 3. РАЗРАБОТКА ПРОГРАМНОГО МОДУЛЯ 23

3.1 Обзор и анализ существующих языков программирования 23

3.2 Техническое задание к программному модулю 26

3.3 Программная реализация разработанного эволюционного алгоритма 31

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

3.5 Анализ экономической эффективности 50

ЗАКЛЮЧЕНИЕ 66

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 67

Введение

В современном мире во многих отраслях человеческой деятельности требуется выполнение задач с большим количеством вычислений. Чтобы решить подобного рода задачи, чаще всего принимают решение об увеличении количества персонала. Однако, данный способ решения задачи не исключает возможности возникновения проблем, в связи с тем, что присутствует обычный «человеческий фактор», который может стать причиной для совершения ошибки.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.1 Обзор и анализ существующих задач маршрутизации

Задачи маршрутизации относятся к значимым классам задач транспортной логистики. Главными целями задач маршрутизации (VRP) является минимизация стоимости и общей длины маршрутов, сокращение времени на транспортировку грузов.

Vehicle Routing Problem (VRP) — распространенная задача целочисленного программирования, которая считается очень важной и NP- сложной задачей комбинаторной оптимизации [1].

Задачи маршрутизации основаны на совмещении в себя двух известных задач:

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

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

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

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

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

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

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

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

1. Аникин, Б.А., Логистика: учеб. пособие [Текст] / Б.А. Аникина, Т.А. Родкина; - М.: ТК Велби, Изд-во Проспект. - 2008. - 408 с.

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

3. Борисовский, П.А. О сравнении некоторых эволюционных алгоритмов [Текст] / П.А. Борисовский, А.В. Еремеев; Автоматика и телемеханика.: 2004. - №3. c. 3-9.

4. Бухарбаева Л.Я., Филиппов Д.В., Брусиловский Д.П. Прогнозирование и управление цепью поставок в логистической среде товарно-производственных комплексов // Вестник ЧГУ. №3 (141). Экономика (вып. 19). 2009. с 15-21.

5. Григорьева, М.С. Применение информационных технологий для решения задачи доставки мелкопартийных грузов по городу [Текст] / М.С. Григорьева, Д.А. Красникова; Саратов.: 2014. - 139 с.

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

Примечания

Оригинал в pdf