Multi-objective Collaborative Optimization for Scheduling Aircraft Landing on Closely Spaced Parallel Runways Based on

Genetic Algorithms

Nanjing 211106, P.R.China

?

Multi-objective Collaborative Optimization for Scheduling Aircraft Landing on Closely Spaced Parallel Runways Based on

Genetic Algorithms

ZhangShuqin*,JiangYu,XiaHongshan

College of Civil Aviation, Nanjing University of Aeronautics and Astronautics,

Nanjing 211106, P.R.China

(Received 22 December 2015; revised 12 March 2016; accepted 19 March 2016)

A scheduling model of closely spaced parallel runways for arrival aircraft was proposed, with multi-objections of the minimum flight delay cost, the maximum airport capacity, the minimum workload of air traffic controller and the maximum fairness of airlines′ scheduling. The time interval between two runways and changes of aircraft landing order were taken as the constraints. Genetic algorithm was used to solve the model, and the model constrained unit delay cost of the aircraft with multiple flight tasks to reduce its delay influence range. Each objective function value or the fitness of particle unsatisfied the constrain condition would be punished. Finally, one domestic airport hub was introduced to verify the algorithm and the model. The results showed that the genetic algorithm presented strong convergence and timeliness for solving constraint multi-objective aircraft landing problem on closely spaced parallel runways, and the optimization results were better than that of actual scheduling.

air transportation; runway scheduling; closely spaced parallel runways; genetic algorithm; multi-objections

0 Introduction

The growth rate of airport capacity has been lagged behind the increasing aviation demand. Some busy airports expanded runways to tackle this problem. Compared with other configurations, closely spaced parallel runways (CSPR), i.e., runways spaced less than 762 m, could better improve the capacity of runway system, as well as hold more flexibility for aircraft landing[1]. Therefore, the CSPR′s expansion has become the first choice to alleviate the capacity-demand contradiction. However, inadequate research on CSPR and the stronger impact of the wake flow between aircraft on CSPR renders scheduling aircraft on CSPR a great challenge. So far, related studies covered three aspects as follows:

(1) CSPR′s capacity: Capacity calculation model[2]and evaluation model[3], method for enhancing capacity[4-5]and the relationship between runways operation modes and the theoretical capacity[6].

(2) Approach procedure to CSPR: Hammer et al. and Eftek et al. proposed paired approach procedures[7-8]; Domino et al. analyzed the paired approach procedure′s feasibility[9]and Sun et al. investigated its collision risk[10]; and Mundra et al. analyzed the paired approach procedure′s advantages and the required hardware[11].

(3) Influence of wake turbulence and its countermeasures: Rad[12]developed a concept of dynamic separations using wake vortex predictions, in order to reduce the wake effects. Rossow et al.[13]analyzed the propagation mechanism of the wake flow from a dynamic view and proposed a method to evaluate the influence of wake turbulence; Tian et al.[1]studied the time intervals of aircraft landing on CSPR when the operational characteristic of wake turbulence was the worst.

However, the research on CSPR had two problems:

(1) Static state. Runway capacity, approach mode and the influence of wake turbulence were confined to theoretical research. Therefore, the research results could not be directly applied to practical scheduling.

(2) One-sidedness. Almost all researchers confined to study a part of the factors influencing runway scheduling. However, practical runway scheduling was a complex optimization problem and it was affected by various factors.

Many studies, domestic and abroad, on aircraft arrival sequencing problems, have accomplished both theoretically and practically. But those works mainly focused on how to sequence the landing aircraft[14-16]and improve its efficiency[17-18], without studying multi-objective optimization problem.

Therefore, a CSPR scheduling model was proposed to improve the operating efficiency of CSPR, and therefore to ease the demand-supply contradiction. The genetic algorithm was introduced to solve the model. The model was designed to obtain four objectives: the minimum delay cost, the maximum runway capacity, the best fairness among airlines and the minimum workload of air traffic controllers.

1 Modeling

Aircraft landing is defined as assigning landing runway and landing time to certain aircraft belonging to some airlines at one time window. The goal of aircraft landing is to balance the demand and the supply, and to minimize the operation cost.Scheduling is completed coordinately by three parts: airlines, airport and air traffic control department. Safety holds the highest priority during scheduling; economy the second, and fairness the third. Targeting at the three goals, airports should serve as many aircraft as possible within limited time span while increasing aviation business charges. Throughout this procedure, air traffic controllers would face a critical challenge, because the operating safety of airport terminal can be improved by reducing the workload of controllers while the number of aircraft landing on the runways is increased. Therefore, we comprehensively considered the interests among the departments when scheduling aircraft.

To simplify the problem, we assumed that: Firstly, aircraft parking time was within 2 h and the serving time of departure lounge bridges was within 1 h. Security charge of the cargo was zero. Secondly, runway occupying time of all aircraft was 45 s. Finally, the basic information of the aircraft was given.

1.1 Objective functions

The flights here are divided into two kinds: multi-tasking flights and single-tasking flights. The aircraft of the former will have other missions in 1 h. So, the minimum delay cost Z1is given as

(1)

whereNis the number of landing aircraft; Cfithe delay cost of flight fi, which is related to its unit time delay cost cfiand delay time; ε=0.5 the coefficient of super-liner growth. tfi,Tfi,Lfiand Efiindicate the actual landing time, the target landing time, the latest landing time and the earliest landing time, respectively. If the aircraft of flight fihas only one fly mission at the airport, the flight is defined as a single tasking flight and φfi=1; otherwise the flight is multi-tasking flight and φfi=0.λfiis the penalty coefficient of the unit time delay cost of multi-tasking flight and is obtained by

(2)

wherecafiis the unit time delay cost of aircraft executing flightfi.

Runway capacityZ2is defined as the number of flights landing on the runway within 1 h. So, the maximum runway capacity is given by

(3)

The change number of landing order is used to measure the workload of air traffic controllersZ3here, so the minimum workload is given by

(4)

The best fairness is given by

(5)

whereZ4represents the fairness.XaandYaare the proportion of delay cost of flights and the proportion of aviation business charges belonging to airlinea, and they are described as

(6)

(7)

whereFis a set of flights andFaa set of aircraft belonging to airlinea;Uathe aviation business charges of airline andAa set of airlines,a∈A.

1.2 Constraint formulations

Efi≤tfi≤Lfi

(8)

(9)

Eq.(8) illustrates constrains for all flights landing time, and Eq.(9) the constraints of each flight with only one runway.Ris a set of runways. If flightfilands on runwayr,ξfir=1; otherwiseξfir=0.

The aircraft here are divided into three types according to the strength of their wake flow: Heavy (H), Middle (M) and Light (L). The landing time interval between the leading aircraft and the trailing is not less than the minimum time interval, and also not less than runway occupying time. The constraint is given by

(10)

whereS(fi,fj)represents the separation time between flightsfiandfjon the same runway ands(fi,fj)the separation time between flightsfiandfjon different runway. If flightsfiandfjland on the same runway,σ(fi,fj)=1， otherwiseσ(fi,fj)=0. If flightfilands on the runway afterfj,d(fi,fj)=1, otherwised(fi,fj)=0.Mis a great positive number.

The minimum time intervals between two aircrafts landing on the same runway are shown in Table 1.

Table 1 Minimum separation times between two aircraft on the same runway s

The minimum time intervals between two aircraft landing on different runways are obtained through the relationship between the long term planning capacity of single runway and that of closely spaced parallel runways, shown as Table 2.

Table 2 Minimum separation times between two aircraft on different runway s

Actual runway capacity is not larger than the ultimate capacity, and it is constrained as

Z2≤V

(11)

whereVis the ultimate capacity of runways.

Eq.(12) demonstrated the change number of aircraft landing order

(12)

(13)

where Reset is the maximum change value of landing order.

2 Genetic Algorithm

2.1 Double chromosome encoding

Each chromosome consists of two chromatids: one chromatid encodes the landing time, and the other the landing runway, as shown in Fig. 1.

Fig.1 Double chromosome coding

2.2 Weighted average method

The weighted average method is divided into two kinds: one is punishing each objective function value, and the other is punishing the fitness. The former is simply called SFWM, and the latter is GFWM. The processes are shown as follows:

(1) The process of SFWM

① Calculate each objective function value, and punish each value of the particle violating the constraints. For example, if particleekviolates the constraints, and the number ism, each valueziwill be set intozi+m*(fix(log10zi)+1), where fix(log10zi) represents the magnitude ofzi.

② Normalize the objective function values according to the mapminmax function of MATLAB, and the fitness is equal to the weighted sum of all normalized objective function values.

(2) The process of GFWM

① Calculate each objective function value and normalize each one.

② Assign the weighted sum of the normalized values to the fitness. If the particle violates the constraints, then punish its fitness.

2.3 Operating steps of genetic algorithm

Step 1 Population initialization: Create matrix P one column of full rank to ensure the diversity of initial population. The row is equal to 2N, and the column isn, wherenis the population size.

Step 2 Calculate the fitness and assign the value of matrix P to matrix P′.

Step 3 Selection: Sort all particles of initial population in descending order of their fitness values, and the top 80% particles are chosen as the next generation individuals candidate and assigned to matrix O.

Step 4 Crossover: Assign the matrix P′ to P″. Randomly generate one arrayW=w1w2…wi…w2N. The crossover process is operated as follows:

(1) Ifwi=1, index= P′(i, k), P′(i,k)= P′(i,n+1-k) and P′(i,n+1-k)=index.

(2) Ifwi=0, corresponding position values of the mating particles are not changed.

Step 5 Mutation: Randomly generate one number, and the mutation process is operated as:

(1) If the number is less than the mutation probability, generate one positive integerlbetween 0 and 2N.

① If the positive integerlis odd, randomly generate one integerxbetween -30 and 30 and assign it to P″(l,k).

② If the positive integerlis even, P″(l,k) is equal to its opposite.

(2) If the number is not less than the mutation probability, do not perform mutation operation.

Step 6 Update population: The matrix Q is equal to the combination of matrix O,P′ and P″. Firstly, delete the same column of matrix Q to protect the diversity of the population, and assign the remaining column to matrix Q′. Secondly, calculate the fitness of matrix Q′ and sort it in descending order. Finally, select the topnparticles and assign them to matrix P.

Step 7 Stop and output the optimal solution if the maximum generation number is achieved. Otherwise, go to Step 2.

3 Results

The genetic algorithms presented above were implemented in MATLAB on a 3.40 GHz PC with 8 192 MB memory. The parameters of the simulation experiment were set as:n=100, Reset=3; the maximum iterative algebra was 100 and the mutation probability was equal to 0.01. The weight values of each objective function were equal to 0.4, 0.3, 0.15 and 0.15, respectively. We took one hub airport as an example to analyze the model, and some information of the flights were shown in Table 3.

Table 3 Sample data of flights

Fig.2 illustrates all the objective function values obtained by three kinds of algorithms, where ″AS″ is the abbreviation for actual scheduling of the airport. Taking the values of AS as the reference, the percentage increase of the objective function value is shown in the secondary vertical axis of Fig.2.

Fig.2 Objective values obtained by three different methods

Fig. 2 indicates that delay cost of genetic algorithm is significantly less than that of AS, and runway capacity of the former is obviously improved. In particular, runway capacity of SFWM is nearly 2.5 times of that of AS. The reduction of delay cost is beneficial to airline′s operation. The improvement of runway capacity can not only increase airport revenue, but also improve the operating efficiency of runway surface and the safety of air transportation. The fairness of the two methods was increased by 77.39% and 84.29%, respectively. The increase of the fairness can weaken monopoly of some airlines to promote harmonious development of aviation transportation market. There were 39 aircrafts waiting for landing within the scheduling time window. If the change number of landing order of all aircraft was the maximum, i.e., 3, the total change number would be equal to 117. Fig. 2 shows that AS is equal to 268. So the scheme of AS was not suitable to the model here. However, the schemes obtained by the two kinds of genetic algorithm met Eq.(12) in section 1.3.Table 4 shows the objective function values in different cases.

Table 4 Results in different simulation conditions

The following conclusions can be summarized from Table 4:

(1) WhenZ1is optimal, i.e.: the value ofZ1is the minimum, the delay cost is the minimum. However, runway capacity is the minimum, and the value ofZ4of SFWM is the maximum, i.e., the fairness of scheduling is the worst. On the contrary, that of GFWM is the minimum, i.e., the fairness was the best.

(2) When runway capacity is the maximum, the value ofZ3of SFWM is also optimal. However, delay cost is the maximum, and the second method has the maximum workload and delay cost.

(3) When the value ofZ3is the minimum, it represents the workload is the minimum. The first method also has the optimalZ2. The second method has the minimum runway capacity and the worst fairness.

(4) WhenZ4is optimal, it represents the fairness is the best. Delay cost of the second method is the minimum. However, two methods have the minimum runway capacity. And the workload of first method is the maximum.

The conclusions presented above indicate an almost negative correlation between delay cost and runway capacity.

According to the three evaluation grades: excellent(ex), average(av) and poor(po), the data of Table 4 can be translated into those in Table 5.

Table 5 Evaluation grades from Table 4

The three evaluation grades were respectively assigned to 3, 2 and 1, and thus the scores of two methods are shown in Table 6.

Table 6 Evaluation scores of the scheme

Some conclusions can be drawn from Table 6: Firstly, the comprehensive score of SFWM is higher whenZ2andZ3are optimal. A higher score indicates the scheme is more suitable for putting into practice. Secondly, the comprehensive scores of GFWM is higher whenZ1andZ4are optimal. Therefore, decision makers can select the appropriate scheduling scheme according to different scheduling environment.

The convergence was an effective medium to test intelligent algorithm, and the variation of fitness values could excellently reflect it, which are shown in Figs. 3, 4.

Fig.3 Fitness values of SFWM in each generation

Fig.4 Fitness values of GFWM in each generation

Figs.3,4 indicate that the two kinds of genetic algorithms both have excellent convergence with declining fitness. In addition, the convergence of the latter is better than that of the first one, because its curve becomes more smooth.

Program running time is a standard to measure the efficiency of the algorithm. Parts of program running times are shown in Fig. 5.

Fig.5 Running time of the program

Fig.5 shows that the running time of the program of SFWM was shorter than that of GFWM. The average running time of SFWM was equal to 42.9 s, and it was 2.2 s shorter than that of GFWM. The shorter the running time is, the more conductive putting into practice and improving the dynamics of flight scheduling is.

4 Conclusions

We transformed the minimum time intervals between two aircrafts landing on the same runway into those on different runways, then the model with multi-objections for aircraft landing on CSPR was proposed. The delay cost of multi-tasking flights was punished to weaken the influence on the next task. Finally, two kinds of penalty mechanisms were used to deal with multi-objective functions, and the following conclusions were summarized from the simulation.

(1) The solution of genetic algorithm is more outstanding than that of AS.

(2) Genetic algorithm based on SFWM is more suitable to solve the model than the other one.

(3) Genetic algorithm has strong convergence, and the program running time is shorter. So it has a good practical value.

However, some relevant parameters of genetic algorithm are mainly determined through the experimental simulation. It needs to be studied further.

[1] TIAN Yong, SUN Jia, WAN Lili, et al. Separation determining method of closely spaced parallel runways [J]. Journal of Traffic and Transportation Engineering, 2013, 13(1):70-76. (in Chinese)

[2] TAO mei, NIE Rutu, ZHAO Weijing. Capacity of closely-spaced parallel runways using dependent approach procedures [J]. Journal of Transportation Systems Engineering and Information Technology, 2014, 6(14): 182-193.(in Chinese)

[3] PENG Y, WEI G, JUN Q S. Capacity analysis for parallel runway through agent-based simulation [J]. Mathematical Problems in Engineering, 2013.

[4] JANIC M. Steeper approach procedure for increasing ultimate capacity of closely spaced parallel runways [J]. Transportation Research Record: Journal of the Transportation Research Board, 2015:81-89.

[5] GUO H Q, ZHU J F. Calculation models of capacity and delay for closely spaced parallel runway [J]. Journal of Traffic and Transportation Engineering, 2008, 4: 10-16.

[6] GU Zhengbing. Study on instrument operation modes for closely spaced parallel runways of HONG-QIAO airport [J].Journal of Civil Aviation University of China, 2010, 28(5): 21-24. (in Chinese)

[7] HAMMER J B. Case study of paired approach procedure to closely spaced parallel runways [J]. Air Traffic Control Quarterly, 2000, 8(3):223-252.

[8] EFTEK ARI R, HAMMER J B, HAVENS D A, et al. Feasibility analyses for paired approach procedures for closely spaced parallel runways[C]∥IEEE Integrated Communications, Navigation and Surveillance Conference (ICNS), 2011. Venice: IEEE, 2011:1-14.

[9] DOMINO D, TUOMEY D, STASSEN H P, et al. Paired approaches to closely spaced runways: Results of pilot and ATC simulation[C]//Digital Avionics Systems Conference (DASC), 2014 IEEE/AIAA 33rd.[S.l.]: IEEE, 2014: 1B2-1-1B2-15.

[10]SUN Jia, TIAN Yong. Collision risk analysis of closely spaced parallel runways under parallel dependent approach procedure[J]. Journal of Harbin University of Commerce (Natural Sciences Edition), 2014, 30(2):241-245. (in Chinese)

[11]MUNDRA A D, COOPER W W, SMITH A P, et al. Potential benefits of a paired approach procedure to closely parallel runways in instrument and marginal visual conditions[C]// IEEE Digital Avionics Systems Conference. St. Paul: IEEE, 2008: 10-27.

[12]RAD T, SCH?NHALS S, HECKER P. Dynamic separation minima coupled with wake vortex predictions in dependent runway configurations [J]. Proceedings of the Institution of Mechanical Engineers, Part G: Journal of aerospace engineering, 2014, 228(8): 1450-1457.

[13]ROSSOW V J, MEYN L A. Guidelines for avoiding vortex wakes during use of closely spaced parallel runways [C]∥26th AIAA Applied Aerodynamics Conference. Honolulu,Hawall:[s.n.],2008.

[14]HU Minghua, MA Yuanyuan, TIAN Wen, et al. Optimized sequencing and scheduling approach for arrival traffic flow at complex terminal area[J]. Journal of Nanjing University of Aeronautics & Astronautics, 2015,47(4):459-466.(in Chinese)

[15]WU Y, SUN L, QU X. A sequencing model for a team of aircraft landing on the carrier[J]. Aerospace Science and Technology, 2016, 54: 72-87.

[16]JI X P, CAO X B, TANG K. Sequence searching and evaluation: A unified approach for aircraft arrival sequencing and scheduling problems[J]. Memetic Computing, 2016(8): 1-15.

[17]JIANG Y, YANG Y B, ZHOU H. Innovative predatory search algorithm for aircraft arrival sequencing and scheduling problems[J]. Transactions of Nanjing University of Aeronautics & Astronautics, 2010,27(4):361-366.

[18]FURINI F, KIDD M P, PERSIANI C A, et al. Improved rolling horizon approaches to the aircraft sequencing problem[J]. Journal of Scheduling, 2015, 18(5): 435-447.

Ms. Zhang Shuqin is currently a Ph.D. candidate and mainly focuses on runway scheduling.

Dr. Jiang Yu is currently an associate professor, and studies airport scheduling.

Prof. Xia Hongshan is currently a doctoral tutor, and he mainly studies traffic information.

(Executive Editor: Zhang Bei)

V351.11 Document code: A Article ID: 1005-1120(2016)04-0502-08

*Corresponding author, E-mail address:shuqin1969_happy@yeah.net.

How to cite this article: Zhang Shuqin, Jiang Yu, Xia Hongshan. Multi-objective collaborative optimization for scheduling aircraft landing on closely spaced parallel runways based on genetic algorithms[J]. Trans. Nanjing Univ. Aero. Astro., 2016, 33(4):502-509.

http://dx.doi.org/10.16356/j.1005-1120.2016.04.502