ZHANG Guangyu, WANG Hongbo, , ZHAO Wei, GUAN Zhiying, and LI Pengfei

1) State Key Laboratory on Integrated Optoelectronics, College of Electronic Science and Engineering, Jilin University,Changchun 130012, China

2) CRRC Changchun Railway Vehicles Co., Ltd., Changchun 130000, China

Abstract This paper presents a novel intelligent and effective method based on an improved ant colony optimization (ACO)algorithm to solve the multi-objective ship weather routing optimization problem, considering the navigation safety, fuel consumption, and sailing time. Here the improvement of the ACO algorithm is mainly reflected in two aspects. First, to make the classical ACO algorithm more suitable for long-distance ship weather routing and plan a smoother route, the basic parameters of the algorithm are improved, and new control factors are introduced. Second, to improve the situation of too few Pareto non-dominated solutions generated by the algorithm for solving multi-objective problems, the related operations of crossover, recombination, and mutation in the genetic algorithm are introduced in the improved ACO algorithm. The final simulation results prove the effectiveness of the improved algorithm in solving multi-objective weather routing optimization problems. In addition, the black-box model method was used to study the ship fuel consumption during a voyage; the model was constructed based on an artificial neural network. The parameters of the neural network model were refined repeatedly through the historical navigation data of the test ship,and then the trained black-box model was used to predict the future fuel consumption of the test ship. Compared with other fuel consumption calculation methods, the black-box model method showed higher accuracy and applicability.

Key words multi-objective optimization; weather routing; ACO algorithm; fuel consumption

1 Introduction

In recent years, the role and status of weather routing in ship maritime navigation have become increasingly prominent, and many algorithms for the optimization design of ship weather routes have been proposed. Common algorithms include the isochrone method, dynamic programming method, evolutionary algorithm, genetic algorithm,and ant colony optimization (ACO) algorithm. A singleobjective optimization is no longer adequate for the weather routing optimization problem, as usually, multiple objectives with multiple constraints need to be simultaneously optimized. In the multi-objective weather routing optimization problem, several optimization objectives often conflict with one another, so that optimization cannot be simultaneously achieved. The Pareto dominance relationship is often used to compare the multi-objective optimization problem; it is necessary to find a set of compromise solutions to optimize each objective as much as possible.

The isochronal method is the earliest algorithm for planning the shortest time route for ships based on weather forecast data (James, 1957). However, the method does not give the correct isochron, and its own ‘isochron loop’problem makes it unsuitable for computer-aided calculations. A modified isochron method suitable for computeraided calculations can calculate the minimum fuel consumption and the shortest sailing time (Hagiwara and Spaans, 1987). In recent years, a three- dimensional modified isochrone method was proposed and it can achieve the minimum fuel consumption and expected arrival time under the premise of safe navigation (Linet al., 2013; Fang and Lin, 2015).

The basic idea of the dynamic programming method is similar to that of the isochrone method, and its core is Bellman’s optimization principle (Bellman, 1956). In the ship weather routing optimization problem, the dynamic programming algorithm transforms the route optimization problem into a multi-stage decision-making problem and obtains the global optimal solution by finding the local optimal solution of each stage (Fig.1). A new forward three-dimensional dynamic programming (3DDP) method can minimize fuel consumption during ship navigation(Shaoet al., 2012). Experiments showed that the improved 3DDP method is easier to program and has a better optimization effect.

Evolutionary algorithms are a cluster of algorithms that mimic Darwin’s theory of species evolution. Among them,the genetic algorithm was first proposed (Holland, 1975),and it has been used in the traveling salesman problem(TSP) (Dorigo and Gambardella, 1997). Vector evaluated genetic algorithms proved that evolutionary algorithms have great advantages in searching the Pareto optimal solution set of multi-objective problems and laid a foundation for future evolutionary algorithms to solve multi- objective problems (Schaffer, 1985). Zitzler and Thiele (1999)proposed the strength Pareto evolutionary algorithm which is characterized by an elite retention mechanism. Debet al.(2002) proposed a non-dominated sorting-based multi- objective evolutionary algorithm which is called the nondominated sorting genetic algorithm II. This algorithm features an improved non-dominated sorting method and includes a selection operator; thus, it can find a better solution and create a more distant Pareto optimal frontier.Zhang and Li (2007) applied the concept of decomposition to a multi-objective evolutionary algorithm; they decomposed the multi-objective problem into several scalar optimization subproblems and then optimized them. Wang and Li (2018) improved the real-coded genetic algorithm and presented a faster and more efficient method to design the shortest route in a dynamic environment with good results.

Fig.1 Schematic diagram of the route design method based on dynamic programming.

In recent years, the ACO algorithm has been widely applied to multi-objective problems and weather routing problems. It was proposed by Dorigoet al. (1991). It was also applied to the TSP and achieved good results (Dorigo and Gambardella, 1997). The ACO algorithm can effectively solve complex optimization problems and has strong parallelism and robustness. The electronic chart display and information system (ECDIS) as a platform, combining the ACO algorithm and genetic algorithm, was used to establish an optimization model for trans-ocean route planning; the results showed that a single target could be effectively optimized (Tsou and Cheng, 2013). A two-way search ACO algorithm was proposed in which the ant colony started from the starting point and the destination;this approach enhanced the practicability of the algorithm(Cuiet al., 2014). Moreover, a new route decision- making method was used to accelerate the algorithm convergence speed and avoid local optimization.

Guntsch and Middendorf (2002) first proposed the concept of ‘population’ and combined it with the ACO algorithm. This algorithm is very competitive in solving dynamic optimization problems. Pareto solution set-based ACO algorithm solves multi-objective combinatorial optimization problems (Doemeret al., 2004). The results proved the superiority of the algorithm. Multi-objective ACO framework based on the concept of decomposition solves the bi-objective TSPs (Chenget al., 2012).

In this paper, the authors propose an intelligent and effective method based on an improved ACO algorithm to solve the multi-objective ship weather routing optimization problem. The contributions are as follows:

1) The mathematical models of multi-objective weather route optimization problems are presented, including the geographical coordinates; the ship motion position equation is discretized in time to build the ship motion model.In addition, the marine navigation area modeling grid to construct the environmental grid model is presented.

2) A novel method for the multi-objective weather routing of ships is proposed based on the ACO algorithm. To increase the algorithm effectiveness, besides modifying the algorithm parameters, the authors also propose a new control operator. Owing to the introduced control operator,the algorithm can plan a smoother route and can be applied to a long-distance ship weather route.

3) The authors combine the excellent operators of the genetic algorithm with the traditional ACO algorithm to improve the population richness and increase the number of Pareto non-dominated solutions.

4) A black-box model of oil consumption is built. The model is based on an artificial neural network (ANN). The parameters of the black-box model are trained by the historical navigation data of the test ship, and then the trained black-box model is used to predict the future fuel consumption of the test ship. Compared with other fuel consumption calculation methods, the value obtained by the black-box model is more accurate.

The rest of the paper is organized as follows: Section 2 describes the mathematical model of the ship weather route design. Section 3 introduces the principle of the improved ACO algorithm. Section 4 describes the fuel consumption black-box model building. Section 5 shows the route simulation results of the improved algorithm. Section 6 presents the conclusions.

2 Mathematical Model of Ship Weather Routing

2.1 Ship Motion Model

Under geographical coordinates, the equations for calculating the ship motion position are as follows:

whereφNandλNrepresent the latitude and longitude of the ship location at the current time, respectively, andφN+1andλN+1represent the latitude and longitude of the ship location at the next moment, respectively. These parameters are the ship motion state variables that describe the ship position. Also,Rrepresents the ant movement step length,θis the ship sailing direction, ?φis the distance of one latitude-difference, and ?λis the distance of one longitude-difference.

If the earth is regarded as a regular sphere, the longitude lines are equal in length; therefore, ?λcan be calculated using the following formula.

2.2 Navigation Environment Model

In this paper, the ship navigation area is modeled as a grid map; that is, the navigation area is equally spaced along the horizontal direction and the vertical direction to form several grids. Each node of the grids will be assigned a unique label number. The grid spatial resolution can be 0.25?×0.25?, 0.5?×0.5?, 1?×1?, and so on. The higher the spatial resolution, the more the data that need to be stored,and the more steps the ants will take in the movement process, which means that the algorithm will consume more time to solve the problem. Considering this situation,a spatial resolution of 1?×1? is adopted in this paper.

The longitude range of the simulation experiment navigation area is selected as [20?N, 60?N], and the latitude range is selected as [80?W, 0?W]. The navigation area is divided by the above grid method. Fig.2 is the grid map,with 41×81 nodes in total. All nodes are numbered; the upper left node is numbered ‘1’, the node below is ‘2’,and so on. Points S and E represent the starting point and the end point of the route planning, respectively.

Fig.2 Grid map model and label numbers.

The relationship between the actual geographical coordinates of a grid node and its corresponding number is as follows:whereNis the grid node number;λandφrepresent the longitude and latitude of the geographic coordinates of a grid node, respectively;wis the width of the grid map;lis the length of the grid map; andφtoprepresents the maximum latitude of the navigation area.

In general, it is impossible to ensure that all route points fall on the grid nodes. When a route point falls outside the grid nodes, the meteorological data of the point can be obtained by the bilinear interpolation algorithm. Suppose(λ+ω,φ+υ) is the geographical coordinate of the current ship position, whereλandφare the integer part of the floating-point coordinate, andωandυare the fractional part of the floating-point coordinate when the value interval is [0,1). Then, the weather dataξof the current route point can be obtained according to the weather data corresponding to the four grid nodes around it:

3 Principle of the Improved Ant Colony Optimization Algorithm

Presently, there are few examples that apply the ACO algorithm to multi-objective ship weather routing optimization design. The traditional ACO algorithm is not suitable for the ship weather routing optimization design on sea. The main reasons are as follows: First, the route designed by the traditional ACO algorithm is not smooth;this problem is especially prominent in the long-distance path planning. Second, the operation speed of the traditional ACO algorithm is slow, and the code execution efficiency is not high, which leads to the result not being ideal. Also, when the traditional ACO algorithm tends to be stable, it is difficult to find other new solutions to enrich the population, so the Pareto non-dominated solutions produced by the algorithm are too few.

To address the above problems, Liet al. (2018) improved the ant movement rule and pheromone-updating method in the ACO algorithm to solve the single- objective problem and obtained good results. Based on this, this paper adds some new improvements to solve the multiobjective problem. The specific improvement ideas are described in the following subsections.

3.1 Improvement of Algorithm Basic Parameters

In general, a basic route needs to be selected during ship weather routing. To make the optimized route better fit the great circle route – especially so that when the route deviates from the basic route to avoid obstacles, the algorithm can quickly modify the route – the authors introduce a new coefficient to the formula of the transition probability–route control factor (RCF).

According to the above functions, the RCF expression can be fitted by MATLAB curve fitting toolbox:

whereajis the introduced coefficient,j∈[1, 3];fis the number of times the ants move;iis the serial number of route points;i∈[1, 2NS+1];vis the actual speed of the ship; andDistis the longitudinal distance from the ship’s position to the great circle route.

Thus, the state transition probability in the ACO algorithm is described as follows:

whereτis the pheromone concentration,αis the relative importance degree of the residual pheromone concentration,βis the relative importance degree of the expected value, andηk(f,i)is heuristic information of theithroute point.

In general, in the traditional ACO algorithm, the heuristic informationηkof a point is equal to the reciprocal of the distance from the point to the target point. However,the definition of heuristic information is not suitable for long-distance path planning; therefore, the authors redefine the heuristic function as shown in the next equation:

whereLSis the distance from the current waypoint to the starting point S.LEis the distance from the current waypoint to the end point E.LGCRis the distance of the great circle route between the starting point and end point.nis a constant used to control the magnitude ofηk(f,i).

3.2 Introduction of Genetic Operators

Two crucial issues must be considered in finding the Pareto optimal solution set for multi-objective problems.The first, algorithm convergence, is how quickly the Pareto optimal solution is found. The second, population diversity,is how to make the distribution of non- dominated solutions on the Pareto front more symmetrical. The traditional ACO algorithm is not rich in solutions, especially when the algorithm tends to be stable; it is difficult to find other new solutions to enrich the population, resulting in too few non-dominated solutions when multi-objective problems are solved. To address this problem, the authors introduce the excellent evolution operator of the genetic algorithm into the ACO algorithm.

The genetic algorithm is also widely used in ship route planning. Compared with the ACO algorithm, the genetic algorithm has better randomness and route optimization ability. When the crossover probability is higher, many new individuals can be created in each iteration. However,the genetic algorithm does not make full use of heuristic information, which leads to the slow speed of solutions.Therefore, to prevent the ACO algorithm from falling into a local optimum at an early stage and increase the diversity of solutions to multi-objective problems, the crossover,recombination, and mutation operations of the genetic algorithm are mixed into the ACO algorithm in this paper.The specific related operations are implemented as described below:

Crossover: After each iteration of the algorithm, all solutions are sorted according to the non-dominated rules to divide the individual’s non-dominated level rank. The individuals with rank 1 are selected and added to the Pareto optimal solution set. Afterward, the route points in all the non-dominated solutions are randomly crossed and reorganized except for the starting and end points. If a new non-dominated solution occurs, the route is retained and passed on to the next iteration.

Mutation: The position of a waypoint on the route is randomly changed; if the variation solution is better than the original solution, it is kept; otherwise, it is discarded.

3.3 Description of Optimization Problem

This section describes the use of the improved ACO algorithm to solve the multi-objective ship weather routing problem. During ship route optimization, it is necessary to select a basic route as a reference to make the route search more purposeful, avoid blindness, and speed up the search.Especially, when the route deviates from the basic route to avoid obstacles, the algorithm can quickly correct the current course according to the basic route. The basic routes available for selection generally include the great circle route and the rhumb line (Fig.3).

Fig.3 The great circle route and the rhumb line.

The shortest route between two points on the sea is the great circle route; therefore, this route is used as the basic route of ship weather routing, and the basic route is fixed.

The method of improving the ACO algorithm to search for route points is illustrated in Fig.4. Point S and point E represent the starting and end points of the ship weather routing, respectively. Point A and point B represent two random waypoints on the optimized route. The algorithm hasKiterations, andMants are released in each generation. Each ant starts to build its route from the starting point S,and every time the ant arrives at a waypoint, the great circle route between the current point and the target point is established.

Fig.4 Schematic diagram of route search.

Taking route point A as an example, the datum courseComust first be determined in the ants’ search of the next waypoint. The courseCocan be obtained through the following equations:

whereDλis the difference in longitude between the current route point and the end point, andφnandφdare the latitude values of the current point and the end point, respectively.

Afterward,NSexpansions are performed on both sides of the datum course in units of discrete angles ?θto form 2NS+1 movement directions, that is, 2NS+1 reachable waypoints. The computational complexity iso(K·M·(2NS+1)2).In addition, ships may encounter dangerous areas during navigation. Therefore, it is necessary to avoid island reef areas, restricted areas, and sea areas where relevant meteorological parameters are beyond the limits of the ship tolerance. Then, the reachable waypoints in the forbidden area are deleted to reduce computational complexity. Finally, among the remaining waypoints, an optimal waypoint B is selected to replace the current point A according to the state transition probability. The cycle is repeated until ants complete the route search, and then the optimization objective function value is calculated.

After the completion of one iteration, the obtained solutions are ranked according to the Pareto dominance relation, and the rank of individuals is divided. Then, the population is sorted; the non-dominated individuals with high ranks are selected to obtain a new solution set after crossover, recombination, and mutation operations. The new solution set is passed on to the next generation, which continues until the maximum number of iterations is reached. After all iterations are completed, the output is the Pareto optimal route set, and the route optimization simulation map and the Pareto frontier are drawn.

The process through which the improved ACO algorithm solves the multi-objective ship weather routing optimization problem is illustrated in Fig.5.

4 Calculation of Ship Fuel Consumption

In general, there are three common methods for calculating the fuel consumption of the main engine: the interpolation method, formula method, and black-box model method. This chapter introduces the three methods, and finally, the best method is adopted in this paper to calculate the fuel consumption in ship weather routing.

4.1 Interpolation Method

Interpolation is a common method to calculate the fuel consumption of ships. According to the ship historical navigation data, one can set up the ship speed and fuel consumption table and estimate the fuel consumption by interpolation. This method is simple to implement and has no complex calculation process. However, the fuel consumption values are all estimations; thus, accurate values cannot be obtained.

4.2 Formula Method

When the ship is running at a constant speed, the main engine of the ship consumes fuel to rotate the propeller.The effective thrust of the ship is equal to the total resistance it encounters. Therefore, the fuel consumption is determined by the resistance and the propulsion of the main engine. Therefore, the core idea of the formula method is to use the relationship between the machinery horsepower, effective horsepower, and total resistance to determine the ship fuel consumption.

Fig.5 Flowchart of the improved ACO algorithm for solving the multi-objective problem.

4.2.1 Power conversion relationship

The power transmission diagram of the main engine is shown in Fig.6, which specifically depicts the gradual conversion process of the main engine power.

Since the effective thrust and the total resistance of the hull are balanced at a constant speed, the effective power of the ship at this time is expressed as follows:

wherePErepresents the effective horsepower,Rrepresents the resistance of the ship, andvSrepresents the ship current speed.

According to the power transfer relationship of the main engine,PScan be derived fromPE, and then the ship fuel consumption in unit time can be obtained:

wherePSrepresents the machinery horsepower,Frepresents the fuel amount used by the ship in unit time,SFOCrepresents the fuel consumption efficiency (kg (kW h)?1).

4.2.2 Resistance component analysis

The above section shows that the ship fuel consumption can be obtained when the effective horsepower is known, and the effective horsepower is related to the ship speed and the total resistance. In general, the total resistance of a running ship can be divided into water resistanceRwaterand air resistanceRwind, and water resistance can be subdivided into hull resistanceRhulland wave resistanceRwave. To simplify the description, the specific expressions of resistance are not presented in this paper.Therefore, the expression of total resistance is

The formula method is more suitable for theoretical calculations but not for solving the actual fuel consumption of ships. It contains too many unknown variables,most of which are related to the ship’s own characteristics;it is difficult to obtain these parameters. Moreover, the calculation process of the formula method is too complex and tedious; thus, this method is infrequently used to study practical problems.

4.3 Black-Box Model of Fuel Consumption

Fig. 6 Power transmission diagram of main engine.

The black-box model is a mathematical model of the experimental object constructed by input and output experimental data. Based on the study of the model system performance, the future trend of the experimental object can be predicted. The modeling process of the black-box model is essentially the continuous optimization of model parameters. Assuming that there is sufficient ship navigation data, a black-box model of the ship fuel consumption can be established. A large and effective historical ship navigation data set is crucial for building an accurate fuel consumption model.

The data used in this paper to build the black-box model were collected from a domestic ferry, MS Smyril,in the Faroe Islands, and the ferry was also used as a test vessel for multi-objective weather routing optimization simulation experiments. The ship belongs to the Strandfaraskip Landsins Transportation Company and makes a daily round trip between Torshavn and Suduroy; each trip lasts approximately 2 hours one way. The main scale parameters of the ferry are presented in Table 1 (Petersen,2011).

Table 1 Detailed parameters of test ship

The construction of the fuel consumption black-box model includes two parts: the preprocessing of the ship navigation data and the construction of the neural network model. The following two parts are described in detail.

4.3.1 Data preprocessing

Various kinds of sensors were installed onboard the ferry to collect and record ship navigation data. The ferry company recorded and published data on all voyages from February to April 2010.

Furthermore, owing to the great uncertainty of the environment in which the data were collected, the obtained original data had defects and could not be directly applied to the training of the neural network model. Therefore,before the use of the collected data to build the fuel consumption black-box model, they were processed to ensure a uniform data format of each measurement.

1) Fuel volume flow rate and voyage speed

The fuel flow measurement period was 1 s, and the speed measurement period was 3 s. To ensure the reliability of the data, the initial navigation data was first screened; that is, the voyages whose flight time was too short or too long were removed from the initial sample. Since the trip duration was approximately 2 h, the navigation data with sailing times between 5000 and 8000 s were used. A certain voyage was randomly selected from the screened data,and the changes in the fuel flow and speed of the ship during the voyage were plotted, as shown in Fig.7 and Fig.8.

Fig.7 Time-varying curve of main engine fuel consumption rate.

Fig.8 Ship speed variation curve during the sailing cycle.

2) Wind direction and wind speed

The sampling period of wind direction and wind speed was 2 s. To unify the data format, the wind direction data and the wind speed data were processed into two vertical velocity components, as shown in Fig.9.

The two wind speed components can be calculated by the actual wind speed and the relative wind direction, as shown in the following formulas:

whereVwindis the wind speed,θwindis the relative wind direction angle,Vheadis forward wind speed, andVcrossis the lateral wind speed.

Since the sampling period of each measurement data is different, it is not guaranteed that each data point has a corresponding value at a certain moment. Therefore, be-fore the training of the network model parameters, the eigenvalue extraction of the data is required. First, the discrete intercept time was determined; the screened effective range was divided into several flight segments in discrete time units. Then, the average value of various data in each time period was calculated as the characteristic value. This way, the formats of model input data and output data were unified.

4.3.2 Construction of artificial neural network

After the preprocessing of the ship historical navigation data, the black-box model of fuel consumption was built based on the ANN. The preprocessed navigation data were used to train the model parameters, and the trained blackbox model was used to predict the ship future fuel consumption.

An ANN is a mathematical tool (Harris and Yann, 1992)that mimics the working characteristics of human brain neurons and carries out distributed parallel processing of data; it is very suitable for the construction of black-box models. The structure of an ANN model includes an input layer, an output layer, and many hidden layers. In this paper, a feedforward backpropagation (BP) ANN with a hidden layer is adopted for constructing a fuel consumption black-box model. The BP ANN was proposed by Rumelhart and McClelland in 1986 and is one of the most widely used networks.

As shown in Fig.10, the black-box model is constructed by the BP ANN with a three-layer network structure. Excessive input data can complicate the analysis of the model,and some of the insignificant inputs may also bias the final result. Therefore, properly selecting the input layer variables of the model is crucial. In this paper, the fuel consumption of the ship is taken as the output layer variable of the model, while the eigenvalues of the navigation speed, heading wind speed, lateral wind speed, significant wave height, and the encounter angles of swell and wave directions are taken as the input values of the model.

Fig.10 Fuel consumption black-box model diagram.

4.3.3 Model training and testing

The preprocessed ship navigation data were divided into two sets: a training data set and a test data set, both of which contain input variables and outputs. The training set was used to train the parameters of the black-box model,while the test set was used to detect the errors of the model.The black-box model training error function is set as shown below:

wherelossis the error function value,ysis the actual measured fuel consumption, andyois the model output fuel consumption.

In the parameters training process, the error function value of the black-box model drops rapidly and is finally controlled at approximately 0.0021; the error function curve is shown in Fig.11.

Fig.11 Error function value curve of the black-box model.

The black-box model method can build the unique fuel consumption model of the corresponding ship according to different ship navigation data. Compared with the interpolation method and the formula method, the blackbox model method has better accuracy and applicability and is easier to operate. In addition, the accuracy of the model is directly proportional to the input amount of the model and the amount of training data. The larger the amount of data, the better the model can combine realtime meteorological information and provide a fuel consumption value closer to the actual navigation conditions.Therefore, the black-box model method is adopted in this paper as the calculation method of fuel consumption in ship weather routing.

5 Analysis of Simulation Results

Generally, in multi-objective optimization problems,several optimization objectives are often conflicting, and the optimum values cannot be simultaneously achieved.Therefore, in solving multi-objective problems, the Pareto dominance relation is often used to compare the qualities of several solutions. For a feasible solutionxof a multiobjective problem, if there is no other feasible solutionyso thatF(y) dominatesF(x), thenxis called the Pareto optimal solution of the problem. The Pareto optimal solution is not unique, but multiple solutions are possible. All Pareto non-dominated solutions form the Pareto optimal solution set, and the surface formed by the optimal solutions is called the Pareto front surface. In other words,there is no better solution than the individual performance corresponding to the Pareto optimal solution in the feasible solution set, and there is no difference between Pareto optimal solutions. Since any solution in the Pareto optimal solution set can be the optimal solution, designers can design according to their own choices and the goal.

The multi-objective ship weather routing mentioned in this paper refers to balancing the relationship between the sailing time and fuel consumption on the premise of ensuring the ship navigation safety. The selected simulation object is the ferry Smyril, and the ship parameters are presented in Table 1. In the simulation experiment, the optimal route was computed for departure S (62?W, 44?N)and arrival E (13?W, 28?N) points. The length of the great circle between the points S and E was 2523.41 nautical miles. The speed of the experimental ship was 15 kn in calm water. The ship was required to leave the departure port at 00:00 March 7, 2016, and the weather forecast data from ECMWF were updated every 6 h. Combined with the ship speed in still water, the step length of each ant colony algorithm could be estimated. In addition, to ensure the ship navigation safety, the sea areas where the wave height exceeded 5 m or the wind speed exceeded 16 m s?1were defined as dangerous areas, and navigation was prohibited in these areas. As shown in Fig.12, the ship navigation position of the ship was selected four times during a simulated route on March 7, 2016, with the corresponding wind and wave information. The figure shows the diagram of the wind and wave alarm area. The light and dark color areas represent the dangerous area with wind speed greater than 16 m s?1and wave higher than 5 m, respectively. The figure shows that ships can timely avoid the dangerous areas encountered during navigation,thus ensuring safe navigation.

Fig.12 Real-time position and weather information of ship.

During the voyage, since the optimized route is discretized in units of fixed navigation steps, the ship sailing time is composed of several discrete time intervals ?t,and the ship fuel consumption rateSfocper unit time is calculated by the fuel consumption black-box model.Therefore, the fuel consumptionFcan be obtained by the following formula:

To prove the effectiveness of the improved ACO algorithm in solving the multi-target ship weather routing optimization problem, a multi-objective route optimization simulation was separately performed using three ACO algorithms of different optimization degrees, and the results were compared. The first algorithm is the traditional ACO algorithm without any improvement; the second is the ACO algorithm with improved basic parameters; the third is the improved ACO algorithm with added genetic operators.

a) As mentioned earlier, when the traditional ACO algorithm solved the route optimization problem, the obtained planned route was not smooth, as shown in Fig.13.

The traditional ACO algorithm is not suitable for solving multi-objective optimization problems. On the same grid map, regardless of the algorithm number of runs, the same non-dominated solutions are always obtained. Fig.14 shows the Pareto optimal frontier drawn by the traditional ACO algorithm for solving multi-objective problems, where the abscissa is the voyage time and the ordinate is the fuel consumption. The number of non- dominated solutions is too small, and the solution quality is not high.

b) For the ACO algorithm with improved basic parameters, the shortest time route obtained is shown in Fig.15.The shortest time route could be timely corrected route after the dangerous area had been avoided, and the second half of the route was basically consistent with the great circle route. The total range of the great circle route was 2523.41 nautical miles, the sailing time was 201.43 h, and the average speed was 12.78 kn. The total range of the ship weather route was 2560.84 nautical miles, which was 37.43 nautical miles more than the Dayan route. However,the total voyage time was 192.75 h, which is shortened by nearly 9 h, and the average speed was approximately 13.35 kn. In other words, under the dynamic weather conditions,the improved ACO algorithm can find an optimal route from the departure port to the destination port according to the specific requirements.

The Pareto optimal front obtained is shown in Fig.16,and the non-dominated solutions are significantly better in quantity and quality than those obtained by the first algorithm.

Fig.13 Comparison of simulation results between two algorithms on route smoothness.

Fig.14 Pareto optimal frontier obtained by the traditional ACO algorithm.

Fig.15 Shortest time route obtained by the local improved ACO algorithm.

c) The third group of multi-objective route optimization experiments uses the improved ACO algorithm with added evolutionary operators. When searching for route points, the algorithm calculates the function values of the two optimization objectives (sailing time and fuel consumption). For each iteration, the algorithm sorts the obtained solutions according to the Pareto dominance relation to select the Pareto optimal solutions. Then, the Pareto optimal solutions are passed on to the next itera- tion after a series of genetic operators are applied, thus repeating the process.

Fig.16 Pareto optimal frontier obtained by the local improved ACO algorithm.

Fig.17 The Pareto optimal set of routes.

Fig.18 The Pareto optimal frontier obtained by the improved ACO algorithm.

Finally, once all iterations are completed, the set of all Pareto optimal routes is obtained as shown in Fig.17, and the corresponding Pareto front is shown in Fig.18. Compared with the traditional ACO algorithm, the improved ACO algorithm designed a smoother route, which can be used for long-distance path planning. The algorithm generated more Pareto optimal solutions, and the distribution of the Pareto frontier formed by the optimal solutions in space was also relatively uniform, which accords with the expected result. Therefore, the improved ACO algorithm has great advantages over the traditional ACO algorithm in solving the multi-objective ship route optimization problem, both in the number of non-dominated solutions and the distribution of the final Pareto front.

6 Summary

The optimal weather routing of ships is of great significance for maritime transportation and has great economic and practical value. In recent years, the role and status of meteorological navigation in ship maritime navigation have become increasingly prominent. Additionally, the role and status of weather routing in the marine navigation of ships have become increasingly prominent. Therefore, many algorithms for ship weather routing optimization have been proposed, but most classical algorithms are only for single-objective optimization problems. Considering the ship navigation safety, fuel consumption, and sailing time,this paper proposes an intelligent and effective multi- target ship weather routing optimization method based on an improved ant colony algorithm to ensure the safe, economical, and punctual navigation of ships at sea.

However, the proposed algorithm features some shortcomings. First, in the process of environmental modeling,the accuracy of the used meteorological data is not very high, and the obstacles involved are not comprehensive.Second, when calculating the fuel consumption of a ship,the algorithm considers only the fuel consumption of the ship main engine during navigation; the fuel consumption of the auxiliary engine on board and the consumption during the ship navigation in and out of the port are not considered. Third, when calculating the ship arrival time,the algorithm does not consider the waiting time spent in the process of entering and leaving the port. Thus, more studies are needed to improve the ACO algorithm to alleviate the shortcomings and prepare the algorithm for practical applications.

Acknowledgement

This study was funded by the Russian Foundation for Basic Research (RFBR) (No. 17-07-00361a).