A Multi-Objective INLP Model of Sustainable Resource Allocation for Long-Range Maritime Search and Rescue

Abstract

Maritime search and rescue (SAR) operations play a crucial role in reducing fatalities and mitigating human suffering. Compared to short-range maritime SAR, long-range maritime SAR (LRMSAR) is more challenging due to the far distance from the shore, changeful weather, and less available resources. Such an operation put high requirements on decision makers to timely assign multiple resources, such as aircraft and vessels to deal with the emergency. However, most current researches pay attention to assign only one kind of resource, while practically, multiple resources are necessary for LRMSAR. Thus, a method is proposed to provide support for decision makers to allocate multiple resources in dealing with LRMSAR problem; to ensure the sustainable use of resources. First, by analyzing the factors involved in the whole process, we formulated the problem as a multi-objective optimization problem, the objective of which was to maximize both the probability of completing the tasks and the utilities of allocated resources. Based on the theory of search, an integer nonlinear programming (INLP) model was built for different tasks. Second, in order to solve the non-deterministic polynomial-time hardness (NP-hard) model, by constructing a rule base, candidate solutions can be found to improve the calculation efficiency. Furthermore, in order to obtain the optimal scheme, the Non-dominated Sorting Genetic Algorithm II (NSGA-II) was applied to the candidate solution sets to approximate Pareto fronts. Finally, an emergency case of Chinese Bohai Sea was used to demonstrate the effectiveness of the proposed model. In the study, 11 resource allocation schemes were obtained to respond to the emergency, and calculation processes of schemes were further analyzed to demonstrate our model’s rationality. Results showed that the proposed models provide decision-makers with scientific decision support on different emergency tasks.

1. Introduction

The fast development of the technologies in aircraft and vessels brings great convenience to human-beings; at the same time, it also brings some serious disasters. For instance, in 2014, Malaysian Airlines flight MH370 carrying 227 passengers and 12 crews were lost, causing serious loss of both human lives and economic benefits. In response to this disaster, large-scale maritime search and rescue (SAR) operations were carried out by multinational organizations [1]. It is not surprising that SAR is critically important in such an emergency [2], which draws much more attention from people in various fields. According to the distance from the shoreline, SAR operations can be divided into short-range maritime SAR and long-range maritime SAR [3]. With the development of SAR in the world, short-range maritime SAR is obviously improved [3]. However, long-range maritime SAR (LRMSAR) still remains the most challenging task among SAR operations.

The challenges of LRMSAR can be summarized as follows: first, there is a contradiction between the urgency of the operation and the far distance from the operational area of LRMSAR to the shore. Because of the far distance, there are few fishing boats and merchant vessels available in the neighborhood of the area. Furthermore, professional SAR vessels are unable to reach the operational area quickly. Second, comparative speaking, the sea environment can be worse and more unpredictable with an increase of distance from the shore [3]. The ever-changing oceanic climate of LRMSAR can make survival difficult for people in distress.

To overcome these challenges, at present, most countries adopt the joint aeronautical and maritime search and rescue in response to LRMSAR operation. The efficiency and effectiveness of coordinated air-maritime search and rescue are far more than a single selection of vessel or aircraft. However, such a complex joint operation can bring many problems to decision makers. For example, in order to respond as fast as possible, among all resources, the decision maker needs to select which aircraft and vessel to participate in the operation. Resource allocation of LRMSAR determines the effectiveness and efficiency of operation directly. Hence, reasonable resource allocation with sustainability can ensure the effective operation and rational use of resources, leading to limited casualties.

In regard to LRMSAR resource allocation decision, many challenges prevent decision makers from making scientific decisions, namely: 1) the space of resource allocation is complicated and large; 2) there are many types and quantities of resources; and 3) the location, capacity, speed, track spacing and scanning width of LRMSAR resources are different. In order to effectively respond to the rescue, decision makers need to analyze a large amount of data to select resources correctly in a short time. Therefore, an executable resources scheme is necessary to obtain accurate resources quantities; however, few quantitative models of SAR have been provided until now. While quick response is important for LRMSAR, decision makers will spend a lot of time on making decisions by themselves without any decision support. In general, the current resource allocation of LRMASR is wasteful and inefficient, which causes unsustainable use of resources. Therefore, it is challenging to choose a sustainable resource allocation scheme.

Despite that the resource allocation decision-making of LRMSAR is significant and challenging, most of the resource allocation still relies on the expert experience of decision makers. Due to the lack of time available for human decision-makers, it is not reliable to manually determine the resource allocation scheme. Motivated by the above analysis, in this paper, we propose a sustainable resource allocation method, specifically, a multi-objective INLP (integer nonlinear programming) model for LRMSAR emergency response. Our method can be divided into the following steps: firstly, in order to consider comprehensive realistic factors, we formulated the problem as a multi-objective optimization problem, the goal of which was to maximize both the probability of completing the tasks and the utilities of allocated resources. Based on the theory of search, an integer nonlinear programming (INLP) model was built to allocate multiple resources. Secondly, in order to solve the NP-hard model, by constructing a rule base, candidate solutions can be found to improve the calculation efficiency. Furthermore, in order to obtain the optimal scheme, the Non-dominated Sorting Genetic Algorithm II (NSGA-II) algorithm was applied to approximate Pareto fronts to get the candidate solution sets. The proposed models could be applied to resource allocation of LRMSAR to provide decision-makers with scientific decision support on different emergency tasks, which can greatly improve LRMSAR’s effectiveness and utilize resources rationally, ultimately reducing casualties.

We conclude our contributions as follows: first, most current researches pay attention to assign only one kind of resource, while practically multiple resources are necessary for LRMSAR; in order to provide decision support to LRMSAR, a multi-objective INLP model is proposed to find the most efficient and effective assignment of available resources for different task, aiming to ensure the abilities for fulfilling different emergency tasks with reasonable and sustainable allocated resources. Moreover, current studies have mostly focused on the optimization of search process, and have not quantitatively modeled the complete search and rescue operation. In this paper, we quantitatively modeled the multi-stage process of LRMSAR, and based on the theory of search, we proposed a mathematical model for the possibility of LRMSAR (POR) to measure the effectiveness of the operation. We defined POR as the product of the probability of search (POS) and the probability of live (POL) of people. In the search operation, according to the principle of division of responsibility area, a POS calculation model of the multi-aircraft collaborative was established. In the rescue operation, the relationship between the longest survival time of people and the whole operation time cost was modeled to measure the impact of POL. Furthermore, a rule-based NSGA-II algorithm was applied in the model solving. We constructed a resource utilization rule base to get a preliminary feasible resource set at first. Then, this feasible resource set was used as the input of NSGA-II algorithm to find the optimal resources allocation scheme. This method can be applied on a better initial population basis to find globally optimal solutions faster.

The remainder of this paper is organized as follows: Section 2 introduces the related works of the resource allocation problem on LRMSAR. In Section 3, the process of long-range maritime search and rescue is introduced, and we describe the basic problem of resource allocation. Section 4 presents the model of multi-objective integer nonlinear programming of LRMSAR resource allocation. The model construction and solving methods are introduced separately in this part. Section 5 demonstrates how we can use our model to solve a real incident at Chinese Bohai Sea. Finally, Section 6 presents a final summary of this study.

2. Related Works

By reviewing the related works for appropriate methodology, we found that similar resource allocation problems have been discussed quite rarely. Most existing works have talked about the experience of maritime SAR organization management, capability evaluation, vessel allocation, aircraft allocation, etc. In general, there were few papers that use mathematical modeling methods to solve the problems related to LRMSAR. In the following, we discuss the related works from the perspective of organization management, capability evaluation, SAR vessel, and aircraft allocation, respectively.

Organization Management: the International Aeronautical and Maritime Search and Rescue Manual (IAMSAR), which is merged between the International Aeronautical Organization (ICAO) and the International Maritime Organization (IMO) in 1998, focused on the organization and management of SAR and provided technical support for SAR operations. Yan et al. [4] tried to overcome limited time pressure, while retaining minimum rescue project duration. They proposed a heuristic resource-constrained project scheduling approach to get a rescue scheme for the maritime disaster rescue. Degre et al. [5] proposed a risk assessment model, which considered not only static parameters such as the vessel’s age, cargo, flag, etc., but also dynamic parameters, such as the visibility and traffic conditions that can be faced when navigating, to solve the maritime traffic problem. Urk et al. [6] described how the policy for sea shipping safety (POLSSS) (a study was commissioned to RAND Europe and Maritime Simulation Centre the Netherlands (MSCN)) was embedded in the Dutch vessel traffic management policy for the sea shipping areas.

Capability Evaluation: Jacobsen et al. [7] examined the feasibility of providing long-range search and rescue for personnel in the Barents Sea, and illustrated the possibility of improved search and rescue capacity. Brachner et al. [8] proposed a simulation model that supported the planning of an offshore emergency response system. The model was trace-driven by means of environmental data. It included a number of stochastic parameters and output a heat-map to visualize the response capacity [9].

SAR vessel allocation: modern decision-making and mathematical evaluation theory have been applied to study the optimal selection method of choosing salvage vessel when there are many salvage vessels available [10,11], in which Zhu et al. [10] used predefined principles to guide the selection of vessel in SAR, while Zhou [11] used multiple properties to compare the advantages and disadvantages among the alternative vessel, and help decision makers to choose proper vessel in SAR.

SAR aircraft allocation: Karatas et al. [12] proposed a hybrid method based on the linear Integer Programming model (ILP) and applied simulation optimization to solve the helicopter allocation problem in the process of SAR. For persistent SAR operations with a system of UAVs (Unmanned Aerial Vehicles), Lee et al. [13] developed a mixed integer linear program (MILP) capable of generating efficient search and rescue operation plans. A rolling horizon scheduling approach was used for real-time operations that account for unanticipated changes to the system parameters.

In conclusion, there have been few works focusing on resource allocation for aircraft and vessels in maritime SAR, and even less on LRMSAR. Little research has used optimization method and a mathematical model to allocate resources. Moreover, most of them only pay attention to the search stage, instead of the entire search and rescue process, and ignore the impact of people’s living conditions in the search and rescue operation. As discussed in Introduction Section, LRMSAR resource allocation in this paper is actually a multi-objective decision making problem. However, traditional methods cannot process large amounts of data to obtain the optimal solutions, because the time cost of ordinary method is huge and cannot solve the multi-objective conflict. Thus, an optimization method was applied in this paper. At present, multi-objective optimization methods have been successfully applied in different fields, such as engineering application, economic front, management decision, etc. With this optimization method to solve LRMSAR resource allocation, an optimal solution can be obtained rapidly and accurately, which ensures the rational utilization of resources, so as to improve the efficiency of SAR operation.

3. Problem Description

In order to allocate resource sustainably, the objective of LRMSAR resource allocation should maximize both the probability of completing the tasks and the utilities of allocated resources. Therefore, we formulated this problem as a multi-objective optimization problem.

As shown in Figure 1, it was assumed that there are available professional and government SAR vessels and aircraft around the sea area. In addition, there may be several available merchant/fishing vessels nearby the sea area. The differences of emergencies lie in emergency attributes, sea environment, and the available resources. Moreover, the location, capacity, velocity, track spacing and scanning width, etc. of LRMSAR resources are different. Considering cooperation of aircraft and vessels, we wanted to study how to select available resources to carry out SAR task, and get an efficient and sustainable resource allocation scheme. Aimed at analyzing the related concepts and basic operation processes, this section describes the problem of LRMSAR in this paper and lays the realistic foundation for model construction in the next chapter.

3.1. Elements Involved in Long-Range Maritime SAR

During the long-range maritime SAR operation process, three kinds of elements are involved, which are available resources to be scheduled, people waiting to be rescued, and the resource utilization rules that can be relied on. In the following, we will illustrate the detailed information of these elements.

(1) SAR Resource

As the basis of the emergency response, the available resources are the executor of the SAR task. Considering the great challenges long-range maritime SAR face, the use of only one vessel or aircraft can hardly satisfy the requirements in this situation. With the development of unmanned aerial vehicle (UAV) and fixed-wing aircraft recently, aircrafts gradually becomes prominent in the search operation, which can greatly improve the search efficiency [13]. Moreover, an aircraft can search for a larger area, drop life-saving equipment to people and play an important role in guiding the SAR vessels. Therefore, when considering available resources, in this work, we focused on the collaborative operation of both aircraft and vessels. Similarly, the decision variables of INLP model include aircraft and ships in Section 4.2.1.

(2) People in Distress at Sea

People in distress at sea are the rescue targets of LRMSAR operations. In this paper, we used the word “people” as an abbreviation for “people in distress”. For people, the harsh environment at sea poses a great threat to their lives [4]. First of all, the search operation is the cornerstone of the entire operation. If they cannot be found, all of the remaining operation is in vain. SAR is carried out in an extremely harsh environment at sea, which undoubtedly increases the difficulty to locate people. At the same time, the survival status of people should also be considered during the operation. People could lose their lives due to long-term harsh environments (e.g., low temperatures, danger to drowning). Therefore, it is important to ensure the people survive after being found, which puts forward great demands for the LRMSAR resource allocation.

(3) Resource Utilization Rule

Through the efforts of decades and the experience of SAR operations, a great deal of knowledge has been accumulated as rules at present, and operations mostly rely on the guidance of these rules [14]. By organizing, expressing, and storing the knowledge of experts and historical experience of SAR, a resource utilization rule base can be constructed. After preliminarily screening all the resources, effective strategies and decision support are provided for the decision makers of LRMSAR under a reasonable matching mechanism. The utilization of knowledge base can make the operation quickly and accurately. However, although the rule matching method can get a feasible solution candidate, it is not refined enough to accurately provide a practical solution.

3.2. Long-Range Maritime SAR Operation Process

For LRMSAR operations, some factors need to be taken into consideration. First, the speed of the aircraft is much faster than a vessel, which can quickly reach the operational area and locate people in a short time. Second, although UAV and fixed-wing aircraft have excellent search capability, their own structure is not suitable for them to salvage after finding the people. Despite that helicopters have a certain abilities to salvage and rescue, compared to the capability of search and airdrop, its salvage capacity remains limited. Therefore, we only considered that LRMSAR operations are implemented by aircraft in the search operation, and vessels in the rescue operation. Similarly, we constructed multi-objective INIP model according to the facts that aircrafts perform search task and ships perform salvage task in Section 4. As shown in Figure 2, the simplified LRMSAR operation process in this paper generally includes the following three stages [14]: alarm receiving, search operation, and rescue operation.

In the early alarm receiving stage, the Maritime Search and Rescue Center (MSARC) receives the alarm signal, and immediately collects and confirms the information of maritime emergency, including the information of sea environment (wave height, visibility, wind level, flow direction, etc.), incident information (emergency cause, scale, location, etc.). We assumed that the stage 1 can provide the input parameters we need in Section 4.2.1.

In the search operation stage, due to the operational area are far away from shore, all kinds of aircrafts need to cover the search area quickly to find people in distress and airdrop supplies and lifesaving items to them. Based on this, a mathematical model about the effectiveness of aircraft performing search operation was constructed, which is the calculation of POS in Formulas (4) and (5) of Section 4.2.2. In addition, considering the aircraft can airdrop the supplies to people, a mathematical model about the uncertain survival time of people is given in Formulas (7) and (8) of Section 4.2.2.

While in the rescue operation stage, when the vessels receive the position signal from the search operation, the vessels will go to salvage people in distress. Afterward, the medical staff on the vessel will rescue the people and send them to the nearest hospital for further treatment. Based on this, a mathematical model about the effectiveness of vessel performing rescue operation was constructed, which is the calculation of POL in Formulas (6)–(10) of Section 4.2.2.

4. Resource Allocation Considering Cooperation of Aircraft and Vessels for LRMSAR

In order to provide support for decision makers, we needed to obtain the optimal resources allocation scheme that not only ensures the possibility of operations, but also makes full use of resources without unnecessary waste. Aiming at this target, we constructed a multi-objective integer nonlinear programming (INLP) model for allocating the resources. The quantitative description of the problem is shown in Figure 3. First, some information related to marine environment and incident was used as the input of our model. Then, constraints were used to judge whether the scheme was feasible based on our model. If possible, double objectives were utilized to measure the effectiveness of the scheme. Finally, a rule-based intelligent optimization algorithm was designed to solve the model and optimize the calculating process. The approximate Pareto fronts were obtained to get optimal resources allocation scheme candidates.

4.1. Basic Theory of Search Concepts

In our work, we used the theory of search to quantitatively describe the search operation process. The theory of search is a branch of Operations Research, which studies how to use limited search resources effectively and find people with an uncertain location in an optimal way [15]. Its relevant concepts and index of the theory of search were used in our resource allocation model. The following is a brief introduction.

(1).

Probability of Containing (POC). This refers to the probability that the search area contains the people. If the POC is up to 1, it means that the search area contains all people. POC is related to the accuracy of the search area.

(2).

Probability of Detection (POD). This refers to the probability that search resources can find the target when the search target is 100% located in a certain sea area. POD is used to evaluate the effectiveness of the search unit in the search area, which is usually expressed as a percentage and can measure the likelihood of success in finding a target. POD can be obtained from experiments and expert experience.

(3).

Probability of Search (POS). Professor Koopman put forward the concept of POS in “The Theory of Search” [15], which means the possibility of finding the people eventually. POS is mainly affected by two factors: 1) searchers must detect certain areas that contain targets (POC) and 2) searchers must have the ability to detect and find search targets in the search area (POD). Therefore, the formula of POS is:

$$POS=POC\times POD$$

(1)

(4).

Survival time. The harsh environment at sea will reduce the survival time of people in distress. The survival time of people refers to the longest time that the body can survive in the seawater under normal conditions. According to previous studies, this mainly depends on the ability of individuals to resist the cold and the surface temperature of seawater, provided that no drowning occurs and no marine animals are injured in the process of drifting. The count shows that the longest survival time of normal human body is 12 min when immersed in seawater at 0 °C, 2 h and 40 min when the water temperature is 10 °C, and 16 h and 20 min when the water temperature is 20 °C [16]. If people are found too late, they will lose their lives, which should be avoided. Thus, LRMSAR requires higher efficiency to maintain people’ vital signs.

4.2. Multi-Objective INLP Model Construction

In this part, a multi-objective INLP model is constructed, and the calculation process is as shown in Figure 4. First, a detailed description of input parameters information is given in Section 4.2.1. Moreover, the calculation process of objective 1 is explained, which is the maximum probability of completing the tasks. As mentioned in Introduction, we defined POR as the product of the probability of search (POS) and the probability of live (POL) of people. Respectively, the calculation process (Step a, b, c) of POS is represented in the Formulas (4) and (5) of Section 4.2.2. The calculation process of POL (step d, e, f) is represented in Formulas (6)–(9) Section 4.2.2. Furthermore, the calculation process of Objective 2 (step g) is explained, which is maximum the average utility of resources. A detailed description is given in Formula (10) of Section 4.2.2. Finally, the constraints (step h, i, j) of this model are represented in Formulas (11)–(13) of Section 4.2.3.

4.2.1. Input Parameters

Table 1. Input parameters and the detailed descriptions.

Parameter	Description
$B$	Current sea state level ($1\le B\le 9,B\in N$)
$N$	Number of people
$S$	Search area
$M$	Number of all resources types
$I$	Number of aircraft types
$J$	Number of vessels types
$n_i^a,n_j^v$	Quantity of each aircraft/vessels type ($i\le I,j\le J,i,j\in N$)
$d_i^a,d_j^v$	The initial distance of aircraft/vessel from the operational area ($i\le I,j\le J,i,j\in N$)
$v_i^a,v_j^v$	The velocity of each aircraft/vessels types ($i\le I,j\le J,i,j\in N$)
$b_i^a,b_j^v$	The maximum sea states allowed by the aircraft/vessel to go to sea ($i\le I,j\le J,i,j\in N$)
$Ca{p}_i\left(B\right)$	Search ability (the area of an aircraft searching at unit time) of the $i$th aircraft under sea states B ($i\le I,i\in N$)
$P_i$	Probability of detection (POD) of the $i$th aircraft ($i\le I,i\in N$)
$Sa{l}_j$	The unit time of the $j$th vessel salvage for each people ($j\le J,j\in N$)
${\mathrm{c}}_j$	The maximum capacity to carry people of the $j$th vessel ($j\le J,j\in N$)
$T^l\left(B\right)$	The longest survival time of people under certain sea states level B

lists the input parameters of model and their detailed explanations. Most of them can be obtained directly, apart from some certain capabilities of different resources (such as $Ca{p}_i\left(B\right)$, POD of an aircraft, $Sa{l}_j$ of a vessel). We assumed that they are known in our model. The experience shows that we can get this information through historical data.

Decision variables $x_i$ and $x_j$ express the numbers of aircraft $i$ and vessel $j$. If $x_i$ or $x_j$ is 0, operations did not need aircraft or vessel. Therefore, the mathematical expression of LRMSAR resource allocation scheme is:

$$X=(x_i,x_j),x_i\in \left\{x_1,x_2,\cdots ,x_I,\right\},x_j\in \left\{x_{I+1},x_{I+2},\cdots ,x_{I+J}\right\},$$

(2)

where $x_1,x_2,\cdots ,x_I$ mean the allocation scheme of aircraft, and $x_{j+1},x_2,\cdots ,x_J$ mean the allocation scheme of vessels.

4.2.2. Objective Function

(1) Objective 1: Maximize the probability of a successful LRMSAR (POR)

For emergency rescue operations, the purpose of formulating resources allocation scheme is to effectively complete the LRMSAR task. We considered the facts as follows: on the one hand, it is very important to find and detect people in time, and there is a certain probability that the people can be successfully detected; on the other hand, apart from concerns about detecting the people, it is also important to make sure people are alive when detected. That means that the operation should be rapid and effective. Therefore, we used the POR, which is the probability of a successful LRMSAR operation, to evaluate the efficiency and effectiveness of emergency response. Specifically, POR can directly reflect the whole operation’s success rate. This paper used the following definition of POR: the possibility that people can be searched and rescued alive in a given period of operation time. POR is mainly composed of two parts: POS [15] (probability of search) and POL (probability of live), which is represented in Formula (3). We introduced the concept of the possibility of live to describe how possible the people will be alive as time goes by:

$$POR=POS\times POL$$

(3)

1) Mathematical model of POS

The definition of POS was given in Section 4.1; it can be represented as Formula (11). In search operations, the value of POS is between 0 and 1 [17]. As the search area is input, the people were all included in this area. Therefore, as mentioned in Section 4.1, the value of POC in this paper is 1. Consider that LRMSAR is a multi-aircraft collaborative operation, and different types of aircraft cover different areas. According to the division of responsibility area for different types of aircraft [18], POS can be represented in Formula (4). Where $P_i$ is the probability of detection (POD) of aircraft, S is the search area which both are input parameters. $S_i$ is the search area of different aircraft when operation end. The $S_i$ can be calculated as the search area of a type of aircraft between the time of arrival and the operation end, and it can be represented in the second row of Formula (4). As for the Ts, the end time of search operation, it can be calculated by the third row of Formula (4), where the proving process is denoted in Formula (5). $t_i^a$ is the time of arrival for different aircraft types, which can be calculated by Formula (5). $Ca{p}_i(B)$ is the area of an aircraft searching at a unit time which is an input parameter. For a search operation, all aircraft jointly carry out the search task. When the last aircraft search the last area, it represents the end of the search operations.

$$\begin{array}{l}POS=POC\times POD={\displaystyle \sum \frac{S_i}{S}·P_i}\\ S_i=(Ts-t_i^a)·Ca{p}_i(B)·x_i\\ Ts=\frac{S+{\displaystyle \sum _{i=1}^I{t}_i^{a}Ca{p}_i\left(B\right)x_i}}{{\displaystyle \sum _{i=1}^{I}Ca{p}_i\left(B\right)x_i}}\end{array}$$

(4)

$$\{\begin{array}{l}{\displaystyle \sum _{i=1}^I(Ts-t_i^a)}·Ca{p}_i\left(B\right)·x_i=S\hspace{1em}\left(1\right)\\ t_i^a=\frac{d_i^a}{V_i^a}\hspace{1em}\left(2\right)\end{array}\Rightarrow Ts=\frac{S+{\displaystyle \sum _{i=1}^I\frac{d_i^a}{V_i^a}Ca{p}_i\left(B\right)x_i}}{{\displaystyle \sum _{i=1}^{I}Ca{p}_i\left(B\right)x_i}}$$

(5)

2) Mathematical model of POL

POL represents the possibility that people in distress are still alive when salvaged. When aircrafts locate the people, it will send the position signal to the vessels. The more time spent and worse the maritime environment is, the weaker people will be. Assuming that POL decreases with whole operation time cost, the expression of POL is:

$$POL=\frac{T^l-E\left(T^r\right)}{T^l}$$

(6)

where $E\left(T^r\right)$ is the average waiting time of people getting salvaged. We used $E\left(T^r\right)$ to represent the effect on POL, and the proving process is denoted in Formula (6). $T^l$ refers to the longest survival time of people and $T^l-E\left(T^r\right)$ refers to survival time remaining. Therefore, the greater ratio of $T^l-E\left(T^r\right)$ to $T^l$, the greater the POL. $T^l$ in POL refers to the longest survival time of people; in other words, how long people can survive before getting rescued in an operation [16]. There are two factors that will affect $T^l$, as shown in Figure 5, which are the sea state (B) and time of people getting supplies ($T^s$). In this paper, $T^l$ can be represented by Formula (7).

$$\begin{array}{l}{T}^l=T^l(B)+\Delta T^l\\ \Delta T^l=\alpha \left(1-\frac{E\left(T^s\right)}{T^l(B)}\right)\end{array}$$

(7)

$$\{\begin{array}{l}E(T^s)=\frac{{\displaystyle \sum _{j=1}^N{T}_j^s}}{N}\\ NU{M}_k=S_k·\rho ={\displaystyle \sum _i{x}_i}·Ca{p}_i(B)(t_i-t_{i-1})\\ {\overline{T}}_k^s=t_i+t_{i-1}/2\\ {\displaystyle \sum _{j=1}^N{T}_j^s}=NU{M}_k·{\overline{T}}_k^s={\displaystyle \sum _i[x_i}·Ca{p}_i(B)(t_i-t_{i-1})·\rho ]·\frac{t_i+t_{i-1}}{2}\end{array}\Rightarrow E(T^s)=\frac{{\displaystyle \sum _i[x_i}·Ca{p}_i(B)(t_i^2-t_{i-1}^2)]}{2S}$$

(8)

where $T^l(B)$ is the input parameter referring to the longest survival time of people under certain sea states level B. As we know, if the sea state is worse, the living environment will be worse. $T^l(B)$ is the standard for people to survive in this sea state. Moreover, $\Delta T^l$ is the extended survival time after getting supplies. Due to that the aircraft will airdrop lifesaving supplies when they detect people, the earlier people get the supplies, and the more likely they are to survive. In this paper, $\Delta T^l$ can be represented in the second row of Formula (7), where $\alpha$ is the longest extended time for people. In this paper, the people are found quickly, which assumes the longest extended time can last for 3 h. $E\left(T^s\right)$ is the average waiting time of people before getting searched, which the proving process is denoted in Formula (8). Drawing on the conclusion that survival time of people in biomedical or public health research obeys a normal distribution in certain literature [19], in this paper, we assumed the survival time of all people at sea obeys normal distribution. We used $E\left(T^s\right)$ to measure the effect on $T^l$. It is known that the sooner aircraft find the people, the faster people can get supplies, and the longer people can survive. The shorter $E\left(T^s\right)$ is, the longer $T^l$ will be. See Figure 6.

In Formula (8), N is the number of people that is an input parameter, ${\displaystyle \sum _{j=1}^N{T}_j^s}$ is the accumulation of waiting time of each people in the search operation, which is also the accumulation of time to search for each people. However, we cannot directly get the real waiting time of each person. Therefore, we divided all people into several groups, according to which aircraft and which period they are detected. Due to the difference of velocity, the aircraft arrived one after another. Figure 6 shows the time when different aircraft (a, b, c, d etc.) arrived at the operational area and type set of aircraft participating in different time periods (e.g., types set {a, b, c} for time periods. Thus, the average search time (${\overline{T}}_k^s$) of each group can be obtained, and then the total time of each group can be accumulated as ${\displaystyle \sum _{k=1}^m{T}_k^s}=NU{M}_k·{\overline{T}}_k^s$, where $NU{M}_k$ is the number of people in group k. Hence, we needed to calculate the people detected in each period, such as between $\left[t_0,t_1\right]$, by certain types of aircraft. For $NU{M}_k$, different types of aircraft joined at different times; search velocity was constant in different time periods, thus, the search area $S_k$ in different time periods could be calculated, where $i$ is the aircraft participated in a time period $\left[t_{i-1},t_i\right]$. $Ca{p}_i\left(B\right)$ is the search ability of a certain aircraft, which is an input parameter. $x_i$ is the quantity of a certain type of aircraft. Historic experience shows that the distribution of people is usually highly uncertain and cannot be expressed by an empirical probability distribution. In this paper, we assumed that all people were evenly distributed within the search area. We assumed that the density of people in the search area is $\rho$, thus, the number of people N can be defined as $S·\rho$, and $NU{M}_k$ can be defined as $S_k·\rho$. For ${\overline{T}}_k^s$, because search velocity is constant in different time periods, the average search time in $\left[t_{i-1},t_i\right]$ can be represented as $t_i+t_{i-1}/2$. Thus, we can calculate $E\left(T^s\right)$ in Formula (8).

For $E\left(T^r\right)$ in POL, we assumed that the rescue operation was uniform and continuous, in that people detected were assigned to different vessels to salvage. Based on that assumption, the calculation of $E\left(T^r\right)$ was defined as in Formula (9), where $N·POS$ is the number of people who have been found in the search operation. As shown in Figure 7, the time of each person waiting to be salvaged accumulated constantly. $T_i^r$ is the time of each person waiting for being salvaged. Thus, ${\displaystyle \sum _{i=1}^{N·POS}{T}_i^r}$ is the accumulation of the time spent on salvaging each people, and can be represented in the second row of Formula (9), where $Sa{l}_j$ is the unit time spent on salvaging each people of a vessel $j$. $t_j^v$ is the arrival time of vessel $j$, which can be calculated by input parameters. $x_j$ is the quantity of a vessel $j$.

$$\{\begin{array}{l}E\left(T^r\right)=\frac{{\displaystyle \sum _{i=1}^{N\times POS}{T}_i^r}}{N\times POS}\\ {\displaystyle \sum _{i=1}^{N\times POS}{T}_i^r}={\displaystyle \sum _{j=1}^J\left[N_j{t}_j^v+{\displaystyle \sum _{i=1}^{N_j}i·\left(\frac{Sa{l}_j}{x_j}\right)}\right]}\end{array}\Rightarrow E\left(T^r\right)=\frac{{\displaystyle \sum _{j=1}^J\left[N_j{t}_j^v+{\displaystyle \sum _{i=1}^{N_j}i·\left(\frac{Sa{l}_j}{x_j}\right)}\right]}}{N·Pos}$$

(9)

$N_j$ is the number of people salvaged by vessel $j$ and $N_j$ is actually the number of people salvaged by vessel j, and need to be solved. In order to give full usage to the salvage capability of each type of vessel, it was assumed that the salvage of each vessel was carried out continuously, and all vessels were coordinated and undisturbed. Thus, the following conditions should be satisfied when optimizing the number of people $N_j$. 1) The salvaging time spent by a vessel for $N_j$ people should be longer than that of any vessel for $N_j-1$ people, and less than that of any vessel for $N_j-1$ people. 2) The number of people salvaged ($N_j$) by the vessel $j$ will not exceed the capacity of itself. In the case of a certain number of people, the global optimal solution can be got through the local optimal solution generated by continuous iteration. And then get the $N_j$.

(2) Objective 2: Maximize the average utility of resources (AUR)

When we assigned resources for LRMSAR, if we only pursued the object of maximizing the POR, eventually, all resources meeting the constraints will be assigned to LRMSAR operations. However, in reality, this will cause a waste of resources, and available resources cannot be fully assigned. On the one hand, it is necessary to ensure that certain resources execute daily sea patrol duties and other daily tasks; on the other hand, considering the concurrence of multiple emergencies, it is necessary to ensure the mobility of some resources, so that they can be on standby for other SAR tasks. Moreover, in reality, not all allocated resources can achieve the same effect, and as the resources increase, the marginal utility of resource will decrease. In order to avoid wasting resources, on the premise of maximizing the POR, we should consider using as few resources as possible to complete the LRMSAR operation. Based on the above considerations, the objective of maximizing the AUR should also be added to the optimization of resources allocation. In this paper, the utility can be measured by POR. Thus, the formula for calculating AUR is as follows:

$$AUR=POR/{\displaystyle \sum _{i=1}^M{x}_i}$$

(10)

From Figure 8, we can draw the conclusion that the two objectives in this paper are conflicting. First, from a practical viewpoint, after reaching a certain number, the increment of POR tends to be slow, which shows that the increment of the amount of resources will not always contribute to POR. The reason for this phenomenon is that the marginal utility of resources becomes lower and lower. As the operations proceed, the average workload of resources will gradually decrease, so that the contribution of new resources to the task becomes smaller and smaller. Second, from a mathematic viewpoint, as shown in Figure 8, the slope of the secant is actually the value of AUR (as shown in Formula (10)), and as the value of y-axis (POR) increases, the slope of secant (AUR) decreases. Therefore, the two objectives in this paper are conflicting. When the amount of resources is enough, the POR is high, however, there will be a redundancy of resources, so that AUR is small. When the amount of resources is insufficient, POR is low, but AUR is large. The optimal resource allocation scheme should satisfy maximizing both the two objectives.

4.2.3. Constraints

(1). Total number of resources constraints:

$$\{\begin{array}{l}0\le x_i\le n_i^a,x_i\in N,i=1,2,\cdots ,I\\ 0\le x_j\le n_j^v,x_j\in N,j=1,2,\cdots ,J\end{array}$$

(11)

(2). The upper limit for people of vessel capacity:

$$N\le {\displaystyle \sum _{i=1}^J{\mathrm{c}}_j},\hspace{1em}N\in N^{\ast }$$

(12)

(3). Time for an aircraft (vessel) arrives at the area does not exceed the total time of search (rescue) operation.

Each type of resources must arrive at the operational area before the task is over, or the allocation is meaningless. Thus, both $t_i$ and $t_j$ should satisfy:

$$\{\begin{array}{l}{t}_i<Ts,\hspace{1em}i\in \left\{1,2,\cdots ,I\right\}\\ t_j<Tr,\hspace{1em}j\in \left\{1,2,\cdots ,J\right\}\end{array}$$

(13)

where $Ts$ is the end time of search operation and $Tr$ is the end time of the whole SAR operation.

4.3. Rule-Based Multi-Objective Optimization Algorithm

For solving the above model, and finding the most efficient assignment of available resources, we used rule-based NSGA-II optimization algorithms to solve the problem. Firstly, an LRMSAR resources utilization rule base was constructed to get preliminary feasible resources. Secondly, NSGA-II optimization algorithms incorporated with the proposed model was designed, thus, it can approximate Pareto fronts to get optimal resources allocation scheme candidates. The value of the feasible solution determines the final optimization effectiveness, and usually the feasible solution generated randomly can easily lead to the inability to find the global optimal solution. Thus, the rule-based multi-objective optimization algorithm does not only make full use of the abundant disposal experience and expert knowledge in historical cases, but also makes the algorithms evolution perform on a better initial population basis to find globally optimal solutions faster. The solution to this paper is shown in Figure 9.

4.3.1. Preliminary Feasible Resource Set Based on the Rule Base

The rule base construction can be conducted by two main steps: rule base knowledge acquisition and presentation. For the acquisition, by referring to the experience of SAR service personnel and relevant books, we summarized the applicable rules and operating procedures of resources in real SAR process. These rules knowledge includes detailed information about various SAR resources, and its operating procedures in different environmental situations. For example, the international aeronautical and maritime search and rescue manual [2] jointly launched by the International Maritime Organization (IMO) and International Civil Aviation Organization (ICAO), where the rule knowledge of SAR decision is formulated through experimental research. Relevant knowledge is mentioned in the National Maritime Search and Rescue Manual of China [20]. Some resources utilization rules are shown in

Table 2. Rule knowledge example.

Resources Name	Anti-Wind Grade	Sea State Level	Application Area	Maximum Capacity (/Person)	Maximum Duration of Flight (/h)
Coast Guard Boat 051	7	5	Coastal Area	20	/
Coast Guard Boat 052	6	4	Coastal Area	25	/
Coast Guard Boat 053	9	6	Coastal Area	35	/
Coast Guard Boat 0503	5	4	Shelter Area	18	/
A365N	5	4	/	/	4
S-76C++	6	5	/	/	3.5
S-76A	8	7	/	/	4.5

.

As for the rule knowledge presentation, the primary and foreign keys of the relational database were used to associate rules and express the relationship between knowledge. At present, the semantic network, object-oriented, production, and ontology representation are used in knowledge representation [21]. According to the characteristics of SAR resources utilization rules, this paper chose production representation, one of the most widely used knowledge representation methods to express it. A production system includes three parts: rule base, inference engine, and database. The rule base is made up of independent rules. The BNF description of the long-range SAR resources utilization rules is as follows:

$$\begin{array}{l}<\mathrm{Rule}>::=<\mathrm{Condition}><\mathrm{Decision}><\mathrm{Rule} \mathrm{credibility}>\\ <\mathrm{Condition}>::=<\mathrm{Triggering} \mathrm{Condition} 1><\mathrm{Logical} \mathrm{relationship}><\mathrm{Triggering} \mathrm{Condition} 2>\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}[<\mathrm{Logical} \mathrm{relationship}>\mathrm{L}<\mathrm{Triggering} \mathrm{Condition} \mathrm{i}>]\\ <\mathrm{Decision}>::=<\mathrm{Decision} \mathrm{Clauses}1><\mathrm{Logical} \mathrm{relationship}><\mathrm{Decision} \mathrm{Clauses}2>\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}[<\mathrm{Logical} \mathrm{relationship}>\mathrm{L}<\mathrm{Decision} \mathrm{Clauses} \mathrm{i}>]\\ <\mathrm{Triggering} \mathrm{Condition}>::=\mathrm{AND}(?)|\mathrm{OR}(?)\\ <\mathrm{Rule} \mathrm{credibility}>::=<(0,1]?R>\end{array}$$

(14)

Among them, the values of conditional attributes of rules are different in various scenarios, which will affect the change of results. The premise is also known as conditions, and antecedents. The conclusion is the operation to be performed. Generally speaking, rules can have multiple preceding items, like AND, OR or AND and OR. Therefore, the form of decision rule writing is:

$$\begin{array}{l}IF<\mathrm{Condition} 1><\mathrm{Condition} 2>\\ Then<\mathrm{Decision}>with<\mathrm{Rule} \mathrm{credibility}>\end{array}$$

(15)

Taking Rule 1 as an example, the decision rule of “Above five sea state, HuaYing boat A cannot execute the mission.” is expressed as:

$$\begin{array}{l}IF<\mathrm{sea} \mathrm{state}\ge 5>\\ Then<\mathrm{Huayin} \mathrm{boatA}=\mathrm{NO}>with<1>\end{array}$$

(16)

After standardizing all the rules according to the corresponding standards, the corresponding rule base can be constructed. A flowchart of rule matching mechanism in this paper is shown in Figure 10; the pseudo-code is listed in Algorithm 1.

Algorithm 1. Pseudo-code of rule matching mechanism.

Input: Rule base, R; Global situation data, DGS; Equipment Set, SE. Output: Equipment Candidate, CE. (1). R’ = generate_situation_specified_rules(R, DGS) s (2). FOR e IN SE: (3). IF e satisfies R’ THEN (4). DO add e into CE (5). ENDIF (6). END

4.3.2. NSGA-Ⅱ Optimization Algorithms

Based on the feasible solution of the previous step, the NSGA-Ⅱ algorithm is used for optimization. Since the increase of the candidate resources allocation scheme will lead to the problem of classic NP-hard, the time cost of ordinary algorithms is huge and cannot solve the multi-objective conflict problem. Hence, an optimization is necessary. During the last 10 years, many algorithms, such as SPEA, SPEA2, PAES, NSGA-Ⅱ, [22] etc., have been widely applied in solving discrete multi-objective problems.

NSGA-II is a popular multi-objective evolutionary algorithm (MOEA), which uses non-dominated sorting and shares variable methods to maintain the diversity of Pareto frontiers effectively, and it has been proven to be effective in solving two objective problems [22,23]. The implementation is based on the MOEA Framework (http://moeaframework.org/), which is a free and open source Java library for developing and experimenting with MOEAs.

NSGA-II uses a fast non-dominated sorting mechanism to reduce the computational complexity of non-dominated sorting, and introduces elite mechanism into the algorithm to improve the performance of the algorithm. In order to maintain the diversity of the population, crowding distance is used to rank individuals in the same non-dominant sequence. The algorithm flow of NSGA- II can be described as follows:

Step 1: define the parameters of the algorithm including population size, iterations, and the crossover probability parameter.

Step 2: initialize the population. The initial population is randomly generated based on a feasible solution of the previous step.

Step 3: sort the population. Each individual stands for specific resource allocation. By calculating the parameters of the INLP model and the objective functions above, the individuals will be evaluated and a non-dominated sorting to the initial population will be made to get the Pareto solution set. Then, individuals are given ranks and crowding distance values, and the binary tournament selection operation will be implemented.

Algorithm 2. Pseudo-code for the proposed algorithm.
Input: Initial population members, P of size N, maximum number of generations, maxGen, crossover probability, pc, mutation probability, pm Output: P, BestF
(1).	BestF$\leftarrow \varnothing ;$
(2).	count=0;
(3).	InitializeScenario(B,N,S,M, Aircraft,I Ship,J,);
(4).	P ← GeneratePopulation(N);
(5).	for i ← 1 to maxGen
(6).	$t_i^a,t_j^v$ [I+J] $\leftarrow$ Calculateti(P);
(7).	$Ts$$\leftarrow$ CalcuculateT(P, $t_i^a$);
(8).	$S_i$ [N] $\leftarrow$ Calculatesi(P, $Ts$);
(9).	POS$\leftarrow$ Calculatepos(P, $S_i$[N]);
(10).	PersonDetected$\leftarrow$N*POS;
(11).	$N_j$$\leftarrow$ Sort($t_j^v$);
(12).	for j $\leftarrow$ 1 to N;
(13).	ShipPerformsSalvaging$\leftarrow$ FindMinT(TimeSequenceofShip);
(14).	count$\leftarrow$count +PersonSalvaged(P, ShipPerformsSalvaging);
(15).	UpdateTimeSequence(TimeSequenceofShip);
(16).	if count+1>PersonDetected;
(17).	Break;
(18).	$E\left(T^s\right)$$\leftarrow$ Et1 ($Ca{p}_i\left(B\right)$, $t_i^a$)
(19).	$E\left(T^r\right)$$\leftarrow$ Et2 (N,POS, Salj)
(20).	POL$\leftarrow$ Possibilityoflive($E\left(T^r\right)$, $E\left(T^s\right)$)
(21).	ConstraintsCheck(P);
(22).	Obj1$\leftarrow$ POR(P,POL,POS);
(23).	Obj2$\leftarrow$ CalculateAUR(P,POR)
(24).	Non-dominated sorting(P);
(25).	Oc$\leftarrow$ Crossover(P,pc);
(26).	Om$\leftarrow$ Mutate(P,pm);
(27).	end
(28).	BestF$\leftarrow$ nondominatedsorting(P);

Step 4: mutation and crossover. The mutation operator is used to mutate the population, and the offspring population Q is generated by crossover operations on each individual with a certain probability.

Step 5: evaluate the temporary population. Non-dominated sorting and crowd distance sorting will be conducted on the temporary population, which is composed of the present population P and the offspring population Q.

Step 6: generate a new population. Select the best half individuals from the temporary population to generate a new population.

Step 7: evolution and iteration. The termination condition is then checked to see whether the algorithm should stop: if yes, the current population is the result and if no, new populations will be generated to start a new iteration from step 3.

Since the objective function is a complex calculation process based on INLP model parameters, the detailed calculation flow integrated with the NSGA-II is listed in Algorithm 2.

5. Case Study

In order to verify the validity of the proposed model, we use some instances to clarify in this section. The calculation and analysis of the case are demonstrated in this part. The scheme is a large-scale distress occurring in the Beihai Sea, China. A merchant ship with 70 people caught fire, and the vessel lost power. Because of the danger of overturning, the people on that ship abandoned the ship. After the distress occurred, the ship personnel issued an emergency alert through the special communication equipment for distress. After receiving the confirmation of the alarm information, the Beihai Search and Rescue Center (SARC) made a SAR emergency response according to the procedure. On the basis of measuring sea state, grasping the available SAR resources around the surrounding area, and calculating the search area, it is necessary to urgently allocate resources to operate SAR task and save people’s life. According to the definition given by the Chinese State Oceanic Administration, this action belongs to the long-range SAR operation, with the distress location more than 20 nautical miles from the shore. The basic information of the emergency is as follows: a merchant vessel with 70 people was caught fire, which lost power and person has abandoned this vessel. The distance between the distress area and the nearest local professional SARC and Naval SARC is 90 and 120 nautical miles, respectively. Meanwhile, there are five fishing and merchant vessels available in the vicinity of the operational area, and some professional rescue vessels and aircraft in the local professional SARC are carrying out routine patrols outside. The operational area to be searched is 800 (n mile)². The current sea state level is measured as level 4, and the wind grade is 3. According to the historical data statistics and the experimental results, the longest waiting time of people in distress at the sea state level 4 is almost 5 h. The basic information of available resources performance is shown in

Table 3. Information on SAR resources performance.

Resource Type	Affiliated Organization	Resource Performances
		${\mathit{d}}_{\mathit{i}}^{\mathit{a}},{\mathit{d}}_{\mathit{j}}^{\mathit{v}}$ (kn)	${\mathit{b}}_{\mathit{i}}^{\mathit{a}},{\mathit{b}}_{\mathit{j}}^{\mathit{v}}$	${\mathit{v}}_{\mathit{i}}^{\mathit{a}},{\mathit{v}}_{\mathit{j}}^{\mathit{v}} (\mathbf{kn}/\mathbf{h})$	$\mathit{C}\mathit{a}{\mathit{p}}_{\mathit{i}}\left(\mathit{B}\right)$ (n mile2 h−1)	${\mathit{P}}_{\mathit{i}}$	$\mathit{S}\mathit{a}{\mathit{l}}_{\mathit{j}}$ (h)	${\mathbf{c}}_{\mathit{j}}$	${\mathit{n}}_{\mathit{i}}^{\mathit{a}},{\mathit{n}}_{\mathit{j}}^{\mathit{v}}$
Zhi-8A helicopter	P	90	4	220	100	0.95	0	0	2
Zhi-8S helicopter	P	90	3	170	90	0.7	0	0	2
B-27 fixed-wing aircraft	P	90	4	300	130	0.9	0	0	3
Y-12 fixed-wing aircraft	P	90	4	620	240	0.91	0	0	1
Huaying ambulance boat	P	90	4	39	0	0	0.02	3	4
Beihai resuce 117	P	90	4	27	0	0	0.06	15	2
Rescue Boat	G	90	4	32	0	0	0.03	7	3
Large Marine Rescue Vessel	G	90	5	22	0	0	0.08	20	1
Zhi-8KA helicopter	G	120	5	280	120	0.8	0	0	2
Yun-12 fixed wing aircraft	G	120	4	550	200	0.95	0	0	2
Be-200 fixed wing aircraft	G	120	3	700	270	0.85	0	0	1
Hospital-ship	G	120	5	18	0	0	0.12	40	1
920rescue boat	G	120	3	35	0	0	0.01	8	3
Haixun 01	G	120	5	40	0	0	0.08	20	2
Fishing vessel A	S	30	4	12	\	\	0.04	12	1
Fishing vessel B	S	40	5	10	\	\	0.01	10	1
Fishing vessel C	S	80	5	9	\	\	0.05	9	1
Merchant vessel A	S	120	4	32	\	\	0.15	32	1
Merchant vessel B	S	150	4	39	\	\	0.1	39	1

.

Based on the above known information, the resources of different organizations were allocated to satisfy the efficient implementation of operations with as few resources as possible. The integer nonlinear programming model of this paper was used to solve the optimal resource allocation scheme.

In the first line of the table, the performance of $d_i^a,d_j^v$, $b_i^a,b_j^v$, $v_i^a,v_j^v$, $Ca{p}_i\left(B\right)$, $P_i$, $Sa{l}_j$, ${\mathrm{c}}_j$, $n_i^a,n_j^v$, respectively, express the initial distance of aircraft/vessel from the operational area, the maximum sea states allowed by the aircraft/vessel to go to sea, speed of each aircraft/vessels types, search ability of aircraft under sea states level 4, probability of detection ($POD$) of the $i$th aircraft, the unit time of the $j$th vessel salvage for each people, the maximum capacity of the $j$th vessel, and the available quantity of each aircraft/vessels type. In the second column, affiliated organization ”P” means professional SARC, ”G” means government SAR force, and “S” means social SAR force.

5.1. Preliminary Feasible Resources Based on the Rule Base

The above resources information and environmental information were input into the rule base we have constructed, and the rule matching engine was used to screen the feasible resources. That is to say, the actual environmental information was input, such as the current sea state level is 4, the wind grade is 3, and so on. It matched the performance of the resources through rule base. The resources were filtered to get an initial set of feasible resources, as shown in

Table 4. Preliminary feasible resources set.

Affiliated Organization	Resource Type
Professional Search and Rescue Center (SARC)	Huaying ambulance boat
Professional SARC	Beihai rescue 117
Government Search and Rescue (SAR) force	Haixun 01
Professional SARC	Rescue lifeboat
Social SAR force	Fishing vessel A
Social SAR force	Merchant vessel A
Social SAR force	Merchant vessel B
Professional SARC	Zhi-8A
Professional SARC	Zhi-8S
Professional SARC	Y-12
Professional SARC	B-27
Government SAR force	Yun-12
Government SAR force	Be-200

.

5.2. NSGA-Ⅱ Algorithms to Optimize Resource Allocation

According to the information in the case, we know B = 8; N = 70; S = 800 (n mile)²; $T^l\left(B\right)$ = 5; in this case, six aircrafts and seven vessels can be allocated (M = 13, I = 6, J = 7). Therefore, the decision variable $X$ for this case is represented in Formula (14):

$$\begin{array}{l}X=\left(x_i,x_j\right)\\ =\underset{aircraft}{\underbrace{(x_1,x_2,\cdots ,x_6,}}\underset{vessel}{\underbrace{x_7,\cdots ,x_{13})}}\end{array}$$

(17)

The above known information is input into the multi-objective INLP model. NSGA- II intelligent optimization algorithms were incorporated. The proposed model was designed to approximate Pareto fronts to get optimal resources allocation scheme candidates. In the application of NSGA-II algorithm, the championship selection mechanism was used to simulate binary crossover and differential mutation operators, and the termination condition is to select the maximum evolutionary algebra. We initialized the size of the candidate solutions to 200 and set the maximum generation to 1000. In the crossover operator, the crossover probability was set to be 0.8. The probability of the bit flip mutation was 0.05.

Finally, the optimal solution set of the LRMSAR was obtained through the algorithm of NSGA-II, and the Pareto frontier is shown in Figure 11, the x-axis is POR, and the Y-axis is AUR. Finally, we get 11 Pareto solutions in

Table 5. The solutions to resource allocation solved by the NSGA-II.

Serial Number	Resource Allocation Scheme	Obeject1: POR	Obeject2: AUR
A	[0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 1 0 0 0]	0.3646	0.0729
B	[0 1 1 1 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0]	0.4107	0.0684
C	[0 1 1 1 0 0 1 1 0 0 0 0 0 0 0 1 0 1 0]	0.4563	0.0652
D	[0 1 2 0 0 0 1 1 0 0 1 0 0 0 0 1 0 1 0]	0.4760	0.0595
E	[1 1 2 0 0 0 1 1 0 0 1 0 0 0 0 1 0 1 0]	0.4890	0.0543
F	[2 1 3 0 0 0 1 1 0 0 0 0 0 0 1 1 0 1 0]	0.5042	0.0504
G	[4 1 2 0 0 0 1 1 0 0 0 0 0 0 0 1 0 1 0]	0.5204	0.0473
H	[4 1 3 0 0 0 1 1 0 0 0 0 0 0 0 1 0 1 0]	0.5228	0.0435
I	[4 1 2 0 0 0 1 1 0 0 0 0 1 0 1 1 0 1 0]	0.5289	0.0407
J	[4 1 3 0 0 0 1 1 0 0 0 0 1 0 0 1 0 1 0]	0.5312	0.0379
K	[4 1 3 0 0 0 1 1 0 0 1 0 1 0 0 1 0 1 0]	0.5313	0.0354

.

5.3. Result Analysis

Since our model is an integer programming model, we generated 11 Pareto solutions. In addition, it is the candidate of LRMSAR resource allocation scheme. In the next part, we analyzed the results of the case.

5.3.1. Comparison of the Pareto Set

Firstly, we made a comparative analysis on the value of two objectives of these 11 schemes. As shown in Figure 12, it can be seen that the lower the value of AUR is, the higher the value of POR will be. In addition, the two objectives are contradictory. The value of POR is increased from the scheme A to K. However, the growth rate of POR has been getting slower and slower since the beginning of scheme F, which finally close to the line. It is clear that with the growth of the value of POR, and the value of AUR decreases. Therefore, with the increasing number of resources, the growth of POR will be slower and slower, indicating that the contribution of the continued increased resource to the LRMSAR operation will gradually approach 0. That is to say, the marginal utility of resources becomes lower and approaches 0.

From Figure 12, the highest resource of POR is scheme K, followed by J. By comparing the resource composition and POR of these two schemes, the difference of POR of these two schemes is only 0.0001, while the resource composition of scheme J used one vessel fewer than K, and the vessel is Merchant vessel A. In fact, the contribution of Merchant vessel A to long-range maritime SAR operations is not great, thus, the improvement of POR can also be neglected. Therefore, Merchant vessel A has little significance to participate in LRMASR operations. Merchant vessel A can be provided to decision makers as an alternative resource. Similarly, by analyzing the differences between other schemes, we can formulate alternative resources sets.

5.3.2. Detailed Procedure Analysis of the Solution

Secondly, in this section, we are going to deeply analyze two schemes in the above, to shed some light on the calculating process of our model. In this way, we wanted to show how decision-makers’ preferences can affect the final results, in details, how results differ in the aspect of two different optimization purposes. In

Table 6. Resource type and quantity constitution of scheme F, K.

(a) Scheme F
Scheme F	Professional SARC	Government SAR Force	Social SAR Force
Aircraft	Y-12 fixed-wing aircraft x1 Zhi-8A helicopter    x1	Yun-12    x1
Vessel	Huaying ambulance boat x2 Beihai rescue 117    x1 Rescue lifeboat     x3	Haixun 01    x1	Fishing vessel A x1
POR	0.5042
AUR	0.0354
(b) Scheme K
Scheme K	Professional SARC	Government SAR Force	Social SAR Force
Aircraft	B-27 fixed-wing aircraft x1 Y-12 fixed-wing aircraft x1	Yun-12    x1
Vessel	Huaying ambulance boat x4 Beihai rescue 117    x1 Rescue lifeboat    x3	Haixun01   x1	Fishing vessel A  x1 Merchant vessel A x1
POR	0.5312
AUR	0.0379

a,b, there are separately show the resource type and quantity constitution of scheme F and K.

a) Calculating Process “Search Operation”

Table 7. Results illustration of the search operation in schemes F and K.

(a) Scheme F				(b) Scheme K
Scheme F Aircraft	Arrived Time (h)	Search Area (n mile2)	People Detected	Scheme K Aircraft	Arrived Time (h)	Search Area (n mile2)	People Detected
Y-12	0.145	444	35	Y-12	0.145	308	24
Yun-12	0.218	356	29	Yun-12	0.218	242	20
Zhi-8A	0.3	146	11	B-27	0.409	102	9
$Ts$	1.996			$Ts$	1.43
POS	0.91			POS	0.925

a,b shows that some results about search operation of resource allocation F, K. Scheme F has aircraft such as: one Y-12, one Yun-12, and one Zhi-8A are listed in Table 7a, we can get the distance of each aircraft, from the starting position to where emergency happened. In addition, according to their velocity, the arrival time of each aircraft can also be calculated, which was 0.145 for Y-12, 0.218 for Yun-12 and 0.3 for Zhi-8A, as illustrated in Table 7. From this point, we can get two important metrics: 1) as discussed in our model, aircraft are supposed to join the search operation as they arrive at the searching area. Therefore, we can get each aircraft’s searching area increment as time goes on. 2) If the search area is given, we can obtain the number of people detected at a certain time, as illustrated in Table 7. Additionally, the average waiting time of each person can be obtained.

Compare these two schemes, the total time of search operation of scheme K is faster than F. Different aircraft join the operations, and their search area is completely different. Hence, as the possibility of search (POS) is calculated according to each aircraft’s search area and the possibility of detection (POD), it can be calculated that the POS for each scheme is 0.912 and 0.925, which means scheme K shows the advantages of a high POS. From Table 7, only one aircraft is different between the two schemes, and it can be seen that B-27 is superior to Zhi-8A. From the decision makers’ standpoint, they can decide the scheme according to the urgency. Along with the POS being calculated, the number of people detected is clear, and rescue operation is targeted on these people. However, POS is not the only metric which should be considered during the search operation. People in distress should be located and delivered with supplies as soon as possible. Therefore, their survival time can be extended according to the environment. When the vessels find them as soon as possible, their possibility of live (POL) can be guaranteed at a high level. In this aspect, all the aircraft are expected to arrive and search the emergency area quickly. It is easier to be found when aircraft Y-12 and Yun-12 are selected in both two schemes, which results from the fact that their arrival time is the earliest compared to the rest. Ts (Time of search operation) of scheme K is higher than F, thus, the aircraft in scheme K search for all people faster, and the material required is given in the form of airdrop. According to Formula (8), for scheme K, the average waiting time for each person to be searched ($E\left(T^s\right)$) is 1.12 h, and referring to Formula (7) the survival time for people in distress is extended by 2.4 h. Hence, the longest waiting time for people to be rescued is extended to 7.4 h from 5 h.

b) Calculating Process “Rescue Operation”

Since the purpose of the rescue operation is to salvage people as quickly as possible, we needed to find the scheme that all the vessels can finish the rescue operation in an acceptable time. Similar to the aircraft, vessels vary in the aspect of arrival time, along with the difference in the capability of salvaging. In the most perfect situation, vessels will have enough carrying capacity, thus, they will continue on salvaging instead of waiting. Reflected in two schemes, for vessels of scheme F demonstrated in Figure 13a, different column colors represent the number of salvaged people of different vessel before a certain time, the x-axis refers to the time of rescue operation, the y-axis refers to the number of people salvaged. For vessels of scheme K demonstrated in Figure 13b. We can see that the arrival time of different vessels vary in the range of 2 to 4. The Huaying ambulance boat arrive the salvaging location first, fishing vessel A follows, and both finish their salvaging task between 2.81 and 3. Because the Huaying ambulance boat has strong salvage ability, but its capacity to carry people (${\mathrm{c}}_j$) is limited, the salvage operation ends early. In scheme F, there is one Huaying ambulance boat, while in scheme K, there are two. Rescue lifeboats also play an important role in the whole operation, because one-third of people are saved by it. It is observed that despite the limitation of capability, during the whole operation, there are at least two types of vessel are salvaging people. Hence, both schemes can make full use of the time. There are also some differences between these two schemes: scheme F takes 0.25 h more than scheme K, but it only requires eight vessels, while scheme K needs eleven vessels. On the other hand, scheme F takes full use of its vessels while scheme K needs a merchant vessel to take part, and only salvages two people while its capacity is up to 20.

As discussed in a), we can get $E\left(T^s\right)$. Using both $E\left(T^s\right)$ and $E\left(T^r\right)$ calculated by Formula (9), in our model the POL of each scheme is 0.54 and 0.57. The results show that because scheme F takes more time to finish the salvaging operation, it gets a poor POL compared with scheme K, which means the people in distress at the sea have more possibility to survive in scheme K.

It is easy to get the POR for scheme F and scheme K, which is the product of POS and POL. By Formula (3) we can calculate the average utility of resources (AUR) of each scheme, which is 0.0379 and 0.0354. Comparing the AUR of them, there is an obvious tradeoff between POR and AUR. In most of the case, decision makers may want a higher POR; however, some aircraft or vessels must be on duty. It is up to decision makers to decide which scheme should be used. As discussed above, if decision-makers want to have a high possibility of search, they may want to choose scheme K. However, in some certain cases, such as when multiple emergencies are happening, decision-makers may want a more efficient scheme that can avoid wastes of equipment.

To sum up, the results show that our method can greatly improve LRMSAR’s efficiency and ultimately reduce casualties. At the “Oriental Star” sunken ship accident in 2016, the SAR resource was allocated by traditional experience; 12 people were rescued and 442 people were killed [24]. Contrarily, in a merchant vessel accident in case study, the SAR resource was allocated by our optimization method; about 52–63 people could have been rescued. Compared to these two accidents, the optimization method is more efficient than the traditional method.

The model in this paper was constructed on the theoretical basis of the Optimistic Criterion [25] (Max-max Criterion), one of the uncertain decision-making theory. Based on this, our model was constructed under certain ideal conditions. When constructing the mathematical model of problem, in order to reflect the real LRMSAR situation, the elements in actual SAR operation are considered as much as possible. However, maritime search and rescue operations are affected by the harsh environment, which makes the real operation very difficult. Especially for long-range maritime SAR operation, there are many risks in the operation process, and the fact is more complex than the proposed model in this paper. Therefore, the resources allocation of LRMSAR remains a risk decision.

This paper proposed a basic model of resource allocation, however, there are still some challenges that need to be addressed in the future. First, we will try to use an agent-based simulation method to simulate uncertain events. The position of people in distress at sea is highly uncertain and dynamic in maritime search and rescue. In reality, due to the harsh environment at sea and ocean currents, people will float away from the original position. Second, the collaborative relationship between resources will be taken into account in the problem model. There is a synergistic relationship between different resources in SAR organizations, usually in SAR formations or other forms. Third, emergency response is actually a dynamic process based on the evolution of accident. Therefore, decision makers need to consider various scenarios that may occur in the future of emergency, and the estimation information of the probability of occurrence in each scenario to allocate resources. Future research should concern the probability of various scenarios within the model.

6. Conclusions

The problem of resource allocation in maritime search and rescue is a hot issue in the academic and engineering domains. Compared to short-range maritime SAR, long-range maritime search and rescue (LRMSAR) is more challenging due to the far distance from the shore, changeful weather, and less available resources. Such an operation put high requirements on decision makers to timely assign multiple resources, to ensure the effective operation and rational use of resources. Thus, it is necessary for decision makers to allocate a sustainable resources scheme. However, there are seldom works focusing on resource allocation for aircraft and vessels in maritime SAR, and less on LRMSAR. To solve this problem, we proposed a method to provide support for decision makers to allocate multiple resources in dealing with LRMSAR problem.

Our paper provides a new thought for the research on resource allocation of LRMSAR. Firstly, we formulated resource allocation as a multi-objective integer nonlinear programming (INLP) problem, which aims to ensure the abilities for fulfilling different emergency tasks efficiently and effectively with reasonable resource allocation. Then, two mathematical objectives functions were formulated to measure the efficiency and effectiveness of LRMSAR. Secondly, for NP-hard model solving, an LRMSAR resources rule base was constructed to obtain preliminary feasible resources. Then, the NSGA-Ⅱ algorithm was modified according to the characteristics of LRMSAR resource allocation, to approximate the Pareto front with non-dominated scheme candidates. In the case study, based on the proposed models and algorithm, 11 resource allocation schemes were obtained, and calculation processes of two schemes were further analyzed. This showed that when the possibility of LRMSAR operation (POR) reached a certain level, adding extra resources will only result in wasting, and it did not make sense for the effectiveness of whole operations. At the same time, the influence of decision makers’ preferences will significantly affect the structure of schemes.

In general, the proposed models and approaches can be applied to resource allocation problems of MSAR, to provide decision-makers with scientific decision support on different emergency tasks. However, this paper has merely proposed a basic model of LRMSAR resource allocation, which was simplified to some extent, and there are still some challenges that need to be addressed in the future, as mentioned in Section 5.3.2. In the next step, a dynamic drift of people at sea could be considered using a more comprehensive resource allocation model.