РЕЗУЛЬТАТЫ ИССЛЕДОВАНИЙ ПРОБЛЕМЫ МОДЕЛИРОВАНИЯ ГРАФА МАРШРУТА СУДНА НА ОСНОВЕ АЛГОРИТМОВ КЛАСТЕРИЗАЦИИ
Аннотация
В современной теории графов для исследователей актуален класс задач, связанных с формированием графа, построением его вершин и ребер на основе заданных условий и большого числа исходных данных. Такие задачи относят к классу нереализуемых задач. Методы искусственного интеллекта, кластерного анализа, применение эвристических и эволюционных алгоритмов совместно с новыми компьютерными технологиями позволяют решать подобные задачи наиболее эффективным образом. Задача формирования графа маршрута движения судна относится к классу таких задач. Эвристика заключается в возможности применения результатов кластеризации исходной цифровой базы данных как основы для формирования вершин и ребер графа. Данная задача является предметом рассмотрения статьи. В статье используется цифровая база района плавания, которая включает отметки глубин, высот и мелей. Метод кластеризации осуществляется на базе метрики, учитывающей расстояние между точками на карте и разность глубин. Приведены численные значения параметров кластеризации и числовые значения расчета критерия качества кластеризации для различных значений коэффициентов метрики. Разработан, реализован программно и подробно описан алгоритм кластеризации. Приведены результаты программного моделирования алгоритма на участке, характеризующимся извилистой береговой чертой, наличием мысов, мелей, бухт и заливов, а также распределением островов в районе построения маршрута. На основе кластеризации выполнено формирование графа путей движения судна. Приведен алгоритм построения вершин и ребер графа. Программная модель позволяет визуализировать исходную цифровую базу данных и полученные результаты. В заключение указаны основные необходимые направления для дальнейших исследований.
Ключевые слова
кластеризация, метрика, качество кластеризации, путь судна, электронная навигационная карта
Читать полный текст статьи: PDF
Список литературы
Лобастов В. М. Электронные картографические системы в судовождении: учеб. пособие / В. М. Лобастов. - Владивосток: Изд-во МГУ им. Г. И. Невельского, 2009. - 167 с.
Вагущенко Л. Л. Судовые навигационно-информационные системы: учеб. пособие / Л. Л. Вагущенко. - Одесса: Феникс, 2004. - 302 с.
Клюева С. Ф. Моделирование маршрута движения судна на основе алгоритмов кластеризации / С. Ф. Клюева, А. Д. Акмайкин, П. А. Салюк // 2016 International Siberian Conference on Control and Communications (SIBCON). Proceedings. National Research University Higher School of Economics. Russia, Moscow, May 12 - 14, 2016. - IEEE Catalog Number: CFP13794. - CDR.
Клюева С. Ф. Применение алгоритмов кластеризации в задачах навигации по глубинам морского дна / C. A. Клюева // Евразийское научное объединение. - 2016. - Т. 1. - № 4 (16). - С. 4-9.
Gower J. C. A General Coefficient of Similarity and Some of Its Properties / J. C. Gower // Biometrics. - 1971. - Vol. 27. - No. 4. - Pp. 857-871. DOI: 10.2307/2528823.
Ali B. B. K-means clustering based on gower similarity coefficient: A comparative study / B. B. Ali, Y. Massmoudi // Modeling, Simulation and Applied Optimization (ICMSAO), 2013 5th International Conference on. - IEEE, 2013. - Pp. 1-5. DOI: 10.1109/ICMSAO.2013.6552669.
Atev S. Clustering of vehicle trajectories / S. Atev, G. Miller, N. P. Papanikolopoulos // IEEE Transactions on Intelligent Transportation Systems. - 2010. - Vol. 11. - Is. 3. - Pp. 647-657. DOI: 10.1109/TITS.2010.2048101.
Savchuk T. O. Information technology of clustering problem situations in computing and office equipment / T. O. Savchuk, S. I. Petrishyn, P. Kisała, B. Imanbek, S. Smailova // 16th Conference on Optical Fibers and Their Applications. - International Society for Optics and Photonics, 2015. - Pp. 98161W-98161W-8. DOI:10.1117/12.2229126.
Бирюков А. С. Решение задач кластерного анализа коллективами алгоритмов / А. С. Бирюков, В. В. Рязанов, А. С. Шмак // Вычислительная математика и математическая физика. - 2008. - Т. 48. - № 1. - С. 176-192.
Goldberg A. V. Computing the shortest path: A-search meets graph theory / A. V. Goldberg, C. Harrelson // Proceedings of the sixteenth annual ACM - SIAM symposium on Discrete algorithms. - Philadelphia, PA, USA: Society for Industrial and Applied Mathematics, 2005. - Pp. 156-165.
Поляков И. В. Алгоритмы поиска путей на графах большого размера / И. В. Поляков, А. А. Чеповский, А. М. Чеповский // Фундаментальная и прикладная математика. - 2014. - Т. 19. - № 1. - С. 165-172.
Akmaykin D. A. Optimization of the search algorithm for the shortest route / D. A. Akmaykin, S. F. Klyueva, O. A. Bukin, P. A. Salyuk // “Stability and Control Processes” in Memory of VI Zubov (SCP), 2015 International Conference. - IEEE, 2015. - Pp. 545-548.
Акмайкин Д. А. Эвристический поиск оптимального маршрута судна по Северному морскому пути / Д. А. Акмайкин, С. Ф. Клюева, П. А. Салюк // Вестник Государственного университета морского и речного флота имени адмирала С. О. Макарова. - 2015. - № 5 (33). - С. 55-62.
Акмайкин Д. А. Проект системы оперативного анализа и оптимизации движения морских судов / Д. А. Акмайкин, С. Ф. Клюева, П. А. Салюк // Вестник Государственного университета морского и речного флота имени адмирала С. О. Макарова. - 2015. - № 1 (29). - С. 229-236.
Фирсов Ю. Г. Основные требования к обеспечению качества современной батиметрической (топографической) съемки / Ю. Г. Фирсов // Вестник Государственного университета морского и речного флота имени адмирала С. О. Макарова. - 2014. - № 3 (25). - С. 171-179.
Фирсов Ю. Г. Новые методы пространственной визуализации результатов инженерной батиметрической съемки / Ю. Г. Фирсов, И. В. Кожухов // Вестник Государственного университета морского и речного флота имени адмирала С. О. Макарова. - 2014. - № 2 (24). - С. 17-23.
Об авторах
Акмайкин Денис Александрович - кандидат физико-математических наук, доцент.
МГУ им. адм. Г.И. НевельскогоКлюева Светлана Федоровна - кандидат технических наук
МГУ им. адм. Г.И. НевельскогоСалюк Павел Анатольевич - кандидат физико-математических наук
ТОИ ДВО РАН
