Multi-objective gate assignment based on robustness in hub airports

Abstract

To enhance the robustness of the gate assignment, reduce the possibility of flight conflict, and improve the quality of passenger services, a multi-objective gate assignment model is proposed by minimizing flight conflict probability and number of flights assigned to aprons. The biogeography-based optimization algorithm is used to solve the proposed model with a new method for estimating the conflict probability. The simulation results show that the ratio of interval time of two flights assigned to the same gate between 60 and 120 min is as high as 82% when the rate of the flights assigned to aprons is controlled below 0.4. This means that the robustness increases greatly, and the probability of flight conflicts decreases, which is beneficial to the implement of flight assignment plan. In addition, the biogeography-based optimization algorithm is more effective to solve the proposed model and very easy to find out the optimal solutions.

Keywords

Gate assignment aircraft robustness biogeography-based optimization hub airport

Introduction

With the rapid growth of civil aviation transportation in China, air traffic has increased dramatically, resulting in the increase in flight delays and congestion.^1,2 The actual departure or arrival time of aircraft is uncertain due to the increase in flights. At present, most China airports adopt pre-established gate assignment. Each aircraft is assigned to the corresponding gate according to the expected arrival or departure time ahead. But the pre-established gate assignment schedule often cannot match with the need due to the influence of uncertain factors such as weather or traffic flow. Gate assignment is becoming more and more complicated.

One of the most important uncertain factors is the random delay of aircraft through the statistics of many pre-established gate assignment schedule.³ The random delay of aircraft may decrease the robustness of gate assignment and increase the transit time of flights. Robustness of gate assignment is to ensure minimal interference in pre-established gate assignment, considering the influence of uncertain factors, under the precondition of aircraft safety. The main goal of the ground movement problem is to minimize the time spent by the aircraft during their ground movements.⁴ Therefore, how to improve the robustness of gate assignment and decrease the transit time under uncertain factors have become the hot spot of ground resources operation in hub airport.

The rest of this article is organized as follows. Section “Review” presents a review of the gate assignment problem (GAP). Section “Model development” presents a multi-objective gate assignment model with taking the robustness of schedule into account. Section “Gate assignment optimization simulation based on BBO” presents the biogeography-based optimization (BBO) algorithm to solve the multi-objective optimization model. The numerical results are reported in section “Numerical,” and the conclusions are presented in section “Conclusion.”

Review

Scholars in the world have carried out extensive research on how to optimize the gate assignment schedule to improve the efficiency of airport ground resource, and they have obtained many research results. In this article, the models and simulation of gate assignment are summarized, respectively.

Some scholars established single-objective gate assignment models to minimize the walking distance of passengers,^5,6 the sliding distance of flights,^7,8 or the leisure time of gates.⁹ However, some scholars established multi-objective models to optimize the gate assignment. P Kumar et al.¹⁰ considered different conflicting objectives such as maximization of gate rest time between two turns, minimization of towing an aircraft with a long turn, and minimization of overall cost. U Dorndorf et al.¹¹ established a model to maximize the total assignment preference score, to minimize the number of unassigned flights during overload periods, to minimize the number of tows, and to maximize a robustness measure. HK Sang et al.¹² proposed a model to minimize weighted nominal taxi time and weighted taxi delay, as well as passenger transit time in the terminal. Y Jiang et al. established a model according to the problems of airport passenger service quality. A gate assignment model is based on minimizing the total walking distance of all passengers and balancing the average walking distance of passengers among different airlines.¹³ KV Prem et al.¹⁴ introduced new additional objectives to gate assignment that have not been studied in the literature, including maximization of passenger connection revenues, minimization of zone usage costs, and maximization of gate plan robustness. KC Chong et al. took two kinds of considerations into account. One is passenger walking distance from arrival gate to departure gate, and the other is the transport baggage distance from one gate to another. The objective was to minimize the total distance between the gates related to assign the arrival plane to the suitable gates.¹⁵

Some scholars also proposed optimization methods or intelligent algorithms to solve the GAP. MG Hakk et al. proposed a method that combined the benefits of heuristic approach with some stochastic approach instead of using a purely probabilistic approach to top-down solution of the GAP. The proposed method generates an assignment order for the whole planes that corresponds to assignment priority.¹⁶ Y Pi et al. developed a novel airport gate assignment problem (AGAP) model. The greedy randomized adaptive search procedures (GRASP) have strong intuitive greedy appeals, prominent empirical track records, and trivial to be efficiently implemented on parallel processors. More importantly, GRASP can overcome the precocity. Experimental results demonstrate that the GRASP algorithm on AGAP evidently exceeds GA algorithms on the quality of solutions and time complexity.¹⁷ CH Yu et al. built a mathematical model to show the relationship among three factors impacting on the gate assignment: robustness, tows, and passenger transfer distance. An artificial intelligence-based hybrid meta-heuristic algorithm was designed to solve this problem.¹⁸ O Aoun et al. adopted the original algorithm based on Markov decision process (MDP) to solve the GAP under uncertainty and introduced some stochastic parameters that depend on probabilities to express fluctuations in flight operations. The MDP provided a robust solution for the GAP.¹⁹ YH Wang et al.²⁰ built a mixed set programming method to build a data and logical model of gate assignment and developed efficient search strategies to achieve global optimal solution. KC Chong et al. proposed a model to minimize the total distance between the gates that are related to assign the arrival plane to the suitable gates. An integer linear programming (ILP) model was built to solve the GAP.²¹ M Marinelli et al. proposed a meta-heuristic approximation approach, namely, simulated annealing to solve the GAP. The results suggested that the decreasing number of un-gated flights occurred with the implementation of the proposed method.²² M Marinelli et al. proposed a hybrid approach called biogeography-based bee colony optimization (B-BCO). This approach is obtained fusing two meta-heuristics: BBO and bee colony optimization (BCO) algorithms. The proposed B-BCO model integrates the BBO migration operator into the bee’s search behavior.²³

The multi-objective models are built to solve the GAP. The heuristic algorithm is often combined with other algorithms to solve these models. These articles are mostly concerned about travelers and airports, while the robustness of gate assignment schedule should also be taken into consideration. Many scholars also established models to improve the robustness of gate assignment. A Lim and Wang²⁴ established a stochastic plan model by determining an evaluation function that had nothing to do with the real arrival or departure times of flights. BC Smith et al. established a gate assignment model from the perspective of different models. It required the same type of flights to be assigned to the same gates as possible as it could, so the robustness could be improved.²⁵ Dumas et al.²⁶ established a gate assignment model from the network effect to reduce the scale of gates assignment. G Diepen et al. established a cost function to evaluate the spare time between two consecutive flights assigned to the same gate. They improved the robustness of gate assignment by minimizing the total cost.²⁷ SW Yang et al. designed an improved gray model (GM) (1, 1) model to predict the arrival time or departure time of flights. And on the basis of this, the gate is assigned beforehand to improve the robustness.²⁸ L Xu et al. regarded the GAP as a stochastic binary integer programming problem. Flights were divided into different uncertain sets. Robust solution was to ensure that gate assignment was flexible to uncertain arrival or departure time of flights in the sets.²⁹ U Dorndorf et al.¹¹ established a model to minimize the unassigned flights during the overload period to maximize the robustness. JH Li et al. introduced different probability distributions of flight delay and established robust gate assignment model to minimum conflict probability. And the greedy tabu search algorithm was designed to solve the model.³⁰ H Zhao and Cheng³¹ put forward a mixed-integer model to find the more robust solve for gate assignment model and designed ant colony algorithm. XT Wang et al.³² converted the gate assignment into selection of corresponding gate type and established mathematical model to increase the robustness of gate assignment. ME Narciso et al. put forward an experimental method to assess the minimum number of gates required by arrival or departure flights under limited delay. And they analyzed shortcomings and benefits on different strategies.³³

To sum up, researches on gate assignment robustness mainly focused on the balance among free time of gates and the decrease on the number of unassigned flights. The robustness of gate assignment is mainly reflected in the conflict probability between two consecutive flights assigned to the same gate, so this article adopts a new way to estimate conflict probability between two flights. The gate assignment plan is optimized by minimizing the conflict probability, and the number of flights assigned to aprons is controlled minimum as the other object. The BBO algorithm is used to simulate the model. The results show that the cost is saved and the utilization rate of gates is improved. These two objects are combined to find a new way to improve the robustness of gate assignment.

Model development

Assumptions

According to the operation requirement of hub airports and air traffic management, some assumptions for gate assignment model development are proposed as follows. (1) The gate assignment is a continuous operation process. So the article selects all the arrival–departure flights in a certain period to engage in research. (2) The capacity of airport can meet the demand of flights within the research period, each aircraft can be assigned to a gate, including gates and aprons, and the aprons are always available for flights. (3) When an aircraft performs the arrival and departure flight at the same time, it is defined as flight pair. The flight pair needs to be assigned to the same gate and has a same flight number. (4) All the information of flights within the research period, including flight schedule plan, aircraft basic information, gate information, is known.

Notation

The indices, parameters, and variables used in the model are defined as follows:

F: flight set $F = {f_{1}, f_{2}, \dots, f_{m}}$ , m is the total quantity of flights within the research period, and $f_{i} (1 \leq i \leq m)$ is the flight number which is ordered by the flight schedule. The bigger i is, the later flight $f_{i}$ arrives at the airport;

$c_{f_{i}}$ : type of the aircraft which executes flight $f_{i}$ . The bigger $c_{f_{i}}$ is, the larger aircraft is;

G: gate set, $G = {g_{1}, g_{2}, \dots, g_{n}}$ , n is the quantity of gates, $g_{k} (1 \leq k \leq n)$ is the gate number

X_{g_{k}} = {\begin{matrix} 1, gate g_{k} is a gate \\ 0, gate g_{k} is an apron \end{matrix}

$c_{g_{k}}$ : type of gate $g_{k}$ . the bigger $c_{g_{k}}$ is, the larger the gate is;

$a_{f_{i}}$ : schedule arrival time of flight $f_{i}$ ;

$d_{f_{i}}$ : schedule departure time of flight $f_{i}$ ;

$a'_{f_{i}}$ : actual arrival time of flight $f_{i}$ ;

$d'_{f_{i}}$ : actual departure time of flight $f_{i}$ ;

t: buffer time interval of two connected flights which are assigned to the same gate. The actual service time interval for flight $f_{i}$ in the gate is $[a'_{f_{i}} - t, d'_{f_{i}} + t]$

y_{f_{i}, g_{k}} = {\begin{matrix} 1, if flight f_{i} is assigned to gate g_{k} \\ 0, otherwise \end{matrix}

z_{f_{i}, f_{j}} = {\begin{matrix} 1, if flight f_{i} and f_{j} are assigned to the same gate \\ 0, otherwise \end{matrix}

Model

The robustness of schedule is taken into account to study the gate assignment in hub airport in China, and the utilization of aprons is also considered, which is related to the operation cost. The presented gate assignment optimization model is a bi-objective model.

According to the flight schedule, the arrival time $a_{f_{i}}$ and departure time $d_{f_{i}}$ for flight $f_{i}$ are known. Obviously, the longer interval time between flight $f_{i}$ and the later flight $f_{j}$ is, the less probability conflict occurred. Therefore, the gate assignment objective function (1) is established on the basis of minimizing flight conflict probability

min Z_{1} = \sum_{f_{i}, f_{j} \in F, i < j} (z_{f_{i}, f_{j}} \times P (f_{i}, f_{j}))

(1)

where $z_{f_{i}, f_{j}}$ is used to judge whether flight $f_{i}$ and flight $f_{j}$ are assigned to the same gate, and $P (f_{i}, f_{j})$ represents the flight conflict probability function. $P (f_{i}, f_{j})$ is related to $e (f_{i}, f_{j})$ , which is explained in section “A new way to estimate $P (f_{i}, f_{j})$ .” According to objective function (1), the more gates or aprons the airport constructs, the less probability the conflict occurs.

For both airports and airlines, it is important to improve the proportion of passengers embarking/disembarking through aerobridge (referring to passing rate) to decrease the operation cost. Thus, the gate assignment objective function (2) is established on the basis of minimizing the number of flights assigned to aprons

min Z_{2} = \frac{\sum_{f_{i} \in F} \sum_{g_{k} \in G, X_{g_{k}} = 0} y_{f_{i}, g_{k}}}{\sum_{f_{i} \in F} f_{i}}

(2)

where $\sum_{f_{i} \in F} \sum_{g_{k} \in G, X_{g_{k}} = 0} y_{f_{i}, g_{k}}$ indicates the quantity of flights assigned to aprons, while $| \sum_{f_{i} \in F} f_{i} |$ indicates the total flight number within the research period.

The model of gate assignment can be established as follows

min Z_{1} = \sum_{f_{i}, f_{j} \in F, i < j} (z_{f_{i}, f_{j}} \times P (f_{i}, f_{j}))

(3)

min Z_{2} = \frac{\sum_{f_{i} \in F} \sum_{g_{k} \in G, X_{g_{k}} = 0} y_{f_{i}, g_{k}}}{\sum_{f_{i} \in F} f_{i}}

(4)

Subject to

z_{f_{i}, f_{j}} = \sum_{f_{j} \in F j > i} \sum_{f_{i} \in F} \sum_{g_{k} \in G, X_{g_{k}} = 1} (y_{f_{i}, g_{k}} \times y_{f_{j}, g_{k}})

(5)

\sum_{g_{k} \in G} y_{f_{i}, g_{k}} = 1, \forall f_{i} \in F

(6)

y_{f_{i}, g_{k}} \in {0, 1}

(7)

y_{f_{i}, g_{k}} \times y_{f_{j}, g_{k}} \times (d_{f_{i}} - a_{f_{j}}) \times (d_{f_{j}} - a_{f_{i}}) \leq 0

(8)

c_{f_{i}} \leq c_{g_{k}} + (1 - y_{f_{i}, g_{k}}) M

(9)

i, j, k, x \in Z^{+}

(10)

Equation (5) is used to judge whether flight $f_{i}$ and flight $f_{j}$ are assigned to the same gate.

Equations (6) and (7) indicate that each flight has only one gate to be assigned. Therefore, for the flight $f_{i}$ , there is only one gate $g_{k}$ to achieve $y_{f_{i}, g_{k}} = 1$ in the gate set G.

Equation (8) indicates that two flights cannot be arranged to the same gate at the same time. When $y_{f_{i}, g_{k}} \times y_{f_{j}, g_{k}} = 0$ , two flights are not assigned to the same gate. When $y_{f_{i}, g_{k}} \times y_{f_{j}, g_{k}} = 1$ , flight $f_{i}$ and flight $f_{j}$ are assigned to the same gate. $a_{f_{i}} < d_{f_{i}}$ and $a_{f_{j}} < d_{f_{j}}$ are constant valid, so one value of $(d_{f_{i}} - a_{f_{j}}) and (d_{f_{j}} - a_{f_{i}})$ must be zero, or one is positive and the other is negative. This can avoid the conflict of two flights.

Equation (9) means that the gate type should match the aircraft type. When $y_{f_{i}, g_{k}} = 1$ , flight $f_{i}$ is assigned to gate $g_{k}$ , and it should meet $c_{f_{i}} \leq c_{g_{k}}$ . When $y_{f_{i}, g_{k}} = 0$ , there is no relationship between flight $f_{i}$ and gate $g_{k}$ .

Equation (10) is a positive integer constraint.

Gate assignment optimization simulation based on BBO

A heuristic BBO algorithm is adopted to simulate and solve the gate assignment optimization model. The BBO algorithm is a new intelligent optimization algorithm, which has better search efficiency than the previous intelligent optimization algorithms. The BBO algorithm was originally proposed in the study by Simon³⁴ which is based on the mathematical models of biogeography. In principle, there are two main operators in BBO, that is, migration and mutation. Before optimizing, each individual of population is evaluated and then follows migration and mutation step to reach global minima.

Encoding way

In the simulation process, the arrival–departure flights within the study period and the gates at the airport are encoded to form the real number code.

Generating initial solution

The gate assignment is a multiple-objective constraint problem. In this article, the initial solution is generated by generating the roulette to improve efficiency. The gate is assigned to the flight randomly. So, the initial solution usually does not meet the constraints.

Designing habitat suitability index

The individual in the BBO algorithm corresponds to the nature habitat. Habitat suitability index (HSI) is used to measure the quality of the individual in the nature habitat and regard it as a reference to rank the individual. Object functions $z_{1}$ and $z_{2}$ can be considered in the HSI. The two object functions are added to the object function Z as a constraint to form a new objective function as follows

Z = Z_{1} + η Z_{2}

(11)

where $η$ is the conversion factor of estimate value. According to the study by Simon (2008), $η$ is a random value between 0 and 0.5, it is more efficient to optimize the model when it equals 0.1. So, set $η = 0.1$ .

Then, the HSI function can be expressed as follows

f_{HSI} = \frac{M}{Z}

(12)

where M is a large real number, so $f_{HSI}$ can avoid to be too small.

The operation of BBO algorithm

Migration and mutation operation are included in the operation of BBO algorithm. Migration operation includes emigration and immigration. Species with high HSI have high emigration and low immigration rate. Species with poor HSI is opposite. Mutation operation is used to enhance the diversity of individual in the habits. Both of them can change the HSI. After the migration and mutation operations, the coding sequence may not satisfy the constraints any more. Therefore, the feasibility of the coding sequence needs to be tested. Then, update the individuals and continue to proceed with the iteration. Finally, the optimal solution to satisfy the constraint is selected. The process of BBO is shown in Figure 1.

Figure 1.

Gate assignment model process based on the BBO algorithm.

The BBO algorithm process mainly includes two operations, the migration and the mutation, whose operation procedures are shown as follows. Given hypothesis that the number of habitats is d, and characteristic vector of habitat individual i corresponds to a candidate solution set $X_{i} = (X_{i 1}, X_{i 2}, \dots, X_{in}), i = 1, 2, \dots, d$ , where $X_{in}$ corresponds to the suitability index variables (SIVs) of individual species in each habitant.

Migration operation

According to the principle of BBO, species with better HSI have high emigration rate and low immigration rate. Species with poor HSI is opposite. The migration operation includes the immigration and emigration operation and can change the HSI. Rank the individual according to the HSI. The immigration rate $μ_{s}$ and emigration rate $λ_{s}$ satisfy formula (13)

{\begin{matrix} μ_{s} = \frac{q + 1 - s}{q + 1} \\ λ_{s} = 1 - μ_{s} \end{matrix}, s = (0, 1, 2, \dots, q)

(13)

where q indicates the maximum number of species, s indicates the number of species for inhabitat individual. The number of species can be determined by the HSI. In this article, the maximum number of species is equal to the number of habitat individual, and the habitat individual can be arrayed by HSI. The species number of individual habitat, whose HSI is maximum, is d. The species number of individual habitat i is $d - i$ . $λ_{d - i}$ is used to select the species element of individual i and adopt $μ_{d - i}$ to select specie element $X_{i' k}$ from other individual $i'$ to replace $X_{ik}$ . The procedure of migration is shown in Table 1.

Table 1.

The procedure of migration.

Procedure Habitat migration
Begin
for $i = 1 to d$
Select $X_{ik}$ with probability based on $λ_{d - i}$
If $rand (0, 1) < λ_{d - i}$ then
for $i' = 1 to d$
Select $X_{i' k}$ with probability based on $μ_{d - i}$
If $rand (0, 1) < μ_{d - i}$ then
Replace a random SIV $X_{ik}$ with $X_{i' k}$
End if
End for
End if
End for
End

Mutation operation

Mutation operation is used to enhance the diversity of individual in the habitats and change the habitat suitability values. Mutation probability is small. This article adopts a simple mutation manner. Each iteration selects species elements $X_{ik}$ of individual habitats i with the smaller mutation probability $P_{m}$ . Selecting species element $X_{ik}$ needs to mutate and be replaced by random species elements. The procedure of mutation is shown in Table 2.

Table 2.

The procedure of mutation.

Procedure mutation
Begin
for $i = 1 to d$
Compute the probability $P_{m}$
select SIV $X_{ik}$ with probability based on $P_{m}$
Replace $X_{ik}$ with a randomly generated SIV
End for
End

Numerical

The data for simulation

The data for simulation are the real operation data from a hub airport in China. There are total 61 groups of flight data to be used to simulate the model. The selected flights are waiting to be allocated to gates during 8:00–15:00.The flight data include flight number, type of aircraft, arrival time, and departure time, as shown in Table 3.

Table 3.

The flight data during 8:00–15:00 from a huge airport in China.

Flight number	Arrival time	Departure time	Type of aircraft	Flight number	Arrival time	Departure time	Type of aircraft
F001	8:00	9:05	L	F031	11:00	12:00	M
F002	8:00	9:10	M	F032	11:00	12:10	M
F003	8:00	9:10	L	F033	11:05	12:10	L
F004	8:05	9:15	L	F034	11:05	12:15	M
F005	8:20	9:20	M	F035	11:10	12:20	M
F006	8:20	9:30	M	F036	11:10	12:35	M
F007	8:40	9:40	M	F037	11:10	12:30	L
F008	8:40	9:50	M	F038	11:15	12:20	S
F009	8:45	9:45	M	F039	11:40	12:40	M
F010	8:55	9:55	L	F040	11:45	12:55	M
F011	9:05	10:15	M	F041	11:50	12:50	M
F012	9:20	10:40	M	F042	11:50	13:20	M
F013	9:25	10:35	M	F043	11:55	12:50	M
F014	9:30	10:40	L	F044	12:00	13:00	S
F015	9:40	10:50	S	F045	12:00	13:10	M
F016	9:40	10:40	M	F046	12:00	13:00	S
F017	9:45	10:45	M	F047	12:00	13:10	M
F018	9:50	11:15	M	F048	12:05	13:15	L
F019	9:55	11:00	M	F049	12:05	13:10	M
F020	9:55	11:20	M	F050	12:10	13:10	M
F021	10:00	11:10	L	F051	12:30	13:40	L
F022	10:05	11:10	M	F052	12:40	14:10	M
F023	10:10	11:20	M	F053	12:40	14:10	M
F024	10:15	11:15	S	F054	12:50	13:55	M
F025	10:30	11:40	M	F055	12:55	15:10	L
F026	10:30	11:40	M	F056	12:55	14:10	S
F027	10:35	11:45	M	F057	13:00	14:20	M
F028	10:40	12:30	M	F058	13:05	14:25	M
F029	10:45	11:55	L	F059	13:05	14:10	L
F030	10:55	12:05	M	F060	13:10	14:40	M
				F061	13:10	14:40	M

L: large aircraft; M: medium aircraft; S: small aircraft.

Gates G000–G015 in the hub airport are selected to simulate the gate assignment model. The relevant gate information includes gate number and types of gate. In addition, G000–G014 are gates, and G015 is a set of aprons, which are always available for flights. The available gate data are shown in Table 4.

Table 4.

The available gate data at the hub airport in China.

Gate	Type of gate	Gate	Type of gate
G000	L	G008	M
G001	M	G009	L
G002	L	G010	M
G003	M	G011	L
G004	L	G012	M
G005	M	G013	L
G006	L	G014	L
G007	M

L: large gate; M: medium gate; S: small gate.

The layout of the gate position in the hub airport is shown in Figure 2. The airport consists of three parts: terminal, taxiway, and runway. Gates G000–G014 are near the terminal, others away from terminal are aprons. Parking at these gates G000–G014 can help to reduce passengers walking distance and airport operation cost. The green taxiing routes are departure routes and the red taxiing routes are arrival routes. The arrival flights land on the runway and slide into these gates along the red taxiway routes, while the departure flights are pushed out from these gates and slide into the runway to take off along the green taxiway routes.

Figure 2.

The layout of the gate position in the hub airport.

A new way to estimate $P (f_{i}, f_{j})$

Conflict probability function $P (f_{i}, f_{j})$ can be defined as exponential function and power function

P (f_{i}, f_{j}) = \frac{e (f_{i}, f_{j}) - min {e (f_{i}, f_{j})}}{max {e (f_{i}, f_{j})} - min {e (f_{i}, f_{j})}}

(14)

Expression form of power function is shown as follows

e (f_{i}, f_{j}) = {\begin{matrix} {(\frac{l (f_{i}, f_{j})}{2 t})}^{2} & l < 0 \\ 0 & l \geq 0 \end{matrix}}

(15)

Expression form of exponential form is shown as follows

e (f_{i}, f_{j}) = \exp (- β l (f_{i}, f_{j}))

(16)

where t indicates the buffer time between two consecutive flights. The turnaround time for a flight is 30 min. Buffer time for each flight is defined as $t = 15$ , indicating that each flight has more 15 min to deal with emergency when it arrives or departs at the airport. As a result, the robustness of gate assignment can be improved. According to the statistics and the study by Lim and Wang,²⁴ the conflict probability function $P (f_{i}, f_{j})$ is more suitable for the real situation by adopting exponential form when $β = 0.05$ .

In addition, $l (f_{i}, f_{j}) = a_{f_{j}} - d_{f_{i}} - 2 t$ indicates the free time between two consecutive flights $f_{i}$ and $f_{j}$ . $l (f_{i}, f_{j}) < 0$ indicates that the free time between two consecutive flights is less than the buffer time and may cause conflict. When the free time is longer, the probability of conflict between two flights is lower. When the free time is shorter, the probability of conflict between two flights is higher. $l (f_{i}, f_{j}) \geq 0$ indicates that the buffer time between two consecutive flights is enough, and the probability of conflict is almost zero. Two functions above can satisfy this character, so they can be used to indicate the conflict probability.

This article, respectively, adopts exponential function and power function to indicate the conflict probability. Conflict probability curve generated by two functions is shown in Figure 3.

Figure 3.

Illustration of $P (f_{i}, f_{j})$ on different estimation functions.

It can be seen from Figure 3 that the value of $P (f_{i}, f_{j})$ decreases as $l (f_{i}, f_{j})$ increases when $l (f_{i}, f_{j}) \leq 0$ . In addition, the conflict probability indicated by exponential function mostly is lower than that indicated by power function. Two conflict probability functions are adopted to simulate the model, respectively. It can be seen from Figure 2 that same $l (f_{i}, f_{j})$ corresponds to different conflict probabilities $P (f_{i}, f_{j})$ under two different conditions. So, $P (f_{i}, f_{j})$ cannot be compared directly.

The model is simulated according to objective function (1) with two different $P (f_{i}, f_{j})$ , resulting in two different results of gate assignment. Conflict may happen when the free time between two consecutive flights assigned to the same gate is less than 30 min. So the interval time of two consecutive flights assigned to the same gate is estimated while adopting two different $P (f_{i}, f_{j})$ . The results are shown in Figure 4(a) and (b).

Figure 4.

The interval time adopting (a) exponential function and (b) power function.

Figure 4(a) indicates the distribution of interval time when adopting exponential function, and Figure 4(b) indicates the distribution of interval time when adopting power function. It can be seen from Figure 4(a) and (b) that the number of interval time below 30 min under probability curve of the exponential function is less than that under probability curve of the power function. The distribution of interval time below 30 min is mean under probability curve of the exponential function, and flight ration of them below 30 min is less than 0.05. But the distribution of interval time below 30 min is not mean under probability curve of the power function, and the flight ration of interval time below 20 min is 0.38. This can easily lead to conflict on consecutive flights during rush hours and cannot improve the operation efficiency of the ground resources. So we select exponential function as evaluation index.

Numerical

Exponential function is selected as the evaluation function, and the model is solved by BBO algorithm. The model is simulated under the situation of best robustness (objective function (1)) and the lowest distribution rate of flights assigned to aprons (objective function (2)), respectively. The value of objective function changes with the increase in iteration, as shown in Figure 5(a) and (b). Different color represents different number of population, and each line indicates the change tendency of the objective function under the specific population number.

Figure 5.

The 2D figure on the evolution process of (a) $Z_{1}$ and (b) $Z_{2}$ .

It can be seen from Figure 5(a) that the values of objective function $Z_{1}$ decrease as the iterations number increase. It means lower probability of conflict and fewer flights assigned to aprons. So the robustness of gate assignment schedule continues to be improved. The convergent speed is the fastest at the 200th generation. With the increase in iteration numbers, the algorithm searches for the optimal solution at a slower speed in the feasible region. It can be seen from Figure 5(b) that the values of objective function $Z_{2}$ decrease as the number of iterations increase. At least 50th generation can converge to the optimal solution. Iteration number increases with the increase in population number, and the algorithm searches for the optimal solution at a slower speed in the feasible region. The optimal solution of objective function $Z_{2}$ is 0.09. They all can reach the optimal solution even though the number of population is different. The two figures above indicate that BBO algorithm can converge at feasible region and search for the optimal solution.

In the process of simulation, the results of gate assignment are compared under the situation of random assignment (not considering the objective function), the best robustness (only considering the objective function 1), and the lowest distribution rate of gates assigned to aprons (only considering the objective function (2)), respectively. The results are shown in Table 5 and Figure 6.

Table 5.

The optimization results under three different situations.

Simulation results	The conflict probability $Z_{1}$	The rate of aprons $Z_{2}$	The number of flights assigned to aprons
Random assignment	0.166	0.377	23
The best robustness	0	0.770	47
The lowest distribution rate of gates assigned to aprons	0.395	0.098	6

Figure 6.

The comparison results of conflict probability and the rate of aprons under three different situations.

The following conditions can be seen from Table 5 and Figure 6:

Under the situation of best robustness, the minimum conflict probability of gate assignment is zero, indicating that conflict will not be caused. At the same time, the distribution rate of flights assigned to aprons is as high as 0.770, which is the highest among them. A total of 14 flights are assigned to gates, while other flights are assigned to aprons. The robustness of gate assignment is improved, while the distance of aircraft’s sliding and passengers’ walking is increased. This will increase operation cost and reduce the service satisfaction of passengers.

Under the situation of the lowest rate of flights assigned to aprons, the number of flights assigned to aprons is much less than that under other situations. This will decrease sliding distance of flights, the cost of airlines, and the walking distance of passengers, while the conflict probability under this situation is more than that under other situations. It decreases the robustness, which indicates that this way of gate assignment may lead to conflict and delay of flights.

It can be seen from above that better robustness may increase the number of flights assigned to aprons and then increase the operation cost of airlines. The rate of flights assigned to aprons will lead to the worse robustness of gate assignment and flight delay. So, during the process of gate assignment, the robustness and the rate of flights assigned to aprons can be both taken into consideration.

The objective function $Z_{2}$ is transformed into the constraint condition. Higher indicates that more than half number of flights is assigned to aprons, resulting in more walking distance for passengers. So, $Z_{2}$ is defined as 0.1, 0.2, 0.3, 0.4, and 0.5 to simulate the model. The results are shown in Table 6 and Figure 7.

Table 6.

The simulation results of gate assignment under different rates of aprons $Z_{2}$ .

Rate of aprons $Z_{2}$	Conflict probability $Z_{1}$	Number of flights assigned to aprons	Actual passing rate of flights (%)
0.1	0.414	6	90.16
0.2	0.227	12	80.33
0.3	0.108	17	70.59
0.4	0.046	24	60.66
0.5	0.011	30	50.82

Figure 7.

The conflict probability and number of flights assigned to aprons under different rates of aprons $Z_{2}$ .

It can be seen from Table 6 and Figure 7 that the value of objective function $Z_{1}$ keeps decreasing with the increase in $Z_{2}$ . The rate of flights assigned to aprons increases, resulting in the decrease in passing rate of flights. Fewer flights are assigned to gates, decreasing the probability of conflict and improving the robustness of gate assignment. So, there is some relation between the robustness of gate assignment and the number of flights assigned to aprons. When the number of flights assigned to aprons is more, the robustness of gate assignment is better. The actual passing rate of flights is a little different from $Z_{2}$ because the best robustness is calculated with the limitation of $Z_{2}$ .

More flights are assigned to aprons, fewer flights are assigned to gates, resulting the interval time between two consecutive flights assigned to the same gate is longer. The impact on other flights is smaller when delays on one or more flights are caused by weather or other reasons. The gate assignment is uneasy to be disturbed, reducing the probability of conflict and improving the robustness. Compare the time interval distribution between two consecutive flights under the situation of first come first served and $Z_{2} = 0.1, 0.2, 0.3, 0.4, 0.5$ . The results are shown in Table 7 and Figure 8.

Table 7.

The distribution of interval time.

Assign way	Interval time (min)
Assign way	<20	20–25	25–30	30–35	35–40	40–60	60–90	90–120	>120
$Z_{2} = 0.1$	14	5	6	4	4	4	3	0	0
$Z_{2} = 0.2$	4	3	2	5	5	13	2	0	0
$Z_{2} = 0.3$	0	0	0	3	4	10	8	2	1
$Z_{2} = 0.4$	0	0	0	0	0	3	12	6	1
$Z_{2} = 0.5$	0	0	0	0	0	0	3	7	6

Figure 8.

The ratio of different interval times.

Table 7 indicates the time interval distributions of consecutive flights allocated to the same gate in the three different kinds of situation. Figure 8 indicates the proportion of intervals time between consecutive flights allocated to the same gate in the three situations. It can be seen from Table 7 and Figure 8 that when $Z_{2} = 0.1$ and $Z_{2} = 0.2$ , there are, respectively, 29 and 14 flights (63% and 42% of total flights) whose time intervals less than 35 min. This means that it is very easy to cause flight conflict under these two situations. So, the robustness of gate assignment is also inferior. When $Z_{2} = 0.5$ , the robustness of gate assignment is very high; however, almost half of flights are assigned to an apron, which means lower utilization of gates, and may increase passengers’ walking distance and decrease their satisfaction. When $Z_{2} = 0.3$ and $Z_{2} = 0.4$ , the time intervals between 30 and 40 min, respectively, take over 25% and 0%. This indicates that it is also easy to cause flight conflict during the peak hour when $Z_{2} = 0.3$ , and the flights assigned to gates under $Z_{2} = 0.3$ is only little more than that under $Z_{2} = 0.4$ , under which there are 37 flights allocated to gates, the passing rate decreases in comparison with the former two methods, and the ratio of interval time of two flights assigned to the same gate between 60 and 120 min is 82%. The results shows that the robustness increases greatly, and the probability of flight conflicts decreases, which is beneficial to the implement of flight assignment plan.

Increasing of flights assigned to aprons will improve the robustness of gate assignment, which also leads to longer passenger walking distance and lower airport service satisfaction. And if utilization of gate increases immensely, flights’ conflict may easily happen at busy period and delay increases. Therefore, the robustness and the number of flights assigned to aprons should be both considered. In view of the two kinds of factors, it can be concluded that the robustness and passing rate of gate assignment both meet airport operation requirements when $Z_{2} = 0.4$ . Its specific Gantt figure of gate assignment results are shown in Figure 9. It can be seen from Figure 9 that the gate assignment results improve the utilization ration of gates G000–G014 and reduce the utilization ratio of aprons G015. This can reduce the taxiing distances of flights. In addition, flights are even distributed at gates, increasing the interval time between two consecutive flights. This can reduce the conflict probability and improve the robustness of gate assignment.

Figure 9.

The Gantt chart of gate assignment results when $Z_{2} = 0.4$ .

Conclusion

In this article, a multi-objective gate assignment model is proposed to minimize flight conflict probability and number of flights assigned to aprons. By controlling the proportion of flights assigned to the apron, we can find out optimally robust assignment results under different proportions. The model is simulated using actual operation data from a hub airport in China, so the results are more reliable. The BBO algorithm is more effective to solve the model and very easy to find out optimal solutions; meanwhile, its program is very simple. For different airports, the proposed model can be used to optimize gate pre-assignment according to actual situations and improve the performance and stability of the plan. Gate assignment plan of different robustness should be chosen based on actual situations at these airports. Flexibility of gate assignment is also improved by controlling the proportion of aprons.

This article mainly considers that how the flight conflict influences the robustness of gate assignment. Besides, other factors like weather and walking distance of passengers can also be taken into consideration when optimizing the gate assignment.

Footnotes

Academic Editor: Xiaobei Jiang

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by National Nature Science Foundation of China 61104159 and 61573181, the National Nature Science Foundation of China and Civil Aviation Administration of China U1333117, the Natural Science Foundation of Jiangsu Province BK20131366, and the Youth Science and Technology Innovation Foundation NS2013067.

References

Atkin

JAD

Burke

Ravizza

. The airport ground movement problem: past and current research and future directions. In: Proceedings of the fourth international conference on research in air transportation, Budapest, 1–4 June 2010, pp.131–138. Federal Aviation Administration (FAA) & EUROCONTROL.

Stergianos

Atkin

Schittekat

Pushback delays on the routing and scheduling problem of aircraft. J Appl Op Res 2015; 7: 68–79.

Yan

Tang

CH.

A heuristic approach for airport gate assignments for stochastic flight delays. Eur J Oper Res 2007; 180: 547–567.

Lobato

Carvalho

Pereira

. Airport ground movement, operations research and Big Data. New York: Springer, 2015.

Babic

Teodorovic

Tosic

Aircraft stand assignment to minimize walking. J Transp Eng 1984; 110: 55–66.

Bandara

Wirasinghe

SC.

Walking distance minimization for airport terminal configurations. Transport Res A: Pol 1992; 26: 59–74.

Yin

Zhao

Simulation model and algorithm of multi-runway airport gate assignment. J Traffic Transport Eng 2010; 10: 71–76.

Xiong

Zhang

Airport gate assignment with airplane taxiing cost analysis. J Transp Syst Eng Inf Technol 2010; 10: 165–170.

Bolat

Procedures for providing robust gate assignments for arriving aircrafts. Eur J Oper Res 2000; 120: 63–80.

10.

Kumar

Pradeep Kumar

Bierlaire

Multi-objective airport gate assignment problem. In: Proceedings of the 11th Swiss transport research conference, Ascona, 11–13 May 2011, pp.1–14. Lausanne: Swiss federal Institute of Technology.

11.

Dorndorf

Jaehn

Pesch

Flight gate scheduling with respect to a reference schedule. Ann Oper Res 2012; 194: 177–187.

12.

Sang

Feron

Clarke

JP.

Gate assignment to minimize passenger transit time and aircraft taxi time. J Guid Control Dynam 2013; 36: 467–475.

13.

Jiang

Zeng

Luo

YX.

Multi-objective gate assignment based on passenger walking distance and fairness. Math Probl Eng 2013; 70: 717–718.

14.

Prem Kumar

Bierlaire

. Multi-objective airport gate assignment problem in planning and operations. J Adv Transport 2014; 48: 902–926.

15.

Chun

Nordin

. An integer programming model for gate assignment problem at airline terminals. In: Proceedings of the international conference on mathematics, engineering and industrial applications 2014, Penang, Malaysia, 28–30 May 2014. AIP Publishing.

16.

Hakk

Osman

Ibrahim

. A stochastic neighborhood search approach for airport gate assignment problem. Expert Syst Appl 2012; 39: 316–327.

17.

Song

Sun

. Mathematical models, GRASP algorithms and fitness landscape analysis for aircraft gate assignment problem. In: Proceedings of 2014 tenth international conference on computational intelligence and security, Washington, DC, 15–16 November 2014, pp.64–68. New York: IEEE.

18.

Lau

HYK

. A hybrid algorithm for solving gate assignment problem with robustness and tow considerations (Research and development in intelligent systems XXXI). Cambridge, UK: Springer, 2014.

19.

Aoun

El Afia

Using Markov decision processes to solve stochastic gate assignment problem. In: Proceedings of the international conference on logistics and operations management, Rabat, Morocco, 5–7 June 2014, pp.42–47. New York: IEEE.

20.

Wang

Zhu

. A constraint programming model of gate assignment based on mixed set programming. Aeronaut Comput Tech 2014; 44: 18–21.

21.

Chong

Nordin

SZ.

An integer programming model for gate assignment problem at airline terminals. AIP Conf Proc 2015; 1660: 171–182.

22.

Hidayatno

Moeis

Dharma

GAS

. Designing gate assignment model to find the optimum airport gate assignment order. J Tek Ind 2015; 17: 1–6.

23.

Marinelli

Palmisano

Dell’Orco

. Fusion of two metaheuristic approaches to solve the flight gate assignment problem. Transport Res 2015; 10: 920–930.

24.

Lim

Wang

Robust airport gate assignment. In: Proceedings of the 17th IEEE international conference on tools with artificial intelligence, Washington, DC, 14–16 November 2005, pp.74–81. New York: IEEE.

25.

Smith

Johnson

EL.

Robust airline fleet assignment: imposing station purity using station decomposition. Transport Sci 2006; 40: 497–516.

26.

Dumas

Aithnard

Soumis

Improving the objective function of the fleet assignment problem. Transport Res B: Meth 2009; 43: 466–475.

27.

Diepen

van den Akker

Hoogeveen

. Using column generation for gate planning at Amsterdam Airport Schiphol. Technical Report UU-CS-2007–018, Institute of Information and Computing Sciences, Utrecht, 2007.

28.

Yang

. Airport gate assignment based on improved GM (1, 1) model. In: Proceedings of the 2009 IEEE international conference on grey systems and intelligent services, Nanjing, China, 10–12 November 2009, pp.403–407. New York: IEEE.

29.

Wang

. A robust approach for the airport gate assignment. In: Proceedings of the international forum on shipping, ports and airports (IFSPA) 2010-integrated transportation logistics: from low cost to high responsibility 2011, Chengdu, China, 15–18 October 2010, pp.15–24. Hong Kong: Hong Kong Polytechnic University and Southwest Jiaotong University.

30.

Zhu

Chen

Robust assignment model of airport gate based on flight delay distribution. J Traffic Transp Eng 2014; 14: 74–82.

31.

Zhao

Cheng

Ant colony algorithm and simulation for robust airport gate assignment. Math Probl Eng 2014; 2014: 804310-1–804310-7.

32.

Wang

Tian

. Research on robustness of gate assignment based on column generation methods. J Wuhan Univ Technol 2015; 39: 171–174.

33.

Narciso

Piera

MA.

Robust gate assignment procedures from an airport management perspective. Omega 2015; 50: 82–95.

34.

Simon

Biogeography-based optimization. IEEE T Evolut Comput 2008; 12: 702–713.

Multi-objective gate assignment based on robustness in hub airports

Abstract

Keywords

Introduction

Review

Model development

Assumptions

Notation

Model

Gate assignment optimization simulation based on BBO

Encoding way

Generating initial solution

Designing habitat suitability index

The operation of BBO algorithm

Migration operation

Mutation operation

Numerical

The data for simulation

A new way to estimate P ( f i , f j )

Numerical

Conclusion

Footnotes

Declaration of conflicting interests

Funding

References

A new way to estimate $P (f_{i}, f_{j})$