ЭВРИСТИЧЕСКИЙ ПОИСК ОПТИМАЛЬНОГО МАРШРУТА СУДНА ПО СЕВЕРНОМУ МОРСКОМУ ПУТИ

• Main Authors: Акмайкин Денис Александрович, Клюева Светлана Федоровна, Салюк Павел Анатольевич
• Format: Text
• Language: unknown
• Published: Федеральное государственное бюджетное образовательное учреждение высшего образования «Государственный университет морского и речного флота имени адмирала С.О. Макарова» 2015
• Subjects: граф; кратчайший путь; оптимальный маршрут; эвристический алгоритм; алгоритм Флойда; оптимизация поиска пути; вектор оценок; безопасность мореплавания; Northern Sea Route
• Online Access: http://cyberleninka.ru/article/n/evristicheskiy-poisk-optimalnogo-marshruta-sudna-po-severnomu-morskomu-puti; http://cyberleninka.ru/article_covers/16025562.png

В работе рассматриваются вопросы оценки поиска оптимальных маршрутов судов с точки зрения затрат времени на переход, экономичности маршрута и его безопасности. Приведен анализ построения оптимального маршрута судна на основе приближенных алгоритмов и эвристической оценочной функции. В результате проведенного исследования был разработан и программным образом реализован эвристический алгоритм A2015. Работоспособность алгоритма показана на примере формирования оптимального маршрута судна для трассы Северного морского пути. Выполнена формализация постановки задачи. В работе представлена пошаговая реализация разработанного эвристического алгоритма построения оптимального маршрута судна. Представленная в статье программная реализация алгоритма А2015 включает сравнение его с классическими алгоритмами Дейкстры и Флойда-Уоршелла. Представленный алгоритм позволяет в некоторых случаях на порядок быстрее сформировать оптимальный маршрут судна для трассы морского пути в сравнении с классическими алгоритмами поиска пути на графе. Такой поход позволяет значительно сократить объем всех возможных вычислений и быстро получать возможные решения для оперативного анализа обстановки в заданном районе плавания. This paper deals the results of the research for constructing an optimal route for the ship in accordance with route time, economical aspects and safety if navigation. The analysis of the constructing of the optimal ship’s route based on the approximation algorithms and heuristic evaluation function presented in this paper. In result of work, a heuristic algorithm A2015 was formulate and was realized n software implementation. The efficiency of algorithm shown by the example of the formation optimal ships route for the Northern Sea Route. A statement of a problem formalized. The paper describes a step-by-step guide of execution of heuristic algorithm to constructing an optimal route of the ship. Presented in the article algorithm A2015 software implementation includes comparing it with the classical Dijkstra and Floyd-Warshall algorithms. The algorithm A2015 can in some cases much faster to generate the optimal ship’s route in a sea in comparison with the classical shortest path algorithms. This approach uses is possible to significantly reduce the amount of all possible amount of calculations, and operational get possible solutions for quick analysis of the situation in a given area of navigation.