Vessel route planning based on historical traffic data and model representations of computational geometry

The paper is concerned with maritime safety. The problem of planning a route for a vessel crossing water areas with heavy traffic is considered. When sailing under such conditions, navigators follow a trajectory that is established in a specific water area. It can be defined officially or be accepted on an informal basis while representing collective navigation experience. If the latter, it seems productive to plan a route using the data on the traffic of other ships that crossed the water area earlier (the same idea underlies "big data" task methods). In the papers published earlier, such route planning was based on a cluster analysis of retrospective data on ship traffic, which involved dividing the water area into sections and highlighting characteristic values of speeds and courses in them. The problem with this approach was the choice of partitioning parameters which had to be set for each specific water area separately. In this paper, another approach is proposed, when the graph of possible routes includes a selection of the trajectories of individual ships that were previously implemented in the specific water area. This article further develops the methods for solving the problem of ship route planning in areas with heavy traffic. The proposed method is based on the formation of a possible route graph from a set of intersecting broken lines, each of which represents a route implemented earlier. Each edge of the graph is assigned a measure of its “popularity”, which characterizes the proximity of other edges to it. The shortest path on a weighted graph is constructed considering not only the geometric length of the edges, but also the measure of their “popularity”. The paper regards the formation of a possible route graph, a number of its nodes and edges is esteemed, recommendations as to how to select a method for defining the shortest path on its graph are provided. Examples of route planning for the Tsugaru Strait and the Seaport of Vladivostok are provided.

1. Frank M.O., Ovchinnikov K.D., Ryzhov V.A. Review of Russian and foreign experience of marine unmanned surface vehicles development. Morskiye intellektual'nyye tekhnologii = Marine intellectual technologies. 2022;57(3-1):22–28. DOI: 10.37220/MIT.2022.57.3.002. (In Russ.).

2. Korenev A.S., Khabarov S.P., Shpectorov A.G. A route calculation for unmanned vessel. Morskiye intellektual'nyye tekhnologii = Marine intellectual technologies. 2021;54(4-1):158–165. DOI: 10.37220/MIT.2021.54.4.047. (In Russ.).

3. Dyda A.A., Pushkarev I.I., Chumakova K.N. Static obstacles avoidance algorithm for unmanned ship. Vestnik Gosudarstvennogo universiteta morskogo i rechnogo flota imeni admirala S.O. Makarova. 2021;13(3):307–315. DOI: 10.21821/2309-5180-2021-13-3-307-315. (In Russ.).

4. Ardelyanov N.P. Intermediate results of the e-navigation concept. Vestnik gosudarstvennogo morskogo universiteta imeni admirala F.F. Ushakova. 2022;39(2):8–11. (In Russ.).

5. Rivkin B.S. e-Navigation: Five Years Later. Giroskopiya i navigatsiya = Gyroscopy and Navigation. 2020;28(1):101–120. DOI: 10.17285/0869-7035.0026. (In Russ.).

6. Pismarkin D.D. Course stability and optimization of a ship's way of a vessel at external disturbing influences in criteria of the concept of development of e- Navigation. Transport business of Russia. 2020;(2):152–156. (In Russ.).

7. Tsolakis A., Benders D., de Groot O., Negenborn R.R., Reppa V., Ferranti L. COLREGs-aware Trajectory Optimization for Autonomous Surface Vessels. IFAC-PapersOnLine. 2022; 55(31):269–274. DOI: 10.1016/j.ifacol.2022.10.441.

8. 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.

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

10. Sotnikova M.V. Algorithms of marine ships routing taking into account weather forecast, Vestnik of Saint Petersburg university applied mathematics. Computer science. Control processes. 2009;(2):181–196. (In Russ.).

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

12. Taratynov V.V. Celesoobraznost' razdeleniya morskih putej. Morskoj flot. 1969;(9):19–20. (In Russ.).

13. Lentaryov A.A. Osnovy teorii upravleniya dvizheniem sudov. Vladivostok: Morskoj gosudarstvennyj universitet; 2018. 181 p. (In Russ.).

14. Grinyak V.M., Devyatisilnyi A.S., Ivanenko Y.S. Decision support for marine traffic control based on route clustering. Vestnik Gosudarstvennogo universiteta morskogo i rechnogo flota imeni admirala S.O. Makarova. 2020;12(3):436–449. DOI: 10.21821/2309-5180-2020-12-3-436-449. (In Russ.).

15. Grinyak V.M., Shulenina A.V. Marine traffic data clustering for ships route planning. Informatsionnyye tekhnologii = Information Technologies. 2021;27(11):607–615. DOI: 10.17587/it.27.607-615. (In Russ.).

16. Grinyak V.M, Devyatisilnyi A.S. Ships route planning in heavy-traffic marine area based on historical data. Modelirovaniye, optimizatsiya i informatsionnyye tekhnologii = Modeling, Optimization and Information Technology. 2022;10(3):25–26. DOI: 10.26102/2310-6018/2022.38.3.014. (In Russ.).

17. Onyango S.O., Owiredu S.O., Kim K.I., Yoo S.L. A Quasi-Intelligent Maritime Route Extraction from AIS Data. Sensors. 2022;22(22):8639. DOI: 10.3390/s22228639.

18. Grinyak V.M., Shurygin A.V. Programma sbora traektornyh dannyh o dvizhenii sudov iz otkrytyh internet istocnikov. Patent RU 2018618729. 19.07.2018. (In Russ.).

19. Golovchenko B.S., Grinyak V.M. Information system for vessels traffic data capture. Vestnik Gosudarstvennogo universiteta morskogo i rechnogo flota imeni admirala S.O. Makarova. 2014;(2):156–162. (In Russ.).

20. 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 = Modeling, Optimization and Information Technology. 2020;8(1). DOI: 10.26102/2310-6018/2020.28.1.003. (In Russ.).

21. Yager R., Filev D. Essentials of fuzzy modeling and control. New York: John Wiley & Sons; 1994. 388 р.

22. Yager R.R., Filev D.P. Generation of Fuzzy Rules by Mountain Clustering. Journal of Intelligent and Fuzzy Systems. 1994;2(3):209–219. DOI: 10.3233/IFS-1994-2301.

23. Aizerman M.A., Braverman E.M., Rozonoer L.I. Extrapolative problems in automatic control and the method of potential functions. American Mathematical Society Translations. 1970;(2):3. (In Russ.).

24. 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. DOI: 10.3390/e15062218.

25. 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. DOI: 10.1017/S0373463316000850.