Hostname: page-component-69cd664f8f-96srj Total loading time: 0 Render date: 2025-03-12T21:04:03.501Z Has data issue: false hasContentIssue false
  • English
  • Français

Maritime accidents-based optimal rescue ship location using dynamic programming and particle swarm optimisation algorithm

Published online by Cambridge University Press:  12 March 2025

Sang-Lok Yoo  and
Kwang-Il Kim
Sang-Lok Yoo
Affiliation:
Future Ocean Information Technology, Jeju 63169, Republic of Korea
Kwang-Il Kim*
Affiliation:
Department of Marine Industry and Maritime Police, Jeju National University, Jeju 64343, Republic of Korea
*
*Corresponding author: Kwang-Il Kim; Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

This study describes an optimal method for deploying rescue ships in response to marine accidents using dynamic programming and particle swarm optimisation in an archipelago. We solved the shortest distance problem from a rescue ship to a marine accident using dynamic programming, which avoids obstacles, such as land or aquacultures. The optimal location problem is NP-hard. However, the optimal locations were found to be efficient among the various candidate combinations using particle swarm optimisation. We compared two models based on the set covering location model (SCLM) and P-median model (PMM). The PMM outperformed the SCLM approach in the test. The findings of this study may be valuable for directing judgments regarding search and rescue (SAR) vessel placements to maximise resource utilisation efficiency and service quality. Furthermore, this process can flexibly arrange multiple rescue ships.

Keywords

search and rescue (SAR)operations researchoptimisationshortest path
Type
Research Article
Information
The Journal of Navigation , First View , pp. 1 - 16
Check for updates
Copyright
Copyright © The Author(s), 2025. Published by Cambridge University Press on behalf of The Royal Institute of Navigation

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Abi-Zeid, I., Morin, M. and Nilo, O. (2019). Decision Support for Planning Maritime Search and Rescue Operations in Canada. Proceedings of the 21st International Conference on Enterprise Information Systems, 328–339.CrossRefGoogle Scholar
Adeh, I. M., Baroughi, F. and Alizadeh, B. (2017). A modified particle swarm optimization algorithm for general inverse ordered p-median location problem on networks. Facta Universitatis, Series: Mathematics and Informatics, 32(4), 447–468.Google Scholar
Akbari, A., Eiselt, H. A. and Pelot, R. (2018a). A maritime search and rescue location analysis considering multiple criteria, with simulated demand. INFOR: Information Systems and Operational Research, 56(1), 92–114. doi:10.1080/03155986.2017.1334322Google Scholar
Akbari, A., Pelot, R. and Eiselt, H. A. (2018b). A modular capacitated multi-objective model for locating maritime search and rescue vessels. Annals of Operations Research, 267(1-2), 3–28. doi:10.1007/s10479-017-2593-1CrossRefGoogle Scholar
Alnahhal, M. and Noche, B. (2015). A genetic algorithm for supermarket location problem. Assembly Automation, 35(1), 122–127. doi:10.1108/AA-02-2014-018CrossRefGoogle Scholar
Astbury, J. (1987). Search area determination and search unit deployment. The Journal of Navigation, 40(1), 63–72. doi:10.1017/S0373463300000308CrossRefGoogle Scholar
Bellman, R. (1966). Dynamic programming. science, 153(3731), 34–37. doi:10.1126/science.153.3731.34CrossRefGoogle ScholarPubMed
Caprara, A., Toth, P. and Fischetti, M. (2000). Algorithms for the set covering problem. Annals of Operations Research, 98(1), 353–371. doi:10.1023/A:1019225027893CrossRefGoogle Scholar
Denardo, E. V. (2012). Dynamic Programming: Models and Applications. Englewood Cliffs, NJ: Prentice-Hall.Google Scholar
Guimin, C., Jianyuan, J. and Qi, H. (2006). Study on the strategy of decreasing inertia weight in particle swarm optimization algorithm. Journal-Xian Jiaotong University, 40(1), 53.Google Scholar
Guoxiang, L. and Maofeng, L. (2010). SARGIS: A GIS-Based Decision-Making Support System for Maritime Search and Rescue. In 2010 International Conference on E-Business and E-Government, 1571–1574. doi:10.1109/ICEE.2010.398CrossRefGoogle Scholar
Hakimi, S. L. (1965). Optimum distribution of switching centers in a communication network and some related graph theoretic problems. Operations Research, 13(3), 462–475. doi:10.1287/opre.13.3.462CrossRefGoogle Scholar
Jung, C. Y. and Yoo, S. L. (2019). Optimal rescue ship locations using image processing and clustering. Symmetry, 11(1), 32. doi:10.3390/sym11010032CrossRefGoogle Scholar
Kennedy, J. and Eberhart, R. (1995). Particle Swarm Optimization. Proceedings of ICNN'95-International Conference on Neural Networks, Vol. 4, 1942–1948.CrossRefGoogle Scholar
KMST (2016). Accident Position Information based on Electronic Chart. Sejong: Korea Maritime Safety Tribunal. Available at: http://data.kmst.go.kr/WebVMS_KMST/WebVMS.jsp [Accessed 12 Jan. 2016].Google Scholar
Kratzke, T. M., Stone, L. D. and Frost, J. R. (2010). Search and Rescue Optimal Planning System. In 2010 13th International Conference on Information Fusion, 1–8. doi:10.1109/ICIF.2010.5712114CrossRefGoogle Scholar
Lin, Q., Song, H., Gui, X., Wang, X. and Su, S. (2018). A shortest path routing algorithm for unmanned aerial systems based on grid position. Journal of Network and Computer Applications, 103, 215–224. doi:10.1016/j.jnca.2017.08.008CrossRefGoogle Scholar
Megiddo, N. and Supowit, K. J. (1984). On the complexity of some common geometric location problems. SIAM Journal on Computing, 13(1), 182–196. doi:10.1137/0213014CrossRefGoogle Scholar
Mladenović, N., Brimberg, J., Hansen, P. and Moreno-Pérez, J. A. (2007). The p-median problem: A survey of metaheuristic approaches. European Journal of Operational Research, 179(3), 927–939. doi:10.1016/j.ejor.2005.05.034CrossRefGoogle Scholar
Ock, Y. S. (2010). Pending issues and policy about abalone culture. Policy Res Fish, 5, 13–36.Google Scholar
Qin, J., Ni, L. L. and Shi, F. (2012). Combined simulated annealing algorithm for the discrete facility location problem. The Scientific World Journal, 2012, 1–7. doi: 10.1100/2012/576392Google ScholarPubMed
Ramachandran, S., Deshpande, O., Roseman, C. C., Rosenberg, N. A., Feldman, M. W. and Cavalli-Sforza, L. L. (2005). Support from the relationship of genetic and geographic distance in human populations for a serial founder effect originating in Africa. Proceedings of the National Academy of Sciences, 102(44), 15942–15947. doi:10.1073/pnas.0507611102CrossRefGoogle Scholar
Richardson, H. R. and Discenza, J. H. (1980). The United States coast guard computer-assisted search planning system (CASP). Naval Research Logistics Quarterly, 27(4), 659–680. doi:10.1002/nav.3800270413CrossRefGoogle Scholar
Roth, R. (1969). Computer solutions to minimum-cover problems. Operations Research, 17(3), 455–465. doi:10.1287/opre.17.3.455CrossRefGoogle Scholar
Shi, Y. and Eberhart, R. C. (1998). Parameter Selection in Particle Swarm Optimization. In Evolutionary Programming VII: 7th International Conference, San Diego, California, USA. doi:10.1007/BFb0040810CrossRefGoogle Scholar
Shi, Y. and Eberhart, R. C. (1999). Empirical Study of Particle Swarm Optimization. Proceedings of the 1999 Congress on Evolutionary Computation-CEC99. doi:10.1109/CEC.1999.785511CrossRefGoogle Scholar
Tian, D. and Shi, Z. (2018). MPSO: Modified particle swarm optimization and its applications. Swarm and Evolutionary Computation, 41, 49–68. doi:10.1016/j.swevo.2018.01.011CrossRefGoogle Scholar
Tipton, M. J. and Golden, F. S. C. (2011). A proposed decision-making guide for the search, rescue and resuscitation of submersion (head under) victims based on expert opinion. Resuscitation, 82(7), 819–824. doi:10.1016/j.resuscitation.2011.02.021CrossRefGoogle ScholarPubMed
Toregas, C., Swain, R., ReVelle, C. and Bergman, L. (1971). The location of emergency service facilities. Operations Research, 19(6), 1363–1373. doi:10.1287/opre.19.6.1363CrossRefGoogle Scholar
Wang, Z. and Guo, G. (2003). Present situation and future development of mobile robot navigation technology. Robot, 25(5), 470–474.Google Scholar
Xiong, W., Van Gelder, P. H. A. J. M. and Yang, K. (2020). A decision support method for design and operationalization of search and rescue in maritime emergency. Ocean Engineering, 207, 107399. doi:10.1016/j.oceaneng.2020.107399CrossRefGoogle Scholar
Yoo, S. L. and Jung, C. Y. (2017). Optimal arrangement of patrol ships based on k-means clustering for quick response of marine accidents. Journal of the Korean Society of Marine Environment & Safety, 23(7), 775–782. doi:10.3390/sym11010032CrossRefGoogle Scholar
Zhang, H., Liu, M., Liu, R. and Hu, T. (2008). Path Planning of Robot in Three-Dimensional Grid Environment Based on Genetic Algorithms. In 2008 7th World Congress on Intelligent Control and Automation. doi:10.1109/WCICA.2008.4593059CrossRefGoogle Scholar
Zhu, W., Jia, D., Wan, H., Yang, T., Hu, C., Qin, K. and Cui, X. (2015). Waypoint graph based fast pathfinding in dynamic environment. International Journal of Distributed Sensor Networks, 11(8), 238727. doi:10.1155/2015/23872CrossRefGoogle Scholar