Ships route planning based on multidimensional clustering of traffic data
Authors: Артемьев А.В. , Гриняк В.М. , Девятисильный А.С. , Дудко Д.О. , Сазонтова М.Д. 
Published: June 2024

Статья посвящена проблеме обеспечения безопасности движения судов на морских акваториях. В условиях насыщенного трафика навигационная безопасность может быть обеспечена только при соблюдении судами определённой схемы движения. В работе ставится задача планирования маршрута судна на акватории с интенсивным движением таким образом, чтобы он соответствовал практике судоходства, сложившейся в конкретном районе. В том случае, если правила и ограничения движения существуют неформально, перспективным путём планирования маршрута является обращение к ретроспективным данным о движении с использованием идей машинного обучения. Предлагаемый в работе метод планирования маршрутов основан на кластеризации данных о движении судов. Выделенные кластеры представляют собой области в трёх- или четырёхмерном фазовом пространстве с близкими значениями скоростей и курсов судов. На основе полученной таким образом информации формируется граф возможных маршрутов судна, вершины которого соответствуют границам выделенных кластеров и областям их пересечения, а ребра – выделенным характерным курсам судов. Каждая точка в многомерном фазовом пространстве характеризуется координатами, курсом и скоростью судна, вводится метрика расстояния между точками, для кластеризации данных о движении используется плотностный алгоритм пространственной кластеризации (DBSCAN). Обсуждается вычислительная сложность рассматриваемой задачи в условиях реальных акваторий, делается вывод о возможности конструктивного решения задачи стандартными вычислительными средствами. Приводится пример решения задачи на реальных данных о движении судов в Сангарском проливе, который свидетельствует о пригодности использования разработанных алгорит-мов в практике судовождения.
The paper is devoted to the problem of ensuring the safety of vessel traffic in marine areas. In conditions of heavy traf-fic, navigational safety can be ensured only if ships adhere to a certain traffic pattern. The work sets the task of planning a vessel's route in water areas with intense traffic in such a way that it corresponds to the shipping practice that has de-veloped in a particular area. In the event that traffic rules and restrictions exist informally, a promising way to plan a route is to use historical traffic data using machine learning ideas. The route planning method proposed in this work is based on clustering data on vessel movement. The selected clusters represent areas in three- or four-dimensional phase space with similar speeds and courses of ships. Based on the information obtained in this way, a graph of possi-ble vessel routes is formed, the vertices of which correspond to the boundaries of the selected clusters and the areas of their intersection, and the edges correspond to the selected characteristic courses of the vessels. Each point in the mul-tidimensional phase space is characterized by the coordinates, course and speed of the vessel, a distance metric be-tween points is introduced, and a density spatial clustering algorithm (DBSCAN) is used to cluster motion data. The computational complexity of the problem under consideration in the conditions of real water areas is discussed, and a conclusion is drawn about the possibility of a constructive solution to the problem using standard computing tools. An example of solving the problem using real data on the movement of ships in the Tsugaru Strait is given, which indicates the suitability of using the developed algorithms in navigation practice.