An Integrative Approach with Sequential Game to Real-Time Gate Assignment under CDM Mechanism

Abstract

This paper focuses on real-time airport gate assignment problem when small-scale or medium- to large-scale flight delays occur. Taking into account the collaborative decision making (CDM) of the airlines and the airport, as well as the interests of multiagent (airlines, airports, and passengers), especially those influenced by flight banks, slot assignment and gate assignment are integrated into mixed set programming (MSP), and a real-time gate assignment model is built and solved through MSP coupled with sequential game. By this approach, the delay costs of multiagent can be minimized simultaneously; the fuel consumption of each airline can be basically equalized; the computation time can be significantly saved by sequential game; most importantly, the collaboration of the airlines and the airport is achieved so that the transferring cost caused by the delay of flight banks can be decreased as much as possible. A case study on small-scale flight delays verifies that the proposed approach is economical, robust, timesaving, and collaborative. A comparison of the traditional staged method and the proposed approach under medium- to large-scale flight delays proves that the integrative method is much more economical and timesaving than the traditional staged method.

(ProQuest: ... denotes non-US-ASCII text omitted.)

Academic Editor:Hu Shao

College of Civil Aviation, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China

Received 26 December 2013; Revised 7 May 2014; Accepted 8 May 2014; 1 June 2014

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

1. Introduction

According to the statistical data of China's civilian aviation in 2011 [1], the existing 175 airports include 3 4F-class airports, 30 4E-class airports, 40 4D-class airports, and 85 4C-class airports. The number of civilian airports is expected to increase up to 244 by 2020. Meanwhile, the reconstruction and expansion of most major airports will be performed to meet the increasing demands. In this case, the resource management of these airports will turn out to be increasingly complex. Therefore, a great number of researches have been presented to solve the problem of airport resource management, gate assignment included. Gate assignment problem can be divided into two categories: preassignment and real-time assignment.

In the aspect of preassignment, Bolat developed a gate assignment model that is aimed at minimizing the idle time of the gates both in 1996 and 2000; meanwhile, heuristic algorithm combined with branch-and-bound technique was designed for solution [2]. In 2001, Bolat devised a linearization representation of the same objective and replaced heuristic algorithm with genetic algorithm [3]. In 2003, You et al. [4] were devoted to the study of genetic algorithm, which promoted the multiobjective algorithm for the preassignment of airport gates. In 2005, Lim and Wang constructed a different model that is aimed at reducing the number of conflicts during aircraft operation, and the model was solved by combining tabu search with local search in heuristic algorithm [5]. In 2011, Li et al. proposed an assignment model to obtain the maximum comprehensive efficiency of airlines, airports, and passengers; besides, the solution algorithm was developed based on greedy tabu search [6].

In the aspect of real-time assignment, Cheng designed a gate scheduling knowledge base system [7] by utilizing mathematical programming techniques, in order to support preassignment and real-time assignment. In later studies, they developed two other models to establish a gate assignment expert system: network-based model [8] and rule-based reactive model [9]. In 2010, Li devised an assignment model that was aimed at maximizing the sum of all the flight eigenvalues (aircraft type, flight inbound/outbound time, and the number of passengers) and the gate eigenvalues (idle time of the gates) [10]. Furthermore, Wei and Liu proposed an approach to perform gate reassignment by minimizing the number of the flights assigned to the apron, the disturbance caused by the assignment, and the walking distance of passengers; meanwhile, a heuristic algorithm combining tabu search was adopted for optimization [11].

The existing research shows that the studies on gate preassignment have evolved and matured over time. However, a comprehensive consideration on the interests of multiagent, namely, airports, airlines, and passengers, has not been given to real-time gate assignment.

Additionally, flight bank [12], a decisive role in determining the satisfaction of passengers and the benefits of airlines, is generally considered in slot assignment rather than gate assignment. Nevertheless, the gate assignment will also be influenced by flight banks, because transfer passengers would have to wait longer if flight banks are delayed, which increases the delay cost of gate assignment. Flight bank is the product of the collaborative decision making (CDM) [13] for airports, airlines, and air traffic control center (ATCC). In CDM mechanism, airports, airlines, and ATCC should work collaboratively to control the entire operation cost. However, almost all kinds of assignment algorithms, such as gate assignment, aircraft sorting, and flight scheduling, are performed separately, which goes against the original intentions of CDM mechanism. In the existing real-time gate assignment [13], airports are given fixed schedule of the delayed flights. Airlines are not informed of the possible gate assignment schemes and not all the information of possible slot rearrangements are delivered to the airport, as a result, the flight banks may be delayed to a great extent. To solve this problem, the CDM should be implemented accurately: ATCC provides updated slots to airlines; airlines choose the slot assignment schemes corresponding to the optimal gate assignment (based on minimum cost principle); finally, the optimal gate assignment is carried out by the airport based on the provided slot assignment schemes. The innovation taking into account the impacts of flight banks while achieving CDM is capable of guaranteeing reasonable slot assignment and gate assignment, thereby saving delay cost for multiagent (airlines, airports, and passengers) significantly, connecting flight banks smoothly, and transferring passengers conveniently.

In order to achieve slot assignment and gate assignment at the same time, integrative recovery strategy [14] is considered as a solution. Generally, traditional integrated recovery strategies, such as MSP, are time-consuming, because the permutation and combination of the optional objects will become enormous with the increasing of the scale of the problem to be solved. However, sequential game has been applied in resource allocation [15, 16] and is proven to be timesaving by deleting the infeasible permutation and combination of the objects from the computation process. Besides, sequential game also guarantees that the benefits of the related game players are maximized. Therefore, sequential game is applied innovatively in real-time gate assignment for timesaving computation and effective cost control.

Consequently, this paper proposes a novel model taking into account the benefits of multiagent, the impact of flight banks, CDM mechanism, fairness principle, and sequential game between the airlines, in order to achieve the following goals. Firstly, the total delay cost, including the walking cost of passengers, the taxiing cost of aircraft, the idle cost of gates, and the waiting cost of transfer passengers should be minimized. Secondly, the taxiing fuel for aircraft of each airline should be balanced. Thirdly, the flight banks containing delayed flights should be connected effectively with minimum adverse impacts on the interests of the airlines. Lastly, unreasonable solutions should be excluded in the first place, thereby saving computation time and resources. To make the model work, MSP combined with sequential game is designed for modeling and solving.

The remainder of this paper is organized as follows. The real-time gate assignment model is established in Section 2. In Section 3, the detailed steps of the solution algorithm are provided. In Section 4, two cases (small-scale flight delays and medium- to large-scale flight delays) are given and the experimental results are analyzed accordingly. Finally, conclusions are drawn in Section 5.

2. Real-Time Gate Assignment Model

2.1. Variable Definition of the Model

The definitions of the variables in the model are given as follows.

(1) N denotes the set of flights and M denotes the set of gates, i , k ∈ N , j ∈ M , 0 < M < N ;

(2) W denotes the set of flight banks, w ∈ W , _{W m} denotes the set of flight banks for airline m , _{W m} ∈ W , _{t m w 1} is the scheduled arrival time of flight bank w for airline m , and _{t m w 2} is the actual arrival time of flight bank w for airline m , _{t m w 2} ...5; _{t m w 1} ;

(3) Q is the set of aircraft types, A is the set of airlines, n ∈ Q , m ∈ A , _{Q i} denotes the type of flight i , expressed in numbers, and the bigger _{Q i} is, the larger flight i is;

(4) S is the set of slots, s ∈ S , _{S m} is the set of slots for airline m when airline m exchanges slots with other airlines to cut the waiting time of transfer passengers, _{S m} ∈ S ;

(5) _{X i j} is a zero-one variable, and _{X i j} equals 1 when flight i is assigned to gate j , else _{X i j} equals 0; _{Y m w} is a zero-one variable, and _{Y m w} equals 1 when flight bank w belongs to airline m , else _{Y m w} equals 0;

(6) _{F i} is the fuel consumption of flight i per minute;

(7) T _{1 i} and T _{2 i} denote the taxiing time of flight i before and after the reassignment, respectively;

(8) _{P i} is the number of passengers in flight i ;

(9) L _{1 i} and L _{2 i} denote the walking time for the passengers of flight i before and after the reassignment, respectively;

(10) I _{1 j} and I _{2 j} denote the idle time of gate j before and after the reassignment, respectively;

(11) _{r m w} is the number of transfer passengers in flight bank w of airline m ;

(12) C 1 is the price of jet fuel per kilogram, C 2 is the walking cost of each passenger per minute, C _{3 j} is the cost of the idle time for gate j per minute, and C 4 is the waiting cost for each transfer passenger per minute;

(13) _{R i j} is the time when flight i arrives at gate j , _{L i j} is the time when flight i departs from gate j , and _{R k j} is the time when flight k arrives at gate j , _{R k j} > _{L i j} ;

(14) _{G j} denotes the type of gate j , expressed in numbers, and the bigger _{G j} is, the larger gate j is;

(15) Δ T is the buffer time between any two consecutive flights assigned to the same gate;

(16) _{I b j} denotes the beginning of the idle time for gate j and _{I e j} denotes the end of the idle time for gate j ;

(17) _{f S m} is the waiting cost of the transfer passengers for airline m , which is less than the waiting cost of the transfer passengers before the slot exchange of airline m ;

(18) _{X S m} is a zero-one variable, _{X S m} equals 1 when _{S m} is the slots combination for airline m after the exchange, else _{X S m} equals 0;

(19) _{Ω m} is the set of slot combinations which makes the waiting time of transfer passengers for airline m less after the slot exchange;

(20) Δ _{K n m} is the increased fuel consumption of type n aircraft belonging to airline m ; z is the number of airlines, so, 1 / z is the expected proportion, corresponding to the ideal situation of complete equalization for all airlines.

2.2. Objectives

( 1) Minimize the Increased Total Cost. The total cost involves fuel cost, walking cost of passengers, idle cost of gates, and waiting cost of transfer passengers. To achieve the goal of minimizing the increased total cost caused by flight delays, the following four values need to be minimized at the same time: taxiing time of aircraft, walking time of passengers, idle time of gates, and waiting time of transfer passengers. The objective function is formulated as follows: [figure omitted; refer to PDF] _{F i} ( T _{2 i} - T _{1 i} ) C 1 denotes the increased taxiing cost of flight i ; _{P i} ( L _{2 i} - L _{1 i} ) C 2 denotes the incremental walking cost for passengers of flight i ; ( I _{2 j} - I _{1 j} ) C _{3 j} denotes the change of the idle cost for gate j ; _{r m w} ( _{t m w 2} - _{t m w 1} ) C 4 denotes the increased waiting cost of transfer passengers in flight bank w of airline m .

( 2) Minimize the Increased Taxiing Time of Aircraft. Since fuel cost accounts for about 30% of the total operation cost for airlines, fuel cost decrease will make a huge difference in the cost control of airlines. Fuel cost reduction can be achieved by minimizing the incremental taxiing time of all the aircraft according to [figure omitted; refer to PDF]

( 3) Minimize the Increased Walking Time of Passengers. The reduction of walking distance or time improves the satisfaction of passengers. The purpose of minimizing the walking time of passengers can be realized by [figure omitted; refer to PDF]

( 4) Minimize the Increased Idle Time of Gates. As airport gates are the core resources of an airport, improving the utilization rate of the idle gates attributes to better airport operation. To realize this goal, the idle time of airport gates can be minimized by [figure omitted; refer to PDF]

( 5) Minimize the Increased Waiting Time of Transfer Passengers. Flight bank has been widely applied in hub airports, so that the transferring efficiency of passengers, the utilization rate of airport resources, and the operational effectiveness of airlines can be improved. Generally, flight bank is capable of connecting flights effectively thus minimizing the waiting time of transfer passengers. However, delayed flight banks will lead to a series of problems, such as increased waiting time of passengers and increased operation cost. The objective function that is aimed at reducing the increased waiting time caused by the delay of flight banks is given by [figure omitted; refer to PDF]

Theorem 1.

The increased waiting time of transfer passengers does not necessarily depend on slot assignment.

Proof of Theorem 1.

Suppose V is the set of delay time for all the flights, V = { _{v 1} , _{v 2} , ... , _{v z} } , k = 1,2 , ... , z , _{v k} = ( s , i ) means slot s is randomly assigned to flight i , and _{v k} = | _{t s} - _{t i} | , where _{t i} denotes the scheduled arrival time of flight i and _{t s} denotes the time of slot s . Since the number of flights is equal to the number of slots and all the delayed flights are not cancelled, each flight can be assigned to one and only one slot; then, we have [figure omitted; refer to PDF]

As slot s is randomly assigned to flight i and the number of slots is equal to the number of flights, | _{∑ s ∈ S t s} - _{∑ i ∈ N t i} | is a constant. Hence, the increased waiting time of transfer passengers does not necessarily depend on the slot assignment, but the delay of flight banks.

Theorem 2 (gate assignment hinges on the slot assignment).

Gate assignment depends on the arrival time of flights and the idle time of available gates; therefore, slot assignment plays a decisive role in gate assignment.

According to Theorems 1 and 2, the slot assignment for delayed flights should be implemented with minimum delay of flight banks, so that the optimal gate assignment with minimum delay cost can be produced. This is why flight bank is involved in the objective of minimizing the waiting cost of transfer passengers in gate assignment.

( 6) Minimize the Waiting Cost by Optimizing the Slot Assignment through Non-Zero-Sum Sequential Game. The slots assigned to airlines are exchangeable, so airlines can reduce the waiting time of transfer passengers by exchanging the slots with each other. The process of slot exchange can be achieved through non-zero-sum sequential game between airlines. In sequential game, all the airlines are aware of their previous policy or selection and have to make their current decisions according to their tradeoff of future possibilities. Zero-sum sequential game refers to the situation that the income of one side is equal to the loss of the other side. As our subject is about controlling the loss caused by the flight delays for all the related airlines, non-zero-sum sequential game theory [15] is adopted in this application. The model of non-zero-sum sequential game is given by [figure omitted; refer to PDF] where A denotes the set of airlines; _{S m} is the set of all optional slot series for airline m , ∀ m ∈ A ; _{ρ m} is the realization probability of _{S m} ; P ( ρ ) denotes the expected revenue matrix.

Theorem 3.

In a sequential game, any realization probability points to a behavior strategy.

Proof of Theorem 3.

_{ρ m} ( _{s m} ) = _{∏ α ∈ s m β m} ( α ) , where _{ρ m} ( _{s m} ) is the realization probability for airline m to obtain slot series _{s m} ( _{s m} ∈ _{S m} ) , _{β m} is the probability distribution of T ( _{h m} ) , and T ( _{h m} ) is the set of optional policies under information set _{h m} for airline m .

Therefore, any realization probability comes from a corresponding behavior strategy.

The set of behavior sequences for airline m on information set _{h m} is denoted by λ ( _{h m} ) , γ is an expansion of the behavior sequences denoted by λ ( _{h m} ) γ ( λ ( _{h m} ) γ = λ ( _{h m} ) ∪ γ ) , and the realization probability of λ ( _{h m} ) can be denoted by _{ρ m} ( λ ( _{h m} ) ) .

Consequently, the behavior γ on information set _{h m} can be confirmed by [figure omitted; refer to PDF] where _{ρ m} ( λ ( _{h m} ) ) > 0 and _{β m} ( γ ) can be any value, when _{ρ m} ( λ ( _{h m} ) ) = 0 .

Suppose that β = ( _{β 1} , _{β 2} , ... , _{β q} ) , where β is the behavior strategy set for all airlines, ρ = ( _{ρ 1} , _{ρ 2} , ... , _{ρ q} ) , where ρ is the corresponding realization probability and _{ρ 0} denotes the realization probability of the virtual player, nature, usually a fixed value, and S = _{S 0} × _{S 1} × ... × _{S q} , where S denotes sequence space and s = ( _{s 0} , _{s 1} , ... , _{s q} ) ∈ S , where s is a set of slot series. The expected revenue function can be expressed by [figure omitted; refer to PDF] where P ( s ) = P ( c ) , P ( c ) is the revenue of implementing s towards some end note c , and ^{∏ m = 0 q} _{ρ m} ( _{s m} ) is the realization probability of approaching c .

According to the above description, when the revenue P ( ρ ) for all airlines is maximized, the transferring cost for all the airlines can be achieved, and the objective function is given by [figure omitted; refer to PDF] where _{f S m} is the value of the objective function _{f 5} for airline m , when _{S m} is the slots combination after the exchange.

( 7) Balance the Increased Fuel Consumption for Each Airline. Fairness principle requires that the fuel consumption caused by flight delays should be averaged for airlines to bear. However, airlines are of different scales and aircraft are of different types, so the average fuel consumption should be made from the aspects of both aircraft and airlines. This goal is achieved by averaging the proportion of the fuel consumption change for a certain aircraft type belonging to a certain airline to the fuel consumption change for a certain aircraft type of all airlines. The objective is represented by [figure omitted; refer to PDF] where Δ _{K n m} / _{∑ m ∈ A} Δ _{K n m} is the proportion of the fuel consumption change of type n aircraft belonging to airline m to the fuel consumption change of all airlines' type n aircraft.

2.3. Integrative Assignment Model

According to the above analysis, the real-time gate assignment model based on the principle of minimum delay cost for multiagent can be expressed as follows: [figure omitted; refer to PDF] where (12) is the objective function. Equation (13) means every flight is assigned to one and only one gate. Equation (14) is the corresponding relationship between flight and gate. Equation (15) means each slot combination is adopted by one and only one airline. Equation (16) is the corresponding relationship of slot combinations and airlines. Equation (17) enforces that the type of the gate where the aircraft is assigned should match the type of the aircraft. Equation (18) stipulates that the idle time of the gate should be longer than buffer time for the sake of safety. Equation (19) indicates that the beginning of the idle time for any gate should be earlier than the arrival time of the flight which will be assigned to the gate, and the end of the idle time should be later than the departure time of the flight. Equation (20) refers to validity constraint.

Compared with the traditional staged model (the slot assignment is produced before the gate assignment), the advantages of the proposed model are presented as follows: ( 1 ) the sequential game helps to obtain better slot combinations for all the airlines and ( 2 ) the CDM mechanism contributes to generating gate reassignment with less delay cost of multiagent due to the collaboration of airlines and airports.

To solve the multiobjective optimization problem (MOOP) [17], the objectives are sorted in order of priority, because all the objectives cannot be optimized simultaneously. As the service concept is becoming more and more important, the waiting time and waiting time of passengers are given the highest priority. The second highest priority is the taxiing time of aircraft, because the fuel cost is the direct operation cost of airlines. Following the taxiing time of aircraft is the implicit idle cost of the airport. Fuel equalization is the lowest priority, because the slot exchange between airlines also contributes to the fairness principle when the fuel consumption is not equalized at the very beginning.

3. Solution Algorithm

Mixed set programming (MSP) [18-20] is a logic reasoning algorithm based on first-order logic and set reasoning. In MSP, set operations, quantifiers, Boolean logic, logic functions, date/time reasoning, and numerical constraints are integrated in one system; the reasoning on numeric types, such as reals and integers, is expanded to global reasoning over mixed domains of set types, such as Booleans and references. Most importantly, MSP makes the modeling and solving for constraint satisfaction problems (CSP) realizable. The so-called set programming here is to systematically integrating set reasoning and operational research algorithm, establishing a rigorous and complete set theoretical formulation based on set variables and solving the model by set reasoning algorithm, instead of simply combining set notations with set variables and set constraints. The MSP adopted in this paper involves three major parts, detailed as follows.

Part 1 (carry out optional slot assignment schemes).

Consider the following.

Step 1.

Sort the flight banks that have not been finished at time t by ascending order of scheduled arrival time, expressed as B ( t ) = { _{b 1} , _{b 2} , ... , _{b k} } , where B denotes flight bank set and k is the serial number of flight bank.

Step 2.

Let _{u k} equal the number of flights in flight bank k /the actual arrival time of flight bank k . Then, define the close time of flight bank k corresponding to the maximum _{u k} as t 1 , t 2 as the close time of the next flight bank when it has not been finished at time t and can be finished at time t 2 , and τ = min ... ( t 1 , t 2 ) .

Step 3.

Assign the flights of the flight bank corresponding to the maximum _{u k} to the time slots before τ by the order of scheduled arrival time. If the number of delayed flights is n , then n ! slot assignment plans will be generated.

Step 4.

Repeat Steps 1, 2, and 3 for the rest of the flight banks until all the flights are reassigned with slots. It should be noted that, when Part 1 is implemented, a number of slot assignment schemes are produced.

Part 2 (optimize the slot assignment schemes through non-zero-sum sequential game).

Consider the following.

Step 1.

Input the information needed to implement non-zero-sum sequential game, namely, airlines, delayed flights, and provided slots.

Step 2.

Implement non-zero-sum sequential game for all the airlines and calculate the delay cost of the airlines according to the optional slot assignment schemes. The non-zero-sum sequential game between airlines is implemented according to the following.

(1) In order to cut the delay cost of airline A, exchange the i st ( i = 1,2 , ... , n ) combination of flight and slot of airline A with the j st ( j = 1,2 , ... , m ) combination of flight and slot of airline B, and the exchange meet the requirements of heuristic rules.

(2) Repeat ( 1 ) till all the combinations of flights and slots of airline A are exchanged with that of airline B.

(3) In order to cut the delay cost of airline B, exchange the i st ( i = 1,2 , ... , n ) combination of flight and slot of airline B with the j st ( j = 1,2 , ... , m ) combination of flight and slot of airline A, and the exchange meet the requirements of heuristic rules.

(4) Repeat ( 3 ) till all the combinations of flights and slots of airline B are exchanged with that of airline A.

(5) Combine the above results, and the optional slot exchange schemes are obtained.

(6) Divide the optional slot exchange schemes into two categories: equilibrium schemes and nonequilibrium schemes. In equilibrium schemes, three kinds of situations are included: a win-win situation for airlines A and B, airline A wins and airline B loses, and airline A loses and airline B wins. Nonequilibrium schemes refers to the schemes that make both airlines lose, thereby should be deleted.

(7) Calculate the value of _{f 6} according to the equilibrium schemes.

Step 3.

Repeat Step 2 till the slot assignment scheme corresponding to the minimum delay cost for all the airlines is generated.

Part 3 (carry out the optimal gate assignment scheme).

Consider the following.

Step 1.

Read the preassignment results of all the flights and obtain the time periods of the available airport gates.

Step 2.

For the delayed flights without subsequent flight banks keep their gate assignment as far as possible.

Step 3.

For the delayed flights with subsequent flight banks, go to Step 4.

Step 4.

Select out the flights which are not delayed but assigned to the gates affected by the delayed flights, and the selection is made on flights which arrive within the span of 50 minutes around the scheduled arrival time of the delayed flights according to [8]. Combine these selected flights with the flights in Step 3, a new flight set is produced. Then, gate assignment for the flights of this flight set can be carried out based on the principle of minimum delay cost according to the types of the flights and the available gates.

Step 5.

Combine the assignment results of Steps 2-4, then the real-time gate assignment set is obtained. The real-time gate assignment set includes three parts: gates assigned to the delayed flights with subsequent flight banks, gates assigned to the delayed flights without subsequent flight banks, and gates assigned to the flights which are not delayed but affected by the reassignment of the delayed flights.

To design a solving strategy with preferable performance, heuristic rules are organically integrated in the algorithms. By this method, on one hand, the constraints in the optimization model can be strictly satisfied to ensure the feasibility of the solution; on the other hand, the search process can be flexibly controlled. The heuristic rules are given as follows:

(1) when the scheduled serial number of the flight bank for some delayed flights is k , then the actual serial number of the flight bank should be no less than k ;

(2) when airlines exchange their time slots with each other, the serial numbers of the corresponding flight banks should be as similar as possible.

The above three parts as well as the heuristic rules are implanted into depth first search algorithm (DFS) [14], so that the integrative research for slots assignment and gate assignment can be performed. As a result, the slot assignment is optimized to be consistent with the optimal gate assignment which satisfies the multiobjective set previously.

In traditional staged algorithm, the cooperation of airlines is not taken into account, so the slots for delayed flights of airline A can only be adjusted within airline A instead of airline B, and the slots for delayed flights of airline B can only be adjusted within airline B instead of airline A. As a result, the gate assignment may cause losses for both airlines.

Compared with the traditional staged algorithm, the proposed integrative algorithm generates the following advantages: ( 1 ) the slots are exchangeable between the airlines, so the transferring cost of airlines can be decreased as much as possible; ( 2 ) the slot assignment and gate assignment are integrated into the MSP which supports integrative modeling and solving, so CDM mechanism for the airlines and the airport can be well achieved; ( 3 ) based on the software POEM, an integrative MSP method which supports non-zero-sum sequential game is designed, so the gate assignment can be generated much more effectively.

4. Experimental Results

For integrative modeling and solving, the software POEM [14] is taken into application. In order to support sequential game, a game class is added into the program. Four parts are included in the game class: players (airlines), actions (slot exchanges), costs of the players (delay cost of the airlines after the slot exchanges), and total cost of the sequential game. Additionally, rule class, equilibrium class, nonequilibrium class, and result class are designed to run the program. The constraints on the behavior of all the players (rules for slot exchange) are defined in rule class; the equilibrium characteristics for sequential game is included in the equilibrium class; the nonequilibrium characteristics for sequential game is included in the nonequilibrium class; the schemes and the corresponding delay cost for each airline are generated and stored in the result class. By applying those classes in POEM, the sequential game for the airlines in Part 2 can be performed. Parts 1 and 3 are achieved by the original function of the software POEM.

The environment where the experiment is carried out is represented as follows: ( 1 ) CPU: Intel(R) Core(TM) i7-3770 CPU @ 3.40 GHz; ( 2 ) RAM: 8.00 GB; ( 3 ) system type: x86-based PC; ( 4 ) system manufacturer: Dell Inc.; ( 5 ) OS name: Microsoft Windows 7; ( 6 ) OS version: 6.1.7601 Service Pack 1 Build 7601.

4.1. A Case Study on Small-Scale Flight Delays

The data listed in Table 1 is from the 42 operational flights arriving from 9:20 to 11:00 at some major airport, involving three airlines and three types of aircraft. The airlines are Air China (CA), China Eastern (MU), and China Southern (CZ), symbolically denoted by C, E, and S, respectively. The types of the aircraft are small, medium, and large, symbolically denoted by C, D, and E, respectively.

Table 1: Flight information.

Flight number	Arrival time	Departure time	Aircraft type	Passenger	Flight bank	Airline
1	9:20	10:20	E	300	1	C
2	9:30	10:30	E	300	1	S
3	9:35	10:25	C	100	1	S
4	9:40	10:35	D	200	2	E
5	9:40	10:35	D	200	2	S
6	9:40	10:40	E	300	2	E
7	9:40	10:30	C	100	2	C
8	9:40	10:35	D	200	2	C
9	9:40	10:40	E	300	2	E
10	9:45	10:40	D	200	1	S
11	9:45	10:35	C	100	1	E
12	9:45	10:45	E	300	1	C
13	9:45	10:35	D	200	1	S
14	9:50	10:40	C	100	1	E
15	9:55	10:55	E	300	2	C
16	9:55	10:50	D	200	2	E
17	10:00	11:00	E	300	3	E
18	10:00	10:55	D	200	3	E
19	10:00	11:00	E	300	3	C
20	10:00	10:55	D	200	3	C
21	10:05	10:55	C	100	2	S
22	10:05	11:05	E	300	2	C
23	10:10	11:00	C	100	2	C
24	10:10	11:10	D	200	2	C
25	10:15	11:15	E	300	2	C
26	10:15	11:05	D	300	2	C
27	10:25	11:15	D	200	2	S
28	10:25	11:15	C	100	2	C
29	10:35	11:35	E	300	2	S
30	10:40	11:30	C	100	3	E
31	10:40	11:40	E	300	3	S
32	10:45	11:35	C	100	4	E
33	10:45	11:45	D	200	4	S
34	10:45	11:35	C	100	4	S
35	10:45	11:40	D	200	4	E
36	10:50	11:40	C	100	3	S
37	10:50	11:40	C	100	3	C
38	10:50	11:50	E	300	3	E
39	10:50	11:40	C	100	3	E
40	10:55	11:50	D	200	4	C
41	11:00	12:00	E	300	4	S
42	11:00	12:00	E	300	4	E

In Table 1, number 17 and number 37 are special flights, meaning the gates should remain the same when flight delays occur and real-time assignment is needed. The gate information is listed in Table 2, 35 gates involved.

Table 2: Gate information.

Gate number	Gate type	Walking time/min	Taxiing time/min	Idle period
1	C	8	12	9:00~12:00
2	E	9	11	9:00~12:00
3	E	9	10	9:00~12:00
4	E	8	9	9:00~12:00
5	E	7	8	9:00~12:00
6	E	6	7	9:00~12:00
7	E	8	6	9:00~12:00
8	E	6	5	9:00~12:00
9	E	7	4	9:00~12:00
10	E	8	3	9:00~12:00
11	D	9	2	9:00~12:00
12	D	8	3	9:00~12:00
13	E	7	4	9:00~12:00
14	E	5	5	9:00~12:00
15	E	3	4	9:00~12:00
16	E	2	5	9:00~12:00
17	E	1	6	9:00~12:00
18	E	2	8	9:00~12:00
19	E	4	10	9:00~12:00
20	E	4	9	9:00~12:00
21	D	7	8	9:00~12:00
22	D	8	11	9:00~12:00
23	D	9	10	9:00~12:00
24	D	9	11	9:00~12:00
25	D	7	12	9:00~12:00
26	C	6	13	9:00~12:00
27	D	6	14	9:00~12:00
28	E	5	15	9:00~12:00
29	D	6	20	9:00~12:00
30	D	7	17	9:00~12:00
31	D	8	18	9:00~12:00
32	D	9	18	9:00~12:00
33	C	9	20	9:00~12:00
34	C	9	21	9:00~12:00
35	C	8	22	9:00~12:00

The provided arrival times for flights number 13, number 17, and number 37 are 10:05, 10:30, and 11:10. As number 17 and number 37 are special flights, the adjustment should be made on flights arriving within the interval [9:50, 10:50] according to [8]. In other words, a part of the flights in flight bank 1 and flight bank 2 will be influenced by the delay. The original gate assignment is listed in Table 3.

Table 3: Original gate assignment information.

Flight	Gate	Flight	Gate	Flight	Gate
1	15	2	17	3	7
4	9	5	27	6	10
7	19	8	31	9	18
10	21	11	29	12	13
13	20	14	26	15	6
16	25	17	3	18	8
19	16	20	22	21	28
22	5	23	23	24	12
25	2	26	4	27	14
28	34	29	15	30	27
31	17	32	20	33	24
34	35	35	10	36	29
37	21	38	18	39	32
40	13	41	8	42	9

By utilizing the software POEM for the integrative modeling and solving, flights number 13, number 17, and number 37 are delayed to arrive at 10:05, 10:30, and 11:10, respectively, and the real-time gate assignment is produced with results listed in Table 4.

Table 4: Real-time gate assignment results.

Flight	Gate	Flight	Gate	Flight	Gate
1	15	2	17	3	7
4	9	5	27	6	10
7	19	8	31	9	18
10	21	11	29	12	13
13	30	14	4	15	16
16	23	17	3	18	6
19	20	20	12	21	24
22	14	23	25	24	5
25	28	26	32	27	22
28	15	29	17	30	26
31	7	32	11	33	10
34	4	35	18	36	35
37	21	38	19	39	1
40	13	41	8	42	9

4.1.1. Economic Efficiency

According to the practical operation of most airlines, the fuel consumptions for large aircraft, medium aircraft, and small aircraft are 46 kilograms per minute, 28 kilograms per minute, and 12 kg kilograms per minute, respectively. The idle costs of large gates, medium gates, and small gates are 6 CNY per minute, 4 CNY per minute, and 2 CNY per minute, respectively. In addition, the fuel price is 7 CNY per kilogram, the walking cost of passengers is 3 CNY per minute, and the waiting cost of transfer passengers is 1 CNY per minute.

The total cost is 301,986 CNY in the preassignment, while 305,560 CNY in the reassignment, so it is increased by 3,574 CNY, a small growth of 1.18%. After the reassignment, the increases of all kinds of costs are given in Figure 1.

Figure 1: Increases of all kinds of costs.

[figure omitted; refer to PDF]

Fuel cost is increased from 68,306 CNY to 69,860 CNY with a growth of 2.28%, and the fuel consumption increased by the flight delays is equalized for airlines to bear, illustrated in Figure 2. Walking cost is increased from 153,000 CNY to 154,200 CNY, with a growth of 0.78%. Idle cost is decreased from 17,980 CNY to 17,940 CNY, with a drop of 0.22%. Since the gates are of three types, the increased costs of each type are minimized at the same time, results represented in Figure 3. Waiting cost is increased from 62,640 CNY to 63,600 CNY, with a growth of 1.53%. The reason why the waiting cost is increased with just a minor growth of 1.53% is that most of the flight banks are not delayed. The increases of all costs turn out to be quite small after the reassignment; therefore, the real-time assignment is acceptable. Besides, the increased waiting cost accounts for 26% of the total increased cost, which testifies that taking into account the waiting cost of transfer passengers in the cost control is very necessary.

Figure 2: Balanced fuel consumption.

[figure omitted; refer to PDF]

Figure 3: Idle costs for different types of gates.

[figure omitted; refer to PDF]

Figure 2 shows that the increased fuel consumption of each type of aircraft is basically equalized for each airline, so the fairness principle is well abided by.

It is demonstrated in Figure 3 that the idle cost of small gates remains the same. For medium gates, the idle cost is increased by 80 CNY; and for large gates, the idle cost is decreased by 120 CNY. Although the idle cost of medium gates grows, the total cost of all gates turns out to be decreased, because the unit idle cost of large gates is more than that of medium gates.

Consequently, in the circumstance of small-scale flight delays, the real-time gate assignment model proposed in this paper is capable of achieving economic efficiency by adjusting a small number of gates.

4.1.2. Robustness

In fleet assignment [21, 22] and fleet planning [23, 24], robustness has been widely applied, but not in the research of gate assignment. As a complex system, gate assignment should also be robust: on one hand, the gates influenced by the flight delays can be restored in short term; on the other hand, the disturbance brought by the adjustment of the gates can be restricted within a certain scale. Theoretically, the evaluation criteria of the robustness for gate assignment include the utilization of gates, the recoverability of the affected gates and the service quality for passengers. Gate assignment with good performance is supposed to be generated with high utilization rate of gates, small-scale disturbance and convenient service for passengers.

Two major factors are considered to evaluate the robustness of the real-time assignment.

(1) Maximum utilization rate of the gates involves use rate and occupancy rate. Use rate is equal to the number of engaged gates divided by the total number of the gates; occupancy rate is equal to the holding time of the gates divided by the available time of all the available gates.

(2) Maximum service level for passengers means minimizing the growth of the walking time and waiting time for passengers.

Table 5 shows that the use rate is increased from 88.57% to 91.43% with a growth of 2.86%; the occupancy rate is increased from 36.75% to 37.86% with a growth of 1.11%; walking time is increased from 51,000 minutes to 51,400 minutes with a growth of 0.78%; waiting time is increased from 62,640 minutes to 63,280 minutes with a growth of 1.02%. The flight delays indeed lower the service quality for passengers by a small decrease; however, the utilization rate of the gates has risen with a big growth. To make a conclusion, the robustness of the real-time assignment scheme is well testified.

Table 5: Robustness evaluation.

	Utilization of gates	Service for passengers
Use rate (%)	Occupancy rate (%)	Walking time (%)	Waiting time (%)
Growth	2.86	1.11	0.78	1.02

4.1.3. Timeliness and Collaboration

The cost caused by flight delays can be reduced as much as possible through CDM mechanism. The following part of the case study is taken as an example to make a clear illustration on CDM.

ATCC provides three slots (slot 1 [10:05, 10:55] of flight bank 2, slot 2 [10:30, 11:30] of flight bank 3, and slot 3 [11:10, 12:00] of flight bank 4) for the three delayed flights (A: number 13, B: number 37, and C: number 17) to the airlines. It should be noted that number 13, number 17, and number 37 are flights from three different airlines. As the slots can be exchanged between any two airlines, 6 different slot assignment schemes will be produced theoretically; accordingly, the corresponding gate assignment schemes will also be different. However, if all the schemes are calculated in turn to locate the optimal one, the computation process will be very time-consuming and resource-wasting. So, non-zero-sum sequential game theory is utilized to exclude the infeasible schemes and find out the cost-optimal slot assignment scheme; the process is illustrated in Figure 4 (applying (10)).

Figure 4: Non-zero-sum sequential game for airlines.

[figure omitted; refer to PDF]

Figure 4 shows that only two feasible schemes are carried out from six optional choices, meaning 2/3 of the action sequences are excluded from the set of feasible solutions thereby saving 2/3 of the computation time. Suppose that the realization probability of each slot exchange plan is equal; then, the loss caused by flight delays for each slot assignment plan can be calculated by (11). In plan 1, slots 1, 2, and 3 are directly assigned to flights A, B, and C,respectively, causing a total loss of 1600 CNY. In plan 2, slots 1, 2, and 3 are assigned to flights A, C, and B, respectively, causing a total loss of 960 CNY.

Traditionally, the airlines will adopt plan 1 directly, and the slot assignment will be delivered to the airport without considering the related costs of the airport. However, the gate assignment scheme under this slot assignment is not the optimal choice. According to the calculation, the gate assignment corresponding to plan 2 is better than the gate assignment under plan 1. Under plan 2, the operation cost of both the airport and the airlines can be controlled more effectively; meanwhile, the satisfaction of the passengers can be improved to a greater extent. It can be concluded that real-time gate assignment is produced based on the information of the delayed flights; hence, varying degrees of flight delays (slot reassignment) will lead to different real-time gate assignment schemes, but only one is optimal when comparing the total costs of all the schemes. In turn, the optimal gate assignment scheme can provide a reference for airlines to reassign the delayed flights to updated slots provided by ATCC. In the whole process, CDM between the airlines (and the airport) is effectively achieved, thereby protecting the benefits of airlines, airports, and passengers.

4.2. A Case Study on Medium- to Large-Scale Flight Delays

In the traditional staged method, the slots are reassigned to the flights without consideration of minimizing the delay cost before the gate assignment; as a result, the real-time gate assignment without CDM mechanism may not be optimal. Nevertheless, in the integrative method presented in this paper, the slots can be interchanged between the airlines in the process of real-time gate assignment; therefore, the delay cost of the real-time gate assignment can be minimized as much as possible. To present a significant comparison of the integrative method and the traditional staged method, large-scale flight delays are introduced into the case study. The information on delayed flights before slot exchange is listed in Table 6 and the information on delayed flights after slot exchange is listed in Table 7. The computation results are given in Table 8.

Table 6: Delay information before the slot exchange.

Flight number	Arrival time	Departure time	Flight bank
4	9:50	10:45	2
5	9:50	10:50	2
8	9:55	10:50	2
9	10:15	11:15	3
12	9:50	10:50	2
13	10:00	10:50	1
16	10:10	11:05	2
17	11:00	12:00	4
23	10:40	11:30	2
24	10:30	11:30	2
27	10:40	11:30	2
37	10:55	11:45	3

Table 7: Delay information after the slot exchange.

Flight number	Arrival time	Departure time	Flight bank
4	9:50	10:45	2
5	9:50	10:50	2
8	9:55	10:50	2
9	10:40	11:40	2
12	10:00	11:00	1
13	9:50	10:40	2
16	10:10	11:05	2
17	10:55	11:55	3
23	10:15	11:05	3
24	10:30	11:30	2
27	10:40	11:30	2
37	11:00	11:50	4

Table 8: Comparison of the results generated by traditional staged method and integrative method.

	Fuel cost/CNY	Walking cost/CNY	Idle cost/CNY	Waiting cost/CNY	Total cost/CNY	Total increase/%	Time/min
Original cost	68,306	153,000	17,980	62,640	301,986	/	/
Staged method	70,448	158,400	17,940	65,880	312,668	3.54	10.17
Integrative method	69,860	157,800	17,830	64,080	309,570	2.51	2.66

As the equalization of fuel cost and the robustness of the gates almost remain the same, the comparison is mainly made on the costs and the computation time. Since the number of the optional slot assignment schemes is 132 and the number of the feasible schemes is 32, the computation time of the integrative method should be around 1/4 of the computation time needed in the traditional staged method. Table 8 shows that the staged method is able to reassign the gates appropriately but produces an increase of 3.54% on the total cost, and the computation process consumes 10.17 minutes. However, the integrative method just brings an increase of 2.51% on the total cost, and the computation process only takes 2.66 minutes. Therefore, the integrative method is superior to the traditional staged method in the aspects of cost control and computation time control (2.66/10.17 is approximately equal to 1/4), not only in the circumstance of the aforementioned small-scale flight delays, but also under the situation of medium- to large-scale flight delays.

Figure 5 gives a visualized comparison of each cost item for the staged method and the integrative method. The bar stands for the difference of the increase produced by those two methods, and the greater the value is, the more cost the integrative method can cut. Among these items, the most significant change caused by the integrative method is made in the waiting cost for transfer passengers, which is cut by 2.39%, and this is because ( 1 ) flight bank is taken into account in the optimization; ( 2 ) sequential game is applied in the slot exchange between airlines; and ( 3 ) gate assignment and slot assignment are implemented under the CDM mechanism.

Figure 5: Decreases generated by the integrative method compared with the staged method.

[figure omitted; refer to PDF]

According to the comparison under the condition of medium to large scale flight delays, the integrative method proposed in this paper is much superior to the traditional staged method.

4.3. Conclusions of the Case Studies

Based on the experimental results of Sections 4.1 and 4.2, the conclusion are made as follows.

(1) As the approach proposed in this paper is practical, the gate assignment problem is well solved; meanwhile, all the constraints posed in the multiobjective function are satisfied.

(2) The approach is well applied in minimizing delay cost under the situations of both small-scale flight delays and medium- to large-scale flight delays.

(3) The interests of both airlines and airports are taken into account, which contributes to the application of CDM mechanism.

(4) The non-zero-sum sequential game excludes the infeasible slot combinations, so the computation time of the approach is saved to a great extent. In the first case (small-scale flight delays), as the feasible slot assignment schemes account for 1/3 of the total slot combinations, the computation time is saved by around 2/3. In the second case (medium- to large-flight delays), because the feasible slot assignment schemes account for around 1/4 of the total slot combinations, the computation time is saved by about 3/4. If the proportion of the feasible schemes is smaller, the computation time can be saved much more significantly.

5. Conclusions

This research focuses on the integrative approach with sequential game to the problem of real-time gate assignment. The assignment model is formulated based on CDM mechanism and minimal delay cost principle for multiagent when flight delays occur; meanwhile, MSP combined with sequential game method is designed for calculation. The case studies for both small-scale and medium- to large-scale flight delays verify the validity of the integrative method. Firstly, all kinds of costs are minimized better than the traditional staged method, especially, the waiting cost of transfer passengers. Secondly, the increased fuel burn is basically balanced for each airline. Thirdly, the CDM of the airlines and the airport is well achieved. Lastly, more than half of the computation time needed in the traditional method is saved in the integrative method. In summary, due to the economic efficiency, robustness, collaboration, and timeliness, the integrative approach proposed in this paper is reasonable and feasible in restoring normal airport operation and guaranteeing regular air transportation.

Acknowledgments

This research is funded by the Key Program of National Natural Science Foundation of China (no. 61232002 and no. 60939003), China Postdoctoral Science Foundation (nos. 2012M521081 and 2013T60537), the Fundamental Research Funds for the Central Universities (no. NS2014066), and Postdoctoral Science Foundation of Jiangsu Province (no. 1301107C).

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

References

[1] Planning & Development Department of Civil Aviation Administration of China 2011 Statistical Data on Civil Aviation of China , China Civil Aviation Publishing House, Beijing, China, 2011.

[2] A. Bolat, "Procedures for providing robust gate assignments for arriving aircrafts," European Journal of Operational Research , vol. 120, no. 1, pp. 63-80, 2000.

[3] A. Bolat, "Models and a genetic algorithm for static aircraft-gate assignment problem," Journal of the Operational Research Society , vol. 52, no. 10, pp. 1107-1120, 2001.

[4] J.-J. You, C.-M. Ji, X. Fu, "New method for solving multi-objective problem based on genetic algorithm," Journal of Hydraulic Engineering , no. 7, pp. 64-69, 2003.

[5] A. Lim, F. Wang, "Robust airport gate assignment," in Proceedings of the 17th IEEE International Conference on Tools with Artificial Intelligence (ICTAI '05), pp. 74-81, November 2005.

[6] J.-H. Li, J.-F. Zhu, Q. Gao, "Airport gate assignment based on Greedy Tabu Search algorithm," Journal of Transportation Systems Engineering and Information Technology , vol. 11, no. 4, pp. 173-179, 2011.

[7] Y. Cheng, "Network-based simulation of aircraft at gates in airport terminals," Journal of Transportation Engineering , vol. 124, no. 2, pp. 188-196, 1998.

[8] C. Yu, "A knowledge-based airport gate assignment system integrated with mathematical programming," Computers and Industrial Engineering , vol. 32, no. 4, pp. 837-852, 1997.

[9] Y. Cheng, "A rule-based reactive model for the simulation of aircraft on airport gates," Knowledge-Based Systems , vol. 10, no. 4, pp. 225-236, 1998.

[10] W. Li, "Optimized assignment of civil airport gate," in Proceedings of the International Conference on Intelligent System Design and Engineering Application (ISDEA '10), vol. 2, pp. 33-38, October 2010.

[11] D. X. Wei, C. Y. Liu, "Airport gate reassignment problem," Journal of Nanjing University of Aeronautics and Astronautics , vol. 41, no. 2, pp. 257-261, 2009.

[12] W. Li A Method to Construct Flight Bank for Hub Airports , Nanjing University of Aeronautics and Astronautics, College of Civil Aviation, Nanjing, China, 2010.

[13] Q. Gao, J. Yan, J.-F. Zhu, "Airlines' optimization decision of slot allocation in CDM," Journal of Transportation Systems Engineering and Information Technology , vol. 11, no. 5, pp. 94-98, 2011.

[14] B. Zhu, J. F. Zhu, Q. Gao, "Constraint programming model of integrated recovery for aircraft and crew," Journal of Traffic and Transportation Engineering , vol. 13, no. 1, pp. 77-83, 2013.

[15] D. Gerardi, R. B. Myerson, "Sequential equilibria in Bayesian games with communication," Games and Economic Behavior , vol. 60, no. 1, pp. 104-134, 2007.

[16] Z.-J. Li, C.-T. Cheng, F.-X. Huang, X. Li, "Sequential game-based resource allocation strategy in grid environment," Journal of Software , vol. 17, no. 11, pp. 2373-2383, 2006.

[17] H. C. Gomes, F. de Assis das Neves, M. J. F. Souza, "Multi-objective metaheuristic algorithms for the resource-constrained project scheduling problem with precedence relations," Computers & Operations Research , vol. 44, pp. 92-104, 2014.

[18] J. Yan, T. S. Wu, Q. Gao, J. F. Zhu, "Slot switching model of airlines under cooperative game," Journal of Traffic and Transportation Engineering , vol. 12, no. 5, pp. 85-90, 2012.

[19] J. Y. Zhou, "A note on mixed set programming," in Proceedings of the IEEE The 7th International Symposium on Operations Research and Its Applications, pp. 131-140, 2008.

[20] J. Zhou, "Introduction to the constraint language NCL," Journal of Logic Programming , vol. 45, no. 1-3, pp. 71-103, 2000.

[21] X. H. Zhu, J. F. Zhu, Q. Gao, "The research on robust fleet assignment problem based on flight purity," Forecasting , vol. 30, no. 1, pp. 71-74, 2011.

[22] D. Y. Mou, Z. X. Zhang, "Robust fleet scheduling problem based on probability of flight delay," Journal of Civil Aviation University of China , vol. 28, no. 6, pp. 35-39, 2010.

[23] Y. Wang, H. Sun, "Heuristic algorithm to incorporating robustness into airline fleet planning," Systems Engineering--Theory & Practice , vol. 33, no. 4, pp. 963-970, 2013.

[24] H. Sun, P. Zhang, Y. Wang, "Fleet planning approach based on optimized fleet capacity allocation in airline networks," Journal of Southwest Jiaotong University , vol. 45, no. 1, pp. 111-115, 2010.