Avoiding sudden maritime risk: A new variable speed route planning model by integrating Spatio-temporal dimension

Variable speed route planning is important for ships to avoid large-scale and sudden risk. However, in the face of massive amounts of grid data, current algorithms are still unable to establish a mathematical model to effectively avoid such risk in a variable speed manner. Therefore, this paper proposes a variable speed maritime route planning model integrating spatial and temporal considerations. First, in the temporal dimension, a bi-objective mixed-integer linear programming model is developed considering the minimization of risk and residual action power, and selection and mutation operators in the genetic algorithm are improved to solve the programming model. Second, a segment parallel A*(SPA*) method is proposed to improve spatial planning capacity. SPA* successfully reduces runtime by designing a parallel computing structure and adaptive heuristic function to simultaneously handle several segments of the path considering variable speed and reduce the expansion of useless grids. Three rounds of simulation experiments are conducted on small and large datasets with sudden and continuous risk scenarios in the vicinity of the South China Sea and Indonesian Throughflow, respectively. These experiments involve comparative analyses of our algorithm with the uniform speed scheme and with three conventional algorithms. The results show that in the face of both sudden and continuous risks, the path of our model outperforms the uniform speed scheme in all cases, takes an average of only 13.11 s to plan a route on the large dataset and is more compliant with the norms of the International Maritime Organization (IMO). Numerically, it is approximately 6 times and 7 times lower than the best performing of the remaining algorithms in terms of runtime and the rate of violating IMO.