# A Two-Stage Optimization Model for Airport Stand Allocation and Ground Support Vehicle Scheduling
## 5 The NSGA-II Algorithm Combining Local Search Strategies  
Genetic algorithm (GA) is a computational optimization technique inspired by the principles of biological evolution and natural selection. It mimics the genetic processes found in nature, such as reproduction, mutation, and crossover, to iteratively improve solutions to complex problems. Based on the traditional NSGA-II algorithm, we incorporate destruction and repair operations with a local search. After completing the crossover and mutation operations of the genetic algorithm, destruction and repair operations are used to adjust individuals within the population, ensuring that the algorithm can better explore optimal solutions while maintaining strong global search capabilities. Taking the stand allocation problem as an example, the modeling steps are explained as follows. (1) Chromosome encoding. An integer encoding method is adopted. The genes in the chromosome are sorted by the scheduled arrival time of flights. The numbers on the genes represent the stand number. Figure 4 shows a part of the chromosome. (2) Generate the initial population. An initial population is generated using a random constraint-satisfying method. The specific steps are as follows:  
Step 1: Select the first flight \(i,i\in F\) from the set of unallocated flights \(F\). According to the aircraft type of flight \(i\), we can obtain the set of compatible stands \(G_{i}\);  
Step 2: If there is a free stand \(g\), assign flight \(i\) to stand \(g\). Otherwise, traverse these stands and check if the time between the completion of the previous flight's service at the stand and the arrival time of the current flight meets the required time interval constraint. Add the stands that meet the constraint to the feasible stand set. Randomly select the smallest stand from the feasible set and assign the flight to this stand. If the feasible stand set is empty, traverse the set \(G_{i}\) and choose the stand that completes its task the earliest. (3) Evolve the population using the two-point crossover method and random mutation method to obtain offspring individuals. In the initial stage of the population, the crossover probability and mutation probability are set relatively high, while in the later stages of iteration, they should gradually decrease. The specific probability definition is shown in Equation (28). \[p_{i}=p_{max}-i\times\frac{p_{max}-p_{min}}{N} \tag{28}\]  
where \(i\) is the current iteration generation, \(p_{i}\) is the crossover/mutation probability for the current iteration, \(p_{max}\) and \(p_{min}\) are the initially set maximum and minimum values, respectively, and \(N\) is the population size. (4) Local search: First, apply the destroy method (function \(d(x)\)) to the current chromosome to randomly select flights for removal. Then, use the repair method (function \(r(x)\)) to creating a new solution. Destroy Method: select \(m\) flights to remove from the current solution \(X_{0}\) and add them to the removed flight set \(A\). The first flight in \(A\) will be the flight with the maximum delay from the current solution \(X_{0}\). The selection method for the remaining \(m-1\) flights is as follows: randomly select a flight from \(A\), then sort the remaining flights in \(X_{0}\) based on  
Figure 4: Chromosome encoding for stand allocation problem (example). their relevance to this selected flight to obtain the set \(X^{{}^{\prime}}\)[36]. The relevance calculation method is as Equations (29)-(30):  
\[R_{ij}=\frac{1}{d_{ij}^{\prime}+v_{ij}} \tag{29}\]  
\[d_{ij}^{\prime}=\frac{d_{ij}}{maxD} \tag{30}\]  
\[v_{ij}=\left\{ \begin{array}{c}1,\text{ Flights $i$ and $j$ are assigned to the same stand}\\ 0,\text{ {otherwise}}\end{array} \right. \tag{31}\]  
Equation (30) explains the method of standardizing \(d_{ij}\), where \(d_{ij}\) is the distance between flights \(i\) and \(j\), \(maxD\) represents the largest distance. The closer two flights are, the higher their correlation.