[PDF] The Airport Gate Assignment Problem: Scheduling Algorithms and

16700_3K0004584_honbun.pdf

The Airport Gate Assignment Problem: Scheduling

Algorithms and Simulation Approach

MARCH, 2012

Ahmed Thanyan AL-Sultan

Graduate School of e

nvironmental science (Doctor Course)

OKAYAMA UNIVERSITY

1

Contents

1 introduction 4

1.1 General preview .............................................

............ 5

1.2 previous works ......................................................

..... 7

2 Kuwait International Airport (KIA) 11

2.1 KIA gates terminal ......................................................

12

2.2 Data collection ......................................................

..... 14

3 Problem description and model formulation 17

3.1 Problem description ...................................................

18

3.2 Identify decision variables ..............................

................ 20

3.3 Constraints and objective function ........................

............ 22

4 Algorithms and data generation 24

4.1 Greedy algorithm

...................................................... .. 25

4.2 Other scheduling algorithms ......................................... 27

4.3 Tabu search heuris

tic .................................................. 30

4.3.1 New neighborhood search methods .......................... 30

4.3.2 The interval exchange move .................................. 31

4.3.3 The apron exchange move .................................... 33

4.3.4 Tabu short-term memory ..................................... 34

4.4 Data generation ......................................................

. 35 2

5 Results and analysis 37

5.1 Results .........................................................

......... 38

5.1.1 Result of objective 1 ........................................ .... 38

5.1.2 Result of objective 2 ............................................ 47

6 Simulation approach 53

6.1 Objective of the simulation approach ............................... 54

6.2 Arrival rate estimation and simulation steps ..................... 55

6.3 Simulation results .............................................

.......... 57

7 Conclusion 65

Bibliography 68

Acknowledgements 72

Appendix 73

3

Chapter 1

Introduction

4

1.1 General preview

The rapid development of airlines has made airports busier and more complicated. The assignment of schedule to available gates is a major issue for daily airline operations. We consider the over-constrained airport gate assignment problem (AGAP) where the number of flights exceeds the number of available gates, and where the objectives are to minimize the number of ungated flights and the total walking distance or connection times. The procedures used in this pr oject are to create a mathematical model formulation to identify decision variables to identify, constraints and objective functions. In addition, we will consider in the AGAP the size of each gate in the terminal and also the towing process for the aircraft. We will use a greedy algorithm and a Tabu search meta-heuristic to solve the problem and compare it with other scheduling methods. Actual and forecasted data will be simulated in the experiment. The greedy algorithm minimizes ungated flights while providing initial feasible solutions that allow flexibility in seeking good solutions, especially in case when flight schedules are dense in time. Experiments conducts give good results. The distance a passenger has to walk in any airport to reach various key areas, including departure gates, baggage belts and connecting flights provide for an important performance measure for the quality of any airport. While 5 certain walking distances are fixed, others are dynamic. In particular, the distances traversed by passengers from check-in counters to gates and from gate to gate, in the case of transfer or connecting passengers, change according to how scheduled flights are assigned to gates. This allows for the ground handling agents and airlines, together with airport authorities, to dynamically assign airport gates to scheduled flights so as to minimize walking distances while, consequently, minimizing connection times. Which flight to gate assignment policy to be used so as to achieve such minimum times can be derived at the start of such planning day based on published flights schedules and booked passenger loads. The airport gate assignment problem (AGAP) seeks to find feasible flight to gate assignments so that total passenger c onnection times and walking distances is minimized. Distances that are taken into account are those from check-in to gates in the case of embarking or originating passengers, from gates to baggage claim areas (check-out) in the case of disembarking or destination passengers and from gate to gate in the case of transfer or connecting passengers. In the over-constrained case, where the number of aircraft exceeds the number of available gates, we include the distance from the apron or tarmac area to the terminal for aircraft assigned to these areas. 6 The problem of assigning gates to flight arrivals and departures is an important decision problem in daily operations at major airports all over the world. Strong competition between airlines and the increasing demands of passengers for increased comfort has made the measures of quality in their decisions at an airport as important performance indices of airport management. This is why mathematical modeling of this problem and the application of Operations Research (O

R) methods to solve those models

have been studied widely in OR literature. The common characteristics of busy international airports usually involve serving a large number of different airlines, a large number of flights over day, and accommodating various types of aircrafts.

1.2 previous works

Much work has been centered on the gate assigning problem with the objective of minimizing distance cost (or variants of this). One of the first attempts to use quantitative means to minimize intra-terminal travel into a design process was given by Braaksma and Shortreed (1971). The assignment of aircraft to gates that mi nimize travel distances is an easily motivated and understood problem but a difficult one to solve. The total passenger walking distance is based on passenger embarkation and 7 disembarkation volumes, transfer passenger volumes, gate to gate distances, check in to gate distances and aircraft to gate assignments. In the gate assignment problem, the cost associated with the placing of an aircraft at a gate depends on the distances from key facilities as well as the relations between these facilities. The basic gate assignment problem is quadratic assignment problem as shown to be NP-hard in Obata (1979). Babic et al. (1984) formulated the gate assignment problem as linear 0-1 IP. A branch and bound algorithm is used to find the optimal solution where transfer passengers are not considered. Haghani and Chen (1998) proposed an integer programming formulation of the gate assignment problem and heuristic solution procedure for solving the problem. The multiple objective model for the gate assignments were proposed in Yan and Huo (2001) where the model is formulated as a multiple objective 0-1 integer programming. Network model (Yan and Chang, 1998) and simulation models (Cheng, 1998a, b) were also proposed to formulate the problem. Since the gate assignment problem is NP-hard, various heuristic approaches have been suggested by researches, e.g. Haghani and Chen (1998) proposed a heuristic that assi gns successive flights parking at the same gate when there is no overlapping. Flights are assigned based on the shortest walking distance coefficients. Xu and Bailey (2001) provide a 8 Tabu search meta - heuristic to solve the problem. The algorithm exploits the special properties of different types of neighborhood moves, and creates highly effective candidate list strategies. The work of Yan et al. (2008) considered stochastic disturbances in daily passenger demand that occur in actual operations. They established a stochastic - demand flight scheduling model, SDFSM. Two heuristic algorithms, based on arc-based and route based strategies, were developed to solve the SDFSM. In addition, previous work (Ding et el., 2004) has considered the over constrained gate assignment problem which addressed both the objectives of minimizing the number of ungated aircraft while minimizing total walking distance. In the work of AL-Sultan, A.T. (2011) considered in the airport gate assignment problem the size of each gate in the terminal and also the towing process for the aircraft. In addition, analyses were added for the buffer time that is the time that locks the aircraft gate after departure. In the current project, Actual and forecasted data will be simulated in the experiment to estimate the percentage of the ungated flights and walking distance cost.

Furthermore, we will compare between

four aircraft scheduling algorithms which are greedy algorithm and other three scheduling methods. We will use actual aircrafts arrival and departure schedules. The number of 9 passengers for each aircraft will be generated randomly using the Monte

Carlo method.

The Airport gate assignment problem (AGAP) seeks to find feasible flight to gate assignments so that the number of the flights that need be assigned to the apron and total passenger connection times, as can be proxies by walking distances, are minimized. This project is organized as follows. Since we will apply our mathematical model on a real data, in chapter 2 we explain Kuwait international airport gates terminal and the actual data collection. Next, we will describe the problem and explain the objective functions on chapter 3. In chapter 4, the aircrafts scheduling Algorithms that will be used in this project will be explained. The analysis of the results will be showed in chapter 5. The simulation approach will be explained in chapter 6. 10

Chapter 2

Kuwait International Airport (KIA)

11

2.1 KIA gates terminal

We will apply our model at Kuwait international airport (KIA) that has becomes busier after applying the "Open Skies" policy that applies to both passenger and cargo operations, forms an essential part of the Kuwait government's latest initiative to promote the state as a major centre for financial, commercial and economic activities in the Gulf Region. KIA is already serves more than 50 airlines currently connect Kuwait directly with over 100 international destinations; In addition, there is considerable scope for expansion. The airport underwent a massive renovation and expansion project from 1999-2001, in which the former parking lot was cleared and a terminal expansion was built. This incorporated new check-in areas, a new entrance to the airport, the construction of a multi-storey parking structure, and an airport mall. Kuwait International Airport can currently handle more than seven million passengers a year. A new general aviation terminal was completed in 2008 under a BOT scheme and is operated by Royal Aviation. Kuwait international airport has one terminal that has ten gates for the aircrafts. The gate numbers are 1,2,3,4,5,21,22,24,25 and 26. Figure 2.1 describes the shape of the terminal. 12

Figure 2.1 KIA's gates terminal

Next to the terminal there are stands (aprons) for the ungated flights, there are several locations for aircraft stands such as cargo flights stand area, VIP or privet flight stand area, and the regular stand area which is used mostly for the ungated commercial aircrafts. In this project, we will use actual aircraft arrival and departure schedules. The number of passengers for each aircraft will be generated randomly using the Monte

Carlo method.

13

2.2 Data collection

Table 2.1 presents a sample from the actual schedule (daily movement) for the arrival and departure flights for a specific week. The rest of the data is presented in the appendix.

The schedule contents:

1. A/L: Airline.

2. A/C: Type of aircraft.

3. Time: arrival / Departure time.

4. FLT: Flight number.

5. Arrival from / Departure to

6. Gate: gate number.

Table 2.1 Sample of the daily movement

A/L A/C

Arrival

Departure

FLT

From TimeGateFLT To Time Gate

JAI 737 574 COK 004025 573 COK 0140 25

RJA 319 5256 AMM00453 5257AMM0130 3

MEA

320 408 BEY 011021 409 BEY 0200 21

THY

737 1172 IST 011526 1173IST 0215 26

MSR

737 614 CAI 014522 615 CAI 0245 22

Note that the time which presented in the daily movement is the actual time for the arrival or departure time. For example, the arrival time for the first flight in table 2.1 is 0040 which means the aircraft arrived at 00:40. Furthermore, the rest of the data which is presented in the appendix shows 14 the daily movement for whole week. For example, if a flight arrived at time

14700 mean that the flight arrived at

time 21:00 in the 7th day (21*7 = 147).

From the collected data:

- We have 756 arrival flights and 754 departure flights. - From the arrival flights, we have 212 flights ungated (which means that

28.04% from the arrival flights are ungated).

- From the departure flights, we have 193 flights ungated (which means that 25.60% from the departure flights are ungated). Table 2.2 presents the types of aircrafts that could be assigned to each gate in the terminal. The sign "O" means that the type of aircraft can be assigned to the gate. We can notice that Gate 1 is the smallest gate in the terminal since it has the smallest number of types of aircraft which can be assigned to it. On the other hand, Gate 2, Gate 4, Gate 5, Gate 21 and Gate

22 are considered the largest gates in the terminal since they could be used

to any type of aircraft. 15 Table 2.2 types of aircrafts that could be assigned to each gate in the terminal A/C Gate1 Gate2 Gate3 Gate4Gate5Gate21Gate22Gate24 Gate25 Gate26

310 ż ż ż ż ż ż ż ż ż ż

319 ż ż ż ż ż ż ż ż ż ż

320 ż ż ż ż ż ż ż ż ż ż

321 ż ż ż ż ż ż ż ż ż ż

300
ż ż ż ż ż ż ż ż ż 330
ż ż ż ż ż ż ż 340
ż ż ż ż ż ż ż

727 ż ż ż ż ż ż ż ż ż ż

737 ż ż ż ż ż ż ż ż ż ż

747
ż ż ż ż ż ż 767
ż ż ż ż ż ż ż ż 777
ż ż ż ż ż ż DC10 ż ż ż ż ż ż ż E95 ż ż ż ż ż ż ż ż ż ż MD90 ż ż ż ż ż ż ż ż 16

Chapter 3

Problem description and model formulation

17

3.1Problem description

In this project, we consider the airport gate assignment problem (AGAP), where the number of flights exceeds the number of gates available. Our main objective is to minimize the number of ungated flights or minimize the number of flights assigned to the apron and the total walking distance or connection times. We will consider the size of each gate in the terminal. We represent i set of gates that can be assigned to flight. To show how i will be used, table 3.1 shows the values of i for each type of aircraft that been used in KIA.

Table 3.1 values of

i for each type of aircraft

Type of aircrafts

Values of

i

310,319,320,321,727,737,E95 26,25,24,22,21,5,4,3,2,1

300,767,MD90 26,25,24,22,21,5,4,3,2

767,MD90 26,25,22,21,5,4,3,2

330,340,DC10 26,22,21,5,4,3,2

747 26,22,21,5,4,2

777 22,21,5,4,3,2

According to the KIA officials, the towing process for the aircrafts will be applied if this aircraft is scheduled to a specific gate for more than 6 hours. The towing process means pulling off an aircraft from the terminal gate to the aircraft stand area. The same process will be used to pull off an aircraft from the stand area to the terminal gate for departure. According to the KIA officials, the towing process takes approximately one hour. One of 18 the reasons for using the towing process is if a flight is scheduled to use a gate for more than 6 hours, we pull off this aircraft from the assigned gate after one hour from its arrival to give an opportunity to other aircrafts to use this gate. Table 3.2 shows an example for using the towing process if a flight is scheduled to use a gate for more than 6 hours.

Table 3.2 example for using the towing process

Before applying the towing process

A/L

A/C Arrival Departure

FLT

From Time FLT To Time

KAC 320 672 DXB 1400 551 DAM 2100

After applying the towing process

A/L

A/C Arrival Departure

FLT

From Time FLT To Time

KAC

320 672 DXB 1400 - - 1500

KAC

320 - - 2000 551 DAM 2100

In addition, we will add a buffer time which is added between two continuous flights that assigned to the same gate. The time interval locked for particular aircraft equals to ],[ ii da . Where and are the arrival and the departure time of flight i. i a i d andrepresent the earliest and the latest time that the flight can be assigned to a gate. In this project, we will let the sum of andrepresents the buffer time. The goal of buffer time is to enlarge the interval betwee n any two adjacent aircrafts assigned to the same gate, which naturally decrease the probability of conflict between these two aircrafts. It is recommended to let the latest time higher 19 or equal to the earliest time since in KIA (in most of the cases) the delay departures are more than the early arrivals.

3.2Identify decision variables.

Notations:

N: Represents set of flights arriving to/departing from the airport. M: Represents set of gates available at the airport. n: Total number of flights. m: Total number of gates. i a : Arrival time of flight i. i d : Departure time of flight i. ji f , : Number of passengers transferring from flight i to flight j. lk w , : Walking distance for passengers from gate k to gate l. : The earliest time that the flight can be assigned to a gate. : The latest time that the flight can be assigned to a gate. : The buffer time which is equal to . i : Represents set of gates that can be assigned to flight i. DF: the difference between the departure and the arrival time (6 hours).

TP: The towing process (1 hour)

20 Additionally, we will make use of two dummy gates. Gate 0 represents the entrance or exit of the airport, and gate

1mrepresents the apron

where flights arrive at when no gates are available. Hence, represents the walking distance between gate kand the airport entrance or exit, and represents the number of originating departure passengers of flight i; represents number of the disembarking arrival passengers of flight i. So represent the walking distance between the apron and gate k (usually significantly larger than the distance among different gates). ok w , i f ,0 0,i f km w ,1

The binary variables

otherwise 0. 1) (0 gate toassigned is flight if 1mkkiy ik

The following constraint must be satisfied:

ji kkji&),,( )1(1mkyy jkik Implies or ji da ij da This condition disallows any two flights to be scheduled to the same gate simultaneously (except if they are scheduled to the apron). 21

3.3Constraints and objective function

Our objective is to minimize the number of flights assigned to the apron and the total walking distance. The mathematical formulation can be expressed as follow:

Minimize

(3.1) n i mi y 11,

Minimize (3.2)

n in jm km ln in i iiiiljkilkji wfwfyywf 111
11 11

0,0,,0,0,,,,

1 Equation (3.1) refers to the first objective which minimizes the number of flights assigned to the apron. And equation (3.2) refers to the second objective which is minimizes the total walking distance. We will call the value of equation (3.2) the walking distance cost.

The constraints:

1. Ensures that every flight must be assigned to one and only one gate or

assigned to the apron. .)1,(,1 , i kki niiy

Where

i represent set of gates that can be assigned to flight i.

2. Each flight's departure time is later than its arrival time

22
).1,(,niida ii

3. Two flights schedule cannot overlap if they are assigned to the same gate

,0))(( ,, jiijkjki adadyy ,1,&,,( ),1,jikkji ji mkn.1,0 , ki y 23

Chapter 4

Algorithms and data generation

24

4.1 Greedy algorithm

To solve the AGAP, we will use Greedy algorithm which uses a heuristic methods for minimizing the number of flights assigned to the apron. And then compare it with other scheduling method. First we will explain the basic details of greedy algorithm. The steps are as follow:

1. Sort the flights according to the departure time

Let represents the earliest available time (actually the departure time of last flight) of Gate k Set ).1(nid i )1(mkg k 1 k g for all k.

2. For each flight i.

- Find gate k such that and is maximized; and ik ag k g i k; - If such k exists, assign flight i to Gate k, update ik dg. - If k does not exist, assign flight i to the apron.

3. Output the result.

Note that in step 2 before assigning flight i to gate k, we will check if hours. If the answer is yes, we will divide this flight into two flights and apply the to wing process which will take TP=1 hour. The first flight's time interval becomes 6DFad ii ]1,[ ii aa and the second flight's time interval become . This means if a flight is scheduled to use a gate ],1[ ii dd 25
for more than 6 hours, we pull off this aircraft from the assigned gate after one hour from its arrival to give an opportunity to other aircraft to use this gate. Then for this flight's departure, if we find a gate, we will assign this flight to this gate one hour before its departure. Proof of the correctness of the greedy algorithm:

By induction, assume we have

found the optimum solution after scheduling flight i by the greedy algorithm. Now by this, we will assign flightto gate. But the optimal solution is to drop flightand assign to gate . Hence we can always replace by to make our greedy solution no worse than the optimal solution. There are two cases we should consider: f 'f kf )'(ff'k'ff

1. If , since we sort the flight by departure time, we have

as we considered the earliest available time of the gates, we find the greedy solution is better or at least equal to the optimal solution. 'kk k g' 'ff dd k g

2. If , we find that 'kk

' ' kk gg , and kk gg' ' since we choose the maximum in the greedy solution. The figure 4.1 illustrates this. k g 26
Figure 4.1 the correctness of the greedy algorithm

4.2 Other scheduling algorithms

In this section, we will present other three scheduling algorithms that will be compared with greedy algorithm. We call those three scheduling algorithms Method 1, Method 2 and Method 3. The only difference between those algorithms and greedy algorithm is the condition of flights sorting (according to the arrival or departure time) and also the earliest available time (maximized or minimized). k g We will explain in more detail the difference between those algorithms by showing the steps for each aircraft scheduling method. 27

Method 1

1. Sort the flights according to the arrival timeLet

represents the earliest available time (actually the departure time of last flight) of Gate k Set ).1(nid i )1(mkg k 1 k g for all k.

2. For each flight i.

- Find gate k such that and is minimized; and ik ag k g i k; - If such k exists, assign flight i to Gate k, update ik dg . - If k does not exist, assign flight i to the apron.

3. Output the result.

Method 2

1. Sort the flights according to the arrival time

Let represents the earliest available time (actually the departure time of last flight) of Gate k Set ).1(nid i )1(mkg k 1 k g for all k.

2. For each flight i.

- Find gate k such that and is maximized; and ik ag k g i k; - If such k exists, assign flight i to Gate k, update ik dg. - If k does not exist, assign flight i to the apron.

3. Output the result.

28

Method 3

1. Sort the flights according to the departure timeLet

represents the earliest available time (actually the departure time of last flight) of Gate k Set ).1(nid i )1(mkg k 1 k g for all k.

2. For each flight i.

- Find gate k such that and is minimized; and ik ag k g i k; - If such k exists, assign flight i to Gate k, update ik dg. - If k does not exist, assign flight i to the apron.

3. Output the result.

Note that we will apply in step 2 for each of the three scheduling algorithms as we did for greedy algorithm. In step 2, we will apply the towing process. The conditions are the same which as follow: before assigning flight i to gate k, we will check if 6DFad ii hours. If the answer is yes, we will divide this flight into two flights and apply the towing process which will take TP=1 hour. The first flight's time interval becomes and the second flight's time interval become. ]1,[ ii aa],1[ ii dd Table 4.1 summarizes the difference between greedy algorithm and other scheduling algorithms. 29
Table 4.1 difference between greedy algorithm and other scheduling algorithms

Method

Flight sorting

k g㩷 greedy departure maximized

Method 1 arrival minimized

Method 2 arrival maximized

Method 3 departure minimized

4.3 Tabu search heuristic

Tabu search (TS) algorithm is specially designed for the AGAP. TS is meta-heuristic approach that is recognized as a very effective tool for many combinatorial optimization problems. The basic TS approach is to search for the optimum solution with the assistance of an adaptive memory procedure that proceeds as follows. At each iteration, candidate neighborhood moves are evaluated, which then lead from the current solution to a new solution.

4.3.1 New neighborhood search methods

- The insert move: move a single flight to a gate other that the one it currently assigns. This move is the same as the original insert move. - The interval exchange move: exchange two flight intervals in the current assignment. A flight interval consists of one or more consecutive flights in one gate. 30
- The apron exchange move: exchange one flight which has been assigned to the apron with a flight that is assigned to a gate currently. We now discuss the interval exchange move and apron exchange move in greater detail.

4.3.2 The interval exchange move

The essential reason for the interval exchange move is to find two compatible intervals, which will allow us to get a feasible solution. In order to get this, interval data should contain four time points: the earliest available time (t1), the start time (t2), the end time (t3) and latest available time (t4). Figure 4.2 illustrates the meaning of these four time points.

Figure 4.2 the four time points of an interval

Further to this, we define two functions on intervals. Extend Left () extends the current interval by adding the flight which is just left to it, and Extend Right () extends the current interval by adding the flight which is just right to it. 31
Additionally, previous (i) returns the flight just arranged before flight i in the same gate, next (i) returns the flight just arranged after flight i. With these, we can now stat an algorithm for finding compatible intervals in Algorithm 1.

Algorithm 1 finding compatible intervals

1. Select two flights a, b in different gate, where a, b have overlap time.

2. Initialize interval A

a ,interval B b;

3. A.t1

previous (a). Departure;

4. A.t2

a. arrival;

5. A.t3

a. departure;

6. A.t4

next (a). Arrival;

7. B.t1

previous (b). Departure;

8. B.t2

b.arrival;

9. B.t3

b.departure;

10. B.t4

next (b). Arrival;

11. Success

true;

12. While A and B are incompatible and success is true do

13. If (A.t2 < B.t1 and extend left (B))

14. Success

false; 32

15. If (B.t2 < A.t1 and extend left (A))

16. Success

false;

17. If (A.t3 > B.t4 and extend right (B))

18. Success

false;

19. If (B.t3 > A.t4 and extend right (A))

20. Success

false;

21. End while

22. If success

23. Exchange interval A and B;

24. Else output "exchange Failed";

4.3.3 The apron exchange move

The apron exchange move is used to deal with the flights that are assigned to the apron. In each move, we exchange one flight that is assigned to the apron currently with a flight that has been assigned to a gate. As the minimal number of flights out of the gates has been determined by the greedy algorithm, we cannot perform a many- many exchange, so we can only effect a single flight exchange. 33

4.3.4 Tabu short-term memory

Tabu search memory plays an important role in the search process. It forbids the solution attribute changes recorded in the short-term memory to be reused. How long a restricti on is in effect depends on the tabu tenure parameter, which identifies the number of iterations a particular restriction remains in force (F. Glover and M. Laguna, 1997) In our AGAP problem, since there are three types of neighborhood search moves, the tabu short-term memory can be implemented as follows (where iter denotes the current iteration number):

1. Insert Move: denoted as

),( , ),(liki tenuretabuiterlikitabu_)),(),(( to prevent the move ; ),(),(liki

2. Interval Exchange move: denoted as

tenuretabuiterldckbatabuldckba_)),,(),,((),,,(),,( to prevent the move ),,(),,(kdclba;

3. Apron Exchange Move: denoted as

tenuretabuiterOUTbkatabuOUTbka_),(),((),.(),( to prevent the move ),(),(kbOUTa. 34

4.4 Data generation

The arrival time and the departure time for flight i are actual data from the schedule department at Kuwait international airport. But other data should be generated or assumed to apply our model. Those data are concerning the walking distance and number of passengers. First for the walking distance, we assume that the distance measure between two gates which are next to each other is 1 unite. For example, if one passenger arrived at gate 25 his walking distance to the passport control is 5 units (The distance measure is known as Manhatten Distance). Table 4.2 represents a summary for the assumed walking distance from a specific gate to the passport control.

Table 4.2 walking distance

Gate Distance (in units)

1,21 2 2,22 1 3,24 4 4,25 5 5,26 6

Apron

10 We can use table 4.2 to assume the walking distance from gate k to the airport entrance or exit ( ) or the walking distance from the airport entrance or exit to gate k (). For the transferring passengers, the walking distance from gate k to gate l () is randomly generated in the interval [1, 10]. 0,k w k w ,0 lk w , 35
Now for the arriving passengersand the departing passengers are randomly generated from different interval sizes depending on the type of the aircraft. Table 4.3 represents the scenarios to generate the arriving and the departing passengers. 0,i f i f ,0 Table 4.3 data generation for the arriving and departing passengers Type Data

Generation

310
[180,280] 319
[80,126] 320
[80,180] 321
[86,186] 300
[235,335] 330
[235,335] 340
[195,295] 727
[87,187] 737
[89,189] 747
[324,424] 767
[88,188] 777
[244,344]

DC10[270,370]

E95 [80,110]

MD90[87,187]

There are rarely small numbers of passengers transferring from one flight to another flight. The number of transfer passengers will increase if flight schedules are close, but not too close (At least 1 hour differen t). The number of transferring passengers from flight i to flight j () is usually within a certain interval, say [1, 50]. ji f , 36

Chapter 5

Results and analysis

37

5.1Results

We implement R (statistical software) to solve the problem. We have two objective functions. The first objectiv e function minimizes the number of flights assigned to the apron. And the second objective function minimizes the total walking distance. In this chapter, we will present the detailed results and analysis for both objective functions separately.

5.1.1 Result of objective 1

We will represent the results for each scheduling algorithm for the first objective function which is minimizing th e number of ungated flights. First, we will use greedy algorithm and then Method 1 then Method 2 and finally

Method 3.

First, we will apply greedy algorithm to obtain initial feasible solutions for the first objective function. Table 5.1 represents a sample for the output for the aircraft scheduling. We can notice from the presented table that the first five flights have no arrival information since those flights arrived in the previous day. 38
Table 5.1 the output for the aircraft scheduling using greedy algorithm A/L

A/C Arrival Gate Departure

From time To time AXB

737 - - 2 TRV/CCJ 0010

SYZ

320 - - 1 DAM 0020

MSR

320 - - 4 LXR 0030

LZB

320 - - 5 BOJ 0040

IAC

320 - - 21 BOM/MAA 0050

... ... ... ... ... ... ... RJA

310 AMM 2310 1 AMM 2405

KLM

330 AMS 2315 Apron AMS 2435

JZR

320 DXB 2350 3 - 2450

PIA

310 LHE 2355 22 PEW/LHE 2510

We have used the buffer time (

which is equal to ) that will be added between two continuous flights that assigned to the same gate. The time interval locked for particular aircraft equals to ],[ i d i a . By using greedy algorithm, we tried equal to 0, 10, 20 and 30 minutes. In addition, we have tried

0 4 minutes but output gives negative result.

The next results represent the output results for using greedy algorithm for the incoming and outgoing flights for different values o f . Table 5.2 represents the output analysis for the ungated flights for different values of . 39
Table 5.2 output analysis for the ungated flights using greedy algorithm 㩷 㩷

0 㩷10

IncomingOutgoingIncoming Outgoing

Greedy algorithm 85 82 112 113

Difference from the actual data127 111 100 80

Saving percentage 59.91% 57.51% 47.17% 41.45%

㩷

3020㩷 㩷

IncomingOutgoingIncoming Outgoing

Greedy algorithm 135 136 168 168

Difference from the actual data77 57 44 25

Saving percentage 36.32% 29.53% 20.75% 12.95%

From the output, after applying Greedy algorithm, the total number of ungated flights for

0 is 85 for the incoming flights and 82 for the

outgoing flights. The difference between the actual data and the output is

127 for the incoming flights and 111 for the outgoing flights. Note that the

number of the ungated flights for the actual data is 212 in the incoming flights and 193 in the outgoing flights. So we have minimized the number of ungated flights by 59.91% in the incoming and 57.51% for the outgoing flights.

Choosing the values of

or depends on the airports conditions. In KIA the delay departure flights are more than the early arrivals. As a result, KIA could consider giving a buffer time for the departure flights more than the arrival flights (i.e. letting ). For example, if KIA agree to let

30 minutes then the possible time intervals for flightare i

40
]30,0[ ii daand ]20,10[ ii da. Both intervals give same result regarding the number of ungated flights and saving percentage. We will summary the output for the ungated flights by using greedy algorithm in table 5.3 by showing the positive and negative results for the different values of and. A positive result means that the saving percentage for the ungated flights is positive. However, a negative result means that the saving percentage for the ungated flights is negative. The (O) mark shows a positive result and (-) mark shows a negative result. Table 5.3 positive and negative results using different values of and. 0 10 20 30 40 0 O

O O O -

10

O O O - -

20

O O - - -

30 O - - - -

40 - - - - -

Next, we will apply Method 1 to obtain initial feasible solutions for the first objective function (minimize the number of flights assigned to the apron). Table 5.4 represents a sample for the output of the aircraft scheduling. 41
Table 5.4 the output for the aircraft scheduling using Method 1 A/L A/C

Arrival Gate Departure

From time To time AXB

737 - - 2 TRV/CCJ 0010

SYZ

320 - - 1 DAM 0020

MSR

320 - - 4 LXR 0030

LZB

320 - - 5 BOJ 0040

IAC

320 - - 21 BOM/MAA 0050

... ... ... ... ... ... ... RJA

310 AMM 2310 25 AMM 2405

UAL

777 - 2315 3 IAD 2345

KLM

330 AMS/BAH2315 22 AMS 2435

KAC

340 - 2320 21 KUL 2350

The next results represent the output results for using Method 1 for the incoming and outgoing flights for different values of . Table 5.5 represents the output analysis for the ungated flights for different values of . Table 5.5 output analysis for the ungated flights using Method 1 㩷 㩷

0 㩷10

Incoming

Outgoing Incoming Outgoing

Method 1 93 102 115 122

Difference from the actual data 119 91 97 71

Saving percentage 56.13% 47.15% 45.75% 36.79%

㩷

3020㩷 㩷

Incoming

Outgoing Incoming Outgoing

Method 1 145 147 177 184

Difference from the actual data 67 46 35 9

Saving percentage 31.60% 23.83% 16.51% 4.66%

From the output, after using Method 1, the total number of ungated flights for

0 is 93 for the incoming flights and 102 for the outgoing

42
flights. The difference between the actual data and the output is 119 for the incoming flights and 91 for the outgoing flights. We have minimized the number of ungated flights by 56.13% for the incoming and 47.15% for the outgoing flights. Then will apply Method 2 to obtain initial feasible solutions for the first objective function (minimize the number of flights assigned to the apron). Table 5.6 represents a sample for the output of the aircraft scheduling. Table 5.6 the output for the aircraft scheduling using Method 2 A/L A/C

Arrival Gate Departure

From time To time AXB

737 - - 2 TRV/CCJ 0010

SYZ

320 - - 1 DAM 0020

MSR

320 - - 4 LXR 0030

LZB

320 - - 5 BOJ 0040

IAC

320 - - 21 BOM/MAA 0050

... ... ... ... ... ... ... RJA

310 AMM 2310 4 AMM 2405

UAL

777 - 2315 5 IAD 2345

KLM

330 AMS/BAH2315 Apron AMS 2435

KAC

340 - 2320 Apron KUL 2350

The next results represent the output results for using Method 2 for the incoming and outgoing flights for different values of . Table 5.7 represents the output analysis for the ungated flights for different values of . 43
Table 5.7 output analysis for the ungated flights using Method 2 㩷 㩷

0 㩷10

Incoming

Outgoing Incoming Outgoing

Method 2 94 99 121 129

Difference from the actual data 118 94 91 64

Saving percentage 55.66% 48.70% 42.92% 33.16%

㩷

3020㩷 㩷

Incoming

Outgoing Incoming Outgoing

Method 2 147 154 178 182

Difference from the actual data 65 39 34 11

Saving percentage 30.66% 20.21% 16.04% 5.70%

From the output, after using Method 2, the total number of ungated flights for

0 is 94 for the incoming flights and 99 for the outgoing

flights. The difference between the actual data and the output is 118 for the incoming flights and 94 for the outgoing flights. We have minimized the number of ungated flights by 55.66% for the incoming and 48.70% for the outgoing flights. Finally, we will apply Method 3 to obtain initial feasible solutions for the first objective function (minimize the number of flights assigned to the apron) Table 5.8 represents a sample for the output of the aircraft scheduling. 44
Table 5.8 the output for the aircraft scheduling using Method 3 A/L A/C

Arrival Gate Departure

From time To time AXB

737 - - 2 TRV/CCJ 0010

SYZ

320 - - 1 DAM 0020

MSR

320 - - 4 LXR 0030

LZB

320 - - 5 BOJ 0040

IAC

320 - - 21 BOM/MAA 0050

... ... ... ... ... ... ... RJA

310 AMM 2310 1 AMM 2405

AXB

737 CCJ/IXE 2305 24 IXE/CCJ 2410

KLM

330 AMS/BAH2315 Apron AMS 2435

JZR

320 DXB 2350 4 - 2450

The next results represent the output results for using Method 3 for the incoming and outgoing flights for different values of . Table 5.9 represents the output analysis for the ungated flights for different values of . Table 5.9 output analysis for the ungated flights using Method 3 㩷

0㩷 10㩷

IncomingOutgoingIncoming Outgoing

Method 3 141 141 156 153

Difference from the actual data 71 52 56 40

Saving percentage 33.49% 26.94% 26.42% 20.73%

㩷 㩷

3020 㩷

IncomingOutgoingIncoming Outgoing

Method 3 178 181 198 200

Difference from the actual data 34 12 14 -7

Saving percentage 16.04% 6.22% 6.60% -3.63%

From the output, after using Method 3, the total number of ungated flights for

0 is 141 for the incoming flights and 141 for the outgoing

45
flights. The difference between the actual data and the output is 71 for the incoming flights and 52 for the outgoing flights. We have minimized the number of ungated flights by 33.49% for the incoming and 26.94% for the outgoing flights. Note that when we let

30 minutes, the output gives

negative result in the outgoing flights since the saving percentage is not positive. In table 5.10, we will compare greedy algorithm and the other aircraft scheduling algorithms (Method 1, Method 2 and Method 3) by taking the average between the incoming and outgoing flights for the saving percentage for the ungated flights for different values of . Table 5.10 Saving percentage averages comparison for the ungated flights

Algorithm

㩷

0 㩷10 20㩷 㩷30

Greedy 58.71% 44.31% 32.93% 16.85%

Method 1 51.64% 41.27% 27.72% 10.59%

Method 2 52.18% 38.04% 25.44% 10.87%

Method 3 30.22% 23.58% 11.13% 1.49%

From table 5.10, we conclude that greedy algorithm gives the best result among all the other scheduling methods regarding the saving percentage for the ungated flights. Method 1 and Method 2 give almost same percentage. However, Method 3 gives the worst result among the other scheduling methods. 46

5.1.2 Result of objective 2

Before applying the scheduling algorithms to get an initial feasible solution for the first objective function, we have estimated the walking distance cost for the actual data by generating random data for the number of passengers and walking distance. The estimated cost was 1,509,752. In this section, we will use the previous output for the ungated flights to find the solution for the second objective function (minimize the total walking distance). To do this, we must generate random data for the number of passengers and walking distance as explained in the data generation section in chapter 4. The method that will be used to solve the second objective function is Tabu search heuristic which was also explained in chapter 4. First we will present the results by using the results of greedy algorithm and then Method 1 then Method 2 and finally Method 3. First, we will use the result of greedy algorithm. Table 5.11 represents the sample for the generated data for the number of passengers and the walking distance for each flight. 47
Table 5.11 generated data for the number of passengers and the walking distance (greedy algorithm) A/L A/C

Arrival

j f ,0 Gate ji W ,ji f ,0,i f

Departure

From time To time AXB

737 - - 0 2 2 0 178TRV/CCJ 0010

SYZ

320 - - 0 1 1 0 137DAM 0020

MSR 320 - - 0 4 4 0 127LXR 0030

LZB

320 - - 0 5 5 0 99 BOJ 0040

IAC

320 - - 0 21 6 0 140BOM/MAA 0050

DLH

330 - - 0 2 2 0 322FRA 0055

AFG 310 - - 0 1 1 0 236KBL 0100

KAC

320 BEY 0005 80 4 4 0 0 - 0105

RJA

319 AMM 0045 1075 5 44 97 AMM 0130

... ... ... ... ... ... ... ... ... ... ... RJA

310 RJA 2310 2121 2 0 0 AMM 2405

KLM

330 KLM 2315 327Apron8 0 0 AMS 2435

JZR

320 JZR 2350 1543 4 0 0 - 2450

PIA

310 PIA 2355 24622 1 0 0 - 2510

Table 5.12 presents the estimated walking distance cost with different values of . The saving percentages are calculated by comparing the estimated walking distance cost after using the Tabu search heuristic with the estimated walking distance cost for the actual data which is 1,509,752. Table 5.12 Estimated walking distance cost and actual data comparison by using greedy algorithm 㩷 0 10 20 30 walking distance cost 1242082 1351051 1413588 1497324

Saving percentage 17.73% 10.51% 6.37% 0.82%

With a buffer time

0 the walking distance costs was 1,242,082. This

means that the walking distance saving percentage is 17.73%. Next, we will use the result of Method 1. Table 5.13 represents the sample for the generated data for the number of passengers and the walking distance for each flight. 48
Table 5.13 generated data for the number of passengers and the walking distance (Method 1) A/L A/C

Arrival

j f ,0ji W , Gate ji f ,0,i f

Departure

From time To time AXB

737 - - 0 1 0 0 134TRV/CCJ 0010

SYZ

320 - - 0 2 0 0 84DAM 0020

MSR

320 - - 0 3 0 0 123LXR 0030

LZB

320 - - 0 4 0 0 135BOJ 0040

IAC

320 - - 0 5 0 0 123BOM/MAA 0050

DLH

330 - - 0 21 0 0 239FRA 0055

AFG

310 - - 0 22 0 0 276KBL 0100

KAC

320 BEY 0005 15824 0 0 0 - 0105

JAI

737 COK 0040 96 25 7 39189COK 0140

... ... ... ... ... ... ... ......... ... RJA

310 AMM 2310 22325 3 33180AMM 2405

UAL

777 - 2315 0 3 1 16292IAD 2345

KLM

330 AMS/BAH 2315 23822 0 0 295AMS 2435

KAC

340 - 2320 0 21 6 4 199KUL 2350

Table 5.14 presents the estimated walking distance cost with different values of . With a buffer time0 the walking distance costs was

1,309,913. This means that the walking distance saving percentage is

13.24%. However, the saving percentage is negative when we let

30
minutes. Table 5.14 Estimated walking distance cost and actual data comparison by using Method 1 㩷 0 10 20 30 walking distance cost 130991313383981442087 1561896

Saving percentage 13.24% 11.35% 4.48% -3.45%

Next, we will use the result of Method 2. Table 5.15 represents the sample for the generated data for the number of passengers and the walking distance for each flight. 49
Table 5.15 generated data for the number of passengers and the walking distance (Method 2) A/L A/C

Arrival

j f ,0 Gate ji W ,ji f ,0,i f㩷

Departure

From time To time AXB

737 - - 0 1 0 0 134 TRV/CCJ 0010

SYZ

320 - - 0 2 0 0 84 DAM 0020

MSR

320 - - 0 3 0 0 123 LXR 0030

LZB

320 - - 0 4 0 0 135 BOJ 0040

IAC

320 - - 0 5 0 0 123 BOM/MAA 0050

DLH

330 - - 0 21 0 0 239 FRA 0055

AFG

310 - - 0 22 0 0 276 KBL 0100

KAC

320 BEY 0005 15824 0 0 0 - 0105

JAI

737 COK 0040 96 3 7 39189 COK 0140

... ... ... ... ... ... ... ...... ... ... RJA

310 AMM 2310 2234 3 33180 AMM 2405

UAL

777 - 2315 0 21 1 16292 IAD 2345

KLM

330 AMS/BAH 2315 238Apron0 0 295 AMS 2435

KAC 340 - 2320 0 Apron6 4 199 KUL 2350

Table 5.16 presents the estimated walking distance cost with different values of . With a buffer time0 the walking distance costs was

1,294,204. This means that the walking distance saving percentage is

14.28%. However, the saving percenta

ge is also negative when we let

30 minutes.

Table 5.16 Estimated walking distance cost and actual data comparison by using Method 2 㩷 0 10 20 30 walking distance cost 1294204138266214674411557137

Saving percentage 14.28% 8.42% 2.80% -3.14%

Finally, we will use the result of Method 3. Table 5.17 represents the sample for the generated data for the number of passengers and the walking distance for each flight. 50
Table 5.17 generated data for the number of passengers and the walking distance (Method 3) A/L A/C

Arrival

j f ,0 Gate ji W ,ji f ,0,i f

Departure

From time To time AXB

737 - - 0 1 0 0 184TRV/CCJ 0010

SYZ

320 - - 0 2 0 0 142DAM 0020

MSR

320 - - 0 3 0 0 128LXR 0030

LZB

320 - - 0 4 0 0 123BOJ 0040

IAC

320 - - 0 5 0 0 129BOM/MAA 0050

DLH

330 - - 0 21 0 0 241FRA 0055

AFG

310 - - 0 22 0 0 202KBL 0100

KAC

320 BEY 0005 11024 0 0 0 - 0105

RJA

319 AMM 0045 13125 8 21107AMM 0130

... ... ... ... ... ... ... ......... ... RJA

310 AMM 2310 2531 4 3 253AMM 2405

AXB

737 CCJ/IXE 2305 11924 8 37185IXE/CCJ 2410

KLM

330 AMS/BAH 2315 305Apron2 42244AMS 2435

JZR

320 DXB 2350 1674 0 0 0 - 2450

Table 5.18 presents the estimated walking distance cost with different values of . With a buffer time0 the walking distance costs was

1,418,381. This means that the walking distance saving percentage is

6.05%. However, the saving percentage is negative when we let

20 and

30 minutes.

Table 5.18 Estimated walking distance cost and actual data comparison by using Method 3 㩷 0 10 20 30 walking distance cost 141838114496981541133 1579837

Saving percentage 6.05% 3.98% -2.08% -4.64%

In table 5.19, we will give a summary for the comparison between the four scheduling methods by showing the positive and negative results for the different values of regarding the saving percentage for the walking 51
distance cost. The (O) mark shows a positive result. However, (-) mark shows a negative result. Table 5.19 positive and negative results for the walking distance cost using different values of Algorithm 0㩷 10㩷 20㩷30㩷 㩷40㩷

Greedy O O O O -

Method 1 O O O - -

Method 2 O O O - -

Method 3 O O - - -

For the second objective function which is minimizing the passengers walking distance cost. From table 5.19, we also conclude that greedy algorithm gives the best result among all the other scheduling methods regarding the saving per centage for the walking distance cost. By using greedy algorithm, the saving percentage for the walking distance cost gives positive result until

30 minutes. Method 1 and Method 2 give almost

same result. The saving percentage for the walking distance cost for both Method 1 and Method 2 gives positive result until

20 minutes.

However, Method 3 gives the worst result among the other scheduling methods. The saving percentage for the walking distance cost gives positive result until

10 minutes.

52

Chapter 6

Simulation approach

53

6.1 Objective of the simulation approach

The rapid development of airlines has made airports became busier. As a result, the problem of assigning gates to flight arrivals and departures is an important decision problem in daily operations at major airports all over the world. With the increasing of flights frequency every year, some airport officials want to estimate how many gates in the terminal will be needed in the future so that the airport could handle the increasing number of flights. The objective of this approach is to use an aircraft scheduling algorithm to estimate the optimum number of gates in the terminal needed in the future under a specific percentage of the total number of ungated flights and buffer time limit. Further more, we will analyze the walking distance estimation in this approach. In order to estimate the optimum number of gates, in this simulation approach we suppose that the total number of ungated flights should be at most 20% from the total number of flights and the latest time that the flight can be assigned to a gate is at least 30 minutes. In other word, for the flight time interval we will let

30 minutes and

be always equal to 0. So we will let the flight time interval equal to and run the simulation until we find the optimum number of gates when the total number of ungated flights should be at most 20% from the total number of flights. ]30, i d[ i a 54

6.2 Arrival rate estimation and simulation steps

Before we explain the simulation steps, we should find the arrival rate for the aircrafts. We have collected actual data for the incoming aircrafts frequency. The collected data is monthly data for 5 years period (60 observations). We will use the Stochastic Models Box & Jenkins methodology (1976) to do forecasting for the number of incoming aircrafts and then estimate the arrival rate for the aircrafts. The general Box & Jenkins model of order (p, P, q, Q) abbreviated by

ARIMA (p, d, q) x (P, D, Q) L

And the ARIMA model will be expressed as

tL

QqtdDLL

pp aBBZBBBB)()()1()1)(()( 0 Regarding to our data, after applying Box & Jenkins methodology, the best model for the incoming aircrafts frequency that has been found is as follow:

ARIMA (1, 0, 0) x (1, 1, 1)12

The Estimates of Parameters:

9305.0ˆ

1 ,,and

9844.0ˆ

12,1

7898.0ˆ

12,1

41.56ˆ

0 Therefore, the fitted ARIMA model can be expressed as follow tt aBZBBB)ˆ1(ˆ)1)(ˆ1)(ˆ1( 12

12,101212

12,11 55
tt aBZBBB)7898.01(41.56)1)(9844.01)(9305.01(

121212

Or

12252413121

7898.041.569160.09844.00145.00156.09305.0

ZZZZZZ

tttttttt aa Figure 6.1 shows aircraft arrival pattern with the forecasted data including upper and lower bound for monthly data. From the results, after 2 years ahead it has been forecasted that in most crowded case that the number of arrivals will be 401,760 flights. Then the arrival rate is one flight every 9 minutes (401760 / 31*24*60 = 9).

In addition, it has been estimated

that the departure time for each flight is between 90 and 100 minutes. Figure 6.1 shows aircraft arrival pattern with the forecasted data (AC is the incoming aircrafts frequency)

Time Series Plot for AC

(with forecasts and their 95% confidence limits)

6 121824303642485460

15002500350045005500

AC Time 56

The simulation steps are as follow:

(1) The arrival time for flight i is ia i 9 and the departure time is .

100,90

iii aad (2) Let the latest time that the flight can be assigned to a gate equal to 30 minutes (in other word we let

30 minutes).

(3) Types of aircrafts and passengers are generated randomly. (4) Apply the scheduling algorithm. (5) Apply Tabu search (TS) algorithm (6) Run time is one week period. (7) Do 30 times replicate.

6.3 Simulation results

We will apply our simulation approach for each aircraft scheduling method. For each method, we will pr esent flights scheduling output, average and the percentage of the ungated flights from the total flights with different number of gates and the walk ing distance cost change percentage. The walking distance cost change percentage will be calculated by comparing the estimated walking di stance cost by using the simulation approach and the estimated value for the walking distance cost for the actual data which is 1,509,752. 57
First, we will apply our simulation approach to greedy algorithm. Table 6.1 shows a sample of the output for one replicate with number of gates equal to ten and

30 minutes.

Table 6.1 simulation output using greedy algorithm A/L A/C

Arrival

j f ,0 Gate ji W ,ji f ,0,i f

Departure

From time To time

MSR 320 CAI 0009 1531 0 0 97 CAI 0210

UAE 330 DXB 0018 3052 5 13299DXB 0221

JZR 320 DOH 0027 1533 2 4 102AMM 0234

RJA 320 AMM 0036 1634 3 5 158AMM 0243

JZR

320 BOM 0045 84 5 8 6 117HBE 0252

IRA 727 AWZ 0054 18021 5 43102AWZ 0303

JZR

320 BEY 0103 12422 2 23177DAM 0313

JZR

320 SYZ 0112 15624 0 0 0 - 0321

MEA 330 BEY 0121 26926 10 26274BEY 0321

... ... ... ... ... ... ... ...... ... ...

ETD 320 AUH 2100 16826 5 22127AUH 2310

JAI 737 BOM 2109 17922 8 25167BOM 2314

JZR

320 BOM 2118 163Apron7 36131HBE 2319

KAC

300 CAI 2127 32421 2 39302CMB 2336

Next, we do all the 30 times replicates for the simulation. Table 6.2 presents the average and th e percentage of the ungated flights from the total flights with different number of gates. Table 6.3 presents the walking distance cost change percentage using the simulation approach. Table 6.2 percentage of ungated flights using simulation approach (greedy algorithm)

Number of gates 10 11 12

Ungated flights 367 295 225

Percentage

32.73% 26.29% 20.07%

Table 6.3 percentage of walking distance cost using simulation approach (greedy algorithm)

Number of gates 10 11 12

Walking distance cost 2208202.9 2133456.7 2080175.4

Change%

46.26% 41.31% 37.78%

58
We conclude that we will reach to out target which is the total number of ungated flights should be at most 20% of the total flights and the latest time that the flight can be assigned to a gate at least 30 minutes latest time when we let the number of gates equal to 12. Or in other word, the current number of gates in the terminal is 10 gates. After two years KIA should add two new gates in the terminal if they want to keep the percentage of the ungated flights at most 20% of the total fights with buffer time equal to 30 minutes. By letting the number of gates equal to 12, the estimated number of ungated flights is 225 and the walking distance cost will be increased

37.8%.

Next, we will apply our simulation approach to Method 1. Table 6.4 shows a sample of the output for one replicate with number of gates equal to ten and

30 minutes.

59

Table 6.4 simulation output using Method 1

A/L A/C

Arrival

j f ,0 Gate ji W ,ji f ,0,i f

Departure

From timeTo time KAC

320 BAH 00091781 0 0 0 - 0213

GFA

320 BAH 00181512 4 2 172BAH 0226

JZR

320 - 00270 3 4 1 124AMM 0235

MEA

321 BEY 003693 4 0 0 116BEY 0246

IRA

727 SYZ 00451595 9 23180SYZ 0245

JZR

320 DOH 005416621 4 27117ATZ 0302

JZR

320 - 01030 22 9 39174SSH 0306

KAC

340 FRA 011224526 0 0 0 - 0318

JZR

320 LCA 012112024 3 46152DOH 0330

... ... ... ... ... ... ... ......... ... QTR

321 DOH 23061175 5 36165DOH 2516

GFA

330 BAH 231528221 6 24304BAH 2517

KAC

310 DOH 232420522 8 8 234HYD 2534

KAC

320 - 23330 26 9 41141DOH 2533

Based on 30 times replicates, table 6.5 presents the average and the percentage of the ungated flights from the total flights with different number of gates. Table 6.6 presents the walking distance cost change percentage using the simulation approach. Table 6.5 percentage of ungated flights using simulation approach (Method 1) number of gates 10 11 12

Ungated flights 366 294 223

percentage

32.68% 26.25% 19.91%

Table 6.6 percentage of walking distance cost using simulation approach (Method 1) number of gates 10 11 12 walking distance cost 2187555.7 2134526.7 2058271.367 change%

44.90% 41.38% 36.33%

The results are almost same as greedy algorithm. Using Method 1 we conclude also that we will reach to out target when we let the number of 60
gates equal to 12. The estimated number of ungated flights is 223 and the walking distance cost will be increased 36.33%. Also we will apply our simulation approach also to Method 2. Table 6.7 shows a sample of the output for one replicate with number of gates equal to ten and

30 minutes.

Table 6.7 simulation output using Method 2

A/L A/C

Arrival

j f ,0 Gate ji W ,ji f ,0,i f

Departure

From timeTo time KAC

340 CGK/KUL 00092502 0 0 198CAI 0218

JZR

320 DXB 001895 1 3 34163HRG 0228

JZR

320 SAH/BAH 002782 3 2 4985BOM 0227

JZR

320 MHD 00361424 0 0 0 - 0236

KAC

320 CAI 00451375 2 18109BAH 0246

JZR 320 DXB 005499 21 0 0 0 - 0255

KAC

310 HYD 010327622 6 3 267IKA 0309

KAC 320 DXB 011213424 4 36152DXB 0317

KAC

777 - 01210 Apron3 31299CAI 0327

... ... ... ... ... ... ... ......... ... KAC

340 MNL/BKK 2315221Apron0 0 0 - 2521

KAC

777 LHR 23243054 0 0 0 - 2534

OMA

737 MCT 23331112 3 34135MCT 2543

KAC

777 BOM 234224822 9 9 341LHR 2544

Based on 30 replicates, Table 6.8

presents the average and the percentage of the ungated flights from the total flights with different number of gates. Table 6.9 presents the walking distance cost change percentage using the simulation approach. 61
Table 6.8 percentage of ungated flights using simulation approach (Method 2)

Number of gates 10 11 12

Ungated flights 367 295 225

Percentage

32.77% 26.34% 20.09%

Table 6.9 percentage of walking distance cost using simulation approach (Method 2)

Number of gates 10 11 12

Walking distance cost 2196257.4 2142121.5 2071356.1

Change% 45.47% 41.89% 37.20%

The results are almost same as the previous two algorithms. Using Method 2 we conclude also that we will reach to out target when we let the number of gates equal to 12. The estimated number of ungated flights is

225 and the walking distance cost will be increased 37.20%.

Finally we will apply our simulation approach also to