CN106022534B - A Method for Solving Aircraft Landing Problem Based on Improved Difference Algorithm - Google Patents

Abstract

The present invention proposes a kind of method for solving the problems, such as aircraft landing based on modified difference algorithm, specifically includes: establishing aircraft landing model and fitness function；It generates population primary and calculates the fitness value of each population at individual；It made a variation, intersected, generate population of new generation；Select keeping optimization；Judge termination condition, exports optimal solution.The present invention accelerates convergence rate, improves optimization precision and efficiency, while solving stagnation problem, and reduce the economic punishment in aircraft landing problem, has general applicability in aircraft landing problem.

Description

A Method for Solving Aircraft Landing Problem Based on Improved Difference Algorithm

technical field

The invention belongs to the field of aircraft dispatching, in particular to a method for solving the aircraft landing problem based on an improved differential algorithm.

Background technique

Over the past 20 years, the demand for air transport has increased significantly, which has resulted in an increasingly congested airspace, causing airports to be unable to cope with all the demand. Therefore, airport managers face great challenges in providing efficient service, shifting or changing the landing or departure time of some aircraft, these changes may lead to inefficient use of airport resources and reduced customer service, aircraft landing problems in determining the landing time of arriving aircraft Therefore, the optimization calculation of the aircraft landing problem has a great effect on the cost reduction in actual application. The aircraft landing problem involves constructing an aircraft landing schedule such that each aircraft is assigned to land on a specific runway at a specific time while ensuring that all problems and safety constraints are met with the goal of landing the aircraft earlier than scheduled Financial penalties for arriving or arriving late are minimized.

Airplane landing problem is a difficult non-deterministic polynomial (NP-hard) problem. For this reason, heuristic and meta-heuristic algorithms are widely used to find high-quality solutions in acceptable time frames instead of exact algorithms. Although exact algorithms can provide optimal solutions, their computation time tends to grow exponentially with the problem size, which makes them only suitable for small and medium-sized problems. Although many algorithms have been proposed to solve the aircraft landing problem, almost none of them have been proven to be an effective solution to the problem in all instances, and their performance usually decreases gradually as the instance becomes larger.

The differential evolution algorithm is a very well-known evolutionary algorithm, which is very effective in solving continuous optimization problems. Unfortunately, the differential evolution algorithm is not so good in the application of combinatorial optimization problems. The main disadvantage lies in its very high computational cost. Cost, especially when the population size is large, the convergence rate drops rapidly, which greatly reduces the efficiency of optimization. It is of great significance to improve the differential evolution algorithm to make up for the problem of slow convergence.

Contents of the invention

The technical problem solved by the present invention is to provide a method for solving the aircraft landing problem based on the improved differential algorithm. In the differential algorithm, mutation, crossover, and selection are introduced to speed up the convergence speed, improve the optimization accuracy and efficiency, and reduce the Financial Penalties in the Airplane Landing Problem.

The technical solution that realizes the object of the present invention is:

The method for solving the aircraft landing problem based on the improved differential algorithm comprises the following steps:

Step 1: Given the constraints of the aircraft landing problem and the maximum number of iterations G _max , establish the aircraft landing model and fitness function;

Step 2: Generate the first-generation population according to the aircraft landing model, the population size is NP, where each population individual represents an aircraft landing scheme;

Step 3: Calculate the fitness value of each population individual according to the fitness function;

Step 4: The target solution for each population individual Perform mutation operations to generate mutation solutions The following iterative formula mutates for one dimension in the target solution, namely

Among them, the target solution Represents the set of landing schemes for all aircraft; n represents the total number of aircraft in the aircraft landing problem, j represents the number of the current aircraft, Indicates the landing scheme arrangement of the jth aircraft in the i-th landing scheme; F=rand(0.1,1.5), and F represents the variation factor in the variation operation; and are solutions randomly selected from the current population, and

Step 5: Solve the target and mutation solution Perform crossover operations to generate a new generation of populations

Step 6: Calculate the new generation population The fitness value of , and with Comparing the fitness value of , making a selection to generate a new target solution

Step 7: Determine whether the maximum number of iterations G _max is reached, and if so, output Otherwise, go to step 3.

Further, in the method for solving the aircraft landing problem based on the improved differential algorithm of the present invention, in step 1, the constraints of the aircraft landing problem are:

Among them, x _i is the landing time of the i-th aircraft, x _j is the landing time of the j-th aircraft, i=1,2,...,n, j=1,2,...,n, i≠ _j , n is the number of planes, E _i is the earliest landing time stipulated by No. _i plane, Li is the latest landing time stipulated by No. The specified landing interval of the aircraft.

Further, in the method for solving the aircraft landing problem based on the improved differential algorithm of the present invention, in step 1, the fitness function is:

Among them, f is the fitness function, T _i represents the target arrival time of the i-th aircraft, C1 _i represents the economic penalty per unit time that the i-th aircraft arrives late relative to the target arrival time, and C2 _i represents the i-th aircraft The economic penalty per unit of time generated when the aircraft arrives earlier than the target arrival time, i=1,2,...,n, n is the number of aircraft.

Further, in the method for solving the aircraft landing problem based on the improved differential algorithm of the present invention, in step 2, the aircraft landing plan includes the landing runway and landing time of each aircraft.

Further, in the method for solving the aircraft landing problem based on the improved differential algorithm of the present invention, in step 5, the new generation population for:

in, CR∈[0,1] is the cross ratio, Rand(j)∈[0,1] means that the aircraft corresponding to No. j randomly selects a number, Rnd(i)∈{1,2,...,n} Indicates the number of aircraft numbers selected at random.

Further, in the method for solving the aircraft landing problem based on the improved differential algorithm of the present invention, in step 6, the new target solution for:

in, f(·) is the fitness function.

Compared with the prior art, the present invention adopts the above technical scheme and has the following technical effects:

1. The method of the present invention has a fast convergence speed, solves the stagnation problem simultaneously, and improves optimization efficiency;

2. The method of the present invention increases the diversity of the population in the application process of the aircraft landing problem, the optimization accuracy is high, and the economic penalty cost is greatly reduced;

3. The method of the present invention has universal applicability in the problem of aircraft landing.

Description of drawings

Fig. 1 is the flow chart of the method for solving the aircraft landing problem based on the improved differential algorithm of the present invention.

Detailed ways

Embodiments of the present invention are described in detail below, examples of which are shown in the drawings, wherein the same or similar reference numerals denote the same or similar elements or elements having the same or similar functions throughout. The embodiments described below by referring to the figures are exemplary only for explaining the present invention and should not be construed as limiting the present invention.

The description of the aircraft landing problem is as follows:

(1) Each aircraft must be assigned to a defined runway;

(2) No more than one aircraft can land on the same runway at the same time;

(3) The landing time of each aircraft should be within the predefined time window;

(4) The interval time between aircraft landing on the same runway must meet the safety standard interval time.

First, establish the parameter system of the aircraft landing problem, as shown in the following table:

no Arriving aircraft number m runway number S_ij The time interval required for aircraft i and aircraft j to land on the same runway T_i The expected target landing time of aircraft i E_i Earliest landing time of aircraft i L_i The latest landing time of aircraft i C1_i The economic penalty per unit of time for aircraft i arriving late relative to the target time C2_i The economic penalty per unit of time for aircraft i arriving earlier relative to the target time x_i The landing time of aircraft i

The method for solving the aircraft landing problem based on the improved differential algorithm proposed by the present invention, the method flow as shown in Figure 1, specifically includes the following steps:

Step 1: Given the constraints of the aircraft landing problem and the maximum number of iterations G _max , establish the aircraft landing model and fitness function.

The constraints of the aircraft landing problem are:

Among them, x _i is the landing time of the i-th aircraft, x _j is the landing time of the j-th aircraft, i=1,2,...,n, j=1,2,...,n, i≠ _j , n is the number of planes, E _i is the earliest landing time stipulated by No. _i plane, Li is the latest landing time stipulated by No. The specified landing interval of the aircraft.

The fitness function is:

Among them, f is the fitness function, T _i represents the target arrival time of the i-th aircraft, C1 _i represents the economic penalty per unit time that the i-th aircraft arrives late relative to the target arrival time, and C2 _i represents the i-th aircraft The economic penalty per unit of time generated when the aircraft arrives earlier than the target arrival time, i=1,2,...,n, n is the number of aircraft.

Step 2: Generate the first-generation population according to the aircraft landing model, and the population size is NP=5, where each population individual represents an aircraft landing scheme. The population size taken here is small, which is called differential evolution, which can effectively improve the convergence speed of the differential evolution algorithm, but it will increase the risk of stagnation problems.

The solution expression of the aircraft landing scheme is:

The landing plan of an aircraft includes the landing runway and landing time of the aircraft. The landing plan is represented by a real number with a decimal, the integer part represents the landing runway, and the decimal part represents the landing time on the runway.

The aircraft landing scheme of the present embodiment is shown in the table below:

aircraft number 1 2 3 4 5 6 landing plan 2.4 1.45 1.3 3.7 3.55 2.2

The total number of runways here is 3, so the value of the integer part is in [1,3], which represent three runways respectively, and the decimal part represents the landing time. On the same runway, they are arranged in ascending order corresponding to the priority of time. For example, the landing scheme 1.3 of aircraft No. 3 is expressed as: the landing runway is runway No. 1, 0.3=(the landing time of the aircraft on runway 1-the earliest preset landing time of runway 1)/(the latest preset landing time of runway 1 -Runway 1 preset earliest possible landing time).

Step 3: Calculate the fitness value of each population individual according to the fitness function.

Step 4: The target solution for each population individual Perform mutation operations to generate mutation solutions The following iterative formula mutates for one dimension in the target solution, namely

Among them, the target solution Represents the set of landing schemes for all aircraft; n represents the total number of aircraft in the aircraft landing problem, j represents the number of the current aircraft, Indicates the scheme arrangement of the jth aircraft in the i-th landing scheme; F=rand(0.1,1.5), and F represents the variation factor in the variation operation; and are solutions randomly selected from the current population, and

The variation factor F here is not just randomly selected once, but the F=rand(0.1,1.5) operation must be performed every time the mutation operation is calculated, which can greatly increase the diversity of the population, thus effectively solving the problem The stagnation problem brought about by reducing the population size.

Step 5: Solve the target and mutation solution Perform crossover operations to generate a new generation of populations

new generation population Expressed as:

in, CR∈[0,1] is the cross ratio, Rand(j)∈[0,1] means that the aircraft corresponding to No. j randomly selects a number, Rnd(i)∈{1,2,...,n} Indicates the number of randomly selected aircraft numbers, and the Rnd(i) operation guarantees at least from get a variable.

Step 6: Calculate the new generation population The fitness value of , and with Comparing the fitness value of , making a selection to generate a new target solution

new target solution Expressed as:

in, f(·) is the fitness function.

Step 7: Determine whether the maximum number of iterations G _max is reached, and if so, output Otherwise, go to step 3.

So far, the entire process of the method for solving the aircraft landing problem based on the improved differential evolution algorithm is over. Taking the optimal solution obtained in the above process, we can draw the following conclusions:

First of all, this method is generally applicable to the problem of aircraft landing, and the optimal solution obtained reaches the level of existing algorithm optimization. Through optimization, the economic penalty and cost are greatly reduced, and it solves the problem of traditional differential evolution algorithm in solving combinatorial optimization problems. The problem of slow convergence improves the speed and efficiency of optimization.

The above description is only a part of the implementation of the present invention, it should be pointed out that for those of ordinary skill in the art, without departing from the principle of the present invention, some improvements can also be made, and these improvements should be regarded as the present invention. scope of protection.

Claims (1)

1. The method for solving the aircraft landing problem based on the improved differential algorithm is characterized by comprising the following steps of:

step 1: given constraints and maximum number of iterations G for an aircraft landing problem_maxEstablishing an aircraft landing model and a fitness function;

step 2: generating an initial generation population according to the aircraft landing model, wherein the population scale is NP, and each population individual represents an aircraft landing scheme;

and step 3: calculating the fitness value of each population individual according to the fitness function;

and 4, step 4: target solution for each population individualPerforming mutation operation to generate mutation solutionThe following iterative formula is mutated for one dimension in the target solution, i.e.

Wherein the target solutionRepresents a set of landing scenarios for all aircraft;n represents the total number of aircraft in the aircraft landing problem, j represents the number of the current aircraft,representing the arrangement of the landing scheme of the jth aircraft in the ith landing scheme; f ═ rand (0.1,1.5), F denotes a mutator in a mutation operation;andare respectively solutions randomly selected from the current population, an

And 5: to the target solutionAnd mutation solutionPerforming cross operation to generate a new generation of population

Step 6: computing new generation populationAnd an adaptation value ofComparing the fitness values of the target data to select and generate a new target solution

And 7: judging whether the maximum iteration number G is reached_maxIf yes, outputtingOtherwise, go to step 3;

in step 1, the constraint conditions of the aircraft landing problem are as follows:

wherein x is_iLanding time for airplane # i, x_jThe landing time of the j-th aircraft is 1,2,.. the landing time of the j-th aircraft is n, j is 1,2,.. the landing time of the j-th aircraft is n, i ≠ j, n is the number of aircraft, E_iEarliest landing time specified for aircraft # i, L_iLatest landing time, s, specified for aircraft # i_ijSpecified landing interval time for the ith aircraft and the jth aircraft landing on the same runway;

in step 1, the fitness function is:

where f is the fitness function, T_iIndicating the target arrival time of airplane # i, C1_iIndicating the economic penalty per unit time incurred by aircraft # i late in relation to the target arrival time, C2_iRepresenting the economic penalty of the ith airplane per unit time caused by the early arrival of the relative target arrival time, wherein i is 1, 2.

In step 2, the aircraft landing scheme comprises a landing runway and landing time of each aircraft;

in step 5, a new generation populationComprises the following steps:

wherein,CR∈[0,1]for the crossover ratio, rand (j) e[0,1]Indicating that the airplane corresponding to the j number randomly selects a number, wherein Rnd (i) epsilon {1, 2.. multidot.n } represents the number of the randomly selected airplane;

in step 6, the new target solutionComprises the following steps:

wherein,f (-) is the fitness function.