Ships route planning in heavy-traffic marine area based on historical data

The paper considers the problem of planning a route for sea vessel shifting. Under the conditions of heavy traffic, navigators should follow the traffic scheme accepted in this defined water area. Such a pattern may not be officially established while representing collective experience in navigation. In this case, route planning based on the data on the movement of other ships that had been in this water area before (the same idea underlies the methods of "big data" tasks) appears to be productive. In the papers published earlier, such route planning employed a cluster analysis of retrospective data on the movement of ships, which involved dividing the water area into sections and isolating their characteristic values of speeds and courses. The problem with this approach was the choice of partitioning parameters, which had to be set for each specific water area separately. This paper proposes another approach when the graph of potential routes includes a selection of the trajectories of individual ships that had been previously implemented in the selected water area. The article regards a method for constructing such a graph of possible routes, estimates the number of its vertices and edges, and gives recommendations on the choice of a method for finding the shortest path on this graph. A possible method premised on the notion of combining straight and maneuverable sections of vessel traffic that can be applied to interpolate the missing data required to build a graph is discussed. Examples of route planning in a number of real water areas are given: Vladivostok, Tokyo Bay, the Tsugaru Strait.

1. Tam Ch.K., Bucknall R., Greig A. Review of collision avoidance and path planning methods for ships in close range encounters. Journal of Navigation. 2009;62(3):455–476. DOI: 10.1017/S0373463308005134.

2. Obshchiye polozheniya ob ustanovlenii putey dvizheniya sudov. Izdaniye GUNiO MO SSSR; 1987. № 9036. (In Russ.).

3. Grinyak V.M., Ivanenko Y.S., Lulko V.I., Shulenina A.V., Shurygin A.V. Multi-measure navigation safety estimation and digital represent for marine area. Modelirovaniye, optimizatsiya i informatsionnyye tekhnologii = Modelling, Optimization and Information Technologies. 2020;8(1):40–41. (In Russ.).

4. Grinyak V.M., Shulenina A.V., Prudnikova L.I., Devyatisilnyi A.S. Ships route planning on heavy-traffic marine area. Modelirovaniye, optimizatsiya i informatsionnyye tekhnologii = Modelling, Optimization and Information Technologies. 2021;9(2). DOI: 10.26102/2310-6018/2021.33.2.018. (In Russ.).

5. Grinyak V.M., Shulenina A.V., Ivanenko Yu.S. Ship routes planning based on traffic clustering. Journal of Physics: Conference Series. 2021;13:012080. DOI: 10.1088/1742-6596/1864/1/012080.

6. Chertkov A.A. Avtomatizaciya vybora kratchajshih marshrutov sudov na osnove modificirovannogo algoritma Bellmana-Forda. Vestnik Gosudarstvennogo universiteta morskogo i rechnogo flota imeni admirala S.O. Makarova. 2017;9(5):1113–1122. DOI: 10.21821/2309-5180-2017-9-5-1113-1122. (In Russ.).

7. Wang H.B., Li X.B., Li P.F., Veremey E.I., Sotnikova M.V. Application of real-coded genetic algorithm in ship weather routing. Journal of Navigation. 2018;71(4):989–1010. DOI:10.1017/S0373463318000048.

8. Lazarowska A. Ship’s trajectory planning for collision avoidance at sea based on ant colony otimisation. Journal of Navigation. 2015;68(2):291–307. DOI: 10.1017/S0373463314000708.

9. Pershina L.A., Astreina L.S. Ship routing based on weather conditions. Ekspluatatsiya morskogo transporta. 2019;(2):30–38. (In Russ.).

10. Fedorenko K.V., Olovyannikov A.L. Issledovanie osnovnyh parametrov geneticheskogo algoritma primenitel'no k zadache poiska optimal'nogo marshruta. Vestnik Gosudarstvennogo universiteta morskogo i rechnogo flota imeni admirala S.O. Makarova. 2017;9(4):714–723. DOI: 10.21821/2309-5180-2017-9-4-714-723. (In Russ.).

11. Pallotta G., Vespe M., Bryan K. Vessel pattern knowledge discovery from AIS data: a framework for anomaly detection and route prediction. Entropy. 2013;15:2218–2245.

12. Naus K. Drafting route plan templates for ships on the basis of AIS historical data. Journal of Navigation. 2019;73(3):726–745.

13. Zhen R., Jin Y., Hu Q., Shao Zh., Niktakos N. Maritime anomaly detection within coastal waters based on vessel trajectory clustering and naïve Bayes classifier. Journal of Navigation. 2017;70(3):648–670.

14. Zhao L., Shi G. Maritime anomaly detection using density-based clustering and recurrent neural network. Journal of Navigation. 2019;72(4):894–916.

15. Tang H., Wei L., Yin Y., Shen H., Qi Y. Detection of abnormal vessel behaviour based on probabilistic directed graph model. Journal of Navigation. 2019;73(5):1014–1035.