Введение 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
Задача поиска оптимального маршрута в условиях динамически меняющихся ограничений возникает практически повсеместно. Особенно в наши дни, когда ведутся активные наработки в области искусственного интеллекта: создание бытовых роботов-пылесосов, автопилотов (к примеру, компания «Яндекс» уже запустила экспериментальные такси без водителя в Москве [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 рассматривается в данной работе.
Вопрос навигации судов был актуален с самого зарождения человеческой цивилизации. Плавание в океанских просторах всегда считалось опасным, в какой-то степени непредсказуемым предприятием. В данной работе был рассмотрен не встречавшийся ранее метод нахождения оптимального по времени маршрута, учитывающий динамически меняющиеся ограничения (например, погодные), основывающийся на гексагональной растеризации, алгоритме поиска в ширину и математической морфологии.
Были разработаны вспомогательные алгоритмы генерации случайных ограничений-многоугольников и их растеризации в гексагональном растре, а также непосредственно алгоритм поиска оптимальных маршрутов в условиях динамически меняющихся ограничений. Был проведён анализ получившегося алгоритма, показана практическая применимость на реальных тестовых данных о состоянии погоды. Разработанный алгоритм может быть адаптирован для любых движущихся в условиях динамически меняющихся ограничений объектов. Написана программная реализация, код которой находится в репозитории на github (ссылка: https: //github .com/4eckah7 8/weather_routing).
Подводя итоги, можно сказать, что маршрутизация по погодным условиям (англ. weather routing) - это хотя и относительно не новая концепция, но она довольно быстро получила широкое распространение и повышенное внимание ученых и практиков в последние годы. Возможно, это связано с возросшими вычислительными возможностями современных вычислительных систем.
В целом ожидается, что область погодных маршрутов и оптимизации рейсов будет всё более привлекать исследовательский интерес в будущем. Она достаточно широка, в ней используется множество подходов, о чем свидетельствует множество статей с порой совершенно различными разработанными методиками. Также присутствует явная экономическая выгода. Улучшение качества прогнозов погоды, доступность данных и всё увеличивающаяся вычислительная мощность открывают пути для дополнительных исследований по оптимизации погодных маршрутов. Можно с уверенностью сказать, что это перспективное поле для научных и коммерческих исследований.
