Optimization Method for Departure Flight Scheduling Problem Based on Genetic Algorithm

Zhang Haifeng（张海峰），Hu Minghua（胡明华）

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

Optimization Method for Departure Flight Scheduling Problem Based on Genetic Algorithm

Zhang Haifeng（张海峰）*，Hu Minghua（胡明华）

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

Except for the bad weather or other uncontrollable reasons，a reasonable queue of departure and arrival flights is one of the important methods to reduce the delay on busy airports.Here focusing on the Pareto optimization of departure flights，the take-off sequencing is taken as a single machine scheduling problem with two objective functions，i.e.，the minimum of total weighted delayed number of departure flights and the latest delay time of delayed flight.And the integer programming model is established and solved by multi-objective genetic algorithm. The simulation results show that the method can obtain the better goal，and provide a variety of options for controllers considering the scene situation，thus improving the flexibility and effectivity of flight plan.

air transportation；pareto optimization；genetic algorithm；scheduling departure of flight

0 Introduction

It is estimated in the“Twelfth Five-Year Plan”of civil aviation development that normal rates of flights will be higher than 80%.In 2011，China Civil Aviation scheduled flight punctuality rate was 77.2%，and the flight punctuality rate become a hot issue of social concerns.The factors impacting flight punctuality rate include airline＇s own reason，flow control，weather and other reasons.The core issue for improving flights＇punctuality rate is how to arrange reasonable arrival and departure sequences of the flights.It requires the air traffic management to minimize the delay of the flights with actual airspace capacity limitation and runway safety interval constraint conditions，so as to reduce the loss for airlines and customers and to improve flights punctuality rate［1］.

Collaborative decision making（CDM）systems have been used by several regional air traffic management bureaus to reduce the delay in some airports since 2012，e.g.Guangzhou airport. Since current CDM system can only use simple rules for departure flights sequencing，the experience of controller is still indispensible.Therefore，the flight scheduling in China is mainly directed based on experiences of air traffic controllers with high labor intensity，especially when the delay of flight occurring in a large area.The usual sequence strategy involves：（1）First come first served，i.e.scheduling the flights by departure preparation time；（2）Scheduling the flights by urgency of departures，i.e.scheduling by the ticket times of the flights，earlier time earlier departed.

Currently，the operating mode of runway in some airports is one for departure and one for arrival，i.e.one runway is dedicated for take-off and one runway for landing.Therefore，the whole system can be regarded as separate runway systems for both runways.This paper focuses on discussing optimization of take-off sequence for the flights.

Li et al.［2］used moving or controlled dynamic ant colony algorithm optimization to study arrival sequencing and scheduling issues for theflights in dynamic environment.Chen et al.［3］built a mixed integer programming model for arrival sequencing and scheduling issues，and raised heuristic algorithm of priority concept.Shi et al.［4］investigated dynamic sequencing model，optimization method and sorting system designing for the flights arriving and departing the terminal area with multi-runways.In the researches mentioned above，the target value of flight departure is single.However，from perspective of airlines＇service quality，the objective function of flight departure is usually multi-objects.Popular objective is to keep the minimum of total take-off delays of the flights.When several flights are waiting for take-off，with the requirements of this objective function，reasonable strategy is to keep some flights delay and thus to enable other flights can depart on time.But at the same time，the waiting time for the delayed flights will be very long，causing serious impact on the service quality once the flight was delayed for too long time.Therefore，scheduling the departure sequence for the flights can be regarded as a machine scheduling problem with two objective functions.

（1）The minimum of total number of flight take-off delays：give a certain weight to each flight，when it has to be delayed，and start adjusting the flights with low weight.The weight can be confirmed by referring to the numbers of passengers in the flights，i.e.，the greater the number of passengers，the higher the priority of the weight，and vice versa.

（2）The minimum of latest time of delayed flights：it is because that when several flights have the conflict of delayed time，the lengths of their delayed time needs to be compared for making choice.

In research of multi-objective issues，Smiths first raised the Pareto optimization strategy［5］，and looked for more balanced solution among efficient solutions.Setting double objective issues as f and g，the efficient solution of the Pareto optimization is defined as：no feasible solution can meet the following conditions：f（π＇）≤f（π）and g（π＇）≤g（π）.The Pareto optimization can find as many efficient solutions as possible on the basis of meeting the above conditions，and easily select the applicable solution in most situations.This paper uses the Pareto optimization to find the solution.

When f and g are the minimizing optimization objectives，according to the above definition，the efficient solution area is shown by the bold line in Fig.1.But the real efficient solution is unknown in actual application of the algorithm. Hence，one can only solve the approximation area E（P）（shown in the dotted line in Fig.1）of the efficient solutions as an alternative objective.

Fig.1 Approximation of effective solutions

1 Mathematic Models

1.1 Departure process

Taking the flights’departure process as an example（Fig 2），the flight receives instructions of being ready for take-off from control tower—taxis from apron to runway—start take-off—enter into complete route of airport＇s airspace sector—start departure from the appointed place. For air traffic controller who faces the complex decision in the limitation of capacity of runway，the input data include all basic information of departure flights，such as ticket time，the importance of flight，time required for take off，and the output is the sequence of departing flights.Then the number and delay time of delayed flights are known.

1.2 Model introduction

From the perspective of scheduling theory，one can regard the time when the flight receives take-off instruction to be ready for entering the runway as the release time，and the departure time on the flight ticket as due time.If the actual take-off time of the flight is later than the due time，the flight will be delayed，which should be avoided as much as possible in actual situation. From the start to the end of take-offs after finishing the waiting time on the runaway，such period can be regarded as the processing time，and the detailed value can be calculated by statistics data or overall consideration of flying distance and speed.

Fig.2 Process of flight＇s departure

It is assumed that there are n arrived flights waiting for take-off，and only one flight can take off from the runway at the same time；earliest time，due time and latest time for each flight are different and can be confirmed when the time is 0.

（1）Definition of symbols

j Flight＇s serial number，j=1，…，n

i The i th location in the take-off sequence，

i=1，…，n

（2）Constants

rjEarliest time the flight j can take off

djDue time for flight j

wjWeight of flight j

pjTime required for the flight j to take off

M A big integer

（3）Decision variables

SiActual start take-off time for the i th sequence flight

LiDelay time of the i th sequence flight，if no delay，Li=0

xijxij=1 means the flight j is arranged to take off at sequence i.

UiUi=1 means flight arranged for sequence i is delayed

（4）Objective function and constraints

This paper is to solve the so-called Pareto optimization objectives，and the two objective functions are as follows

The minimum of total flight weighted number ofdelay

The minimum of the longest delay time of the delayed flights

Constraint conditions

Constraints（1），（2）ensure the corresponding relationship between flight j and sequence i，constraints（3），（4）ensure the starting take-off time for the flight arranged at sequence i is later than the earliest take-off time and the actual ending take-off time of previous flight，and constraint（5）ensures Ui=1 if the actual take-off time of the flight at sequence i，or Ui=0.Constraints（6）and（7）ensure Li=0 if there is no delay，or Li=0 should be equal to the difference between the actual take-off time and the latest take-off time of the flight at sequence i.Solve the above model and get xij，as well as a sequenceπ discribing the original issue.

1.3 Explanation

On the basis of the above model，if any new situation comes out，the air traffic controller only needs to update the above estimate value and input parameters according to the latest situation，thus providing intuitive and timely initial plan for further decision.For example，after the bad weather occurs，all flights cannot depart from the airport.When the weather permits，the information of flights will be renewed，that is，the earliest time the flight，due time，etc.After all input data replacement，the new solution will be calculated by the model.For a specific flight，the expected departing time can be estimated and announced to customers，the good service quality will be accepted by customers.

2 Multi-objective Optimization

According to the scheduling theory，when earliest take-off time of all flights is 0，the minimum number of total delayed departure flights can obtain the optimal solution within polynomial time，and the minimum of the longest delayed time is NP-complete［6］.If the earliest take-off time of all flights are different，the above two issues are all NP-hard issue［7］.

As both the objective functions f and g in this paper are NP-hard，it is difficult for traditional method of operational research to gain satisfied results.So currently when solving the issue with single machine and two objectives，the most commonly used method is artificial intelligence，including genetic algorithm［8］，Tabu search，simulated annealing，etc.

Genetic algorithm is one useful tool to realize the simulation of biological system evolution process via crossover and mutation between chromosomes and the evalution via searching space multiple solutions［9-14］，so as to find the overall optimal solution for the issue.This method has the impliciting concurrency and overall solution space searching capacity.

2.1 Coding

The solution for the issue can be expressed by sequence number of each flight，and the integer coding is expressed in Fig.3，where ijrepresents that the flight i is scheduled at the location ij.

Fig.3 Chromosome coding

2.2 Fitness value

Fitness value is used to decide the performance of the solution for the population during the interative process of the algorithm.There are two methods.One is to consider both two objective functions f and g.In order to find out E（P）to form the appropriate area of the effective solution，it needs to share fitness value information［15-16］between these two objective functions. Firstly calculate the Euclidean distance between objective space（0，1）after standardization of two solutionsπ1andπ2，secondly calculate the niche count for solutionπ∈E（P），based on which，calculate the final fitness value.The other is to search along the boundary space of current known effective solution area without consideration of sharing fitted value information［11］，and adopt crowding distance as the evaluation to describe the distance between the points on the boundary and other neighboring points，bigger value means more uniform distribution of the solution，the more possibility it should be selected.

Step 1 Sort the current R effective solutions according to objective functions f and g respectively and set them as f1，f2，…，fRand g1，g2，…，gR，corresponding to the points of the boundary j=1，…，R.

Step 2 Set y［k，f］and y［k，g］respectively represent sorting of current R effective solutionsπkaccording to objective functions f and g，if cd1（y［1，f］）=∞，cd1（y［1，g］）=∞，cd1（y［R，f］）=∞and cd1（y［R，g］）=∞，for others＇k=2，…，R-1，

there will be

where fmax，gmaxand fmin，gminare the maximum values and minimum values of the objective functions f and g respectively.

Step 3 After the above results are calculated，the final crowding distance will be

where cd（πk）is taken as the fitness value of the solution.But for single objective issue，it can directly adopt the f or g value as the fitness value.

2.3 Population initialization and crossover

According to the above coding principle，randomly generating a set of 1 to n arrangement to form the initial solutions，repeating this process，and the initial solution set with numbers of P can be obtained.

Crossover operator will form matching library of crossover operation via the parity individuals in father generation.Identify a crossover location according to crossover probability Pc（0＜Pc＜1），and then change the gene string after that location.This article uses one-point crossover to replace the coding after the crossover point.In order to ensure the feasibility of the solution，coding after the crossover point in father generation one will be sorted by sequence in father generation two，similarly，coding in father generation two will be sorted by sequence in father generation one.In Fig.4，｛1，2，4｝in the Father generation 1 are sorted as｛4，2，1｝per sequence in the Father generation 2，similarly，｛5，1，3｝in the Father generation two are changed to be｛5，3，1｝.

Fig.4 Crossover

2.4 Mutation

Mutation operator is used to prevent the population from early convergence to local optimal solution，and converse the code to other value after selecting mutation location.Moreover，in order to keep the feasibility of the solution，it needs to converse the code at original location to the code at mutation location with the probability val-ue of Pm（0＜Pm＜1）（Fig.5）.

Fig.5 Mutation

2.5 Selection and termination conditions

Combine the definition of fitness value and use the probability of fitness value for individuals to decide whether it participates in crossover or mutation processes，and select the probability Ps（0＜Ps＜1）.Each time select the effective solution boundary after combining the father generation and offspring sets，if the number of current effective solution is less than P，then calculate all crowding distance of all current effective solutions successively，and list them in a descending order per the distance.Select successively until the current population quantity reaches P.

The termination conditions are as follows：（1）Iterations are completed；（2）No change happens in fitted values between continuous several generations.

3 Numerical Examples Validation

The following is to validate the function of genetic algorithm for multi-objective optimization issue when the number of take-off flight is m= 40，80，100 respectively.Given time pj，the flight j take-off time meets the average distribution of［1，100］，the weight wjis the average distribution of［1，5］，and the earliest take-off time rjmeets the average distribution of［1，MS］. Time window（dj-rj）meets the average distribution between［（1-T-R/2）×MS，（1-T+R/ 2）×MS］，where MS is the sum of pjfor all the flights，and the value ranges of T and R are 0.2，0.4，0.6 and 0.4，0.6，0.8，respectively.Parameters for the genetic algorithm are as follows：population size P=100，selection probability Ps=0.1，crossover probability Pc=0.6，mutation probability Pm=0.1.Five cases for each parameter group are calculated.

In order to evaluate multi-objective genetic algorithm，（The optimal value obtained from single objective genetic algorithm sums f and g is also added into the effective solution boundary）this paper compares the results sorting by first come first serve（FCFS），departure urgency（smaller Δ=dj-rj，more urgency）with（fΔ，gΔ）.In Fig.2，|E（P）|avgis the average value for numbers of effective solutions in E（P），and bigger value means more solutions.The results show that most of the calculations can find out 5—8 effective solutions to select based on site conditions（Table 1）.（favg-fmin）/fminshows the difference between average value of current effective solutions at objective value f and single object optimal solution obtained from genetic algorithm fmin，and the smaller distance indicates the better result of the effective solution if taking f as the standard.In addition，the definition of（gavggmin）/gminis similar.favg/fFCFSshows the comparison between the average value of the effective solution at objective value f and the result from FCFS.Comparing with the single objective by the genetic algorithm，the results show that the average performance of the proposed algorithm is more stable，which is better than the traditional heuristic method.

Fig.6 shows the effective solution boundaries in a group of examples under different m，T，R.

4 Conclusions

The frequent flight delay in busy airports is literally unpleasant.This paper models a take-off scheduling problem as a single machine scheduling problem with two objective functions（the minimum of total amount of delayed flights with weight and the minimum of latest delay time）. Each flight is with different preparation time，take-off time and departure time.In order to put the Perato optimization solution into practice，the multi-objective genetic algorithm is used to calculate the effective solutions set，and the calculation results of experimental case show that the method can gain a better objective value in comparison with the traditional heuristic method and also canprovide a relatively intuitive decision support for the controller，who can select the one that mostly meets the actual situation from the effective solutions set，thus effectively reducing the delay issue of flight caused by unreasonable departure flight＇s sequence and improving the level of aviation service.

Table 1 Performance comparison of the proposed algorithms

Fig.6 Result of effective solutions

Acknowledgements

This work was supported by the National Natural Science Foundation of China（No.61079013）and the Natural Science Fund Project in Jiangsu Province（No. BK2011737）.

［1］ Brinton C，Provan C，Lent S，et al.Collaborativedeparture queue management［C］∥Proceedings of 9th USA/Europe Air Traffic Management Research and Development Seminar.Berlin，Germany：［s. n.］，2011.

［2］ Li Guanbin，Zhan Zhihui，Zhang Jun.Ant colony algorithm for arrival sequencing and scheduling optimization［J］.Computer Engineering and Design，2009，30（17）：4047-4052.

［3］ Chen Weiwei，Geng Rui，Cui Deguang.Optimization of sequencing and scheduling for arrival aircrafts in approach area［J］.Journal of Tsinghua University：Science and Technology，2006，46（1）：157-160.

［4］ Shi Saifeng.The research on terminal aircraft sorting system in Guangzhou［D］.Nanjing University of Aeronautics and Astronautics，2011.

［5］ Iskandar B P，Murthy D N P，Jack N.A new repairreplace strategy for items sold with a two-dimensional warranty［J］.Comput Oper Res，2005，32（3）：669-682.

［6］ Smith W E.Various optimizers for single stage production［J］.Naval Research Logistics Quarterly，1956，3（1）：7-17.

［7］ Du J，Leung T.Minimizing total tardiness on one machine is NP-hard［J］.Mathematics of Operations Research，1990，15（3）：483-491.

［8］ Bae S W，Park J W，Clarke J P.Modified mixed integer linear program for airport departure scheduling［C］∥AIAA Guidance，Navigation，and Control Conference 2013.Boston，USA：AIAA，2013.

［9］ Ferreira D M，Rosa L P，Ribeiro V F，et al.Genetic algorithms and game theory for airport departure decision making：GeDMAN and CoDMAN［M］. Knowledge Management in Organizations：Springer International Publishing，2014：3-14.

［10］Weng M，Sedani M.Schedule one machine to minimize early/tardy penalty by tabu search［C］∥Proceedings of the Annual IIE Research Conference.Orlando，FL：［s.n.］，2002.

［11］Loukil T，Teghem J，Tuyttens D.Solving multi-objective production scheduling problems using metaheuristics［J］.European Journal of Operational Research，2005，161（1）：42-61.

［12］Deb K，Prata P A，Agarwal S，et al.A fast and elitist multi-objective genetic algorithm：NSGA-II［J］. IEEE Transactions on Evolutionary Computation，2002，6（2）：182-197.

［13］Jin Feng，Song Shiji，Wu Cheng.Genetic algorithm based on NDP with application to job shop scheduling［J］.Journal of Tsinghua University：Science and Technology，2006，46（4）：488-491.

［14］Yin J N，Hu M H，Zhang H H，et al.Optimization approach for collaborative operating modes of multirunway systems［J］.Acta Aeronautica et Astronautica Sinica，2014，35（3）：795-806.

［15］Lu H，Yen G G.Rank-density-based multi-objective genetic algorithm and benchmark test function study［J］.IEEE Transactions on Evolutionary Computation，2003，7（4）：325-343.

［16］Yen G G，Lu H.Dynamic multi-objective evolutionary algorithm：adaptive cell-based rank and density estimation［J］.IEEE Transactions on Evolutionary Computation，2003，7（3）：253-274.

（Executive editor：Zhang Tong）

O221.6，U8 Document code：A Article ID：1005-1120（2015）04-0477-08

*Corresponding author：Zhang Haifeng，Senior Engineer，E-mail：zhanghf0606@163.com.

How to cite this article：Zhang Haifeng，Hu Minghua.Optimization method for departure flight scheduling problem based on genetic algorithm［J］.Trans.Nanjing U.Aero.Astro.，2015，32（4）：477-484.

http：//dx.doi.org/10.16356/j.1005-1120.2015.04.477

（Received 6 June 2014；revised 5 September 2014；accepted 30 September 2014）