An Improved Adaptive Parallel Genetic Algorithm for the Airport Gate Assignment Problem

Abstract

Gate assignment problem (GAP) is the core issue of airport operation management. However, the limited resources of airport gates and the increase of flight scale result in serious problems for gate allocation. In this paper, to provide decision-making support for large-scale GAPs, a model based on gate assignment rules (e.g., flight type constraints, safe time interval constraints, and adjacency conflict constraints) is built to formulate the problem. An improved adaptive parallel genetic algorithm (APGA) is then designed to solve the model. The algorithm is effective because it introduces the idea of elite strategy and parallel design and can adaptively adjust the crossover probability. Moreover, different instances are presented to demonstrate the proposed algorithm. The calculation results of this algorithm are compared with those of standard genetic algorithm and CPLEX, which show that the proposed algorithm has better performance and takes a shorter computational time. In addition, we verify the stability and practicability of the algorithm by repeated experiments on large-scale flight data.

This work is licensed under http://creativecommons.org/licenses/by/4.0/ (the “License”). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.

1. Introduction

During the past twenty years, the number of flights in China has increased significantly. The limited resources of airports have gradually become a bottleneck that limits the development of the aviation industry. Therefore, how to dispatch various resources reasonably has become an intractable problem to be solved. Specifically, one of the most critical problems is gate assignment problem (GAP), which deals with the optimal assignment of flights to gates.

With the rapid growth of the number of flights, limited airport resources have been overwhelmed. Among them, the resource shortage of contact stands (an area adjacent to a terminal building where an aircraft can easily be loaded and unloaded) is particularly prominent. According to the International Air Transport Association (IATA) regulations, 90%–95% of all departing passengers should be boarded via jet bridges [1]. However, in China, only about 70–75% of all departing passengers board through the jet bridges. Therefore, in view of the current flight volume, airport contact stands are very scarce in China.

There are two traditional ways to solve the shortage of airport gate resources. First, directly increase the infrastructure and equipment resources, such as expanding the airport apron. However, the airport's infrastructure cannot be expanded indefinitely; moreover, the expansion of the airport and the investment in hardware equipment require a large amount of capital, time, manpower, land, etc., which are restricted by various factors. Second, optimize flight-gate allocation (i.e., improve the utilization efficiency of airport gates and reduce airport operation costs). At present, the gate assignment of large- and medium-sized airports in China mainly relies on manual allocation, supplemented by a computer system. However, in large hub airports, the flight takeoff and landing processes have the characteristics of short time and high density. According to statistics, more than 70% of all flight delays are caused by improper scheduling of airport resources; 15.45% of flight delays are caused by ground operation delays and departure delays [2]. The quality of gate assignment depends on the experience of operators, and it is difficult to ensure the optimal allocation of flights to gates. Moreover, manual allocation of airport gates contributes to low efficiency and high cost. With the development of airports, the complexity of GAP has increased exponentially. Therefore, an intelligent allocation method is urgently needed.

Based on the above problems, the contributions of this study are as follows. First, an optimization model is established for large-scale gate assignment problems, which comprehensively considers the factors of the remote stand penalty, the travel distance of passengers, and the fuel consumption of taxiing. The airport allocation personnel can adjust the weight of the corresponding objective according to their own preferences or the airport's allocation strategy so that the allocation plan is more in line with the actual allocation needs. Although there are some literatures that consider multiobjective optimization, there are few literatures considering these three aspects comprehensively. And the objective function of the model is quantified as a cost index, which is beneficial for the airport to compare and evaluate the allocation results from an economic point of view. Second, it is clearly noted that GAP is an NP-hard problem. Therefore, an improved adaptive parallel genetic algorithm is proposed to solve the model. The proposed algorithm fully considers how to obtain more initial feasible solutions. In the iterative process, the optimal solution is retained by using elite strategy, and the computational speed of the algorithm is accelerated by using parallel design. Moreover, a case study is presented to demonstrate the proposed algorithm. With the data from Kunming Changshui International Airport, the results of the proposed algorithm are compared with those of traditional genetic algorithm and CPLEX. It indicates that the computational time of the proposed algorithm is shorter than that of traditional genetic algorithm. And the proposed algorithm is still applicable when CPLEX cannot find the exact solution as the scale of the problem increases.

This paper is organized in the following manner. The literature review of GAPs is presented in Section 2. In Section 3, we formally define the problem and build an optimization model of gate assignment problem based on airport gate allocation rules. In Section 4, we propose an improved adaptive parallel genetic algorithm to solve the large-scale GAPs. Section 5 presents different instances to demonstrate and verify the effectiveness and practicability of the proposed algorithm, and Section 6 gives the conclusion.

2. Literature Review

In recent years, as taking off and landing sorties and passenger flows increase rapidly, to solve the shortage of airport gate resources, GAP has attracted a lot of attention. The methods for solving the GAP can be roughly divided into three categories: mathematical programming methods, computer simulation, and heuristic algorithms. The following is an overview of these three types of methods.

The first is the mathematical programming method. Babić et al. [3] solved the gate assignment model by branch and bound method to minimize the travel distance of passengers. Bihr [4] tried to convert the GAP to a 0-1 linear programming problem with the objective of minimizing passenger travel distance. Although the solution is ideal, it also provides some ideas for practical application in the dynamic airport environment. Yan and Huo [5] proposed a multiobjective model to help airport authorities solve the GAP efficiently and quickly. In order to verify the effectiveness of the model, they used the weighted method, column generation method, simplex method, and branch and bound method to solve the model with the actual data from Chiang Kai-Shek (CKS) Airport. Jaehn [6] considered a special case in which the largest flight/gate departure preference score is the only goal. He proposed a dynamic programming method and used actual data from a European airport to verify the effectiveness of the method. Maharjan and Matis [7] proposed a binary integer multicommodity flow network model to balance the transportation efficiency of shuttle bus and passenger satisfaction, which has been applied in Continental Airlines at George W. Bush Intercontinental Airport in Houston (IAH). Jiang et al. [8] proposed a gate assignment model to minimize the total passenger walking distance and balance the passenger walking distance between different routes. Yu et al. [9] converted the robust GAP to a mixed-integer programming problem, which mainly considers three factors: the robustness of flight schedules, facilities and personnel costs during towing, and passenger satisfaction. However, the number of flights to be allocated in the above literature is less than 50, which is far from the actual number of flights that airports need to allocate. When the number of flights that need to be allocated increases, the mathematical programming method often cannot obtain satisfactory results due to the sharp increase of the problem complexity.

The second common method is computer simulation. Baker [10] introduced a rule-based simulation system and evaluated the impact of different rules on gate utilization. Srihari and Muthukrishnan [11] introduced a knowledge-based expert system to GAPs and performed a sensitivity analysis. Cheng [12] proposed a knowledge-based airport gate assignment system to provide a solution that satisfied static and dynamic conditions in a reasonable computational time. Yan et al. [13] proposed a simulation framework, which analyzed the effects of random flight delays on static gate allocation and evaluated fuel consumption time. Finally, simulation experiments were performed at Chiang Kai-Shek airport to evaluate the effectiveness of the framework. Yan and Tang [14] integrated the disturbance of random factors on gate assignment into the framework. The framework includes three components, a random gate allocation model, a real-time allocation rule, and two penalty adjustment methods. However, computer simulation requires researchers to be proficient in computer programming. Moreover, due to the different influencing factors of each airport, it is difficult to directly migrate the simulation system designed for a specific airport to other airports. If migration is necessary, the simulation system needs to be redesigned, which leads to a high cost.

There are also various studies using heuristic methods to solve GAPs. Mangoubi and Mathaisel [15] used a greedy algorithm to find the initial feasible solution of the gate assignment model, the objective of which is to minimize the total travel distance of passengers. Ding et al. [16] studied the overconstrained GAP, intending to minimize the number of flights at remote stands and the total walking time of passengers. They proposed a hybrid algorithm of simulated annealing and tabu search to solve the model. Dorndorf et al. [17, 18] reviewed the development of the GAPs，and for disruption management in flight-gate scheduling, they proposed two methods to incorporate robustness into a flight-gate assignment problem. Dorndorf et al. [19] considered the general case in which an aircraft may be assigned to different gates. They presented a simple transformation of the flight-gate scheduling (FGS) problem to a graph problem, i.e., the clique partitioning problem (CPP). A heuristic based on the ejection chain algorithm by Dorndorf and Pesch [20] was designed to solve this model. They extended their model to minimize the deviations from a reference schedule. They proposed a heuristic with two variants, which iteratively solve subproblems in order to find a solution for the multiple period problem [21]. They also extended their model to focus on the stochastic objectives, which aim at minimizing the expected number of violations of any kind of constraints. An online decision support system was presented to propose recovery actions for resolving constraint violations. Finally, they compared this model to other approaches and different robustness measures based on real-life test data [22]. Şeker and Noyan [23] and Zhao and Cheng [24] considered that the uncertainty inherent in airport traffic might lead to the occupation of gates allocated to specific flights, which may cause flight conflicts and other problems. Therefore, they set up a mixed-integer programming model and introduced random factors into the model. Tabu search and ant colony algorithms were used to obtain a reasonable allocation scheme with better robustness. Liu et al. [25] proposed an optimization model considering operational security, the objective of which was to minimize the deviation of the gate idle time, and a genetic algorithm was used to solve the model. Dell’Orco et al. [26] proposed a new metaheuristic algorithm which was called fuzzy bee colony algorithm that combines bee colony algorithm and fuzzy inference system to minimize the total passenger travel time and the number of remote stands used. Deng et al. [27] proposed an improved adaptive particle swarm optimization algorithm, which takes full advantage of alpha stable distribution and dynamic score calculation. In order to stably escape the local minima and improve the global search ability, the alpha stable distribution theory is used instead of the uniform distribution. Yu et al. [28] designed an adaptive large neighborhood search algorithm (ALNS) to solve the gate assignment model considering traditional cost and robustness. Liu et al. [29] proposed an optimization model for the GAP considering operational safety constraints, the main objective of which is to minimize the dispersion of gate idle time periods. They adopted genetic algorithm to solve this model, and the effectiveness and efficiency of the algorithm were verified via an illustrative example. Mokhtarimousavi et al. [30] mathematically formulated GAP as a three-objective (total passenger walking distance, taxiway conflicts, and costs) problem, which was solved by NSGA-II. Xu and Cai [31] developed an improved GA considering structural properties to avoid GA’s prematurity. They compared the results of the proposed algorithm with those of CPLEX to illustrate the effectiveness of the algorithm. However, heuristic algorithms often cannot obtain optimal solutions, and the convergence speed is closely related to the design of the algorithm.

Although several works have investigated GAPs, few studies have given attention to large-scale GAP. GAP is a complex problem, which is affected by a variety of factors. In order to simplify the problem, various studies only considered the basic constraints and omitted some important constraints (e.g., aircraft type constraints, nation constraints, and adjacency conflict constraints), which cannot meet the actual requirements of airport authorities. Moreover, in the case study of most research works, the number of flights used is less than 50, which is far from the actual number of flights in airports. Therefore, this paper proposes an adaptive parallel genetic algorithm to solve the large-scale GAP. In the beginning, the algorithm increases the search speed to expand the search scope and decreases the search speed when it is close to the optimal solution to improve the accuracy of the solution. Then, on this basis, elite strategy and parallel design are introduced to further improve the accuracy and convergence speed. Finally, based on the data from Kunming Changshui International Airport, we present different instances to verify the stability and effectiveness of the algorithm.

3. Problem Formulation and Model Development

The process of airport gate allocation is restricted by various conditions. In this section, we first briefly introduce the basic prerequisites of the GAP. Then, we describe the model's objective function and constraints.

3.1. Basic Prerequisites

Due to the complexity of the practical problems, almost all gate assignment models need to meet certain preconditions. This paper studies the gate assignment model based on the following assumptions.

  Prerequisite 1: data information. The relevant data required for the gate assignment include the following:

(i) Flight Information. It includes the planned arrival and departure time of flights, the number of passengers, the aircraft type of the flight, etc.

(ii) Gate Information. It includes the topological structure of airport gates, the attributes of each gate (e.g., the type of gate, nation attributes, and default boarding gates), the utilization of current gates, etc.

(iii) Relevant Parameters of Gate Allocation. It includes the minimum safe time interval of the same gate, the restriction information of adjacent gates, etc.

  Prerequisite 2: gate assignment time window. In the actual operation of the airport, the takeoff and landing of a flight is a continuous and dynamic process. Considering the actual requirement of airports, we use the time window to divide the assignment task in the time dimension (i.e., the allocation of gates is optimal within the current time window). This article sets the length of time window to one day.

  Prerequisite 3: airport capacity. We assume that the airport's gate capacity can meet the requirements for gate allocation. That is, for a given flight and gate data, there is at least one feasible solution for the GAP.

3.2. Notations

Before setting up the model, we list the definitions of the parameters and variables to be used in the objective function and constraints, as shown below.

(i) Parameters

  $F$: set of flight pairs to be assigned each day, $F=\mathrm{1,2,3},\dots ,n_f$.

  $G$: set of airport gates, $G=\mathrm{1,2,3},\dots ,n_g$.

  $n_f$: total number of flight pairs to be allocated per day, $n_f=F$.

  $n_g$: number of airport gates, $n_g=G$.

  $f_i^{\text{type}}$: the type of aircraft for flight $i$, $i\in F$.

  $f_i^{\text{nation}}$: international and domestic attributes of flight $i$. If flight $i$ is a domestic flight, then $f_i^{\text{nation}}=1$; otherwise, $f_i^{\text{nation}}=0$, $i\in F$.

  $g_j^{\text{nation}}$: international and domestic attributes of gate j. If gate j is a domestic flight, then $g_j^{\text{nation}}=1$; otherwise, $g_j^{\text{nation}}=0$, $j\in G$.

  $g_j^{\text{type}}$: set of flight type that can be accommodated by gate j, $j\in G$.

  $p_i^a$: number of arriving passengers of arrival flight in flight pair $i$.

  $p_i^d$: number of departing passengers of departure flight in flight pair $i$.

  ${\text{ETA}}_i$: estimated arrival time of flight i, $i\in F$.

  ${\text{ETD}}_i$: estimated departure time of flight i, $i\in F$.

  $T_{\text{buffer}}$: minimum safe time interval of the same stand.

  $T_{\text{neighbor}}$: minimum safe time interval between aircraft sliding in and pushing out in adjacent aircraft stands.

  $g_j^{\text{bridge}}$: if there is a jet bridge in gate j, then $g_j^{\text{bridge}}=1$; otherwise, $g_j^{\text{bridge}}=0$, $j\in G$.

  $N_{jk}$: if gate j is adjacent to gate k, then $N_{jk}=1$; otherwise, $N_{jk}=0$, $j,k\in G,j\ne k$.

  $Q_{jk}$: if gate j and gate k are adjacent, then $Q_{jk}=1$; otherwise, $Q_{jk}=0$.

  $S_1$: according to ${\text{ETA}}_i$, ${\text{ETD}}_i$, and $T_{\text{buffer}}$, find the flights that will cause conflict when assigned to the same gate and then traverse all flights and save the result in the conflict dictionary $S_1$.

  $S_2$: according to ${\text{ETA}}_i$, ${\text{ETD}}_i$, and $T_{\text{neighbor}}$, find the flights that will cause conflict when assigned to adjacent gates and then traverse all flights and save the result in the conflict dictionary $S_2$.

  $s_p$: average travel speed of passengers.

  $s_f$: average taxi speed of the aircraft.

  $d_j^a$: passenger travel distance from gate $j$ to baggage claim area, $j\in G$.

  $d_j^d$: passenger travel distance from check-in counter to gate $j$, $j\in G$.

  $D_j$: average distance from the landing runway to the gate $j$, $j\in G$.

  ${\text{fuel}}_i$: fuel consumption per taxi unit time of flight $i$ (fuel consumption is related to the type of flight $i$).

  $C_1$: unit penalty cost of a flight parked at a remote stand.

  $C_2$: unit travel time cost of passengers.

  $C_3$: unit cost of aircraft fuel.

(ii) Decision variables

The decision variable $x_{ij}=1$ if and only if flight i is assigned to gate j; otherwise, $x_{ij}=0$.

Given the decision variable $x_{ij}$, the solution of the gate assignment problem could be transformed as a 0-1 binary matrix, as shown in Table 1. A row of the matrix represents a gate, a column of the matrix represents a flight, and the elements in the matrix denote the values of the decision variables.

Table 1

The solution form of the gate assignment problem.

Gate	Flight
	1	2	3	…	$n_f$
1	0	1	0	…	0
2	0	0	1		0
3	1	0	0		0
…	…
$n_g$	0	0	0		1

3.3. Objective Functions

From the actual operation of airport gate assignment, the assignment process involves the interests of many parties. In this paper, we mainly consider three objectives, including the penalty cost of remote stands, the travel time cost of passengers, and the fuel consumption cost of taxiing [17, 32]:

(i) Generally, when an aircraft is parked at a remote stand, it is necessary to coordinate ground service personnel, apron vehicles, platform lift trucks, passenger elevator vehicles, etc. When the aircraft is parked at a contact stand, it only needs a jet bridge. The use of the jet bridge is very convenient for aircraft, crews, and passengers. There is a ground well near the bridge, which is convenient for refueling. It can also save the APU and fuel consumption of the aircraft, and the passengers and crews do not have to struggle. Based on a flight, according to the type of aircraft, the number of passengers, the time of use, and the related costs of supporting equipment, it is estimated that the aircraft needs at least 400–455 yuan to stop at the remote stand and only 200–300 yuan to stop at the contact stand. Therefore, based on such considerations, we will impose penalties on flights allocated to remote stands, as shown in equation (1).

(ii) Whether for inbound or outbound flights, the convenience and speed of boarding or baggage retrieval is one of the important indicators for passengers to measure the airport service level. Therefore, in order to improve passengers' satisfaction with airport services, airports should assign flights to the nearby stands to reduce passenger travel distance as far as possible. As shown in equation (2), since there are no data of transit passengers, we do not consider the travel distance of transit passengers here.

(iii) As the aviation transport industry is a capital-intensive industry with an average profit margin of only 3%∼6%, reducing production costs is of great significance for maintaining the survival and development of enterprises. The cost of aircraft fuel usually accounts for about 30% of all operating costs of airlines. In recent years, due to the continuous rise of international oil prices, airlines are facing increasing pressure on fuel consumption costs year by year. Therefore, reducing fuel consumption as much as possible and saving transportation costs have always been the issues that airlines are most concerned about and strive to solve. In the GAPs, the selection of gates directly determines the ground taxiing distance of the aircraft from the quick exit to the parking gate, which determines the ground taxiing cost of the aircraft. Therefore, the gate assignment scheme has a direct impact on the ground taxiing cost of aircrafts.

Considering the processing of the follow-up algorithm and the different preferences of different personnel, we make a weighted summation of these three objectives. As shown in equation (4), ${\alpha }_1$, ${\alpha }_2$, and ${\alpha }_3$ are the preference coefficients of allocation personnel, which are used to indicate the importance of different objectives.$$\begin{array}{}\text{(1)}& \min Z_1=C_1{\displaystyle \sum _{j=1}^{n_g}{\displaystyle \sum _{i=1}^{n_f}{x}_{ij}1-g_j^{\text{bridge}}}},\text{(2)}& \min Z_2=C_2\frac{{\displaystyle {\sum }_{j=1}^{n_g}{\displaystyle {\sum }_{i=1}^{n_f}{x}_{ij}{p}_i^a{d}_j^a+x_{ij}{p}_i^d{d}_j^d}}}{s_p},\text{(3)}& \min Z_3=C_3\frac{{\displaystyle {\sum }_{j=1}^{n_g}{\displaystyle {\sum }_{i=1}^{n_f}{x}_{ij}{\text{fuel}}_i{D}_j}}}{s_f},\text{(4)}& \min Z={\alpha }_1{Z}_1+{\alpha }_2{Z}_2+{\alpha }_3{Z}_3.\end{array}$$

3.4. Constraints

Due to the differences in airport positioning, service area, and scheduling rules, there are certain differences in the constraints of different airports. However, there are a lot of allocation rules that almost all airports need to follow when allocating gates, only slightly different in specific details. According to the actual business rules of large hub airports, the aircraft stand allocation model has the following constraints:

(i) Uniqueness constraint: an aircraft must and can only park at one stand.

$$\begin{array}{}\text{(5)}& {\displaystyle \sum _{j=1}^{n_g}{x}_{ij}}=1,\hspace{1em}\forall i\in F.\end{array}$$

(ii) Conflict constraint of the same gate: there shall be a safe time interval between two consecutive aircraft assigned to the same gate to guarantee the safe departure of the former aircraft and the safe entry of the latter.

$$\begin{array}{}\text{(6)}& x_{ij}+x_{lj}\le 1,\hspace{1em}\forall i,l\in S_1,\forall j\in G.\end{array}$$

(iii) Conflict constraint of adjacent gates: the aircraft parked on the adjacent aircraft stand cannot enter and leave the aircraft stand at the same time. There should be a certain time interval when the aircraft slides in and out.

$$\begin{array}{}\text{(7)}& x_{ij}+x_{lk}\le 1,\hspace{1em}\forall i,l\in S_2,\forall Q_{jk}=1.\end{array}$$

(iv) Aircraft type restriction: large aircraft stands can park all types of aircraft, while small aircraft stands can only park corresponding small aircraft.

$$\begin{array}{}\text{(8)}& f_i^{\text{type}}\in g_j^{\text{type}},\hspace{1em}\forall x_{ij}=1,\forall i\in F,\forall j\in G.\end{array}$$

(v) International and domestic attribute constraints: as flights are divided into international flights and domestic flights, gates are also divided into corresponding attributes. According to the relevant regulations of the airport, international flights can only park in international gates, while domestic flights need to stop in domestic gates.

$$\begin{array}{}\text{(9)}& f_i^{\text{nation}}=g_j^{\text{nation}},\hspace{1em}\forall x_{ij}=1,\forall i\in F,\forall j\in G.\end{array}$$

4. Design of Improved Adaptive Parallel Genetic Algorithm

The model established in this paper is a mixed-integer programming model, and the large-scale GAP involves hundreds of flights, which is difficult to be solved by the traditional optimization algorithm in polynomial time. Therefore, we consider using the genetic algorithm to solve the model. Through an in-depth analysis of the model, the traditional genetic algorithm is improved in this section. We design an improved adaptive parallel genetic algorithm (APGA) that considers global and local search capabilities.

4.1. Encoding Approach

Chromosomes are encoded by digital code. In order to explain the encoding mode of chromosomes better, sample data are used for illustration. Sort the flight pair data according to the estimated departure time, as shown in Table 2.

Table 2

Flight pair information sorted by estimated departure time.

Paired flight no.	Flight no.	Estimated time of arrival	Estimated time of departure	Aircraft type
0	B1378	00:00	00:10	C
1	B2835	00:00	00:15	C
2	B6832	00:05	01:10	C
3	XU997	01:15	2:15	C
4	9MAGD	01:25	02:30	D
5	HSCBA	02:00	02:55	C
6	B7992	00:00	06:20	C
…	…	…	…	…

Each flight pair is then assigned to a gate, as shown in Table 3. Gate no. in the table is only used to explain the design of chromosome encoding and does not represent the actual allocation.

Table 3

An example of flight pair assignment.

Paired flight no.	Gate no.
0	0
1	2
2	6
3	4
4	7
5	3
6	4
…	…

According to the above encoding principles, the chromosome encoding sequence is shown in Figure 1. The length of the chromosome is the number of flights, that is, the length of the chromosome is determined by the number of paired flights. The gene loci on the chromosome represent the flights to be assigned, and the numbers on the loci indicate the gate no. For example, paired flight no. 0 is assigned to gate no. 0; paired flight no. 1 is allocated to gate no. 2, and so on.

[figure omitted; refer to PDF]

From the experimental results of CPLEX, it can be seen that the traditional mathematical programming method is not suitable for more than 120 flights. Compared with heuristic methods, the time consumption cost is too high, and as the scale of the problem increases, the result cannot be obtained. In order to further verify that the APGA algorithm is applicable to large-scale GAPs and to demonstrate the stability of the algorithm for different datasets with the same number of flights, we randomly generated 10 different flight datasets from the flight data on November 23, 2019, and each set of data contains 200 flights. We determined that the number of contact stands for testing is 40, and the number of remote stands is 38. We conducted five repeated experiments on different datasets to reduce the influence of random factors.

The results of repeated tests of different instances are shown in Table 14. The first column of the table indicates the serial number of instances, and the column “Repeated experiments” are the results of 5 repeated experiments. The corresponding result value of each experiment is the value of the objective function $Z$, and the specific calculation process is shown in equation (4). The remaining columns are statistical indicators of repeated experimental results, mainly including maximum, mean, minimum, standard deviation, and coefficient of variation. By observing the maximum, minimum, and standard deviation in the table, we can find that for different datasets, the final objective function values are basically between 46000 and 47500, and the standard deviations are all below 1000. Further analysis of CV (coefficient of variation) shows that for datasets with different mean values, the CV values are all below 0.21%, which indicates that the algorithm can maintain high stability. It shows that in the case of large-scale GAPs, the proposed algorithm can not only reduce computation time but also have high stability and practicability.

Table 14

Results of repeated experiments.

Instances	Repeated experiments					Min	Mean	Max	Standard deviation	Coefficient of variation (%)
	1	2	3	4	5
1	473368	472216	471553	471016	473011	471016	472233	473368	979.45	0.21
2	467090	469041	468431	467084	467486	467084	467826	469041	873.23	0.19
3	466083	467888	466372	466732	466804	466083	466776	467888	686.06	0.15
4	467818	466947	465739	467786	467005	465739	467059	467818	845.94	0.18
5	466347	467341	465296	467755	466343	465296	466616	467755	963.36	0.21
6	469341	468463	468388	467527	469455	467527	468635	469455	788.84	0.17
7	463768	462837	464477	463782	463544	462837	463682	464477	587.90	0.13
8	472016	473555	472281	472936	471434	471434	472444	473555	822.53	0.17
9	461351	460935	460981	461921	462282	460935	461494	462282	591.48	0.13
10	464262	462783	463428	464093	463054	462783	463524	464262	641.79	0.14

6. Conclusions

Based on the analysis of the research status of GAPs, we propose a gate assignment model based on the actual assignment rules of airports, which comprehensively considers the factors of the remote stand penalty, the travel distance of passengers, and the fuel consumption of taxiing. First, we formulate actual allocation rules into model constraints, such as flight type constraints, safe time interval constraints, nation constraints, adjacency conflict constraints, and so on. Next, an improved adaptive parallel genetic algorithm is proposed to solve the large-scale GAPs. Then, we generate different sample datasets from the real data of Kunming Changshui International Airport. The calculation results of the proposed algorithm are compared with those of standard genetic algorithm and CPLEX, which show that the proposed algorithm has better performance and takes a shorter computational time. In addition, we repeat tests on a large dataset of 200 flights to show the stability and practicability of the algorithm. Moreover, even if the size of the GAP becomes larger and the required iteration cannot be completed within the required time, we can also stop the algorithm and obtain an approximate solution.

Notably, compared with the actual process of gate assignment, the factors considered in the model are relatively simplified, and only the factors that are critical in the actual process are considered. This paper assumes that the capacity of the airport can meet the requirements of gate allocation. However, during the peak hours of airport operation, airport resources are tight, and there may not be an allocation result that allows all flights to be assigned. The algorithm still wants to allocate all flights, so it cannot get a feasible solution. Therefore, built upon the proposed algorithm, new assignment strategies will be introduced in future research.

Acknowledgments

This research was sponsored by the Key Laboratory of Airport Cluster Intelligent Operation of China (KLAGIO20180801).

References

[1] E. Piazza, "Increasing airport efficiency: injecting new technology," IEEE Intelligent Systems, vol. 17 no. 3, pp. 10-13, DOI: 10.1109/mis.2002.1005625, 2002.

[2] Z. Ma, D. Cui, "Optimizing airport flight delays," Journal-Tsinghua University, vol. 44 no. 4, pp. 474-477, 2004.

[3] O. Babić, D. Teodorović, V. Tošić, "Aircraft stand assignment to minimize walking," Journal of Transportation Engineering, vol. 110 no. 1, pp. 55-66, DOI: 10.1061/(ASCE)0733-947X(1984)110:1(55), 1984.

[4] R. A. Bihr, "A conceptual solution to the aircraft gate assignment problem using 0, 1 linear programming," Computers & Industrial Engineering, vol. 19 no. 1–4, pp. 280-284, DOI: 10.1016/0360-8352(90)90122-3, 1990.

[5] S. Yan, C.-M. Huo, "Optimization of multiple objective gate assignments," Transportation Research Part A: Policy and Practice, vol. 35 no. 5, pp. 413-432, DOI: 10.1016/s0965-8564(99)00065-8, 2001.

[6] F. Jaehn, "Solving the flight gate assignment problem using dynamic programming," Zeitschrift für Betriebswirtschaft, vol. 80 no. 10, pp. 1027-1039, DOI: 10.1007/s11573-010-0396-9, 2010.

[7] B. Maharjan, T. I. Matis, "Multi-commodity flow network model of the flight gate assignment problem," Computers & Industrial Engineering, vol. 63 no. 4, pp. 1135-1144, DOI: 10.1016/j.cie.2012.06.020, 2012.

[8] Y. Jiang, L. Zeng, Y. Luo, "Multiobjective gate assignment based on passenger walking distance and fairness," Mathematical Problems in Engineering, vol. 2013,DOI: 10.1155/2013/361031, 2013.

[9] C. Yu, D. Zhang, H. Y. K. Lau, "MIP-based heuristics for solving robust gate assignment problems," Computers & Industrial Engineering, vol. 93, pp. 171-191, DOI: 10.1016/j.cie.2015.12.013, 2016.

[10] V. J. Baker, "Pitching a tent in the native village; Malinowski and participant observation," Journal of the Humanities and Social Sciences of Southeast Asia, vol. 143 no. 1, pp. 14-24, DOI: 10.1163/22134379-90003339, 1987.

[11] K. Srihari, R. Muthukrishnan, "An expert system methodology for aircraft-gate assignment," Computers & Industrial Engineering, vol. 21 no. 1–4, pp. 101-105, DOI: 10.1016/0360-8352(91)90071-d, 1991.

[12] Y. Cheng, "A knowledge-based airport gate assignment system integrated with mathematical programming," Computers & Industrial Engineering, vol. 32 no. 4, pp. 837-852, DOI: 10.1016/s0360-8352(97)00001-6, 1997.

[13] S. Yan, C.-Y. Shieh, M. Chen, "A simulation framework for evaluating airport gate assignments," Transportation Research Part A: Policy and Practice, vol. 36 no. 10, pp. 885-898, DOI: 10.1016/s0965-8564(01)00045-3, 2002.

[14] S. Yan, C.-H. Tang, "A heuristic approach for airport gate assignments for stochastic flight delays," European Journal of Operational Research, vol. 180 no. 2, pp. 547-567, DOI: 10.1016/j.ejor.2006.05.002, 2007.

[15] R. S. Mangoubi, D. F. X. Mathaisel, "Optimizing gate assignments at airport terminals," Transportation Science, vol. 19 no. 2, pp. 173-188, DOI: 10.1287/trsc.19.2.173, 1985.

[16] H. Ding, A. Lim, B. Rodrigues, Y. Zhu, "The over-constrained airport gate assignment problem," Computers & Operations Research, vol. 32 no. 7, pp. 1867-1880, DOI: 10.1016/j.cor.2003.12.003, 2005.

[17] U. Dorndorf, A. Drexl, Y. Nikulin, E. Pesch, "Flight gate scheduling: state-of-the-art and recent developments," Omega, vol. 35 no. 3, pp. 326-334, DOI: 10.1016/j.omega.2005.07.001, 2007.

[18] U. Dorndorf, F. Jaehn, C. Lin, H. Ma, E. Pesch, "Disruption management in flight gate scheduling," Statistica Neerlandica, vol. 61 no. 1, pp. 92-114, DOI: 10.1111/j.1467-9574.2007.00361.x, 2007.

[19] U. Dorndorf, F. Jaehn, E. Pesch, "Modelling robust flight-gate scheduling as a clique partitioning problem," Transportation Science, vol. 42 no. 3, pp. 292-301, DOI: 10.1287/trsc.1070.0211, 2008.

[20] U. Dorndorf, E. Pesch, "Fast clustering algorithms," ORSA Journal on Computing, vol. 6 no. 2, pp. 141-153, DOI: 10.1287/ijoc.6.2.141, 1994.

[21] U. Dorndorf, F. Jaehn, E. Pesch, "Flight gate scheduling with respect to a reference schedule," Annals of Operations Research, vol. 194 no. 1, pp. 177-187, DOI: 10.1007/s10479-010-0809-8, 2012.

[22] U. Dorndorf, F. Jaehn, E. Pesch, "Flight gate assignment and recovery strategies with stochastic arrival and departure times," OR Spectrum, vol. 39 no. 1, pp. 65-93, DOI: 10.1007/s00291-016-0443-1, 2017.

[23] M. Şeker, N. Noyan, "Stochastic optimization models for the airport gate assignment problem," Transportation Research Part E: Logistics and Transportation Review, vol. 48 no. 2, pp. 438-459, DOI: 10.1016/j.tre.2011.10.008, 2012.

[24] H. Zhao, L. Cheng, "Ant colony algorithm and simulation for robust airport gate assignment," Mathematical Problems in Engineering, vol. 2014,DOI: 10.1155/2014/804310, 2014.

[25] S. Liu, W. Chen, J. Liu, "Optimizing airport gate assignment with operational safety constraints," pp. 61-66, DOI: 10.1109/IConAC.2014.6935461, .

[26] M. Dell’Orco, M. Marinelli, M. G. Altieri, "Solving the gate assignment problem through the fuzzy bee colony optimization," Transportation Research Part C: Emerging Technologies, vol. 80, pp. 424-438, DOI: 10.1016/j.trc.2017.03.019, 2017.

[27] W. Deng, H. Zhao, X. Yang, J. Xiong, M. Sun, B. Li, "Study on an improved adaptive PSO algorithm for solving multi-objective gate assignment," Applied Soft Computing, vol. 59, pp. 288-302, DOI: 10.1016/j.asoc.2017.06.004, 2017.

[28] C. Yu, D. Zhang, H. Y. K. Lau, "An adaptive large neighborhood search heuristic for solving a robust gate assignment problem," Expert Systems with Applications, vol. 84, pp. 143-154, DOI: 10.1016/j.eswa.2017.04.050, 2017.

[29] S. Liu, W.-H. Chen, J. Liu, "Robust assignment of airport gates with operational safety constraints," International Journal of Automation and Computing, vol. 13 no. 1, pp. 31-41, DOI: 10.1007/s11633-015-0914-x, 2016.

[30] S. Mokhtarimousavi, D. Talebi, H. Asgari, "A non-dominated sorting genetic algorithm approach for optimization of multi-objective airport gate assignment problem," Transportation Research Record: Journal of the Transportation Research Board, vol. 2672 no. 23, pp. 59-70, DOI: 10.1177/0361198118781386, 2018.

[31] R. Xu, K. Cai, "Solving airport gate assignment problem using an improved genetic algorithm with dynamic topology," Recent Developments in Intelligent Computing, Communication and Devices, vol. 752, pp. 877-884, DOI: 10.1007/978-981-10-8944-2_102, 2019.

[32] J. Xiong, C. Zhang, "Airport gate assignment with airplane taxiing cost analysis," Journal of Transportation Systems Engineering and Information Technology, vol. 10 no. 3, pp. 165-170, DOI: 10.1016/s1570-6672(09)60069-6, 2010.

[33] D. E. Goldberg, J. H. Holland, "Genetic algorithms and machine learning," Machine Learning, vol. 3, pp. 95-99, DOI: 10.1023/A:1022602019183, 1988.

[34] K. A. de Jong, "“Analysis of the behavior of a class of genetic adaptive systems”," 1975. Ph.D. thesis

[35] I. Kucukkoc, A. D. Karaoglan, R. Yaman, "Using response surface design to determine the optimal parameters of genetic algorithm and a case study," International Journal of Production Research, vol. 51 no. 17, pp. 5039-5054, DOI: 10.1080/00207543.2013.784411, 2013.

[36] Y. L. Wang, C. F. Wang, "Aircraft stands pre-assignment based on passenger traffic characteristics and cross entropy," Journal of Transportation Systems Engineering and Information Technology, vol. 16 no. 4, pp. 211-216, 2016.