A new dynamic pushback control method for reducing fuel-burn costs:Using predicted taxi-out time

Gun LIAN,Yping ZHANG,*,Zhiwei XING,Qin LUO,Showu CHENG

aSchool of Transportation Science and Engineering,Harbin Institute of Technology,Harbin 150090,China

bGround Support Equipment Research Base,Civil Aviation University of China,Tianjin 300300,China

cThe Second Research Institute of Civil Aviation Administration of China,Chengdu 610041,China

KEYWORDS Airport surface operation;Fuel-burn cost;Gate-hold time;Pushback control;Taxi-out time prediction;Taxiway queue threshold

Abstract Long departure-taxi-out time leads to significant airport surface congestion,fuel-burn costs,and excessive emissions of greenhouse gases.To reduce these undesirable effects,a Predicted taxi-out time-based Dynamic Pushback Control(PDPC)method is proposed.The implementation of this method requires two steps: first,the taxi-out times for aircraft are predicted by the leastsquares support-vector regression approach of which the parameters are optimized by an introduced improved Fire fl y algorithm.Then,a dynamic pushback control model equipped with a linear gate-hold penalty function is built,along with a proposed iterative taxiway queue-threshold optimization algorithm for solving the model.A case study with data obtained from Beijing International airport(PEK)is presented.The taxi-out time prediction model achieves predictive accuracy within 3 min and 5 min by 84.71%and 95.66%,respectively.The results of the proposed pushback method show that total operation cost and fuel-burn cost achieve a 14.0%and 21.1%reduction,respectively,as compared to the traditional K-control policy.(3)From the perspective of implementation,using PDPC policy can significantly reduce the queue length in taxiway and taxi-out time.The total operation cost and fuel-burn cost can be curtailed by 37.2%and 52.1%,respectively,as compared to the non-enforcement of any pushback control mechanism.These results show that the proposed pushback control model can reduce fuel-burn costs and airport surface congestion effectively.

1.Introduction

Airport surface-operations play an important role in an airtransportation system.Nearly 33% of operation cost is incurred by the surface-transportation sector.It is well documented that excessive fuel-burn and emissions at airports are due mainly to surface congestion,which can lead to long taxiing and queuing times for aircrafts.1According to Federal Aviation Administration(FAA)statistics,7.7 million aircrafts taxied in and out of major United States airports.The average US taxi-out time is 16.63 min.So more than 128 million minutes are spent in the taxi-out process.This situation is expected to further deteriorate with the rise in demand for air transport.2The long taxiing-time malaise has been observed also at Beijing International airport(the world's second-busiest airport),and is of increasing concern at other major international airports.

Faced with the severe environmental and economic repercussions of excessive fuel consumption,the industry recognizes that there is an urgent need to significantly curtail taxiing times,and taxiing fuel-burn cost,and to alleviate airport surface congestion effectively.In order to achieve this,a commonly implemented strategy is the well-known Departure Pushback Control method,which is essentially‘‘a(chǎn) low-cost and centralized approach that manages pushback process from the gates,”3and transfers long taxiing times into longer gatehold times.However,this method can significantly increase gate-hold costs.This attests to the need to work towards an effectively crafted balance of aircrafts that incur fuel-burncosts and spew emissions on taxiways,and aircrafts held at gate and accruing gate-hold costs,when applying a pushback control strategy in order to achieve the objective of reducing surface congestion at airports.

2.Literature review

From a mathematical modeling perspective,queuing models have been mainly used to study departure operations at airports.Shumsky4considered the taxiway system to be a queuing system,and developed the static and dynamic analytical models to predict the take-off times of flights,but ignored the stochastic nature of the runway service process.Hebert Dietz5developed and implemented multiple queuing models successfully in mixed-traf fi c cases by using data from LaGuardia airport.These models can deal with arrival and departure operations simultaneously.Pujet et al.6built an input-output model in which the queuing servers include both airport terminals and runways in the prediction of taxi-out time,and compare several departure control schemes.

Idris et al.7presented a queuing model to estimate the taxiout times of every single aircraft by analyzing the factors affecting taxiing times,such as terminal configuration and takeoff queue lengths.However,this model did not model the runway service time explicitly,and it ignored the necessary information about the number of aircraft on the ground.Consequently,this model can be used only in tactical applications such as surface-movement advisory tools.Ravizza et al.8built a surface movement model,and used multiple linear regression methods to predict taxi-out times.Simaiakis and Balarkrishnan.9,10developed an analytical queuing-network model of the departure process to supervise queues on the ground,and a predictive model for estimating taxiing times and taxioff times to improve the coordination of the various departure processes,and thus increase surface efficiency.Cheng et al.11employed a nonlinear control system to establish a simulation model(based on feedback linearization)that estimates taxiing performance efficiently.This system was bene fi cial for the better coordination of surface traf fi c movements by the reduction of the clearing time required of taxiing aircraft and aid controllers.Zhang and Wang12proposed an econometrics regression model that relies on computer software and statistical tools to determine the unimpeded taxiing time and taxiing delay.Carr et al.13employed a departure traf fi c model by assigning a series of simple queuing dynamics and traf fi c rules.Their proposed model was tested using Monte Carlo simulation with actual operation data from Newark Liberty International(EWR)airport.The margin of error of their simulation results(measured as the difference between the simulated and actual take-off times)was found to be less than 10%for nearly 88%of aircraft included in their study.

Other approaches,such as integer programming,14mixedinteger programming,15and multi-objective parallel evolution algorithm,16have also appeared in the literature that addresses the alleviation of airport surface congestion.Murc?a17designed a robust optimization method to meter the departures of aircraft in‘‘uncertainty”taxi-outs.This approach could dynamically determine an optimal departure sequence of aircraft being released from the gate.Cheng18developed a dynamic programming-based taxi-route optimization model using the Dijkstra's algorithm.Lee et al.19compared the performance of two different pushback control strategies using data obtained from the Detroit Metropolitan Wayne County(DTW)airport.The first strategy was a queue-based control strategy emphasizing aggregate-level surface,while the second strategy adjusted taxi-out times on a first-come- first-serviced basis,using a node-link model of the airport,and an integer programs to optimize the pushback times.Balakrishnan and Jung20used integer programming to optimally coordinate surface operations at Dallas/Fort Worth(DFW)airport.They studied surface operations pertaining to both arriving and departing aircraft,and focused on optimizing taxiing routes by using different control points on the airport ground.Using real air traf fi c data,their study concluded that‘‘controlled pushback”achieved an 18%reduction in taxi-out times,while‘‘taxi reroutes”resulted in a 14%reduction in taxi-in times.

Collaborative Decision Making(CDM),which allows for the exchange of departure slots between airlines,is another approach to mitigating surface congestion.Vossen and Ball21explored a mediated departure-slot trading mechanism,and introduced a general bartering framework that allows airlines to trade slots on formal application,and proposed an optimization model for slot-exchange procedures.Madas and Zografos.22studied the application of an integrated methodological framework for assessment,and the selection,of the best slot-allocation strategies in regard of the various airport topologies.Liu etal.23,24employed discrete differential evolution algorithm,and proposed an aircraft pushback slot-allocation model that considered external cost of airport surface congestion to minimize the total surface cost.

From the foregoing discussion,the issue of surface congestion at airports can be addressed by either employing pushback-control methods,or by optimizing taxiing routing.In this study,our focus rests on the first of these strategies,namely,departure-pushback-control frameworks dedicated to achieving the advantageous balance aircrafts on the taxiways and aircrafts hold at the gates.

We begin with Feron et al.,25who introduced into the literature the study of the use of virtual queues in airport surface-traf fi c management research,and proposed several departure pushback-control strategies,such as pushback sequencing and pushback rate control to curtail surface congestion at airports.Then there are Burgain et al.26who presented a more re fined version of this work,wherein a Collaborative Virtual Queue(CVQ)concept was employed to hold aircraft away from the taxiway queue.The most commonly employed pushback-rate-control approach is the well-known K-control strategy,which is based on the virtual queue concept,and enforces a threshold method that permits aircraft to pushback with a constant rate until the number of aircraft in the taxiway queue reaches the prede fined threshold value K.Mathematically,this pushback control method can be expressed as:

where k is the current queue length(number of aircrafts)in taxiway,K is the maximum allowable(threshold)queue length or taxiway queue threshold,λ(k)is the pushback rate corresponding to the current queue length,and λ is the fixed pushback rate employed until the queue threshold is reached.Note that the chosen value of K has to be large enough to maintain high levels of taxiway and runway utilization,but conversely,a very large K-value can lead to excessive taxiing times and related fuel-burn costs.Hence,an appropriate choice of K is critical to maintain a balanced control method.

At Boston Logan International(BOS)airport,Simaiakis et al.27employed the traditional K-control method to determine the optimal K value that reduces surface congestion as well as fuel-burn by airport field evaluation.Their results estimated that implementing the K-control method reduced fuelburn by about 12000-15000 kg/day,while the gate-hold times increased by 4.3 min when averaged across the 247 flights,and in their study.Similar results are also reported in Simaiakis,28where the optimal pushback rates that minimized surface operation costs are estimated by employing a tandem queuing model with dynamic programming.Martinez29studied the impact of varying gate-hold-times limits on on-time departure performance at LaGuardia airport by deploying the K-control method.Their study concluded that the largest possible reduction in taxi-out times and associated fuel-burn is achieved when no limits are enforced on the gate-hold time.Nevertheless,from a practical point of view,gate-hold time limits are helpful for freeing up gates for taxiing-in aircrafts and can maintain both efficiency and fairness of airlines.

K-control presents outstanding performance for departure pushback control,but without predicting the taxi-out time,it cannot control the gate-hold time and taxi-out time precisely for an individual aircraft.Moreover,K-control strategy provides only rigid static pushback rates,while a reasonable method should adjust the pushback rate dynamically to adapt the surface traf fi c state.

Consequently,we focus on developing a Predicted taxi-out time-based Departure dynamic Pushback Control method(PDPC)that not only rations aircraft pushback rate,but is also geared to allocate operations time rationally,and achieve the necessary tradeoff between fuel-burn reduction and gatehold times.The performance of this PDPC method is compared also with the K-control method.The motivation for the method presented in this paper stems from obtaining a practically viable pushback control mechanism.It is imperative to retain the nice properties of the PDPC method(low fuel-burn,minimal costs,etc.),yet provide air traf fi c controllers with the flexibility to allow aircraft to pushback without incurring additional delays in the manner of the K-control method.The structure of proposed model is shown in Fig.1.

The proposed model of the pushback control method,shown in Fig.1,consists of two modules:Module I,the taxiout time prediction module,is used to predict taxi-out times;Module II,the pushback method module,is used to transfer the predicted taxi-out time into gate-hold time and actual taxi-out time,to save fuel-burn cost.The aim of this module is to find the optimal taxiway queue length threshold.

This paper is organized as follows.In Section 2,we review the related works,and describe the model structure of the pushback method model.Next,in Section 3,we introduce a taxi-out time prediction model using nature-inspired metaheuristic optimization in least squares support vector regression.Based on taxi-out prediction,Section 4 proposes the dynamic pushback model equipped with a linear penalty function.An iterative taxiway queue length threshold optimization algorithm is also designed,along with the numerical results using data at PEK airport in Section 5.In order to evaluate the proposed pushback control method,a comparison of results with the K-control method is presented,and the pro fi t in using the PDPC method is displayed in Section 5.Finally,Section 6 summarizes our findings,and provides some pointers for future research.

3.Taxi-out time prediction

The first step of the pushback model is the taxi-out time prediction.Other researchers'efforts are mentioned,such as those of Pujet et al.6who predicted taxi-out time by an input-output queuing model.Simaiakis and Balakrishna10predicted taxiout time by a queuing model of departure process as well.Statistic and machine learning methods are well employed to predicting taxi-out time.Balakrishna et al.30,31considered the stochastic nature of the departure process,and designed reinforcement learning algorithms to predict taxi-out time trends approximately 30-60 min in advance.Ravizza et al.32used different approaches,which included multiple linear regression,least median squared linear regression,M5 model trees,Mamdani fuzzy rule-based systems,and TSK fuzzy rule-based systems,to predict taxi-out times.Lee et al.33implemented machine-learning approaches to predict taxi-out time,and found that Support Vector Regression method is more effective than the Linear regression method and the Dead reckoning method.

3.1.Factors analysis

Researchers have found that departure taxi-out time is effected by several factors,including the departing queue length on the taxiway,the number of arriving aircraft during the taxi-out process,30,31taxiing route distance,28and time of a day.30Thus in this research,several factors are taken into consideration.Note x=[x1,x2,x3,x4]as the state variable,where x1is the departing queue length on taxiway,x2is the number of arriving aircraft during taxi-out process,x3is taxiing route distance and x4is plan take-off time.For lack of some details such as weather and behaviors of pilots,these characters cannot be considered.

Fig.1 Predicted taxi-out time-based dynamic pushback control method model structure.

3.1.1.Analysis with individual factor

In order to explore the influence of each factor on taxi-out time,different individual factors are analyzed.The coefficient of determination R2and p-value are checked for actual taxiout times set and its corresponding individual factor.The R2is shown as follows:

where y is the actual value,is the mean value of y,^y is the value of corresponding individual factor,and n is the number of taxi-out time samples.

Table 1 shows the results of relevance and significance analysis.

From Table 1,it can be found that the results of x1-x3have significant correlation with the target value.Although the correlation between x4and the target value is weak,x4is also considered for its significance.The other less important factors,which were mentioned in Ref.8such as number of engines of the aircraft(R2=0.007&p=0.039)and using the wake vortex categories of the aircraft(R2=0.032&p=4.4×10-5),are not taken into consideration.

3.2.Least squares support vector regression

The Support Vector Regression(SVR)technique is an effective forecasting method,the approach of which is to map input variables into a high-dimensional space through a kernel function K(x,x′)to constructing a linear decision function.The regression function of SVR is

where ω is the weight vector,φ(x)can be replaced by kernel function,and b is the bias term.The optimal SVR function can be obtained by minimizing risk term||ω||2.Risk function is generally determined with ε-SVR,which has two parameters(C,ε)to be optimized.Whereas the parameter ε can be eliminated on a least squares loss function ekby Least Squares Support Vector Regression(LSSVR).This study uses a least squares cost function in a LSSVR to train the input data,obtaining a linear set of equations in dual space,and reducing the computationalburden.Given a training data setthe optimal regression function is determined by solving the following formula:

Table 1 Results of relevance and significance analysis between taxi-out time and the individual factor.

where ekare error variables,φ(xk)are nonlinear mapping function,and φ（x）Tφ（xk）=K（x，xk）,C is the empirical error constant.

In this study,we have only a few features(＜10)and the scale of training sample is between 10 and 10,000.Thus it is proper to use the Gaussian Radial Basis(RBF)function kernel.Moreover,since RBF kernel function possesses the advantages of high classi fi cation accuracy and computational efficiency,this study maps the input variables with RBF kernel function.The RBF kernel can be expressed as k(x,x′)=exp(-γ||x-x′||2),where γ is the parameter to be optimized.The LSSVR regression function is formulated as

where αjare Lagrange multipliers.

3.3.Improved fi re fl y algorithm optimization

3.3.1.Fire fl y algorithm

The Fire fl y Algorithm(FA),as a new nature-inspired metaheuristic optimization algorithm proposed by Yang,34is highly efficient at solving numerous optimization problems.In FA,the fi re fl ies are attracted one to another according to two factors:brightness and attraction.Brightness is determined by the location of the fi re fl y and the target value.Fire fl ies with higher brightness represent higher attraction,and attract the lowbrightness fi re fl ies.Fire fl ies would move randomly if they had similar brightness.

The optimization problem can be considered as the maximization problem in regarding brightness as the objective function.De fi ning the brightness of the fi re fl ies as I=I0e-γr2ij,the relationship of the attractiveness of fi re fl ies and distance can be written as β=β0e-γr2ij.Where γ is the absorption coefficient,and γ ∈ ［0.1，10］,rijis the Cartesian distance between fi re fl ies i and j.β0is the attractiveness when rij=0.When fi re fl y i is attracted by fi re fl y j,the update function of location is written as

where rand is the random number which follows a Gaussian distribution,and rand∈[0,1].

3.3.2.Adaptive step factor

Step factor affects the global and local optimal searching ability.The large step factor adapts to the global optimal solution ability while gradually reducing the step factor benefits of the fine tuning for local optimal space.In order to improve the convergence efficiency of FA,an adaptive step factor is proposed to replace the traditional step factor,which is written as

where α0is the initial attractive coefficient,ψ is the controlling parameter empirically selected as 0.9,t is the number of iterations.This adaptive step factor induces monotonical decrease as the number of iterations increase.

3.3.3.Le′vy flight

The random walk method of conventional FA often leads to premature convergence instead of remaining globally optimal when dealing with numerous local optimal solutions.In order to improve the probability of searching global optimal solution,this study adopts Le′vy flight to update the distance between fi re fl ies.Le′vy flight,proposed by P.Le′vy,is random walk theory that the walk length follows Le′vy distribution,L(s)～|s|-ζ,where 1＜ ζ≤3 is an index,s follows a powerlaw distribution.Le′vy flight follows the laws of nature more than Gaussian distribution and uniform distribution and more adapt to Nature-inspired metaheuristic optimization algorithm.Thus the new location update function is written as

where?denotes entry-wise multiplication.

3.3.4.Improved fi re fl y algorithm-based support vector regression structure

In this study,regarding the LSSVR as the main body of predictive model,and considering the optimal parameters of the LSSVR model as an optimization problem,the objective is to reduce prediction errors.The flowchart of Improved Fire fl y Algorithm-based Support Vector Regression(IFA-LSSVR)is shown in Fig.2.

Fig.2 shows three modules of IFA-LSSVR model:data classi fi cation module,IFA optimization module,and LSSVR model.Data classi fi cation charges the normalization and data set classi fi cation.Data are classified into three sets including training set,validating set and test set.The training set is used to train LSSVR model and test set is used to evaluate the performance of predictive model after IFA optimization operation.In IFA the optimization module,a maximum number of iterations is set for stopping the iterations.Or once the value of fi tness function has no improvement(it meets with accuracy),the IFA optimization module will also ful fi ll the termination criteria.Thus,the optimal parameters,selected by IFA,are used to build the optimized LSSVR model.

Fig.2 Flowchart of IFA-LSSVR model.

4.Taxiway queue length threshold optimization

4.1.Assumption and notations description

In this section,a predicted taxi-out-time based dynamic pushback control method of which the target is to find the optimal taxiway queue-length threshold,is presented as the means of reducing departure operation cost.In the scope of the problem under consideration,aircraft follow is a sequence of operations as described below.An aircraft is allocated an available gate,where a departure pushback request is sent,following a time lapse,to execute a routine,such as accommodate alighting passengers,maintenance checks,and boarding passengers.The aircraft stays at the gate until it receives the mandatory pushback approvals from air traf fi c control,and after obtaining the necessary instructions,the aircraft moves away from the gate,and joins the taxiway queue, finally entering the runway when it arrives at the pole position in the queue,from where it takes off.In this paper,we consider an operation starting from the instant a pushback request is initially sent,to the instant this aircraft reaches the runway.That is,we model the excess gate-hold time and the corresponding taxiout time for each aircraft.

For the remainder of this study,several air traf fi c operating assumptions are made:

(1)Runway-configuration and operability remain the same throughout the day,and are unaffected by factors such as meteorological conditions,airline service disruptions,etc.

(2)The service time of take-off follows the same distribution,and is calculated as a weighted average service time across different aircraft classes(small,large,and heavy).

(3)Aircrafts in the departure queue are attended-to on the first-come- first-served rule.

Based on these conditions,the departure pushback control problem addressed in this study aims to obtain an optimal trade-off between gate-hold times and taxiway queuing times,while respecting flow-balance constraints and limits on gatehold times and taxiway queue lengths.The aim is to minimize the total operational cost.To analyze the above-described problem,the notations and Definitions described in Table 2 are used throughout the paper.

The taxi-out process includes four kinds of events named stop,turn,acceleration and taxiing with constant speed.Each phase consumes different level of fuel-burn.Khadilkar et al.35has concluded that:

(1)Taxi-out time dominates the taxi-out fuel burn and is statistically significant.

(2)The effect of the numbers of stops and turns on total fuel burn is very small and appears to be negligible.

Consequently,the taxi-out time and number of acceleration events(one acceleration event is de fined as the aircraft accelerated at more than 0.15 m/s2for at least 10 s)are considered as independent variables.The calculation formula of fuel-burn consumption for one aircraft follows

where a1m,a2m,a3mare the corresponding parameters to be estimated according the aircraft type m.nais determined by the taxi-out routes.

4.2.Dynamic pushback rate

Recall that the conventional K-control,the pushback rate,can be mathematically expressed as Eq.(1).This pushback control method has been tested at BOS airport.25Motivated by the successes of the K-control method,this study prescribes a dynamic pushback control method(DPC)that uses a variable pushback rate that is dependent not only on the taxiway queue threshold,and also on the current taxiway queue length.It advocates a linear penalty function to dynamically controlthe pushback rate,with the objective of minimizing the total operation cost,thereby obtaining the optimal taxiway queue threshold K.specifically,this pushback rate of DPC method can be mathematically expressed thus:

Table 2 Notations and Definitions of pushback control model.

Comparing the form of the K-control method(see Eq.(1))to that of the DPC method(see Eq.(11)),it is evident that the K-control method is too lenient,for it allows the pushback rate to be 1 until the queue length reaches the threshold.

4.3.Gate-hold penalty

Note that in this research,we find that the main operation cost comes from fuel-burn,whereas in departure process(for the present purpose,which is the process from‘‘pushback”to‘‘begin take-off”)fuel-burn happens after actual pushback rather than at the gate-hold.The minimum fuel-burn cost would induce aircraft always to prefer to be held at the gate,with the engine on,to save time on the taxiway.Thus,a gate-hold penalty prescribed to avoid long gate-hold times.In Ref.28,this penalty is called‘‘nonutilization of taxiway.”

The penalty for gate-hold times is set to follow an exponential function of the form pj=eθgj-1,where θ is a parameter that represents the value at which the gate-hold cost is equal to the fuel-burn cost(break-even point).Note that the threshold time at which this break-even occurs varies according to the specific airport under consideration.In our case,we assume that this threshold time limit is 30 min,as an aircraft at PEK is considered to be‘‘on-time”if it pushes back from the gate within 30 min of its scheduled departure time.35Equating the fuel-burn and gate-hold costs,we get θ=0.2096.Therefore,the penalty incurred by flight j per unit of gate-hold time is pj=e0.2096gj-1.Fig.3 depicts the fuel-burn cost and the gate-hold cost as a function of time,where it can be seen that the linear fuel-burn cost exceeds the gate-hold costs until the break-even time of 30 min,and subsequently,the exponentially increasing gate-hold cost always dominates the fuelburn cost.

4.4.Objective function

The pushback control method sets the pushback rates to balance two objectives,i.e.minimizing the fuel-burn cost,and gate-hold penalty cost.Objective function can be written as

Fig.3 Fuel-burn and gate-hold costs as a function of time.

where constraints Eq.(13)are the pushback rate for aircraft j when the current taxiway queue length is k,constraints Eq.(14)are the fuel burn consumption of aircraft on taxiing routes,constraints Eq.(15)are the taxiway queue length threshold,constraints Eq.(16)are the gate-hold time limit.

4.5.Taxiway queuing analysis

This study concentrates mainly on the runway used for departure.As precursor to the queuing analysis,we need to verify whether the pushback request rates follow a Poisson process.Towards this target,using the pushback request time set for a seven-day period(include the tested date)from the obtained data,the χ2test is performed.If the null hypothesis,‘‘the pushback request during each day follows a Poisson process,”cannot be rejected,the pushback requests during one day can be safely assumed to follow a Poisson distribution with rate λ.The service time at the taxiway is also assumed to follow an exponential distribution with rate μ,where μ=1/τ.Since the taxiway queue length is constrained to not exceed a threshold K,this queuing system loosely resembles an M/M/1/K queue system.

Compare to the conventional M/M/1/K queue system,in our problem setting,an aircraft of which the initial pushback request is denied can reapply for pushback after one service completion.The following Markov chain model describes a queuing system where the states of the Markov chain represent the current taxiway queue length k(0≤k≤K);the transition rate from state k to(k+1)is given by λ(1-k/K);and the Markov chain returns to state k from state(k+1)with a rate of μ.The state transition diagram of the Markov chain is shown in Fig.4.

Following standard Markov chain procedures,the state transition equations can be formulated as follows:

Solving the Eqs.(17)-(19),the generic expression for the probability being in state k(k≠0)is expressed as:

Fig.4 State transition diagram of the Markov chain.

Using the probabilities Eqs.(20)and(21),the expected queue length in taxiway,and the average pushback rate,can be estimated as Eq.(22)and Eq.(23).

Using Little's law,the expected waiting time for an aircraft in the taxiway is given by:

Thus,the fuel-burn consumption of an aircraft can be written as

Now we consider the situation that there are no predictive taxi-out times.As pushback decision makers have no idea of the possible taxi-out time in advance,the pushback process remains reliant on the operator's judgement on whether to push or hold at gate.The gate-hold time for an aircraft is the time betweenitsinitialpushbackrequestandactualpushback.Afterwards,the expected gate-hold time can be achieved by a conditioningofthenumberofaircraftinthetaxiwayqueue.Notethat when the current taxiway queue length is k,the pushback probability for an aircraft is(1-k/K),and the probability of holdat-gate is(k/K).The gate-hold aircraft sends a new pushback requestafterwaitingoutoneservicecompletion.Withthisinformation,the conditional expected gate-hold time without predicting taxi-out time E[gnp]when k≠K is given by:

When the current taxiway queue length is K,an aircraft would have to hold at gate for at least one service completion(τ)before it has a chance to pushback successfully.The conditional gate-hold time when the current taxiway queue length K,is given by:

Consequently,the expected gate-hold times without predictive taxi-out time(gate-hold time of DPC method)can be calculated as the product of the conditional gate-hold times,and on the probability of the current taxiway queue length being k,then summing all possible values of k(k=0,1,...,K),as shown below:Now we consider the PDPC method,and assume that the taxi-out time was predicted in advance according to a series of factors,and note the predicted taxi-out time as F.Once the pushback method is implemented,an optimal taxiway queue-length threshold K has been determined.Consequently,the maximum taxiway-queue evacuation time is given by the product of μ and K.Thus,the expected gate-hold time based on predicted taxi-out time when the current taxiway queuelength is k can be given by:

where Fjis the jth element of F.

Finally,the total operation cost for an aircraft when the current taxiway queue-length is k,with a fixed taxiway queue-length threshold K,can be calculated as follows:

As seen in the foregoing discussion,in order to obtain the optimal total operation cost,along with the best K value,an algorithm is proposed,and the details are elaborated in the following discussion.

4.6.Taxiway queue-length threshold optimization algorithm

In this section,an iterative taxiway queue-length Threshold Optimization Algorithm(TOA)is proposed-taking the predicted taxi-out time,historical pushback request rates,and mean service times as input-that returns the optimal total operation cost,and corresponding optimal taxiway queue threshold,by using PDPC method.

The basic need to develop an iterative algorithm stems from the presence of lost pushback requests in the queuing system,which occurs when an aircraft has been denied the pushback permission and reapplies for pushback.Consequently,this iterative procedure has to make sure that multiple pushback requests from one single aircraft are taken into consideration,and that all departure pushback requests are satis fi ed at the closure of the time window.The outer-loop of the proposed algorithm,as the decision variable K,is bounded between 1≤K≤30,according to the capacity of the taxiway and other referents.Thus,all feasible values of K are iterated over,and this forms the intermediate loop of this algorithm.For each value of K,the inner-loop is developed to evaluate the expected waiting time in taxiway and gate-hold,and the collected data are then used to calculate the total operation cost.

In the initialization step of the inner loop,the pushback request rate is input at its original value.The algorithm is solved through Eq.(20)and Eq.(22),and the difference(δ)between the computed pushback rate Eq.(23)and the original pushback request rate is also calculated,and the pending difference is then added to the new pushback rate.The algorithm then updates the pushback-request rate,and this iterative procedure continues until the difference(δ)of the final iteration is less than a tolerance(say,ε=10-5).The gate-hold times are also calculated by Eq.(29)to estimate the total operation cost.Once an inner-loop is finished,the value of K is incremented by 1,and the iterative process continues.The pseudocode of this algorithm is shown below.

5.Case study at PEK

This section presents the computed results of the departure process employing the PDPC method.The datasets in this study are the Aviation System Performance data(2013)of PEK,from the Second Research Institute of Civil Aviation Administration of China,with a huge traf fi c volume.PEK airport has three parallel runways,with Runway 18R/36L being used for combined arrival and departure operations,Runway 18L/36R mainly dedicated to departures,and Runway 01/19 used only for arrivals,with all three runways serving both departures and arrivals at traf fi c rush hour(Civil Aviation Administration of China,2013).Thus,the departure data of 18L/36R runway are chosen in this study.The ASP data contains the following information:aircraft type,schedule take-off time,gate,schedule landing time,apply-pushback time,actual pushback time,actual take-off time for departure flights,and actual landing time of arrival flights.

The most intact recorded data are those compiled in October and November by careful screening.To begin with,the time horizon was set as 16 h(6:00AM to 10:00PM).The initialized maximum population size and maximum number of iterations in IFA are chosen as 20 and 100,respectively.The mean service time at the taxiway(τ)was fixed at 1.70 min(which is consistent with that at other major airports,e.g.,BOS).The fuel-burn cost(c)was set as 1$/kg(based on the prevailing costs in 2013),and the fuel-burn cost follows the findings presented in Ref.36.The lower and upper limits on the taxiway queue length were set as Klow=1 and Kup=30(similar to Ref.27),respectively,with the upper limit being comparable to limiting conditions at other international airports of similarcapacity.The PDPC model is implemented in MATLAB 2015b.Using the pushback requests data from 11-Nov-2013 to 17-Nov-2013,the results of the χ2test revealed that the null hypothesis‘‘the pushback request during each day follows a Poisson process”cannot be rejected at a 95%confidence level.The values of parameters a1,a2,and a3are following Ref.35,such as for A320,a1=-0.0896,a2=0.0124,a3=0.1174,and for B757,a1=0.2133,a2=0.0173,a3=0.0699,etc.In addition,the overview of training dataset is recorded in Table 3.

Table 3 Overview of training dataset from PEK airport.

As described is Table 3,#of departing queue,#of arriving number and plan take-off time are obtained from ASP dataset,as well as the gates information for each departure aircraft.Distance of taxi-out route set is obtained from China's civil aviation domestic AIP.Taxi-out routes include the routes between south entrance and north entrance of 18L/36R runway to aircraft stands/gates(include 139 terminal stands and 114 remote stands),respectively.The plan take-off time set is transferred into a minute-format of a day(for example,7:00 is recorded as 420).

5.1.Results comparison of taxi-out time prediction

Given the performance data of flights,the proposed IFALSSVR model estimates the taxi-out time from 11-Nov-2013 to 17-Nov-2013 by using the related factors.Table 4 describes the performance measures of prediction,and the comparison with several conventional methods with identical factors,where RMSE is the root mean square error,MAPE is the mean absolute percentage error,PA#is the predictive accuracy percentage within±#minutes,GLR is the Generalization linear regression method.

As described is Table 4,the introduced IFA-LSSVR outperforms other approaches on all performance measures.The RMSE and MAPE are 2.16 min and 16.69%,respectively.The PA3 and PA5 are 84.71%and 95.66%,respectively.Details of prediction results in an individual day(498 flights)are shown in Fig.5.

Fig.5 depicts the details of results for each predictive method.We can see intuitively in Fig.5 that there is a biggap between the results of GLR and actual taxi-out time,and GLR approach presents obvious underestimations across the whole day in taxi-out time prediction.The traditional SVR model performs better than the GLR model,while the IFALSSVR model achieves the best fi tting ability,both at peak hours and off-peak hours.Meanwhile,the shape of curves implies the trend of taxi-out time in a day without any pushback control method.We can obtain two peak periods,which occur between at 7:00-9:00 and 15:00-17:00,respectively.Especially at the first peak period,some of these aircrafts spend more than 40 min taxiing or waiting at the runway queue,leading to excessive and undesirable greenhouse gas emissions.

Table 4 A comparison of modeling performance measures for predictive methods at PEK airport.

Fig.5 Plot of average actual taxi-out time vs predicted taxi-out time in 15 min for each predictive method on Nov.13,2013.

5.2.Comparison of pushback control methods

For the PDPC method tested in this work,a total of four results were obtained by varying the maximum limits on the gate-hold times,and the values(in minutes)chosen for these limits on gate-hold times were set as{15,20,25,≥30}.The inputs to the simulation model include the predicted taxi-out time set,the pushback request times,the service time,the fuel-burn cost per flight per minute,and the prescribed limits on the gate-hold time.The performance measures of interest were identified as the optimal taxiway queue threshold(K),the optimal cost(CT,in$),the average taxiway waiting time(w,in minutes),the average gate-hold time(g,in minutes)and the fuel cost reduction(CR,in$).And in particular,we monitored the effect of limiting the gate-hold times and the taxiway queue threshold on the total cost function.Note that the fuel-cost reduction is computed as the difference between the fuel-burn costs for the no-control method,and the fuel cost for the PDPC method under consideration.Before implementing the PDPC method,we simulated the pushback process without the pushback control method.By fixing the taxiway queue length as 106,aircraft can be pushed back without gate-hold to simulating the no-control scenario.Total operation cost on a single day at PEK is calculated as$157612.52.

We employed the proposed iterative taxiway queue-length threshold optimization algorithm to solve the PDPC method,using the pushback request data on November 13,2013.The indicator curves(g,w and CT)of loop in TOA are shown in Fig.6.

Fig.6 portrays a part of indicator curves of loops in TOA(the cost value is extremely high for small values of the taxiway queue threshold).The arrow lines display the feasible regions for each gate-hold time limit,such as the condition within 30 min for gate-hold times of all aircrafts is K-value≥18,etc.The cost curve follows a convex profile and the optimal cost is obtained at K=19 when gate-hold time limit is 30 min.The opposite trend between the curve of g for each taxiway queue threshold and it of w shows the transformation ability of PDPC method.The optimal results for each gate-hold time limit are recorded in Table 5.

Fig.6 Indicator curves of loop in TOA.

As expected from the numerical results presented in Table 5,the required optimal queue-length K reduces,with a corresponding increase in the maximum allowable gate-hold times:i.e.,as aircrafts are permitted to remain for a longer duration at the gates,a reduction in the taxiway threshold-queue length,and the associated average taxiway waiting time,are both observed.Conversely,the average gate-hold times for aircraft increase,along with a corresponding increase in gate-hold time limits,and the total cost reduces as a function of the limit on gate-hold times,reaching a minimum value of US$85127.17,corresponding to the gate-hold time limit of 30 min,which is exactly the break-even point between gate-hold costs and taxiing costs set in our model.At this moment,the average gatehold time and average taxi-out time on taxiway are 9.8 min and 10.82 min,respectively.

The results of the proposed model can be compared to the K-control method.With the same set of inputs,departure process is simulated following the control rule.Fig.7 displays a part of indicator curve of loops with K-control method.

Fig.7 shows that the indicator curves of K-control method has similar trend with PDPC method.The condition within 30 min for gate-hold times of all aircrafts is K-value≥15 and the optimal cost is obtained at K=16 when gate-hold time limit is 30 min.The shape of g and w curves shows that K-control method has the ability of transferring w to g as well.

Table 6 presents the simulation results of K-control method at PEK airport.

We can see from Table 6 that results of K-control method show a similar trend for each measure,while for the determined gate-hold time limit,K-control has bigger CTand w values,and smaller K and g values,than the PDPC method.These trends'details are depicted in Fig.8(a)-(e).

Fig.7 Indicator curves of loop with K-control method.

A pictorial representation of the sensitivity of the various performance measures to the gate-hold time limits(with the departure pushback control strategies employed)is presented in Fig.8(a)-(e).In Fig.8(a),the K-value-curve of K-control is linear decreasing,while that of the PDPC method is not,due to the impact of dynamic control.The extending gaps of optimal cost between two methods with the increasing of G imply,according to Fig.8(b),that these gate-hold limits have more impact on the PDPC method.In Fig.8(c)and(d),the exact-same gaps of w and g between K-control and PDPC method just show that both methods could transfer part of the original taxi-out time into gate-hold time,even though their transferring ability is different.And Fig.8(e)shows the capacity for saving fuel-burn cost.

Consequently,the proposed PDPC method can produce a reduction in total operation cost and fuel-burn cost of 14.0%and 21.1%respectively,compared to K-control method(at G=30 min).Note that this optimal PDPC method represents 37.2%and 52.1%reduction on total operation cost and fuelburn cost,respectively,as compared to the cost of not enforcing any pushback control mechanism.

This positive result shows a high level of ability to reduce fuel-burn cost and airport surface congestion.The proposed pushback control model provides an effective incentive for decision-makers to improve taxi-out operation performance.

5.3.Operation pro fi t of using PDPC method at PEK

An effect of using the PDPC method is the ability to avoid large numbers of aircraft having to be pushed back during in a short time.Appropriate delayed pushback achieves a lot of cost saving,as well as the operation pro fi t.Based on the totaloperation indicators analysis in Section 5.2,some hourly details are presented to interpret the pro fi t at PEK.The performance number of pushbacks,the average queue lengths in taxiways,and hourly operational time without the PDPC method(G=30 min)are shown in Fig.9,respectively.

Table 5 Results for PDPC method with limit on gate-hold time.

Table 6 Results for K-control method with limit on gate-hold time.

Fig.8 Comparison of results between K-control method and PDPC method.

Because the departure queuing system is a non-loss process,all aircrafts have to be pushed back in the time window.PDPC method,as shown in Fig.9(a),has such a trend of converting pushback rate to the average.This is evident in the hours from 8:00 to 10:00,and from 13:00 to 16:00.Note that this time conversion is restricted by gate-hold time limits when an aircraft cannot be pushback-postponed in finitely.

In Fig.9(b),no queue lengths are more than those without pushback control method.Thus we can figure out that aircraft which are held at gate reduce traf fi c pressure on the taxiway.Once the queue lengths in the taxiway are curtailed,taxi-out time will decrease correspondingly.Fig.9(c)compares the average gate-hold time and average taxi-out time in each hour.The summation of two values is the average predicted taxi-out time.Note that the first bar shows only taxi-out time.That is because the number of pushback requests in the period from 6:00 to 7:00 is small(17 pushback requests),and that gatehold behavior is unnecessary.Then,the visual fact is that the percentage of gate-hold time rises with the increase in traf fi c volume.This observed performance,especially in peak hours,can curtail departure taxi-out time and surface congestion effectively.

Fig.9 Performance in each hour over a 16 h period on Nov.13,2013.

6.Conclusions

Airport surface congestion is a key problem in the aviation industry,as it can lead to long taxiing times and excessive fuel-burn.Employing a departure pushback control strategy that can stem costs and temper environmental effects is of paramountimportance to the entire aviation industry.Towards the goal of reducing taxi-out time in the taxiway and the corresponding fuel-burn cost,a predicted taxi-out time-based dynamic pushback control model to ration aircraft pushback rate is proposed.The major conclusions of this study have been summarized as follows:

(1)This model can precisely and dynamically control the gate-hold time and taxi-out time for an individual aircraft using predicted taxi-out time.The aim of the proposed PDPC method is to find the optimal taxiway queue length threshold,which not only needed to reduce the number of pushback aircraft at peak hours,but also to keep the high utilization of taxiway.

(2)The proposed IFA-LSSVR method can predict taxi-out time precisely.Using actual performance data at PEK airport,the results show better predictive ability than conventional regression approaches,and can achieve accuracy within ±3 and ±5 min at 84.52% and 92.36%,respectively,in an individual day.

(3)The solution offered by the PDPC model shows a high capability to reduce total operation costs,average taxi-out time,and fuel-burn cost.It can achieve 52.1%and 21.1%reduction in fuel-burn cost compared to the no-control situation and the K-control method.The comparison of airport operation performances strongly suggests that the alleviating of airport surface congestion is mandatory.

(4)Because we assumed that the taxiway service times for all aircrafts are equal,and calculated by using a weighted average service time across all aircraft types,there is a need to adapt our method to incorporate multiple aircraft types.Another possible extension would be to model departure pushback in the presence of multiple runways.

Acknowledgment

This research has been partially supported by the National Natural Science Foundation of China-Civil Aviation Joint Fund(Nos.U1533203,U1233124.)