Exploring Maritime Search and Rescue Resource Allocation via an Enhanced Particle Swarm Optimization Method

Abstract

Maritime search and rescue (SAR) plays a very important role in emergency waterway traffic situations, which is supposed to trigger severe personal casualties and property loss in maritime traffic accidents. The study aims to exploit an optimal allocation strategy with limited SAR resources deployed at navigation-constrained coastal islands. The study formulates the problem of SAR resource allocation in coastal areas into a non-linear optimization model. We explore the optimal solution for the SAR resource allocation problem under constraints of different ship and aircraft base station settings with the help of an enhanced particle swarm optimization (EPSO) model. Experimental results suggest that the proposed EPSO model can reasonably allocate the maritime rescue resources with a large coverage area and low time cost. The particle swarm optimization and genetic algorithm are further implemented for the purpose of model performance comparison. The research findings can help maritime traffic regulation departments to make more reasonable decisions for establishing SAR base stations.

1. Introduction

Rapid economic development promotes cargo carriage among different countries in the manner of varied transportation modes (e.g., air transport, highway and maritime transportation). It is noted that seaborne transportation assumes a large amount of cargo transiting tasks due to the advantages of lower freight, higher capacity, convenience, etc. [1,2]. Traffic density in both coastal and inland channels has experienced a drastic expansion in recent years, whilst ship berthing and departure activities have rapidly increased as well [3,4]. Moreover, merchant ships are designed towards large size and tonnage for the purpose of carrying more goods in a more cost-effective manner and for varied maritime traffic participants. Thus, traffic safety enhancement attracts significant yet increasing attention from both maritime traffic regulators and scholars, considering that a ship collision accident may lead to unaffordable loss [5,6]. In addition, maritime accidents may exert a severely negative influence on the marine ecological environment (e.g., an oil tanker may spill hundreds of tons of oil in an accident event), and huge efforts are needed to remediate the environmental impact. In this context, a timely maritime search and rescue (SAR) operation can largely mitigate negative accident effects in terms of reducing casualties and property loss [7,8].

Currently, SAR operations are primarily performed by volunteers from non-government organizations, professional rescue teams organized by maritime traffic regulation departments and so on. It is observed that the majority of rescue teams and facilities are deployed around coastal areas, and thus a long time is required to distribute sufficient maritime rescue resources when an accident occurs far from coastal lines [9]. Both the SAR regulation departments and researchers are paying more attention to optimizing SAR resource deployment [10]. More specifically, we may save a large amount of wasted search time when partial SAR resources (e.g., rescue team, inshore rescue boat) are reasonably pre-allocated at islands. In this way, the rescue operation can be performed in a more efficient manner when an accident happens, thus significantly reducing potential losses caused by the accident [11]. Many studies have been conducted to identify optimal path planning and facility distribution scenarios to minimize the total overhead (i.e., total traveling distance, time cost) in SAR activities [12,13,14]. It is found that the problem of optimizing SAR resource distribution can be formulated as a discrete location optimization problem. The main reason is that basic SAR resource elements and deployment locations are arranged in a discrete manner [15,16].

Previous studies suggest that the maximum coverage model, p-median model and p-center model can successfully obtain optimal solutions for the discrete location optimization problem [17,18]. The maximum coverage model is a type of classical yet efficient location optimization method, which prioritizes the coverage area when implementing a potential resource allocation task (e.g., SAR, tsunami recue) [19,20]. Each facility used in an accident rescue task is distributed with the rule of ensuring maximum rescue coverage range, whilst facility deployment locations are assigned different weights based on the accident occurrence probability. Zhang et al. transformed the coverage model of an uncertain location set into an equivalent deterministic location model via the help of uncertainty distribution [21]. The p-median relevant models provide an optimal distribution strategy by considering factors of both location and facility allocation [22]. The p-center relevant models are implemented by trying to explore the optimal on-site rescue capacity with limited rescue equipment [23]. Note that the cost function for p-center-based models mainly consists of the maximum response time, maximum coverage distance and minimum overhead loss. Many studies have been conducted to achieve optimal rescue resource distributions by establishing a multi-objective hybrid model with the support of heuristic-relevant models [24,25,26].

Moreover, it is found that maritime emergency logistic optimization issues are attracting increasing attention in the community. Cho et al. proposed a two-phase framework to solve the path planning problem for deploying multiple unmanned aerial vehicles in a maritime accident area [25]. OTOTE et al. proposed a decision-making-oriented model to implement a maritime search and rescue plan with the support of optimal search theory [27]. Thomas et al. proposed a novel metamodel to estimate the mission success possibility for a SAR task with the support of a supervised learning method [28]. Similar studies can be found in [29,30,31]. We find that the particle swarm optimization (PSO) method is commonly used to determine the optimization deployment strategy of maritime rescue facilities. Wu et al. integrated reinforcement learning and a PSO model to achieve real-time maritime rescue assignment with multiple autonomous underwater vehicles [32]. Kumar et al. employed a PSO model to fulfill a search and rescue mission for launching a swarm of unmanned aerial vehicles [33].

It can be noticed that less attention is paid to enhancing SAR efficiency by arranging rescue resources at isolated islands. The main disadvantages of previous maritime rescue resource allocation studies can be summarized into the following two aspects. (1) It is assumed that varied resources used for achieving the SAR task are disposed of at coastal areas for the purpose of easy facility maintenance. There is a growing need to deploy SAR resources around islands far away from coastal lines due to the significant rising maritime trade volume around the world. (2) It is noted that previous SAR-related activities are mainly reliant on ships, while less attention is paid to allocating planes in SAR actions. To address these issues, we propose a novel framework to explore optimal SAR resource allocation scenarios via the help of an enhanced particle swarm method. The primary focus of the study is to explore the optimal rescue base station setup with varied ship and aircraft numbers via the support of empirical maritime traffic accident reports. Our contributions are summarized as the following three aspects: (1) we collect maritime traffic accident data from our cooperators affiliated with the Hainan maritime rescue coordination center, China, which are further used to explore maritime traffic accident hotspot variation patterns; (2) we propose an enhanced particle swarm optimization model to optimize rescue resource distribution considering empirical maritime traffic accident occurrence hotspot areas; (3) we testify to our model’s performance with different yet typical maritime search and rescue resource setups in simulated maritime traffic scenarios. The remainder of the paper is organized as follows. First, a data description is provided in Section 2. Second, Section 3 illustrates the methodology for the study, which consists of SAR problem modeling and optimal solution development with the EPSO model. Third, we provide experimental setups and results in Section 4, and, finally, we briefly conclude the study in Section 5.

2. Data

The empirical maritime traffic accident data were collected from our cooperators, who are affiliated with the Hainan maritime rescue coordination center (MRCC), Hainan, China. Note that many raw accident reports are discarded due to sensitivity and completeness (e.g., some accidents involve military ships). Thus, we finally obtained 88 maritime accident data samples, and the time span ranged from March 2016 to April 2021. Moreover, the accident location data were further processed to avoid potential information leakage due to MRCC requirements. More specifically, we primarily focus on traffic accidents involving merchant ships, as military-related accidents are beyond our research scope. In addition, we found that the traffic accidents were mainly triggered by physical health problems among the ship crew and ship collisions (e.g., SAR action is strongly required). Note that over 15 SAR actions (i.e., 15 traffic accident data samples) were conducted via the help of both air ambulances and rescue ships. In addition, the maritime traffic accident report indicated that over 28 (45) SAR activities were implemented with aircraft (ships).

Following the rule in previous studies [34], we employed the data augmentation logic to generate additional maritime traffic accidents via the help of empirical traffic accident reports. More specially, we generated 800 traffic accident data samples by adding or subtracting a random value to or from the longitude and latitude of the empirical traffic accident data. Moreover, we generated 1200 traffic accidents around the main navigation routes in the study ocean area. In sum, we collected over 2000 traffic accident samples in our study. Each accident sample is labeled as {${\mathrm{lon}}_{\mathrm{r}}$, ${\mathrm{lat}}_{\mathrm{r}}$, ${\mathrm{ship}}_{\mathrm{r}}$, ${\mathrm{plane}}_{\mathrm{r}}$}, $\mathrm{r}$ = (1, 2, …, 2000). Note that symbols ${\mathrm{lon}}_{\mathrm{r}}$ and ${\mathrm{lat}}_{\mathrm{r}}$ represent the longitude and latitude for the rth traffic accident sample. The ${\mathrm{ship}}_{\mathrm{r}}$ and ${\mathrm{plane}}_{\mathrm{r}}$ demonstrate the essential ship and plane number used in the SAR task for the accident. When an SAR action requires ship and aircraft rescue at the same time, we consider the maximum time cost for the ship and aircraft arriving at traffic accident spots as the shortest rescue time in fulfilling the SAR task. We provide the hot spot map for the traffic accident dataset (see Figure 1), and the larger dark-red data samples indicate that more accidents are likely to happen in the highlighted region.

3. Methodology

A quick response can obviously mitigate casualties and environmental pollution in a maritime traffic accident, whist regular and reasonable deployment of SAR facilities can obviously improve SAR activity efficiency. More specifically, it is reasonable and cost-effective to establish a rescue station around the islands and reefs in the offshore area. Meanwhile, the rescue station number is supposed to be optimized to achieve the most cost-effective performance considering cost and rescue time. With the help of historical traffic accident data, we propose to optimize SAR resources by exploiting traffic patterns via an EPSO model. First, we formulated the optimal SAR resource allocation scenario into a nonlinear optimization problem. Second, we determined the optimal solution for the nonlinear optimization formula with the EPSO model.

3.1. SAR Resource Allocation Problem Formulation

SAR resource allocation is indeed a nonlinear optimization problem, which aims to obtain minimum loss (in terms of time cost) with optimal resource allocations. To this aim, we established the objective model based on the minimum rescue time cost. Note that the study focuses on SAR via the help of ships and aircraft, and the SAR base station for ship maintenance is different from that of aircraft. Based on the above-mentioned assumption, we labeled the SAR base station as a collection ${\mathrm{SAR}}_{\mathrm{c}}\left(\mathrm{j}\right)$ = (${\mathrm{lon}}_{\mathrm{j}}$, ${\mathrm{lat}}_{\mathrm{j}}$), $\mathrm{j}$ = (1, 2, M + N). The symbols ${\mathrm{lon}}_{\mathrm{j}}$ and ${\mathrm{lat}}_{\mathrm{j}}$ demonstrate the longitude and latitude for jth SAR base station. The base station number for the ship maintenance is M, while the counterpart for the aircraft base station is N. In other words, the overall base station number for implementing the SAR task is M + N in our study. When a maritime traffic accident occurs, we obtain the ship and aircraft number used for the SAR task separately, though the two types of facilities may be situated at the same location. The objective function for fulfilling the SAR task is to obtain the minimum rescue time to distribute sufficient ships and aircraft to the maritime accident area.

Note that the rescue distance for each ship (and aircraft) was calculated by the spherical distance between the accident site (labeled as longitude and latitude) and the nearest base station. According to the rule of thumb, we set a constant value for the ship (and aircraft) speed during the rescue time calculation procedure. The ship and aircraft were launched from different rescue stations in our study. We employ the symbols m and n to demonstrate the ship and aircraft number used for fulfilling the SAR task for the rth maritime traffic accident. For a given rth maritime traffic accident, the distance ${\mathrm{D}}_{\mathrm{ship}}^{\mathrm{r}}$ (${\mathrm{D}}_{\mathrm{air}}^{\mathrm{r}}$) between the traffic accident spot and ship (aircraft) SAR rescue base station is formulated as Equation (1) (Equation (2)). The overall time cost for fulfilling the SAR task of launching a ship to the spot is obtained with Equation (3), and the time cost for an aircraft is calculated with Equation (4). In this way, the time cost for performing the rth SAR activity with the ship and aircraft number as m and n is obtained with Equation (5). We obtain the minimum time cost for fulfilling the rth rescue task with Equation (6), and the average time overhead ${\mathrm{T}}_{\mathrm{MSR}}$ for 2000 traffic accidents is shown in Equation (7). More specifically, we employ the ${\mathrm{T}}_{\mathrm{MSR}}$ indicator to quantify the model performance in performing the SAR task.

$${\mathrm{D}}_{\mathrm{ship}}^{\mathrm{r}}=\sqrt{{\left({\mathrm{lon}}_{\mathrm{r}}-{\mathrm{lon}}_{\mathrm{s}}\right)}^2+{\left({\mathrm{lat}}_{\mathrm{r}}-{\mathrm{lat}}_{\mathrm{s}}\right)}^2}$$

(1)

$${\mathrm{D}}_{\mathrm{air}}^{\mathrm{r}}=\sqrt{{\left({\mathrm{lon}}_{\mathrm{r}}-{\mathrm{lon}}_{\mathrm{a}}\right)}^2+{\left({\mathrm{lat}}_{\mathrm{r}}-{\mathrm{lat}}_{\mathrm{a}}\right)}^2}$$

(2)

$$\mathrm{T}{\left(\mathrm{ship}\right)}^{\mathrm{r}}=\frac{{\mathrm{D}}_{\mathrm{ship}}^{\mathrm{r}}}{{\mathrm{V}}_{\mathrm{ship}}}, 1\le \mathrm{r}\le 2000$$

(3)

$$\mathrm{T}{\left(\mathrm{air}\right)}^{\mathrm{r}}=\frac{{\mathrm{D}}_{\mathrm{air}}^{\mathrm{r}}}{{\mathrm{V}}_{\mathrm{air}}}, 1\le \mathrm{r}\le 2000$$

(4)

$${\mathrm{T}}_{\mathrm{m}+\mathrm{n}}^{\mathrm{r}}=\mathrm{Max}\{{\displaystyle \sum }_{\mathrm{i}=0}^{\mathrm{m}}\mathrm{T}{\left(\mathrm{ship}\right)}_{\mathrm{i}}^{\mathrm{r}}, {\displaystyle \sum }_{\mathrm{i}=0}^{\mathrm{n}}\mathrm{T}{\left(\mathrm{air}\right)}_{\mathrm{n}}^{\mathrm{r}}\}$$

(5)

$${\mathrm{T}}^{\mathrm{r}}= \mathrm{Min}\left\{{\mathrm{T}}_{\mathrm{m}+\mathrm{n}}^{\mathrm{r}}\right\}, 1\le \mathrm{m}+\mathrm{n}\le \mathrm{M}+\mathrm{N}$$

(6)

$${\mathrm{T}}_{\mathrm{MSR}}=\frac{{{\displaystyle \sum }}_{\mathrm{r}=1}^{2000}{\mathrm{T}}^{\mathrm{r}}}{2000}$$

(7)

where (${\mathrm{lon}}_{\mathrm{r}}$, ${\mathrm{lat}}_{\mathrm{r}}$) denotes the longitude and latitude for the rth accident location. The ship base station’s longitude and latitude are demonstrated as (${\mathrm{lon}}_{\mathrm{s}}$, ${\mathrm{lat}}_{\mathrm{s}}$), whilst the counterpart for the aircraft base station is denoted as (${\mathrm{lon}}_{\mathrm{a}}$, ${\mathrm{lat}}_{\mathrm{a}}$). The symbol $\mathrm{T}{\left(\mathrm{ship}\right)}^{\mathrm{r}}$ demonstrates the time cost for the ship traveling from the base station to the rth accident spot with a constant speed ${\mathrm{V}}_{\mathrm{ship}}$. The rule is applicable to the parameters $\mathrm{T}{\left(\mathrm{air}\right)}^{\mathrm{r}}$ and ${\mathrm{V}}_{\mathrm{air}}$. Moreover, the parameters $\mathrm{T}{\left(\mathrm{ship}\right)}_{\mathrm{i}}^{\mathrm{r}}$ and $\mathrm{T}{\left(\mathrm{air}\right)}_{\mathrm{n}}^{\mathrm{r}}$ are the time costs for the ith $\mathrm{T}{\left(\mathrm{ship}\right)}^{\mathrm{r}}$ and $\mathrm{T}{\left(\mathrm{air}\right)}^{\mathrm{r}}$, respectively. The symbol ${\mathrm{T}}_{\mathrm{m}+\mathrm{n}}^{\mathrm{r}}$ demonstrates the overall time cost of launching m ships and n aircraft to the accident area, while ${\mathrm{T}}^{\mathrm{r}}$ denotes the minimum time cost for the rth SAR task.

3.2. Optimal Solution with EPSO Model

The conventional PSO model obtains an optimal solution by retaining the global and local optimal location information obtained by each particle during the optimal solution exploitation procedure. We note that the PSO model may become trapped in the local optimal solution while identifying optimal setups of SAR base stations. To address the issue, we propose an EPSO model following the logic of randomly initializing the particle location. The EPSO model employs a large number of particles to artificially simulate the movement of bird group behavior in the search space [35]. Note that each individual particle plays an important role in exploring an optimal solution for the particle swarms. An individual particle iteratively finds the optimal solution in the potential search space, and the formulas for conducting the iterative activity are shown in Equations (8) and (9), respectively [36]. Note that the parameter $\mathrm{w}$ is the inertia weight demonstrating the relationship between the current particle speed $\mathrm{V}\left(\mathrm{k}+1\right)$ and previous particle speed $\mathrm{V}\left(\mathrm{k}\right)$. The parameter k is the iteration number, whilst ${\mathrm{c}}_1$ and ${\mathrm{c}}_2$ are the learning factors. Both ${\mathrm{t}}_1$ and ${\mathrm{t}}_2$ are random factors ranging from 0 to 1. The particle’s local optimal position is demonstrated as ${\mathrm{p}}_{\mathrm{loc}}\left(\mathrm{k}\right)$ and the counterpart for the global position is labeled as ${\mathrm{p}}_{\mathrm{glo}}\left(\mathrm{k}\right)$. Moreover, the current position for the particle is shown as $\mathrm{p}\left(\mathrm{k}+1\right)$, and the previous particle position is labeled as $\mathrm{p}\left(\mathrm{k}\right)$. More specifically, the current particle position $\mathrm{p}\left(\mathrm{k}+1\right)$ can be obtained with the help of its previous position $\mathrm{p}\left(\mathrm{k}\right)$ and the particle velocity.

The solution space in the study is to obtain the location of the rescue base station that is situated around coastal islands. In other words, optimal solution determination in our study is indeed an integer non-linear programming problem. It is noted that computational power may not be fully exploited due to convergence issues. More specifically, particles may easily fall into the local optimal location. The EPSO model helps particles to obtain an optimal solution by assigning a random location to the particle when it converges at a location position. In other words, we update the particle state with a random value when the particle speed does not significantly vary for a given iterative number (see Equation (10)). The parameter $\mathrm{V}\left(\mathrm{z}\right)$ demonstrates the particle speed for zth iteration time, while the symbols ${\mathrm{V}}_{\mathrm{t}}$ and ${\mathrm{L}}_{\mathrm{t}}$ are speed and iteration time thresholds. An overview of the framework for the proposed EPSO model is shown in Figure 2.

Table 1. Varied variables and the corresponding explanations.

Variable	Meaning	Variable Attribute
${\mathrm{SAR}}_{\mathrm{c}}\left(\mathrm{j}\right)$	the jth SAR base station location with longitude ${\mathrm{lon}}_{\mathrm{j}}$ and latitude ${\mathrm{lat}}_{\mathrm{j}}$	non-decision/continuous
M	ship base station number	non-decision/discrete
N	aircraft ship base station number	non-decision/discrete
${\mathrm{D}}_{\mathrm{ship}}^{\mathrm{r}}$	distance between the traffic accident location and ship base station	non-decision/continuous
${\mathrm{D}}_{\mathrm{air}}^{\mathrm{r}}$	distance between the traffic accident location and aircraft base station	non-decision/continuous
$\mathrm{T}{\left(\mathrm{ship}\right)}^{\mathrm{r}}$	time cost for sending a rescue ship to accident location	decision/continuous
$\mathrm{T}{\left(\mathrm{air}\right)}^{\mathrm{r}}$	time cost for sending a rescue aircraft to accident location	decision/continuous
${\mathrm{T}}_{\mathrm{m}+\mathrm{n}}^{\mathrm{r}}$	time cost for sending m ships and n aircraft to the traffic accident area	decision/continuous
${\mathrm{T}}^{\mathrm{r}}$	minimum time cost for the rth SAR task	decision/continuous
${\mathrm{T}}_{\mathrm{MSR}}$	average time cost for 2000 traffic accidents	decision/continuous
$\mathrm{w}$	inertia weight	non-decision/continuous
$\mathrm{V}\left(\mathrm{k}\right)$	the kth particle speed	non-decision/continuous
$\mathrm{V}\left(\mathrm{k}+1\right)$	the (k + 1)th particle speed	non-decision/continuous
ci (i = 1, 2)	learning factor	non-decision/continuous
ci (i = 1, 2)	random factor	non-decision/continuous
${\mathrm{p}}_{\mathrm{loc}}\left(\mathrm{k}\right)$	local optimal position	non-decision/continuous
${\mathrm{p}}_{\mathrm{glo}}\left(\mathrm{k}\right)$	global optimal position	non-decision/continuous
$\mathrm{p}\left(\mathrm{k}+1\right)$	current particle position	non-decision/continuous
${\mathrm{V}}_{\mathrm{t}}$	speed threshold	non-decision/continuous
${\mathrm{L}}_{\mathrm{t}}$	iteration threshold	non-decision/discrete

lists the variables used in the EPSO model mentioned in the above section, which can be classified into decision and fixed variables. Note that the majority of variables are indeed continuous parameters. The discrete variables in our study consist of the ship base station number, aircraft ship base station number and iteration threshold. We consider the time-related parameters as decision variables in our study, which include $\mathrm{T}{\left(\mathrm{ship}\right)}^{\mathrm{r}}$, $\mathrm{T}{\left(\mathrm{air}\right)}^{\mathrm{r}}$, ${\mathrm{T}}_{\mathrm{m}+\mathrm{n}}^{\mathrm{r}}$, ${\mathrm{T}}^{\mathrm{r}}$ and ${\mathrm{T}}_{\mathrm{MSR}}$. The objective function for the study aims to find the minimum value for ${\mathrm{T}}^{\mathrm{r}}$ and ${\mathrm{T}}_{\mathrm{MSR}}$, which are indeed the minimum time cost with given SAR resource setups.

$$\mathrm{V}\left(\mathrm{k}+1\right)=\mathrm{wV}\left(\mathrm{k}\right)+{\mathrm{t}}_1{\mathrm{c}}_1\left({\mathrm{p}}_{\mathrm{loc}}\left(\mathrm{k}\right)-\mathrm{p}\left(\mathrm{k}\right)\right)+{\mathrm{t}}_2{\mathrm{c}}_2\left({\mathrm{p}}_{\mathrm{glo}}\left(\mathrm{k}\right)-\mathrm{p}\left(\mathrm{k}\right)\right)$$

(8)

$$\mathrm{p}\left(\mathrm{k}+1\right)=\mathrm{p}\left(\mathrm{k}\right)+\mathrm{V}\left(\mathrm{k}+1\right)$$

(9)

$$\mathrm{V}{\left(\mathrm{k}\right)}_{\mathrm{z}}\le {\mathrm{V}}_{\mathrm{t}}, \mathrm{z}=\left({\mathrm{L}}_{\mathrm{t}1},{ \mathrm{L}}_{\mathrm{t}1}+1, \dots {\mathrm{L}}_{\mathrm{t}2}\right)$$

(10)

4. Experiment

To verify the proposed model’s performance, we employ the EPSO model to perform the SAR resource allocation task in the manner of considering only the ship carrier and the combination of both ships and aircraft. Moreover, the conventional particle swarm optimization (PSO) model [37] and genetic algorithm (GA) [38] are implemented for the purpose of model performance comparison. The three models are implemented with an NVIDIA Geforce RTX 2080, Intel (R) Xeon (R) gold 6230 CPU @ 2.10 GHz, while the memory size is 64 GB. Note that we obtain costs for each scenario by focusing on the factors of base station number and accident location, whilst the speed for the ship and aircraft are set as constant values (43 and 220 km/h) in the study. We obtained typical parameter settings.

In addition, we conducted a group of experiments to determine the optimal parameter settings for the different models. The typical parameters for the GA model are illustrated as follows. The population size was set to 200, the maximum epoch number was 6000, whilst the mutation and crossover probability were set to 0.15 and 0.05, respectively. In addition, the epoch number for the PSO model was set to 6000 as well, and the particle number in our study was set to 80. The inertia weight, individual learning rate and group learning rate were set to 0.9, 0.8 and 0.3.

4.1. SAR Task Performance with Ship

We implemented the simulation with the help of accident data samples, main sea routes and an SAR rescue base station. Figure 3 demonstrates the distributions under different numbers of SAR rescue base stations (e.g., 5, 10, 15, 20, 25, 30). Figure 3a illustrates the distributions of five ship base stations for an SAR task, whilst the x-axis and y-axis denote the latitude and longitude of each of the base stations. Note that both the latitude and longitude data were deidentified in our study for the purpose of avoiding the unauthorized disclosure of sensitive data. The accident locations (see the red color in Figure 3a) are distributed along the main sea routes, and the collection of ship base stations is marked in green. The white plus symbols indicate the selected ship base stations obtained by the EPSO model. It was found that the selected ship base stations (see the white plus marks in Figure 3a) covered as much of the sea region as possible. As a result, we considered that the EPSO model achieved a trade-off between limited SAR resources and large SAR sea area.

It can be inferred that the area with latitude ranging from 4° to 8° may require more ships when implementing the SAR task, according to Figure 3a. More specifically, the SAR operation may fail to obtain satisfactory performance if the traffic accident is serious. Figure 3b demonstrates the distributions of 10 rescue base stations output by the EPSO model. We found that the base station located at the high-risk sea area in Figure 3b (i.e., latitude ranging from 4° to 8°) was three-fold larger compared to that in Figure 3a. In other words, the proposed EPSO model successfully identified the dangerous sea area, while more resources were allocated to the area with additional redundant SAR resources. The ship allocation strategy for 15 (see Figure 3c), 20 (see Figure 3d), 25 (see Figure 3e) and 30 (see the Figure 3f) ship base stations confirmed the above-mentioned analysis. In sum, we consider that the proposed EPSO model can reasonably yet efficiently allocate SAR resources when a maritime traffic accident occurs.

We calculated the average rescue time costs for different models under different base stations. It can be found that more rescue base stations can significantly reduce the average time cost, as shown by the curve’s variation tendency for the EPSO, PSO and GA models shown in Figure 4. Moreover, the EPSO average rescue time experienced a significant decreasing tendency, which could be obviously seen when the ship base stations were set to 5, 10, 15 and 20 (see the blue curve in Figure 4). For instance, the average rescue time for the EPSO model with five ship base stations was approximately 20% lower than the counterpart with 10 base stations. The average time cost for the EPSO model with 25 base stations was close to that of the counterpart with 30 base stations, which suggested that there was a minimum value for the average rescue time when implementing the SAR task. The PSO and GA rescue times showed similar variation tendencies to that of the EPSO model. In other words, the average rescue time decreased when the base station number increased from 5 to 30. In addition, the average time cost for the GA model was larger than the counterparts of the EPSO and PSO models, whilst the base station number was same for the different models.

Table 2. Rescue time distributions for different models under varied ship base station number.

Base Station Number	EPSO (h)	PSO (h)	GA (h)
5	5.430	5.430	5.501
10	4.057	4.092	4.389
15	3.570	3.593	3.906
20	3.312	3.327	3.735
25	3.159	3.178	3.704
30	3.068	3.116	3.649

provides the average time costs for different models, which confirm the above-mentioned analysis. More specifically, the average rescue time for the EPSO model was smaller than those of the PSO and GA models under the same base station number. The rescue time for the PSO model was the same as that of the EPSO when the base station number was set to 5. The rescue time for the PSO model was longer than that of the EPSO with an increase in the base station number, which indicated that our proposed model obtained better performance. It can be inferred from Table 2 that the EPSO rescue time was slightly smaller than that of the PSO. Compared to the PSO model, the EPSO model can arrange SAR resources in a more efficient manner. In addition, the GA model required a longer rescue time in comparison with both the EPSO and PSO models. For example, the GA rescue time with the constraint of 10 ship base stations was 4.389 h, which was approximately 10% larger than those of the EPSO and PSO models (i.e., 4.057 h and 4.092 h, respectively). The rescue time with additional ship base stations (15, 20, 25 and 30) showed a similar variation tendency for the GA model.

4.2. SAR Task Performance with Both Ship and Aircraft

We further verified the model’s performance by dispatching both rescue ships and aircraft in an SAR task. After interviewing several professional SAR practitioners, it was found that the aircraft number was usually smaller than 10 for the purpose of fulfilling an SAR task. Following the rule, we conducted the experiment while the aircraft number was set to 5 and 10 in the study. Figure 5 demonstrates the rescue time distributions for the EPSO, PSO and GA models with different aircraft and ship base station numbers. Note that the x-axis in Figure 5a demonstrates the total number of ship and aircraft base stations while the aircraft station number was 5 (and the ship base station number ranged from to 5 to 30 with intervals of 5). The rule is applicable to the x-axis in Figure 5b, while the aircraft base station number was set to 10. Figure 5a suggests that the GA model required a longer rescue time compared with the PSO model with the same rescue resource limitations.

Moreover, the EPSO rescue time was shorter than those of both the GA and PSO models as well. Figure 5a suggests that the GA model’s performance deteriorated when the base station number was larger than 30, which indicates that the GA model may fail to reasonably allocate rescue aircraft and ships in an SAR activity. On the contrary, both the PSO and EPSO models showed a decreasing tendency when more rescue resources were available. It was found that a larger aircraft number can reduce the time cost for an SAR task considering that the average rescue time distributions in Figure 5b show a decreasing tendency. However, the variation tendency for the rescue time cost can be more clearly observed in Figure 5b. More specifically, the GA model rescue time was significantly larger than the counterparts of the PSO and EPSO models (see green curve in Figure 5b). Moreover, the EPSO model obtained slightly better performance compared to the PSO model (see both the red and blue curves in Figure 5b). In sum, the above-mentioned qualitative analysis suggests that the EPSO model can allocate the maritime rescue resources in a more reasonable manner compared to the PSO and GA models.

Table 3. Rescue time distributions with different ship and aircraft base station number.

Ship Base Station Number	Aircraft Base Station Number	EPSO (h)	PSO (h)	GA (h)
5	5	5.163	5.163	5.242
5	10	5.107	5.111	5.229
10	5	4.398	4.416	4.754
10	10	4.349	4.380	4.536
15	5	4.191	4.225	4.535
15	10	4.142	4.248	4.506
20	5	4.058	4.085	4.431
20	10	4.029	4.027	4.506
25	5	4.005	4.078	4.371
25	10	3.936	3.979	4.501
30	5	3.954	3.994	4.565
30	10	3.921	3.938	4.551

provides the rescue time distributions with different ship and aircraft base station distributions for the three models. We found that the time cost was slightly lower under the constraint that the aircraft base station number was two-fold larger and the ship base station number was the same (as shown in the first three rows in Table 3). Moreover, an increase in the ship base station number can significantly reduce the rescue time compared to that of aircraft. For instance, the EPSO rescue time with s constraint of five ships and five aircraft base stations was 5.163 h, while the counterpart with a constraint of 10 ships and 5 aircraft base stations was 4.398 h. The time costs with the same resource limitations for the PSO (GA) model were 5.163 h (5.242 h) and 4.416 h (4.754 h), which showed a similar variation tendency to those of the EPSO model. The above-mentioned analysis can be further confirmed by additional ship and aircraft allocation strategies. In this manner, we considered that we may need to allocate more ship resources instead of aircraft to efficiently conduct an SAR activity in the real world. It was suggested that 20 ships and 5 aircraft base stations can yield satisfactory performance (i.e., covering a potential yet large accident area in a more cost-effective manner).

We have simulated a ship and aircraft allocation strategy for an SAR task, and more details can be found in Figure 6. More specifically, the red multiplication marks in Figure 6 demonstrate the simulated maritime locations, and candidate ship (aircraft) base stations are denoted by green (blue) circles. We set the number of selected ship and aircraft base stations to 20 and 5, respectively. The yellow pentagram and white plus marks represent the selected aircraft and base stations in the figure. We found that the candidate ship and aircraft stations covered high-risk waterways, and the density for the two types of SAR stations was obviously larger in the higher-risk areas (i.e., larger density distributions indicated by red multiplication marks).

It was noted that the selected ship base stations were deployed around arterial navigation routes (see the white plus sign with latitude ranging from 4° to 9°). We can infer that the ship base stations can successfully dispatch ships into potential yet risky accident waterway areas, and thus mitigate the losses caused by potential maritime traffic accidents. Moreover, three aircraft base stations were allocated around the arterial waterway routes (i.e., 60% base stations were deployed at dangerous navigation routes). We observed that two ship base stations and aircraft stations were deployed around boundary areas, which can be found in the top-right and bottom-left plus and pentagram marks in Figure 6. Such a base station deployment strategy guaranteed efficient and timely SAR activity implementation when a maritime traffic accident occurred in a sea area far away from the coastal region. Consequently, we can conclude that the proposed EPSO model can efficiently allocate SAR resources by reasonably deploying ship and aircraft rescue base stations.

5. Conclusions

Appropriate yet reasonable arrangement of SAR resources plays a crucial role in reducing losses caused by a maritime traffic accident, especially for constrained navigation areas (e.g., islands). In this context, much attention has been paid to finding an optimal solution for the purpose of establishing sufficient yet reasonable base stations considering the factors of coverage and cost. To this aim, we proposed a novel EPSO model to determine an optimal SAR base station deployment strategy with given rescue resources. The proposed EPSO model identified optimal base station locations considering the minimum time cost for implementing an SAR task.

We have conducted a simulated SAR task with two typical setups for the purpose of model performance verification. From the perspective of fulfilling the SAR task implemented only with ships, the proposed EPSO model always required a lower time cost to implement the SAR task with the constraint of the same base station number. For instance, the rescue time cost for the EPSO model with 10 ship base stations was 4.057 h, while the counterparts for the PSO and GA models were 4.092 h and 4.389 h, respectively. Overall, the aggregated time costs for the EPSO, PSO and GA models were 3.766 h, 3.789 h and 4.147 h. From the perspective of fulfilling the SAR task implemented with both ships and aircraft, the proposed EPSO model outperformed the other two models (i.e., PSO and GA) considering that the aggregated time costs for the three models were 4.271 h, 4.304 h and 4.644 h. The experimental results confirmed that the proposed EPSO model required less time to fulfill the SAR task compared to the conventional PSO and GA models.

In the future, we can further expand our studies in the following directions. First, we did not consider adverse weather influences when we implemented the SAR task. We could quantify the negative impact caused by adverse weather in our future work. Second, more resource allocation strategies considering additional and varied rescue resources (e.g., additional traffic carriers) deserve further attention. Lastly, we could evaluate additional heuristic models (such as the ant colony model, pigeon-inspired optimization model) with varied parameter settings to tackle the SAR resource allocation optimization problem.