Vessel route planning based on historical traffic data and model representations of computational geometry

Abstract

Статья посвящена проблеме безопасного движения судов в условиях насыщенного трафика. Рассматривается задача планирования маршрута перехода морского судна через акватории с интенсивным движением. При плавании в таких условиях судоводители придерживаются некоторой схемы движения, принятой на конкретной акватории. Эта схема может существовать как директивно, так и неформально, являясь обобщением коллективного судоводительского опыта. В последнем случае представляется продуктивным планирование маршрута на основе данных о движении других судов, находившихся на акватории ранее (та же идея лежит в основе методов задач «больших данных»). В работах, опубликованных ранее, такое планирование маршрута осуществлялось на основе кластерного анализа ретроспективных данных о движении судов, что предполагало разбиение акватории на участки и выделение в них характерных значений скоростей и курсов. Проблемой такого подхода является выбор параметров разбиения: их требуется задавать для каждой конкретной акватории отдельно. В настоящей работе предложен другой подход, когда граф возможных маршрутов строится на основе множества пересекающихся ломаных, каждая из которых представляет собой реализованный ранее маршрут. При этом каждому ребру графа приписывается мера его «желательности», характеризующая близость к нему других ребер. Кратчайший путь на взвешенном графе строится с учетом не только геометрической длины ребер, но и меры их «желательности». В статье рассматривается способ построения такого графа возможных маршрутов, делается оценка числа его вершин и ребер, даются рекомендации по выбору метода поиска кратчайшего пути на этом графе. Приводятся примеры планирования маршрутов на ряде реальных акваторий: Владивосток, Сангарский пролив. The paper is concerned with maritime safety. The problem of planning a route for a vessel crossing water areas with heavy traffic is considered. When sailing under such conditions, navigators follow a trajectory that is established in a specific water area. It can be defined officially or be accepted on an informal basis while representing collective navigation experience. If the latter, it seems productive to plan a route using the data on the traffic of other ships that crossed the water area earlier (the same idea underlies "big data" task methods). In the papers published earlier, such route planning was based on a cluster analysis of retrospective data on ship traffic, which involved dividing the water area into sections and highlighting characteristic values of speeds and courses in them. The problem with this approach was the choice of partitioning parameters which had to be set for each specific water area separately. In this paper, another approach is proposed, when the graph of possible routes includes a selection of the trajectories of individual ships that were previously implemented in the specific water area. This article further develops the methods for solving the problem of ship route planning in areas with heavy traffic. The proposed method is based on the formation of a possible route graph from a set of intersecting broken lines, each of which represents a route implemented earlier. Each edge of the graph is assigned a measure of its “popularity”, which characterizes the proximity of other edges to it. The shortest path on a weighted graph is constructed considering not only the geometric length of the edges, but also the measure of their “popularity”. The paper regards the formation of a possible route graph, a number of its nodes and edges is esteemed, recommendations as to how to select a method for defining the shortest path on its graph are provided. Examples of route planning for the Tsugaru Strait and the Seaport of Vladivostok are provided.

Topics & Concepts