«Оптимизация маршрутов в условиях чрезвычайных ситуаций» - Дипломная работа

Содержание

ВВЕДЕНИЕ 7

Глава 1. АНАЛИТИЧЕСКАЯ ЧАСТЬ 9

1.1. Анализ предметной области 9

1.1.1 Основные понятия, включенные в построение маршрута 9

1.1.2 . Оптимизация маршрута 9

1.2. Содержательная постановка задачи 11

1.3. Обзор и анализ существующих программных средств оптимизации маршрута 11

1.4. Задачи маршрутизации транспорта 15

1.4.1 Разновидности VRP 17

1.5. Анализ алгоритмов поиска оптимального пути 19

1.5.1 Точные алгоритмы 20

1.5.2 Неточные алгоритмы 25

1.5.3 Метод Кларка-Райта 29

Вывод по 1 главе 33

Глава2. ПРОЕКТНАЯ ЧАСТЬ 34

2.1 . Техническое задание 34

2.2 .Функциональное моделирование и проектирование 36

2.3 Формальная постановка задачи 37

Вывод по 2 главе 41

Глава 3 .РАЗРАБОТКА 42

3.1 Описание структуры данных 42

3.2 Описание структуры программного продукта 43

3.3 Описание кода программы 44

3.4 Описание интерфейса пользователя 49

3.5 Оценка качества решения 54

3.5.1Тестирование ПО 54

3.5.2 Проверка в нормальных условиях 55

3.5.3 Проверка в экстремальных условиях 55

3.5.4 Проверка в исключительных ситуациях 55

3.6 Вычислительный эксперимент и анализ результатов 55

3.7 Технико-экономическое обоснование 56

3.7.1 Трудоёмкость разработки 57

Вывод по 3 главе 59

ЗАКЛЮЧЕНИЕ 60

ЛИТЕРАТУРА .62

Введение

Транспорт - это отрасль материального производства, осуществляющая перевозки людей и грузов.

Изменение местонахождения товарно-материальных ценностей с помощью транспортных средств называется транспортировкой грузов.

Транспортная логистика решает следующие задачи:

• создание транспортных систем;

• совместное планирование транспортных процессов на различных видах транспорта (в случае смешанных перевозок);

• обеспечение технологического единства транспортно-складского процесса;

• выбор способа транспортировки и транспортного средства;

• определение рациональных маршрутов передвижения.

По назначению различают внешнюю (в логистических каналах снабжения - сбыта) и внутреннюю (внутрипроизводственную) транспортировку. Оба вида транспортировки взаимосвязаны между собой и образуют транспортную систему предприятия.

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

Для достижения указанной цели поставлены следующие задачи:

1. рассмотреть основные алгоритмы поиска оптимального маршрута;

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

3. рассмотреть и проанализировать существующие программные средства оптимизации маршрута; 

4. на основе полученных данных анализа разработать приложение, позволяющее пользователям отметить на карте места, которые необходимо посетить и получить оптимальный путь, наглядно показанный на Yandex.Maps[16],

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

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

Глава 1.АНАЛИТИЧЕСКАЯ ЧАСТЬ

1.1 Анализ предметной области

1.1.1 Основные понятия, включенные в построение маршрута

Маршрут (нем. Marschroute, от франц, marche — ход, движение вперёд и route — дорога, путь) — путь следования объекта, учитывающий направление движения относительно географических ориентиров или координат, с указанием начальной, конечной и промежуточных точек, в случае их наличия.

По строению трассы маршруты в отношении географической привязки к местности подразделяются на:

• линейные - с посещением одного или нескольких пунктов (кроме начального), находящихся на трассе;

• радиальные - (стационарные) с посещением одного пункта на маршруте;

• кольцевые (кроссинг-туры) - с совпадением точек начала и конца маршрута и посещением нескольких пунктов на маршруте. Другим вариантом может быть кольцевой маршрут по посещаемой местности или стране, причем место прибытия в страну или местность (условно аэропорт, станция железной дороги) может быть (а) неизменным, т.е. путешествие по стране началось и завершилось в одном и том же пункте, и (б) отличным от места прибытия в местность или страну. [1]

1.1.2 Оптимизация маршрута

Рассмотрим понятие оптимизации.

Оптимизация — процесс максимизации выгодных характеристик, соотношений (например, оптимизация производственных процессов и производства), и минимизации расходов.

Задачи оптимизации сформулирована, если заданы: 

• критерий оптимальности (экономический, технологические требования — выход продукта, содержание примесей в нем и другое);

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

• математическая модель процесса;

• ограничения, связанные с экономическими и конструктивными условиями, возможностями аппаратуры, требованиями взрывобезопасности и другое.

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

Причем эти характеристики могут относиться не только непосредственно к самому маршруту, но и к способу и особенностям передвижения транспортного средства по этому маршруту.

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

Выделяют маршруты кольцевые и маятниковые:

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

При маятниковом маршруте осуществляется периодический заезд в пункт отправки, в котором осуществляется загрузка или дозагрузка транспортного средства.

Заключение

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

Далее были рассмотрены существующие программные средства для оптимизации маршрутов, такие как: Логист, Zig-zag, SpeedyRouten Мегалогист. Выявлены их плюсы и минусы.

Так же были проанализированы алгоритмы поиска оптимального пути как точные, так и неточные. И в итоге был выбран метод Кларка-Райта, так как он показался простым и наиболее подходящей для решения моей задачи. Данный алгоритм был подробно рассмотрен на примере простой задачи.

После были представлены схемы, реализованные в программе Ramus:

• Контекстная диаграмма методологии IDEF0

• Декомпозиция первого уровня

• Декомпозиция третьего уровня

• Структура решения задачи

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

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

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

• проведен анализ основных методов и алгоритмов поиска оптимального маршрута; 

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

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

1. Амиров, Магомед Единая транспортная система / Магомед Амиров. - М.: КноРус медиа, 2016. - 355 с.

2. Аникеич А.А., Грибов А.Б., Сурин С.С. Сменно-суточное планирование работы грузовых автомобилей на ЭВМ. М.: Транспорт, 1976. - 152с.

3. Афонин, А. М. Промышленная логистика / А.М. Афонин, Ю.Н. Царегородцев, А.М. Петрова. - М.: Форум, 2017. - 304 с.

4. Балашов, Е. П. Проектирование информационно-управляющих систем / Е.П. Балашов, Д.В. Пузанков. - М.: Радио и связь, 1987. - 256 с.

5. Бережной В.И. Методы и модели логистического подхода к управлению автотранспортным предприятием. Ставрополь: Ставроп. гос. техн, ун., Интеллект-сервис, 1997.

6. Боковой, Ю. В. Особенности методологии проектирования информационных систем для малого и среднего бизнеса / Ю.В. Боковой. - М.: Синергия, 2006. - 254 с.

7. Вендров, А. М. Практикум по проектированию программного обеспечения экономических информационных систем / А.М. Вендров. - М.: Финансы и статистика, 2006. - 192 с.

8. Ишкова, Э. А. Самоучитель С#. Начала программирования / Э. А. Ишкова. - М.: Наука и техника, 2013. - 496 с.

9. Касаткин, А. И. Профессиональное программирование на языке си.

Управление ресурсами / А.И. Касаткин. - М.: Высшая школа, 2012. - 432 с

10. Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: построение и анализ. Москва: Вильямс, 2006.

П.Молоканова, Н.П. Курсовое и дипломное проектирование: Учебное пособие / Н.П. Молоканова. - М.: Форум, НИЦ ИНФРА-М, 2013. - 88 с

12. Путилин, А. Б. Компонентное моделирование и программирование на языке UML. Практическое руководство по проектированию информационных систем: моногр. / А.Б. Путилин, Е.А. Юрагов. - М.: НТ Пресс, 2005. - 664 с.

13. Смирнов М.И., Хайруллин Р.З. Математические модели, используемые в системе оптимизации доставки товаров автотранспортом «Диспетчер» // Препринты ИПМ им.М.В.Келдыша. № 13. - М., 2002.

14. Строгалев В. И, Толкачева И. О. Имитационное моделирование. — МГТУ им. Баумана, 2008. — С. 697-737. — ISBN 978-5-7038-3021-5.

15. httns://zig**zag.org

16. httns: //www.va**ex.ru/mans.

Примечания

Оригинал в pdf