A New Meta-Heuristic Approach for Aircraft Landing Problem

，，，

College of Civil Aviation，Nanjing University of Aeronautics and Astronautics，Nanjing 211106，P.R.China

Abstract:A new meta-heuristic approach is proposed in this paper based on a new composite dispatching rule to tackle the aircraft landing problem（ALP）.First，the ALP is modeled as a machine scheduling problem with the objective of minimizing the total penalty，i.e.，total weighted earliness plus total weighted tardiness.Second，a composite dispatching rule，minimized penalty with due dates and set-ups（MPDS），is presented to determine the landing sequence.Then，an efficient heuristic approach is proposed to solve the problem by integrating the MPDS rule and CPLEX solver.In the first stage，the landing sequence is established based on the proposed MPDS rule.In the second stage，landing time is optimized using CPLEX solver.Next，a new meta-heuristic strategy is introduced into the heuristic approach by conducting the local search from the potential landing sequences，which are generated by the proposed MPDS rule.Finally，the performance of the proposed approach is evaluated using a set of benchmark instances taken from the OR library.The results demonstrate the effectiveness and efficiency of the proposed approaches.

Key words:arrival scheduling；air traffic control；decision support；meta-heuristic；local search

0 Introduction

The rapid growth of air traffic has led to a mismatch between traffic demand and scarce supply resources.Demand-supply mismatch results in airport congestion problems with substantial flight delays，excessive fuel consumption，and consequent air pollutant emissions.Countermeasures could be supplybased，such as adding runways to provide more capacity，or demand-based，such as demand management to control air traffic，or combined operational management to improve the efficiency of the system given the same demand and supply.The pure supply-side solution is capital-intensive and time-consuming.Demand management，ranging from legislative instruments to market-based measures，sacrifices the accessibility of some communities.They are not the focus of this study；instead，we focus on operational management of improving airspace system efficiency.In particular，we propose a new metaheuristic approach to schedule arrival aircraft efficiently.

The problem of arrival scheduling（aircraft landing problem，ALP）has attracted considerable attention［1-4］.To tackle the ALP，one should seek to determine the sequence and time of aircraft landing on available runways by optimizing given objectives while subject to a variety of operational constraints.Previous research generally focused on one of the following objectives:（1）Minimizing the total penalty［1-10］，i.e.，total weighted earliness plus total weighted tardiness；（2）minimizing the total delay［11-13］；and（3）minimizing the completion time of the last aircraft（or maximizing runway throughput）［14-15］. Concerning the solution algorithms to solve the ALP，CPLEX can be used to solve smallscale ALP.As ALP is an NP-hard problem，the computation time to find an exact solution grows exponentially with the increase of the number of aircraft. Therefore，dynamic programming（DP）［9，16］and branch and bound（BB）［1，17］，have been implemented to solve the ALP. Moreover，some researchers have sought assistance from the heuristic and meta-heuristic algorithms to tackle the ALP，such as cellular automata optimization（CAO）［6］，simulated annealing（SA）［7-8］，genetic algorithm（GA）［13］，and ant colony optimization（ACO）［18］.

In summary，studies of ALP encompass the following elements:Choosing an appropriate objective，setting a variety of operational constraints，modeling the problem，and implementing a solution algorithm. The above review revealed that there were usually two optimization strategies for ALP—one to optimize the landing time directly and one to determine the aircraft sequence first and then to allocate landing time.In comparison，the former is timeconsuming，especially when the number of arrival aircraft increases.For the second strategy，however，the neighborhood generation method of a candidate sequence should be specifically designed to reduce the computation time.Hancerliogullari et al.［19］took ALP as a machine scheduling problem and combined the composite dispatching rule and SA algorithm to solve the ALP.However，the composite dispatching rule only played a unique role as a hot start for the SA algorithm.In this study，we tackled the ALP by（1）proposing a new composite dispatching rule，（2）presenting a new heuristic approach based on such proposed rule，and（3）developing a new meta-heuristic approach through generating the neighborhood by the proposed rule.

The remainder of this paper is organized as follows.The problem formulation is defined in Section 1.Section 2 presents the proposed rule and the new meta-heuristic approach.The results and discussion are illustrated in Section 3.Concluding remarks are provided in Section 4.

1 Problem Formulation

1.1 Definition and description of ALP

Nowadays，parallel runways are the most common runway configuration of busiest airports around the world，especially in China.Each runway could be treated separately since the regular operation mode is independent parallel approach or segregated parallel operation.So，the ALP with a single runway is considered in this paper.As a result，the ALP can be defined as follows.To be given a set of arrival aircraft，the goal is to assign a landing sequence and time for each aircraft by optimizing the given objective while subject to a variety of operational constraints［20］.

As illustrated in Fig.1，ALP is trying to schedule the arrival aircraft（jobs）on the runway（machine）where the scheduled time is constrained by the earliest（release date）and the latest landing time（deadline），ought to land on the runway at the target landing time（due date）.The time window constraints could be obtained through trajectory prediction［21］.In the machine scheduling problem，setup time should be considered，which is similar to the wake vortex（WV）separations（time separation）in ALP.Table 1 summarizes the notation and variables used in this study.

Fig.1 Illustration of aircraft landing problem

1.2 Modeling and optimization of ALP

The mixed integer liner program（MILP）formulation for ALP is described as follows

Table 1 Notation and variables

Eq.（1）minimizes the total penalty of landing deviations from the target landing time. Eq.（2）specifies the time window constraint.Eqs.（3）—（4）ensure that the safe separations between the leading and following aircraft.Eqs.（5）—（8）define the earliness and tardiness of landing.Eq.（9）defines the scheduled time of arrival.

There exist two optimization strategies:One directly tackles the MILP formulation to obtain the scheduled landing time（SLT）and the other first establishes the sequence，then determines the SLT.In the former，once the SLT is obtained，the landing sequence is straightforward.However，it is timeconsuming.In the latter，once the sequence is determined，the SLT can easily be calculated by

or further optimized by the sub-problem as follows

Compared to the original problem，Eqs.（3）—（4）are replaced by Eq.（13）.With this change，the number of constraints in the sub-problem is 8n-3 while it is 3n(n-1)/2+6nin the original problem.Such a decrease in the number of constraints significantly reduces the complexity of the MILP programming.

2 New Meta-Heuristic Approach

2.1 General composite dispatching rules

In the machine scheduling field，dispatching rules are useful when one attempts to find a reasonably good solution in a relatively short time［22］.The most common dispatching rules are earliest release date first（ERD，first come first served rule in ALP）rule，earliest due date first（EDD）rule，minimum slack first（MS）rule，weighted shortest processing time first（WSPT）rule，and so on.The advantages include solving the problem quickly，ease of implementation，and optimal for particular cases.However，a single dispatching rule has limitations of being used in practice and resulting in unpredictably bad solutions because objectives and constraints in the real application could be more complicated.Composite dispatching rule（CDR）is a ranking expression that combines some basic dispatching rules，which could perform significantly better than a single dispatching rule［23-24］. Each basic rule in CDR has its scaling parameter that is chosen to scale the contribution of each basic rules properly.

For the total weighted tardiness minimization problem，the apparent tardiness cost（ATC）rule is a typical CDR.It is a combination of the WSPT rule and the MS rule.By this rule，jobs are scheduled one at a time according to the highest-ranking index

For the total weighted tardiness minimization problem with sequence-dependent set-ups，the ATC rule can be extended to the ATCS rule［24］，which is a combination of WSPT rule，MS rule，and shortest set-up time（SST）rule.

whereskjrepresents the jobkbefore the jobj，the average set-up time of the remaining jobs，andK2the scaling parameter as to set-up time.

For the total weighted tardiness minimization problem with sequence-dependent set-ups and future release times，the ATCS rule can be further extended to ATCSR rule［23］through introducing ERD rule.

whereK3is the scaling parameter.Such composite rule contains four basic rules—WSPT rule，MS rule，SST rule，and ERD rule.This ranking index establishes a one-to-one relationship between these four specific factors.

2.2 The proposed composite dispatching rules

As mentioned，ALP is similar to machine scheduling［25］.However，there are specific features of an ALP when compared with a machine scheduling problem.

Once an aircraft is landing on a runway，it is assumed that the job is completed.Such an assumption indicates that the processing time（runway occupied time，ROT）in ALP can be ignored due to the actual condition that WV separation is more prominent than ROT.The noted composite dispatching rules are mainly concerned with the objective of total weighted tardiness，whereas the objective of total penalty，i.e.，weighted earliness and tardiness，is taken into account in this paper.

Considering these differences，we propose a new rule—minimized penalty with due dates and setups（MPDS）.

The MPDS rule contains four basic rules—improved MS rule，SST rule，ERD rule，and Minimize Penalty rule，as indicated by the four terms in Eq.（22）.Furthermore，to obtain good results，the values of scaling parameters should be appropriate for the particular instance of the problem.

K1is related to the due date range factorR，and a study has suggested a guideline for selectingK1

where the estimated makespan can be

K2is related to the due date tightness factorτ

K3is related to the release date tightness

K4is mainly related to the incurred penalty and the number of aircraft

2.3 Heuristic and meta-heuristic algorithm

An efficient heuristic algorithm is developed firstly to tackle the ALP in this subsection.As mentioned in Section 1.2，we first determine the landing sequence based on the dispatching rule，single or composite. Then we optimize the landing times（Eqs.（11）—（18））by using CPLEX software.For a single dispatching rule，like EDD or ERD，it is quite easy.The corresponding heuristic algorithm（EDD_HA or ERD_HA）consists of two significant steps:Sorting and optimizing.For composite dispatching rule，the algorithm（MPDS_HA）is slightly more complicated.Algorithm 1 presents the pseudo-codes of MPDS_HA.

Algorithm 1:MPDS based Heuristic Algorithm(MPDS_HA)for ALP

1.Sett=0;C j=0;J={1,2,???,n};?j∈J

2.Calculate scaling parameters using Eqs.(23)—(26)

3.CalculateIMCDS(t,k)j,according to Eq.(22),j={1,2,…,n}andskj=0

4.Findj={j∈J|max[IMPDS(t,k)j]}and put it in the first place

5.SetC j=δj,t=C j,k=j

6.RemovejfromJ

7.WhileJ≠Φdo

8. CalculateIMPDS(t,k)j,according to Eq.(21),?j∈J

9. Findj={j∈J|max[IMPDS(t,k)j]}

10. UpdateC j=max(rj,C k+skj)

11. Updatet=C j

12. Updatek=j

13. RemovejfromJ

14.End While

15.Get the landing sequence and set it into Eq.(13)

16.Optimize sub-problem(Eqs.(11)—(18))using CPLEX

After setting the initial parameters（line 1），the first landing aircraft is obtained by determining scaling parameters（line 2），calculating ranking index（line 3），finding the highest one（line 4），and updating the decision time（line 5）.Then，remove this aircraft（line 6）to construct the remaining set of landing aircraft.Next，MPDS_HA executes the while loop（lines 7—13）for a nonempty remaining set of landing aircraft.Within the while loop，the landing sequence is scheduled once at a time，and the following are executed:Calculating ranking index（line 8），finding the highest（line 9），updating the SLT（line 10），updating the decision time（line 11），updating the scheduled aircraft（line 12）and removing the scheduled aircraft（line 13）.Then，the landing sequence is obtained and set into Eq.（13）（line 15）.Finally，the SLT is optimized by using CPLEX（line 16）.

These proposed algorithms are indeed efficient and easy to be implemented.However，we could not overlook the drawback of these algorithms，i.e.，the shortsightedness.On the one hand，the landing sequence is determined by the highest-ranking index.On the other hand，once the landing sequence is determined，it could not be changed.There will be a particular situation，in which several ranking indexes are very close to each other.Such a situation means there is a good chance that we have different optional landing sequences.Therefore，a new metaheuristic algorithm based on MPDS rule（MPDS_MHA）is developed to overcome the shortsightedness of Algorithm 1.Algorithm 2 presents the pseudo-codes of MPDS_MHA.

Algorithm 2:MPDS based Meta-heuristic Algorithm(MPDS_MHA)for ALP

1.Lines 1-6 of Algorithm 1t=0;C j=0;j,k={1,2,…,n};k≠j

2.WhileJ≠Φdo

3. CalculateIMPDS(t,k)j,according to Eq.(22),?j∈J

5. UpdateC j=max(rj,C k+skj)

6. Updatet=C j

7. Updatek=j

9. RemovejfromJ

10.End While

11.Get the initial landing sequence Seq0

12.Get the initial landing times and objective Obj0by solving sub-problem(Eqs.(11)—(18))

13.Get the initial solutionS0{Seq0,Obj0}

14.Construct the neighborhood structures(NS)by mergingN j∈J{j},N j{j}∩N j+1{j}≠?

15.LetKbe the number of NS

16.Seti=1

17.While(i≤K)do

18. Seq1←Generates a neighborhood of Seq0using NSi

19. Get the landing times and objective Obj1by solving sub-problem(Eqs.(11)—(18))

20. If Obj1＜Obj0then

21.S0{Seq0,Obj0}←S1{Seq1,Obj1}

22.i=1

23. Else

24.i=i+1

25. End If

26.End While

27.Return the best solution

The several initial steps of Algorithm 2 are the same as Algorithm 1. Next，MPDS_MHA executes the first while loop（lines 2—9）of calculating，sorting and updating to obtain the initial landing sequence.The specific step of MPDS_MHA lies in line 8，which generates the potential neighbors of each scheduled aircraft.At this step，αis a predefined parameter，which could affect the number of potential neighbors. For each scheduled aircraft，there will be at least one potential neighbor，and the adjacent scheduled aircraft may share the same potential neighbors.Then，the initial solution is obtained（lines 11—13）.Next，MPDS_MHA adopts a meta-heuristic framework.Within the meta-heuristic framework，the following steps are implemented.As shown in Fig.2，if the adjacent scheduled aircraft have some common neighbors.The neighborhood structures（NSs）are constructed by merging the potential neighbors.If the adjacent scheduled aircraft have totally different potential neighbors，NS is constructed accordingly（line 14）.After setting the number of NS（line 15），the main loop of the local search is executed（lines 17—26）.At each iteration，generate a neighborhood solution by using NSi（line 18），in which the roulette wheel selection is implemented to apply the insertion，reversion or swap operator.As shown in Fig.3，the insertion means getting two indexes randomly and making their position adjacent.The reversion means to invert the old sequence of the neighborhood.And the swap means to exchange the position of the two aircraft.Then，the optimized landing times and objective values are produced（line 19）.If the generated neighborhood solution（S1）is better than the so-far best solution（S0）（line 20），then replaceS0withS1（line 21）.Otherwise，increaseiby one（line 24）to call the next local search.MPDS_MHA will stop the search if the so-far optimum of thekneighborhood structure cannot be improved any further.

Fig.2 An example of neighborhood construction

Fig.3 Methods of neighborhood generation

3 Computational Results and Discussion

3.1 Computational scenario

The performance of the proposed method is evaluated using a set of benchmark instances taken from the OR library.Such instances are summarized in Table 2.Also，we split the benchmark instances into small scales involving 10—50 aircraft and large scales involving 100，200，and 500 aircraft.

The proposed algorithms were run on a PC with a 2.3 GHz Intel Core I5-6200U processor and 4 GB RAM.The corresponding MILP model of ALP was solved using CPLEX software（IBM ILOG CPLEX Optimization studio version 12.5.1）.

Table 2 Computational scenarios

3.2 Small scale instances

As mentioned in section 1.2，for solving the ALP，there exists a strategy of first establishing the landing sequence，then determining the SLT.Also，once the sequence is determined by using ERD，EDD or MPDS，the SLT can easily be calculated by Eq.（10）or further optimized through Eqs.（11）—（18），i.e.，by MPDS_HA.

Table 3 provides a comparison between different strategies（calculation or optimization）under different dispatching rules，in which the objective values are taken as performance，and only small-scale instances are considered.

From Table 3，we could find that:（1）The proposed MPDS rule is better than single dispatching rules；（2）the optimization strategy，i.e.，MPDS_HA，is far better than the calculation strategy；and（3）the MPDS_HA could obtain the optimal solutions for the small-scale instances，except Instance 8.

Table 3 Computational results of small scale instances

While looking into the details of cases，we identified several reasons for Instance 8 being difficult to obtain the optimal solution by MPDS_HA.The first reason is the short scheduled time window per aircraft in Instance 8.The scheduled time window per aircraft is the entire scheduled window divided by the total number of aircraft.We considered only Instances 1—5 and Instance 8，as the same WV separations were used in these cases.The average scheduled window of Instance 8 is around 20 s，which is much lower than the others（40—65 s），which leaves limited flexibility for resorting.The second reason is that the proposed MPDS rule does not always bring about the optimal landing sequence，which inevitably leads to the sub-optimal solution during the optimization by MPDS_HA.Because the MPDS rule only has a shortsighted vision，it determines one aircraft's position each round，as shown in Eq.（22）or line 9 of the Pseudo Codes of MPDS_HA.Therefore，we have developed MPDS_MHA by using meta-heuristic strategy，i.e.，to generate the potential sequences for local searching.

Fig.4 provides the scenarios and scheduling results of Instance 8，which consisted of earliest and latest landing time（black star line），TLTs（Target Landing Times，black box），SLTs obtained by CPLEX（black diamond），SLTs by MPDS_HA（black circle）and SLTs by MPDS_MHA（black triangle）withα=0.25.Fig.5 displays the deviations between the TLTs and the SLTs obtained from different methods.The objective value of Instance 8 by CPLEX，MPDS_HA，and MPDS_MHA are 1 950，2 230 and 1 950，respectively.

Fig.4 Scheduled results of Instance 8

Fig.5 Deviations between TLTs and SLTs of Instance 8

Table 4 illustrates all the results of Instance 8 by different methods.

As shown in Figs.4，5，most scheduled results are the same，while some are entirely different.However，by MPDS_HA，there are 21 aircraft whose SLTs are not sticking to the corresponding TLTs，while by CPLEX，21，and by MPDS_MHA，20. Furthermore，MPDS_MHA is more likely to schedule those aircraft with a lower penalty for early or late landing.The subsequence of the 23th—27th landing aircraft is a case in point.

By MPDS_HA，the subsequence is aircraft#26，#16，#25，#43，#35.

By CPLEX，the subsequence is aircraft#26，#25，#43，#35，#16.

By MPDS_MHA，the subsequence is aircraft#26，#25，#16，#43，#35.

And the penalties of aircraft#16，#25，#26，#35，#43 are 10，15，30，15，and 25 per second.From Fig.5，we could find that aircraft#16（penalty 10）is deviated from the TLT most by MPDS_MHA，while aircraft#31（penalty 15）is deviated from the TLT most by MPDS_HA.

Table 4 Objective value comparison of Instance 8

3.3 Large scale instances

3.3.1 Parameter analysis

Since scaling parameters play an essential role in the MPDS rule，the primary purpose of this subsection is to prove our parameter determination method（Eqs.（23）—（26））is as good as a grid search strategy，which is used in the machine scheduling［23］.

Take airland#9 as an example，the grids are

K1={1.0,2.5,4.0,4.5,5.0,5.5,6.0,7.5,10}，

K2={0.025,0.05,0.075,0.1,0.25,0.5,1,2.5,5,10},

K3={50,250,500,1 000},andK4=2 000，whileK1=4.13K2=0.03，K3=136 andK4=2 000 based on Eqs.（23）—（26）.

Fig.6 shows objective values with different scaling parameters.The minimum total penalty is 6 792，and the maximum is 8 073.Fig.7 illustrates the distribution of scheduled results with different scaling parameters for ALP#9.Nearly 97%of the scheduled results are less than 7 097.Meanwhile，6 841 is our objective value based on MPDS_HA for the scaling parameters.The conclusion could be drawn that tuning the scaling parameters can obtain a better result，but it is time-consuming，while our parameter determination method is a competent way.

Fig.6 Results with different scaling parameters for Instance 9

Fig.7 Distribution of results with different scaling parameters

3.3.2 Effectiveness of MPDS_MHA

In this section，the effectiveness of MPDS_MHA will be evaluated by large-scale instances.The results obtained with the proposed algorithms and other existing methods are shown in Table 5.

Table 5 also shows the percentage gap（G）for comparison regarding the best objective values.The percentage gap（G）is calculated as

where Obj is the best objective value obtained by different methods and Obj′is the best value so far.

From Table 5，we could find that MPDS_MHA is far better than MPDS_HA since the former one considers meta-heuristic strategy. In comparison to the other existing methods，MPDS_MHA is also a competitive and promising algorithm.

We take Instance 9 as an example to carry out the comparison study about the computational times，as shown in Table 6.The CPU time of MPDS_HA is 1.3 s，significantly shorter than those of the existing methods.The time-effectiveness of MPDS_HA is mostly attributed to the reduction of constraints in the mathematical optimization problem after the landing sequence is determined with the proposed composite dispatching rule，MPDS.Howev-er，MPDS_MHA needs more time，compared with MPDS_HA，to conduct the local search for finding the near-optimal solution.

Table 5 Objective value comparison of large-scale instances

Table 6 CPU time comparison of Instance 9

4 Conclusions

A new meta-heuristic approach，based on composite dispatching rule，is put forward in this paper to solve the aircraft landing problem of minimizing the total penalty.Such proposed composite dispatching rule，MPDS，could not only efficiently establish an initial landing sequence but also effectively provide the potential landing sequences by the ranking indexes，as shown in line 8 of Algorithm 2.Thereupon，the proposed approach，MPDS_MHA，could find a good solution within a reasonable time after the local search.

Our proposed methods are evaluated by using a set of benchmark instances taken from the OR library. The computational results show that the MPSD_HA method could get a generally good result in a short time and the MPSD_MHA method could obtain the optimal result in a little bit longer time.Therefore，the combination of CDR and metaheuristic strategy is an effective way to solve the ALP.

Future work is worth exploring in the following areas—applying the proposed method to solve multirunway ALP and ALP with arrival time uncertainty，developing a new composite dispatching rule for multi-objective ALP，and tackling the integrated arrival and departure scheduling problem based on our approach.