The Concept of Determining a Ship’s Route Based on the Capability Plot and Dijkstra’s Algorithm—Finding the Ship’s Route Between Anchorages

1. Introduction

The development of modern navigation, in particular the determination of optimal routes for ships, has long attracted the attention of researchers and practitioners in the field of maritime transport. Contemporary navigation faces challenges arising from the increasing number of ships on the seas and oceans, the growing demand for efficient maritime transport, and the increasingly complex aspects related to safety at sea and environmental protection. In response to these challenges, scientists and engineers have developed methods and algorithms to effectively determine ship passage routes, taking into account a range of factors such as weather conditions, the movement of other vessels, water depth and environmental constraints.

The first attempts to use computers to determine shipping routes date back to the 1950s and 1960s, when George Hanssen wrote a paper on the subject [1]. The author proposed a special program to increase the safety of naval vessels by determining passage routes based on predictable hydrometeorological conditions. At the time when the first computers capable of performing analytical calculations appeared, weather charts, ocean current charts and wind charts were used to determine the passage routes of ships, as well as the methods introduced by the authors [2,3] and maps showing the strength of sea waves in specific areas. In the years that followed, technological advances made it possible to use more sophisticated techniques and algorithms.

There are three main types of algorithms, and their various variations, that can be found in the contemporary literature related to the determination of ship passage routes. These include genetic algorithms, graph search algorithms and swarm algorithms.

Genetic algorithms are inspired by biological processes and include concepts such as natural selection, recombination and mutation. When analyzing the literature related to this type of algorithm, several primary applications can be distinguished:

Finding a safe route in areas with limited maneuverability: An example of using a genetic algorithm to determine a route between islands and reefs is presented in [4]. The authors of this publication found that traditional algorithms, such as ant colony algorithms, did not perform well in this context, so they proposed their own algorithm using environmental information. Another approach to determining a ship’s route in restricted waters was presented by the authors of [5]. They focused on a parallel genetic algorithm, and additionally, considered criteria related to water depth and travel time.
Determining routes where the criteria include minimizing energy consumption, travel time, etc.: This type of approach was taken by the authors of publications [6,7]. They presented an algorithm using elements of particle swarm optimization and genetic algorithms to determine the route. This approach successfully optimized fuel consumption.
Determination of collision avoidance routes: This category includes publications that do not directly address the determination of a route from a starting point to an end point, but instead present algorithms that adapt local segments of the route to the new conditions surrounding the ship, for example, to perform a collision avoidance maneuver. Examples of publications related to this type of algorithm are [8,9,10]. The authors presented different approaches to collision avoidance maneuvers, ranging from harbor operations to applications related to autonomous vehicles.

Another type of algorithm used to determine ship passage routes are graph search algorithms. These algorithms are used to search, analyze and navigate through graphs, which are data structures containing nodes and edges between them. Basic graph-related techniques such as Breadth-First Search (BFS) and Depth-First Search (DFS) are used in cases where the time to generate a passage route is more critical than its optimization. An example of a publication where the authors use these methods to determine routes for small vessels is [11]. The authors showed that using BFS and DFS algorithms generated routes for vessels faster than using genetic algorithms, although the routes were less accurate.

A-star (A*), D-star (D*) and Dijkstra’s algorithms are used to determine passage routes using graph search algorithms. A challenge with these methods is how to determine the transition weights between individual nodes. In the classical approach to the problem, the weight can be taken as the distance between points. In this case, the resulting route is optimized on the basis of distance. Such criteria have been used, for example, by the authors of publications [12,13,14,15].

An alternative approach to determining the transition weights between individual points in the graph was presented by the authors of publications [16,17], who used data collected from the Automatic Identification System (AIS) to develop a graph. In the first publication, the transition weights were inversely proportional to the number of ships passing between the vertices. In the second, the authors used Delaunay triangulation analysis to calculate transition weights. Publication [18] explored the potential use of graph search algorithms in conjunction with neural networks to predict fuel consumption and develop a route that minimizes energy consumption. In addition to solutions that focus on finding the shortest or least congested routes, the literature also includes studies that consider hydrometeorological conditions such as wave height, wind speed and ocean currents. Examples of such publications are [19,20,21,22], where the authors used the A* algorithm and weather maps to determine a safe passage route for the ship.

The final type of algorithm that is most commonly used to determine ship passage routes are swarm algorithms. Swarm algorithms are a category of optimization techniques inspired by the social behavior of animals such as insects, birds or fish. In nature, animals often interact in groups, forming swarms, flocks and schools, and their coordinated actions can lead to the solution of complex problems. Swarm algorithms include the following:

Ant colony algorithms: These are inspired by how ants find the shortest path to a food source. In ant colony algorithms, agents (virtual ants) explore the solution space and leave pheromone trails that guide other ants to optimal solutions.
Particle swarm algorithms: These are based on the behavior of schools of fish or flocks of birds. In particle swarm algorithms, particles (points in the solution space) move through the search space, guided by their own experience and information from other particles, to find an optimal solution.
Bee-inspired algorithms: These algorithms mimic the behavior of bees foraging for food, where bees identify the best food sources and recruit other bees to exploit those sources.
Firefly algorithms: The main principle of operation is the attraction of fireflies based on their brightness, which represents the quality of a given solution to the problem. The brighter the firefly (the better the solution), the greater the attraction it exerts on other fireflies. The brightness of a firefly depends on the objective function and decreases with distance: fireflies closer together are more attracted than those further apart. Fireflies with lower brightness move towards brighter ones, meaning that the algorithm iteratively improves its solution.

In the literature dedicated to swarm algorithms, it is evident that all the aforementioned types find applications in determining ship passage routes. An example publication where the authors demonstrated how ant-inspired algorithms can be used to improve the efficiency of maritime navigation is [23]. The authors integrated the Electronic Chart Display and Information System (ECDIS) with a Geographic Information System (GIS) platform to model the maritime space. The algorithm simulates the behavior of ants searching for the optimal path to a food source, where the ants (ships) explore the search space to find the safest route. Experimental results showed that routes determined using the ant algorithm were more efficient than those determined using the great circle method. However, the authors of publication [24] had a different perspective on ant algorithms. In their work, they argued that the classical ant algorithm has drawbacks, such as a tendency to get stuck in local minima and low convergence speed, which affect the quality and speed of route determination. In addition to determining passage routes for ships, ant algorithms can also be used for various applications, including route planning for mobile robots [25,26], determining passage routes for units involved in maritime rescue missions [27,28], and planning collision avoidance routes [29].

In contrast to ant algorithms, particle swarm algorithms are characterized by faster convergence and the ability to optimize multiple variables. This property has been demonstrated in [30]. The authors combined the particle swarm algorithm with Dijkstra’s algorithm to find the shortest route between start and end points, taking into account obstacles. The algorithm presented in this publication uses a cost function based on the total length of the route. Another example of a publication focusing on ship route planning and extending the particle swarm algorithm is [31]. In this paper, the authors introduced the concept of Chaos Multi-Population Particle Swarm Optimization (CMPSO), which is an improved particle swarm algorithm enhanced by chaos theory.

Bee-inspired swarm algorithms also have applications in route optimization, particularly in the context of maritime navigation. They use mechanisms inspired by the way bees search for and share information about food sources. This gives these algorithms a high capacity to explore the solution space and effectively avoid local minima. The use of bee algorithms in route optimization for surface and underwater vessels allows dynamic adaptation to changing conditions, such as obstacles along the route or variations in the weather, making them valuable tools for managing the safety and efficiency of maritime navigation. This feature was exploited by the authors of [32], who presented an algorithm that determines an escape route for submarines to avoid detection by hostile vessels.

This paper demonstrates the use of a modified version of Dijkstra’s algorithm and position-keeping Capability Plots (CP) to determine a passage route that minimizes the impact of environmental forces on the ship’s hull, thereby reducing energy consumption. This method has been developed for autonomous vessels equipped with a positioning system based on a set of anchors. For such vessels, the challenge is to move from the starting point to the pre-planned anchorage area. As the thrusters are not involved in the positioning operation, their power is significantly lower than the thrusters used in Dynamic Positioning (DP) systems, resulting in reduced maneuverability. For this reason, the ship’s passage route should be chosen in such a way as to minimize the influence of disturbance factors. The verification of the presented algorithm was carried out using a simulator developed in the Unity3D environment.

3. Route Determination for Ship Passage Using Capability Plots

The determination of a vessel’s route between two geographical points (the starting and ending points of the route) is one of the initial tasks in planning any maritime operation, for example as an anchoring operation at an anchorage site. Vessels designated to keep their position at anchor are typically equipped with thruster systems that are considerably less powerful than those on vessels equipped with a DP system. This difference means that in higher wind speeds, they cannot maneuver freely using only their thrusters, resulting in increased energy consumption and a prolonged travel time along the route. To minimize the impact of environmental forces on the vessel’s hull and thereby reduce the energy consumption, the use of the vessel’s CP and Dijkstra’s algorithm can be advantageous.

3.1. The Concept of the Algorithm

The implemented algorithm aims to determine the route for a vessel equipped with a set of anchors, between its current position and the designated location for deploying the first anchor. Figure 5 shows a fragment of the anchor planning tool, together with the navigation scenario that will demonstrate the operation of the algorithm.

The diagram above includes two points: A, the starting point, and B, the endpoint. It is assumed that the designated passage route should end at the location of the first anchor drop. The distance between the points is 2.4 NM.

The first step in determining the ship’s passage route is to define the area in which the ship can maneuver. For such an assumed area, a grid of waypoints is generated. The density of these points is defined by the user. Figure 6 shows the navigational situation from Figure 5 with the waypoints included. Each point in the matrix is represented by its latitude and longitude.

When preparing the anchoring operation, the ship’s crew arrives at the designated anchorage area and makes a preliminary assessment before analyzing anchor placement and maneuvering strategies. For this reason, the presented algorithm starts to determine the route from the point closest to the ship’s current position.

For the purpose of demonstrating the algorithm’s function, a waypoint density of 10 was assumed, resulting in a matrix where each row and column contains 11 points (with numbering starting from 0). It was also assumed that the wind speed acting on the ship is 10 m/s, with a direction of 20°.

The considered case of route determination is a classic graph search problem. One of the popular methods for solving such problems is the use of Dijkstra’s algorithm. Dijkstra’s algorithm finds the shortest path between two vertices in a weighted graph, where edges are assigned numerical values known as weights. As a greedy algorithm, Dijkstra’s approach makes locally optimal choices at each stage, leading to a globally optimal solution. However, for the algorithm to function correctly, the graph must not contain edges with negative weights.

The individual transition weights between points in the matrix are obtained by converting the ship’s CP into a series of coefficients based on the wind angle of attack on the ship’s hull. This conversion is performed using Equation (27).

where F_α(α)—resultant environmental force currently acting on the ship’s hull at angle α; F_max—maximum resultant environmental force that can act on the ship’s hull.

The maximum value of the environmental force that can act on the ship’s hull is determined during the creation of the CP. For the ship presented in Section 2, the maximum environmental force is 320 kN. Figure 7 illustrates the transition weights for individual points, depending on the wind impact angle.

The next step after defining the table shown in Figure 7 is to define the transition matrix between individual points. This matrix specifies which neighboring points each current point is connected to and the cost of moving to each of them. To determine the relationships between points (each point to every other point), a matrix is created where the rows represent the current point being evaluated by the algorithm and the columns represent potential neighbors. In this case, the matrix has the following dimensions:

[number of waypoints × number of waypoints]

In the case of the navigational situation shown in Figure 5, the matrix has dimension [121 × 121]. The individual points in the transition matrix have been defined according to the order shown in Figure 8.

During the initialization of the table, all transition weights are set to a value of 10, indicating that there is no passage between the respective points. Next, for each point, all neighboring points are determined, the transition weights between them are calculated, and the values are entered into the appropriate locations in the transition matrix. To illustrate the method for determining transition weights, Figure 9 shows a section of the waypoint grid with designated weights between points. In calculating the individual values, a wind direction of 20 degrees relative to north was assumed.

A section of the table with completed transition weights is shown in Figure 10. Due to limited space, the numerical values in the table have been rounded to two decimal places. The full values are available in Figure 7.

The table should be interpreted as follows:

Starting from point 0 (row 0), the transition cost to point 1 is 0.3095, to point 11 is 0.0533 and to point 12 is 0.1937. The transition cost to all other points is 10, as there is no connection between point 0 and those points. The transition cost from point 0 to itself is also 0.

With the weight table defined, the ship’s passage route can be determined using Dijkstra’s algorithm. The Python code for the algorithm is presented as Algorithm 1:

Algorithm 1: Dijkstra algorithm

def dijkstra(graph, start):
    # Initialization of weights to all vertices as 10
    distances = {vertex: 10 for vertex in graph}
    # Weight to itself set to 0
    distances[start] = 0

    # Initialization of the priority queue
    priority_queue = [(0, start)]

    while priority_queue:
        # Retrieving the vertex with the smallest sum of weights
        current_distance, current_vertex = heapq.heappop(priority_queue)

        # Skip if the current sum of weights is bigger
        if current_distance > distances[current_vertex]:
            continue

        # Iteration over the neighbors of the current vertex
        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight

            # Updating the sum of weights if a shorter path is found
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

return distances

3.2. Ship Route Without Using the Algorithm

From the navigational scenario shown in Figure 5, it can be inferred that the distance between the current position of the ship and the anchoring point is 2.4 NM (approximately 4.5 km). Over such a short distance, manual control with a constant course can be used to reach the endpoint, as illustrated in Figure 11.

To determine the impact of environmental forces on a ship moving on a course of 35° over a distance of 4500 m, a simple coefficient was introduced to enable later comparison with the route determined by the algorithm. The coefficient is expressed as follows:

$T = \sum_{i = 1}^{n} d_{i} \cdot k_{i}$

(28)

where T—route cost function [-]; n—number of transitions between waypoints [-]; i—current transition between waypoints [-]; d—distance between waypoints March; k—cost of transition between waypoints [-]

In Equation (28), the cost of transition between waypoints is read from the table shown in Figure 6.

For the navigational scenario depicted in Figure 11, after substituting the distance values between points and the transition costs from Figure 7 (taking into account wind direction and the ship’s course), the route cost function yielded a value of 846.

The energy consumption required to navigate the route shown in Figure 11 can be determined from the thruster data (Table 2) and the ship information (Table 1). The total energy consumption is given in Table 3.

In the table above:

Phase—current route segment.
S—distance between points.
V—speed of the ship.
t—the duration of the navigation of the given segment.
Course—ship’s course.
True wind angle—angle of wind impact on the vessel.
Env. Force vector—environmental forces affecting the vessel over a given distance.
Sum of thrust—thrust generated by propellers.
Fuel consumption—fuel consumption per route section.
Energy consumption—energy consumption per route section.

3.3. Route Determined Using Dijkstra’s Algorithm and the Capability Plot

The passage route determined by Dijkstra’s algorithm for the navigational scenario presented in Figure 5 is shown in Figure 12.

In the figure above, the starting point of the determined route is marked in red, and as each waypoint gets closer to the destination, the color gradually shifts to green. The final passage route is presented in Figure 13.

The cumulative weight of transitions for the identified route is 0.8476, which is the lowest value obtainable given the parameters of the anchorage. It is possible to find alternative routes that yield the same sum, however, from the algorithm’s operational perspective, there is no difference between them.

The value of the route cost function is presented in Table 4.

For the route determined by the algorithm, the value of the route cost function was 747, approximately 13% lower than when the ship travels directly to the endpoint.

The energy consumption in the above case can be determined in a similar way to the direct route to the endpoint. Table 5 shows an analysis of the energy consumption for the route determined by the algorithm, based on the current route segment.

The energy consumption for the route determined by the algorithm was 4231.127 [kWh], which is 7.58% less than the direct route to the end point.

3.4. Other Examples of Determined Routes

The algorithm presented in the publication can be used to determine routes for different hydrometeorological conditions. Below are some examples of routes determined, together with information on the specific weather conditions for which they were generated.

3.4.1. Navigation Scenario #1

In the navigation scenario shown in Figure 14, the route determined by the algorithm to the first anchorage point is presented. The route has been generated based on environmental condition data for the area covered by the anchor plan:

wind speed: 25 m/s.
true wind direction: 350°.
sea current speed: 1 m/s.
true sea current direction: 20°.

To determine the route cost function, new transition weights between waypoints must be calculated (the wind speed has changed from 10 m/s to 25 m/s). The new values are shown in Figure 15.

The route cost function is shown in Table 6. To show only the cost of the route determined by the algorithm, the table does not include the cost of reaching the starting point.

The cost of the route function for the first scenario, when the ship travels straight to the destination, is about 1261, which is approximately 8.6% more than for the route determined by the algorithm. In order to compare the energy consumption when the ship travels directly to the destination with that when it follows the route determined by the algorithm, an energy consumption analysis was carried out, the results of which are presented in Table 7 and Table 8. To illustrate only the difference between the algorithmic route and the direct route to the endpoint, the first waypoint on the grid was set as the starting point (A) and the green waypoint on the grid was set as the endpoint (B).

During the route directly to the destination, energy consumption was 5062.43 [kWh].

The energy consumption analysis showed that the energy consumption for the route determined by the algorithm was 4848.06 [kWh], 6.36% less than for the direct route to the destination.

3.4.2. Navigation Scenario #2

Navigational scenario #2 is similar to scenario #1. Again, a passage route to the first anchoring point was determined (Figure 16) based on the hydrometeorological data for the anchorage area:

wind speed: 25 m/s.
true wind direction: 90°.
sea current speed: 1 m/s.
true sea current direction: 20°.

Using the transition weights from Figure 15, the route cost function can be determined (Table 9). In the analysis of the route cost function, the cost of reaching the first waypoint was again excluded.

The cost of the route function for the first scenario, when the ship travels straight to the destination, is about 1131, which is approximately about 4.8% more than for the route determined by the algorithm.

For the second scenario, an energy consumption analysis was also carried out using the same assumptions as for the first scenario. The results are shown in Table 10 and Table 11.

During the route directly to the destination, energy consumption was 5773.44 [kWh].

In Scenario 2, the energy consumption for the route determined by the algorithm was 5426.18 kWh, resulting in a 6% reduction in energy consumption compared to the direct route.

3.4.3. Navigation Scenario #3

The final navigation scenario illustrates a situation where the vessel is within the waypoint grid when determining the passage route. In this case, the vessel does not start from the edge of the waypoint grid, but from the nearest adjacent point, as shown in Figure 17. The environmental conditions at the anchorage have been taken into account when determining the passage route:

wind speed: 10 m/s.
true wind direction: 75°.
sea current speed: 0.5 m/s.
true sea current direction: 20°.

In the above scenario, the transition weights shown in Figure 7 (for a wind speed 10 m/s) should be used to determine the route cost function. Table 12 shows the calculated route cost function.

The cost of the route function for the first scenario, when the ship travels straight to the destination, is about 598, which is approximately about 12.4% more than for the route determined by the algorithm.

The energy consumption analysis for the third case is shown in Table 13 and Table 14. As in the previous two scenarios, the start point (A) is the red point on the waypoint grid, while the end point (B) is the green point.

During the route directly to the destination, energy consumption was 3174.81 [kWh].

In Scenario 3, the energy consumption for the route determined by the algorithm was 2642.28 kWh, resulting in a 16.7% reduction in energy consumption compared to the direct route.

4. Discussion

Section 3 presents the concept of an algorithm that determines a local passage route based on local hydrometeorological conditions and knowledge of the ship’s capability plot. The algorithm works by dividing the area through which the route is to pass into smaller squares (e.g., an area of 10.2 km² is shown in the publication) where environmental conditions are assumed to be constant, and then determining the route through each square. When moving from one area to the next, the route is recalculated based on the new environmental conditions. Despite the simplicity of the algorithm’s structure, several potential limitations to its application were identified during implementation:

The ship’s capability plot must be available. As mentioned in the publication, any DP 2 or higher vessel is required to have it, but if the route is being determined for a DP 1 vessel or one without such a system, the capability plot would need to be calculated independently.
If the route needs to be updated during operation, the vessel must monitor wind speed in real time and measure or estimate the speed of the sea current.
The speed of route calculation also depends on the programming language used. The algorithm described in the paper was written in Python and also used as part of code written in C#. Both are high-level languages. If the algorithm were implemented in C or C++, shorter route generation times could be achieved. Currently, the times are as follows: for a 6 × 6 grid—0.05 s, for an 11 × 11 grid—0.36 s, for a 16 × 16 grid—0.47 s, and for a 21 × 21 grid—0.85 s.

This publication also presents a comparison of the ship’s passage routes for two cases: a direct route from the starting point to the end point, and the algorithm-determined route. The comparative analysis showed that along the route determined by the algorithm, environmental forces exerted 13% less stress on the ship’s hull, resulting in a 7.5% reduction in energy consumption. In addition, three other examples of routes determined by algorithm were presented. In two cases, a 6% reduction in energy consumption was achieved compared to the direct route to the destination, and in one case, environmental conditions were found that allowed a route with a 16% reduction in energy consumption.

Theoretically, the presented algorithm has no limitations regarding the maximum length of the determined route, provided that real-time data on wind and ocean currents are available. Unfortunately, during the route determination studies, it was not possible to determine a route beyond a single area of uniform environmental conditions because there was no way to introduce multiple changes in hydrometeorological conditions along the route. It was decided to demonstrate the functionality of the algorithm using the example of a vessel that needs to reach an anchorage. Such vessels do not travel very long distances, so it was possible to consider their entire operational area as one with consistent environmental conditions.

The studies showed that the presented algorithm could be used in the future for autonomous control of vessels that have to anchor according to a pre-planned anchorage layout.

5. Conclusions

The determination of ship passage routes plays a crucial role in maritime management, contributing to improved efficiency, enhanced safety and protection of the marine environment. By properly defining a passage route, it is possible to avoid potentially dangerous areas such as shoals or reefs, significantly reducing the risk of collisions, breakdowns and other incidents that threaten both the crew and the vessel. Routing systems and algorithms should also take into account changing sea conditions, monitoring wind, currents and waves and updating the route as necessary.

This paper presents a method for planning a ship’s passage route using capability plots and an algorithm based on Dijkstra’s algorithm. By using these plots to determine transition weights between points, it was possible to find a route that minimized the impact of wind on the ship’s hull. However, this does not mean that the chosen route meets other criteria such as minimizing travel time or being the shortest route. Nevertheless, for ships that are not equipped with thrusters that allow free movement along any axis, the method presented in the publication will be safer. The proposed route determination algorithm can be used to plan a route while the ship is in port. It can also monitor the ship’s route during navigation, recalibrating the transition weights based on the current environmental conditions and adjusting the route accordingly.

Source link

Jakub Wnorowski www.mdpi.com

Greenberg News

The Concept of Determining a Ship’s Route Based on the Capability Plot and Dijkstra’s Algorithm—Finding the Ship’s Route Between Anchorages

1. Introduction

3. Route Determination for Ship Passage Using Capability Plots

3.1. The Concept of the Algorithm

3.2. Ship Route Without Using the Algorithm

3.3. Route Determined Using Dijkstra’s Algorithm and the Capability Plot

3.4. Other Examples of Determined Routes

3.4.1. Navigation Scenario #1

3.4.2. Navigation Scenario #2

3.4.3. Navigation Scenario #3

4. Discussion

5. Conclusions

Greenberg

1. Introduction

3. Route Determination for Ship Passage Using Capability Plots

3.1. The Concept of the Algorithm

3.2. Ship Route Without Using the Algorithm

3.3. Route Determined Using Dijkstra’s Algorithm and the Capability Plot

3.4. Other Examples of Determined Routes

3.4.1. Navigation Scenario #1

3.4.2. Navigation Scenario #2

3.4.3. Navigation Scenario #3

4. Discussion

5. Conclusions

Related Posts

Plants, Vol. 14, Pages 936: Optimizing Water&ndash;Fertilizer Coupling Across Different Growth Stages of Tomato in Yellow Sand Substrate: Toward Enhanced Yield, Quality, and Resource Use Efficiency

NOAA’s National Ocean Service: Working for you!

Biosensors, Vol. 15, Pages 191: Analysis of Personalized Cardiovascular Drug Therapy: From Monitoring Technologies to Data Integration and Future Perspectives

Greenberg

Plants, Vol. 14, Pages 936: Optimizing Water–Fertilizer Coupling Across Different Growth Stages of Tomato in Yellow Sand Substrate: Toward Enhanced Yield, Quality, and Resource Use Efficiency