Research on Airport Gate Allocation Problem Based on NSGA-II Algorithm

Abstract

The Airport Gate Allocation Problem (AGAP) is a key problem in the daily operation of modern air transport industry. In view of the situation that the passenger flow of an airline in the existing terminal T of an airport has reached the saturation state, in order to cope with the future development, a satellite Hall s is added. On the basis of the goal of maximizing flight allocation and relieving passenger transfer tension, the overall planning and allocation of all boarding gates of T and s are carried out. To solve this problem, this paper constructs a multi-objective constraint model. In this paper, NSGA-II algorithm is selected as the solution algorithm. In order to speed up the convergence speed of the algorithm, a set of initial solutions is generated by using the matching algorithm based on first come first served. Finally, the TOPSIS method is used to select the compromise solution which satisfies the decision makers from a set of Pareto fronts obtained by NSGA-II algorithm. This paper uses the data provided by the competition to carry out the experiment, and analyzes and displays the results of the experiment.

1 Introduction

With the economic globalization and the rapid increase of global transportation, the demand for air transportation is also growing rapidly. Airport gate allocation problem (AGAP) plays a more and more important role in the daily operation of modern air transport industry. AGAP mainly studies the airport gate to gate allocation [1]. With the rapid increase of global traffic, the demand for air transport is also growing rapidly, so airports are increasingly facing the pressure of transport capacity [2]. However, it is a very time-consuming process to expand the airport capacity by planning and constructing new terminals, which can’t relieve the pressure of transport capacity in a short period of time. Therefore, airport operators or terminal operators must make more effective use of limited gate to ensure the safety and smooth operation of the airport. Optimizing airport operations requires all airport partners to communicate as a team. Gate assignment is a key activity and most other ground operations are then performed based on its results [3]. The task of airport gate marking is to allocate a set of flights from different airlines to a fixed number of gates. Unreasonable allocation may lead to flight delay, low customer satisfaction, unbalanced gate utilization, ground congestion and aircraft push back or taxiing conflicts [4]. The problem of flight gate assignment needs to be solved and optimized.

According to the situation that the passenger flow of an airline in the existing terminal T of an airport has reached the saturation state, in order to cope with the future development, the satellite Hall s is added. Although the introduction of satellite hall alleviates the pressure of insufficient boarding gate in the original terminal, it has a certain negative impact on the flight connection of transfer passengers. This paper establishes a mathematical model of this problem, optimizes the allocation of boarding gate, analyzes the transfer tension of transfer passengers, and provides reference for the adjustment of airline flight planning.

2 Problem Analysis and Modeling

2.1 Problem Description

AGAP can be described as matching n aircrafts with n gates. At the same time, it needs to meet the goals of maximizing flight allocation, minimizing the use of gate, minimizing the transfer time of tourists and transfer tension. The solution space of this problem is [69]^319, which belongs to NP-hard problem, which can’t be solved by traditional mathematical programming method. Therefore, in this experiment, we seek an intelligent optimization algorithm to comprehensively consider the quality of the results and the controllable running time (see Table 1).

Table 1. Symbol description

2.2 Constraint Analysis

Based on the coding of aircraft and gate, gate x_i is assigned to aircraft i. Some rules need to be considered: they are transformed into symbolic mathematical expressions as follows (1)–(9):

$$ x{}_{i} \in \left\{ {0,1, \ldots \left| M \right|} \right\}\quad \quad \quad \quad \forall i \in N $$

(1)

$$ x{}_{i} \in \left\{ {1,2, \ldots \left| M \right|} \right\}\quad \quad {\text{if}}\quad i \in I $$

(2)

$$ U_{i} - V_{xi} = 0 $$

(3)

$$ \left| {PA_{{\text{i}}} - GA_{xi} } \right| \le 1 $$

(4)

$$ \left| {PD_{{\text{i}}} - GD_{xi} } \right| \le 1 $$

(5)

$$ x_{i} \ne x_{j} \quad \quad {\text{if}}\quad \left( {D_{j} - A_{i} } \right)\left( {D_{i} - A_{j} } \right) > 0 $$

(6)

$$ A_{j} - D_{i} \ge 45\quad \quad {\text{if}}\quad Z_{ij} = 1 $$

(7)

Constraint (1) means that the aircraft i either stops at fixed gate x_i (x_i ∈ {1,2,… |M|}),or stop at the temporary gate, then the corresponding gate number x_i = 0; constraint (2) indicates that aircraft i belongs to the important flight set I marked with asterisk, which must be assigned to fixed gate; constraint (3) (4) (5) each gate and each aircraft have domestic/international, arrival/departure, wide body aircraft/narrow body aircraft and other functional attributes, the aircraft can only be assigned to the gate corresponding to its attributes. Constraint (3) represents the flight width attribute U_i of aircraft i, its fixed choice of gate x_i can accommodate flight width attribute $V_{{x_{i} }}$ to be consistent, constraint (4) denotes the domestic/international attribute PA_i of the arriving aircraft i. which must be included by the arrival types $GA_{{x_{i} }}$ that gate x_i can accommodate. due to the domestic/international nature of the aircraft PA_i either domestic or foreign codes correspond to −1 and 1 respectively, but the attributes of domestic/international flights at the gate $GA_{{x_{i} }}$ QUOTE may be domestic or foreign, or both, corresponding to −1,1,0.Therefore, inequality is used, such as domestic arrival aircraft (−1) can choose the type of boarding gate, domestic arrival (−1) or domestic and foreign arrival (0), which can be expressed as the absolute value of the coding distance corresponding to the two is less than 1; constraint (5) refers to the domestic/international constraint of flight arrival, same as constraint (4); constraint (6) indicates that there can only be one flight at a boarding gate at the same time. That is to say, when the time of aircraft i and aircraft j to the departure period of occupying the gate coincides, they will not be assigned to the same gate, that is, x_i ≠ x_i; Constraint (7) indicates that the time interval between aircraft i and j (i before j) allocated at the same gate is greater than or equal to 45 minutes, that is, the arrival time A_j of j must be at 45 minutes after departure time D_i of i [5].

2.3 Objective Function Analysis

2.3.1 Objective 1: Maximize Flight Gate Allocation

Allocate as many aircraft as possible to the appropriate gate, and on this basis, minimize the number of gates used. It does not need to meet the constraints of arrival/departure time of domestic aircraft, but only needs to consider the arrival/departure time of domestic aircraft. The objectives can be expressed as (8) and (9), that is maximizing the number of flights scheduled to the fixed gate and minimizing the number of gates used. The priority order of the former is higher than that of the latter.

$$ \max \sum\limits_{i = 1}^{N} {F_{i} } $$

(8)

$$ \min \sum\limits_{k = 1}^{\left| M \right|} {P_{k} } $$

(9)

In Eq. (8), F_i = 1 if x_i ≠ 0, i.e. when aircraft I is assigned a fixed gate instead of a temporary gate, F_i = 1; in Eq. (9), P_k = 1 if ∃i ∈ N, x_i = k, that is, as long as there is an aircraft using gate k, then P_k = 1.

2.3.2 Objective 2: Consider the Shortest Process Time of Transit Passengers

Considering that the flight is arranged in different terminal halls, when the passengers arriving or departing by this flight transfer, they need different transfer time in different positions of different terminal halls to another organization. On the basis of the two objectives in question 1, another objective (10) is added, that is, to minimize the total process time of transit passengers. However, the priority order is: maximize the number of flights arranged to the fixed gate > minimize the total process time of transit passengers > minimize the number of gates used.

$$ \min \sum\limits_{i = 1}^{N} {\sum\limits_{j = 1}^{N} {\left\{ {f_{ij} T_{{PA_{i} PD_{{\text{j}}} {\text{x}}_{{\text{i}}} {\text{x}}_{{\text{j}}} }} F_{{\text{i}}} F_{{\text{j}}} {\text{ + f}}_{{{\text{ij}}}} {*}360{*}\left( {1 - F_{{\text{i}}} F_{{\text{j}}} } \right)} \right\}} } $$

(10)

3 Model Solution

3.1 NSGA-II Algorithm Flow

Since problem herein is a constrained multi-objective optimization problem, and each object constrains each other, there is no solution to ensure all objectives reaching the optimal results for such problems. And hence the solution set to such constrained multi-objective optimization problems is a Pareto solution set, a set of non-inferior solutions. Currently multi-objective genetic algorithm (MOGA) is one of the most common algorithms for analyzing and solving multi-objective optimization problems. MOGA’s core is to coordinate the relations among each objective and seek an optimal solution with a best possible result for all objectives. Among numerous MOGAs, non-dominated sorting genetic algorithm II (NSGA-II) is the most influential and most widely applied. This paper adopts NSGA-II as the solution. Figure 1 is the TOPSIS algorithm flow.

According to algorithm flow and understanding of NSGA-II, the steps of the algorithm are as follows:

Step 1: Define parameters such as iterations, population size, crossover probability and mutation probability, and set counter as 0;

Step 2: The initial population is generated randomly, and the selection bits of all kinds of ships can be integer coded.

Step 3: The population is ranked non-inferiorly. According to the objective function and constraint function, each individual is given a value of rank and crowding distance. Then, the binary tournament selection operation is carried out for the population;

Step 4: Crossover and mutation operation.

Step 5: The temporary population is evaluated. The temporary population is composed of the current population M and the offspring population N generated by cross mutation. By comparing the individual rank and crowding distance, the non-inferior ranking of the temporary population is generated;

Step 6: Create a new population. Through the evaluation of the temporary population in step 5, a certain optimal individual is selected to form a new population;

Step 7: Judge whether the specified number of iterations has been reached. If the specified number of iterations has been reached, output the optimal solution. Otherwise, add 1 to the counter and go to step 3 to continue.

Fig. 1.

NSGA II algorithm

3.2 TOPSIS Method Flow

Since NSGA-II algorithm generates a set of Pareto frontiers, how to select the relative optimal solution from the feasible solutions becomes the final problem to be solved. This paper adopts a common evaluation and decision-making method in the field of decision-making – TOPSIS [7], which is a is a multi-criteria decision analysis method proposed by C. L. Hwang and K. Yoon in 1981. It is a method of ranking the objects to be evaluated by comparing their proximity to the idealized objectives, and the importance of the goal can be measured and presented by setting the weight matrix of the goal. Therefore, such method is very suitable for the problem herein.

The main steps of TOPSIS are as follows:

Step 1: Establish a normalized decision matrix A.

Step 2: Establish weighted and standardized decision matrix R. r_ij = x_ij × q_j, q_j is the weighted value of the object of No. j.

Step 3: Define positive and negative ideal solutions $f_{j}^{ + } ,f_{j}^{ - }$;

Step 4: Calculate the Euclidean distance between feasible solution and positive and negative ideal solutions;

Step 5: Calculate relative closeness of feasible solution to ideal solution. Finally, according to the degree of relative closeness, rank the order from high to low. The solution with the highest relative closeness is the optimal solution in Pareto solution set.

4 Application Examples

4.1 Application Scenario

(1). Airport layout: The layout design of Terminal (T) and Satellite hall (S) is shown in Fig. 3. T has all the functions for an international airport terminal, including departure, arrival, entry and exit and waiting hall. Satellite hall S is an extension of Terminal T, with a waiting hall but no entry and exit function.

There is a tram line connecting T and S, through which international and domestic passengers can be ferried between T and S rapidly. It is assumed that passengers can be transported to each point without waiting, and each trip costs 8 min. Terminal T has 28 boarding gates, and S has 41 gates. The configurations of each gate meet the required regulations (see Fig. 2).

Fig. 2.

Airport layout

(2). Gate assignment: Boarding gates are fixed stands and equipped with corresponding equipment to enable various technical operations when aircrafts are docked. Aircraft-gate assignment requires consideration on the following rules:

• (a) Make overall planning on the assignment of all gates in T and S;

• (b) The functional attributes of each fate, such as domestic/international, arrival/departure, and wide body aircraft/narrow body aircraft, are assigned in advance and cannot be changed. The flights in the aircraft ferrying plan can only be assigned to the gates that match their attributes;

• (c) The arrival and departure flights of each ferrying aircraft must be assigned to the same gate, and cannot be moved to elsewhere;

• (d) The time interval between two aircrafts assigned to the same gate must be greater than or equal to 45 min;

• (e) The airport also has ad-hoc gates for aircraft that cannot be assigned to a fixed gate. It is assumed that there is no limit to the number of ad-hoc gate.

(3). Passenger flow: The passenger flow can be classified for standardization according to the departure passengers, terminal passengers and transit passengers. However, since a newly-added satellite hall has little impact on departure and arrival passengers, it is not included in the scope of this study. The flow of transit passengers from the arrival of the previous flight to the departure of the next flight is composed of 16 different scenarios based on permutation and combination of domestic (D) and international (I), terminal (T) and satellite hall (S). The shortest flow time and number of rides by MRT of such scenarios are given in the table below. The first number of each grid is the shortest flow time (minutes), and the second number is the number of rides by MRT. Riding time on MRT and passenger’s walking time are not included in the shortest flow time (see Table 2).

Table 2. Passenger flow time and number of MRT rides

4.2 Result Analysis

4.2.1 Result Analysis of Object 1

After data preprocessing, gates are needed to be assigned to a total number of 319 aircrafts, among which 52 are wide body aircraft and 267 are narrow body aircraft. According to the statistics of the results, 52 wide body aircrafts and 214 narrow body aircrafts were successfully assigned. The successful assignment ratio for wide body is 1, namely all wide body crafts are successfully assigned; the narrow body crafts have a successful assignment ratio of 0.8015. After analysis, due to fewer number of wide body aircraft, gates are sufficient to accommodate them, resulting in all wide body aircrafts being assigned. But since the number of narrow body aircrafts is big, and hence number of gates is insufficient relatively, resulting time conflict when assigning narrow body crafts and a relatively lower successful ratio. But the ratio still reaches 80% and is regarded as relatively optimal results, and hence verifies the advantage of the algorithm and model of the paper (see Table 3).

Table 3. Number and ratio of aircraft allocated in wide-body and narrow-body aircraft

According to the input data, there are 69 gates in total, including 28 gates in terminal T and 41 gates in satellite hall S. Because it is indicated that priority should be given to the assignment of flights, the weights of the two objective functions of maximizing the assignment of flights and minimizing the use of boarding gates are set as 0.6 and 0.4 respectively. The following table is resulted from the experiment, that is, a total number of 67 gates are used, of which all the gates in the terminal are used, and there are two gates in the satellite hall left unoccupied. In addition, the average utilization rate of the boarding gate is calculated in Table 4. The average utilization rate of the boarding gate of terminal T is 55.27%, which is higher than the utilization rate of the satellite hall, 63.19%. After multiple experiments, it can be concluded that if the weight of minimizing the gate is increased, the average utilization rate of the gate can be increased.

Table 4. The number and utilization of gates in terminals and satellite halls

4.2.2 Result Analysis of Object 2

According to the question design, the goal of maximizing the flight assignment is higher than minimizing the transfer time of passengers, which is higher than minimizing the gate utilization. Therefore, in this experiment, the weights of the three objectives are set to 0.5, 0.3, 0.2 respectively, and the following experimental results are obtained.

Since maximizing the assignment of flights has always been the most important goal, the results have maintained a high consistency during the experiment. From Table 5, we can see that the number of wide body aircrafts that are successfully assigned is 52, with a success rate of 1; while the number of successfully assigned narrow body aircraft is 213, with a success rate of 0.7978. Compared with object 1, the success rate is slightly lower, because the minimization of tourists’ transfer time is considered.

Table 5. Number and ratio of aircraft successfully allocated in wide and narrow body aircraft

Through the analysis of the optimal solution obtained in this experiment, it can be concluded that the number of unoccupied gates is 3, including 1 unoccupied gate in terminal T, and 2 unoccupied gates in satellite hall. Further analysis shows that the average utilization rate of the boarding gate in the terminal is 0.6021, and that in the satellite hall is 0.6133. The result is relatively better than the experimental result of the problem, because the weight of minimizing utilization of gates is increased in the weight setting of the experiment, and hence the performance of such objective in the optimal solution is improved (see Table 6).

Table 6. Number and utilization of gates in terminals and satellite halls

Statistical analysis of the data shows that the total number of arriving or departing passengers on the 20th day is 2833, of which the number of successfully transferred passengers is 2018, and the number of unsuccessfully transferred passengers is 815. Further analysis of the data shows that the reason for unsuccessful passenger transfer is that the aircraft of arriving or departing passenger is assigned to an ad-hoc gate. The passengers on the aircrafts that are successfully assigned to fixed gates are successfully transferred (see Table 7).

Table 7: Ratio of transfer success to failure

In this experiment, if the passenger's flight is assigned to an ad-hoc gate, then the passenger’s transfer time will be set to 6 h as a penalty for transfer failure. According to the analysis on the statistics of passenger’s transfer time, the proportion of passengers with a transfer time over 90 min is 28.77%, with a total number of 815 people, and all of the long transfer time are caused by assigning the passenger's aircrafts to ad-hoc gates. Apart from the above exceptions, the transfer time of passengers shows an approximately normal distribution, that is, the transfer time of passengers is concentrated in the range from 50 min to 70 min, and the proportion of transfer time greater than or less than this range is small.

Further analysis of the data can get the transfer tension of the passengers. Among the successful passengers, the transfer tension also presents an approximate normal distribution. 38.51% of the passengers’ transfer tension is between 20% and 40%. It can be seen that the transfer time of the passengers is not tight and there is enough time for them to transfer.

Fig. 3.

Passenger transfer time distribution and tension distribution

5 Conclusion

Based on the analysis of the impact of newly added satellite halls on passengers, this paper abstracts such as the problem of flight gate assignment. On the premise of satisfying the constraints, the four objectives – maximizing flight assignment, minimizing gate utilization, minimizing passenger transfer time and minimizing passenger transfer urgency – are optimized simultaneously, and then the flight gate assignment problem is abstracted into a multi-objective constrained optimization problem. In this paper, NSGA-II algorithm is then selected as the solution algorithm. In order to speed up the convergence rate of the algorithm, a group of initial solutions are generated based on the “first come, first served” matching algorithm, which can greatly improve the accuracy and convergence rate of the algorithm. Finally, TOPSIS method is used to select the relative optimal solution from a group of feasible solutions obtained from NSGA-II algorithm.