ЭВРИСТИЧЕСКИЙ ПОИСК ОПТИМАЛЬНОГО МАРШРУТА СУДНА ПО СЕВЕРНОМУ МОРСКОМУ ПУТИ
Аннотация
В работе рассматриваются вопросы оценки поиска оптимальных маршрутов судов с точки зрения затрат времени на переход, экономичности маршрута и его безопасности. Приведен анализ построения оптимального маршрута судна на основе приближенных алгоритмов и эвристической оценочной функции. В результате проведенного исследования был разработан и программным образом реализован эвристический алгоритм A2015. Работоспособность алгоритма показана на примере формирования оптимального маршрута судна для трассы Северного морского пути. Выполнена формализация постановки задачи. В работе представлена пошаговая реализация разработанного эвристического алгоритма построения оптимального маршрута судна. Представленная в статье программная реализация алгоритма А2015 включает сравнение его с классическими алгоритмами Дейкстры и Флойда-Уоршелла. Представленный алгоритм позволяет в некоторых случаях на порядок быстрее сформировать оптимальный маршрут судна для трассы морского пути в сравнении с классическими алгоритмами поиска пути на графе. Такой поход позволяет значительно сократить объем всех возможных вычислений и быстро получать возможные решения для оперативного анализа обстановки в заданном районе плавания.
Ключевые слова
граф, кратчайший путь, оптимальный маршрут, эвристический алгоритм, алгоритм Флойда, оптимизация поиска пути, вектор оценок, безопасность мореплавания, Floyd algorithm
Читать полный текст статьи: PDF
Список литературы
Акмайкин Д. А. Проект системы оперативного анализа и оптимизации движения морских судов / Д. А. Акмайкин, С. Ф. Клюева, П. А. Салюк // Вестник Государственного университета морского и речного флота имени адмирала С. О. Макарова. - 2015. - № 1. - С. 229-236.
Akmaykin D. Solaris’ information system for ship’s navigation, using operational analysis of shipboard and satellite remote sensing data of hydrosphere and atmosphere / D. Akmaykin, D. Homenko, P. Salyuk, I. Stepochkin, K. Smirko // SPIE Proceedings, Ocean Remote Sensing and Monitoring from Space. - 2014. - № 9261-41. - С. 1-10.
Васьков А. С. Взаимосвязь зон навигационной безопасности судна/ А. С. Васьков, В. А. Васьков, А. А. Мироненко // Вестник Государственного морского университета имени адмирала Ф. Ф. Ушакова. - 2013. - № 2. - С. 18-21.
Макоско А. А. Гидрометеорологическое обеспечение плавания по трассам Северного морского пути / А. А. Макоско // Арктика: экология и экономика. - 2013. - № 3. - С. 40-49.
Мироненко A. A. Формирование маршрута судна в автоматизированных навигационных комплексах: автореф. дис. … канд. техн. наук: 05.22.19. - СПб., 2002. - 24 с.
Некрасов С. Н. Комбинированный метод оценки навигационной безопасности при плавании по внутренним водным путям / С. Н. Некрасов, A. A. Прохоренков // Вестник Государственного университета морского и речного флота имени адмирала С. О. Макарова. - 2011. - № 1. - С. 106-108.
Прохоренков A. A. Применение ситуационного метода оценки навигационной безопасности при плавании по внутренним водным путям / А. А. Прохоренков // Вестник Государственного университета морского и речного флота имени адмирала С. О. Макарова. - 2011. - № 1. - С. 91-95.
Берштейн Л. С. Использование темпоральных графов как моделей сложных систем / Л. С. Берштейн, А. В. Баженюк // Известия ЮФУ. Технические науки. - 2010. - № 4 (105). - С. 198-203.
Kostakov V. Temporal graphs / V. Kostakov // Proc. of Physica A: Statistical Mechanics and its Applications. - 2008. - V. 388. - Pp. 1007-1023.
Chapman W. L. System Design Is an NP-Complete problem / W. L. Chapman, J. Rozenblit, A. T. Bahill // Systems Engineernig. - 2001. - V. 4. - № 3. - Pp. 222-229.
Костюк Ю. Л. Приближённые алгоритмы решения сбалансированной задачи k коммивояжёров / Ю. Л. Костюк, М. С. Пожидаев // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. - 2008. - № 1. - С. 106-112.
Частикова В. А. Разработка и сравнительный анализ эвристических алгоритмов для поиска наименьшего гамильтонова цикла в полном графе / В. А. Частикова, К. А. Власов // Фундаментальные исследования. - 2013. - № 10-1. - С. 63-67.
Об авторах
Акмайкин Денис Александрович - кандидат физико-математических наук, доцент
МГУ им. адм. Г. И. НевельскогоКлюева Светлана Федоровна - кандидат технических наук
МГУ им. адм. Г.И. НевельскогоСалюк Павел Анатольевич - кандидат физико-математических наук
ТОИ ДВО РАН
