AIS based shipping routes using the dijkstra algorithm

• Autorzy: Silveira P. , Teixeira A. P. , Guedes-Soares C.

Identyfikatory

DOI

10.12716/1001.13.03.11

• Języki publikacji: EN

Abstrakty

EN

This paper proposes an approach for identifying and characterizing shipping routes using information contained in Automatic Identification System messages broadcasted by ships and recorded by the coastal Vessel Traffic Service centre. The approach consists of using historical Automatic Identification System data to build a graph, where nodes are cells of a grid covering the geographical area being studied and the weights of directional edges are inversely related to ship movements between cells. Based on this graph, the Dijkstra algorithm is used to identify a potential safe route, assumed to be the most used route by ships between two locations. A second graph is created simultaneously, with the same nodes and edges, but with edge weights equal to the average speed of transitions between cells, thus allowing the determination of the average speed profile for any possible path within the graph. The proposed approach is applied to two scenarios: an approach to the port of Lisbon and the entry through the fairway to a RO-RO terminal in the port of Setubal in Portugal.

Słowa kluczowe

EN

Dijkstra’s Algorithm; AIS Data; Automatic Identification System (AIS); AIS based shipping routes; shipping routes; Vessel Traffic Service (VTS); port of Setubal; Ro-Ro Terminal

• Wydawca: Faculty of Navigation, Gdynia Maritime University
• Czasopismo: TransNav : International Journal on Marine Navigation and Safety of Sea Transportation
• Rocznik: 2019
• Tom: Vol. 13, no. 3
• Strony: 565--571
• Opis fizyczny: Bibliogr. 19 poz., rys.

Twórcy

autor

Silveira P.

• Instituto Superior Tecnico (IST) , Lisboa, Portugal

autor

Teixeira A. P.

• Instituto Superior Tecnico (IST) , Lisboa, Portugal

autor

Guedes-Soares C.

• Instituto Superior Tecnico (IST) , Lisboa, Portugal

Bibliografia

• 1. Cormen, T., Leiserson, C., Rivest, R., & Clifford, S. (2009). Introduction to Algorithms (3rd ed.). The MIT Press.
• 2. Dijkstra, E. W. (1959). A Note on Two Problems in Connexion with Graphs. Numerische Mathematik, 1(1), 269–271. http://doi.org/10.1007/BF01386390 - doi:10.1007/BF01386390
• 3. Etienne, L., Devogele, T., & Bouju, A. (2010). Spatio-Temporal Trajectory Analysis of Mobile Objects Following the Same Itinerary. The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, 38(II), 86–91. http://doi.org/10.1007/s11263-012-0594-8 - doi:10.1007/s11263-012-0594-8
• 4. IMO. (20178). IMO - Ships’ routeing (2017 Edition). International Maritime Organization.
• 5. ITU. (2014). Technical characteristics for an automatic identification system using time division multiple access in the VHF maritime mobile frequency band, M.1371-5. International Telecommunication Union.
• 6. Joo, S.Y., Cho, T.J., Cha, J.M., Yang, J.H., Kwon, Y.K. (2012). An economic ship routing system based on a minimal dynamic-cost path search algorithm. KIPS Trans. Comput. Commun. Syst. 1 (2), 79–86. - doi:10.3745/KTCCS.2012.1.2.079
• 7. Mannarini G., Coppini G., Oddo P., Pinardi N.: A Prototype of Ship Routing Decision Support System for an Operational Oceanographic Service. TransNav, the International Journal on Marine Navigation and Safety of Sea Transportation, Vol. 7, No. 1, doi:10.12716/1001.07.01.06, pp. 53-59, 2013
• 8. Neumann T.: Vessels Route Planning Problem with Uncertain Data. TransNav, the International Journal on Marine Navigation and Safety of Sea Transportation, Vol. 10, No. 3, doi:10.12716/1001.10.03.11, pp. 459-464, 2016
• 9. Pallotta, G., Vespe, M., & Bryan, K. (2013). Vessel pattern knowledge discovery from AIS data: A framework for anomaly detection and route prediction. Entropy, 15(6), 2218–2245. http://doi.org/10.3390/e15062218. - doi:10.3390/e15062218
• 10. Rong, H., Teixeira, A.P. and Guedes Soares, C., (2015a). Simulation and analysis of maritime traffic in the Tagus River Estuary using AIS data, Maritime Technology and Engineering, Guedes Soares, C. & Santos T.A. (Eds.), Taylor & Francis Group, London, UK, pp. 185-194. - doi:10.1201/b17494-26
• 11. Rong, H., Teixeira, A.P. and Guedes Soares, C. (2015b). Evaluation of near-collisions in the Tagus River Estuary using a marine traffic simulation model, Scientific Journals of the Maritime University of Szczecin, 43 (115), pp. 68–78, (ISSN 1733-8670).
• 12. Rong, H., Teixeira, A.P. and Guedes Soares, C. (2016). Assessment and characterization of near ship collision scenarios off the coast of Portugal. Maritime Technology and Engineering 3. Guedes Soares & Santos (Eds.), Taylor & Francis Group, London, 871–878. - doi:10.1201/b21890-115
• 13. Rong, H., Teixeira, A.P. and Guedes Soares, C. (2018). A model for predicting ship destination routes based on AIS data, Maritime Transportation and Harvesting of Sea Resources, Guedes Soares & Teixeira (Eds.), Taylor & Francis Group, London, pp. 257-264.
• 14. Savitzky, A., & Golay, M. J. E. (1964). Smoothing and Differentiation of Data by Simplified Least Squares Procedures. Analytical Chemistry, 36(8), 1627–1639. - doi:10.1021/ac60214a047
• 15. Silveira, P. Teixeira, A.P. and Guedes Soares, C. (2012). Analysis of maritime traffic off the coast of Portugal, Maritime Engineering and Technology, C. Guedes Soares, Y. Garbatov S. Sutulo T. A. Santos, (Eds.), pp. 35-41, Taylor & Francis Group. - doi:10.1201/b12726-7
• 16. Silveira, P., Teixeira, A., & Guedes Soares, C. (2013). Use of AIS Data to Characterise Marine Traffic Patterns and Ship Collision Risk off the Coast of Portugal. The Journal of Navigation, 66, 879–898. http://doi.org/10.1017/ S0373463313000519. - doi:10.1017/S0373463313000519
• 17. Silveira, P., Teixeira, A.P. and Guedes Soares, C. (2015). Assessment of ship collision estimation methods using AIS data, Maritime Technology and Engineering, Guedes Soares, C. & Santos T.A. (Eds.), Taylor & Francis Group, London, UK, pp. 195-204. - doi:10.1201/b17494-27
• 18. Takashima K., Mezaoui B., Shoji R.: On the Fuel Saving Operation for Coastal Merchant Ships using Weather Routing. TransNav, the International Journal on Marine Navigation and Safety of Sea Transportation, Vol. 3, No. 4, pp. 401-406, 2009
• 19. Vespe, M., Visentini, I., Bryan, K., & Braca, P. (2012). Unsupervised learning of maritime traffic patterns for anomaly detection. 9th IET Data Fusion & Target Tracking Conference (DF&TT 2012): Algorithms & Applications, 14–14. http://doi.org/10.1049/cp.2012.0414. - doi:10.1049/cp.2012.0414

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).