Research on Flight First Service Model and Algorithms for the Gate Assignment Problem

Jiarui Zhang,Gang Wang and Siyuan Tong

Abstract: Aiming at the problem of gate allocation of transit flights,a flight first service model is established.Under the constraints of maximizing the utilization rate of gates and minimizing the transit time,the idea of “first flight serving first” is used to allocate the first time,and then the hybrid algorithm of artificial fish swarm and simulated annealing is used to find the optimal solution.That means the fish swarm algorithm with the swallowing behavior is employed to find the optimal solution quickly,and the simulated annealing algorithm is used to obtain a global optimal allocation scheme for the optimal local region.The experimental data show that the maximum utilization of the gate is 27.81% higher than that of the “first come first serve” method when the apron is not limited,and the hybrid algorithm has fewer iterations than the simulated annealing algorithm alone,with the overall passenger transfer tension reducing by 1.615;the hybrid algorithm has faster convergence and better performance than the artificial fish swarm algorithm alone.The experimental results indicate that the hybrid algorithm of fish swarm and simulated annealing can achieve higher utilization rate of gates and lower passenger transfer tension under the idea of “first flight serving first”.

Keywords: Gate assignment,flight first service model,fish swarm algorithm,passenger transfer tension.

1 Introduction

The reasonable allocation of airport gates is an extremely important task of the airport tower.A reasonable and efficient assignment support not only to reduce the number of gates,but also make the entire airport busy and undisturbed,achieving maximum economic benefits by rationally allocating terminals and satellite hall [Zhang (2007)].

For the problem of the allocation of the airport gate,the research of domestic and foreign scholars has been studied from different angles after a long period of theoretical development and practice verification.Xu et al.[Xu and Bailey (2001)] established a mathematical model to solve the problem of putting passenger's shortest walking distance as the optimization target by using the Tabu search algorithm;Ding et al.[Ding,Lim,Rodrigues et al.(2004)] proposed the method of the synergistic use of near and far gate positions on the basis of the shortest walking distance,and used greedy algorithm for optimization;Narciso et al.[Narciso and Piera (2015)] introduced an improved Tabu search algorithm to establish the airport gate allocation model with the minimum collision frequency as the target;Wen et al.[Wen,Sun and Xu (2004);Wen,Li and Wang (2005);Wen (2010)] proposed the idea of “first come serving first”,and combined fixed-point sequence coloring and genetic algorithm to allocate the gate;Xu et al.[Xu,Zhang and Huang (2007)] proposed Memetic algorithm,and integrated greedy algorithm to make the delay time the shortest;Yang et al.[Yang,Tian and Wan (2013)] adopted a new method of using the customer evaluation to build the model;Drexl et al.[Drex and Nikulin (2008)] planed the 2 indicators that passenger' s minimum walking distance and flight evaluation indicators,when used simulated annealing algorithm to find the optimal solution;Li et al.[Li and Li (2016)] proposed a variable Taboo length method and optimized the gate under multiple constraints;Abdullah et al.[Abdullah,Betul,Tuncay et al.(2017)] compared the application of several meta-heuristic algorithms on gate assignment problem.To solve the reassignment of the gate,Yu et al.[Yu,Zhang and Henry (2017)] proposed a heuristic approach.Klabjan et al.[Klabjan and Zhang (2017)] built two multi-commodity network flow models and proposed two heuristic algorithms to solve the models efficiently.Generally speaking,these allocation methods are mainly divided into three aspects:1) expert system,which is to establish a knowledge base based on the distribution principle;2) artificial intelligence algorithm,that is adopted for a single target to perform gate allocation by using heuristic algorithm;3) multi-objective planning,that is,the results of a single goal plan are obtained by weighting.Although some progress has been made in these studies,the allocation of the gate is a NP-hard problem because there are many constraints to be considered,including the flight time of the flight itself,the size of the aircraft,and the time spent in the passenger transit.Thus,related complex models and algorithms have always been a difficult point in the industry.Based on the above reasons,this study integrates 3 factors of the shortest passenger transfer time,the highest efficiency of the terminal building and the minimum flight delay,and establishes airport gate assignment model for the existing gate resources.It builds a flight first service model and the idea of “first flight serving first” is used for the initial static flight allocation.The fish population and simulated annealing hybrid algorithm are applied to seek the rational allocation of the gate allocation again.

2 Flight first service model

2.1 Model symbol

Fstands for the flight collection;{W,N}∈F,Wis expressed as a wide body airport gate;Nis the narrow;Mstands for a gate set,{D,I,G,W,N}∈M,Dbeing indicated as the domestic arrival/departure gate;Idenotes the international arrival/departure gate;Gdenotes the domestic/international arrival/departure gate,andWdenotes the wide body gate for wide-body aircraft to dock;Nis the narrow body airport gate;Yis the delayed flight set,Tis the time set,{TD,△T}∈T;TDis the passenger's transfer time;△Tis the safety time interval expressing between the two flights.

2.2 Constraints

The allocation of the gate is to allocate all the flights in the flight collectionFthat select the appropriate gate from the existing gate setM.

Because the passenger destination is different,and the calculation of transit passengers is more complicated,the study only considers the allocation of gates for transit passengers,which needs to consider multiple constraints [Wei and Liu (2009)] including:

1) Appropriateness:The functional attributes of the domestic/international,arrival/ departure,wide-body/narrow-body machines of each airport gate cannot be changed,but can only be assigned to the gate that matches with flight attributes and aircraft models;

2) Identity:The arrival and departure of each flight must be assigned to the same gate,while cannot be moved elsewhere;

3) Interval:There must be a safe neutral interval between the two aircraft assigned to the same parking space;

4) Uniqueness:Only one aircraft can be parked at the same time.

2.3 Problem assumptions and objective functions

2.3.1 Constraints

where,Eq.(1) represents the matching of the attributes of flightiand gatek,withDIiindicating the domestic/international type of arrival/departure flighti,andDIkindicating the domestic/international type of k in gate set;WIirefers to the width of the flighti,withWIkindicating the gate width of k.The value is 1 only if both are satisfied.Eq.(2) represents the safety interval,αindicating that there must be sufficient safety interval between flightiin flightkand subsequent flightj.Eq.(3) indicates that one gate can only park one aircraft at the same time,and the value is 1 when flightiis assigned to the gatek.Eq.(4) is the range of values of the relevant variables.

2.3.2 Maximum gate utilization

Maximizing the utilization of the airport gate is the time between the next departure flight and the previous arrival flight in the same gate.Two flights meet the safety time and the domestic/international type are matched.The number of internal take-off and landing flights is the highest,that is,the number of flights is arranged as many as possible with the minimum number of gates.

where,idenotes the gate number;jdenotes the flight number arriving at the moment;m refers to the previous arrival flight number;krepresents the next arrival flight number,and both flightsmandnare assigned to the same gatei;trepresents the interval between two flights.

When the utilization rate of the gate is the largest,its objective functionZcan also be expressed as:

2.3.3 Minimum passenger transfer tension

For transit passengers,the arrival and departure flights are not in the same area,which may cause long transit time tightening the trip.The minimum passenger transfer time TD optimization goal is to make the passengers in the transit flight from the arrival flight to the next departure.The time spent between flights is the smallest [Babic,Teodorovic and Toslc (1984)],which mainly includes 3 periods including the shortest process time 1T,the MRT time 2Tbetween different terminals and the passenger travel time 3T,namely:

The location of different airport gates determines the travel time of passengers.Therefore,flights with more passengers should be arranged in the same area of the same terminal.The introduction of passenger transfer tension is indicated byJand the interval between the arrival of the flight and the departure flight is represented by 4T.So,the objective function is as follows:

3 Fish swarm and simulated annealing hybrid algorithm

For the allocation of the airport gate,the research using simulated annealing algorithm has achieved more results,but the convergence time of the algorithm is too long,and needs several numbers of iterations.Furthermore,it depends on the initial value,which may fall into local optimum [Spall (2003)],so this study combines the artificial fish swarm algorithm to solve the gate allocation on the basis of simulated annealing.

3.1 Fish swarm algorithm

In 2002,Li et al.[Li and Qian (2002)] proposed an artificial fish breeding optimization algorithm.By using a new bottom-up optimization model,an artificial fish entity was constructed through the study of foraging behavior of fish,through 4 kinds of behaviors to find the optimal solution,foraging,gathering,rear-end and random [Partridge (1982)].These behaviors can be converted to each other under different conditions,with the characteristics of simpler,parallel,fast jump out of the local extremum,and the fast convergence rate [Ban,Peng and Wang (2007)].

3.2 Hybrid algorithm

3.2.1 Basic ideas

The artificial fish swarm with swallowing behavior is combined with the simulated annealing algorithm.The artificial fish swarm algorithm is used to quickly find the global optimal solution of the artificial fish region,and to search the optimal solution for local individuals through the simulated annealing algorithm.This algorithm can reasonably utilize the ability of simulated annealing algorithm to jump out of the local optimum and solve the random flight of artificial fish [Zhang,Shao and Gan (2006)].Introducing the swallowing behavior based on the artificial fish swarm algorithm can also reduce the complexity of the algorithm to some extent.

3.2.2 Algorithm flow

1) Maximum gate utilization rate

Step 1:Sort all the flights in ascending order from the morning to night according to the departure time,and get a sequenceW;

Step 2:Adopt the “first flight severing first” idea to assign flights to domestic/domestic and international/international under the constraints;

Step 3:Each flight has multiple types of gates that match its attributes,and loop through multiple types of gates for a flight.There are 16 types of combinations,when the allocation type with the highest utilization of the gate is obtained.

2) Minimum passenger transfer tension

On the basis of the minimum passenger transfer tension,the maximum gate utilization rate must also be satisfied.That is,in the case of the distribution result obtained in section (1),the hybrid algorithm is used to adjust the distribution result to obtain a new one.The complete scheme of the allocation scheme and its hybrid algorithm are shown in Fig.1.

Figure 1:Flow chat of the hybrid algorithm

Step 1:Initialize the fish swarm algorithm and simulated annealing algorithm parameters.Set the artificial fish population as Total,the number of iterations as MaxT,the artificial fish dimension as D,the step size as Step,the visual field as V,the crowding factor asδ,the number of moving attempts as TryNum,the initial temperature as T0,cooling coefficient as C,and temperature threshold as T1;

Step 2:Randomly generate Total artificial fish;

Step 3:Each fish chooses the behavior to be performed,updates the position status,and the artificial fish that meets the condition is swallowed;

Step 4:Perform multiple iterations of the global searches to obtain an optimal solution region;

Step 5:Perform a simulated annealing algorithm on the optimal region to obtain an accurate optimal solution.

4 Experimental analysis

4.1 Description of the problem

4.1.1 Airport layout

A terminalTand a satellite hallS,their layout is shown in Fig.2.The terminalTis divided into three areas:N(North),C(Center) andS(South).The satellite HallSis divided into four areas:N,C,SandE(East).There areT1 -T28 andS1-S41 gates in the terminal building and satellite hall respectively.The terminal is connected by the MRT line between the terminal building and the satellite hall.The transfer passenger can take the MRT to travel between the terminal building and the satellite hall,spending 8 minutes in one way.The entry and exit function can only be handled at the terminal building,while the satellite hall possesses no entry and exit function.

Figure 2:Terminal and satellite hall distribution

4.1.2 Dispatch allocation

The total number of airport gates is 69.The plane model assigned to the gate must be the same as the gate.The wide-body models of the airplane are 332,333,33E,33H,33L,773,while the narrow-body models of the airplane are 319,320,321,323,325,738,73A,73E,73H,73L.

The process of transit passengers from the arrival of the previous flight to the departure of the latter flight is combined into 16 different scenarios according to the domestic (D) and international (I),terminal (T) and satellite (S).The minimum process time and MRT ride times for these scenarios are given in Tab.1,where the first number of each cell is the shortest process time.The second is the MRT ride number,and cost 8 minutes once.

Table 1:Process time and MRT times

The travel time of transit passengers from different areas of different terminals is shown in Tab.2 below,including three areas of N,C,and S of the terminal T,and four areas of N,C,S,and E of the satellite hall S.

Table 2:Walking time in different areas

4.1.3 Flight information

This study records flight and passenger information of arriving or departing at an airport on January 20th,2018,including all flights and passengers departing on the 20th or start off on 20th,for a total of 303 flights and 2879 passengers.All data comes from China Eastern Airlines and Shanghai Pudong International Airport.For the sake of calculation,the arrival and departure time of the flight were adjusted appropriately,and the time was changed to 5 minutes as a basic unit.Because the number of flights and the number of passengers is large,for explanation,only the flight information and the results of first ten flights allocation are displayed.The flight information is shown in Tab.3.

Table 3:Ten flights information

4.2 Analysis of results

Under the traditional idea of “first come,first serve”,283 flights were successfully allocated with 61 parking spaces,and between the two flights before and after had a larger idle time,Z=0.6155.Compared with the condition that the utilization rate of the gate was the largest,the idea of “first flight serving first” increased the use frequency of the apron,and the occupancy of the gate in one day is shown in Gantt Chart 3.Fig.3 displays that the largest number of successful flights is 235,with 21 parking spaces.

Figure 3:Airport gates take up time

As can be seen from Fig.3,the 21 gates,excluding the safe time interval between two adjacent flights,have basically reached the maximum utilization rate,and no more flights can be scheduled in unoccupied time between two flights.The assignment results of the first ten flights are shown in Tab.4,and the utilization rate Z of the gate is 0.8936.

Table 4:The assignment results of the maximum utilization

Under the constraint of the minimum passenger transfer time,the simulated annealing algorithm is used to solve the problem under the idea of “first come first serve”.When the passenger's transfer tension J is no longer changed,the maximum number of iterations is 400 times,J=5.198.Through the idea of “first flight serving first”,the fish population and simulated annealing hybrid algorithm are used on the basis of the initial allocation,MaxT=100,Step=0.7,V=2.5,δ=8,TryNum=50,T0=50,C=0.9,T1=0.1.The optimal solution is obtained after less than 200 iterations of the simulated annealing algorithm,where J=3.583,with the final distribution result shown in Tab.5.

Table 5:The assignment results of minimum transfer time

On the other hand,in the case of transit passengers,the shortest process time TD of 2879 passengers is 50524 minutes,and the passenger ratio of transfer results in each time period is shown in Fig.4.The minimum occupation time is more than 15 minutes,and the number of passengers occupying 15-30 minutes accounts only 44%.If the unused gate attributes are changed,and add 10 domestic/domestic wide-body and 2 domestic/domestic narrow-body gates are added,the data validation shows that the ratio of successful passenger transfers within 15-30 minutes will increase to 71%.

Figure 4:Rate of successful transfer passengers

Compared with 400 iterations being used by the simulated annealing algorithm,and being run for 42.529 s,the hybrid algorithm was iterated for less than 300 times,and the running time was 33.58 s.After that,better allocation result was obtained.The convergence curve of the algorithm is shown in Fig.5 whose results were obtained by averaging after 10 runs.

Figure 5:Algorithm convergence curve

In order to verify the performance difference between the pure artificial fish swarm algorithm and the hybrid algorithm,this study uses the test function:

Figure 6:Three-dimensional image of),( yxf function

The graph of the test function is shown in Fig.6,in which there are several minimum values,where the global optimal value of 0 can be obtained at (0,0).The test function is easy to be trapped in the local optimal,so fish swarm algorithm and hybrid algorithm are used to optimize the function respectively.The above parameters were used for both algorithms.Each algorithm was performed 10 times independently to reduce the influence of uncertain factors on experimental results.The average optimization result of the test function is displayed in Tab.6.

Table 6:The performance comparison between fish swarm algorithm and hybrid algorithm

From Tab.6,it can be seen that the hybrid algorithm with swallowing behavior converges faster and performs better than the pure artificial fish swarm algorithm.Because of the reducing complexity of the algorithm,the running time of the hybrid algorithm is shorter,and its overall performance is better.

5 Conclusions

1) Through the idea of “first flight serving first”,the gate is allocated.On the basis of meeting the safety interval,the two flights enable the gate to have the least idle time and the highest utilization efficiency of 89.36%,27.81% higher than “first come first service”.

2) Based on the initial allocation,a hybrid algorithm of fish swarm and simulated annealing is used to obtain the global optimal solution,which makes the allocation of gates satisfy the maximum utilization and the minimum passenger transfer tension,reaching 3.583,which is 1.615 lower than simulated annealing algorithm.

3) Changing the attributes of gates and adding 10 domestic/domestic wide-body gates and 2 domestic/domestic narrow-body gates can greatly reduce the transfer time of passengers,when ratio of successful passengers within 15-30 minutes will increase to 71%.

4) The experimental results show that the hybrid algorithm not only has the characteristics of global and easy realization of artificial fish population,but also contains the strong local search ability of simulated annealing algorithm.In summary,the hybrid algorithm of artificial fish swarm and simulated annealing has better performance than the simple simulated annealing algorithm.

Acknowledgements:This paper is supported by The National Nature Science Foundation of China (No.61703426).

References

Abdullah,A.;Betul,Y.;Tuncay,Ö.;Mutlu Yenisey,M.;Engin,S.(2017):The comparison of the metaheuristic algorithms performances on airport gate assignment problem.Transportation Research Procedia,vol.22,no.12,pp.469-478.

Babic,O.;Teodorovic,D.;Toslc,V.(1984):Aircraft stand assignment to minimize.Journal of Transportation Engineering,vol.110,no.1,pp.55-66.

Ban,X.J.;Peng,L.;Wang,X.H.(2007):Multi-Agent-Based algorithm research on a self-Organization behavior of artificial fish colony.Computer Science,vol.34,no.7,pp.193-196.

Bouras,A.;Ghaleb,M.A.;Suryahatmaja,U.S.;Salem,A.M.(2014):The airport gate assignment problem:a survey.Scientific World Journal,no.2014,pp.1-27.

Ding,H.;Lim,A.;Rodrigues,B.;Zhu,Y.(2004):New heuristics for the overconstrained flight to gate assignments.Journal of the Operational Research Society,vol.55,no.7,pp.760-768.

Drexl,A.;Nikulin,Y.(2008):Multicriteria airport gate assignment and pareto simulated annealing.IIE Transactions,vol.40,no.4,pp.385-397.

Durand,N.;Gianazza,D.;Gotteland,J.B.;Alliot,J.M.(2015):Metaheuristics for air traffic management.Bibliography.

Klabjan,D.;Zhang,D.(2017):Optimization for gate re-Assignment.Transportation Research Part B:Methodological,vol.95,pp.260-284.

Li,Y.L.;Li,Y.(2016):Aircraft stands assignment optimization based on variable tabu length.Journal of Computer Applications,vol.36,no.10,pp.2940-2944.

Li,X.L.;Qian,J.X.(2002):Artificial fish swarm algorithm:bottom-up optimization model.Systems Engineering-Theory ＆ Practice,vol.22,no.3,pp.76-82.

Narciso M.E.;Piera,M.A.(2015):Robust gate assignment procedures from an airport management perspective.Omega,vol.50,no.1,pp.82-95.

Partridge,B.L.(1982):The structure and function of fish schools.Scientific American,vol.246,no.6,pp.114-123.

Spall,J.C.(2003):Introduction to Stochastic Search and Optimization.Wiley Publishing,New York.

Wei,D.X.;Liu,C.Y.(2009):Airport gate reassignment problem.Journal of Nanjing University of Aeronautics ＆ Astronautics,vol.41,no.2,pp.257-261.

Wen,J.(2010):Research on the gate assignment in airport based on genetic algorithm.Science Technology and Engineering,vol.10,no.1,pp.135-139.

Wen,J.;Li,B.;Wang,Q.R.(2005):Graph coloring model and algorithm of gate assignment in airport.Systems Engineering Theory Methodology Applications,vol.14,no.2,pp.136-140.

Wen,J.;Sun,H.;Xu,J.(2004):Study of the gate assignment in airport based on fixed job scheduling algorithm.Systems Engineering,vol.22,no.7,pp.102-106.

Xu,J.;Bailey,G.(2001):The airport gate assignment problem:mathematical model and a tabu search algorithm.Proceeding of the 34th Hawaii International Conference on System Sciences,pp.102-111.

Xu,X.H.;Zhang,P.;Huang,J.X.(2007):Research of airport gate assignment problem based on MA.Journal of Transportation Engineering and Information,vol.5,no.4,pp.10-17.

Yang,C.H.;Zhang,D.;Henry,L.(2017):A heuristic approach for solving an integrated gate reassignment and taxi scheduling problem.Journal of Air Transport Management,vol.62,no.2017,pp.189-196.

Yang,S.S.;Tian,Y.;Wan,L.L.(2013):Research on airport aircraft stands assignment optimization strategy based on client assessing system.Journal of Wuhan University of Technology (Transportation Science ＆ Engineering),vol.37,no.1,pp.167-174.

Zhang,M.F.;Shao,C.;Gan,Y.(2006):Hybrid artificial fish swarm optimization algorithm based on mutation operator and simulated annealing.ACTA Electronica Sinica,vol.34,no.8,pp.1381-1385.

Zhang,Y.F.(2007):The Optimized Research of Aircraft Stands Assignment (Ph.D.Thesis).Civil Aviation University of China,Tianjin.