# Flights Assignment Model of Multiple Airports Based on Game Theory and CDM Mechanism

Authors: Junqiang Liu
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

To minimize delay cost of flights in multiple airports, this paper studied flights assignment problem under delay conditions. By considering the delay cost, airport capacity, and the slot exchange between airlines, this paper proposed a novel assignment model based on game theory and CDM mechanism. An improved ant colony algorithm was proposed to solve the flight assignment problem. The case studies showed that the proposed model can optimize the minimum delay cost between airlines under multiairport capacity constraints. The performance of proposed method was better than that of traditional non-slot-exchange method.


---

## Body

## 1. Introduction

Nowadays, the air traffic demands grow rapidly with the development of the economy. However, it is difficult to satisfy the transportation requirements due to airport capacity constraints and flights delays. Airports, as the key point in air traffic flow management, have been becoming the bottleneck of air traffic management and airport safety operation. The real-time flight assignment problem becomes the key research of air transportation field. In the past twenty years, various complex models, techniques, and algorithms, which include mono-objective optimization and multiobjective optimization, have been studied to support the efficient operation of airports [1].The mono-objective flight assignment method is the key point for researchers in air traffic management (ACM). Zou and Hansen[1] analyzed the flight delay impacts of airlines in the airports. Brunner [2] proposed the flight assignment model considering passenger costs. Gavranis and Kozanidis [3] designed the flight assignment algorithm with flight delay. Furini et al. [4] optimized the flight sequencing problem using a rolling horizon algorithm. In [5], a rolling horizon algorithm is proposed for the aircraft landing sequence problem. According to the operation mode of the capital airport, in reference [6], the theoretical mathematical model of the capacity evaluation is deduced, and the calculation method of the single runway airport capacity is introduced. Vossen and Ball [7] proposed the stochastic model to optimize the routes and time slots simultaneously. In earlier studies, most of them were simplified as a mono-objective problem [8–13].Recently, the cooperative co-evolution multiobjective algorithm is introduced to solve the flight assignment problem [14]. Zhang and Hu [15] optimized the airport congestion and flight delay by a multiobjective genetic algorithm. In the real-time operation, controllers were more likely to seek a good trade-off between the airport congestion and the flight delay [16].However, in real-time air traffic management, the collaborative decision making (CDM) mechanism [17] has been used for airports, airlines, and air traffic control center (ATCC). In CDM mechanism, airports, airlines, and ATCC should work collaboratively to optimize flights assignment. To reduce the delay cost, the CDM should be implemented accurately: ATCC provides updated slots to the airlines; the airlines choose the slot assignment schemes corresponding to the optimal flight assignment (based on the minimum cost principle); finally, the optimal real-time flights assignment is carried out based on the interests between airports, airlines, and air traffic control center. However, until now, there are no papers to support real-time flight assignment which combines CDM mechanism and multiobjective optimization.In summary, many assignment methods have been studied for single airport while few studies have investigated the cases of multiairport flight assignment under CDM mechanism. Therefore, in this paper, it proposes a dynamic real-time flight assignment model of multiairport under CDM mechanism with game theory. Then, an improved ant colony algorithm is designed for solving the problem of real-time flight assignment. The multiple airports examples are shown to test and validate. The experimental results show that the proposed method is better than the traditional one.


## 2. The Model

### 2.1. Variables definition

(1)
T: it consists of multiple time spans of which the duration is Δ (15 min), where T=t1,t2,…tM.
(2)
I: it represents the airports.
(3)
F: it represents the flights in the airports, i,j∈I.
(4)
F
i: it represents the flights which depart from the airport i. It consists of the set Depi of departure flights and the set arri of arrival flights.
(5)
X: it represents the connecting flight sets.
(6)
t
f represents the actual time of arrival or departure of flights; tfd is the actual departure time, and tfa is the actual arrival time.
(7)
Δ
t
f
,
f
′: it represents the interval of connecting flight couple f and f′.
(8)
e
f represents the expected flight time, efd is the expected departure time, and efa is the expected arrival time.
(9)
T
f: it represents the time spans of flight f.
(10)
Ψ
u
,
v
t
i: it represents the capacity curve in airport i.
(11)
U
t
i
,
V
t
i: they are the maximum capacity value of arrival flights and departure flights.
(12)
u
t
i
,
v
t
i: they are the arrival flights of airport i and the departure flights of airport i in time span t.
(13)
A
i represents the ith airport.


### 2.2. The Objective Description

#### 2.2.1. Minimize the Delay Time

The goal is to minimize the delay time when the capacities of airports are considered. The objective function is described as(1)min∑Ai=1n∑f∈Depint∑t∈Tftfd−efdxft+∑f∈Depext∑t∈Tftfd−efdxft+∑f∈Arri∑t∈Tftfa−efayft,where tfd−efd represents the delay time of departure flight and tfa−efa represents the delay time of arrival flight. The objective function consists of the departure delay flights at the restricted airports, departure delay flights between restricted airports, and arrival delay flights at the restricted airports. Equation (1) can be revised further to the equation (2):(2)f1=min∑Ai=1n∑f∈Dep∑t∈Tftfd−efdxft+∑f∈Arri∑t∈Tftfa−efayft.In equation (2), xft represents the departure flight and yft represents the arrival flight. The details are described as follows:(3)xft=3,importantdepartureflightsintimespan,1,normaldepartureflightsintimespan,0,otherwise,(4)yft=3,importantarrivalflightsintimespan,1,normalarrivalflightsintimespan,0,otherwise,Equation (3) is the constraints on time span assigned for departure flights. If the normal flight gets the slot t, then xft=1; if the important flight gets the slot t, then xft=3; otherwise, xft=0. Equation (4) is the constraint on time span assigned for arrival flights which ensures each flight only one arrival time span. If the normal flight f gets the slot t, then yft=1; if the important flight gets the slot t, then yft=3; otherwise, yft=0.


#### 2.2.2. Optimize the Slot Assignment Using Zero-Sum Sequential Game

The airlines can reduce delay cost of important flights by exchanging the slots according to zero-sum sequential game. Zero-sum sequential game means that the income of one side equals the loss of the other side. Because the saving cost of slot exchange between the important flights and normal flights is same, zero-sum sequential game [18, 19] is adopted. The model of zero-sum sequential game is described as follows:(5)Z=FA,SA,pA,Cp,where A represents the airlines; FA represents the flights set of the airlines. SA is the set of all optional slot series for airlines A; pA is the realization probability of SA. Cp denotes the expected cost matrix based on zero-sum sequential game theory.Theorem 1.
The relation between the increased waiting time of flight delay and slot assignment is not dependable.Proof.
Assume thatD is the set of delay time of the flights D=d1,d2,...,dz, dk=s,i represents that slot s is assigned to flight i, and dk=ts−ti where ti is the scheduled arrival time of flight i and ts is the time of slot s. Because there are no canceled flights, there must be only one slot for each flight. Therefore, it has the equation as follows:(6)∑i∈N∑s∈Sxijts−ti=∑k=1zdk=∑s∈Sts−∑i∈Nti,where the slot s is assigned to flight i, ∑s∈Sts−∑i∈Nti is a constant. Therefore, there is no dependable relation between the increased waiting time of flight delay and the slot assignment.Theorem 2.
It is a dependable relation between the flight assignment and the slot assignment.Proof.
In the collaborative decision making (CDM) system, the slot assignment for delayed flights is assigned with minimum delay of flight banks according to slot exchange. Therefore, the flight assignment depends on the slot assignment which plays an important role in flight assignment.Theorem 3.
In the zero-sum sequential game, any realization probability points to a behavior strategy [19].The objective function with zero-sum sequential game is described as follows:(7)minf2=∑fSECSA+ECSB,where fS is the flights which consists of slot-exchange flights pairs SA and SB. ECSA is the expected delay cost of flights SA. ECSB is the expected delay cost of flights SB. Because the optimization of slot assignment can save the delay cost of airlines, based on the game theory, it can get the optimal result when exchanging the flights pairs SA and SB.


### 2.3. General Objective

The general objective is described as follows:(8)minf=minf1,f2,subjectto(9)0≤uti≤Uti,0≤vti≤Vti,∀t∈T,∀i∈I,(10)αtiuti+βtivti≤γti,∀t∈T,∀i∈I,(11)tfd−tfa≥Δtf,f′,∀f,f′∈X,(12)0≤tfid−tfja−tfid−tfja≤δ;fi∈Arri,fj∈Depj;j∈I.The integrative conceptual model of flights assignment is shown in equation (8), which consists of two objective functions. f1 is set as the first highest priority and f2 is the second highest priority. Equations (9) and (10) are the constraints on capacities of airports which consist of the feasible operation areas. The optimal solutions must be on or inside the airport capacity curves, where αti, βti, and γti are coefficients of capacity curve. Equation (11) is the constraint on connecting flights. Equation (12) shows that the arrival time, departure time, and slot exchange should be suitable for inherent relations in flight assignment. δ is the minimum time interval of two flights.


## 2.1. Variables definition

(1)
T: it consists of multiple time spans of which the duration is Δ (15 min), where T=t1,t2,…tM.
(2)
I: it represents the airports.
(3)
F: it represents the flights in the airports, i,j∈I.
(4)
F
i: it represents the flights which depart from the airport i. It consists of the set Depi of departure flights and the set arri of arrival flights.
(5)
X: it represents the connecting flight sets.
(6)
t
f represents the actual time of arrival or departure of flights; tfd is the actual departure time, and tfa is the actual arrival time.
(7)
Δ
t
f
,
f
′: it represents the interval of connecting flight couple f and f′.
(8)
e
f represents the expected flight time, efd is the expected departure time, and efa is the expected arrival time.
(9)
T
f: it represents the time spans of flight f.
(10)
Ψ
u
,
v
t
i: it represents the capacity curve in airport i.
(11)
U
t
i
,
V
t
i: they are the maximum capacity value of arrival flights and departure flights.
(12)
u
t
i
,
v
t
i: they are the arrival flights of airport i and the departure flights of airport i in time span t.
(13)
A
i represents the ith airport.


## 2.2. The Objective Description

### 2.2.1. Minimize the Delay Time

The goal is to minimize the delay time when the capacities of airports are considered. The objective function is described as(1)min∑Ai=1n∑f∈Depint∑t∈Tftfd−efdxft+∑f∈Depext∑t∈Tftfd−efdxft+∑f∈Arri∑t∈Tftfa−efayft,where tfd−efd represents the delay time of departure flight and tfa−efa represents the delay time of arrival flight. The objective function consists of the departure delay flights at the restricted airports, departure delay flights between restricted airports, and arrival delay flights at the restricted airports. Equation (1) can be revised further to the equation (2):(2)f1=min∑Ai=1n∑f∈Dep∑t∈Tftfd−efdxft+∑f∈Arri∑t∈Tftfa−efayft.In equation (2), xft represents the departure flight and yft represents the arrival flight. The details are described as follows:(3)xft=3,importantdepartureflightsintimespan,1,normaldepartureflightsintimespan,0,otherwise,(4)yft=3,importantarrivalflightsintimespan,1,normalarrivalflightsintimespan,0,otherwise,Equation (3) is the constraints on time span assigned for departure flights. If the normal flight gets the slot t, then xft=1; if the important flight gets the slot t, then xft=3; otherwise, xft=0. Equation (4) is the constraint on time span assigned for arrival flights which ensures each flight only one arrival time span. If the normal flight f gets the slot t, then yft=1; if the important flight gets the slot t, then yft=3; otherwise, yft=0.


### 2.2.2. Optimize the Slot Assignment Using Zero-Sum Sequential Game

The airlines can reduce delay cost of important flights by exchanging the slots according to zero-sum sequential game. Zero-sum sequential game means that the income of one side equals the loss of the other side. Because the saving cost of slot exchange between the important flights and normal flights is same, zero-sum sequential game [18, 19] is adopted. The model of zero-sum sequential game is described as follows:(5)Z=FA,SA,pA,Cp,where A represents the airlines; FA represents the flights set of the airlines. SA is the set of all optional slot series for airlines A; pA is the realization probability of SA. Cp denotes the expected cost matrix based on zero-sum sequential game theory.Theorem 1.
The relation between the increased waiting time of flight delay and slot assignment is not dependable.Proof.
Assume thatD is the set of delay time of the flights D=d1,d2,...,dz, dk=s,i represents that slot s is assigned to flight i, and dk=ts−ti where ti is the scheduled arrival time of flight i and ts is the time of slot s. Because there are no canceled flights, there must be only one slot for each flight. Therefore, it has the equation as follows:(6)∑i∈N∑s∈Sxijts−ti=∑k=1zdk=∑s∈Sts−∑i∈Nti,where the slot s is assigned to flight i, ∑s∈Sts−∑i∈Nti is a constant. Therefore, there is no dependable relation between the increased waiting time of flight delay and the slot assignment.Theorem 2.
It is a dependable relation between the flight assignment and the slot assignment.Proof.
In the collaborative decision making (CDM) system, the slot assignment for delayed flights is assigned with minimum delay of flight banks according to slot exchange. Therefore, the flight assignment depends on the slot assignment which plays an important role in flight assignment.Theorem 3.
In the zero-sum sequential game, any realization probability points to a behavior strategy [19].The objective function with zero-sum sequential game is described as follows:(7)minf2=∑fSECSA+ECSB,where fS is the flights which consists of slot-exchange flights pairs SA and SB. ECSA is the expected delay cost of flights SA. ECSB is the expected delay cost of flights SB. Because the optimization of slot assignment can save the delay cost of airlines, based on the game theory, it can get the optimal result when exchanging the flights pairs SA and SB.


## 2.2.1. Minimize the Delay Time

The goal is to minimize the delay time when the capacities of airports are considered. The objective function is described as(1)min∑Ai=1n∑f∈Depint∑t∈Tftfd−efdxft+∑f∈Depext∑t∈Tftfd−efdxft+∑f∈Arri∑t∈Tftfa−efayft,where tfd−efd represents the delay time of departure flight and tfa−efa represents the delay time of arrival flight. The objective function consists of the departure delay flights at the restricted airports, departure delay flights between restricted airports, and arrival delay flights at the restricted airports. Equation (1) can be revised further to the equation (2):(2)f1=min∑Ai=1n∑f∈Dep∑t∈Tftfd−efdxft+∑f∈Arri∑t∈Tftfa−efayft.In equation (2), xft represents the departure flight and yft represents the arrival flight. The details are described as follows:(3)xft=3,importantdepartureflightsintimespan,1,normaldepartureflightsintimespan,0,otherwise,(4)yft=3,importantarrivalflightsintimespan,1,normalarrivalflightsintimespan,0,otherwise,Equation (3) is the constraints on time span assigned for departure flights. If the normal flight gets the slot t, then xft=1; if the important flight gets the slot t, then xft=3; otherwise, xft=0. Equation (4) is the constraint on time span assigned for arrival flights which ensures each flight only one arrival time span. If the normal flight f gets the slot t, then yft=1; if the important flight gets the slot t, then yft=3; otherwise, yft=0.


## 2.2.2. Optimize the Slot Assignment Using Zero-Sum Sequential Game

The airlines can reduce delay cost of important flights by exchanging the slots according to zero-sum sequential game. Zero-sum sequential game means that the income of one side equals the loss of the other side. Because the saving cost of slot exchange between the important flights and normal flights is same, zero-sum sequential game [18, 19] is adopted. The model of zero-sum sequential game is described as follows:(5)Z=FA,SA,pA,Cp,where A represents the airlines; FA represents the flights set of the airlines. SA is the set of all optional slot series for airlines A; pA is the realization probability of SA. Cp denotes the expected cost matrix based on zero-sum sequential game theory.Theorem 1.
The relation between the increased waiting time of flight delay and slot assignment is not dependable.Proof.
Assume thatD is the set of delay time of the flights D=d1,d2,...,dz, dk=s,i represents that slot s is assigned to flight i, and dk=ts−ti where ti is the scheduled arrival time of flight i and ts is the time of slot s. Because there are no canceled flights, there must be only one slot for each flight. Therefore, it has the equation as follows:(6)∑i∈N∑s∈Sxijts−ti=∑k=1zdk=∑s∈Sts−∑i∈Nti,where the slot s is assigned to flight i, ∑s∈Sts−∑i∈Nti is a constant. Therefore, there is no dependable relation between the increased waiting time of flight delay and the slot assignment.Theorem 2.
It is a dependable relation between the flight assignment and the slot assignment.Proof.
In the collaborative decision making (CDM) system, the slot assignment for delayed flights is assigned with minimum delay of flight banks according to slot exchange. Therefore, the flight assignment depends on the slot assignment which plays an important role in flight assignment.Theorem 3.
In the zero-sum sequential game, any realization probability points to a behavior strategy [19].The objective function with zero-sum sequential game is described as follows:(7)minf2=∑fSECSA+ECSB,where fS is the flights which consists of slot-exchange flights pairs SA and SB. ECSA is the expected delay cost of flights SA. ECSB is the expected delay cost of flights SB. Because the optimization of slot assignment can save the delay cost of airlines, based on the game theory, it can get the optimal result when exchanging the flights pairs SA and SB.


## 2.3. General Objective

The general objective is described as follows:(8)minf=minf1,f2,subjectto(9)0≤uti≤Uti,0≤vti≤Vti,∀t∈T,∀i∈I,(10)αtiuti+βtivti≤γti,∀t∈T,∀i∈I,(11)tfd−tfa≥Δtf,f′,∀f,f′∈X,(12)0≤tfid−tfja−tfid−tfja≤δ;fi∈Arri,fj∈Depj;j∈I.The integrative conceptual model of flights assignment is shown in equation (8), which consists of two objective functions. f1 is set as the first highest priority and f2 is the second highest priority. Equations (9) and (10) are the constraints on capacities of airports which consist of the feasible operation areas. The optimal solutions must be on or inside the airport capacity curves, where αti, βti, and γti are coefficients of capacity curve. Equation (11) is the constraint on connecting flights. Equation (12) shows that the arrival time, departure time, and slot exchange should be suitable for inherent relations in flight assignment. δ is the minimum time interval of two flights.


## 3. An Improved Ant Colony Algorithm

The ant colony optimization algorithm can solve the flights assignment problem [20]. The combination optimization problems including phase estimation problem (TSP) [21] and traffic routing problem [22] can be solved using ant colony algorithm. However, the traditional ant colony algorithm cannot support the game theory. Therefore, in this paper, an improved ant colony algorithm is proposed for the multiairport flights assignment problem with zero-sum sequential game under CDM mechanism.


### 3.1. Description

Figure1 shows two processes of ants which are traditional search process (non-slot-exchange flights) and slot exchange search process, respectively. Ants start form a dummy head node F0, choose a node based on pheromone information of each node, and then repeat until reach the last row. Assume that there are k ants for non-slot-exchange flights and ants first walk through the solution space of identified flights. Then, ants walk from one of the unidentified flights. After traversal of the spaces, each ant releases suitable pheromone on each node passed, according to the target value of ant path where each node is within 15 minutes. Assume that there are m ants for slot-exchange flight assignment process which supports slot exchange between important flights and normal flights and it is similar with traditional ant search process where each node span is also within 15 minutes.Figure 1
Ants searching paths (non-slot-exchange process and slot-exchange process).


#### 3.1.1. Two Groups of Ants

In this section, it consists of two ant colony groups which are slot-exchange group and non-slot-exchange group, respectively.(1) Slot-Exchange Group. Calculate the preassignment slot-exchange path according to time in descending order and constraint condition of 15 minutes span. Exchange the ist i=1,2,...,n combination of flight and slot of airlines A with the jst j=1,2,...,m combination of flight and slot of airlines B, and the exchange should meet the rules of CDM mechanism. Therefore, there are ij slot-exchange pairs for ants to search in multiple 15 minutes spans.(2) Non-Slot-Exchange Group. Except the slot-exchange flights, the remaining flights belong to non-slot-exchange group. Get these flights according to time sequence and different airlines.


#### 3.1.2. State Transition Process

(1) Slot-Exchange Group. The ants mm=1,2,…,M search slot-exchange nodes of paths; their state transition probability is based on the pheromone concentration and heuristic information of the nodes. epikt describes the state transition probability of ant k transferring from its located node into node j at time t in the slot-exchange group. The pheromone state transition equation is described as follows:(13)epjkt=eτjteα⋅eηjteβ∑s∈ealloweτsteα⋅ηsteβ,ifs∈eallowm,0,where eτjt means the pheromone concentration of slot-exchange node j at time point t. eallowm describes the available nodes of ant m to choose from the slot-exchange nodes. eα and eβ represent the weight coefficient, and eα=0.4,eβ=0.6.(2) Non-Slot-Exchange Group. The ants kk=1,2,…,K search non-slot-exchange nodes of paths. Its state transition probability is based on the pheromone concentration and heuristic information of the nodes. pikt represents the state transition probability of ant k transferring from its located node into node i at time t. The equation (14) is described as follows:(14)pikt=τitα⋅ηitβ∑s∈allowedτstα⋅ηstβ,ifs∈allowedk,0,where τit means the pheromone concentration of node i at time point t. The s∈allowedk means that ant k chooses the available flight node at next stage. The set allowedk may change according to the choice of ant k. The parameters α and β determine the relative importance of pheromone accumulated on nodes when it has an impact on choice of ants.


#### 3.1.3. Pheromone Update Methods

(1) Slot-Exchange Group. In the slot-exchange group, when an ant searches a slot-exchange node with zero-sum sequential game cost, the pheromone on this node will be updated. The ants release pheromone at the iteration process. The pheromone update rules are as follows:(15)eτit+1=γeτit+Δeτibest,Δeτi=1Lbest,where γ represents volatile coefficient of pheromone and Lbest is the optimal path whose cost is minimum based on the zero-sum sequential game.(2) Non-Slot-Exchange Group. When ants kk=1,2,…,K complete the iteration, pheromone on each node should be updated. New pheromone will be added to nodes while residual pheromone on each node should be volatilized. Therefore, the rules of pheromone modulation are described as follows:(16)τit+1=ρτit+Δτibest,Δτi=0,i∉kbest,0,i∉kbest,where ρ represents volatile coefficient of pheromone, Q shows pheromone strength. Δτi is the total pheromone increment on node i at present iteration. The optimal ants release pheromone at the iteration process Figure 2.Figure 2
The algorithm flowchart.


### 3.2. The Algorithm Flowchart

Figure3 shows the flowchart of algorithm which consists of two parts which are slot-exchange group and non-slot-exchange group, respectively. The difference between our algorithm and traditional ant colony algorithm is that the slot-exchange group can get the optimal slot exchange flights using the game theory. The convergence speed of the slot-exchange group is faster than that of the non-slot-exchange group, because there are more flights in non-slot-exchange group. Based on the complexity theory of ant colony algorithm, the proposed method has the better runtime cost.Figure 3
Capacity curve of Beijing Airport and Baiyun Airport.There are two advantages for the proposed algorithm. (1) The airlines can exchange slots with other airlines; therefore, the delay cost can be saved for airline as much as possible. (2) Based on game theory and optimization technology, the improved ant colony algorithm can be implemented more efficiently than traditional one.


## 3.1. Description

Figure1 shows two processes of ants which are traditional search process (non-slot-exchange flights) and slot exchange search process, respectively. Ants start form a dummy head node F0, choose a node based on pheromone information of each node, and then repeat until reach the last row. Assume that there are k ants for non-slot-exchange flights and ants first walk through the solution space of identified flights. Then, ants walk from one of the unidentified flights. After traversal of the spaces, each ant releases suitable pheromone on each node passed, according to the target value of ant path where each node is within 15 minutes. Assume that there are m ants for slot-exchange flight assignment process which supports slot exchange between important flights and normal flights and it is similar with traditional ant search process where each node span is also within 15 minutes.Figure 1
Ants searching paths (non-slot-exchange process and slot-exchange process).


### 3.1.1. Two Groups of Ants

In this section, it consists of two ant colony groups which are slot-exchange group and non-slot-exchange group, respectively.(1) Slot-Exchange Group. Calculate the preassignment slot-exchange path according to time in descending order and constraint condition of 15 minutes span. Exchange the ist i=1,2,...,n combination of flight and slot of airlines A with the jst j=1,2,...,m combination of flight and slot of airlines B, and the exchange should meet the rules of CDM mechanism. Therefore, there are ij slot-exchange pairs for ants to search in multiple 15 minutes spans.(2) Non-Slot-Exchange Group. Except the slot-exchange flights, the remaining flights belong to non-slot-exchange group. Get these flights according to time sequence and different airlines.


### 3.1.2. State Transition Process

(1) Slot-Exchange Group. The ants mm=1,2,…,M search slot-exchange nodes of paths; their state transition probability is based on the pheromone concentration and heuristic information of the nodes. epikt describes the state transition probability of ant k transferring from its located node into node j at time t in the slot-exchange group. The pheromone state transition equation is described as follows:(13)epjkt=eτjteα⋅eηjteβ∑s∈ealloweτsteα⋅ηsteβ,ifs∈eallowm,0,where eτjt means the pheromone concentration of slot-exchange node j at time point t. eallowm describes the available nodes of ant m to choose from the slot-exchange nodes. eα and eβ represent the weight coefficient, and eα=0.4,eβ=0.6.(2) Non-Slot-Exchange Group. The ants kk=1,2,…,K search non-slot-exchange nodes of paths. Its state transition probability is based on the pheromone concentration and heuristic information of the nodes. pikt represents the state transition probability of ant k transferring from its located node into node i at time t. The equation (14) is described as follows:(14)pikt=τitα⋅ηitβ∑s∈allowedτstα⋅ηstβ,ifs∈allowedk,0,where τit means the pheromone concentration of node i at time point t. The s∈allowedk means that ant k chooses the available flight node at next stage. The set allowedk may change according to the choice of ant k. The parameters α and β determine the relative importance of pheromone accumulated on nodes when it has an impact on choice of ants.


### 3.1.3. Pheromone Update Methods

(1) Slot-Exchange Group. In the slot-exchange group, when an ant searches a slot-exchange node with zero-sum sequential game cost, the pheromone on this node will be updated. The ants release pheromone at the iteration process. The pheromone update rules are as follows:(15)eτit+1=γeτit+Δeτibest,Δeτi=1Lbest,where γ represents volatile coefficient of pheromone and Lbest is the optimal path whose cost is minimum based on the zero-sum sequential game.(2) Non-Slot-Exchange Group. When ants kk=1,2,…,K complete the iteration, pheromone on each node should be updated. New pheromone will be added to nodes while residual pheromone on each node should be volatilized. Therefore, the rules of pheromone modulation are described as follows:(16)τit+1=ρτit+Δτibest,Δτi=0,i∉kbest,0,i∉kbest,where ρ represents volatile coefficient of pheromone, Q shows pheromone strength. Δτi is the total pheromone increment on node i at present iteration. The optimal ants release pheromone at the iteration process Figure 2.Figure 2
The algorithm flowchart.


## 3.1.1. Two Groups of Ants

In this section, it consists of two ant colony groups which are slot-exchange group and non-slot-exchange group, respectively.(1) Slot-Exchange Group. Calculate the preassignment slot-exchange path according to time in descending order and constraint condition of 15 minutes span. Exchange the ist i=1,2,...,n combination of flight and slot of airlines A with the jst j=1,2,...,m combination of flight and slot of airlines B, and the exchange should meet the rules of CDM mechanism. Therefore, there are ij slot-exchange pairs for ants to search in multiple 15 minutes spans.(2) Non-Slot-Exchange Group. Except the slot-exchange flights, the remaining flights belong to non-slot-exchange group. Get these flights according to time sequence and different airlines.


## 3.1.2. State Transition Process

(1) Slot-Exchange Group. The ants mm=1,2,…,M search slot-exchange nodes of paths; their state transition probability is based on the pheromone concentration and heuristic information of the nodes. epikt describes the state transition probability of ant k transferring from its located node into node j at time t in the slot-exchange group. The pheromone state transition equation is described as follows:(13)epjkt=eτjteα⋅eηjteβ∑s∈ealloweτsteα⋅ηsteβ,ifs∈eallowm,0,where eτjt means the pheromone concentration of slot-exchange node j at time point t. eallowm describes the available nodes of ant m to choose from the slot-exchange nodes. eα and eβ represent the weight coefficient, and eα=0.4,eβ=0.6.(2) Non-Slot-Exchange Group. The ants kk=1,2,…,K search non-slot-exchange nodes of paths. Its state transition probability is based on the pheromone concentration and heuristic information of the nodes. pikt represents the state transition probability of ant k transferring from its located node into node i at time t. The equation (14) is described as follows:(14)pikt=τitα⋅ηitβ∑s∈allowedτstα⋅ηstβ,ifs∈allowedk,0,where τit means the pheromone concentration of node i at time point t. The s∈allowedk means that ant k chooses the available flight node at next stage. The set allowedk may change according to the choice of ant k. The parameters α and β determine the relative importance of pheromone accumulated on nodes when it has an impact on choice of ants.


## 3.1.3. Pheromone Update Methods

(1) Slot-Exchange Group. In the slot-exchange group, when an ant searches a slot-exchange node with zero-sum sequential game cost, the pheromone on this node will be updated. The ants release pheromone at the iteration process. The pheromone update rules are as follows:(15)eτit+1=γeτit+Δeτibest,Δeτi=1Lbest,where γ represents volatile coefficient of pheromone and Lbest is the optimal path whose cost is minimum based on the zero-sum sequential game.(2) Non-Slot-Exchange Group. When ants kk=1,2,…,K complete the iteration, pheromone on each node should be updated. New pheromone will be added to nodes while residual pheromone on each node should be volatilized. Therefore, the rules of pheromone modulation are described as follows:(16)τit+1=ρτit+Δτibest,Δτi=0,i∉kbest,0,i∉kbest,where ρ represents volatile coefficient of pheromone, Q shows pheromone strength. Δτi is the total pheromone increment on node i at present iteration. The optimal ants release pheromone at the iteration process Figure 2.Figure 2
The algorithm flowchart.


## 3.2. The Algorithm Flowchart

Figure3 shows the flowchart of algorithm which consists of two parts which are slot-exchange group and non-slot-exchange group, respectively. The difference between our algorithm and traditional ant colony algorithm is that the slot-exchange group can get the optimal slot exchange flights using the game theory. The convergence speed of the slot-exchange group is faster than that of the non-slot-exchange group, because there are more flights in non-slot-exchange group. Based on the complexity theory of ant colony algorithm, the proposed method has the better runtime cost.Figure 3
Capacity curve of Beijing Airport and Baiyun Airport.There are two advantages for the proposed algorithm. (1) The airlines can exchange slots with other airlines; therefore, the delay cost can be saved for airline as much as possible. (2) Based on game theory and optimization technology, the improved ant colony algorithm can be implemented more efficiently than traditional one.


## 4. Case Studies

Two hub airports, Beijing Capital Airport and Guangzhou Baiyun Airport, are considered for this case study. The time period is from 13 : 00 to 17 : 00, andN = 16, Δ = 15 min. After flow control by air traffic management, flights demands in two airports are shown in Tables 1 and 2. The capacity curves of two airports are shown in Figure 3. It can be seen that some flights must be delayed. The important flights are big aircrafts which have three times passengers than normal flights.Table 1
Delayed flight of Beijing Airport (“dep” = departure, “arr” = arrival, “I” = important flight).
Time
Air China
China eastern
China southern
Dep/I
Arr/I
Dep/I
Arr/I
Dep/I
Arr/I
13 : 00–13 : 14
10/0
6/0
6/0
2/0
4/1
1/0
13 : 15–13 : 29
10/0
7/0
6/0
1/0
4/0
3/0
13 : 30–13 : 44
16/2
3/0
6/0
6/0
9/0
1/0
13 : 45–13 : 59
10/0
8/0
6/0
4/0
5/0
10/2
14 : 00–14 : 14
5/0
8/0
16/2
3/0
6/0
3/0
14 : 15–14 : 29
10/0
5/0
2/0
10/2
4/0
5/0
14 : 30–14 : 44
8/0
10/0
4/0
5/0
7/0
7/0
14 : 45–14 : 59
5/0
16/2
7/0
9/0
7/0
7/0
15 : 00–15 : 14
7/0
9/0
4/0
9/0
11/2
7/0
15 : 15–15 : 29
17/2
5/0
6/0
5/0
3/0
7/0
15 : 30–15 : 44
16/2
11/0
6/0
5/0
10/0
5/0
15 : 45–15 : 59
9/0
12/2
7/0
8/1
9/0
7/0
16 : 00–16 : 14
3/0
7/0
12/2
9/0
7/0
3/0
16 : 15–16 : 29
10/0
11/0
5/0
6/0
11/2
6/0
16 : 30–16 : 44
21/2
7/0
3/0
9/0
6/0
5/0
16 : 45–16 : 59
5/0
20/0
2/0
3/0
3/0
3/0
Total
151/8
145/4
98/4
94/2
99/4
81/2Table 2
Delayed flight of Baiyun Airport (“dep” = departure, “arr” = arrival, “I” = important flight).
Time
China southern
China eastern
Air China
Dep/I
Arr/I
Dep/I
Arr/I
Dep/I
Arr/I
13 : 00–13 : 14
9/0
5/0
5/0
1/0
3/1
2/0
13 : 15–13 : 29
9/0
6/0
5/0
4/0
3/0
2/0
13 : 30–13 : 44
15/2
2/0
5/0
5/0
8/0
3/0
13 : 45–13 : 59
9/0
7/0
5/0
3/0
4/0
9/2
14 : 00–14 : 14
4/0
7/0
15/2
2/0
5/0
2/0
14 : 15–14 : 29
9/0
4/0
1/0
9/2
3/0
4/0
14 : 30–14 : 44
7/0
9/0
3/0
4/0
6/0
4/0
14 : 45–14 : 59
4/0
15/2
6/0
4/0
6/0
6/0
15 : 00–15 : 14
6/0
8/0
3/0
8/0
10/2
6/0
15 : 15–15 : 29
16/2
4/0
5/0
4/0
9/0
3/0
15 : 30–15 : 44
15/2
10/0
5/0
4/0
2/0
4/0
15 : 45–15 : 59
8/0
11/2
6/0
7/1
8/0
6/0
16 : 00–16 : 14
6/0
6/0
11/2
8/0
6/0
2/0
16 : 15–16 : 29
5/0
10/0
4/0
5/0
10/2
5/0
16 : 30–16 : 44
20/2
6/0
5/0
8/0
5/0
4/0
16 : 45–16 : 59
4/0
19/0
1/0
2/0
2/0
2/0
Total
135/8
129/4
85/4
78/2
83/4
75/2Tables3 and 4 show the results of flight assignment of two airports. The slot-exchange result is shown in Figure 4, where AC : D : 4 represents that there are four departure flights in Air China and AC : A : 4 represents that there are four arrival flights in Air China. The proportion of slot-exchange between Air China (AC), China Eastern Airlines (CE), and China Southern Airlines (CS) in the Beijing Airport is 2 : 1 : 1. Similarly, in the Baiyun Airport, the proportion between China Southern Airlines, China Eastern Airlines, and Air China is 2 : 1 : 1.Table 3
Result of real-time assignment of Beijing Airport (“EXCH” = exchange flights).
Time
Air China (A)
China eastern (E)
China south (S)
Dep
Arr
EXCH
Dep
Arr
EXCH
Dep
Arr
EXCH
13 : 00–13 : 14
10/0
6/0
0
6/0
2/0
0
4/1
1/0
0
13 : 15–13 : 29
10/0
7/0
0
6/0
1/0
0
4/0
3/0
0
13 : 30–13 : 44
14/2
3/0
2/E
4/0
6/0
0
8/0
1/0
0
13 : 45–13 : 59
10/0
6/0
0
6/0
4/0
0
5/0
10/2
2/A
14 : 00–14 : 14
3/0
8/0
0
13/2
3/0
2/A
6/0
3/0
0
14 : 15–14 : 29
10/0
3/0
0
2/0
10/2
2/A
4/0
5/0
0
14 : 30–14 : 44
8/0
10/0
0
4/0
5/0
0
7/0
7/0
0
14 : 45–14 : 59
5/0
12/2
2/S
7/0
7/0
0
7/0
7/0
0
15 : 00–15 : 14
5/0
9/0
0
4/0
9/0
0
8/2
7/0
2/A
15 : 15–15 : 29
14/2
5/0
2/S
6/0
5/0
0
3/0
7/0
0
15 : 30–15 : 44
14/2
11/0
2/S
6/0
5/0
0
6/0
5/0
0
15 : 45–15 : 59
6/0
10/2
2/E
5/0
8/1
0
9/0
7/0
0
16 : 00–16 : 14
4/0
7/0
0
10/2
7/0
2/A
7/0
3/0
0
16 : 15–16 : 29
8/0
11/0
0
5/0
6/0
0
9/2
6/0
2/A
16 : 30–16 : 44
14/2
7/0
2/E
3/0
6/0
0
6/0
5/0
0
16 : 45–16 : 59
9/0
8/0
0
2/0
6/0
0
7/0
3/0
0
After 17 : 00
9
4
0
5
3
0
5
2
0
Total
151/8
145/4
12
98/4
94/2
6
99/2
81/2
6Table 4
Result of real-time assignment of Baiyun Airport (“EXCH” = exchange flights).
Time
China southern (S)
China eastern (E)
Air China (A)
Dep
Arr
EXCH
Dep
Arr
EXCH
Dep
Arr
EXCH
13 : 00–13 : 14
9/0
5/0
0
5/0
1/0
0
3/1
2/0
0
13 : 15–13 : 29
9/0
6/0
0
5/0
4/0
0
3/0
2/0
0
13 : 30–13 : 44
12/2
2/0
2/E
3/0
5/0
0
8/0
3/0
0
13 : 45–13 : 59
7/0
7/0
0
5/0
3/0
0
4/0
9/2
2/S
14 : 00–14 : 14
4/0
7/0
0
13/2
2/0
2/S
5/0
2/0
0
14 : 15–14 : 29
9/0
4/0
0
1/0
9/2
2/S
3/0
4/0
0
14 : 30–14 : 44
7/0
9/0
0
3/0
4/0
0
6/0
4/0
0
14 : 45–14 : 59
4/0
12/2
2/E
6/0
2/0
0
6/0
6/0
0
15 : 00–15 : 14
4/0
8/0
0
3/0
8/0
0
10/2
6/0
2/S
15 : 15–15 : 29
12/2
4/0
2/A
4/0
4/0
0
8/0
3/0
0
15 : 30–15 : 44
11/2
10/0
2/A
4/0
4/0
0
3/0
4/0
0
15 : 45–15 : 59
8/0
11/2
0
6/0
7/1
0
8/0
4/0
0
16 : 00–16 : 14
4/0
6/0
0
11/2
6/0
2/S
6/0
4/0
0
16 : 15–16 : 29
3/0
10/0
0
4/0
5/0
0
10/2
5/0
2/S
16 : 30–16 : 44
14/2
6/0
2/E
3/0
6/0
0
5/0
4/0
0
16 : 45–16 : 59
8/0
13/0
0
5/0
4/0
0
5/0
3/0
0
After 17 : 00
9
6
0
4
3
0
4
2
0
Total
135/8
129/4
12
85/4
78/2
6
83/4
75/2
6Figure 4
Slot-exchange results.The reason is that Air China selects Beijing Airport as the base airport, and Southern Airlines select Baiyun Airport as the base airport. Therefore, there are more important flights in the base airport. Therefore, from Tables3 and 4 and Figure 4, it can be seen that all important flights are assigned without changing the time span, which reduces the delay cost for airlines (because if the important flights are delayed, the costs are higher than normal flights).After optimization, the capacity curves of the two airports are shown in Figures5 and 6. It is easy to see that the flight assignment solutions are on or inside capacity curves of two airports, which shows that the assignment is feasible.Figure 5
After-optimization result of Beijing Airport.Figure 6
After-optimization result of Baiyun Airport.After optimization, the real-time flight circumstances of two airports are compared in Figures7 and 8. It can be seen that peak traffic has been eliminated, and the airport capacities are fully utilized, which means that the optimization assignment is more rational and reasonable.Figure 7
Flights assignment of Beijing Airport.Figure 8
Flow assignment of Baiyun Airport.In the following, the runtime cost between the proposed method and traditional two-stage method (flight assignment stage and slot-exchange stage) will be compared. The computation time of the traditional method is 3 minutes and 12 seconds, while the time of our method is 1 minutes 6 seconds (average value of seven samples). The reason is that the traditional method uses the whole data space to search by ants, while the data spaces of our method are slot-exchange space and non-slot-exchange space, respectively.At last, the convergences of our method and traditional two-stage algorithm are compared in Figure9. On one hand, our method converges much faster than the traditional one when seven examples are operated. The application of game theory (slot exchange) improves the convergence significantly.Figure 9
The convergence of evolution algorithm.On the other hand, it can be seen that the traditional ant colony algorithm is not suitable for solving this problem. It only gets partial right results in all the seven tests, because the slot exchange is done after the flight assignment. The combination of game theory (slot exchange) and flight assignment in the proposed algorithm shows the better result for the problem.


## 5. Conclusions

Slot exchange between airlines under CDM mechanism and the capacity curves of multiple airports is considered. The real-time flight assignment model which combines game theory and CDM mechanism is studied. The improved ant colony algorithm which consists of the slot-exchange group and non-slot-exchange group is implemented to solve the assignment problem. The case studies show that our method is correct and effective to handle the real-time flight assignment problem. Further research will extend to the flight assignment of multiairport regions under CDM mechanism.



---

*Source: 2569280-2020-01-30.xml*