# Taxiing Route Scheduling between Taxiway and Runway in Hub Airport

Authors: Yu Jiang; Xinxing Xu; Honghai Zhang; Yuxiao Luo
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

To guarantee the operation safety of airport, improve the efficiency of surface operation, and enhance the fairness of taxiing route scheduling, an optimizing model is established for the airport surface taxiing route scheduling. Reducing the total aircraft taxiing route length and reducing the waiting delay time are the goals of the model by controlling the initial taxiing time of aircraft and choosing the right taxiing route. The model can guarantee the continuous taxiing for all aircraft without conflicts. The runway scheduling is taken into consideration in the model to optimize the surface operation. The improved genetic algorithm is designed for simulation and validation. The simulation results show that compared with the ant colony optimization method, the improved genetic algorithm reduces the total extra taxiing distance by 47.8% and the total waiting delay time decreases by 21.5%. The optimization model and improved genetic algorithm are feasible. The optimization of taxiing route method can provide decision support for hub airports.


---

## Body

## 1. Introduction

With the rapid development of air transport and the sharp increase in the number of aircraft, airports have increasingly become a “bottleneck” of the air transportation network. This phenomenon leads to low operation efficiency of resources in the airport increasing aircraft delays and air pollution and other problems [1]. At present, there are two main ways to solve the airport “bottleneck” problem at home and abroad: one is to increase the infrastructure construction of airport surface resources and the other is to improve the operation efficiency of airport surface resources. However, the airport infrastructure construction in China is still far behind the rapid development aboard. Therefore, how to improve the operation efficiency of airport surface resources becomes the main method to resolve the airport “bottleneck” problem.The operation of airport surface resources includes runway scheduling for landings and take-offs, gate assignment, and taxiway routing. Connecting runways and gates, taxiways are the key resource of the airport taxiing process [2]. Thus how to improve the operation efficiency of the taxiway is the key to improve the operation efficiency of airport surface resources.Many scholars have studied aircraft surface taxiing and scheduling and achieved some good achievements. These achievements can be mainly divided into two aspects: one is the preset route of aircraft taxiing and the other is dynamic selection route of aircraft taxiing. Among the preset route of aircraft taxiing researches, Smeltink and Soomer [3] presented the first approach to solve the surface movement problem using the MILP formulation, but the research did not consider the taxiing interval and taxiing time constraints, so there was a certain security risk. Based on the research of Smeltink and Soomer, Rathinam et al. [4] added a taxiing interval constraint to the model, but each aircraft still moved with a predetermined route. Gotteland et al. [5] presented a taxiing model based on the characteristics of aircraft taxiing conflicts and used genetic algorithms to simulate the model, but the research did not consider the waiting problem of aircraft caused by the potential taxiing conflicts. Landry et al. [6] used the theory of complex network, dynamically detected and resolved the conflicts on taxiways and runways, improved the operation efficiency of the surface resources, and ensured the safety of the aircraft taxiing, but the simulation of model was relatively complicated, which could not meet the requirement of real-time scheduling of the taxiing. Anderson et al. [7] proposed two simple queuing models to indicate the taxiing-in and taxiing-out processes of aircraft. The model could be applied for not only predicting the surface congestion, but also evaluating the control strategy which could improve the operation efficiency of airport. But the model had little consideration on the interrelation between landings and take-offs. Pitfield et al. [8] used the Monte Carlo simulation to study the potential taxiing conflicts on congested taxiways, but taxiing optimization had not been performed in the simulation. The study resolved the taxiing conflicts by controlling aircraft to wait in certain nodes. Therefore, the study always belonged to the predetermined route research.The predetermined taxiing route of aircraft is likely to lead to taxiing delays and increase the operation cost. Therefore, some scholars have carried out some studies on dynamic taxiing route of aircraft. Keith et al. [9] formulated a MILP model combining the runway scheduling with taxiway routing in a continuous time environment. The simulation results were significantly better than the results obtained from the runway scheduling and taxiway route routing problem separately. But the simulation data used was relatively simple, and it could not operate in real simulation environment. Balakrishnan and Yoon [10] presented the aircraft dynamic taxiing model. The results could reduce the total taxiing time by controlling the taxiing-out time and taxiing path rerouting. But each aircraft could only be allocated one of the limited routes in the set. Roling and Visser [11] presented an alternative MILP model for ground movement on a space-based network, in which optional routes were assigned for each aircraft in advance. This research only ensured that there were no conflicts in the planning period. Anderson and Milutinović [12] considered aircraft taxiing traffic flows on the taxiway by adjusting the speed of taxiing aircraft on each taxiway segment. Meanwhile the model was employed to consider the flows of aircraft instead of node occupation on the time dimension. The model also effectively incorporated the aircraft taxiing uncertainty into it. You and Han [13] introduced multiple agent technology to model the taxiing route of aircraft. The research considered the contract net protocol theory in the model and selected Dijkstra algorithm to optimize the taxiing route. A multiple agent route optimization algorithm was adopted and the simulation analysis was made. But the research did not take the dynamic nature of aircraft taxiing into account. Wang et al. [14] presented a dynamic taxiing route allocation algorithm to avoid taxiing conflicts, but the uncertainty of the aircraft taxiing speed was not taken into account. Marín et al. [15, 16] abstracted the taxiway into multiple commodity flow problem. The model took the aircraft routing and the queue scheduling problem into account. It belonged to dynamic route assignment scope. However, the presented algorithm could not handle separation constraints in an accurate way. In the dynamic route assignment, scholars have presented dynamic assignment models from different viewpoints, but the accuracy and operation speed of algorithm need to be improved. Carr et al. [17] and Idris et al. [18] considered the interaction influences of arrival and departure taxiing process and presented a route assignment model for dynamic taxiing. But the algorithm used in the solution reduced the speed and accuracy of the model. Baik et al. [19] used graph theory and designed a time-dependent network assignment strategy to optimize the aircraft dynamic taxiing routes. To obtain the satisfactory acceptable solution, García et al. [20] and Gotteland and Durand [21] introduced the heuristic algorithm to improve the operation efficiency of airport surface resources and achieved good achievements.In summary, both in the preset and nonset taxiing routes, most researches formulated a single goal model for aircraft taxiing, without consideration of synergistic operations of other surface resources. Meanwhile, most of the researches only considered unilateral interests of airports, airlines, or air traffic controllers separately, without considering their whole interests comprehensively. In the aircraft taxiing, the occupancy and operation mode of runway have a great influence on the aircraft taxiing route. How to model and simulate the synergistic scheduling of runway and taxiways operation under the premise of considering the interests of all parties is an urgent problem in the airport surface resource scheduling.The needs of air traffic controllers, airlines, and airports are considered in the paper. A synergistic scheduling strategy based on safety, efficiency, and fairness is presented in the airport surface movement. A synergistic scheduling model is established on runway and taxiway scheduling and an improved genetic algorithm is used to simulate the verification of model. It can provide theoretical guidance for resource synergistic scheduling for managers in hub airports.The remainder of this paper is structured as follows. Section2 provides a brief description of the aircraft taxiing scheduling problem and the aspects this paper mainly considered. Section 3 gives the optimizing model of the airport synergistic scheduling problem. In Section 4, the improved genetic algorithm method is introduced first. The simulation data from the airport is then presented. Following this, the results are then shown together with the discussion. Section 5 contains the conclusions.


## 2. Problem Description

Aircraft taxiing scheduling is a complex route scheduling problem including landing and take-off taxiing scheduling. Landing taxiing scheduling means assigning appropriate landing time for landings, selecting the appropriate runway exit to taxiway, and then selecting the appropriate taxiing route to reach the assigned gate. Take-off taxiing scheduling means assigning appropriate push-out time and selecting appropriate taxiing route so that the aircraft can begin to taxi from the gate to the right runway threshold. Therefore, both the operations of landing and take-off are successive. Airport taxiing scheduling for aircraft on airport surface is to determine aircraft approach time, departure time, and taxiing route for each aircraft under the premise of ensuring safety. Therefore, the total taxiing distance (time) of both landings and take-offs is made to be the shortest and the total delays to be the least.In the airport surface taxiing scheduling, the different stakeholders have different requirements. The air traffic control authorities require ensuring the safety of the movement of aircraft on the airport surface. Airlines need to ensure that flights can take off and land on time to reduce delay and taxiing cost. Airport authorities want to improve the utilization efficiency of airport resources. Therefore, the airport surface scheduling, not only security but also efficiency and fairness of scheduling, should be taken into account. The so-called synergistic scheduling is to consider three aspects of comprehensive requirements, as well as the synergistic scheduling of taxiway and runway.


## 3. Model

### 3.1. Assumptions

(1) Aircraft’s speed is constant during taxiing and the taxiing route will be continuous without any stop until to the destination.(2) All aircraft have the same taxiing route unit cost and waiting delay cost.(3) Gate zone has sufficient gates to meet all the demand of landing and take-off aircraft in planned period of time.(4) Take-off aircraft starts taxiing from the gate zone and ends in the runway threshold; landing aircraft start taxiing from the runway exit and end in the gate zone. Each aircraft has a fixed gate and exit on the runway.


### 3.2. Define Variables

F:
set of all aircraft within planned period,F=f1,f2,…,fk;
F
d:
set of all take-offs within planned period;
F
a:
set of all landings within planned period;
A:
set of airlines,A=α1,α2,…,αl;
N:
set of airport surface nodes, any nodenp,nq∈N;
N
r:
set of runway entrance and exit nodes,Nr⊂N;
L
p
q:
the distance between nodesnp and nq (unit: km);
V
i
max
⁡:
the maximum taxiing speed of aircraftfi, and any speed Vi∈0,Vimax⁡;
C
p
q
= 1, if there is a directly connected and usable route from nodenp to node nq; 0, otherwise;
T
i
p:
the time of aircraftfi arrives at the node np;
T
i
o:
the reference scheduling time, namely, the earliest time that aircraft could come into the taxiway system;
R
i
p
q
= 1, if aircraftfi taxies from node np to node nq; 0, otherwise;
Z
i
j
p
= 1, if aircraftfi reaches node np before aircraft fj; 0, otherwise;
N
i:
the taxiing route of aircraftfi, consisting of a series of nodes Ni=(n1i,n2i,…,nkii);
t
i
j
e:
the safe taxiing time interval between aircraftfi and aircraft fj;
t
i
j
w:
the wake turbulence separation between aircraftfi and aircraft fj;
Δ:
the time of aircraft occupying runway;
B
i
j
r
= 1, if aircraftfi uses the runway r before aircraft fj; 0, otherwise;
ETAi:
the estimated starting taxiing time of landing aircraftfi after landing;
ET
P
i:
the estimated push-out time of take-off aircraftfi;
ET
D
i:
the estimated take-off time of take-off aircraftfi;
TB
T
i:
the starting taxiing time of aircraftfi;
T
L
i:
the true taxiing route length of aircraftfi;
S
L
i:
the shortest taxiing route length of aircraftfi from the beginning to end;
D
α:
the total extra taxiing route length of airlineα;
p
α:
the proportion that the number of airlinesα accounts for the total airlines;
∑
p
α
¯:
the proportion that the number of flights of airlineα accounts for the total airlines accumulatively;
D
T
α:
the total waiting delay time of airlineα;
G
1:
the Gini coefficient of taxiing route;
G
2:
the Gini coefficient of waiting delay;
ε
1:
the parameter value of Gini coefficientG1;
ε
2:
the parameter value of Gini coefficientG2.


### 3.3. Objective Functions

In hub airports, the taxiing route length of aircraft and waiting delay are the main factors affecting the efficiency of surface movement. Thus the objective functions of the paper are presented in two aspects: the taxiing route cost and the waiting delay time. Shortening taxiing route length and reducing waiting delay time of all aircraft in the planned period are the main goals in the aircraft scheduling.As the speed of aircraft is constant during taxiing, the taxiing time and taxiing route length of aircraft are equivalent. In the paper, the taxiing time of aircraft refers to the difference between the start time and the end time of taxiing. The goal is to minimize the total taxiing time of all aircraft in planned period:(1)min⁡∑fi∈FTinkii-Tin1i.For landing, the waiting time before entering into the taxiway system is due to the busy use of surface resources, which can postpone the landing aircraft. The same reason can postpone the push-out time of the take-off aircraft from the gate zone. During the synergistic scheduling of taxiway and runway, with the premise of no aircraft affecting the taxiing safety, all aircraft should enter the taxiing system as soon as possible, which can make the total waiting delay time of all aircraft shortest:(2)min⁡∑fi∈FTin1i-Tio.


### 3.4. Constraints

(1) Taxiing Route Constraints. If the runway exit, runway entrance, and gate of aircraft are known, the aircraft taxiing route constraints are to generate a feasible route from the starting point to the end for each aircraft:(3)Ripq≤Cpq∀fi∈F,∀np,nq∈N.Formula (3) ensures that each link of the taxiing route of any aircraft fi needs to meet the capacity and the physical connectivity of taxiway in the airport:(4)∑np∈NRipq-∑ns∈NRiqs=1nq=nkii0other-1nq=n1i∀fi∈F,∀np,nq,ns∈N.Formula (4) ensures that each aircraft is assigned a feasible taxiing route from the starting point to the end point and that all the surface nodes have a liquidity balance. That is to say, if an aircraft reaches a node of the airport surface, it must begin to taxi from this node to the other one:(5)Tip+LpqVi-Tiq·Ripq=0,∀fi∈F,∀np,nq∈N.Formula (5) ensures that the taxiing route of aircraft is always continuous. It does not allow any aircraft to stop to wait during the course of taxiing. When the aircraft fi is taxiing from node np to the next node nq, formula (5) is to be Tiq=Tip+Lpq/Vi:(6)LpqVimax⁡·Ripq-M1-Ripq≤Tiq-Tip∀fi∈F,∀np,nq∈N.Formula (6) restricts the taxiing speed of all aircraft. The speed of each aircraft must be less than the maximal speed.Formula (3)–(6) ensure that any aircraft fi must have an effective taxiing route from its gate to its runway entrance or from its runway exit to its gate and have a continuous taxiing route. However, the route generated here is random, not necessarily the optimal route. What is more, it may conflict with other aircraft during taxiing.(2) Taxiing Security Constraints. Aircraft taxiing on the airport surface usually produces three types of taxiing conflicts: the node conflict, rear-end conflict, and head-on conflict.Node Conflict. The interval time, at which the two aircraft go through the same node, does not meet the minimum safety requirements.Rear-End Conflict. When two aircraft taxi in the same direction on a taxiway, the faster trailing aircraft may overtake the leading aircraft.Head-On Conflict. When two aircraft taxi in the opposite direction on a taxiway, they have an encounter with each other.The taxiing safety constraints of aircraft are to ensure the safety of aircraft taxiing and avoid taxiing conflicts above:(7)ZijpTip+tije-Tjp≤0∀fi,fj∈F,np∈Ni∩Nj.Formula (7) ensures the safety interval of two taxiing aircraft. When two aircraft go through the same node, there must be a safety time interval between them. Safety time interval is related to aircraft type, wake turbulence separation, taxiing speed, and so on:(8)Zijp-Zijq≤2-Ripq+Rjpq∀fi,fj∈F,∀np,nq∈N,Zijp-Zijq≥-2+Ripq+Rjpq∀fi,fj∈F,∀np,nq∈N.Formula (8) can avoid rear-end conflicts during the taxiing of airport. The scene that one aircraft overtakes another must not occur during the taxiing:(9)Zijp-Zijq≤2-Ripq+Rjqp∀fi,fj∈F,∀np,nq∈N,Zijp-Zijq≤-2+Ripq+Rjqp∀fi,fj∈F,∀np,nq∈N.Formula (9) can avoid head-on conflicts during aircraft taxiing. An aircraft must not have an encounter with other aircraft in a certain taxiway during taxiing.(3) Runway Operation Constraints. The runway operation strategy has an important influence on the airport surface taxiing. The successive relationship between two aircraft using the same runway can be divided into four kinds: takeoff-takeoff, takeoff-landing, landing-takeoff, and landing-landing: (10)Tip+tijw-1-ZijpM≤Tjp∀fi,fj∈Fd,∀np∈Nr.Formula (10) ensures that in the case of takeoff-takeoff, two consecutive take-off aircraft must meet wake turbulence separation standards between them:(11)Tinkii+tijw-1-BijrM≤Tjn1j-Δ,∀fi∈Fd,∀fj∈Fa,∀nkii,n1j∈Nr.Formula (11) ensures that in the takeoff-landing process, two aircraft must meet the take-off wake turbulence separation standards. The take-off aircraft must leave the runway before the trailing lands on the runway. The starting taxiing time of landing aircraft fj equals the time difference of reaching the runway and runway occupancy time. If the starting taxiing time is Tjn1j, the time of landing on the runway is Tjn1j-Δ. According to the wake turbulence separation standards, formula (11) is got above:(12)Tin1i-1-BijrM≤Tjnkjj,∀fi∈Fa,∀fj∈Fd,∀n1i,nkjj∈Nr.Formula (12) ensures that, in the case of landing-takeoff, the take-off aircraft can enter the runway until the heading landing aircraft leaves the runway. The time of entrance to the runway for take-off aircraft fj at least equals the time the landing aircraft fi exiting the runway:(13)Tin1i-1-BijrM≤Tjnkjj,∀fi∈Fa,∀fj∈Fd,∀n1i,nkjj∈Nr.Formula (13) assures that, in the case of landing-landing, the two aircraft must meet the wake turbulence safety interval standards. The trailing aircraft cannot land on runway until the heading aircraft taxis off the runway.(4) Taxiing Time Constraints. The taxiing time constraints are used to ensure that the taxiing scheduling of aircraft should be in accordance with the requirements of flight schedule: (14)Tin1i≥ETAi∀fi∈Fa.Formula (14) ensures that the landing aircraft should begin to taxi after the estimated starting taxiing time:(15)Tin1i≥ETPi∀fi∈Fd,(16)Tinkii≤ETDi∀fi∈Fd.Formula (15) ensures that a take-off aircraft must start taxiing after its push-out time. Formula (16) requires aircraft to complete the taxiing and reach the runway entrance before the estimated take-off time.(5) Fairness Constraints. During the course of scheduling of aircraft, sometimes the route length of one airline’s aircraft is always much longer than other airlines, or the total delay is much larger than other airlines. Therefore, the fairness for various airlines needs to be taken into account during the taxiing route scheduling of aircraft. The Gini coefficient in the economics is introduced to restrain the fairness of taxiing scheduling and we use it to quantify the taxiing route fairness and delay fairness. The Gini coefficient can reflect the degree of unfairness for resources distribution. The smaller the value is, the more average the distribution is.As the runway and the gate of an aircraft are known, the shortest path of each aircraft is different. If we want to weigh the fairness of the taxiing route, simply comparing the taxiing route length of each aircraft cannot meet the actual requirements and is not enough as well. Therefore we introduce the concept of extra taxiing distance.Definition 1 (extra taxiing distance).
When the runway and the gate of an aircraft are known, we can get a shortest path for it. Extra taxiing distance is the difference distance between actual route length obtained by planning and the shortest route length. The extra taxiing distance is produced in order to avoid conflicts in the surface taxiing scheduling.
The fairness constraints of aircraft taxiing route are in essence to distribute the extra taxiing distance produced by scheduling between airlines. The smaller the Gini coefficient for airlines is, the more means the taxiing scheduling is. The extra taxiing distance of airlineα is as follows:(17)Da=∑i∈FaTLi-SLi.TLi is the actual length of taxiing route which is obtained by the planning schedule, so TLi=∑k=1ki-1Lnkink+1i. SLi is the shortest route from the starting point to the end, which could be obtained from the Dijkstra algorithm.
The Gini coefficient is defined and calculated as follows:(18)G1=1+∑a∈ApaDa-2∑a∈A∑pa¯Da.Letting G1 be less than a small constraint parameter value ε1, the fairness constraint based on taxiing length could be established as follows:(19)1+∑a∈ApaDa-2∑a∈A∑pa¯Da≤ε1.Formula (19) ensures the fairness of taxiing route length:(20)G2=1+∑a∈ApaDTa-2∑a∈A∑pa¯DTa,(21)1+∑a∈ApaDTa-2∑a∈A∑pa¯DTa≤ε2.Similarly, formula (21) ensures the fairness of waiting delay of all the aircraft.


## 3.1. Assumptions

(1) Aircraft’s speed is constant during taxiing and the taxiing route will be continuous without any stop until to the destination.(2) All aircraft have the same taxiing route unit cost and waiting delay cost.(3) Gate zone has sufficient gates to meet all the demand of landing and take-off aircraft in planned period of time.(4) Take-off aircraft starts taxiing from the gate zone and ends in the runway threshold; landing aircraft start taxiing from the runway exit and end in the gate zone. Each aircraft has a fixed gate and exit on the runway.


## 3.2. Define Variables

F:
set of all aircraft within planned period,F=f1,f2,…,fk;
F
d:
set of all take-offs within planned period;
F
a:
set of all landings within planned period;
A:
set of airlines,A=α1,α2,…,αl;
N:
set of airport surface nodes, any nodenp,nq∈N;
N
r:
set of runway entrance and exit nodes,Nr⊂N;
L
p
q:
the distance between nodesnp and nq (unit: km);
V
i
max
⁡:
the maximum taxiing speed of aircraftfi, and any speed Vi∈0,Vimax⁡;
C
p
q
= 1, if there is a directly connected and usable route from nodenp to node nq; 0, otherwise;
T
i
p:
the time of aircraftfi arrives at the node np;
T
i
o:
the reference scheduling time, namely, the earliest time that aircraft could come into the taxiway system;
R
i
p
q
= 1, if aircraftfi taxies from node np to node nq; 0, otherwise;
Z
i
j
p
= 1, if aircraftfi reaches node np before aircraft fj; 0, otherwise;
N
i:
the taxiing route of aircraftfi, consisting of a series of nodes Ni=(n1i,n2i,…,nkii);
t
i
j
e:
the safe taxiing time interval between aircraftfi and aircraft fj;
t
i
j
w:
the wake turbulence separation between aircraftfi and aircraft fj;
Δ:
the time of aircraft occupying runway;
B
i
j
r
= 1, if aircraftfi uses the runway r before aircraft fj; 0, otherwise;
ETAi:
the estimated starting taxiing time of landing aircraftfi after landing;
ET
P
i:
the estimated push-out time of take-off aircraftfi;
ET
D
i:
the estimated take-off time of take-off aircraftfi;
TB
T
i:
the starting taxiing time of aircraftfi;
T
L
i:
the true taxiing route length of aircraftfi;
S
L
i:
the shortest taxiing route length of aircraftfi from the beginning to end;
D
α:
the total extra taxiing route length of airlineα;
p
α:
the proportion that the number of airlinesα accounts for the total airlines;
∑
p
α
¯:
the proportion that the number of flights of airlineα accounts for the total airlines accumulatively;
D
T
α:
the total waiting delay time of airlineα;
G
1:
the Gini coefficient of taxiing route;
G
2:
the Gini coefficient of waiting delay;
ε
1:
the parameter value of Gini coefficientG1;
ε
2:
the parameter value of Gini coefficientG2.


## 3.3. Objective Functions

In hub airports, the taxiing route length of aircraft and waiting delay are the main factors affecting the efficiency of surface movement. Thus the objective functions of the paper are presented in two aspects: the taxiing route cost and the waiting delay time. Shortening taxiing route length and reducing waiting delay time of all aircraft in the planned period are the main goals in the aircraft scheduling.As the speed of aircraft is constant during taxiing, the taxiing time and taxiing route length of aircraft are equivalent. In the paper, the taxiing time of aircraft refers to the difference between the start time and the end time of taxiing. The goal is to minimize the total taxiing time of all aircraft in planned period:(1)min⁡∑fi∈FTinkii-Tin1i.For landing, the waiting time before entering into the taxiway system is due to the busy use of surface resources, which can postpone the landing aircraft. The same reason can postpone the push-out time of the take-off aircraft from the gate zone. During the synergistic scheduling of taxiway and runway, with the premise of no aircraft affecting the taxiing safety, all aircraft should enter the taxiing system as soon as possible, which can make the total waiting delay time of all aircraft shortest:(2)min⁡∑fi∈FTin1i-Tio.


## 3.4. Constraints

(1) Taxiing Route Constraints. If the runway exit, runway entrance, and gate of aircraft are known, the aircraft taxiing route constraints are to generate a feasible route from the starting point to the end for each aircraft:(3)Ripq≤Cpq∀fi∈F,∀np,nq∈N.Formula (3) ensures that each link of the taxiing route of any aircraft fi needs to meet the capacity and the physical connectivity of taxiway in the airport:(4)∑np∈NRipq-∑ns∈NRiqs=1nq=nkii0other-1nq=n1i∀fi∈F,∀np,nq,ns∈N.Formula (4) ensures that each aircraft is assigned a feasible taxiing route from the starting point to the end point and that all the surface nodes have a liquidity balance. That is to say, if an aircraft reaches a node of the airport surface, it must begin to taxi from this node to the other one:(5)Tip+LpqVi-Tiq·Ripq=0,∀fi∈F,∀np,nq∈N.Formula (5) ensures that the taxiing route of aircraft is always continuous. It does not allow any aircraft to stop to wait during the course of taxiing. When the aircraft fi is taxiing from node np to the next node nq, formula (5) is to be Tiq=Tip+Lpq/Vi:(6)LpqVimax⁡·Ripq-M1-Ripq≤Tiq-Tip∀fi∈F,∀np,nq∈N.Formula (6) restricts the taxiing speed of all aircraft. The speed of each aircraft must be less than the maximal speed.Formula (3)–(6) ensure that any aircraft fi must have an effective taxiing route from its gate to its runway entrance or from its runway exit to its gate and have a continuous taxiing route. However, the route generated here is random, not necessarily the optimal route. What is more, it may conflict with other aircraft during taxiing.(2) Taxiing Security Constraints. Aircraft taxiing on the airport surface usually produces three types of taxiing conflicts: the node conflict, rear-end conflict, and head-on conflict.Node Conflict. The interval time, at which the two aircraft go through the same node, does not meet the minimum safety requirements.Rear-End Conflict. When two aircraft taxi in the same direction on a taxiway, the faster trailing aircraft may overtake the leading aircraft.Head-On Conflict. When two aircraft taxi in the opposite direction on a taxiway, they have an encounter with each other.The taxiing safety constraints of aircraft are to ensure the safety of aircraft taxiing and avoid taxiing conflicts above:(7)ZijpTip+tije-Tjp≤0∀fi,fj∈F,np∈Ni∩Nj.Formula (7) ensures the safety interval of two taxiing aircraft. When two aircraft go through the same node, there must be a safety time interval between them. Safety time interval is related to aircraft type, wake turbulence separation, taxiing speed, and so on:(8)Zijp-Zijq≤2-Ripq+Rjpq∀fi,fj∈F,∀np,nq∈N,Zijp-Zijq≥-2+Ripq+Rjpq∀fi,fj∈F,∀np,nq∈N.Formula (8) can avoid rear-end conflicts during the taxiing of airport. The scene that one aircraft overtakes another must not occur during the taxiing:(9)Zijp-Zijq≤2-Ripq+Rjqp∀fi,fj∈F,∀np,nq∈N,Zijp-Zijq≤-2+Ripq+Rjqp∀fi,fj∈F,∀np,nq∈N.Formula (9) can avoid head-on conflicts during aircraft taxiing. An aircraft must not have an encounter with other aircraft in a certain taxiway during taxiing.(3) Runway Operation Constraints. The runway operation strategy has an important influence on the airport surface taxiing. The successive relationship between two aircraft using the same runway can be divided into four kinds: takeoff-takeoff, takeoff-landing, landing-takeoff, and landing-landing: (10)Tip+tijw-1-ZijpM≤Tjp∀fi,fj∈Fd,∀np∈Nr.Formula (10) ensures that in the case of takeoff-takeoff, two consecutive take-off aircraft must meet wake turbulence separation standards between them:(11)Tinkii+tijw-1-BijrM≤Tjn1j-Δ,∀fi∈Fd,∀fj∈Fa,∀nkii,n1j∈Nr.Formula (11) ensures that in the takeoff-landing process, two aircraft must meet the take-off wake turbulence separation standards. The take-off aircraft must leave the runway before the trailing lands on the runway. The starting taxiing time of landing aircraft fj equals the time difference of reaching the runway and runway occupancy time. If the starting taxiing time is Tjn1j, the time of landing on the runway is Tjn1j-Δ. According to the wake turbulence separation standards, formula (11) is got above:(12)Tin1i-1-BijrM≤Tjnkjj,∀fi∈Fa,∀fj∈Fd,∀n1i,nkjj∈Nr.Formula (12) ensures that, in the case of landing-takeoff, the take-off aircraft can enter the runway until the heading landing aircraft leaves the runway. The time of entrance to the runway for take-off aircraft fj at least equals the time the landing aircraft fi exiting the runway:(13)Tin1i-1-BijrM≤Tjnkjj,∀fi∈Fa,∀fj∈Fd,∀n1i,nkjj∈Nr.Formula (13) assures that, in the case of landing-landing, the two aircraft must meet the wake turbulence safety interval standards. The trailing aircraft cannot land on runway until the heading aircraft taxis off the runway.(4) Taxiing Time Constraints. The taxiing time constraints are used to ensure that the taxiing scheduling of aircraft should be in accordance with the requirements of flight schedule: (14)Tin1i≥ETAi∀fi∈Fa.Formula (14) ensures that the landing aircraft should begin to taxi after the estimated starting taxiing time:(15)Tin1i≥ETPi∀fi∈Fd,(16)Tinkii≤ETDi∀fi∈Fd.Formula (15) ensures that a take-off aircraft must start taxiing after its push-out time. Formula (16) requires aircraft to complete the taxiing and reach the runway entrance before the estimated take-off time.(5) Fairness Constraints. During the course of scheduling of aircraft, sometimes the route length of one airline’s aircraft is always much longer than other airlines, or the total delay is much larger than other airlines. Therefore, the fairness for various airlines needs to be taken into account during the taxiing route scheduling of aircraft. The Gini coefficient in the economics is introduced to restrain the fairness of taxiing scheduling and we use it to quantify the taxiing route fairness and delay fairness. The Gini coefficient can reflect the degree of unfairness for resources distribution. The smaller the value is, the more average the distribution is.As the runway and the gate of an aircraft are known, the shortest path of each aircraft is different. If we want to weigh the fairness of the taxiing route, simply comparing the taxiing route length of each aircraft cannot meet the actual requirements and is not enough as well. Therefore we introduce the concept of extra taxiing distance.Definition 1 (extra taxiing distance).
When the runway and the gate of an aircraft are known, we can get a shortest path for it. Extra taxiing distance is the difference distance between actual route length obtained by planning and the shortest route length. The extra taxiing distance is produced in order to avoid conflicts in the surface taxiing scheduling.
The fairness constraints of aircraft taxiing route are in essence to distribute the extra taxiing distance produced by scheduling between airlines. The smaller the Gini coefficient for airlines is, the more means the taxiing scheduling is. The extra taxiing distance of airlineα is as follows:(17)Da=∑i∈FaTLi-SLi.TLi is the actual length of taxiing route which is obtained by the planning schedule, so TLi=∑k=1ki-1Lnkink+1i. SLi is the shortest route from the starting point to the end, which could be obtained from the Dijkstra algorithm.
The Gini coefficient is defined and calculated as follows:(18)G1=1+∑a∈ApaDa-2∑a∈A∑pa¯Da.Letting G1 be less than a small constraint parameter value ε1, the fairness constraint based on taxiing length could be established as follows:(19)1+∑a∈ApaDa-2∑a∈A∑pa¯Da≤ε1.Formula (19) ensures the fairness of taxiing route length:(20)G2=1+∑a∈ApaDTa-2∑a∈A∑pa¯DTa,(21)1+∑a∈ApaDTa-2∑a∈A∑pa¯DTa≤ε2.Similarly, formula (21) ensures the fairness of waiting delay of all the aircraft.


## 4. Simulation

At the beginning of simulation, we create the surface taxiing route sets for all landing and take-off aircraft. On this basis, we encode for the characteristic of airport surface taxiing scheduling, design an improved genetic algorithm, use the actual data of an airport for simulation and analysis, and compare the results with the results of the ant colony optimization.


### 4.1. Establish Taxiing Route Sets

Establishing surface taxiing route sets is to get the shortest feasible routes for each aircraft from the origin to destination. Aircraft with different origins or destinations need different route sets. The aircraft surface taxiing route problem can be abstracted into point-to-point problem, and Dijkstra algorithm can generate the shortest route for any single aircraft. However, the dynamic scheduling of surface taxiing requires multiple different taxiing routes to meet their demands. TheK shortest path method [22] is used to generate the first K shortest taxiing routes to establish the set of taxiing routes in the paper.


### 4.2. The Improved Genetic Algorithm

The improved genetic algorithm (IGA) for the surface taxiing scheduling is introduced in this section.


#### 4.2.1. Gene Encoding

Selecting gene encoding has an important impact on the design and solution of the genetic algorithm. As aircraft surface taxiing scheduling is extremely complex, simply using the aircraft taxiing route nodes as a chromosome coding accepted by most general genetic algorithm will likely cause a single chromosome to be huge. In addition, the crossover and mutation manipulation will destroy the existing sequence of nodes, which can result in that the adjacent nodes in the sequence are not reachable in real network. Therefore, the paper designs the improved encoding as follows.In the improved encoding, dual-chromosome is adopted. The length of the chromosome is equal to the number of aircraft needed to be scheduled. A chromosome consists of two rows. One is the aircraft taxiing route sequence number row and the other is the aircraft waiting delay time row. We can use only a chromosome to express the taxiing route and the scheduling for all aircraft. Letting the number of aircraft bei, then the chromosome can be expressed as P=R→,T→, where R→=R1,R2,…,Ri and T→=T1,T2,…,Ti. For example, R1 is the R1st route for the 1st aircraft in the corresponding route set. T1 represents waiting delay time for the 1st aircraft. It cannot exceed the maximum waiting delay time, so Ti∈0,Max⁡Delay. This encoding mode not only is fit for the characteristics of aircraft surface taxiing scheduling, but also is easier for the achievement of crossover and mutation manipulation.


#### 4.2.2. The Fitness Function

Population initialization can be generated by the random method, and then we can calculate the individual fitness. According to the characteristics of aircraft taxiing route scheduling, the fitness function designed should take account of the cost of aircraft taxiing (the total taxiing time), the aircraft average waiting delay time, and the number of conflict points:(22)fitness=2*f+t+800*c.According to information of taxiing route line in the chromosome, each aircraft’s taxiing time can be calculated, as well as the total taxiing time f of all aircraft.The average waiting delay time of an aircraftt can be obtained according to waiting delay information in the second row of the chromosome. Each aircraft waiting delay should be as less as possible.Aircraft taxiing with no conflict is the key of aircraft taxiing scheduling. Thec indicates the number of taxiing conflict points. According to chromosomes information, the landing time of each aircraft at each node can be calculated first, and then the number of taxiing conflict points can be obtained based on formula (7) to formula (13). When two aircraft taxi in violation of any safety spatial or temporal requirement, a conflict is recorded. Because in the final aircraft taxiing route scheduling there must be no conflict, this parameter should be set to a larger weight in the simulation.Two methods are adopted to resolve aircraft taxiing route conflicts in taxiing: one is to control the taxiing time of aircraft in the system, and the other is to select one taxiing route dynamically from the predetermined route set. In the paper, the IGA simultaneously uses these two methods to solve the taxiing conflicts. Under the premise of no taxiing conflict in the whole airport surface, we minimize the taxiing cost and waiting delay time for all aircraft in the planning period.


#### 4.2.3. Genetic Manipulation

Based on the above chromosome encoding and fitness calculation, the genetic manipulations can be done. Genetic manipulations mainly include selection, crossover, and mutation. The reinsertion process is added to select the new generation. The selection manipulation takes the random competing selection method. The crossover manipulation takes one-point crossover. According to the needs of the aircraft taxiing route scheduling, the improvements of the genetic manipulation are mainly reflected in two aspects: the reinsertion manipulation and the mutation manipulation.Mutation Manipulation. In the paper, two mutation methods are used. One is a standard mutation based on aircraft taxiing route and waiting delay time. Namely, regular mutation is done on the first row of taxiing route and the second row of waiting delay time of the chromosome. The other is biased mutation based on waiting delay time. A random waiting time α is imposed to the chromosome delay row, α∈-a,b∣a>b>0, such that α∈-6,2. As α is a random number in -6,2, it is always biased negative. After adding the number to the chromosome, the aircraft waiting delay time can bias the direction of decreasing. This method can speed up the time that the individual with a small delay appears.Reinsertion Manipulation. Reinsertion manipulation means replacing the most unsuited individuals in the previous generation of populations by the new suited individuals based on the fitness value. Because the aircraft surface taxiing route is quite complex, easily resulting in conflict points, and most individuals of the resulting generation are worse than the parent generation, the paper introduces the reinsertion manipulation. By reinsertion manipulation, we can use the small number of new individuals with the best fitness value to replace the corresponding number of individuals in the previous generation of population which could maximize the retention of superior individuals in the parent generation.The main flowchart of the improved genetic algorithm used in the paper is shown in Figure1.Figure 1
The main flowchart of the improved genetic algorithm.


### 4.3. Simulation Data

In the paper, some part of airfield configuration diagram of a large airport is used here (Figure2), which contains 37 nodes and 48 edges, two independently running runways and three gate zones (T1, T2, and T3).Figure 2
Part of airfield configuration of a large airport’s taxiways and runways.During the simulation, the paper first established a set with a certain number (set 15) between each gate and each runway threshold or between each runway exit and each gate zone. For example, according to Figure2, we can establish a set with 15 taxiing routes for exit of runway 1 (node 32) and gate zone T1 (node 35). By permutations of the runways and gate zones known, we can get 12 sets and total 180 taxiing routes.Assume that the taxiing speed of aircraft in taxiing way is 10 m/s; the minimum safety distance is 200 m; aircraft runway occupancy time is 30 s; the capacity of two taxiing way direct connected nodesCpq=1; wake turbulence separation criterion is 2 minutes.Genetic Parameters. The generation gap GGAP=0.8, crossover probability XOVR=0.6, mutation probability routine PM1=0.1, biased mutation probability PM2=0.5, biased mutation random waiting time α∈-20,10, genetic generations MAXGEN=200, population size NIND=40, the maximum allowable waiting time DETIME=30 min, and the probability of reinsertion RX=0.2.Fairness Parameters. Consider ε1=0.35, ε2=0.35.In the aircraft scheduling simulation, assume that there are 20 aircraft needed to be scheduled. The estimated landing time of arrivals and the estimated time of push-out for departures are the time whent=0 s. The estimated time for departures must meet the maximum allowable waiting time. Information about the arrivals and departures is shown in Table 1.Table 1
Information of landing and take-off aircraft.
Aircraft number
Airline
Arrival/departure
Gate zone
Runway
1
A
1
Departure
T
1
1
2
A
2
Departure
T
1
2
3
A
3
Departure
T
1
2
4
A
1
Departure
T
2
1
5
A
2
Departure
T
2
1
6
A
3
Departure
T
2
2
7
A
2
Departure
T
3
1
8
A
1
Departure
T
3
1
9
A
2
Departure
T
3
2
10
A
3
Departure
T
3
2
11
A
1
Arrival
T
1
1
12
A
2
Arrival
T
1
1
13
A
3
Arrival
T
1
2
14
A
2
Arrival
T
2
1
15
A
2
Arrival
T
2
1
16
A
1
Arrival
T
2
2
17
A
3
Arrival
T
2
2
18
A
2
Arrival
T
3
1
19
A
1
Arrival
T
3
2
20
A
2
Arrival
T
3
2


### 4.4. Simulation Results

#### 4.4.1. Analysis of Algorithm Performance

Using MATLAB to code the IGA and based on the surface data of one of our country’s large airports, we simulate the model established above. The evolution of the genetic algorithm is shown in Figure3.Figure 3
The evolutionary process of the IGA.The evolutionary process of the IGA shows that in the first 20 generations the evolution of the population converges rapidly, and after 70 generations, the evolution levels off. After 140 iterations, the average fitness value of the population and the fitness value of the best individual start stabilizing. It takes 7 minutes and 55 seconds to run the program, which could meet the timeliness requirements of resources operating and scheduling on airport surface.


#### 4.4.2. Analysis of Simulation Results

Through the simulation, we can get the best individual in the last generation population. Meanwhile, the paper selects a scheduling result through the ant colony optimization (ACO) to contrast the simulation results, which is shown in Table2.Table 2
The comparison of results between IGA and ACO.
Aircraft number
IGA
ACO
Route number
Waiting delay time/s
Route number
Waiting delay time/s
1
12
1773
11
545
2
26
0
23
0
3
26
681
25
1657
4
33
588
31
1520
5
39
0
40
135
6
50
464
53
298
7
71
1041
73
1297
8
62
1299
73
1059
9
85
897
78
0
10
83
1200
89
1761
11
92
1305
103
1285
12
101
189
105
743
13
120
1771
119
1400
14
134
909
121
927
15
134
0
130
0
16
148
0
144
975
17
137
569
139
0
18
157
378
159
355
19
175
410
177
1764
20
178
133
171
1608
Note. Due to the paper length, the path 12 sets with 180 routes cannot be fully demonstrated here.IGA and ACO are both conflict-free scheduling methods. In the two methods, each aircraft has a taxiing route and waiting delay time. We can see from Table2, in the IGA, that 4 aircraft start taxiing with no waiting delay, waiting delay time of 9 aircraft is within 500 s, and waiting delay of 2 aircraft is longer than 1500 s. In the ACO, 4 aircraft have no waiting delays, but only waiting delay of 7 aircraft is within 500 s and waiting delay of 5 aircraft is longer than 1500 s. Therefore, the simulation results of IGA are better than the results of ACO in the taxiing route scheduling.According to the aircraft taxiing scheduling results in Table2 and the route sets, we can get the specific and detailed scheduling for aircraft’s taxiing in the IGA, including the node which each aircraft passes through and the time of arriving at each node in Table 3.Table 3
The specific and detailed scheduling results for aircraft taxiing in IGA.
Aircraft number
The nodes and the arrival time
1
35
23
22
20
18
17
14
12
10
8
6
4
3
2
1
31
1773
1780
1788
1841
1846
1872
1880
1912
1947
1982
2043
2103
2175
2184
2197
2214
2
35
23
25
28
29
30
33
0
7
34
67
97
133
160
3
35
23
25
28
29
30
33
681
688
715
784
778
814
841
4
36
19
14
12
10
8
6
7
5
2
1
31
588
594
620
652
687
722
783
792
852
924
937
954
5
36
19
18
17
14
12
10
8
6
4
5
2
1
31
0
6
14
40
48
80
115
150
211
271
280
352
365
382
6
36
19
21
20
22
24
25
28
29
30
33
464
470
502
510
536
563
571
604
634
670
697
7
37
10
8
6
7
5
4
3
2
1
31
1041
1054
1089
1150
1159
1219
1228
1300
1309
1322
1339
8
7
10
8
6
4
5
2
1
31
1299
1312
1347
1408
1468
1477
1549
1562
1579
9
37
10
12
14
19
18
20
22
23
25
28
29
30
33
897
910
945
977
1003
1011
1043
1069
1077
1104
1137
1167
1203
1230
10
37
10
12
14
19
18
20
22
24
25
28
29
30
33
1200
1213
1248
1280
1306
1314
1346
1372
1399
1407
1440
1470
1506
1533
11
32
11
10
12
14
17
18
20
22
23
35
1305
1367
1377
1412
1444
1452
1478
1510
1536
1544
1551
12
32
11
13
15
14
17
18
20
22
23
35
189
251
286
318
328
336
362
394
420
428
435
13
34
27
26
28
25
23
35
1771
1795
1914
1929
1962
1989
1996
14
32
11
13
15
16
17
14
19
36
909
971
1006
1038
1046
1056
1064
1090
1096
15
32
11
13
15
16
17
14
19
36
0
62
97
129
137
147
155
181
187
16
34
27
26
24
25
23
22
20
21
19
36
0
24
143
175
183
210
218
244
252
284
290
17
34
27
26
24
22
20
21
19
36
569
593
712
744
771
797
805
837
843
18
32
11
10
37
378
440
450
463
19
34
27
26
24
22
20
18
19
14
15
13
11
10
37
410
434
553
585
612
638
670
678
704
714
746
781
791
804
20
34
27
26
24
22
23
21
19
14
15
13
11
10
37
133
157
276
308
335
343
369
401
427
437
469
504
514
527
Note. In the table, the up row indicates the upstream route nodes for each aircraft going through; the down row indicates the time reaching each node.The comparisons and statistics of taxiing route and waiting delay time for each aircraft are shown in Table4. The shortest route (SHR), length of taxiing route (LTR), the extra taxiing distance (EXTD), and the waiting delay time (WDT) information are shown in Table 4.Table 4
The comparisons and statistics of aircraft taxiing.
Aircraft number
Airline
SHR/m
IGA
ACO
LTR/m
EXTD/m
WDT/s
LTR/m
EXTD/m
WDT/s
1
1
4250
4410
160
1773
4420
170
545
2
2
1600
1600
0
0
1760
160
0
3
3
1600
1600
0
681
2340
740
1657
4
1
3660
3660
0
588
3660
0
1520
5
2
3660
3820
160
0
3820
160
135
6
3
2170
2330
160
464
2330
160
298
7
2
2800
2980
180
1041
2990
190
1297
8
1
2800
2800
0
1299
2990
190
1059
9
2
3170
3330
160
897
3390
220
0
10
3
3170
3330
160
1200
3330
160
1761
11
1
2300
2460
160
1305
2460
160
1285
12
2
2300
2460
160
189
2460
160
743
13
3
2170
2250
80
1771
2170
0
1400
14
2
1710
1870
160
909
1710
0
927
15
2
1710
1870
160
0
1710
0
0
16
1
2740
2900
160
0
2980
240
975
17
3
2740
2740
0
569
2740
0
0
18
2
850
850
0
378
2190
1340
355
19
1
3740
3940
200
410
3940
200
1764
20
2
3740
3940
200
133
3820
80
1608
Total
52880
55140
2260
13607
57210
4330
17329From Table4, we can see that, in the IGA, the aircraft 2, 3, 4, 8, 17, and 18 all select the shortest route, greatly reducing the cost of taxiing. And to avoid conflicts, the other aircraft do not select the shortest route which leads to extra taxiing costs. In the ACO, only five aircraft choose the shortest route.From Table4, in the ACO, the total taxiing distance is 57210 m, the total extra taxiing route is 4330 m, and the total waiting delay time is 17329 s. In the IGA of this paper, the total taxiing distance is 55140 m; the total extra taxiing route is 2260 m, which is 47.8% lower than the ACO; the total delay time is 13607 s, which is reduced by 21.5% compared with the ACO, as seen in Figure 4. The advantages of the IGA have been shown. In the specially designed genetic algorithm for surface taxiing scheduling, enough diverse individuals are generated through crossover and mutation manipulation, and excellent variation individuals will enter into the next generation with greater proportion through the selection and reinsertion manipulation. The evolution of the IGA would go in the direction of no conflict, less waiting delay time, and less extra taxiing distance.Figure 4
Comparison of aircraft’s taxiing scheduling in IGA and ACO.According to the simulation results in Table4, we can draw the contrastive analysis diagram of the aircraft taxiing distance and the extra taxiing route in the IGA and ACO, which is shown in Figures 5 and 6.Figure 5
Comparison of taxiing route of aircraft in IGA and ACO.Figure 6
Comparison of the extra taxiing distance of aircraft in IGA and ACO.From Figures5 and 6, compared with the ACO, the results of the IGA are that each aircraft selects a shorter taxiing route as possible, and the taxiing distance is significantly reduced, especially for the extra taxiing route distance. From Figures 5 and 6, it can be seen that, in the IGA, the taxiing distance of 6 aircraft is reduced, 10 aircraft are constant, and 4 aircraft are increased. However, due to a big margin reduced in aircraft 3 and aircraft 18, the total extra taxiing distance reduces by 47.8% compared with the ACO. The IGA reduces the overall taxiing route distance and operating cost effectively. The 47.8% decrease is mainly caused by the concept of the extra taxiing distance. According to the concept, the extra taxiing distance could be reduced to zero with 100% decrease, if all aircraft taxi with their shortest taxiing route. That is to say, not all aircraft have extra taxiing distance. If some (not too many) aircraft’s routes are improved, obvious reflection will be shown in this value.According to Table4, the contrastive analysis diagram of the waiting delay time can also be obtained in Figure 7.Figure 7
Comparison of the waiting delay time of aircraft in IGA and ACO.Waiting delay time refers to the time postponed off the scheduling. The delay time is the difference between the time an aircraft actually begins to enter the surface taxiway system and the earliest possible time it can enter the taxiing system. Table2 and Figure 7 show that, in the IGA, at the time t=0 s, landing aircraft 2 and aircraft 5 leave gate 35 (T1) and gate 36 (T2), respectively, and taking-off aircraft 15 and aircraft 16 leave the runway 1 (exit node 32) and runway 2 (exit node 34), respectively. Therefore, 4 aircraft start to taxi simultaneously. Aircraft 1 is the last aircraft to begin taxiing at the time 1773 s. But it meets the condition that all aircraft can finish the taxiing or begin taxiing in the interval of 30 minutes. Compared with the ACO, 9 aircraft are shortened on waiting delay time, 5 aircraft are unchanged, and 6 aircraft are longer. On the whole, the IGA reduces the aircraft waiting delay time and improves the efficiency of airport surface.The optimizing model provides a seamless connection between taxiway and runway. Runway queuing and scheduling are integrated into the model. The model considers different stakeholders’ requirements, ensuring the safety of airport surface movement, reducing delay and taxiing cost, and improving the utilization efficiency of airport resources. The genetic algorithm used here is greatly improved which is more suitable for the airport surface taxiing scheduling problem and the optimizing model. In the IGA, aircraft could change the initial taxiing time and the taxiing route to optimize the taxiing and scheduling in large data search space rapidly as shown in the results.


#### 4.4.3. The Gini Coefficient and Fairness Analysis for Airlines

(1) Analysis of Scheduling Fairness. According to Table 4, we can calculate the extra taxiing distance (EXTD), the average extra taxiing distance (AETD), the waiting delay time (WDT), and the average waiting delay time (AWDT) for each airline in Table 5 and Figure 8.Table 5
Comparison of the scheduling taxiing route between IGA and ACO.
Airline
Number of aircraft
IGA
ACO
EXTD/m
AETD/m
AWDT/s
AWDT/s
EXTD/m
AETD/m
WDT/s
AWDT/s
1
6
680
113.3
5375
895.8
960
160
7148
1191.3
2
9
1180
131.1
3547
394.1
2310
256.7
5065
562.8
3
5
400
80
4685
937.0
1060
212
5116
1023.2
Gini coefficient
0.3412
0.3422
0.2886
0.4351Figure 8
Analysis on taxiing scheduling of airlines.It can be seen in Table5 and Figure 8, in the IGA, that the average extra taxiing distances of each airline are 113.3 m, 131.1 m, and 80 m, respectively. The Gini coefficient of extra taxiing distance is 0.3412. The average delay time of each airline is 895.8 s, 394.1 s, and 937 s, respectively. The Gini coefficient of the average waiting delay time is 0.3422. Both Gini coefficients meet the requirement within a reasonable range. In the ACO, the Gini coefficient of extra taxiing distance is 0.2886; it is fair but the overall extra distance is too long. The Gini coefficient of the average waiting delay time is 0.4351, which exceeds the required value 0.35. The results indicate that the distribution of the delay between airlines is not fair enough.The optimizing model considers the fairness of scheduling, and the IGA could well finish the solving. The extra taxiing distance and waiting delay time are distributed between airlines fairly. Thus, the interests of various airlines are protected.(2) Impact Analysis on Different Fairness Parameters. The paper mainly analyzes the impact of the two fairness constraint parameters on optimization results. In order to control variables, we set ε1 or ε2 to be 1 and the other to be 0.25, 0.3, and 0.35, respectively. For example, let ε2=1 in the optimization, and the optimization results and properties are shown in Table 6. The average extra taxiing distance and the average waiting delay time of each airline are shown in Table 7 and Figure 9.Table 6
Optimization results of taxiing route with different parameters.
ε
2
=
1
,
ε
1
Total extra taxiing distance/m
Total waiting delay time/s
0.25
2930
14312
0.3
2930
13782
0.35
1569
12468Table 7
Optimization results of each airline with different parameters.
ε
2
=
1
Average taxiing distance
Average waiting delay time
Airline
ε
1
0.25
0.3
0.35
0.25
0.3
0.35
1
101.7
101.7
113.3
570.5
898.5
895.8
2
122.2
164.4
131.1
586.2
394.1
394.1
3
244
168
80
1122.6
968.8
937Figure 9
Optimization results of taxiing scheduling for each airline with different parameters.From Table6, we can see that, with the increase of Gini coefficient (ε2) controlling the delay fairness (namely, fairness reduced), the total extra taxiing distance and the total waiting delay time are falling (namely, efficiency increased). Table 7 and Figure 9 also show that the average extra taxiing distance and the average waiting delay time for each airline are decreasing. This illustrates that the efficiency and fairness of scheduling are mutually affected and restricted. So the selection of fairness parameter values has an important impact on the entire scheduling optimization results.


## 4.1. Establish Taxiing Route Sets

Establishing surface taxiing route sets is to get the shortest feasible routes for each aircraft from the origin to destination. Aircraft with different origins or destinations need different route sets. The aircraft surface taxiing route problem can be abstracted into point-to-point problem, and Dijkstra algorithm can generate the shortest route for any single aircraft. However, the dynamic scheduling of surface taxiing requires multiple different taxiing routes to meet their demands. TheK shortest path method [22] is used to generate the first K shortest taxiing routes to establish the set of taxiing routes in the paper.


## 4.2. The Improved Genetic Algorithm

The improved genetic algorithm (IGA) for the surface taxiing scheduling is introduced in this section.


### 4.2.1. Gene Encoding

Selecting gene encoding has an important impact on the design and solution of the genetic algorithm. As aircraft surface taxiing scheduling is extremely complex, simply using the aircraft taxiing route nodes as a chromosome coding accepted by most general genetic algorithm will likely cause a single chromosome to be huge. In addition, the crossover and mutation manipulation will destroy the existing sequence of nodes, which can result in that the adjacent nodes in the sequence are not reachable in real network. Therefore, the paper designs the improved encoding as follows.In the improved encoding, dual-chromosome is adopted. The length of the chromosome is equal to the number of aircraft needed to be scheduled. A chromosome consists of two rows. One is the aircraft taxiing route sequence number row and the other is the aircraft waiting delay time row. We can use only a chromosome to express the taxiing route and the scheduling for all aircraft. Letting the number of aircraft bei, then the chromosome can be expressed as P=R→,T→, where R→=R1,R2,…,Ri and T→=T1,T2,…,Ti. For example, R1 is the R1st route for the 1st aircraft in the corresponding route set. T1 represents waiting delay time for the 1st aircraft. It cannot exceed the maximum waiting delay time, so Ti∈0,Max⁡Delay. This encoding mode not only is fit for the characteristics of aircraft surface taxiing scheduling, but also is easier for the achievement of crossover and mutation manipulation.


### 4.2.2. The Fitness Function

Population initialization can be generated by the random method, and then we can calculate the individual fitness. According to the characteristics of aircraft taxiing route scheduling, the fitness function designed should take account of the cost of aircraft taxiing (the total taxiing time), the aircraft average waiting delay time, and the number of conflict points:(22)fitness=2*f+t+800*c.According to information of taxiing route line in the chromosome, each aircraft’s taxiing time can be calculated, as well as the total taxiing time f of all aircraft.The average waiting delay time of an aircraftt can be obtained according to waiting delay information in the second row of the chromosome. Each aircraft waiting delay should be as less as possible.Aircraft taxiing with no conflict is the key of aircraft taxiing scheduling. Thec indicates the number of taxiing conflict points. According to chromosomes information, the landing time of each aircraft at each node can be calculated first, and then the number of taxiing conflict points can be obtained based on formula (7) to formula (13). When two aircraft taxi in violation of any safety spatial or temporal requirement, a conflict is recorded. Because in the final aircraft taxiing route scheduling there must be no conflict, this parameter should be set to a larger weight in the simulation.Two methods are adopted to resolve aircraft taxiing route conflicts in taxiing: one is to control the taxiing time of aircraft in the system, and the other is to select one taxiing route dynamically from the predetermined route set. In the paper, the IGA simultaneously uses these two methods to solve the taxiing conflicts. Under the premise of no taxiing conflict in the whole airport surface, we minimize the taxiing cost and waiting delay time for all aircraft in the planning period.


### 4.2.3. Genetic Manipulation

Based on the above chromosome encoding and fitness calculation, the genetic manipulations can be done. Genetic manipulations mainly include selection, crossover, and mutation. The reinsertion process is added to select the new generation. The selection manipulation takes the random competing selection method. The crossover manipulation takes one-point crossover. According to the needs of the aircraft taxiing route scheduling, the improvements of the genetic manipulation are mainly reflected in two aspects: the reinsertion manipulation and the mutation manipulation.Mutation Manipulation. In the paper, two mutation methods are used. One is a standard mutation based on aircraft taxiing route and waiting delay time. Namely, regular mutation is done on the first row of taxiing route and the second row of waiting delay time of the chromosome. The other is biased mutation based on waiting delay time. A random waiting time α is imposed to the chromosome delay row, α∈-a,b∣a>b>0, such that α∈-6,2. As α is a random number in -6,2, it is always biased negative. After adding the number to the chromosome, the aircraft waiting delay time can bias the direction of decreasing. This method can speed up the time that the individual with a small delay appears.Reinsertion Manipulation. Reinsertion manipulation means replacing the most unsuited individuals in the previous generation of populations by the new suited individuals based on the fitness value. Because the aircraft surface taxiing route is quite complex, easily resulting in conflict points, and most individuals of the resulting generation are worse than the parent generation, the paper introduces the reinsertion manipulation. By reinsertion manipulation, we can use the small number of new individuals with the best fitness value to replace the corresponding number of individuals in the previous generation of population which could maximize the retention of superior individuals in the parent generation.The main flowchart of the improved genetic algorithm used in the paper is shown in Figure1.Figure 1
The main flowchart of the improved genetic algorithm.


## 4.2.1. Gene Encoding

Selecting gene encoding has an important impact on the design and solution of the genetic algorithm. As aircraft surface taxiing scheduling is extremely complex, simply using the aircraft taxiing route nodes as a chromosome coding accepted by most general genetic algorithm will likely cause a single chromosome to be huge. In addition, the crossover and mutation manipulation will destroy the existing sequence of nodes, which can result in that the adjacent nodes in the sequence are not reachable in real network. Therefore, the paper designs the improved encoding as follows.In the improved encoding, dual-chromosome is adopted. The length of the chromosome is equal to the number of aircraft needed to be scheduled. A chromosome consists of two rows. One is the aircraft taxiing route sequence number row and the other is the aircraft waiting delay time row. We can use only a chromosome to express the taxiing route and the scheduling for all aircraft. Letting the number of aircraft bei, then the chromosome can be expressed as P=R→,T→, where R→=R1,R2,…,Ri and T→=T1,T2,…,Ti. For example, R1 is the R1st route for the 1st aircraft in the corresponding route set. T1 represents waiting delay time for the 1st aircraft. It cannot exceed the maximum waiting delay time, so Ti∈0,Max⁡Delay. This encoding mode not only is fit for the characteristics of aircraft surface taxiing scheduling, but also is easier for the achievement of crossover and mutation manipulation.


## 4.2.2. The Fitness Function

Population initialization can be generated by the random method, and then we can calculate the individual fitness. According to the characteristics of aircraft taxiing route scheduling, the fitness function designed should take account of the cost of aircraft taxiing (the total taxiing time), the aircraft average waiting delay time, and the number of conflict points:(22)fitness=2*f+t+800*c.According to information of taxiing route line in the chromosome, each aircraft’s taxiing time can be calculated, as well as the total taxiing time f of all aircraft.The average waiting delay time of an aircraftt can be obtained according to waiting delay information in the second row of the chromosome. Each aircraft waiting delay should be as less as possible.Aircraft taxiing with no conflict is the key of aircraft taxiing scheduling. Thec indicates the number of taxiing conflict points. According to chromosomes information, the landing time of each aircraft at each node can be calculated first, and then the number of taxiing conflict points can be obtained based on formula (7) to formula (13). When two aircraft taxi in violation of any safety spatial or temporal requirement, a conflict is recorded. Because in the final aircraft taxiing route scheduling there must be no conflict, this parameter should be set to a larger weight in the simulation.Two methods are adopted to resolve aircraft taxiing route conflicts in taxiing: one is to control the taxiing time of aircraft in the system, and the other is to select one taxiing route dynamically from the predetermined route set. In the paper, the IGA simultaneously uses these two methods to solve the taxiing conflicts. Under the premise of no taxiing conflict in the whole airport surface, we minimize the taxiing cost and waiting delay time for all aircraft in the planning period.


## 4.2.3. Genetic Manipulation

Based on the above chromosome encoding and fitness calculation, the genetic manipulations can be done. Genetic manipulations mainly include selection, crossover, and mutation. The reinsertion process is added to select the new generation. The selection manipulation takes the random competing selection method. The crossover manipulation takes one-point crossover. According to the needs of the aircraft taxiing route scheduling, the improvements of the genetic manipulation are mainly reflected in two aspects: the reinsertion manipulation and the mutation manipulation.Mutation Manipulation. In the paper, two mutation methods are used. One is a standard mutation based on aircraft taxiing route and waiting delay time. Namely, regular mutation is done on the first row of taxiing route and the second row of waiting delay time of the chromosome. The other is biased mutation based on waiting delay time. A random waiting time α is imposed to the chromosome delay row, α∈-a,b∣a>b>0, such that α∈-6,2. As α is a random number in -6,2, it is always biased negative. After adding the number to the chromosome, the aircraft waiting delay time can bias the direction of decreasing. This method can speed up the time that the individual with a small delay appears.Reinsertion Manipulation. Reinsertion manipulation means replacing the most unsuited individuals in the previous generation of populations by the new suited individuals based on the fitness value. Because the aircraft surface taxiing route is quite complex, easily resulting in conflict points, and most individuals of the resulting generation are worse than the parent generation, the paper introduces the reinsertion manipulation. By reinsertion manipulation, we can use the small number of new individuals with the best fitness value to replace the corresponding number of individuals in the previous generation of population which could maximize the retention of superior individuals in the parent generation.The main flowchart of the improved genetic algorithm used in the paper is shown in Figure1.Figure 1
The main flowchart of the improved genetic algorithm.


## 4.3. Simulation Data

In the paper, some part of airfield configuration diagram of a large airport is used here (Figure2), which contains 37 nodes and 48 edges, two independently running runways and three gate zones (T1, T2, and T3).Figure 2
Part of airfield configuration of a large airport’s taxiways and runways.During the simulation, the paper first established a set with a certain number (set 15) between each gate and each runway threshold or between each runway exit and each gate zone. For example, according to Figure2, we can establish a set with 15 taxiing routes for exit of runway 1 (node 32) and gate zone T1 (node 35). By permutations of the runways and gate zones known, we can get 12 sets and total 180 taxiing routes.Assume that the taxiing speed of aircraft in taxiing way is 10 m/s; the minimum safety distance is 200 m; aircraft runway occupancy time is 30 s; the capacity of two taxiing way direct connected nodesCpq=1; wake turbulence separation criterion is 2 minutes.Genetic Parameters. The generation gap GGAP=0.8, crossover probability XOVR=0.6, mutation probability routine PM1=0.1, biased mutation probability PM2=0.5, biased mutation random waiting time α∈-20,10, genetic generations MAXGEN=200, population size NIND=40, the maximum allowable waiting time DETIME=30 min, and the probability of reinsertion RX=0.2.Fairness Parameters. Consider ε1=0.35, ε2=0.35.In the aircraft scheduling simulation, assume that there are 20 aircraft needed to be scheduled. The estimated landing time of arrivals and the estimated time of push-out for departures are the time whent=0 s. The estimated time for departures must meet the maximum allowable waiting time. Information about the arrivals and departures is shown in Table 1.Table 1
Information of landing and take-off aircraft.
Aircraft number
Airline
Arrival/departure
Gate zone
Runway
1
A
1
Departure
T
1
1
2
A
2
Departure
T
1
2
3
A
3
Departure
T
1
2
4
A
1
Departure
T
2
1
5
A
2
Departure
T
2
1
6
A
3
Departure
T
2
2
7
A
2
Departure
T
3
1
8
A
1
Departure
T
3
1
9
A
2
Departure
T
3
2
10
A
3
Departure
T
3
2
11
A
1
Arrival
T
1
1
12
A
2
Arrival
T
1
1
13
A
3
Arrival
T
1
2
14
A
2
Arrival
T
2
1
15
A
2
Arrival
T
2
1
16
A
1
Arrival
T
2
2
17
A
3
Arrival
T
2
2
18
A
2
Arrival
T
3
1
19
A
1
Arrival
T
3
2
20
A
2
Arrival
T
3
2


## 4.4. Simulation Results

### 4.4.1. Analysis of Algorithm Performance

Using MATLAB to code the IGA and based on the surface data of one of our country’s large airports, we simulate the model established above. The evolution of the genetic algorithm is shown in Figure3.Figure 3
The evolutionary process of the IGA.The evolutionary process of the IGA shows that in the first 20 generations the evolution of the population converges rapidly, and after 70 generations, the evolution levels off. After 140 iterations, the average fitness value of the population and the fitness value of the best individual start stabilizing. It takes 7 minutes and 55 seconds to run the program, which could meet the timeliness requirements of resources operating and scheduling on airport surface.


### 4.4.2. Analysis of Simulation Results

Through the simulation, we can get the best individual in the last generation population. Meanwhile, the paper selects a scheduling result through the ant colony optimization (ACO) to contrast the simulation results, which is shown in Table2.Table 2
The comparison of results between IGA and ACO.
Aircraft number
IGA
ACO
Route number
Waiting delay time/s
Route number
Waiting delay time/s
1
12
1773
11
545
2
26
0
23
0
3
26
681
25
1657
4
33
588
31
1520
5
39
0
40
135
6
50
464
53
298
7
71
1041
73
1297
8
62
1299
73
1059
9
85
897
78
0
10
83
1200
89
1761
11
92
1305
103
1285
12
101
189
105
743
13
120
1771
119
1400
14
134
909
121
927
15
134
0
130
0
16
148
0
144
975
17
137
569
139
0
18
157
378
159
355
19
175
410
177
1764
20
178
133
171
1608
Note. Due to the paper length, the path 12 sets with 180 routes cannot be fully demonstrated here.IGA and ACO are both conflict-free scheduling methods. In the two methods, each aircraft has a taxiing route and waiting delay time. We can see from Table2, in the IGA, that 4 aircraft start taxiing with no waiting delay, waiting delay time of 9 aircraft is within 500 s, and waiting delay of 2 aircraft is longer than 1500 s. In the ACO, 4 aircraft have no waiting delays, but only waiting delay of 7 aircraft is within 500 s and waiting delay of 5 aircraft is longer than 1500 s. Therefore, the simulation results of IGA are better than the results of ACO in the taxiing route scheduling.According to the aircraft taxiing scheduling results in Table2 and the route sets, we can get the specific and detailed scheduling for aircraft’s taxiing in the IGA, including the node which each aircraft passes through and the time of arriving at each node in Table 3.Table 3
The specific and detailed scheduling results for aircraft taxiing in IGA.
Aircraft number
The nodes and the arrival time
1
35
23
22
20
18
17
14
12
10
8
6
4
3
2
1
31
1773
1780
1788
1841
1846
1872
1880
1912
1947
1982
2043
2103
2175
2184
2197
2214
2
35
23
25
28
29
30
33
0
7
34
67
97
133
160
3
35
23
25
28
29
30
33
681
688
715
784
778
814
841
4
36
19
14
12
10
8
6
7
5
2
1
31
588
594
620
652
687
722
783
792
852
924
937
954
5
36
19
18
17
14
12
10
8
6
4
5
2
1
31
0
6
14
40
48
80
115
150
211
271
280
352
365
382
6
36
19
21
20
22
24
25
28
29
30
33
464
470
502
510
536
563
571
604
634
670
697
7
37
10
8
6
7
5
4
3
2
1
31
1041
1054
1089
1150
1159
1219
1228
1300
1309
1322
1339
8
7
10
8
6
4
5
2
1
31
1299
1312
1347
1408
1468
1477
1549
1562
1579
9
37
10
12
14
19
18
20
22
23
25
28
29
30
33
897
910
945
977
1003
1011
1043
1069
1077
1104
1137
1167
1203
1230
10
37
10
12
14
19
18
20
22
24
25
28
29
30
33
1200
1213
1248
1280
1306
1314
1346
1372
1399
1407
1440
1470
1506
1533
11
32
11
10
12
14
17
18
20
22
23
35
1305
1367
1377
1412
1444
1452
1478
1510
1536
1544
1551
12
32
11
13
15
14
17
18
20
22
23
35
189
251
286
318
328
336
362
394
420
428
435
13
34
27
26
28
25
23
35
1771
1795
1914
1929
1962
1989
1996
14
32
11
13
15
16
17
14
19
36
909
971
1006
1038
1046
1056
1064
1090
1096
15
32
11
13
15
16
17
14
19
36
0
62
97
129
137
147
155
181
187
16
34
27
26
24
25
23
22
20
21
19
36
0
24
143
175
183
210
218
244
252
284
290
17
34
27
26
24
22
20
21
19
36
569
593
712
744
771
797
805
837
843
18
32
11
10
37
378
440
450
463
19
34
27
26
24
22
20
18
19
14
15
13
11
10
37
410
434
553
585
612
638
670
678
704
714
746
781
791
804
20
34
27
26
24
22
23
21
19
14
15
13
11
10
37
133
157
276
308
335
343
369
401
427
437
469
504
514
527
Note. In the table, the up row indicates the upstream route nodes for each aircraft going through; the down row indicates the time reaching each node.The comparisons and statistics of taxiing route and waiting delay time for each aircraft are shown in Table4. The shortest route (SHR), length of taxiing route (LTR), the extra taxiing distance (EXTD), and the waiting delay time (WDT) information are shown in Table 4.Table 4
The comparisons and statistics of aircraft taxiing.
Aircraft number
Airline
SHR/m
IGA
ACO
LTR/m
EXTD/m
WDT/s
LTR/m
EXTD/m
WDT/s
1
1
4250
4410
160
1773
4420
170
545
2
2
1600
1600
0
0
1760
160
0
3
3
1600
1600
0
681
2340
740
1657
4
1
3660
3660
0
588
3660
0
1520
5
2
3660
3820
160
0
3820
160
135
6
3
2170
2330
160
464
2330
160
298
7
2
2800
2980
180
1041
2990
190
1297
8
1
2800
2800
0
1299
2990
190
1059
9
2
3170
3330
160
897
3390
220
0
10
3
3170
3330
160
1200
3330
160
1761
11
1
2300
2460
160
1305
2460
160
1285
12
2
2300
2460
160
189
2460
160
743
13
3
2170
2250
80
1771
2170
0
1400
14
2
1710
1870
160
909
1710
0
927
15
2
1710
1870
160
0
1710
0
0
16
1
2740
2900
160
0
2980
240
975
17
3
2740
2740
0
569
2740
0
0
18
2
850
850
0
378
2190
1340
355
19
1
3740
3940
200
410
3940
200
1764
20
2
3740
3940
200
133
3820
80
1608
Total
52880
55140
2260
13607
57210
4330
17329From Table4, we can see that, in the IGA, the aircraft 2, 3, 4, 8, 17, and 18 all select the shortest route, greatly reducing the cost of taxiing. And to avoid conflicts, the other aircraft do not select the shortest route which leads to extra taxiing costs. In the ACO, only five aircraft choose the shortest route.From Table4, in the ACO, the total taxiing distance is 57210 m, the total extra taxiing route is 4330 m, and the total waiting delay time is 17329 s. In the IGA of this paper, the total taxiing distance is 55140 m; the total extra taxiing route is 2260 m, which is 47.8% lower than the ACO; the total delay time is 13607 s, which is reduced by 21.5% compared with the ACO, as seen in Figure 4. The advantages of the IGA have been shown. In the specially designed genetic algorithm for surface taxiing scheduling, enough diverse individuals are generated through crossover and mutation manipulation, and excellent variation individuals will enter into the next generation with greater proportion through the selection and reinsertion manipulation. The evolution of the IGA would go in the direction of no conflict, less waiting delay time, and less extra taxiing distance.Figure 4
Comparison of aircraft’s taxiing scheduling in IGA and ACO.According to the simulation results in Table4, we can draw the contrastive analysis diagram of the aircraft taxiing distance and the extra taxiing route in the IGA and ACO, which is shown in Figures 5 and 6.Figure 5
Comparison of taxiing route of aircraft in IGA and ACO.Figure 6
Comparison of the extra taxiing distance of aircraft in IGA and ACO.From Figures5 and 6, compared with the ACO, the results of the IGA are that each aircraft selects a shorter taxiing route as possible, and the taxiing distance is significantly reduced, especially for the extra taxiing route distance. From Figures 5 and 6, it can be seen that, in the IGA, the taxiing distance of 6 aircraft is reduced, 10 aircraft are constant, and 4 aircraft are increased. However, due to a big margin reduced in aircraft 3 and aircraft 18, the total extra taxiing distance reduces by 47.8% compared with the ACO. The IGA reduces the overall taxiing route distance and operating cost effectively. The 47.8% decrease is mainly caused by the concept of the extra taxiing distance. According to the concept, the extra taxiing distance could be reduced to zero with 100% decrease, if all aircraft taxi with their shortest taxiing route. That is to say, not all aircraft have extra taxiing distance. If some (not too many) aircraft’s routes are improved, obvious reflection will be shown in this value.According to Table4, the contrastive analysis diagram of the waiting delay time can also be obtained in Figure 7.Figure 7
Comparison of the waiting delay time of aircraft in IGA and ACO.Waiting delay time refers to the time postponed off the scheduling. The delay time is the difference between the time an aircraft actually begins to enter the surface taxiway system and the earliest possible time it can enter the taxiing system. Table2 and Figure 7 show that, in the IGA, at the time t=0 s, landing aircraft 2 and aircraft 5 leave gate 35 (T1) and gate 36 (T2), respectively, and taking-off aircraft 15 and aircraft 16 leave the runway 1 (exit node 32) and runway 2 (exit node 34), respectively. Therefore, 4 aircraft start to taxi simultaneously. Aircraft 1 is the last aircraft to begin taxiing at the time 1773 s. But it meets the condition that all aircraft can finish the taxiing or begin taxiing in the interval of 30 minutes. Compared with the ACO, 9 aircraft are shortened on waiting delay time, 5 aircraft are unchanged, and 6 aircraft are longer. On the whole, the IGA reduces the aircraft waiting delay time and improves the efficiency of airport surface.The optimizing model provides a seamless connection between taxiway and runway. Runway queuing and scheduling are integrated into the model. The model considers different stakeholders’ requirements, ensuring the safety of airport surface movement, reducing delay and taxiing cost, and improving the utilization efficiency of airport resources. The genetic algorithm used here is greatly improved which is more suitable for the airport surface taxiing scheduling problem and the optimizing model. In the IGA, aircraft could change the initial taxiing time and the taxiing route to optimize the taxiing and scheduling in large data search space rapidly as shown in the results.


### 4.4.3. The Gini Coefficient and Fairness Analysis for Airlines

(1) Analysis of Scheduling Fairness. According to Table 4, we can calculate the extra taxiing distance (EXTD), the average extra taxiing distance (AETD), the waiting delay time (WDT), and the average waiting delay time (AWDT) for each airline in Table 5 and Figure 8.Table 5
Comparison of the scheduling taxiing route between IGA and ACO.
Airline
Number of aircraft
IGA
ACO
EXTD/m
AETD/m
AWDT/s
AWDT/s
EXTD/m
AETD/m
WDT/s
AWDT/s
1
6
680
113.3
5375
895.8
960
160
7148
1191.3
2
9
1180
131.1
3547
394.1
2310
256.7
5065
562.8
3
5
400
80
4685
937.0
1060
212
5116
1023.2
Gini coefficient
0.3412
0.3422
0.2886
0.4351Figure 8
Analysis on taxiing scheduling of airlines.It can be seen in Table5 and Figure 8, in the IGA, that the average extra taxiing distances of each airline are 113.3 m, 131.1 m, and 80 m, respectively. The Gini coefficient of extra taxiing distance is 0.3412. The average delay time of each airline is 895.8 s, 394.1 s, and 937 s, respectively. The Gini coefficient of the average waiting delay time is 0.3422. Both Gini coefficients meet the requirement within a reasonable range. In the ACO, the Gini coefficient of extra taxiing distance is 0.2886; it is fair but the overall extra distance is too long. The Gini coefficient of the average waiting delay time is 0.4351, which exceeds the required value 0.35. The results indicate that the distribution of the delay between airlines is not fair enough.The optimizing model considers the fairness of scheduling, and the IGA could well finish the solving. The extra taxiing distance and waiting delay time are distributed between airlines fairly. Thus, the interests of various airlines are protected.(2) Impact Analysis on Different Fairness Parameters. The paper mainly analyzes the impact of the two fairness constraint parameters on optimization results. In order to control variables, we set ε1 or ε2 to be 1 and the other to be 0.25, 0.3, and 0.35, respectively. For example, let ε2=1 in the optimization, and the optimization results and properties are shown in Table 6. The average extra taxiing distance and the average waiting delay time of each airline are shown in Table 7 and Figure 9.Table 6
Optimization results of taxiing route with different parameters.
ε
2
=
1
,
ε
1
Total extra taxiing distance/m
Total waiting delay time/s
0.25
2930
14312
0.3
2930
13782
0.35
1569
12468Table 7
Optimization results of each airline with different parameters.
ε
2
=
1
Average taxiing distance
Average waiting delay time
Airline
ε
1
0.25
0.3
0.35
0.25
0.3
0.35
1
101.7
101.7
113.3
570.5
898.5
895.8
2
122.2
164.4
131.1
586.2
394.1
394.1
3
244
168
80
1122.6
968.8
937Figure 9
Optimization results of taxiing scheduling for each airline with different parameters.From Table6, we can see that, with the increase of Gini coefficient (ε2) controlling the delay fairness (namely, fairness reduced), the total extra taxiing distance and the total waiting delay time are falling (namely, efficiency increased). Table 7 and Figure 9 also show that the average extra taxiing distance and the average waiting delay time for each airline are decreasing. This illustrates that the efficiency and fairness of scheduling are mutually affected and restricted. So the selection of fairness parameter values has an important impact on the entire scheduling optimization results.


## 4.4.1. Analysis of Algorithm Performance

Using MATLAB to code the IGA and based on the surface data of one of our country’s large airports, we simulate the model established above. The evolution of the genetic algorithm is shown in Figure3.Figure 3
The evolutionary process of the IGA.The evolutionary process of the IGA shows that in the first 20 generations the evolution of the population converges rapidly, and after 70 generations, the evolution levels off. After 140 iterations, the average fitness value of the population and the fitness value of the best individual start stabilizing. It takes 7 minutes and 55 seconds to run the program, which could meet the timeliness requirements of resources operating and scheduling on airport surface.


## 4.4.2. Analysis of Simulation Results

Through the simulation, we can get the best individual in the last generation population. Meanwhile, the paper selects a scheduling result through the ant colony optimization (ACO) to contrast the simulation results, which is shown in Table2.Table 2
The comparison of results between IGA and ACO.
Aircraft number
IGA
ACO
Route number
Waiting delay time/s
Route number
Waiting delay time/s
1
12
1773
11
545
2
26
0
23
0
3
26
681
25
1657
4
33
588
31
1520
5
39
0
40
135
6
50
464
53
298
7
71
1041
73
1297
8
62
1299
73
1059
9
85
897
78
0
10
83
1200
89
1761
11
92
1305
103
1285
12
101
189
105
743
13
120
1771
119
1400
14
134
909
121
927
15
134
0
130
0
16
148
0
144
975
17
137
569
139
0
18
157
378
159
355
19
175
410
177
1764
20
178
133
171
1608
Note. Due to the paper length, the path 12 sets with 180 routes cannot be fully demonstrated here.IGA and ACO are both conflict-free scheduling methods. In the two methods, each aircraft has a taxiing route and waiting delay time. We can see from Table2, in the IGA, that 4 aircraft start taxiing with no waiting delay, waiting delay time of 9 aircraft is within 500 s, and waiting delay of 2 aircraft is longer than 1500 s. In the ACO, 4 aircraft have no waiting delays, but only waiting delay of 7 aircraft is within 500 s and waiting delay of 5 aircraft is longer than 1500 s. Therefore, the simulation results of IGA are better than the results of ACO in the taxiing route scheduling.According to the aircraft taxiing scheduling results in Table2 and the route sets, we can get the specific and detailed scheduling for aircraft’s taxiing in the IGA, including the node which each aircraft passes through and the time of arriving at each node in Table 3.Table 3
The specific and detailed scheduling results for aircraft taxiing in IGA.
Aircraft number
The nodes and the arrival time
1
35
23
22
20
18
17
14
12
10
8
6
4
3
2
1
31
1773
1780
1788
1841
1846
1872
1880
1912
1947
1982
2043
2103
2175
2184
2197
2214
2
35
23
25
28
29
30
33
0
7
34
67
97
133
160
3
35
23
25
28
29
30
33
681
688
715
784
778
814
841
4
36
19
14
12
10
8
6
7
5
2
1
31
588
594
620
652
687
722
783
792
852
924
937
954
5
36
19
18
17
14
12
10
8
6
4
5
2
1
31
0
6
14
40
48
80
115
150
211
271
280
352
365
382
6
36
19
21
20
22
24
25
28
29
30
33
464
470
502
510
536
563
571
604
634
670
697
7
37
10
8
6
7
5
4
3
2
1
31
1041
1054
1089
1150
1159
1219
1228
1300
1309
1322
1339
8
7
10
8
6
4
5
2
1
31
1299
1312
1347
1408
1468
1477
1549
1562
1579
9
37
10
12
14
19
18
20
22
23
25
28
29
30
33
897
910
945
977
1003
1011
1043
1069
1077
1104
1137
1167
1203
1230
10
37
10
12
14
19
18
20
22
24
25
28
29
30
33
1200
1213
1248
1280
1306
1314
1346
1372
1399
1407
1440
1470
1506
1533
11
32
11
10
12
14
17
18
20
22
23
35
1305
1367
1377
1412
1444
1452
1478
1510
1536
1544
1551
12
32
11
13
15
14
17
18
20
22
23
35
189
251
286
318
328
336
362
394
420
428
435
13
34
27
26
28
25
23
35
1771
1795
1914
1929
1962
1989
1996
14
32
11
13
15
16
17
14
19
36
909
971
1006
1038
1046
1056
1064
1090
1096
15
32
11
13
15
16
17
14
19
36
0
62
97
129
137
147
155
181
187
16
34
27
26
24
25
23
22
20
21
19
36
0
24
143
175
183
210
218
244
252
284
290
17
34
27
26
24
22
20
21
19
36
569
593
712
744
771
797
805
837
843
18
32
11
10
37
378
440
450
463
19
34
27
26
24
22
20
18
19
14
15
13
11
10
37
410
434
553
585
612
638
670
678
704
714
746
781
791
804
20
34
27
26
24
22
23
21
19
14
15
13
11
10
37
133
157
276
308
335
343
369
401
427
437
469
504
514
527
Note. In the table, the up row indicates the upstream route nodes for each aircraft going through; the down row indicates the time reaching each node.The comparisons and statistics of taxiing route and waiting delay time for each aircraft are shown in Table4. The shortest route (SHR), length of taxiing route (LTR), the extra taxiing distance (EXTD), and the waiting delay time (WDT) information are shown in Table 4.Table 4
The comparisons and statistics of aircraft taxiing.
Aircraft number
Airline
SHR/m
IGA
ACO
LTR/m
EXTD/m
WDT/s
LTR/m
EXTD/m
WDT/s
1
1
4250
4410
160
1773
4420
170
545
2
2
1600
1600
0
0
1760
160
0
3
3
1600
1600
0
681
2340
740
1657
4
1
3660
3660
0
588
3660
0
1520
5
2
3660
3820
160
0
3820
160
135
6
3
2170
2330
160
464
2330
160
298
7
2
2800
2980
180
1041
2990
190
1297
8
1
2800
2800
0
1299
2990
190
1059
9
2
3170
3330
160
897
3390
220
0
10
3
3170
3330
160
1200
3330
160
1761
11
1
2300
2460
160
1305
2460
160
1285
12
2
2300
2460
160
189
2460
160
743
13
3
2170
2250
80
1771
2170
0
1400
14
2
1710
1870
160
909
1710
0
927
15
2
1710
1870
160
0
1710
0
0
16
1
2740
2900
160
0
2980
240
975
17
3
2740
2740
0
569
2740
0
0
18
2
850
850
0
378
2190
1340
355
19
1
3740
3940
200
410
3940
200
1764
20
2
3740
3940
200
133
3820
80
1608
Total
52880
55140
2260
13607
57210
4330
17329From Table4, we can see that, in the IGA, the aircraft 2, 3, 4, 8, 17, and 18 all select the shortest route, greatly reducing the cost of taxiing. And to avoid conflicts, the other aircraft do not select the shortest route which leads to extra taxiing costs. In the ACO, only five aircraft choose the shortest route.From Table4, in the ACO, the total taxiing distance is 57210 m, the total extra taxiing route is 4330 m, and the total waiting delay time is 17329 s. In the IGA of this paper, the total taxiing distance is 55140 m; the total extra taxiing route is 2260 m, which is 47.8% lower than the ACO; the total delay time is 13607 s, which is reduced by 21.5% compared with the ACO, as seen in Figure 4. The advantages of the IGA have been shown. In the specially designed genetic algorithm for surface taxiing scheduling, enough diverse individuals are generated through crossover and mutation manipulation, and excellent variation individuals will enter into the next generation with greater proportion through the selection and reinsertion manipulation. The evolution of the IGA would go in the direction of no conflict, less waiting delay time, and less extra taxiing distance.Figure 4
Comparison of aircraft’s taxiing scheduling in IGA and ACO.According to the simulation results in Table4, we can draw the contrastive analysis diagram of the aircraft taxiing distance and the extra taxiing route in the IGA and ACO, which is shown in Figures 5 and 6.Figure 5
Comparison of taxiing route of aircraft in IGA and ACO.Figure 6
Comparison of the extra taxiing distance of aircraft in IGA and ACO.From Figures5 and 6, compared with the ACO, the results of the IGA are that each aircraft selects a shorter taxiing route as possible, and the taxiing distance is significantly reduced, especially for the extra taxiing route distance. From Figures 5 and 6, it can be seen that, in the IGA, the taxiing distance of 6 aircraft is reduced, 10 aircraft are constant, and 4 aircraft are increased. However, due to a big margin reduced in aircraft 3 and aircraft 18, the total extra taxiing distance reduces by 47.8% compared with the ACO. The IGA reduces the overall taxiing route distance and operating cost effectively. The 47.8% decrease is mainly caused by the concept of the extra taxiing distance. According to the concept, the extra taxiing distance could be reduced to zero with 100% decrease, if all aircraft taxi with their shortest taxiing route. That is to say, not all aircraft have extra taxiing distance. If some (not too many) aircraft’s routes are improved, obvious reflection will be shown in this value.According to Table4, the contrastive analysis diagram of the waiting delay time can also be obtained in Figure 7.Figure 7
Comparison of the waiting delay time of aircraft in IGA and ACO.Waiting delay time refers to the time postponed off the scheduling. The delay time is the difference between the time an aircraft actually begins to enter the surface taxiway system and the earliest possible time it can enter the taxiing system. Table2 and Figure 7 show that, in the IGA, at the time t=0 s, landing aircraft 2 and aircraft 5 leave gate 35 (T1) and gate 36 (T2), respectively, and taking-off aircraft 15 and aircraft 16 leave the runway 1 (exit node 32) and runway 2 (exit node 34), respectively. Therefore, 4 aircraft start to taxi simultaneously. Aircraft 1 is the last aircraft to begin taxiing at the time 1773 s. But it meets the condition that all aircraft can finish the taxiing or begin taxiing in the interval of 30 minutes. Compared with the ACO, 9 aircraft are shortened on waiting delay time, 5 aircraft are unchanged, and 6 aircraft are longer. On the whole, the IGA reduces the aircraft waiting delay time and improves the efficiency of airport surface.The optimizing model provides a seamless connection between taxiway and runway. Runway queuing and scheduling are integrated into the model. The model considers different stakeholders’ requirements, ensuring the safety of airport surface movement, reducing delay and taxiing cost, and improving the utilization efficiency of airport resources. The genetic algorithm used here is greatly improved which is more suitable for the airport surface taxiing scheduling problem and the optimizing model. In the IGA, aircraft could change the initial taxiing time and the taxiing route to optimize the taxiing and scheduling in large data search space rapidly as shown in the results.


## 4.4.3. The Gini Coefficient and Fairness Analysis for Airlines

(1) Analysis of Scheduling Fairness. According to Table 4, we can calculate the extra taxiing distance (EXTD), the average extra taxiing distance (AETD), the waiting delay time (WDT), and the average waiting delay time (AWDT) for each airline in Table 5 and Figure 8.Table 5
Comparison of the scheduling taxiing route between IGA and ACO.
Airline
Number of aircraft
IGA
ACO
EXTD/m
AETD/m
AWDT/s
AWDT/s
EXTD/m
AETD/m
WDT/s
AWDT/s
1
6
680
113.3
5375
895.8
960
160
7148
1191.3
2
9
1180
131.1
3547
394.1
2310
256.7
5065
562.8
3
5
400
80
4685
937.0
1060
212
5116
1023.2
Gini coefficient
0.3412
0.3422
0.2886
0.4351Figure 8
Analysis on taxiing scheduling of airlines.It can be seen in Table5 and Figure 8, in the IGA, that the average extra taxiing distances of each airline are 113.3 m, 131.1 m, and 80 m, respectively. The Gini coefficient of extra taxiing distance is 0.3412. The average delay time of each airline is 895.8 s, 394.1 s, and 937 s, respectively. The Gini coefficient of the average waiting delay time is 0.3422. Both Gini coefficients meet the requirement within a reasonable range. In the ACO, the Gini coefficient of extra taxiing distance is 0.2886; it is fair but the overall extra distance is too long. The Gini coefficient of the average waiting delay time is 0.4351, which exceeds the required value 0.35. The results indicate that the distribution of the delay between airlines is not fair enough.The optimizing model considers the fairness of scheduling, and the IGA could well finish the solving. The extra taxiing distance and waiting delay time are distributed between airlines fairly. Thus, the interests of various airlines are protected.(2) Impact Analysis on Different Fairness Parameters. The paper mainly analyzes the impact of the two fairness constraint parameters on optimization results. In order to control variables, we set ε1 or ε2 to be 1 and the other to be 0.25, 0.3, and 0.35, respectively. For example, let ε2=1 in the optimization, and the optimization results and properties are shown in Table 6. The average extra taxiing distance and the average waiting delay time of each airline are shown in Table 7 and Figure 9.Table 6
Optimization results of taxiing route with different parameters.
ε
2
=
1
,
ε
1
Total extra taxiing distance/m
Total waiting delay time/s
0.25
2930
14312
0.3
2930
13782
0.35
1569
12468Table 7
Optimization results of each airline with different parameters.
ε
2
=
1
Average taxiing distance
Average waiting delay time
Airline
ε
1
0.25
0.3
0.35
0.25
0.3
0.35
1
101.7
101.7
113.3
570.5
898.5
895.8
2
122.2
164.4
131.1
586.2
394.1
394.1
3
244
168
80
1122.6
968.8
937Figure 9
Optimization results of taxiing scheduling for each airline with different parameters.From Table6, we can see that, with the increase of Gini coefficient (ε2) controlling the delay fairness (namely, fairness reduced), the total extra taxiing distance and the total waiting delay time are falling (namely, efficiency increased). Table 7 and Figure 9 also show that the average extra taxiing distance and the average waiting delay time for each airline are decreasing. This illustrates that the efficiency and fairness of scheduling are mutually affected and restricted. So the selection of fairness parameter values has an important impact on the entire scheduling optimization results.


## 5. Conclusions

The airport surface taxiing route scheduling between taxiway and runway in hub airport problem is studied here. An optimization model based on safety, efficiency, and fairness is established for the aircraft surface taxiing problem. The paper also combines the needs and interests of the air traffic controllers, airlines, and airport authorities. The occupancy of the runway has an important impact on the surface taxiing and is integrated into the airport surface scheduling. The IGA adapted to the problem and model is designed to optimize and solve the problem. Simulation data comes from a large airport. Simulation results show that compared with the ACO, the paper proposed the total extra taxiing distance which is reduced by 47.8% and the total waiting delay time which is decreased by 21.5%. The efficiency of the airport surface taxiing is effectively improved and the surface taxiing fairness interairline is enhanced. The optimal solution got here is in line with expectations.



---

*Source: 925139-2015-03-17.xml*