📄Работа №126391
Тема: Поиск оптимального маршрута в условиях динамически меняющихся ограничений
Тип работы
Дипломные работы, ВКР
Предмет
программирование
Объем:
51 листов
Год:
2022
Просмотров:
97
4750
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
Введение 3
Постановка задачи 5
Обзор существующих методов 7
Глава 1. Реализация вспомогательных алгоритмов 14
1.1. Особенности реализации и хранения 14
1.2. Генерация случайных многоугольников 14
1.3. Гексагональный растр 19
1.4. Растеризация отрезков 22
1.5. Заливка многоугольников 24
Глава 2. Алгоритм поиска оптимального маршрута 26
2.1. Идея и описание алгоритма 26
2.2. Данные для тестирования 29
2.3. Тестирование алгоритма 29
Глава 3. Анализ алгоритма 34
3.1. Повороты карты 34
3.2. Поиск оптимального угла 36
3.3. Временная сложность алгоритма 43
3.4. Характеристики вычислительной среды 45
Заключение 46
Список использованных источников 48
Постановка задачи 5
Обзор существующих методов 7
Глава 1. Реализация вспомогательных алгоритмов 14
1.1. Особенности реализации и хранения 14
1.2. Генерация случайных многоугольников 14
1.3. Гексагональный растр 19
1.4. Растеризация отрезков 22
1.5. Заливка многоугольников 24
Глава 2. Алгоритм поиска оптимального маршрута 26
2.1. Идея и описание алгоритма 26
2.2. Данные для тестирования 29
2.3. Тестирование алгоритма 29
Глава 3. Анализ алгоритма 34
3.1. Повороты карты 34
3.2. Поиск оптимального угла 36
3.3. Временная сложность алгоритма 43
3.4. Характеристики вычислительной среды 45
Заключение 46
Список использованных источников 48
📖 Введение
Задача поиска оптимального маршрута в условиях динамически меняющихся ограничений возникает практически повсеместно. Особенно в наши дни, когда ведутся активные наработки в области искусственного интеллекта: создание бытовых роботов-пылесосов, автопилотов (к примеру, компания «Яндекс» уже запустила экспериментальные такси без водителя в Москве [1]) и т.п. В этой же работе будет рассмотрена задача, относящаяся к одной из важнейших сфер человеческой деятельности - к судоходству.
Важнейшим фактором конкурентоспособности в морской отрасли является минимизация расхода топлива на судоходных маршрутах. В то же время, это согласуется с усилением общемировой тенденции к сокращению выбросов вредных веществ в атмосферу в рамках смягчения последствий изменения климата (например, глобального потепления) [2]. Оба этих требования могут быть удовлетворены посредством поиска оптимального маршрута. Под критериями оптимальности можно понимать очень многое: время в пути (за опоздание или слишком раннее прибытие может быть наложен штраф), расход топлива, минимизация выбросов, безопасность судна и груза (боковая качка может привести к повреждениям судна или потере груза) и комфорт пассажиров (особенно страдающих морской болезнью). Выбор конкретных критериев зависит от поставленной задачи.
Кроме того, в последние годы в академических и в коммерческих кругах значительно возросло внимание к так называемым метеорологическим маршрутам судов (англ. weather routing). Основной задачей в этой области является поиск оптимального пути и скорости движения для заданного рейса в условиях динамически меняющихся ограничений (погодных условий, таких как ветер, высота и направление волн и т.п.). Данную тенденцию можно заметить на рис. 1, где отображено изменение количества статей в области weather routing за последние 60 лет [3].
Рис. 1. Повышение интереса к области weather routing [3]
Большинство существующих разработок в этой области основывается либо на классических алгоритмах поиска кратчайших путей в графе (таких как алгоритм Дейкстры [4, 5, 6, 7], А* [2, 8]), либо на оптимизационных и математических алгоритмах: метод динамического программирования [4], метод многокритериальной оптимизации [9, 10], задача вариационного исчисления [6, 9], задача нелинейного программирования [4, 11], метод изохрон [4, 12], эволюционный алгоритм [4, 9, 10]. Кроме того, в последние годы также возросло количество приложений искусственного интеллекта и машинного обучения [3]. В работе [13] упоминается, что в некоторых системах планирования маршрутов используется метод Монте-Карло.
Однако не было найдено ни одного исследования, опирающегося на идеи гексагональной растеризации карты, математической морфологии и поиске в ширину. Вследствие чего этот подход к решению проблемы weather routing рассматривается в данной работе.
Важнейшим фактором конкурентоспособности в морской отрасли является минимизация расхода топлива на судоходных маршрутах. В то же время, это согласуется с усилением общемировой тенденции к сокращению выбросов вредных веществ в атмосферу в рамках смягчения последствий изменения климата (например, глобального потепления) [2]. Оба этих требования могут быть удовлетворены посредством поиска оптимального маршрута. Под критериями оптимальности можно понимать очень многое: время в пути (за опоздание или слишком раннее прибытие может быть наложен штраф), расход топлива, минимизация выбросов, безопасность судна и груза (боковая качка может привести к повреждениям судна или потере груза) и комфорт пассажиров (особенно страдающих морской болезнью). Выбор конкретных критериев зависит от поставленной задачи.
Кроме того, в последние годы в академических и в коммерческих кругах значительно возросло внимание к так называемым метеорологическим маршрутам судов (англ. weather routing). Основной задачей в этой области является поиск оптимального пути и скорости движения для заданного рейса в условиях динамически меняющихся ограничений (погодных условий, таких как ветер, высота и направление волн и т.п.). Данную тенденцию можно заметить на рис. 1, где отображено изменение количества статей в области weather routing за последние 60 лет [3].
Рис. 1. Повышение интереса к области weather routing [3]
Большинство существующих разработок в этой области основывается либо на классических алгоритмах поиска кратчайших путей в графе (таких как алгоритм Дейкстры [4, 5, 6, 7], А* [2, 8]), либо на оптимизационных и математических алгоритмах: метод динамического программирования [4], метод многокритериальной оптимизации [9, 10], задача вариационного исчисления [6, 9], задача нелинейного программирования [4, 11], метод изохрон [4, 12], эволюционный алгоритм [4, 9, 10]. Кроме того, в последние годы также возросло количество приложений искусственного интеллекта и машинного обучения [3]. В работе [13] упоминается, что в некоторых системах планирования маршрутов используется метод Монте-Карло.
Однако не было найдено ни одного исследования, опирающегося на идеи гексагональной растеризации карты, математической морфологии и поиске в ширину. Вследствие чего этот подход к решению проблемы weather routing рассматривается в данной работе.
✅ Заключение
Вопрос навигации судов был актуален с самого зарождения человеческой цивилизации. Плавание в океанских просторах всегда считалось опасным, в какой-то степени непредсказуемым предприятием. В данной работе был рассмотрен не встречавшийся ранее метод нахождения оптимального по времени маршрута, учитывающий динамически меняющиеся ограничения (например, погодные), основывающийся на гексагональной растеризации, алгоритме поиска в ширину и математической морфологии.
Были разработаны вспомогательные алгоритмы генерации случайных ограничений-многоугольников и их растеризации в гексагональном растре, а также непосредственно алгоритм поиска оптимальных маршрутов в условиях динамически меняющихся ограничений. Был проведён анализ получившегося алгоритма, показана практическая применимость на реальных тестовых данных о состоянии погоды. Разработанный алгоритм может быть адаптирован для любых движущихся в условиях динамически меняющихся ограничений объектов. Написана программная реализация, код которой находится в репозитории на github (ссылка: https: //github .com/4eckah7 8/weather_routing).
Подводя итоги, можно сказать, что маршрутизация по погодным условиям (англ. weather routing) - это хотя и относительно не новая концепция, но она довольно быстро получила широкое распространение и повышенное внимание ученых и практиков в последние годы. Возможно, это связано с возросшими вычислительными возможностями современных вычислительных систем.
В целом ожидается, что область погодных маршрутов и оптимизации рейсов будет всё более привлекать исследовательский интерес в будущем. Она достаточно широка, в ней используется множество подходов, о чем свидетельствует множество статей с порой совершенно различными разработанными методиками. Также присутствует явная экономическая выгода. Улучшение качества прогнозов погоды, доступность данных и всё увеличивающаяся вычислительная мощность открывают пути для дополнительных исследований по оптимизации погодных маршрутов. Можно с уверенностью сказать, что это перспективное поле для научных и коммерческих исследований.
Были разработаны вспомогательные алгоритмы генерации случайных ограничений-многоугольников и их растеризации в гексагональном растре, а также непосредственно алгоритм поиска оптимальных маршрутов в условиях динамически меняющихся ограничений. Был проведён анализ получившегося алгоритма, показана практическая применимость на реальных тестовых данных о состоянии погоды. Разработанный алгоритм может быть адаптирован для любых движущихся в условиях динамически меняющихся ограничений объектов. Написана программная реализация, код которой находится в репозитории на github (ссылка: https: //github .com/4eckah7 8/weather_routing).
Подводя итоги, можно сказать, что маршрутизация по погодным условиям (англ. weather routing) - это хотя и относительно не новая концепция, но она довольно быстро получила широкое распространение и повышенное внимание ученых и практиков в последние годы. Возможно, это связано с возросшими вычислительными возможностями современных вычислительных систем.
В целом ожидается, что область погодных маршрутов и оптимизации рейсов будет всё более привлекать исследовательский интерес в будущем. Она достаточно широка, в ней используется множество подходов, о чем свидетельствует множество статей с порой совершенно различными разработанными методиками. Также присутствует явная экономическая выгода. Улучшение качества прогнозов погоды, доступность данных и всё увеличивающаяся вычислительная мощность открывают пути для дополнительных исследований по оптимизации погодных маршрутов. Можно с уверенностью сказать, что это перспективное поле для научных и коммерческих исследований.
ИЛИ
Поиск аналога
📕 Список литературы
🖼 Скриншоты
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.