An improved genetic algorithm for solving the helicopter routing problem with time window in post-disaster rescue

1.   Introduction

Natural disasters such as earthquakes, tsunamis and hurricanes have devastating consequences for human lives and infrastructure ^[1]. These catastrophic events not only cause immense damage to society, they also pose significant threats to human health and well-being. In recent years, post-disaster rescue has received extensive attention as a critical research field ^[2,3]. The timely and effective response to such emergencies is paramount to saving lives and minimizing the impact on affected communities. Disasters frequently lead to the destruction of roads, which presents substantial challenges for ground transportation and rescue operations. As a result, the utilization of helicopters can be an effective rescue method. Immediately after a large-scale disaster, helicopters are extensively employed for emergency medical services, search and rescue operations and the transportation of supplies and victims ^[4]. Helicopters possess the unique capability to access remote and inaccessible areas regardless of the terrain ^[5]. Therefore, the development of efficient and intelligent optimization algorithms for helicopter routing in post-disaster rescue is of paramount importance in improving rescue efforts and minimizing the loss of life and property ^[6].

The vehicle routing problem (VRP) in post-disaster rescue presents a complex and challenging problem ^[7]. When dispatching helicopters, considerations should not only encompass transportation costs, they should also prioritize rescue efficiency and effectiveness. First, the capacity constraints of helicopters limit the transport of injured individuals and supplies. In post-disaster rescue, the maximization of transportation capacity for victims and essential relief materials in each flight is of paramount importance. This strategic approach is aimed at enhancing rescue efficiency and effectively increasing the rate of lives saved. Additionally, post-disaster rescue efforts are often characterized by time sensitivity, which directly influences the outcomes of survival. Consequently, rescue sites have imposed heightened requirements on helicopter response times. Finally, a critical objective in helicopter rescue missions is to determine the shortest path. By identifying the most efficient route, response times can be minimized, enabling rescuers and supplies to swiftly reach the affected areas and provide prompt emergency relief.

The dispatch of helicopters in post-disaster rescue operations can be considered as an extension of the VRP problem. The genetic algorithm (GA) is a well-established optimization algorithm that has been successfully applied to various types of optimization problems ^[8,9,10]. The GA is known for its competitiveness and adaptability, making it a widely used method in many fields. Notably, the GA has demonstrated its effectiveness in solving VRPs ^[11,12,13].

Considering the characteristics of the GA and the aforementioned problems, this paper proposes the improved GA (IGA) to tackle the VRP with a time window (VRPTW) in post-disaster rescue. In the proposed algorithm, each chromosome encodes a two-dimensional vector to enhance the exploration capability of the GA to address such problems. To address the challenge of obtaining feasible solutions for large-scale constraint problems, a repair strategy has been devised to enhance the performance of the proposed algorithm. Furthermore, to enhance the quality and diversity of the population, an efficient cooperative initialization strategy has been developed. Additionally, to improve the exploitation abilities, the proposed algorithm incorporates a local search strategy based on an improved greedy insertion heuristic. Moreover, to reduce the likelihood of the population being trapped in local optima and enhance global search capabilities, a global search strategy based on encoding structure destruction and construction is presented.

The main contributions of this study are as follows:

1) A cooperative initialization strategy is proposed to enhance the quality and diversity of the population at the beginning of the proposed algorithm, which leads to better performance.

2) A local search strategy is embedded to improve the exploitation capabilities, which enables the proposed algorithm to converge to better solutions.

3) A global search strategy is presented to alleviate the issue of getting trapped in local optima and improve the global search capabilities.

The remaining sections of this paper are organized as follows. Section 2 reviews the literature related to the VRP. Section 3 provides a brief introduction to the problem description and formulation. Section 4 presents all of the components of the proposed algorithm. The experimental results and analysis are shown in Section 5, followed by the conclusions of this study in Section 6.

2.   Literature review

The VRP is a classical combinatorial optimization problem that was first proposed by Dantzig and Ramser ^[14], attracting considerable attention from the research community. In recent years, the VRP has found extensive application in various fields, such as home healthcare logistics ^[15,16] and municipal solid waste disposal ^[17]. The research on the VRP is progressing and expanding. Zulvia et al. ^[18] proposed a green VRP for perishable products, which optimizes operational cost, deterioration cost, carbon emissions and customer satisfaction. Expósito et al. ^[19] studied a hybrid metaheuristic to solve the VRPTW from the quality of service perspective. Liu et al. ^[20] proposed an optimized solution for the time-dependent VRPTW by utilizing an improved ant colony algorithm with a congestion-avoiding approach. The approach aims to mitigate traffic congestion during peak hours and temporal traffic congestion. Bianchessi nd Irnich ^[21] investigated a new and tailored branch-and-cut algorithm in order to avoid traffic congestion and reduce the total costs.

With the increasing complexity of problems, researchers are placing growing emphasis on the development and application of efficient optimization algorithms ^[22,23,24]. Continual development and evolution of various optimization algorithms ^[25,26,27] are being pursued to solve models of various problems ^[28,29]. The optimization algorithms dedicated to solving the VRP have gained significant attention in recent years, making it a prominent research area. Optimization algorithms have achieved significant research accomplishments in various fields ^[30,31,32]. Duan et al. ^[33] developed a robust multiobjective particle swarms optimization approach by incorporating an advanced encoding and decoding scheme, a robustness measurement metric, and a local search strategy to solve the VRPTW under uncertainty. Shen et al. ^[34] presented a hybrid swarm intelligence algorithm that incorporates both inter-route and intra-route improvement heuristics to solve the VRPTW and minimize the total distance. Brito et al. ^[35] utilized a variable neighbourhood search algorithm to solve the close–open VRPTW. Keskin and Catay ^[36] developed an adaptive large neighborhood search algorithm with several removal and insertion mechanisms to solve the VRPTW. Ahmed and Yousefikhoshbakht ^[37] proposed an improved tabu search (TS) algorithm with the intensification and diversification mechanisms to solve the heterogeneous fixed fleet open VRPTW.

Post-disaster rescue is a critical application field of the VRP, dedicated to ensuring prompt disaster response and facilitating the timely delivery of emergency rescue services ^[38]. Numerous VRP models and algorithms have been proposed by researchers to address post-disaster rescue scenarios. Vieira et al. ^[39] proposed hybridizing the ant colony optimization (ACO) metaheuristic with random variable neighborhood descent to solve the VRP problem. The objective of their study was to minimize the operational costs associated with emergency water transport in arid regions. Yi et al. ^[40] developed an enhanced monarch butterfly optimization algorithm to tackle the emergency VRP in natural disaster relief. Maghfiroh and Hanaoka ^[41] utilized a modified simulated annealing (SA) algorithm to solve the dynamic truck and trailer routing problem in last mile distribution for disaster response.

Although there have been numerous studies on post-disaster rescue, there are few studies on the problem of helicopter dispatching in situations where roads are blocked. To fill the aforementioned gaps, this paper models the dispatching helicopter problem in post-disaster rescue, taking into account various factors such as time window constraints, helicopter loading capacity, the transport of injured individuals and supplies and travel distance. Moreover, we have designed an IGA for solving the dispatching helicopters problem in post-disaster rescue.

3.   Problem description and formulation

This section presents the description and formulation of the VRPTW for helicopter rescue operations. First, a formal description of the VRPTW for helicopter rescue operations is provided, along with key assumptions. Then, the proposed VRPTW is mathematically formulated.

3.1.   Problem description

In this study, the dispatching helicopter problem in post-disaster rescue is modeled as an extension of the VRPTW (hereafter called the H-VRPTW). The features of the H-VRPTW are as follows: 1) The system consists of two types of helicopters: rescue helicopters and transport helicopters. 2) Each rescue site has two types of demands, a service duration and a time window constraint. 3) The rescue helicopter is responsible for rescuing all of the victims. 4) The transport helicopter is primarily responsible for delivering supplies to all of the rescue sites, and if the transport helicopter is carrying less than half of its maximum capacity, it can serve as a rescue helicopter and transport injured individuals who are encountered along the way to the rescue center. 5) The rescue sites have perfect communication functionality to ensure smooth information transmission.

The assumptions of the H-VRPTW are as follows:

1) There is only one rescue center and all helicopters must depart from and return to the rescue center.

2) Each rescue site is visited once by each type of helicopter.

3) The demand for rescue sites along the route should not exceed the carrying capacity of the helicopter.

4) Each helicopter must return within the specified maximum route time.

5) The time window of each rescue site cannot be violated.

3.2.   Problem formulation

The H-VRPTW is represented by the directed graph $G = (N, A)$, where $N = \{0\}\cup R$. The set $R$ represents nodes of the rescue sites, and the 0 represents the rescue center. The set of arcs connecting vertices of $N$ is denoted by $A = \{(i, j)\mid i, j\in N, i\neq j\}$. Each rescue site $i\in N$ is assigned a service duration $t_i$ and a time window $[a_i, b_i]$, where $a_i$ and $b_i$ define the earliest and latest possible service times for the rescue site. The arrival time of a helicopter at rescue site $i$ is represented by $g_{ik}$, and the distance traveled for the arc $(i, j)\in A$ is represented by $d_{ij}$. $TH = \{1, \dots, n_1\}$ is the set of transport helicopters, and $RH = \{n_1+1, \dots, n_1+n_2\}$ is the set of rescue helicopters. $H = TH\cup RH$ represents all of the helicopters. Each helicopter $k\in H$ is required to depart from and return to the rescue center.

Taking into account the unique characteristics of the system, the demand for material and casualty care at rescue site $i$ is denoted by $dm_i$ and $dn_i$, respectively. The maximum capacities of helicopter $k$ for material and casualty care are represented by $cm_i$ and $cn_i$, respectively. The notations used in the model are as follows:

Indices:

0: Index of the rescue center

$i, j$: The rescue site index

$k$: Helicopter index

Sets:

$N$: Set of rescue sites and rescue center in the system

$R$: Set of rescue sites

$H$: Set of helicopters in the system

$TH$: Set of transport helicopters

$RH$: Set of rescue helicopters

Parameters:

$a_i$: The earliest service time for rescue site $i$

$b_i$: The latest service time for rescue site $i$

$d_{ij}$: Distance between nodes $i$ and $j$

$dm_i$: The demand for material at rescue site $i$

$dn_i$: The demand for casualty care at rescue site $i$

$cm_i$: The maximum capacity for material for helicopter $k$

$cn_i$: The maximum capacity for casualty care for helicopter $k$

$t_i$: Service duration for rescue site $i$

Decision variable:

$Z_{ijk}$: A binary value that is set to 1 if helicopter $k$ travels directly from the rescue site $i$ to rescue site $j$; otherwise, $Z_{ijk}$ is set to 0, where $i, j \in N$ and $i \neq j$.

$Y_{ik}$: A binary value that is set to 1 if helicopter $k$ serves the rescue site $i$; otherwise, $Y_{ik}$ is set to 0, where $i \in R$.

$g_{ik}$: Arrival time of a helicopter $k$ at rescue site $i$.

$ts_{ik}$: The time when helicopter $k$ started service at rescue site $i$.

Objective:

Constraints:

The objective function in Eq (1) minimizes the total distance traveled by all helicopters. Constraints given by Eqs (2) and (3) state that each route taken by the helicopter starts and ends at the rescue center. Constraints given by Eqs (4) and (5) ensure that each type of helicopter can only be visited once for each rescue site. Constraints given by Eqs (6) and (7) ensure the capacity constraints for material transport and casualty care for the helicopter. Constraints given by Eqs (8) and (9) require that the time of service for each rescue site falls within its time window. Constraints given by Eqs (10) and (11) imposes a restriction on the decision variable.

4.   Proposed algorithm

This section presents the proposed IGA for solving the H-VRPTW problem. The general framework of the IGA is outlined, followed by a detailed description of various components, including encoding and decoding methods, initialization, a crossover operation, a mutation operation, a repair strategy, a local search strategy and a global search strategy. Lastly, the complexity of the proposed IGA is analyzed, providing insights into the computational requirements and efficiency of the proposed algorithm.

4.1.   IGA framework

An improved version of the classical GA has been proposed to solve the dispatching problem in post-disaster rescue. The framework of the IGA approach is shown in Algorithm 1. In the population initialization stage, the IGA employs a cooperative initialization strategy (cf. Subsection 4.3) to generate the population of size $Ps$. In the population evolutionary stage, the crossover operation (cf. Subsection 4.4) and the mutation operation (cf. Subsection 4.5) are performed for the population. Subsequently, the population performs a repair strategy (cf. Subsection 4.6) to ensure that each individual is feasible. After that, the local search strategy (cf. Subsection 4.7) is utilized for the population. Moreover, the better individual is selected to update the population. Then, the global search strategy (cf. Subsection 4.8) is embedded to generate new individuals and replace individuals with long-term evolutionary stagnation. Finally, the evolution stops and the best individual is outputted when the stopping criterion is satisfied.

4.2.   Encoding and decoding

This study encodes each chromosome as a two-dimensional array, where the first dimension corresponds to all helicopters and the second dimension represents the assigned rescue sites for each helicopter. An example of the encoding is shown in Figure 1, where the sequence {0, 3, 6, 8, 10, 0} indicates that a helicopter starts at the rescue center and then visits rescue sites 3, 6, 8 and 10 before returning to the rescue center. The other two sequences, {0, 5, 1, 4, 7, 0} and {0, 2, 9, 0}, represent other routes. Notice that the selection of each rescue site in the constructed route must adhere to the constraints outlined in the H-VRPTW model.

In the decoding process, tasks are assigned to helicopters according to the first dimension of the two-dimensional array, and then each rescue site is processed according to the second dimension of the array. The travel distance of the helicopter to the rescue site is calculated in sequence according to the two-dimensional array sequence of the chromosome, and the objective value of the solution can be obtained.

4.3.   Initialization

A critical aspect of the algorithm is a population that exhibits a high degree of both solution quality and diversity. To solve the considered problem, three initialization rules are used to jointly generate the initial population. The three initialization rules are as follows: 1) a random distribution method; 2) a sorting assignment method using time windows; 3) a sorting assignment method based on rescue site distance. Assuming the population size is $Ps$, the initialization is specified as follows:

1) The $Ps-2$ individuals are generated via a random distribution method. First, randomly sequence all rescue sites. Then, for each rescue site, try to insert rescue sites into all of the current helicopters.

2) One individual is generated via the sorting assignment method by using a time window. First, each rescue site is sorted in ascending order according to the starting time window. Then, sequentially insert each rescue site into the current route at the position of minimum distance.

3) One individual is generated by using the sorting assignment method based on rescue site distance. First, calculate the distance between each rescue site and the rescue center. Second, arrange the rescue sites in ascending order of distance. Finally, sequentially insert each rescue site into the current route at the position of minimum distance.

The main steps of the cooperative initialization strategy are described in Algorithm 2.

4.4.   Crossover operation

Crossover operation is a crucial step in the GA as it enables the transfer of excellent genes from the parent generation to the offspring. A well-designed crossover operation based on chromosome structure is presented as follows:

Step 1: The current chromosome serves as the parent A; randomly select another chromosome as parent B.

Step 2: Randomly select one helicopter from parent B and insert it at the end position of a randomly selected helicopter from parent A. Remove any duplicate rescue sites to generate offspring 1.

Step 3: Randomly select one helicopter from parent A and insert it at the end position of a randomly selected helicopter from parent B. Remove any duplicate rescue sites to generate offspring 2.

Step 4: Compare the fitness of offspring 1 and offspring 2, and retain the superior offspring.

In the crossover operation, the fitness of two offspring is compared, and the one with higher fitness is preserved. This selection process ensures that individuals with superior fitness are retained within the population, allowing favorable individuals to be introduced into the next generation. This gradual evolution of the population, driven by the preservation of higher-fitness individuals, helps the algorithm converge towards the optimal individual as the iterations progress.

Figure 2 shows a schematic of the crossover operation; the rescue sites {6, 4, 7, 9} served by helicopter $H_2$ are selected from parent B and sequentially inserted behind the path of helicopter $H_3$ in parent A; then, a new solution offspring 1 is generated. Similarly, the rescue sites {5, 1, 4} served by helicopter $H_2$ from parent A are inserted sequentially after the path of helicopter $H_3$ in parent B, generating offspring 2. Finally, offspring 1 and offspring 2 are compared, and the superior offspring 1 is retained.

4.5.   Mutation operation

The mutation operation in the GA serves to imitate the mutation phenomenon of some genes on chromosomes in nature. The mutation operation can improve the situation of the GA falling into the local optimum to some extent, while keeping the diversity of the population. In this study, the swap mutation operator is adopted. First, randomly select two mutation operators from parent A, and then the two selected mutation operators are swapped to generate a new individual. Figure 3 provides a schematic of the mutation operator.

4.6.   Repair strategy

After crossover and mutation operations, certain rescue sites in the chromosome may violate the time window constraints. Hence, a repair strategy has been devised to guarantee the feasibility of each individual in the population. First, the rescue sites that violate the time window are removed. Then, for each rescue site that violates the time window, it is inserted into the current route at the position of minimum distance. Algorithm 3 shows the specific steps of the repair strategy.

Figure 4 illustrates the process of chromosome repair. In the figure, helicopter $H_3$ undergoes crossover and mutation operations, resulting in a modified path from {2, 6} to {2, 6, 4, 7}. However, it is observed that the arrival time of helicopter $H_3$ at rescue site {4} is T = 40, which falls outside of the specified service time window of ^[20,35]. Therefore, the rescue site {4} is excluded from the service path of helicopter $H_3$ and inserted at a position that satisfies the time window constraint and minimizes the distance. As a result, the revised service path for $H_3$ becomes {2, 6, 7}, while helicopter $H_1$ is assigned to service the rescue site {4}.

4.7.   Local search strategy

To enhance the exploitation ability of the IGA, a local search strategy based on an improved greedy insertion heuristic is incorporated. First, all rescue sites are placed into a set $R_s$ and the total number $n$ of rescue sites is calculated. Then, a rescue site is randomly selected from $R_s$ and added to the set $R_r$, which is then removed from $R_s$. Third, a rescue site $i$ is randomly selected from $R_r$, and for each rescue site $j$ in $R_s$, the distance between $i$ and $j$ is calculated. The set $R_s$ is then sorted based on the distances calculated, and the rescue site with the shortest distance is added to $R_r$ and removed from $R_s$. This process is repeated $n/10$ times. Fourth, the set $R_r$ is removed from the current solution. Finally, for each rescue site in the set $R_r$, it is inserted into the current route at the position of minimum distance. Algorithm 4 shows the specific steps of the local search strategy.

Figure 5 illustrates the local search approach. Initially, the rescue site {11} is selected from helicopter $H_2$ and added to the set $R_r$ for recording. Subsequently, the nearest rescue site {16} from the remaining unselected rescue sites is chosen and included in the set $R_r$. From the set $R_r$, one rescue site (in this case, {16}) is randomly selected, and then the nearest unselected rescue site {7} to {16} is identified and added to the set $R_r$. Finally, the removed rescue sites {11, 16, 17} in set $R_r$ are reinserted into current route at the position of minimum distance.

4.8.   Global search strategy

When an individual within the population fails to improve after multiple iterations, the individual is regarded as being trapped in local optima. In order to enhance the global search performance, and to avoid getting stuck in local optima, a global search strategy based on encoding structure destruction and construction is presented. First, randomly select $z$ helicopters from the current solution and record the set of rescue sites served by the helicopters in set $R_d$. Then, delete the $z$ helicopters from the current solution. Finally, for each rescue site $i$ in the set $R_d$, insert this rescue site into current route at the position of minimum distance. The steps of the global search strategy are shown in Algorithm 5.

Figure 6 illustrates a global search example. In the figure, the rescue sites {3, 8, 9} for helicopter $H_1$ and {5, 1, 4, 7} for helicopter $H_2$ are initially excluded from their respective routes. Subsequently, these rescue sites are individually reintroduced at positions that minimize the distance of the current route, generating new chromosomes.

4.9.   Complexity of the proposed algorithm

The complexity of the proposed algorithm primarily depends on the complexity of each operational step. In the initialization operation, each chromosome in the population is initialized, which has a complexity of $O(n^2)$. In the crossover operation, rescue paths are selected for crossover and duplicate rescue sites are removed. The complexity of the crossover operation is $O(n)$. In the mutation operation, two operators are randomly selected for swapping mutation, with a complexity of $O(1)$. For the repair strategy, each rescue site that violates the time windows constraint is inserted into the current route at the position of minimum distance, resulting in a complexity of $O(n^2)$. Similarly, the local search strategy involves inserting the removed rescue site into the current route at the position of minimum distance, resulting in a complexity of $O(n^2)$. The global search strategy entails inserting the removed rescues site into the current route at the position of minimum distance, with a complexity of $O(n^2)$. Considering all of these factors, the overall complexity of the proposed algorithm is determined to be $O(n^3)$.

5.   Experimental results

This section presents the experiments conducted to assess the effectiveness of the proposed algorithms. Firstly, the simulation instances of the H-VRPTW are described. Next, the simulation parameters used in the proposed algorithm were tested and selected. Then, the effectiveness of the local search strategy and the global search strategy in the proposed algorithm was respectively evaluated. Afterward, small instances were utilized to verify the performance of the proposed algorithm. Subsequently, the Solomon benchmark test was conducted to verify the effectiveness of the algorithm. Finally, the proposed algorithm was compared with other algorithms to assess its performance.

5.1.   Simulation instances

To better incorporate the system constraints, the simulation test design incorporates an extension of the canonical Solomon instances ^[42]. The extended instances comprise 56 instances, each of which contains 100 rescue sites. The geographical data used in these instances are similar to those used in the canonical Solomon instances, and include three types of instances: cluster instances, random instances and semi-cluster instances. The extended instances maintain consistency with the Solomon instances in terms of the coordinates of rescue sites, time windows, service times and material demands. The number of victims at each rescue site was randomly generated. All algorithms were evaluated by using a standardized termination criterion, with a maximum elapsed CPU time of 100 seconds. This consistent time duration ensures fairness and comparability in the evaluation process.

5.2.   Parameter selection

The experimental parameters consisted of the population size $Ps$, the crossover probability $Pc$, the mutation probability $Pm$ and the maximum number of iterations without improvement $Lm$. Table 1 presents the different values used for the four parameters. An orthogonal array $L_{16}$ was constructed using Taguchi's design of experiments method ^[43]. For each combination of experimental parameters, the proposed algorithm was executed 30 times independently to obtain the average fitness value, which was recorded as the response variable. The results of the experiments are presented in Table 2. Figure 7 presents the factor level trends of the four parameters. According to the results, the proposed algorithm achieves the best performance when $Ps$ is set to 100, $Pc$ is set to 0.3, $Pm$ is set to 0.3 and $Lm$ is set to 10.

5.3.   Efficiency of the local search strategy

To evaluate the effectiveness of the local search strategy, the IGA without an embedded local search strategy (IGA_NL) was designed to enable comparison with the IGA. The experimental results are presented in Table 3, which includes the name of the instance, the optimal values of the results obtained by the two algorithms, the experimental results for the two algorithms and the relative percentage increase (RPI). The RPI is given by Eq (12).

where $f_b$ represents the best solution found by all compared algorithms, and $f_c$ represents the best solution obtained by a given compared algorithm.

The results in Table 3 show that the IGA achieved 51 optimal solutions out of the 56 instances, while the IGA_NL only obtained five optimal solutions. The IGA obtained an average RPI value of 0.24, which is significantly lower than the average RPI value obtained by the IGA_NL. The results of analysis of variance (ANOVA) for the two different methods are shown in Figure 8. It can be concluded from Table 3 and Figure 8 that incorporating the local search strategy can significantly enhance the search ability of the algorithm.

5.4.   Efficiency of the global search strategy

To verify the effectiveness of the proposed global search strategy, the proposed IGA was compared with the IGA without the global search strategy (IGA_NG). The experimental results are shown in Table 4, where a total of 56 instances are considered. The IGA obtained the best solutions for 35 instances, while the IGA_NG obtained the best solutions for 21 instances. The superiority of the proposed global search strategy is further demonstrated by the RPI values in the last two columns. Figure 9 presents the ANOVA comparison between the two methods, confirming that the proposed global search strategy significantly improved the performance.

5.5.   Comparison of small instances

To further assess the feasibility of the IGA, the IBM ILOG CPLEX Optimization Studio solver was utilized to solve small instances; its performance was compared with the IGA. The small instances were generated by selecting a subset of rescue sites from the experimental instances, with the number of rescue sites ranging from four to 20. The name of each instance indicates the number of rescue sites it contains. For example, the instance labeled as "rs4" indicates that it consists of four rescue sites.

The experimental results, as shown in Table 5, demonstrate that CPLEX finds the optimal solution for several small instances. The proposed IGA also achieves the same solution values as CPLEX for instances with 4, 6, 8, 10, 14, 18, and 20 rescue sites. This confirms the feasibility of the proposed IGA approach for solving the VRPTW. Analyzing the results from the perspective of the RPI, it can be observed that the solutions obtained by the IGA exhibit a minor deviation from those obtained via CPLEX. The average RPI was merely 0.28, which demonstrates the effectiveness of the IGA.

5.6.   Solomon benchmark test

Previous studies often use classical benchmark datasets to test the performance of algorithms ^[44]. To validate the effectiveness and search capability of the proposed algorithm, it was compared with other well-known algorithms, including the TS ^[45], ACO ^[46], hybrid GA (HGA) ^[47], and SA ^[48]. The comparison was conducted using the widely recognized Solomon benchmark dataset, which is commonly used to evaluate vehicle routing algorithms. The obtained results were compared with the current international optimal values. In order to optimize the performance of the comparison algorithm, we meticulously fine-tuned its parameters; the outcomes for each parameter are presented in Table 6.

The Solomon benchmark dataset consists of various types of information, including vehicle capacity, customer coordinates, customer demand, time windows and service time. The geographic data in the Solomon instances can be categorized into three types: clustered instances labeled as "cl" and "c2", random instances labeled as "r1" and "r2" and semi-clustered instances labeled as "rc1" and "rc2".

The experimental results are presented in Table 7. Although a slight gap exists between the results obtained by using the IGA and the current international optimal values, this gap is relatively small in terms of the RPI, with an average RPI value of only 2.99. Moreover, the proposed algorithm exhibited significantly better performance compared to other algorithms, with an average RPI of 0.289, 0.080, 0.137 and 0.109 times that of the TS, ACO, HGA and SA algorithm, respectively. The ANOVA results presented in Figure 10 demonstrate that the proposed algorithm exhibits superior effectiveness and stability. The experimental results clearly demonstrate the competitive performance of the proposed IGA in terms of solving the VRPTW.

5.7.   Comparison of IGA with other algorithms

To evaluate the effectiveness of the IGA, the proposed algorithm was compared with the TS algorithm, ACO algorithm, HGA and SA. In the TS algorithm, the tabu list is an $N \times N$ matrix, where $N$ represents the number of customers. The tabu objects are vertex pairs ($j_1$, $j_2$) involved in the neighborhood operation, and their corresponding tabu lengths are stored in the tabu list. When a candidate solution ($S^{candi}$) corresponding to a vertex pair ($j_1$, $j_2$) is selected as the current solution ($S^{now}$) during the neighborhood operation, the corresponding tabu length is assigned to the matrix element ($j_1$, $j_2$). The tabu length is then decremented after each iteration until it reaches 0.

The experimental results are presented in Table 8, demonstrating that the IGA achieved superior solutions for 41 out of 56 instances, accounting for approximately 73.2% of the total instances. Notably, the average RPI of the IGA was only 1.28. Moreover, the proposed algorithm exhibited significantly better performance than the other algorithms, with an average RPI of 0.178, 0.027, 0.075 and 0.041 times those obtained via the TS, ACO, HGA, and SA algorithm, respectively. The effectiveness and stability of the proposed algorithm are found to be considerably higher than those of the other algorithms, as confirmed by the ANOVA results depicted in Figure 11. Furthermore, to illustrate the convergence ability of the algorithm when solving the H-VRPTW, Figure 12 displays the convergence curves for four selected instances: ac102, ac208, ar204 and arc106. These convergence curves clearly demonstrate the remarkable convergence ability of the IGA. In addition, Figure 13 shows the four charts of selected instances: ac106, ac201, ar108 and arc204, further affirming the effectiveness of the proposed algorithm in solving the H-VRPTW.

As the above experimental results and analysis show, the proposed IGA is an effective algorithm for solving the H-VRPTW. The reasons can be concluded as follows. First, a cooperative initialization strategy is employed to generate the population that possesses both high quality and diversity, enabling the IGA to explore a wide range of solutions effectively. Additionally, the incorporation of a local search strategy significantly enhances the exploitation capability of the IGA, leading to improved quality of the solution. Finally, the introduction of a global search strategy helps to prevent the solution from falling into local optima and improves the global search capability of the IGA. Based on the above analyses, the cooperative initialization strategy, the effective local search strategy and the global search strategy are reasons for the outstanding performance of the IGA.

5.8.   Theoretical implications and managerial insights

The effective optimization of the H-VRPTW considering the minimum flight distance of the helicopter improves the efficiency of post-disaster rescue and is of great significance for human safety. Therefore, this paper establishes a mathematical model of the H-VRPTW, considering load constraints, material demand, transportation of the wounded, time window constraints and travel distance. To solve the H-VRPTW, an effective IGA has been proposed; the IGA shows better convergence and optimization performance when solving the H-VRPTW. This study provides a new perspective from which disaster management officials can formulate more refined dispatching schemes, which has practical significance.

One managerial insight is that the research results of this paper have significant reference value for solving the helicopter dispatching problem in post-disaster rescue. Another managerial insight is that the helicopter dispatching scheme can effectively arrange rescue tasks for decision-makers and improve rescue efficiency. Finally, the proposed IGA is effective and applicable for solving dispatching schemes for helicopters in post-disaster rescue.

6.   Conclusions

In this study, the dispatching helicopters problem in post-disaster rescue is addressed. To solve this problem, a reasonable mathematical model of the H-VRPTW that considers the minimum flight distance of the helicopters is proposed, and an effective IGA has been designed to solve the H-VRPTW. In the IGA, a cooperative initialization strategy is included to generate the initial population. Subsequently, a local search strategy is presented to improve the exploitation ability. Furthermore, a global search strategy is embedded to enhance the global search performance. In the simulation experiments, the extended Solomon instances were used to verify the effectiveness of the proposed algorithm. The proposed algorithm was compared with four existing algorithms to assess its competitiveness. The experimental results show that the IGA yielded an average RPI value that was 0.178, 0.027, 0.075 and 0.041 times those of the TS algorithm, ACO algorithm, HGA and SA algorithm, respectively. The experimental results confirm that the proposed algorithm has higher competitive performance.

One limitation of this study is that the optimization objective was limited to consider the minimum flight distance of the helicopters, without considering other objectives, such as economic cost and energy consumption. To improve the research, a multi-objective dispatching model can be explored to optimize multiple objectives simultaneously in the post-disaster rescue. Another limitation is the lack of consideration for external environmental factors and emergencies, such as situations in which helicopters are unable to reach certain areas. To enhance the research, future studies can employ a dynamic programming approach to simulate the dispatching problem for the post-disaster rescue. Finally, the performance of the proposed algorithm needs further improvement. In future research, the proposed algorithm can be enhanced by combining it with other algorithms, such as the SA algorithm.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

This research was supported by the National Natural Science Foundation of China (52205529, 61803192), the Natural Science Foundation of Shandong Province (ZR2021QE195, ZR2021MD090, ZR2018BD008, ZR2016FL13), the Special Fund Plan for Local Science and Technology Development Lead by Central Authority and the Guangyue Youth Scholar Innovation Talent Program support received from Liaocheng University (LCUGYTD2022-03).

Conflict of interest

The authors declare that there is no conflict of interest.