AN APPARATUS FOR DETERMINING AN OPTIMAL ROUTE OF A MARITIME SHIP

Abstract

An apparatus for determining an optimal route of a maritime ship comprises a database configured to store a service speed of the maritime ship. The apparatus further comprises a processor configured to generate a plurality of state nodes, to determine a plurality of time sets, to append the plurality of time sets to the plurality of state nodes to obtain a plurality of appended state nodes, to generate a plurality of edges based on the plurality of appended state nodes, to generate a graph based on the plurality of appended state nodes and the plurality of edges, to apply a preliminarily generated optimal route algorithm on the graph to obtain a preliminarily defined route path, and to apply a genetic algorithm based on the preliminarily defined route path to obtain the optimal route of the maritime ship.

Claims

1. An apparatus for determining an optimal route of a maritime ship, wherein the maritime ship is to depart at a departure location at a departure time, and arrive at a destination location at a destination time, based at least in part on fuel consumption, power consumption, emissions, Estimated Time of Arrival (ETA), care of cargo during a voyage, rough weather avoidance, voyage safety, ship structural stress, passenger sailing comfort, and the apparatus comprising: a database configured to store a service speed of the maritime ship; and a processor configured to: generate a plurality of state nodes based on the departure location, the destination location, and the service speed, each state node of the plurality of state nodes indicating a respective locations; determine a plurality of time sets based on the plurality of state nodes, the departure time, and the destination time, the plurality of time sets being associated with the plurality of state nodes, and each time set of the plurality of time sets indicating a range of arrival times associated with a respective state node of the plurality of state nodes; append the plurality of time sets to the plurality of state nodes to obtain a plurality of appended state nodes; generate a plurality of edges based on the plurality of appended state nodes, each edge of the plurality of edges being associated with a pair of appended state nodes of the plurality of appended state nodes and a respective optimization cost; generate a graph based on the plurality of appended state nodes and the plurality of edges; apply a preliminarily generated route optimization on the graph to obtain a preliminarily defined route path of the maritime ship between the departure location and the destination location; and apply a genetic metaheuristic optimization based on the preliminarily defined route path to obtain the optimal route of the maritime ship.

2. The apparatus of claim 1, wherein: the database is further configured to store a ship performance model, the processor is further configured to determine time constraint information based on the plurality of time sets and the ship performance model, and the processor is further configured to generate the plurality of edges further based on the time constraint information.

3. The apparatus of claim 2, wherein the processor is further configured to: generate the graph further based on the ship performance model.

4. The apparatus of claim 1, wherein: the database is further configured to store bathymetry information, the processor is further configured to determine geographic constraint information based on the plurality of state nodes and the bathymetry information, and the processor is further configured to generate the plurality of edges further based on the geographic constraint information.

5. The apparatus of claim 1, wherein: the database is further configured to store weather information, and the processor is further configured to generate the graph further based on the weather information.

6. The apparatus of claim 1, wherein the respective optimization cost comprises a power consumption of the maritime ship, a fuel consumption of the maritime ship, an emission of the maritime ship, a risk of cargo loss of the maritime ship, a fatigue damage in the structure of the maritime ship, or any combination thereof, wherein the emission of the maritime ship comprises a CO2 emission, SOx emission, NOx emission, PM emission, or any combination thereof.

7. The apparatus of claim 1, wherein the graph is a three-dimensional graph and comprises a first dimension with respect to longitude, a second dimension with respect to latitude, and a third dimension with respect to arrival time.

8. The apparatus of claim 1, wherein the preliminarily defined route path is based on a Dijkstra algorithm, a Bellman-Ford algorithm, an A* search algorithm, a Floyd-Warshall algorithm, a Johnson's algorithm, a Viterbi algorithm, or any combination thereof.

9. The apparatus of claim 1, wherein the processor is further configured to: determine a population of routes comprising a plurality of individuals based on the preliminarily defined route path, and apply the genetic metaheuristic optimization on the plurality of individuals.

10. The apparatus of claim 9, wherein each individual of the plurality of individuals is associated with a respective location deviation, a respective arrival time deviation with regard to the preliminarily defined route path, or both, and wherein the respective location deviations, the respective arrival time deviations of the plurality of individuals, or both, are different from one another.

11. The apparatus of claim 9, wherein the processor is further configured to: perform a selection step, a mutation step, a transfusion step, a crossover step, or any combination thereof, on the plurality of individuals.

12. The apparatus of claim 9, wherein the processor is further configured to: select an individual from the plurality of individuals, wherein the selected individual is associated with an optimal total optimization cost, and wherein the selected individual forms the optimal route of the maritime ship.

13. The apparatus of claim 9, wherein the processor is further configured to: modify the graph, the plurality of edges, or both, based on the selected individual.

14. A method for determining an optimal route of a maritime ship, the method comprising: storing, in a database, a service speed of the maritime ship; generating, by a processor, a plurality of state nodes based on a departure location of the maritime ship, a destination location of the maritime ship, and the service speed, each state node of the plurality of state nodes indicating a respective location; determining, by the processor, a plurality of time sets based on the plurality of state nodes, a departure time of the maritime ship, and a destination time of the maritime ship, the plurality of time sets being associated with the plurality of state nodes, and each time set of the plurality of time sets indicating a range of arrival times associated with a respective state node of the plurality of state nodes; appending, by the processor, the plurality of time sets to the plurality of state nodes to obtain a plurality of appended state nodes; generating, by the processor, a plurality of edges based on the plurality of appended state nodes, each edge of the plurality of edges being associated with a pair of appended state nodes of the plurality of appended state nodes, and a respective optimization cost; generating, by the processor, a graph based on the plurality of appended state nodes and the plurality of edges; applying, by the processor, a preliminarily generated route optimization on the graph to obtain a preliminarily defined route path of the maritime ship between the departure location and the destination location; and applying, by the processor, a genetic metaheuristic optimization based on the preliminarily defined route path to obtain the optimal route of the maritime ship.

15. (canceled)

16. The method of claim 14, further comprising: storing, by the database, a ship performance model; determining, by the processor, time constraint information based on the plurality of time sets and the ship performance model; and generating, by the processor, the plurality of edges based on the time constraint information.

17. The method of claim 16, wherein generating the graph comprises: generating the graph based on the ship performance model.

18. The method of claim 14, further comprising: storing, by the database, bathymetry information; determining, by the processor, geographic constraint information based on the plurality of state nodes and the bathymetry information; and generating, by the processor, the plurality of edges based on the geographic constraint information.

19. The method of claim 14, further comprising: storing, by the database, weather information; and generating, by the processor, the graph based on the weather information.

20. The method of claim 14, further comprising: determining, by the processor, a population of routes comprising a plurality of individuals based on the preliminarily defined route path; and applying, by the processor, the genetic metaheuristic optimization on the plurality of individuals.

21. A computer-readable program product for determining an optimal route of a maritime ship, the computer-readable program product comprising a non-transitory computer-readable medium storing instructions that, when executed by at least one processor, are configured to cause the at least one processor to: store, in a database, a service speed of the maritime ship; generate a plurality of state nodes based on a departure location of the maritime ship, a destination location of the maritime ship, and the service speed, each state node of the plurality of state nodes indicating a respective location; determine a plurality of time sets based on the plurality of state nodes, a departure time of the maritime ship, and a destination time of the maritime ship, the plurality of time sets being associated with the plurality of state nodes, each time set of the plurality of time sets indicating a range of arrival times associated with a respective state node of the plurality of state nodes; append the plurality of time sets to the plurality of state nodes to obtain a plurality of appended state nodes; generate a plurality of edges based on the plurality of appended state nodes, each edge of the plurality of edges being associated with a pair of appended state nodes of the plurality of appended state nodes and a respective optimization cost; generate a graph based on the plurality of appended state nodes and the plurality of edges; apply a preliminarily generated route optimization on the graph to obtain a preliminarily defined route path of the maritime ship between the departure location and the destination location; and apply a genetic metaheuristic optimization based on the preliminarily defined route path to obtain the optimal route of the maritime ship.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0030] Examples of the present disclosure will be described with respect to the following figures:

[0031] FIG. 1 shows a schematic diagram of an apparatus for determining an optimal route of a maritime ship;

[0032] FIG. 2 shows a schematic diagram of a method for operating an apparatus for determining an optimal route of a maritime ship;

[0033] FIG. 3 shows a schematic diagram of a method for operating an apparatus for determining an optimal route of a maritime ship where further examples of the method 200 (FIG. 2) are displayed in more detail;

[0034] FIG. 4 shows a schematic diagram of a plurality of state nodes being arranged to form a grid;

[0035] FIG. 5 shows a schematic diagram of a plurality of time sets associated with a plurality of state nodes at different stages;

[0036] FIG. 6 shows a schematic diagram of a three-dimensional graph having a plurality of state nodes and a plurality of edges;

[0037] FIG. 7 shows a schematic diagram of a simplified graph having a plurality of state nodes and a plurality of edges;

[0038] FIG. 8 shows a schematic diagram of an individual of a plurality of individuals in relation to a great circle route;

[0039] FIG. 9 shows a schematic diagram of different optimal routes for different estimated times of arrival (ETAs);

[0040] FIG. 10 shows a schematic diagram of a Pareto front for different estimated times of arrival (ETAs) and different power consumptions;

[0041] FIG. 11 shows a schematic diagram of an optimal route of a maritime ship in comparison to an actual route of the maritime ship;

[0042] FIG. 12 shows a schematic diagram of a speed of a maritime ship and a wave characteristic for an optimal route and an actual route of a maritime ship; and

[0043] FIG. 13 shows a schematic diagram of wave characteristics at different times.

DETAILED DESCRIPTION

[0044] FIG. 1 shows a schematic diagram of an apparatus 100 for determining an optimal route of a maritime ship, wherein the maritime ship is to depart at a predetermined departure location at a predetermined departure time, and wherein the maritime ship is to arrive at a predetermined destination location at a predetermined destination time, which can be performed in accordance to the user's needs, including but not limited to: minimum fuel consumption, minimum power consumption, lowest emissions, fastest Estimated Time of Arrival (ETA), care of the cargo during the voyage, and hence, rough weather avoidance, safest voyage, least ship structural stress, highest passenger sailing comfort.

[0045] The apparatus 100 comprises a database 101 configured to store a predetermined service speed of the maritime ship. The apparatus 100 further comprises a processor 103 configured to generate a plurality of state nodes based on the predetermined departure location, the predetermined destination location, and the predetermined service speed, each state node indicating a respective location, to determine a plurality of time sets based on the plurality of state nodes, the predetermined departure time, and the predetermined destination time, the plurality of time sets being associated with the plurality of state nodes, each time set indicating a range of arrival times associated with a respective state node, to append the plurality of time sets to the plurality of state nodes to obtain a plurality of appended state nodes, to generate a plurality of edges based on the plurality of appended state nodes, each edge of the plurality of edges being associated with a pair of appended state nodes of the plurality of appended state nodes, each edge being associated with a respective optimization cost, to generate a graph based on the plurality of appended state nodes and the plurality of edges, to apply a preliminarily generated optimal route algorithm on the graph to obtain a preliminarily defined optimal-route path of the maritime ship between the departure location and the destination location, and to apply a genetic algorithm based on the preliminarily defined optimal-route path to obtain the optimal route of the maritime ship.

[0046] FIG. 2 shows a schematic diagram of a method 200 for operating an apparatus for determining an optimal route of a maritime ship, wherein the maritime ship is to depart at a predetermined departure location at a predetermined departure time, and wherein the maritime ship is to arrive at a predetermined destination location at a predetermined destination time in accordance to the user's needs. The apparatus comprises a database and a processor, wherein the database is configured to store a predetermined service speed of the maritime ship.

[0047] The method 200 comprises generating 201, by the processor, a plurality of state nodes based on the predetermined departure location, the predetermined destination location, and the predetermined service speed, each state node indicating a respective location, determining 203, by the processor, a plurality of time sets based on the plurality of state nodes, the predetermined departure time, and the predetermined destination time, the plurality of time sets being associated with the plurality of state nodes, each time set indicating a range of arrival times associated with a respective state node, appending 205, by the processor, the plurality of time sets to the plurality of state nodes to obtain a plurality of appended state nodes, generating 207, by the processor, a plurality of edges based on the plurality of appended state nodes, each edge of the plurality of edges being associated with a pair of appended state nodes of the plurality of appended state nodes, each edge being associated with a respective optimization cost, generating 209, by the processor, a graph based on the plurality of appended state nodes and the plurality of edges, applying 211, by the processor, a preliminarily generated optimal route algorithm on the graph to obtain a preliminarily defined optimal-route path of the maritime ship between the departure location and the destination location, and applying 213, by the processor, a genetic algorithm based on the preliminarily generated optimal path route to obtain the optimal route of the maritime ship.

[0048] FIG. 3 shows a schematic diagram of a method 200 for operating an apparatus for determining an optimal route of a maritime ship. The method 200 comprises the same features as the method 200 as depicted in FIG. 2. In the following, further examples of the method 200 will be described in more detail. A route of a maritime ship may be defined by a series of waypoints forming a trajectory of the maritime ship and the associated time. The waypoints and time in a route can be used to directly calculate the series of the speed, e.g. the speed through water or the speed over ground, and/or the heading of the maritime ship for each waypoint along the route, based on the received MetOcean information around the ship's sailing area. Additionally, the shaft power of the maritime ship may be calculated. In the following, for a simple description of the optimization approach, the sailing variables to define a route are denoted as follows: [0049] {right arrow over (X)}(i,j,t): State (waypoint) variable, where i, j, t represent longitude, latitude and time, respectively. [0050] {right arrow over (U)}(v, θ): Route optimization control variables, where v is velocity, θ is heading angle. As the route is discretized into a series of sub-paths. The control variable can be considered as an attribute of a sub-path between two states in adjacent stages. [0051] {right arrow over (W)}(X): Weather conditions at one state (wave, current, wind). [0052] {right arrow over (C)}: Constraints such as geometric constraint; control constraint (bathymetry constraint, land crossing constraint, maximum continuous rating constraint, etc.)

[0053] An instantaneous cost function to calculate the optimization objective at each state can be denoted by:

I=ƒ({right arrow over (X)}, {right arrow over (W)}, {right arrow over (C)})   (1)

[0054] The total cost for a route/voyage can be obtained by

T(t.sub.e)=∫.sub.t.sub.s.sup.t.sup.eƒ({right arrow over (X)}, {right arrow over (W)}, {right arrow over (C)})dt   (2)

where t.sub.s, t.sub.e are the departure time and destination time, respectively. The optimization cost of a route can be expressed in different forms such as minimum fuel consumption (optimization cost expressed in terms of fuel), minimum power consumption (optimization cost expressed in terms of power), lowest emissions (optimization cost expressed in terms of emissions), fastest Estimated Time of Arrival according to the nature of the cargo (optimization cost expressed in terms of sailing time), rough weather avoidance according to the nature of the cargo (optimization cost expressed in terms of ship motions), safest voyage (optimization cost expressed in terms of safety related to ship motion and the chance of encountering storms/bad weather potential sea ice), least ship structural stress (optimization cost expressed in terms of stress on ship hull), highest passenger sailing comfort (optimization cost expressed in terms of ship motion).

[0055] The total cost in Eq. (2) can be derived by discretizing a route into a series of stages, e.g., n-stages. The optimization cost for each stage can be estimated individually, and then the total optimization cost may be calculated as follows:

[00001]$\begin{array}{cc}T\left(t_e\right)=\underset{i=1}{\overset{n}{.Math.}}f\left(\stackrel{.fwdarw.}{X_l},\stackrel{.fwdarw.}{W_i},\stackrel{.fwdarw.}{C}\right)\Delta t_i& \left(3\right)\end{array}$

[0056] The core function as in Eq. (3) for route optimization is exemplarily the fuel consumption during a ship's voyage. Furthermore, the ETA may be set to be fixed and used as one constraint. This implies that

[00002]$\begin{array}{cc}{t}_e-t_s=\underset{i=1}{\overset{n}{.Math.}}\Delta t_i=\mathrm{constant}& \left(4\right)\end{array}$

[0057] In the following, the implementation of the optimization approach for route planning is described in more detail. A ship can be routed across numerous different routes to reach its destination. The route chosen for a ship's actual voyage duration may be optimized to achieve specific objectives e.g. fuel consumption, emission, risk of cargo loss, voyage duration, cargo safety, etc. In the following, an exemplary objective chosen for route optimization is to minimize a fuel consumption during the voyage, while still maintaining its expected time of arrival (ETA). A hybrid routing optimization algorithm is proposed to solve the routing problem. It is composed of both an initial, preliminarily generated optimal route algorithm, e.g. a Dijkstra algorithm, Dynamic Programming, or Isochrone method, and a genetic algorithm, as explained above.

[0058] Let a route be denoted by a graph system G=(V, A) , wherein V is a set of vertices/nodes, and A is a set of directed edges/arcs composed of various pairs of nodes that are ordered in certain ways. Every directed edge is assigned with a weight/cost. The preliminarily generated optimal route algorithm, e.g. the Dijkstra algorithm, is used for finding the path (composed of a series of state nodes) between the departure location and the destination location with the lowest cost on the weighted graph. Most often, when the number of state nodes becomes large, the algorithm will require a huge computational effort to find the shortest-path solution. In order to reduce the effort while still keeping the capability of finding an optimal path, a genetic algorithm is employed for improving the individual candidate paths (i.e. routes) found by the preliminarily generated optimal route algorithm. Therefore, the hybrid routing optimization algorithm is also able to optimize a route by controlling both speed and/or heading and/or shaft power.

[0059] In order to apply the shortest-path algorithm, e.g. the Dijkstra algorithm, to solve the routing problem, a graph consisting of possible routes is generated first. For the optimal ship route, the algorithm does not only cover the geometric domain but also the time domain, a three-dimensional (3D) graph that is di scretized in form of waypoints or a grid with longitude, latitude and time may be applied. In the graph, the nodes or vertices (i.e. route waypoints) may be considered as states as defined previously. Therefore, any sub-paths or edges in a trajectory can be composed of connections between state nodes in different stages. From the departure location to the destination location, there may be numerous paths for every possible ETA. Note that if the time variable is fixed, various information regarding a connection/edge/arc can be obtained. Then, every connection/edge/arc can be assigned with an optimization cost as a weight. The preliminarily generated optimal route algorithm will return the preliminarily generated optimal route within the graph between the source node (i.e. the departure location) to the target node (i.e. the destination location).

[0060] As explained above, the genetic algorithm is based on a metaheuristic inspired by the theory of evolution, using concepts such as natural selection, reproduction, genetic heritage and mutation. It may also be used as an evolutionary algorithm for the routing problem. A problem of utilizing a genetic algorithm to solve the routing problem is how to create suitable models for the genetic algorithm. An element in a genetic algorithm is the so-called fitness function or objective function, which is actually a variable to be optimized by the algorithm. The aim of the genetic algorithm is to find the minimum value of the fitness function. For an optimized route planning, the objective/fitness function may be defined as fuel consumption, time cost, or other objectives related to a ship's navigation. In the genetic algorithm, a node may be any waypoint associated with a fitness value, which may be computed by the pre-defined fitness function. A simple example for the routing problem can be defined as follows. Let the fitness/objective function be defined by,

[00003]$\begin{array}{cc}f\left(X_1,\mathrm{.Math.},X_n\right)=\underset{i=1}{\overset{n}{.Math.}}g\left(X_i\right)& \left(\mathrm{Xi}\right)\end{array}$

wherein g is a fuel consumption function for a route state X.sub.i and f is the total fitness value, e.g. a total fuel consumption as a cost consumed by a route, which is composed of the states X.sub.1, . . . X.sub.n as an individual. In particular, the total fitness value f may be regarded as a total optimization cost.

[0061] Even for a simple problem in a routing system, which may only change a geometrical variable (longitude and latitude), the searching space for finding an optimal route by a genetic algorithm, i.e. the discretized space, may grow exponentially as the number of elements increases in an individual. Therefore, it may not be efficient to implement a genetic algorithm in the form of a large number of individuals as discussed above. Different approaches for the genetic algorithm may be applied. For example, a multi-objective genetic algorithm, which stochastically solves a discretized nonlinear optimization problem may be applied. For an efficient optimization, a sailing course and velocity profiles may be represented by parametric curves. Exemplary individuals may e.g. be based on two sets of parameters that control the parametric curves used to describe the ship course and velocity. Furthermore, a multi-criteria evolutionary routing algorithm may be applied.

[0062] An exemplary approach may be based on a normal genetic algorithm iterative process of population development. This approach may give the result of a Pareto-optimal set of solutions. The individuals for the first population may be the set of 4 routes, an orthodrome, a loxodrome, a time-optimized isochrone route and a fuel-optimized isochrone route. Furthermore, a genetic algorithm for solving a multi-modal objective function problem may be applied. The variation of latitude and a propeller revolution number in each waypoint may be considered as individuals within the population. This means that an individual may be associated with a set of parameters, which may e.g. influence both geographical location and revolution number. The challenges of implementing only a genetic algorithm or evolutionary algorithm to solve a routing problem can be summarized in two categorizes, i.e. geographical waypoints and time/speed. On one hand, a route may consist of many waypoints. Each waypoint may be a potential variable, which can be one element of an individual and may also be dependent on a former waypoint. On the other hand, the arrival time associated with each waypoint within a route may influence the final solution of the route optimization problem. It may be challenging to find an optimal solution with two sets of dependent variables using any genetic or evolutionary algorithm. However, alternative approaches may also be applied, such as in situ measurements that will be provided by the vessels using the system to have to most updated and correct info on the area it covers.

[0063] In the following, the optimization approach using the hybrid routing optimization algorithm is described in more detail. An aim for utilizing the genetic algorithm is to improve the optimal result given by the preliminarily generated optimal route algorithm, which may be a Dijkstra algorithm as an example. Alternatively, a Bellman-Ford algorithm, an A* search algorithm, a Floyd-Warshall algorithm, a Johnson's algorithm, a Viterbi algorithm, or any other shortest-path algorithm may be applied. The individuals in this algorithm may be a small range of variations for searching nodes/waypoints and arrival time. Thus, it may be easy to find the optimal route of the maritime ship, which may be very close to the global optimal. A graph, in particular a 3D weighted graph, may be generated. The preliminarily generated optimal route algorithm is implemented to work on the graph, in particular on the 3D weighted graph. The genetic algorithm will provide adjustments based on the solution that the preliminarily generated optimal route algorithm provides. Theoretically, the preliminarily generated optimal route algorithm may be able to obtain an optimal solution, which may be extremely close to the global optimal solution in a graph with very fine resolution. However, the computational effort for both constructing the graph and implementing the preliminarily generated optimal route algorithm to work on the graph may be tremendous. Therefore, the preliminarily generated optimal route-algorithm, e.g. the Dijkstra algorithm or any other similar algorithm, may be implemented having a normal-resolution graph and applying the genetic algorithm to further optimize the obtained ship route provided by the preliminarily generated optimal route algorithm. The voyage information such as the departure time and the destination time, the navigation strategy (e.g. power or RPM operation), as well as the grid system may be predefined. Furthermore, the ship performance model as well as the fitness function, the weather information and further sailing constrains, may be used as an input for the route optimization.

[0064] FIG. 4 shows a schematic diagram of a plurality of state nodes being arranged to form a grid. Each state node of the plurality of state nodes is associated with a respective location; thereby defining a waypoint of a route. Firstly, the plurality of state nodes is generated to define the searching area covering a ship's potential voyage trajectory. Specific route planning is based on the shortest distance between the departure location and the destination location. These routes are also named as great circle routes, which may be used as a reference for the grid/state node generation in a route optimization problem. Based on the great circle routes, other state nodes to be defined along further great circles may be perpendicular to the base path. The pseudocode to generate the plurality of state nodes being arranged to form a grid is given below:

TABLE-US-00001 State Node / Waypoint / Grid generator   Input: dep: departure; des: destination;   ν: service speed;   Δt: time interval between stages;  η: transverse resolution;  num_node: number of node in each stage. Output: Nodes Start:  GC_distance←GC_length(dep, des)   Δs ← νΔt  Num_stage←Total_dist / Δs  For i in Num_stage:   CrossNodes←NodeGen(num_node[i], η)   Nodes[i]←CrossNodes Return Nodes

[0065] One example of such a generated grid is given in FIG. 4. As it is shown, the entire ship voyage may be divided into n stages. For each stage, there may be k.sub.i, i=1,2, . . . n possible state nodes associated with geographic locations and arrival times. For each pre-defined state node, a ship may reach it at different time slots, which are named as “timeset”.

[0066] FIG. 5 shows a schematic diagram of a plurality of time sets associated with a plurality of state nodes at different stages. A time set may be defined statically based on which stage the state node is located. The time set may be assigned with every state node. The diagram illustrates how the time axis is assigned with each state node. In the diagram, the round dots, in contrast to the star-like dots, represent possible accessible time sets for the node state in various stages. The generation of those time sets is briefly described as follows:

[0067] Let the departure time denote by ts, the destination time denoted by t.sub.e, and the ETA being calculated as Δt=t.sub.e−t.sub.s. [0068] First step: initialize the time range set as t∈[t.sub.s, t.sub.s+1.5×Δt]. [0069] Second step: define time ranges that can reach/access to different states on a stage. This step may only give a rough accessible time range for adjacent stages. Further constraints will be explained in the following.

[0070] FIG. 6 shows a schematic diagram of a three-dimensional graph having a plurality of state nodes and a plurality of edges. In the hybrid routing optimization approach, a grid may be composed of pre-defined waypoints/state nodes, which may form sailing edges. The plurality of edges may e.g. connect respective state nodes between adjacent stages. As a state node may contain information regarding location and time, an edge may also contain further information such as distance, heading angle, weather information, estimated cost weight etc., which can be calculated and assigned to the respective edge. When creating the grid with the plurality of edges, specific constraints may also be taken into account.

[0071] Such constraints may e.g. comprise geographic constraints. Within the grid, edges typically may not cross land areas. The plurality of edges may not pass state nodes with limited water depth, where a ship may not sail. The plurality of edges may not exceed a maximum sailing distance, which may reduce unreasonable connections between respective state nodes on adjacent stages. Such constraints may e.g. comprise further feasible constraints. The speed of the maritime ship may e.g. not exceed or be lower than a certain value due to the limitation of the ship's engine power and the specifications of operation efficiency.

[0072] Considering the constraints described above, reasonable edges can be generated. The pseudocode is given as follows:

TABLE-US-00002 Edge generation   Input: Nodes;  max_dist: maximum distance ship can go;  S: ship performance model;  E: weather information; Output: Graph Start: For nodes between two adjacent stages:  If (path between two nodes > bath(dl))  and (distance between two nodes < max_dist):   speed = S.estimate_v(nodes, E)   if speed in SpeedRange:    weight = S.estimate_power(speed, E)    Graph.add_edge(node1, node2, [weight])  Return Graph

[0073] One example of a generated graph is shown in FIG. 6. As shown, the graph is composed of three-dimensional variables. From the start state node to the final destination state node, the grid is divided into n stages. There are several state nodes composed of geographic locations and associated arrival time (also related to sailing speeds along the state edge). In the end, the algorithm may generate n end states (candidate routes), which a ship can follow to be sailing the whole voyage. These n end states will form a Pareto front of the routing optimization with respect to multi-objectives, i.e., optimal sailing ETA, minimum fuel consumption, and/or minimum emission for each candidate route.

[0074] After generating the grid, e.g. the 3D geographic state nodes shown in FIG. 6 and the associated time set for each state node as shown in FIG. 5, the preliminarily generated optimal route algorithm, e.g. the Dijkstra algorithm or any other similar algorithm, may be used to find candidate optimal routes with a series of ETAs. Those candidate ship routes may be refined by the genetic algorithm to provide the optimal solution for route optimization.

[0075] The implementation of the hybrid route optimization algorithm is given by the following pseudocode, wherein the preliminarily generated optimal route algorithm and the genetic algorithm used in the code are briefly presented as well.

TABLE-US-00003 Hybrid model for ship route optimization   Input: dep: departure; des: destination; v: service speed;  st: start time; et: end time; E: weather information;  S: ship performance model; B: bathymetry;  Dic: other setting parameters Output: optimal route and corresponding speed at each node Start:  Nodes←NodeGenerator(dep, des, v, **Dic)  GeoC←GeoConstraint(Nodes, B)  Timeset←TimeGenerator(Nodes, st, et **Dic)  TimeC←TimeConstraint(Timeset, S)  Nodes←AddTimeAxis(Nodes, Timeset)  Edges←AddEdge(Nodes, Timeset, GeoC, TimeC)  Graph←GraphGenerator(Nodes, Edges S, E, **Dic)  Dijk_path←Dijkstra_path(Graph)  Final_path←GeneticA(Dijk_path) Return Final_path

[0076] FIG. 7 shows a schematic diagram of a simplified graph having a plurality of state nodes and a plurality of edges, wherein a Dijkstra algorithm as a preliminarily generated optimal route algorithm is applied on the simplified graph. The Dijkstra algorithm may be applied on the graph to provide an optimal route for different ETAs. Each route may comprise state nodes with information of longitude, latitude and arrival time. The Dijkstra algorithm works by visiting edges in the graph starting with the starting node. It follows two basic principles: firstly, a sub-route of a shortest-path route is itself a shortest-path route, and secondly, with a given shortest distance, x, between points A and C, a path going from point A to C through a third point B will always be of a distance greater than or equal to x.

[0077] The basic procedure of the Dijkstra algorithm is illustrated in FIG. 7, wherein the departure state node and the destination state node are marked as “Start” and “Destination”, respectively. There may be many candidate routes/paths to go from “Start” to “Destination”, which may be composed of a series of sub-paths. For each sub-path, its starting point is connected to all of its neighboring points by assigning certain cost values (e.g. fuel consumption). The optimal sub-path follows the line with the lowest value, while this line typically is not used. When a line reaches a point which has already been tested, it is used to compare the current cost to the sub-destination point with preceding options. If the end point cost for the newly tested route is smaller than the original, the new cost is assigned to that point and the original route dismissed as part of an optimal solution. Following this searching procedure, routes evolve towards the end point, and one optimal route remains. In FIG. 7, the bold lines mark the routes with the smallest values, i.e. an optimal route.

[0078] FIG. 8 shows a schematic diagram of an individual of a plurality of individuals in relation to a great circle route. The routes obtained by the preliminarily generated optimal route algorithm, e.g. the Dijkstra algorithm or any other similar algorithm, may further be improved by the genetic algorithm. Genetic algorithm components which may e.g. be applied are population initialization, selection, and/or crossover.

[0079] The output of the preliminarily generated optimal route algorithm, e.g. the Dijkstra algorithm or any other similar algorithm, gives a path and its corresponding arrival time at each node in the path. An individual defined herein e.g. has two set of variables, one for the deviation of the geometrical points in the path, and the other for the deviation of arrival time at each node. The initial population may give a number of individuals as defined above. The fitness function of the genetic algorithm may be the same as the objective function above, which may return a power consumption for a path with location and arrival time. An individual may be added to the shortest path and the fitness value of the new changed path may be calculated by the fitness function. The selection of parents for breeding may e.g. use a stochastic universal sampling method as e.g. introduced in the paper by James Baker, “Reducing bias and inefficiency in the selection algorithm,” Proceedings of the Second International Conference on Genetic Algorithms, pp. 14 to 21, 1986. This approach may represent a further development of the fitness proportion selection method. It may create a wheel which may be associated with each individual and that may have a size proportional to the fitness of the individual. Furthermore, the crossover operator may be adopted. Firstly, a point may be chosen randomly in an individual for both sets of variables. The sequence of chromosome from the first parent to the left of the crossover point and the remaining part of chromosome from the second parent may be combined together to be the offspring. Transfusion may also be added which will put new individuals into the population every several steps in order to avoid premature convergence of the population. The genetic algorithm thus relates to metaheuristics inspired by the theory of evolution, using concepts such as natural selection, reproduction, genetic heritage and mutation.

[0080] An exemplary refined algorithm for route optimization may e.g. be composed of traditional genetic algorithm components, such as population initialization, selection, mutation and crossover, and a local optimization algorithm, e.g. a Dijkstra algorithm or any other similar algorithm, and transfusion. The local optimization algorithm may e.g. be responsible for giving instructive chromosomes for the population. Transfusion may avoid a premature convergence of the population.

[0081] An exemplary pseudocode for the refined algorithm is given as follows:

TABLE-US-00004 HGA  Input: dep: start coordinate; des: end coordinate; r: resolution;  bath: bathymetry info; met: meteorology info; sm: ship model  Output: bestPop: best population;  Start:    Nodeset←NodeGenerator(dep, des, r) # 1   Graph(V,E)←GraphGenerator(Nodeset, bathy)#2   SpecificIndividuals(SI)←Dijkstra(Graph, met, sm)#3   POP←initial_population(Graph) + SI   While cost(POP) not converge:    Parents←Selection(POP) # 4    Parents←Mutation(Parent) # 5    If EvolveTimes%3←0:     POP←Transfusion( ) + parents # 6    Else:     C←Crossover(parents) # 7     POP←parents    bestPop←POP  Return bestPop

[0082] The first step may be to initialize the geographic state nodes/waypoints between the departure location and the destination location.

[0083] A route may be divided into several stages along the great circle path. For each stage, several state nodes/waypoints perpendicular to the great circle sub-route may be generated.

[0084] The graph may be generated based on the plurality of state nodes. The graph may be used for creating feasible connections/edges between the state nodes on adjacent stages.

TABLE-US-00005   Graph  Input: Nodeset; max_dist: maximum distance ship can go from  one waypoint; bath: bathymetry info; dl: water depth limitation  Output: Graph  Start:  For nodes between two adjacent stages:   If (path between two nodes > bath(dl))    and (distance between two nodes < max_dist):     Graph.add_edge(node1, node2)  Return Graph

[0085] An individual may be defined as a path between the departure location and the destination location. It may comprise state nodes in every stage. A feasible individual may be defined based on a connection/edge defined in the graph.

[0086] The selection method uses a fitness proportionate selection, which is to choose a certain proportion of the population with low fitness value. Alternatively, it could be changed to truncation selection, which repeatedly selects the best individual of a randomly chosen subset.

[0087] In order to give a valid mutation on an individual, the following approach may be used:

TABLE-US-00006 Mutation    Input: individual; Graph  Output: mutate individual  Start:  Rind← randomly choose position from an  individual  Inode← in-nodes of individual[Rind]  Onode← out-nodes of individual[Rind]  succ← successors of Inode  pred← predecessor of Onode  AvailNodes← Unique(succ, pred) -  individual[Rind]  individual[Rind]← randomly choose AvailNodes  return individual

[0088] To demonstrate the application of the hybrid route optimization algorithm for route optimization, a ship voyage crossing the North Atlantic Ocean from the European side to New York during a winter season is chosen. In order to compare the benefits of using the hybrid route optimization algorithm for routing optimization, a voyage in January is selected. In this example, the weather information is taken from an ECMWF ERA-interim dataset.

[0089] FIG. 9 shows a schematic diagram of different optimal routes for different estimated times of arrival (ETAs). The ETAs used here are referring to the approximate sailing time that is required in order to give the estimation, rather than providing the specific date or time, which is the standard in the maritime industry for ETAs. The number of state nodes generated in this example is 18381 and the number of arcs/edges assigned is 151424. In total, 65 optimal routes are available for different ETAs, whereas the ETAs range from 96 h to 128 h with a 0.5 h time interval. In this example, the route as shown in FIG. 9 is chosen from a part of a real voyage measured by a container ship. It started at the star mark and ended at the circle mark. The diagram shows all the 65 optimal routes.

[0090] FIG. 10 shows a schematic diagram of a Pareto front for different estimated times of arrival (ETAs) and different power consumptions. The ETAs used here are referring to the approximate sailing time that is required in order to give the estimation, rather than providing the specific date or time, which is the standard in the maritime industry for ETAs. The Pareto front refers to a set of Pareto efficient allocations, which may be depicted graphically. As the exemplary 65 optimal routes are all optimal routes for their respective ETA, the Pareto front can be obtained from them. The diagram indicates that the optimal route for this voyage may e.g. be at an ETA between 105 h and 110 h, while routes with long ETAs correspond to routes which differ significantly from the shortest distance route in order to avoid little storms.

[0091] FIG. 11 shows a schematic diagram of an optimal route of a maritime ship in comparison to an actual route of the maritime ship. The ETAs used here are referring to the approximate sailing time that is required in order to give the estimation, rather than providing the specific date or time, which is the standard in the maritime industry for ETAs. The ETA of the actual route is 105.8 h. An optimal route with approximately the same ETA as the actual route (having an ETA of 106 h) is selected for comparison. The diagram shows the difference between their respective trajectories.

[0092] FIG. 12 shows a schematic diagram of a speed of a maritime ship and a wave characteristic for an optimal route and an actual route of a maritime ship. Exemplarily, the wave characteristic refers to a significant wave height H.sub.s. The optimal route successfully avoids the largest significant wave height H.sub.s and allows for an exemplary 6.32% power consumption reduction. The wave characteristic may, however, also refer to a minimum wave height, a maximum wave height, a wave period, a wave propagation direction, and/or a wave spectrum.

[0093] FIG. 13 shows a schematic diagram of wave characteristics at different times during a voyage. Exemplarily, the wave characteristic refers to a significant wave height H.sub.s. The diagram shows that the optimal route may be determined so as to avoid storm by reducing the speed at the beginning of the voyage. The wave characteristics may, however, also refer to minimum wave heights, maximum wave heights, wave periods, wave propagation directions, and/or wave spectra.

[0094] In summary, a hybrid routing optimization algorithm (HROA) for solving the route optimization problem is provided. The approach may combine a preliminarily generated optimal route algorithm, such as the Dijkstra algorithm or any other similar algorithm, and a genetic algorithm for a more efficient route optimization, based on a graph along the sailing area. The approach has several advantages with regard to route optimization. For example, the approach may allow to optimize a route with respect to multi-objectives, e.g. an accurate ETA and minimum fuel consumption. A trajectory and respective speeds from the planned routes can be further optimized by the genetic algorithm in order to ease actual ship navigation and to avoid extra power consumption through refining course changes. For computational efficiency, parallel computing can easily be applied within the approach, and recalculation can be done during the voyage without a new setup if there are deviations over the states. The performance of the approach is also demonstrated for an exemplary route planning during a winter season when sailing in the North Atlantic. The example shows that the approach has great potential to lower the power consumption and it can provide a ship's sailing schedule with a more accurate expected time of arrival. This algorithm can also overcome the difficulties of conventional algorithms. In particular, it may be easy to consider additional variables such as time and speed in the optimization process. It is demonstrated by an exemplary case that the hybrid route optimization algorithm can easily avoid high significant wave heights H.sub.s in storm zones. The approach further turns out to be suitable for providing reliable routes at rough sea conditions. The approach may also provide the Pareto front which may help users to make tradeoffs within or along the front.

[0095] This work has received funding from the EU FP7 SpaceNav project (grant agreement no. 607371) and the EU Horizon2020 EONav project (grant agreement no. 687537).

REFERENCE NUMERALS

[0096] 100 Apparatus [0097] 101 Database [0098] 103 Processor [0099] 200 Method [0100] 201 Generating [0101] 203 Determining [0102] 205 Appending [0103] 207 Generating [0104] 209 Generating [0105] 211 Applying [0106] 213 Applying