Search

CN-122015863-A - Ship navigation real-time optimal route planning method based on improved genetic algorithm

CN122015863ACN 122015863 ACN122015863 ACN 122015863ACN-122015863-A

Abstract

The invention relates to the technical field of ship route planning, in particular to a ship navigation real-time optimal route planning method based on an improved genetic algorithm. And processing the input data by adopting an improved path search algorithm based on a comprehensive cost function, and generating an initial sailing path, wherein the cost function synchronously considers the length of a sailing section, sailing risk and punishment of violation. And (3) adopting an improved genetic algorithm comprising specific chromosome coding and multi-objective fitness functions to optimize the speed scheme of the initial path and generate an optimal speed distribution scheme. And fusing the initial path and the speed scheme, and outputting a route planning result comprising a route point sequence and recommended speeds of all the air sections. The invention realizes the integrated collaborative optimization of the path and the speed.

Inventors

  • HUANG JUN

Assignees

  • 江苏正沧航运科技有限公司

Dates

Publication Date
20260512
Application Date
20260227

Claims (10)

  1. 1. The real-time optimal route planning method for ship navigation based on the improved genetic algorithm is characterized by comprising the following steps: acquiring an input data set required by ship navigation path planning, wherein the input data set comprises ship static parameters, navigation environment prediction data and navigation constraint conditions, the ship static parameters comprise ship draft and maximum speed, the navigation environment prediction data comprise multi-period water depth data and flow velocity data, and the navigation constraint conditions comprise restricted navigation area coordinates and a lock open time window; processing the input data set based on an improved path search algorithm to generate an initial navigation path, wherein the improved path search algorithm adopts a comprehensive cost function to conduct node expansion, and the comprehensive cost function comprises a navigation section geographic length cost, a navigation risk cost and a violation punishment cost; performing speed scheme optimization processing on the initial navigation path by adopting an improved genetic algorithm to generate an optimal speed distribution scheme, wherein the improved genetic algorithm comprises a chromosome coding scheme and a multi-objective fitness function; And generating a final route planning result according to the initial navigation path and the optimal speed distribution scheme, wherein the final route planning result comprises a route point sequence and recommended speeds of all the navigation segments.
  2. 2. The improved genetic algorithm-based real-time optimal route planning method for ship navigation according to claim 1, wherein the improved path search algorithm-based processing the input data set to generate an initial navigation path comprises: constructing a search node network according to the starting point coordinates and the end point coordinates, wherein the search node network comprises a plurality of nodes to be expanded; for each node to be expanded, executing the following processing: Calculating the actual accumulated cost from the starting point to the current node, wherein the actual accumulated cost comprises a weighted sum of the geographical length cost of the voyage segment, the voyage risk cost and the violation penalty cost; Calculating heuristic estimated cost of the current node according to Euclidean distance between the current node coordinate and the terminal point coordinate, maximum navigational speed of the ship and average risk coefficient of the terminal point area; adding the actual accumulated cost and the heuristic estimated cost to obtain the comprehensive estimated cost of the current node; And selecting the node to be expanded with the minimum cost based on the comprehensive evaluation cost to perform path expansion until the node to be expanded is expanded to a final node, and generating an initial navigation path for connecting the starting point and the final point.
  3. 3. The improved genetic algorithm-based real-time optimal route planning method for ship navigation according to claim 2, wherein the calculating the actual cumulative cost from the starting point to the current node comprises: Extracting the geographical length of the navigation segment between the current node and the father node; acquiring water depth data corresponding to the predicted passing time in the sailing environment prediction data, and calculating sailing risk cost by combining the ship draft and the safety margin, wherein the sailing risk cost is in direct proportion to the reciprocal of the difference value of subtracting the ship draft from the water depth data and subtracting the safety margin from the water depth data; Judging whether the voyage section violates the voyage constraint condition, and if the voyage section passes through a voyage exclusion area and the reverse voyage or the passing time in a unidirectional voyage channel does not meet a ship lock open time window, setting the punishment cost as a preset maximum value; Multiplying the geographical length of the voyage segment by a distance weight coefficient, multiplying the voyage risk cost by a risk weight coefficient, multiplying the illegal punishment cost by a punishment weight coefficient, and adding to obtain the comprehensive cost of the current voyage segment; and adding the comprehensive cost of the current navigation segment to the actual accumulated cost from the starting point to the father node to obtain the actual accumulated cost from the starting point to the current node.
  4. 4. The method for real-time optimal route planning for ship navigation based on improved genetic algorithm according to claim 2, wherein said calculating the heuristic estimated cost of the current node comprises: Calculating Euclidean distance between the current node coordinates and the end point coordinates; calculating a minimum time estimated value based on the Euclidean distance according to the maximum navigational speed of the ship, wherein the minimum time estimated value is obtained by dividing the Euclidean distance by the maximum navigational speed of the ship; extracting historical navigation risk data within a preset radius range of a terminal point, and calculating an average risk coefficient of the terminal point region; And multiplying the minimum time estimated value by a weighted sum of the minimum time estimated value and the average risk coefficient of the end point region to generate heuristic estimated cost of the current node, wherein a risk weighting coefficient in the weighted sum is used for adjusting the influence degree of risks on heuristic estimation.
  5. 5. The method for real-time optimal route planning for ship voyage based on improved genetic algorithm according to claim 4, wherein said extracting historical voyage risk data within a preset radius range of the destination and calculating the average risk coefficient of the destination area comprises: setting a geographical radius range by taking the terminal point coordinates as the center, and constructing a terminal point region range; Inquiring all historical sailing event records falling into the range of the end point area from a sailing risk database, wherein each historical sailing event record comprises an event occurrence position, an event type and a risk level evaluation value; Distributing risk weight factors for each event type according to the event type, wherein the high risk event type corresponds to a higher risk weight factor; Multiplying the risk level evaluation value of each historical sailing event record by a corresponding risk weight factor to obtain a weighted risk value; And summing the weighted risk values of all the historical sailing event records, and dividing the weighted risk values by the total number of the historical sailing event records to obtain the average risk coefficient of the end point region.
  6. 6. The method for real-time optimal route planning for ship navigation based on improved genetic algorithm according to claim 1, wherein the performing speed scheme optimization processing on the initial navigation path by adopting improved genetic algorithm to generate an optimal speed allocation scheme comprises the following steps: performing space division processing on the initial navigation path to obtain a plurality of continuous space; constructing a chromosome by adopting a real vector coding mode, wherein each gene of the chromosome corresponds to a navigational speed value of a navigational section, and the navigational speed value of each navigational section is in a range between the minimum navigational speed of the ship and the official speed limit of the navigational section; Randomly generating an initial population comprising a plurality of chromosomes, each chromosome representing a complete speed assignment scheme; Calculating fitness value of each chromosome based on a multi-objective fitness function, wherein the multi-objective fitness function comprises total voyage time cost, total fuel consumption cost, total voyage risk cost and late punishment cost; performing genetic operation iterative processing on the initial population, wherein the genetic operation iterative processing comprises a selection operation, a crossover operation, a mutation operation and an elite retention operation; and when the iteration termination condition is met, outputting the chromosome with the optimal fitness value as an optimal speed allocation scheme.
  7. 7. The improved genetic algorithm-based real-time optimal path planning method for ship navigation according to claim 6, wherein the calculating fitness value of each chromosome based on the multi-objective fitness function comprises: calculating the voyage time of each voyage according to the voyage value sequence in the chromosome, wherein the voyage time is the algebraic sum of the voyage length divided by the voyage value and the flow velocity data of the predicted transit time; accumulating the voyage time of each voyage section and adding the predicted ship lock waiting time to obtain the total voyage time; calculating total fuel consumption according to the ship fuel consumption coefficient and the voyage time of each voyage, wherein the total fuel consumption is the sum of multiplying the fuel consumption coefficient of each voyage by the cube of the voyage speed value and multiplying the cube of the voyage speed value by the voyage time of each voyage; calculating navigation risks of each navigation segment based on the navigation speed value and the predicted transit time water depth data, and accumulating to obtain total navigation risks; Judging whether the total navigation time exceeds the final arrival time of the service requirement, if so, calculating the late penalty cost, wherein the late penalty cost is the excess time multiplied by a penalty coefficient; And adding the total voyage time with a time weight coefficient, the total fuel consumption with a fuel weight coefficient, the total voyage risk with a risk weight coefficient and the late punishment cost to obtain the fitness value of the chromosome.
  8. 8. The method for real-time optimal planning of navigation of a vessel based on an improved genetic algorithm as claimed in claim 6, wherein said performing an iterative process of genetic operations on said initial population comprises: selecting a parent chromosome from the current population by adopting a tournament selection method, wherein the tournament selection method randomly selects a fixed number of individuals each time, and selects the individuals with the optimal fitness value from the individuals to enter a mating pool; Performing simulated binary crossover operation on the parent chromosomes in the mating pool according to preset crossover probability to generate offspring chromosomes; performing polynomial mutation operation on the offspring chromosomes according to preset mutation probability, and disturbing randomly selected gene values in the chromosomes; Selecting a preset number of individuals with optimal fitness values from the current population, and directly reserving the individuals to the next generation population; Combining the offspring chromosomes generated through the crossover operation and the mutation operation with the individuals which are directly reserved to form a new generation population; and repeatedly executing the selection operation, the crossover operation, the mutation operation and the elite retention operation until the iteration termination condition is met.
  9. 9. The method for real-time optimal route planning for ship voyage based on improved genetic algorithm according to claim 7, wherein said calculating voyage time of each leg based on the sequence of voyage values in the chromosome comprises: Acquiring flow velocity data corresponding to the predicted passing time of each navigation section in the navigation environment prediction data, wherein the flow velocity data comprises flow velocity size and direction; when the ship sailing direction is the same as the water flow direction, adding the sailing speed value and the flow speed data to obtain the actual ground sailing speed; when the ship sailing direction is opposite to the water flow direction, subtracting the sailing speed value from the flow speed data to obtain the actual ground sailing speed; Dividing the length of the navigation section by the actual ground speed to obtain the navigation time of the navigation section under the consideration of the influence of water flow.
  10. 10. The improved genetic algorithm-based real-time optimal route planning method for ship navigation according to claim 1, wherein the method further comprises: acquiring ship position data and environment monitoring data in real time in the actual sailing process of the ship; comparing the ship position data with a route point sequence in the final route planning result to generate a position deviation amount; Triggering a route re-planning process when the position deviation exceeds a preset threshold value; re-executing the processing based on the improved path searching algorithm and the processing adopting the improved genetic algorithm based on the current ship position, the residual end point and the updated navigation environment prediction data to generate an updated route planning result; And sending the updated route planning result to a ship navigation control system.

Description

Ship navigation real-time optimal route planning method based on improved genetic algorithm Technical Field The invention relates to the technical field of ship route planning, in particular to a ship navigation real-time optimal route planning method based on an improved genetic algorithm. Background Existing ship route planning methods typically treat path search and speed planning as two separate or sequential stages. In the path planning stage, common algorithms focus on finding the shortest or most time-saving path in the geospatial area, and the cost function is mostly centered on distance or estimated time. After the space path is obtained, the navigation time is estimated based on the fixed designed navigation speed or the simple average navigation speed, and whether the time sequence constraint such as a lock time window is met or not is judged according to the estimated navigation time. For dynamic navigation environment data, the risk assessment is often carried out only as a static check condition for path feasibility or afterwards. This separate processing mode has drawbacks. The initial path generated by taking the geometric length as a guide is likely to cross a risk area with insufficient water depth and complex flow state or to be too close to the boundary of a forbidden navigation area, and the initial path has hidden danger in safety. The method for timing verification by adopting fixed navigational speed is too coarse, when the path is longer or constraint is complex, the calculated time is very easy to appear and cannot meet the conditions of a ship lock window and the like, so that the whole planning scheme is not feasible, the path needs to be re-planned, and the efficiency is low. The value of the navigational speed directly influences the navigational time, the fuel consumption and the safety of passing through a high risk area, is a continuous variable which needs to be optimized finely, and the simple speed assumption cannot explore the optimal trade-off among punctual, economic and safety. The current technology needs to solve how to synchronously integrate dynamic environment risks and complex rule constraints in a path searching stage to generate a basic feasible space path, and how to systematically optimize the speed of the ship in each navigation section on the basis of the basic feasible space path, so as to realize global optimal planning from the space path to a navigation schedule. Disclosure of Invention The invention aims to solve the defects in the prior art, and provides a ship navigation real-time optimal route planning method based on an improved genetic algorithm. In order to achieve the purpose, the invention adopts the following technical scheme that the ship navigation real-time optimal route planning method based on the improved genetic algorithm comprises the following steps: acquiring an input data set required by ship navigation path planning, wherein the input data set comprises ship static parameters, navigation environment prediction data and navigation constraint conditions, the ship static parameters comprise ship draft and maximum speed, the navigation environment prediction data comprise multi-period water depth data and flow velocity data, and the navigation constraint conditions comprise restricted navigation area coordinates and a lock open time window; processing the input data set based on an improved path search algorithm to generate an initial navigation path, wherein the improved path search algorithm adopts a comprehensive cost function to conduct node expansion, and the comprehensive cost function comprises a navigation section geographic length cost, a navigation risk cost and a violation punishment cost; performing speed scheme optimization processing on the initial navigation path by adopting an improved genetic algorithm to generate an optimal speed distribution scheme, wherein the improved genetic algorithm comprises a chromosome coding scheme and a multi-objective fitness function; And generating a final route planning result according to the initial navigation path and the optimal speed distribution scheme, wherein the final route planning result comprises a route point sequence and recommended speeds of all the navigation segments. Preferably, the processing the input data set based on the improved path search algorithm generates an initial navigation path, including: constructing a search node network according to the starting point coordinates and the end point coordinates, wherein the search node network comprises a plurality of nodes to be expanded; for each node to be expanded, executing the following processing: Calculating the actual accumulated cost from the starting point to the current node, wherein the actual accumulated cost comprises a weighted sum of the geographical length cost of the voyage segment, the voyage risk cost and the violation penalty cost; Calculating heuristic estimated cost of the current node according