A greedy algorithm based on joint assignment of airport gates and taxiways in large hub airports

Nie Tongtong (聶彤彤), Wu Wenjun, He Qichang, Zhang Xuanyi, Sun Yang, Zhang Yanhua

(*Faculty of Information Technology, Beijing University of Technology, Beijing 100124, P.R.China)(**Beijing Capital International Airport Co., Ltd, Beijing 100621, P.R.China)

Abstract

Key words: greedy algorithm, airport gate, taxiway, resources assignment

0 Introduction

Today, air transport increases rapidly which makes civil aviation face a lot of challenges. Therefore, the management and assignment of airport resources have become particularly difficult. There are many kinds of resources in an actual airport, such as gates, taxiways, baggage carousels, and ground crews. Among these, airport gates and taxiways are the most important ones.

The gate is the starting point and the terminal point of each flight. It can be divided into the fixed gate, the remote gate, and the spare gate on the far away apron. Efficient assignment of airport gates can save operating costs, reduce passengers’ walking distance, and improve the quality of experience. At the same time, the gate assignment has a direct impact on the plan of the taxiways, ground crews, baggage carousels, and other resources.

The taxiway is one of the important ground components of the airport. According to the different functions of taxiways, it can be generally divided into parallel taxiways, fast exit taxiways, entry and exit taxiways, contact taxiways, spare gate taxiways and so on[1]. The function of taxiways is to provide access for arrivals or departures. The main fuel consumption of flights is generated by ground taxiing[2]. Therefore, reasonable optimization of taxiways assignment can realize the goal of saving fuel, reducing costs, and protecting the environment.

In this work, the objective is maximizing the ratio of fixed gates and minimizing the ratio of taxiway collisions. The greedy algorithm which transforms global optimization into local optimization to reduce computational complexity and improve operational efficiency, is used to solve the problem of joint assignment of airport gates and taxiways in a large hub airport in China with the data of a one-week schedule. The method allows 2 actions to be taken for each flight, which realizes the joint assignment of gates and taxiways.

The rest of this paper is organized as follows. In Section 1, the related work of airport gates and taxiways assignment problem and the basic concepts of the greedy algorithm are introduced. Then presenting the scenarios and models of the problem in the large hub airport in Section 2. In Section 3, a greedy algorithm is used to solve this problem. Then, the simulation results are discussed in Section 4. Finally, the work of this study and future work are concluded in Section 5.

1 Related work

1.1 The airport gate and taxiway assignment problem

For the assignment problem of airport gates, it is usually considered to maximize the utilization of airport gates[3]or minimize the walking distance of passengers[4,5]. Some academics expanded the single optimization objectives and built a multiple objectives model with push-out avoidance[6]. To solve these problems, the heuristic algorithm is often used, which could approximate the theoretical optimal solution by iterations. The common heuristic algorithms are the greedy algorithm, the genetic algorithm[6,7], the tabu-search algorithm[8], etc.

For the assignment problem of taxiways, the shortest taxiing path[2]or the minimum taxiing time[9]are usually considered as the optimization objective. The taxiway collision is the main cause of increasing the time of taxiing. It is mainly divided into 3 types as shown in Fig.1[2]. The head-to-head collision is 2 flights slide in the opposite direction on the same taxiway. The head-to-end collision is 2 flights slide in the same direction on the same taxiway, and the speed of the rear flight is faster than the front one. The intersection collision is 2 or more flights meet at the same taxiway intersection. The solution to this problem is similar to the assignment of gates. GUROBI, a linear programming software was used in Ref.[10]. The genetic algorithm had an outstanding performance in Ref.[11], and in the research[12], a model with considering the constraints of Baiyun Airport’s taxiing rules was solved by an improved ant colony algorithm, which achieved the optimization of reducing the take-off delay and making the taxiing time shortest.

Fig.1 Types of taxiway collision

At present, there are a lot of researches on the single resource assignment problem in airports, but the joint assignment problem of multiple resources has not been well studied. In the actual operation of an airport, operators will match the taxiway to different gates to shorten the taxiing distance of the flights. The system of runway and taxiway is shown in Fig.2. It is important to design a joint intelligent system to assign multiple resources simultaneously. An airport gate assignment model was constructed in Ref.[8]. The objective function is to minimize the total cost of taxiing distance, free time of airport gate and passengers’ walking distance. They designed a greedy algorithm to solve it and verified the effectiveness of the algorithm. But the algorithm only handled 90 flights at most. A model of multiple objectives airport gate assignment problem with the safety constraints of the taxi-in and push-out conflict avoidance was proposed, and an optimizing solution was given by the ant colony algorithm in Ref.[13]. However, it only handled 48 flights within 7.5 h, which dissatisfy to the large data in hub airport.

Fig.2 Runway and taxiway system

1.2 Greedy algorithm

The greedy algorithm is a typical heuristic algorithm, which is a mental activity of humans. It is a simpler and quicker technique for some optimal solution problems. The key to it is selecting a measuring standard according to the question to determine the decision-making and order step by step. It is not optimal while the whole is taken into account, and what it has got is the best in only the local optimal solution[14].

It is widely used in vehicle resource assignment[15,16]and various optimal assignment problems[17-19]. The airport resource assignment problem is a typical NP-hard problem, which is difficult to solve with traditional mathematical programming algorithms. So, the greedy algorithm is a better choice. It was used to solve the aircraft landing optimal assignment problem in Ref.[20]. The results show that the algorithm has a preferable scheduling performance. A model is considered with the objective function of minimizing the ratio of unassigned flights and walking distance, the greedy algorithm still had a good performance in solving it[21].

In this work, a greedy algorithm is used to transform the global optimization problem into local optimization problems step by step. It realizes an efficient joint assignment of airport gates and taxiways.

2 Scenarios and models

A large hub airport withMgates andZtaxiways is considered. The sets of all the gates and taxiways are defined byGandW, respectively. Three types of gates are considered, the fixed gate, the remote gate, and the spare gate on the far away apron. If the flight is assigned to the remote gate, the passenger should take the shuttle bus to aboard, this situation will cost more time. If the flight is assigned to the spare gate which means the assignment failure. At the same time, the collision of 2 flights taxi in the opposite direction or the same direction on the same taxiway is mainly considered. When a flight arrives, it passes through the taxiway before arriving at the gate. Similarly, it also passes through the same taxiway when the flight leaves the gate. There is a specific correspondence between taxiways and gates. Using a matrixCto express the relevance of gates and taxiways.

(1)

wherecij=1 means the taxiwayiis connected to the gatej, otherwise,cij=0.

The number of flights isN. The flights arrive in sequence according to the arrival time. Considering the rules of airlines, tasks and aircraft types, the flights and gates are matched as a matrixB.

(2)

wherebij=1 means the flighticould be assigned to the gatejaccording to the rules, otherwise,bij=0.

2.1 Objectives

It is well known that the passenger’s QoE (quality of experience) is extremely important in the evaluation of the airport. If the flight is assigned to the fixed gate, the passenger can directly enter the airport through the bridge, so that the passengers have the shortest waiting time and the QoE is the best.

At the same time, the main cause of fuel cost is the taxiway collision in the process of taxiing. Therefore, taxiway collision should be avoided while assigning flights to the fixed gate as far as possible. In summary, the optimization objective considers 3 aspects, which are the ratio of fixed gates, spare gates, and taxiway collision. Eq.(3) denotes the optimization objective of the proposed problem.

(3)

whereY=(yijyiz)N×(M+Z)donates the optimal variable of assignment decision. The first part of the right side of Eq.(3) refers to the weighted cost of flight assign to the fixed gate, the second part refers to the weighted cost of flight assign to the spare gate and the third part refers to the weighted cost of taxiway collision. Whenyij=1, the flightiis assigned to a gatej, otherwise,yij=0.gjandpjdenotes the type of gates. Whengj=1, the gatejis the fixed gate, otherwise,gj=0. Whenpj=1, the gatejis the spare gate, otherwise,pj=0.yizdenotes taxiways assignment of flights. Whenyiz=1, the flightiis assigned to a taxiwayz, otherwise,yiz=0.qzdenotes the penal of the taxiway collision. Whenqz=1, there is a collision on the taxiwayz, otherwise,qz=0.w1,w2,w3are used to adjust the weight of the 3 optimization objectives, wherew1is positive andw2,w3are negative.

2.2 Constraints

According to the objective, all decision variables should be 0 or 1, which can be expressed as

yij,yiz,gj,pj,qz∈{0,1}

(4)

Therefore, the joint assignment of airport resources belongs to the 0/1 programming problem.

A basic mathematical constraint is a flight should be assigned to only one gate and one taxiway. It is expressed as

(5)

Eq.(6) describes the logical constraints which are generated by the airport operational policies. For example, large planes must be assigned to large gates, small planes can be assigned to both large and small gates, while some flights are international flights, so they must be assigned to some specific gates. These constraints are expressed as

yij=rij·yij

(6)

whererijcan be defined as the flight type constraint, the flight attribute constraint, etc. If the gatejsatisfies the operational constraints of flighti,rij=1 and the value ofyijcan be 0 or 1, otherwise,rij=0, the value ofyijis restricted to 0.

There should be at least 5 min apart when the 2 flights taxi on the same taxiway in the same direction to avoid the head-to-end collision. Referring to the model in Ref.[22], it can be expressed as Eq.(7) and (8)

yizyjz(ti1-tj1-5)>0

(7)

yizyjz(ti2-tj2-5)>0

(8)

whereti1denotes the arriving time of flighti,tj1denotes the arriving time of flightj,ti2denotes the departure time of flighti,tj2denotes the departure time of flightj.

Similarly, to avoid the head-to-head collision on the same taxiway, it should be at least 10 min apart when they slide in the opposite direction as Eq.(9).

yizyjz(ti1-tj2-10)>0

(9)

2.3 Optimization problem

Based on the above analysis of optimization objectives and constraints, the model of this problem is as follows:

(10)

The size of the optimal variable isN×(M+Z), and the state of every variable is 0 or 1. So the size of the solution space is 2N×(M+Z), which is extremely large to calculate in a hub airport.

3 Greedy algorithm based solutions

Using the greedy algorithm to solve the joint assignment problem of the airport gates and taxiways in large hub airport needs to make the best choice according to the current state of the airport. When the flight arrives, assign the gate first, and then the taxiway. Two processes for the problem are designed. The first process is to observe the current airport gate states and the available gates for arriving flights. The second process is to select the best gate and taxiway, which is named the decision process.

3.1 Observe state to obtain the available resources

(1) Airport gate state

The airport gate state is used to represent the occupancy of the airport gate from the current momenttto the time stept+T+1. If the number of airport gates isM, the state of airport gates’ information at the current timetis a 0/1 matrix given byAt:

(11)

whereaij,t=1 means the gatejis occupied by flightiat the momentt, otherwise,aij,t=0.

(2) Logical available gates

The logical available gates are used to represent the available gates for the flights under constraintsr. The occupancy time of gates from the current momenttto time stept+T+1. So the logical available gates for the flightvat the current timetis a 0/1 matrix given byBvt.

(12)

When the flightvis allowed to arrive atτ1, leave atτ2, and ifrij=1 for the flightv, thenbτ1～τ2j,t=1, otherwise,bkj,t=0,k?[τ1,τ2].

According to the constraints of the 2 matrices, the available gatesDvtfor flightvat the timetis calculated as

Dvt=(dτ, j,t)(T+1)×M=At·Bvt

(13)

This process can quickly obtain the available gates and occupancy time of gates.

3.2 Decision process

When a flightvarrives, it should be assigned to a gate firstly and then a corresponding taxiway according to the matrixC. A priority indicator for each gatepv={p1,p2,…,pM} is defined.Evis denoted as the set of available gates withdτ, j,t=1.

Step 1 is choosing the best gate. This work selects all the fixed gatesfwithdτ, f,t=1 and denotesFv?Evas the set of these gates. Iff∈Fv, increase the probability ofpfby

pf=apf,f∈Fv,a>1

(14)

wherepfis the probability of the gatef.

Then, find out all the gatesjwithout the taxiway collision and denotesHv?Fvas the set of these gates. Increase the probability of these fixed gatespjby

pj=bpj,j∈Hv,b>1

(15)

IfFv=?, increase the probability of those remote gatesrwithout taxiway collision by

pr=cpr,c>1

(16)

Then selecting the gatej* according to the updated probabilitypv. Otherwise,Ev=?, it means that there is not the available gate for flightvand it will be assigned to the spare gate, thenpM+1=1.

Step 2 is selecting a taxiway. Find out the available taxiway for the gatej* according to the matrixC. There are 2 kinds of situations. When there are lots of available taxiways, choose the taxiwayz* without collision firstly, thenyiz*=0. And if there is a taxiway collision,yiz*=1.

3.3 Algorithm procedure

Based on the above analysis, the specific algorithm procedure is as follows:

Step1A queue of flights is generated according to their arriving time. Start from the first flight in the queue.

Step2CalculateDvtaccording to Eq.(13) and the occupancy time of the arrived flight.

Step3Search for the setsEvandFvaccording toDvt, and increase probabilitypf(f∈Fv) according to Eq.(14). IfFv=?, go to Step 5.

Step4Increase the probabilitypj(j∈Hv) according to Eq.(15), then go to Step 6.

Step5IfFv=?, increase the probabilityprof those remote gates without the taxiway collision according to Eq.(16). IfEv=?, go to Step 7.

Step6Choose the airport gate according to the updated probability ofpv, then go to Step 8.

Step7Choose the spare gate.

Step8Find the taxiways associated with the gate in matrixC. If there are multiple available taxiways, choose the taxiway without collision.

Step9Record the selected gate and taxiway.

Step10If all flights have been assigned, then end. Otherwise, remove the finished flight and update the queue, then go to Step 2.

The flow chart of a greedy algorithm for gates and taxiways joint assignment problem of one flight is shown in Fig.3.

Fig.3 The flow chart of a greedy algorithm for gates and taxiways joint assignment problem of one flight

4 Results and analysis

The simulation environment is Python 2.7. The configuration parameter of the PC is as follows: Processor: Intel (R) Core (TM) i7-7700HQ CPU @ 2.80 GHz 2.81 GHz. Memory: RAM 8.00 G. System type: 64-bit operating system, based on the X86 processor. Operating system version: Windows 10.

The realistic data of an airport in China is used in the simulation which contains information of 698 flights, including airlines, flight numbers, arriving time, departing time, task attributes, aircraft types, and passenger numbers. The daily schedule is slightly changed in practice because of the delays and cancellations, 600 flights are randomly selected from the original data and 5 samples of flight schedules are produced to express these differences. Each schedule record 1 day’s missions of the airport. There is the flight information in 1 h as Fig.4. At the same time, there are 1 414 data for 202 airport gates, including gate numbers, gate attributes, gate types, taxiways, airlines, aircraft types. The fixed gates account for 35% of all gates and the number of the taxiway is 25. All the constraints considered have been introduced in Section 2.2.

Fig.4 The flight information in 1 h

Running 20 times of these 5 samples and the result is shown in Fig.5. The ratio of fixed gates, remote gates, and spare gates is 0.6, 0.38 and 0.02 respectively. The ratio of fixed gates is higher than the ratio of remote gates and the ratio of spare gates is extremely low. It allows more flights are assigned to the fixed gate and avoids assigning to the spare gate, which is the same as the expectation of the assignment of airport gates. Meanwhile, the ratio of taxiway collisions is about 0.25. It is obvious that the change in results for different samples is small. Therefore, the proposed algorithm has good stability.

Fig.5 The experiment results

In order to reveal that the advantages of the joint resource assignment are better than other schemes, it is compared with the random algorithm and a single resource assignment scheme. The random algorithm is choosing an available gate for the arriving flight randomly and then calculate the taxiway collision. The single resource assignment with greedy haven’t considered the factor of taxiway collisions, it prefers to choose the fixed gates in all available gates for arrivals. The results are shown in Fig.6, it can be seen that the greedy algorithm has an outstanding performance. The ratio of fixed gates improved by 20%, the ratio of remote gates and spare gates is less than random. This proves the effectiveness of this algorithm. And the joint assignment with the greedy algorithm has a good balance in optimizing airport gates and taxiways. It decreases the ratio of taxiway collisions from 0.45 to 0.25 on the premise of the same result of gates assignment when comparing with the single assignment based on the greedy algorithm. The proposed method could take 2 actions for arrivals simultaneously. It realizes a joint assignment for airport gates and taxiways.

Fig.6 The results of comparison algorithms

5 Conclusion

This work proposes a joint assignment scheme for airport gates and taxiways based on the greedy algorithm. The goal of this scheme is to maximize the ratio of fixed gates, minimize the ratio of spare gates and taxiway collisions. Simulation results show that compared with the other resource assignment methods, this scheme can increase the ratio of fixed gates to 0.6 and reduce the ratio of taxiway collisions to about 0.25 at the same time. Although, the greedy algorithm can be implemented with relatively low complexity, it is not a global optimal solution. In the future, dynamic joint resource assignment methods using artificial intelligence technologies should be explored to further improve the performance.