{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,20]],"date-time":"2026-05-20T03:49:44Z","timestamp":1779248984541,"version":"3.51.4"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2020,7,28]],"date-time":"2020-07-28T00:00:00Z","timestamp":1595894400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,7,28]],"date-time":"2020-07-28T00:00:00Z","timestamp":1595894400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Bus Inf Syst Eng"],"published-print":{"date-parts":[[2020,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The presented method reconstructs a network (a graph) from AIS data, which reflects vessel traffic and can be used for route planning. The approach consists of three main steps: maneuvering points detection, waypoints discovery, and edge construction. The maneuvering points detection uses the CUSUM method and reduces the amount of data for further processing. The genetic algorithm with spatial partitioning is used for waypoints discovery. Finally, edges connecting these waypoints form the final maritime traffic network. The approach aims at advancing the practice of maritime voyage planning, which is typically done manually by a ship\u2019s navigation officer. The authors demonstrate the results of the implementation using Apache Spark, a popular distributed and parallel computing framework. The method is evaluated by comparing the results with an on-line voyage planning application. The evaluation shows that the approach has the capacity to generate a graph which resembles the real-world maritime traffic network.<\/jats:p>","DOI":"10.1007\/s12599-020-00661-0","type":"journal-article","created":{"date-parts":[[2020,7,28]],"date-time":"2020-07-28T08:13:39Z","timestamp":1595924019000},"page":"435-450","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":63,"title":["Extracting Maritime Traffic Networks from AIS Data Using Evolutionary Algorithm"],"prefix":"10.1007","volume":"62","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4927-9992","authenticated-orcid":false,"given":"Dominik","family":"Filipiak","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5641-3160","authenticated-orcid":false,"given":"Krzysztof","family":"W\u0119cel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7603-7369","authenticated-orcid":false,"given":"Milena","family":"Str\u00f3\u017cyna","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha\u0142","family":"Michalak","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5464-9698","authenticated-orcid":false,"given":"Witold","family":"Abramowicz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,7,28]]},"reference":[{"issue":"3","key":"661_CR1","doi-asserted-by":"publisher","first-page":"722","DOI":"10.1109\/TITS.2017.2699635","volume":"19","author":"VF Arguedas","year":"2017","unstructured":"Arguedas VF, Pallotta G, Vespe M (2017) Maritime traffic networks: from historical positioning data to unsupervised maritime traffic monitoring. IEEE Trans Intell Transp Syst 19(3):722\u2013732","journal-title":"IEEE Trans Intell Transp Syst"},{"key":"661_CR2","volume-title":"Detection of abrupt changes: theory and application","author":"M Basseville","year":"1993","unstructured":"Basseville M, Nikiforov IV (1993) Detection of abrupt changes: theory and application. Prentice Hall, Englewood Cliffs"},{"issue":"8","key":"661_CR3","doi-asserted-by":"publisher","first-page":"716","DOI":"10.1073\/pnas.38.8.716","volume":"38","author":"R Bellman","year":"1952","unstructured":"Bellman R (1952) On the theory of dynamic programming. Proc Natl Acad Sci 38(8):716\u2013719","journal-title":"Proc Natl Acad Sci"},{"key":"661_CR4","unstructured":"Besse P, Guillouet B, Loubes JM, Fran\u00e7ois R (2015) Review and perspective for distance based trajectory clustering. arXiv preprint arXiv:150804904"},{"issue":"3","key":"661_CR5","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1002\/j.2161-4296.2001.tb00238.x","volume":"48","author":"S Bijlsma","year":"2001","unstructured":"Bijlsma S (2001) A computational method for the solution of optimal control problems in ship routing. Navigation 48(3):144\u2013154","journal-title":"Navigation"},{"key":"661_CR6","doi-asserted-by":"publisher","first-page":"551","DOI":"10.12716\/1001.08.04.09","volume":"8","author":"Y Cai","year":"2014","unstructured":"Cai Y, Wen Y, Wu L (2014) Ship route design for avoiding heavy weather and sea conditions. TransNav Int J Mar Navig Saf Sea Transp 8:551\u2013556","journal-title":"TransNav Int J Mar Navig Saf Sea Transp"},{"issue":"2","key":"661_CR7","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1017\/S0373463300009978","volume":"44","author":"S Calvert","year":"1991","unstructured":"Calvert S, Deakins E, Motte R (1991) A dynamic system for fuel optimization trans-ocean. J Navig 44(2):233\u2013265","journal-title":"J Navig"},{"key":"661_CR8","doi-asserted-by":"crossref","unstructured":"Chen Z, Guo J, Liu Q (2017) DBSCAN algorithm clustering for massive AIS data based on the Hadoop platform. In: 2017 International conference on industrial informatics-computing technology, intelligent technology, industrial information integration (ICIICII). IEEE, pp 25\u201328","DOI":"10.1109\/ICIICII.2017.72"},{"issue":"3","key":"661_CR9","doi-asserted-by":"publisher","first-page":"428","DOI":"10.1017\/S0373463300014053","volume":"43","author":"C De Wit","year":"1990","unstructured":"De Wit C (1990) Proposal for low cost ocean weather routeing. J Navig 43(3):428\u2013439","journal-title":"J Navig"},{"key":"661_CR10","doi-asserted-by":"crossref","unstructured":"Dobrkovic A, Iacob ME, van Hillegersberg J (2015) Using machine learning for unsupervised maritime waypoint discovery from streaming AIS data. In: Proceedings of the 15th international conference on knowledge technologies and data-driven business. ACM, p\u00a016","DOI":"10.1145\/2809563.2809573"},{"issue":"2\u20133","key":"661_CR11","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/s41060-017-0092-8","volume":"5","author":"A Dobrkovic","year":"2018","unstructured":"Dobrkovic A, Iacob ME, van Hillegersberg J (2018) Maritime pattern extraction and route reconstruction from incomplete ais data. Int J Data Sci Anal 5(2\u20133):111\u2013136","journal-title":"Int J Data Sci Anal"},{"key":"661_CR12","doi-asserted-by":"crossref","unstructured":"Ester M, Wittmann R (1998) Incremental generalization for mining in a data warehousing environment. In: International conference on extending database technology. Springer, Heidelberg, pp 135\u2013149","DOI":"10.1007\/BFb0100982"},{"key":"661_CR13","unstructured":"Ester M, Kriegel HP, Sander J, Xu X et al (1996) A density-based algorithm for discovering clusters in large spatial databases with noise. In: Kdd\u201996: Proceedings of the second international conference on knowledge discovery and data mining. pp 226\u2013231"},{"key":"661_CR14","unstructured":"Faithfull W (2017) Change detection for software engineers part I: introduction and CUSUM. https:\/\/faithfull.me\/change-detection-for-software-engineers-part-i-introduction-and-cusum\/"},{"key":"661_CR15","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1016\/j.apor.2014.12.005","volume":"50","author":"MC Fang","year":"2015","unstructured":"Fang MC, Lin YH (2015) The optimization of ship weather-routing algorithm based on the composite influence of multi-dynamic elements (ii): optimized routings. Appl Ocean Res 50:130\u2013140","journal-title":"Appl Ocean Res"},{"key":"661_CR16","volume-title":"Adaptive filtering and change detection","author":"F Gustafsson","year":"2000","unstructured":"Gustafsson F (2000) Adaptive filtering and change detection. Wiley, Hoboken"},{"issue":"1","key":"661_CR17","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1017\/S0373463300000333","volume":"40","author":"H Hagiwara","year":"1987","unstructured":"Hagiwara H, Spaans J (1987) Practical weather routing of sail-assisted motor vessels. J Navig 40(1):96\u2013119","journal-title":"J Navig"},{"issue":"1","key":"661_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1175\/1520-0450(1962)001<0001:MTSR>2.0.CO;2","volume":"1","author":"G Haltiner","year":"1962","unstructured":"Haltiner G, Hamilton H, Arnason G (1962) Minimal-time ship routing. J Appl Meteorol 1(1):1\u20137","journal-title":"J Appl Meteorol"},{"key":"661_CR19","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-5653-8","volume-title":"Design research in information systems: theory and practice","author":"A Hevner","year":"2010","unstructured":"Hevner A, Chatterjee S (2010) Design research in information systems: theory and practice, vol 22. Springer, Berlin"},{"issue":"1","key":"661_CR20","first-page":"6","volume":"28","author":"AR Hevner","year":"2008","unstructured":"Hevner AR, March ST, Park J, Ram S (2008) Design science in information systems research. Manag Inf Syst Q 28(1):6","journal-title":"Manag Inf Syst Q"},{"key":"661_CR21","unstructured":"James RW (ed) (1957) Application of wave forecasts to marine navigation. https:\/\/trid.trb.org\/view\/388400"},{"issue":"3","key":"661_CR22","doi-asserted-by":"publisher","first-page":"576","DOI":"10.1016\/j.cor.2011.05.010","volume":"39","author":"O Kosmas","year":"2012","unstructured":"Kosmas O, Vlachos D (2012) Simulated annealing for optimal ship routing. Comput Oper Res 39(3):576\u2013581","journal-title":"Comput Oper Res"},{"key":"661_CR23","doi-asserted-by":"crossref","unstructured":"Lamm A, Hahn A (2017) Detecting maneuvers in maritime observation data with CUSUM. In: 2017 IEEE international symposium on signal processing and information technology (ISSPIT). IEEE","DOI":"10.1109\/ISSPIT.2017.8388628"},{"issue":"3","key":"661_CR24","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/s00773-011-0128-z","volume":"16","author":"A Maki","year":"2011","unstructured":"Maki A, Akimoto Y, Nagata Y, Kobayashi S, Kobayashi E, Shiotani S, Ohsawa T, Umeda N (2011) A new weather-routing system that accounts for ship stability based on a real-coded genetic algorithm. J Mar Sci Technol 16(3):311","journal-title":"J Mar Sci Technol"},{"issue":"4","key":"661_CR25","doi-asserted-by":"publisher","first-page":"1597","DOI":"10.5194\/gmd-9-1597-2016","volume":"9","author":"G Mannarini","year":"2016","unstructured":"Mannarini G, Pinardi N, Coppini G, Oddo P, Iafrati A (2016) VISIR-I: small vessels-least-time nautical routes using wave forecasts. Geosci Model Dev 9(4):1597\u20131625","journal-title":"Geosci Model Dev"},{"key":"661_CR26","doi-asserted-by":"crossref","unstructured":"Mao S, Tu E, Zhang G, Rachmawati L, Rajabally E, Huang GB (2018) An automatic identification system (AIS) database for maritime trajectory prediction and data mining. In: Proceedings of ELM-2016. Springer, pp 241\u2013257","DOI":"10.1007\/978-3-319-57421-9_20"},{"key":"661_CR27","doi-asserted-by":"crossref","unstructured":"Marie S, Courteille E et al (2009) Multi-objective optimization of motor vessel route. In: Proceedings of the international symposium on TransNav, vol 9. pp 411\u2013418","DOI":"10.1201\/9780203869345.ch72"},{"key":"661_CR28","unstructured":"Mazzarella F, Vespe M, Damalas D, Osio G (2014) Discovering vessel activities at sea using AIS data: mapping of fishing footprints. In: 17th international conference on information fusion (fusion). IEEE, pp 1\u20137"},{"key":"661_CR29","unstructured":"Montes AA (2005) Network shortest path application for optimum track ship routing. PhD thesis, Monterey, California. Naval Postgraduate School"},{"issue":"5","key":"661_CR30","doi-asserted-by":"publisher","first-page":"377","DOI":"10.5394\/KINPR.2015.39.5.377","volume":"39","author":"VS Nguyen","year":"2015","unstructured":"Nguyen VS, Im M, Lee S (2015) The interpolation method for the missing AIS data of ship. J Navig Port Res 39(5):377\u2013384","journal-title":"J Navig Port Res"},{"issue":"1\/2","key":"661_CR31","doi-asserted-by":"publisher","first-page":"100","DOI":"10.2307\/2333009","volume":"41","author":"ES Page","year":"1954","unstructured":"Page ES (1954) Continuous inspection schemes. Biometrika 41(1\/2):100","journal-title":"Biometrika"},{"issue":"6","key":"661_CR32","doi-asserted-by":"publisher","first-page":"2218","DOI":"10.3390\/e15062218","volume":"15","author":"G Pallotta","year":"2013","unstructured":"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\u20132245","journal-title":"Entropy"},{"issue":"1","key":"661_CR33","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/s00773-011-0116-3","volume":"17","author":"J Panigrahi","year":"2012","unstructured":"Panigrahi J, Padhy C, Sen D, Swain J, Larsen O (2012) Optimal ship tracking on a navigation route between two ports: a hydrodynamics approach. J Mar Sci Technol 17(1):59\u201367","journal-title":"J Mar Sci Technol"},{"key":"661_CR34","doi-asserted-by":"crossref","unstructured":"Robinson JT (1981) The KDB-tree: a search structure for large multidimensional dynamic indexes. In: Proceedings of the 1981 ACM SIGMOD international conference on management of data. ACM, pp 10\u201318","DOI":"10.1145\/582318.582321"},{"issue":"2","key":"661_CR35","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1145\/356924.356930","volume":"16","author":"H Samet","year":"1984","unstructured":"Samet H (1984) The quadtree and related hierarchical data structures. ACM Comput Surv (CSUR) 16(2):187\u2013260","journal-title":"ACM Comput Surv (CSUR)"},{"key":"661_CR36","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/j.oceaneng.2015.10.021","volume":"110","author":"L Sang","year":"2015","unstructured":"Sang L, Wall A, Mao Z, Xp Yan, Wang J (2015) A novel method for restoring the trajectory of the inland waterway ship by using AIS data. Ocean Eng 110:183\u2013194","journal-title":"Ocean Eng"},{"key":"661_CR37","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/j.rtbm.2015.10.004","volume":"17","author":"H Sch\u00f8yen","year":"2015","unstructured":"Sch\u00f8yen H, Br\u00e5then S (2015) Measuring and improving operational energy efficiency in short sea container shipping. Res Transp Bus Manag 17:26\u201335","journal-title":"Res Transp Bus Manag"},{"key":"661_CR38","unstructured":"Sen D, Padhy CP (2010) Development of a ship weather-routing algorithm for specific application in north indian ocean region. In: The international conference on marine technology. Dhaka, Bangladesh, BUET, pp 21\u20137"},{"issue":"2","key":"661_CR39","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/s00773-011-0152-z","volume":"17","author":"W Shao","year":"2012","unstructured":"Shao W, Zhou P, Thong SK (2012) Development of a novel forward dynamic programming method for weather routing. J Mar Sci Technol 17(2):239\u2013251","journal-title":"J Mar Sci Technol"},{"key":"661_CR40","doi-asserted-by":"crossref","unstructured":"Sivanandam S, Deepa S (2008) Genetic algorithms. In: Introduction to genetic algorithms. Springer, Heidelberg, pp 15\u201337","DOI":"10.1007\/978-3-540-73190-0_2"},{"key":"661_CR41","doi-asserted-by":"crossref","unstructured":"Sz\u0142apczynska J, Smierzchalski R (2009) Multicriteria optimisation in weather routing. p 423","DOI":"10.1201\/9780203869345.ch74"},{"key":"661_CR42","doi-asserted-by":"crossref","unstructured":"Tan WC, Weng CY, Zhou Y, Chua KH, Chen IM (2018) Historical data is useful for navigation planning: data driven route generation for autonomous ship. In: 2018 IEEE international conference on robotics and automation (ICRA). IEEE, pp 7478\u20137483","DOI":"10.1109\/ICRA.2018.8460880"},{"issue":"3","key":"661_CR43","doi-asserted-by":"publisher","first-page":"28","DOI":"10.2478\/pomr-2013-0032","volume":"20","author":"MC Tsou","year":"2013","unstructured":"Tsou MC, Cheng HC (2013) An ant colony algorithm for efficient ship routing. Polish Marit Res 20(3):28\u201338","journal-title":"Polish Marit Res"},{"issue":"5","key":"661_CR44","doi-asserted-by":"publisher","first-page":"1559","DOI":"10.1109\/TITS.2017.2724551","volume":"19","author":"E Tu","year":"2018","unstructured":"Tu E, Zhang G, Rachmawati L, Rajabally E, Huang GB (2018) Exploiting ais data for intelligent maritime navigation: a comprehensive survey from data to methodology. IEEE Trans Intell Transp Syst 19(5):1559\u20131582","journal-title":"IEEE Trans Intell Transp Syst"},{"key":"661_CR45","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.oceaneng.2016.06.035","volume":"123","author":"R Vettor","year":"2016","unstructured":"Vettor R, Soares CG (2016) Development of a ship weather routing system. Ocean Eng 123:1\u201314","journal-title":"Ocean Eng"},{"issue":"4","key":"661_CR46","doi-asserted-by":"publisher","first-page":"989","DOI":"10.1017\/S0373463318000048","volume":"71","author":"HB Wang","year":"2018","unstructured":"Wang HB, Li XG, Li PF, Veremey EI, Sotnikova MV (2018) Application of real-coded genetic algorithm in ship weather routing. J Navig 71(4):989\u20131010","journal-title":"J Navig"},{"issue":"1","key":"661_CR47","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/s10707-018-0330-9","volume":"23","author":"J Yu","year":"2019","unstructured":"Yu J, Zhang Z, Sarwat M (2019) Spatial data management in apache spark: the geospark perspective and beyond. Geoinformatica 23(1):37\u201378","journal-title":"Geoinformatica"},{"key":"661_CR48","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1016\/j.oceaneng.2018.02.060","volume":"155","author":"SK Zhang","year":"2018","unstructured":"Zhang SK, Shi GY, Liu ZJ, Zhao ZW, Wu ZL (2018) Data-driven based automatic maritime routing from massive AIS trajectories in the face of disparity. Ocean Eng 155:240\u2013250","journal-title":"Ocean Eng"}],"container-title":["Business &amp; Information Systems Engineering"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12599-020-00661-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s12599-020-00661-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12599-020-00661-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,27]],"date-time":"2021-07-27T23:15:22Z","timestamp":1627427722000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s12599-020-00661-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,28]]},"references-count":48,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2020,10]]}},"alternative-id":["661"],"URL":"https:\/\/doi.org\/10.1007\/s12599-020-00661-0","relation":{},"ISSN":["2363-7005","1867-0202"],"issn-type":[{"value":"2363-7005","type":"print"},{"value":"1867-0202","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,7,28]]},"assertion":[{"value":"5 February 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 June 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 July 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}