CN117077981B - Method and device for distributing stand by fusing neighborhood search variation and differential evolution - Google Patents

Abstract

The invention discloses a stand allocation method and a stand allocation device integrating neighborhood search variation and differential evolution, which relate to the technical field of airport scene resource scheduling and comprise the following steps: s1, airport incoming and outgoing flight and stand data; s2, building a stand allocation mathematical model; s3, generating an initialization population and setting parameters; determining iteration times, population size, initialization algebra, solved problem dimension and the like; s4, initializing population; randomly initializing a population by taking the upper limit and the lower limit of a search space as a boundary, and then coding the population into binary individuals; s5, group variation crossing and selection optimization; calculating objective function values and sequencing, forming individuals with the top 60% of ranks into a neighborhood, and generating new excellent individuals to enter the next generation through a neighborhood searching mutation mechanism; s6, optimizing the population by using a row 'difference update' strategy and an individual optimization strategy; the method effectively solves the problem of multi-constraint complex optimization, and improves the convergence accuracy and the machine position distribution efficiency of the algorithm.

Description

Method and device for distributing stand by fusing neighborhood search variation and differential evolution

Technical Field

The invention relates to the technical field of airport scene resource scheduling, in particular to a stand allocation method and device integrating neighborhood search variation and differential evolution.

Background

Allocation problems refer to allocation of tasks to a set of resources with minimized cost or maximized allocation benefits. Airport scene resource operation management is realized by airport staff searching for an efficient scene resource scheduling method. Among them, airport stand allocation problems (AGAP) are a very important class of complex optimization problems based on scheduled departure and landing time management of flights. The problems have the characteristics of high solving time complexity, complex real environment and the like. The efficient and reasonable allocation of the stand has important significance for improving the operation efficiency of scene resources and the satisfaction of passengers.

At present, the existing research mainly aims at an optimization target and a solving method of the stand allocation problem. The study of the optimization objectives for the stand allocation problem mainly takes into account the time costs (airport operator angle) and passenger satisfaction. There are two main categories of solutions to the stand allocation problem. The mathematical programming method is a popular solving method, but as the problem scale increases, constraint conditions increase, and the mathematical programming method gradually exposes the problems of long calculation time, low solving efficiency and the like. Heuristic algorithms are increasingly receiving extensive attention from a number of scholars. While heuristic algorithms exhibit many advantages in solving the problem of stand allocation, they still suffer from the problems of being prone to search stalls, reduced post diversity, and the like. Therefore, the method for solving the stand allocation problem by searching the intelligent optimization algorithm is necessary, has important theoretical significance and has wide practical engineering value.

The DE algorithm is an excellent evolutionary algorithm proposed by Storn and Price. The method is simple in principle and high in searching efficiency. Is widely applied to various engineering problems such as resource scheduling, industrial design and the like, and obtains excellent results. However, the DE algorithm is used to solve the complex optimization problem, and simultaneously, many disadvantages are exposed, for example, the DE algorithm enters a later searching stage, the searching capability is reduced, the searching speed is reduced, and the local optimum state is easily trapped. Many scholars have proposed a number of practical and effective methods to overcome these problems of the DE algorithm. The following are summarized in general terms: variation strategy, parameter control and algorithm cooperation.

Disclosure of Invention

Aiming at the problems of easy local optimum sinking, low later convergence speed and the like of the DE algorithm, the invention provides a stand allocation method which effectively realizes stand resource optimization and improves the utilization rate of airport key resources.

The invention adopts the following technical scheme:

a stand allocation method integrating neighborhood search variation and differential evolution comprises the following steps:

s1: acquiring airport incoming and outgoing flight and stand data; the incoming and outgoing flight data comprise a flight number, a flight entering position time, a flight leaving position time, the type of each flight and a planned passenger carrier;

the stand data comprise stand type, stand occupation time, stand size and the like;

s2: constructing a stand allocation mathematical model comprising an objective function model, a constraint condition model and a multi-objective unquantized processing model; the objective function model is determined according to the airport real operation environment, and a differential evolution method is adopted for solving;

the objective function comprises five targets of shortest walking time of passengers, balanced idle time of the machine stations, minimum flight-machine station matching difference, most full utilization of large machine stations and highest occupancy rate of machine stations;

based on the machine position parking safety interval constraint, the invention also considers the machine position uniqueness, the machine position matching constraint and the near machine position priority allocated constraint; processing the objective function in a non-quantization mode to finally obtain the objective function;

s3: randomly generating an initialization population, and setting parameters according to a table 1; basic parameters including but not limited to determining iteration times, population size, initialization algebra, and solved problem dimension;

s4: initializing a population; randomly initializing a population by taking the upper limit and the lower limit of a search space as a boundary, and then coding the population into binary individuals;

s5: population variation, machine position crossing and selection optimization; calculating objective function values and sequencing, forming individuals with the top 60% of ranks into a neighborhood, and generating new excellent individuals to enter the next generation through a neighborhood searching mutation mechanism;

s6: executing a differential upgrading strategy and an individual optimizing strategy to optimize the population; the "differential upgrade" strategy is:

re-computing the population adaptation value after mutation, crossover and selection, and re-averaging to define asCurrent individualX_l Is defined as +.>If->Will thenX_l Defined as the current "difference" and then willX_l Upgrading, if the upgraded 'difference generation' cannot be ensured to be more excellent than the current individual, replacing the 'difference generation' position with the current individual;

s7: and (5) circulating the steps S5 and S6 to appoint training rounds and outputting the optimal result.

Preferably, in S2, the objective function model includes the following aspects:

(1) The passenger walking time is shortest

（1）；

In the middle of，M_pq To be allocated to the standqOn flightspThe number of people to be transferred by the passengers,D_q for passengers to arrive at the standqIs used for the distance of (a),Zis a variable which is 0 to 1,Z=0 represents a flight,Z=1 represents the stand of the machine,Z_pq is a variable which is 0 to 1,Z_pq =0 represents a flight,Z_pq =1 represents the stand of the machine,Pfor the number of flights to be counted,Qthe number of the machine stations is the number of the machine stations;

(2) The idle time of the stand is balanced most, and when delay or conflict occurs, the balanced idle time plays a certain role in buffering so as to avoid large-scale delay;

（2）；

in the method, in the process of the invention,T_pq is thatpFlight arrival at standqTime standqIs used for the idle time of the vehicle,t_q is the machine idle time;

(3) The flight-station matching difference is minimum, the small aircraft can stop at the small station as much as possible, and the large aircraft can stop at the large station;

（3）；

Rho_pq for the current standqThe difference between the largest machine type that can stop and the machine type that the flight should correspond to,Arepresenting the maximum machine position;

(4) Most fully utilizing large-scale machine position

（4）；

H_pq The number of the airplanes parked at the medium-sized airplane station for parking the small-sized airplane at the large-sized airplane station;

(5) Based on the highest occupancy rate of the machine, the current machine occupancy time is related to the arrival and departure time of the parked flights, if the difference value between the current machine occupancy time and the arrival and departure time of the parked flights is smaller, the current machine occupancy time is less, and the fact that more flights can park the machine is indicated;

（5）；

in the middle of，For flightspLeave standqTime of (2)>Stop for flight p arrivalTime of bit q, K represents24h，ZIs a variable which is 0 to 1,Z=0 represents a flight,Z=1 represents the stand of the machine,Z_pq is a variable which is 0 to 1,Z_pq =0 represents a flight,Z_pq =1 represents the stand of the machine,Pfor the number of flights to be counted,Qis the number of stand.

Preferably, in S2, the constraint condition model includes the following aspects:

(1) The position uniqueness, i.e. the idle position can only be occupied by one aircraft at a time;

（6）；

for flightspAssigned to the stand->For flightspIs allocated to the tarmac;

(2) The airplane position is matched and constrained, so that the airplane position is matched with the airplane type, namely, a large airplane can only stop at the large airplane position but cannot stop at the middle and small airplane positions;

（7）；

Q_tin the form of a machine location type,Q_tis of the aircraft type;

(3) The safety interval constraint is that two (or more) airplanes are parked at the same airplane station, and a certain time interval is needed between the departure time of the former airplane and the arrival time of the latter airplane;

(8)；

for the last aircraftp+1 arrival at standqTime of (2)>Is thatcurrentAircraft leaving standqIs used for the time period of (a),sepis a safety interval;

(4) Near-range priority is assigned a constraint, near-range priority being assigned means that passengers can reduce walking time;

（9）；

is near the machine position, is->Is remote, in addition to the above>Is a tarmac.

Preferably, in S2, the objective function adopts no quantization processing, adopts a weighting method to convert the multi-objective problem into a single-objective problem, and introduces a weight factor；

（10）；

（11）；

Is provided with，/>The objective function after the non-quantization treatment is:

（12）；

the final objective function is as follows:

（13）；

in the method, in the process of the invention,r₁ 、r₂ 、r₃ 、r₄ 、r₅ are all the weight factors of the weight factors,is->，/>Is->，/>Is->，/>Is->，/>Is->。

Preferably, in S4, the specific method for encoding the population into binary individuals is as follows:

the original floating point type is replaced by 0-1 for the initial population, so that the search space is simplified, the search efficiency is improved, and a random array is generated;

normalizing the random matrix by using the upper limit and the lower limit of the search space to obtain a random array ND with dimension NxD; the random array ND is an irregular floating point array, so that blind searching is easy to occur, and the efficiency is reduced;

thus, each vector is converted into binary codes distributed in 0-1 according to the discrimination conditions to form a binary populationx_ij ；

Random array expression:

（14）；

the expression of the normalized random matrix of the upper limit and the lower limit of the search space is as follows:

（15）；

the random array ND is:

（16）；

the expression of the discrimination condition is:

（17）；

in the method, in the process of the invention,iis defined by the size of the populationNIt is decided that the method comprises the steps of,jthe size of (c) is determined by the dimension D,radom_arrayis a random matrix of size nxd generated by a random function,rand() Is a random number between 0 and 1,lambis a random number subject to a gaussian distribution,in the matrix with the number of rows being N and the number of columns being D,radomto return a real number generated randomly, itWithin the range of [0,1 ]。shapeIn order to return to the dimensions of the matrix,upandlowis the upper and lower limit of the search space.

Preferably, in S5, the specific method for population variation crossover is:

the adaptation value of the current generation is increased, individuals with the top 60% of the rank form a neighborhood, so that the strength of neighborhood search variation is enlarged, and the mathematical expression is as follows:

(18);

wherein,Theta、parameters related to the number of iterations and obeying the exponential distribution, respectively +.>Is the g-th iteration in the neighborhoodmThe number of excellent individuals is one,m、m₁ andm₂ is taken from [1, N-1 ]]Random integers and are different from each other; />、/>Respectively, the g-th iteration is adjacent to the first iterationm₁ First, them₂ Individual excellent individuals; />And after the current global optimal individual is selected into the neighborhood, guiding the individuals in the neighborhood to gather to the most excellent individual, and further promoting global optimization.

Preferably, in S5, the method for machine level crossing and selection optimization is as follows:

machine position cross operation: for two adjacent stand-flight pairs, performing a stand crossover operation, i.e., changing the gene sequence for two or more of the stand exchange positions;

selecting an optimization operation: and (3) putting the gene sequence obtained after the cross operation into a constraint condition model in the step (S2), judging whether the gene sequence accords with the constraint condition, and then evaluating the objective function value of the stand allocation model.

Preferably, in S6, the calculation formula of the "differential upgrading" strategy is as follows:

(19)；

(20)；

in the method, in the process of the invention,X_l is currently "bad",X_m to update the "difference",for the adaptation value corresponding to the optimal individual,for the adaptation value corresponding to the worst individual, +.>，/>Is two randomly extracted individuals, +.>，/>，And randomly extracting the corresponding adaptation values of the individuals respectively.

Preferably, the individual optimization strategy is based on normal distribution, and the calculation formula is as follows:

（21）；

(22)；

wherein if it</>Will beX_u Is defined as an excellent individual and is defined as an excellent individual,Up，Lowfor the upper and lower limit of the search space, +.>The average value of the population adaptation values of the whole population of the current generation is obtained;X_b updating the obtained individual after optimizing the strategy for the individual;Xis a group of common individuals in the population,Xobeying normal distribution;μindicating the desire, delta is the variance,Nindicating compliance with normal distribution; equation (21) represents that the excellent individual is selected to perform mathematical transformation within the upper and lower limits of the search space by comparison +.>And->Wherein better is preserved into the next generation.

Preferably, a stand allocation device integrating neighborhood search variation and differential evolution comprises at least one processor and a memory; the memory stores instructions executable by the at least one processor to enable the at least one processor to perform the fused neighborhood search variant and differentially evolved stand allocation method.

The beneficial effects of the invention are as follows:

1. the invention effectively solves the problem of multi-constraint complex optimization.

2. The invention designs a population initialization method based on binary codes to improve the searching efficiency in the initial stage. A neighborhood search mutation mechanism with new mutation factors is provided to improve the quality of the mutated individuals and balance global optimization capacity and local optimization capacity.

3. The present invention proposes a "differential upgrade" strategy to pick out individuals with poor performance and boost their competitiveness. Individual optimization strategies based on normal distribution are designed to mine the potential of excellent individuals.

4. The airport stand allocation method based on the NSVMDE algorithm provided by the invention has the advantage that the stand allocation efficiency is remarkably improved.

Drawings

In order to more clearly illustrate the technical solutions of the embodiments of the present invention, the following brief description of the drawings of the embodiments will be made, it being apparent that the drawings in the following description relate only to some embodiments of the present invention and are not limiting of the present invention.

FIG. 1 is a schematic diagram of a DE method neighborhood in the prior art.

Fig. 2 is a schematic illustration of a stand-to-flight pair of the method of the present invention.

FIG. 3 is a schematic cross-machine-position diagram of the method of the present invention.

FIG. 4 is a flow chart of the present invention.

FIG. 5 is a comparative graph of the optimizing ability of the method of the present invention and the comparative method;

wherein FIG. 5 (a) is a functional diagram of the method of the present invention and other comparison algorithmsAn iterative convergence graph with dimensions of 30;

wherein FIG. 5 (b) is a functional diagram of the method of the present invention and other comparison algorithmsAn iterative convergence graph with dimensions of 30;

wherein FIG. 5 (c) is a functional diagram of the method of the present invention and other comparison algorithmsAn iterative convergence graph with dimensions of 50;

wherein FIG. 5 (d) is a functional diagram of the method of the present invention and other comparison algorithmsAn iterative convergence graph with dimensions of 50;

wherein FIG. 5 (e) is a functional diagram of the method of the present invention and other comparison algorithmsAn iterative convergence graph with dimensions of 100;

wherein FIG. 5 (f) is a functional diagram of the method of the present invention and other comparison algorithmsThe iteration convergence graph in the case where the dimension is 100.

Fig. 6 is a diagram of the stand allocation results of the method of the present invention.

FIG. 7 is an optimized graph of the method of the present invention versus a comparison algorithm to solve the problem of stand allocation.

Detailed Description

In order to make the objects, technical solutions and advantages of the embodiments of the present invention more clear, the technical solutions of the embodiments of the present invention will be clearly and completely described below with reference to the accompanying drawings of the embodiments of the present invention. It will be apparent that the described embodiments are some, but not all, embodiments of the invention. All other embodiments, which can be made by a person skilled in the art without creative efforts, based on the described embodiments of the present invention fall within the protection scope of the present invention.

The invention will be further described with reference to the drawings and examples.

Example 1

A stand allocation method integrating neighborhood search variation and differential evolution comprises the following steps:

s1: acquiring airport incoming and outgoing flight and stand data; the incoming and outgoing flight data comprise a flight number, a flight entering position time, a flight leaving position time, the type of each flight and a planned passenger carrier;

the stand data comprises a stand type, stand occupation time, stand size and the like.

S2: constructing a stand allocation mathematical model comprising an objective function model, a constraint condition model and a multi-objective unquantized processing model; the objective function model is determined according to the airport real operation environment, and a differential evolution method is adopted for solving;

the objective function comprises five targets of shortest walking time of passengers, balanced idle time of the machine stations, minimum flight-machine station matching difference, most full utilization of large machine stations and highest occupancy rate of machine stations;

based on the machine position parking safety interval constraint, the invention also considers the machine position uniqueness, the machine position matching constraint and the near machine position priority allocated constraint; and processing the objective function in a non-quantization mode to finally obtain the objective function.

The objective function model includes the following aspects:

(1) The passenger walking time is shortest

（1）；

In the middle of，M_pq To be allocated to the standqOn flightspThe number of people to be transferred by the passengers,D_q for passengers to arrive at the standqIs used for the distance of (a),Z_pq is a variable which is 0 to 1,Z_pq =0 represents a flight,Z_pq =1 represents the stand of the machine,Pfor the number of flights to be counted,Qthe number of the machine stations is the number of the machine stations;

(2) The idle time of the stand is balanced most, and when delay or conflict occurs, the balanced idle time plays a certain role in buffering so as to avoid large-scale delay;

（2）；

in the method, in the process of the invention,T_pq is thatpFlight arrival at standqTime standqIs used for the idle time of the vehicle,t_q is the machine idle time;

(3) The flight-station matching difference is minimum, the small aircraft can stop at the small station as much as possible, and the large aircraft can stop at the large station;

（3）；

Rho_pq for the current standqThe difference between the largest machine type that can stop and the machine type that the flight should correspond to,Arepresenting the maximum machine position;

(4) Most fully utilizing large-scale machine position

（4）；

H_pq The number of the airplanes parked at the medium-sized airplane station for parking the small-sized airplane at the large-sized airplane station;

(5) Based on the highest occupancy rate of the machine, the current machine occupancy time is related to the arrival and departure time of the parked flights, if the difference value between the current machine occupancy time and the arrival and departure time of the parked flights is smaller, the current machine occupancy time is less, and the fact that more flights can park the machine is indicated;

（5）；

in the middle of，For flightspLeave standqTime of (2)>Stop for flight p arrivalTime of bit q, K represents24h，Z_pq Is a variable which is 0 to 1,Z_pq =0 represents a flight,Z_pq =1 represents the stand of the machine,Pfor the number of flights to be counted,Qthe number of the machine stations is the number of the machine stations;

the constraint condition model comprises the following aspects:

(1) The position uniqueness, i.e. the idle position can only be occupied by one aircraft at a time;

（6）；

for flightspAssigned to the stand->For flightspIs allocated to the tarmac;

(2) The airplane position is matched and constrained, so that the airplane position is matched with the airplane type, namely, a large airplane can only stop at the large airplane position but cannot stop at the middle and small airplane positions;

（7）；

Q_tin the form of a machine location type,Q_tis of the aircraft type;

(3) The safety interval constraint is that two (or more) airplanes are parked at the same airplane station, and a certain time interval is needed between the departure time of the former airplane and the arrival time of the latter airplane;

（8）；

for the last aircraftp+1 arrival at standqTime of (2)>Is thatcurrentAircraft leaving standqIs used for the time period of (a),sepis a safety interval;

(4) Near-range priorities are assigned constraints, meaning that passengers can reduce walking time.

（9）；

Is near the machine position, is->Is remote, in addition to the above>Is a tarmac.

The invention considers the constraints of the time of entering and leaving the port, the satisfaction degree of passengers, the stand and the type of the flights, the safety time interval and the like, so as to balance the idle time most, ensure the shortest walking distance of the passengers, fully utilize the large stand, ensure the least matching difference degree of the stand and the highest stand occupancy as the optimization target, establish the objective function and construct the stand allocation mathematical model. For the multi-objective model, a set of single objective functions (formula 10) is given, the objective functions are processed in a non-quantization way, the multi-objective problem is converted into a single objective problem (formula 11) by a weighting method, and weight factors are introduced；

（10）；

（11）；

Is provided with，/>The objective function after the non-quantization treatment is:

（12）；

the final objective function is as follows:

（13）；

in the method, in the process of the invention,r₁ 、r₂ 、r₃ 、r₄ 、r₅ are all the weight factors of the weight factors,is->，/>Is->，/>Is->，/>Is->，/>Is->。

S3, randomly generating an initialization population, and setting parameters according to a table 1; basic parameters including but not limited to determining iteration times, population size, initialization algebra, and solved problem dimension;

s4: initializing a population; randomly initializing a population by taking the upper limit and the lower limit of a search space as a boundary, and then coding the population into binary individuals;

the specific method for encoding the population into binary individuals comprises the following steps:

the original floating point type is replaced by 0-1 for the initial population, so that the search space is simplified, the search efficiency is improved, and a random array is generated;

normalizing the random matrix by using the upper limit and the lower limit of the search space to obtain a random array ND with dimension NxD; the random array ND is an irregular floating point array, so that blind searching is easy to occur, and the efficiency is reduced;

thus, each vector is converted into binary codes distributed in 0-1 according to the discrimination conditions to form a binary populationx_ij ；

Random array expression:

（14）；

the expression of the normalized random matrix of the upper limit and the lower limit of the search space is as follows:

（15）；

the random array ND is:

（16）；

the expression of the discrimination condition is:

（17）；

in the method, in the process of the invention,iis defined by the size of the populationNIt is decided that the method comprises the steps of,jthe size of (c) is determined by the dimension D,radom_arrayis a random matrix of size nxd generated by a random function,rand() Is a random number between 0 and 1,lambis a random number subject to a gaussian distribution,in the matrix with the number of rows being N and the number of columns being D,radomto return a randomly generated real number, it is in the range of [0,1 ]。shapeIn order to return to the dimensions of the matrix,upandlowis the upper and lower limit of the search space.

S5: population variation, machine position crossing and selection optimization; calculating objective function values and sequencing, forming individuals with the top 60% of ranks into a neighborhood, and generating new excellent individuals to enter the next generation through a neighborhood searching mutation mechanism;

the invention improves the poor local searching capability of the DE algorithm by dividing the neighborhood and generating excellent new individuals in the neighborhood by variation, and plays a role in balancing the global optimizing capability and the local optimizing capability to a certain extent.

The neighborhood strategy in the prior art is to combine the current individual and its nearby individuals into a search neighborhood, as shown in figure 1,and->Manifestation of (1) pair->Will have a great influence if +.>And->Is a "difference" individual, then->The performance of (a) is also affected.

In order to balance the global optimization capability and the local optimization capability of the DE algorithm, the diversity of excellent individuals is increased. Firstly, the adaptation values of the current generation are increased, individuals with the top 60% of the ranking are selected to form a neighborhood (the strength of the neighborhood search variation is increased, the algorithm diversity is not lost), the 'difference effect' can be avoided, and meanwhile, under the influence of excellent individuals, the convergence speed and the convergence precision are improved. As known from the conventional mutation strategies of the DE algorithm (DE/rand/k (k=1, 2), etc.), the mutation factor directly affects the stability of the DE algorithm, the selection of a new mutation factor is very important, and the mathematical expression of population mutation crossover is as follows:

(18);

wherein,Theta、parameters related to the number of iterations and obeying the exponential distribution, respectively +.>Is the g-th iteration in the neighborhoodmThe number of excellent individuals is one,m、m₁ andm₂ is taken from [1, N-1 ]]Random integers and are different from each other; />、/>Respectively, the g-th iteration is adjacent to the first iterationm₁ First, them₂ Individual excellent individuals; />And after the current global optimal individual is selected into the neighborhood, guiding the individuals in the neighborhood to gather to the most excellent individual, and further promoting global optimization. Due to->、/>The first 60% of globally excellent individuals already belong to the neighborhood when selected, and thus individuals who variant under their interference will be competitive. The neighborhood search variation strategy effectively improves the local optimization capability, maintains strong convergence performance even under the condition that the individual difference is smaller in the later stage of the DE algorithm, and plays an important role in balancing the global optimization capability and the local optimization capability.

The machine position crossing and selection optimization method comprises the following steps:

machine position cross operation: the allocation scheme for each individual stand-flight pair in the population-based NSVMDE algorithm is shown in fig. 2, where each individual contains N genes (representing the flight pair allocated to the current stand), the jth gene represents the jth aircraft, and the numbers on the genes represent the number of stands for the corresponding aircraft. In this individual, the number of positions that each gene can select must satisfy constraints including the time of flight departure, passenger satisfaction, the position of the stop and the type of flight and the safety interval. As shown in fig. 3, two or more crossing points are randomly set for an individual, and then a level crossing operation is performed according to the crossing probability to change the individual gene sequence;

selecting an optimization operation: and (3) putting the gene sequence obtained after the cross operation into a constraint condition model in the step (S2), judging whether the gene sequence accords with the constraint condition, and then evaluating the objective function value of the stand allocation model.

S6: executing a differential upgrading strategy and an individual optimizing strategy to optimize the population; the "differential upgrade" strategy is:

re-computing the population fitness after mutation, crossover and selection, re-averaging the population fitness values to defineCurrent individualX_l Is defined as +.>If->Will thenX_l Defined as the current "difference" and then willX_l Upgrading, if the upgraded 'difference generation' cannot be ensured to be more excellent than the current individual, replacing the 'difference generation' position with the current individual;

the 'difference generation upgrading' strategy can continuously improve the competitiveness of low-level individuals and the convergence accuracy of the DE algorithm, and the calculation formula is as follows:

(19)；

(20)；

in the method, in the process of the invention,X_l is currently "bad",X_m to update the "difference",for the adaptation value corresponding to the optimal individual,for the adaptation value corresponding to the worst individual, +.>，/>Is two randomly extracted individuals, +.>，/>，And randomly extracting the corresponding adaptation values of the individuals respectively.

Equation (19) and equation (20) use a random extraction of individuals to pair "difference generation"X_l Optimizing, effectively avoiding the algorithm from falling into the local optimumIs the case in (a). Since the minimum adaptation value is to be found,>/>. Thus, if，/>Will guideX_l The regions of excellent individuals are explored. In this way, the competitiveness of the 'bad' population is improved, the population diversity can be increased, and new power is provided for the subsequent DE algorithm evolution.

The normal distribution-based individual optimization strategy aims at mining the potential of excellent individuals, which is necessary for the multi-optimization objective problem, because the DE algorithm tends to fall into a local optimum in the vicinity of excellent individuals. The method can further optimize the individual after 'upgrading', keep excellent individual growth force, and simultaneously continuously optimize the DE algorithm towards a better solution direction, thereby playing a guiding role to a certain extent.

The individual optimization strategy is based on normal distribution, and the calculation formula is as follows:

（21）；

(22)；

wherein if it</>Will beX_u Is defined as an excellent individual and is defined as an excellent individual,Up，Lowfor the upper and lower limit of the search space, +.>The average value of the population adaptation values of the whole population of the current generation is obtained;X_b updating the obtained individual after optimizing the strategy for the individual;Xis a group of common individuals in the population,Xobeying normal distribution;μindicating the desire, delta is the variance,Nindicating compliance with normal distribution; equation (21) represents that the excellent individual is selected to perform mathematical transformation within the upper and lower limits of the search space by comparison +.>And->Wherein better is preserved into the next generation. Equation (21) uses search space upper and lower limits and normal distribution controlX_u Can avoid the algorithm from falling into a local optimum. By and->In contrast, more excellent individuals are continually retained until the next generation.

S7: and (5) circulating the steps S5 and S6 to appoint training rounds and outputting the optimal result.

Verification example 1

In order to verify the effectiveness of the algorithm (NSVMDE) of the invention, the models of the six methods of Bina-DE, M-SSA, NEBDE, PSDE, NS-MJPSO and ACDE/F are respectively evaluated and compared with the invention, and 14 reference functions comprising single mode and multiple modes are selected to respectively verify the optimizing speed and the convergence capacity of the model. Wherein,is a unimodal function used to verify its convergence speed, < >>The multi-modal function is used for verifying the convergence capability of the invention and judging whether the convergence is global.Is a shift unimodal function, ">Shifting the multimodal function ++>Is a mixing function. The parameter settings of the different algorithms are shown in table 1, and the results of the different dimension numerical simulation experiments are shown in tables 2, 3 and 4.

Table 1 parameter settings for different algorithms

Table 2 results of numerical simulation comparisons of the present invention and the comparison method on complex functions (d=30)

Table 3 results of numerical simulation comparisons of the present invention and the comparison method on complex functions (d=50)

Table 4 results of numerical simulation comparisons of the present invention and the comparison method on complex functions (d=100)

Where Opt is the optimal value obtained by the algorithm, worst is the Worst value, mean is the Mean, std is the variance, and Median is the Median.

As can be seen from tables 2 to 4, the present invention has the highest accuracy in the overall view. The accuracy of the Bina-DE algorithm is improved to that of the NEBDE algorithm in a leap way, which shows that a neighborhood searching mechanism plays a great role, and the local searching capability and the global searching capability of the algorithm are well balanced.

The invention compares the experiment with other 5 advanced algorithms to judge that the algorithm is inIn different dimensionsAnd->The optimizing performance of the two functions is run 30 times, and 200 substitution results are plotted as shown in fig. 5.

As shown in fig. 5, the optimizing performance of the present invention in other functions is superior to other algorithms in different dimensions. The invention has excellent optimizing capability and similar trend with NEBDE algorithm, because the neighborhood searching mechanism divides the neighborhood searching range, excellent individuals are generated in the neighborhood, the optimizing direction of the algorithm is guided, the stable and tough searching performance is still maintained in the later stage of the algorithm, and the searching precision is improved.

Verification example 2

The optimized performance of the invention under different dimensions is verified by adopting CEC2005 and CEC2017 standard test functions (NSVMDE), the problem of airport stand allocation is effectively solved, and the utilization rate of important resources of an airport is improved. Airport flight and airplane position data are selected from 26 days of 7 months of 2015 of a certain airport, the data comprise 30 airplane positions and 250 flights;

as shown in FIG. 6, the stand distribution result diagram of the present invention has a maximum distribution rate of up to 98.3%. FIG. 7 is an optimized graph of the present invention and a comparison algorithm for solving the problem of stand allocation, as shown in the figure, the method of the present invention, NSVMDE algorithm, converges with the highest accuracy, and finally converges to 0.591.

Example 2

A stand allocation device integrating neighborhood search variation and differential evolution comprises at least one processor, a memory, an input and output device and a power supply; the memory stores instructions executable by the at least one processor to enable the at least one processor to perform a binary coded representation and multi-class based track prediction method of the foregoing embodiments; the input and output equipment comprises a display, a keyboard, a mouse and a USB interface, and completes the interactive operation of data; the power source may be an external power source or a rechargeable battery to provide power to the device.

Those skilled in the art will appreciate that: all or part of the steps for implementing the above method embodiments may be implemented by hardware related to program instructions, and the foregoing program may be stored in a computer readable storage medium, where the program, when executed, performs steps including the above method embodiments; and the aforementioned storage medium includes: a removable storage device, a read only memory (ReadOnlyMemory, ROM), a magnetic or optical disk, or other various media capable of storing program code.

The above-described integrated units of the invention, when implemented in the form of software functional units and sold or used as stand-alone products, may also be stored in a computer-readable storage medium. Based on such understanding, the technical solutions of the embodiments of the present invention may be embodied essentially or in part in the form of a software product stored in a storage medium, including instructions for causing a computer device (which may be a personal computer, a server, or a network device, etc.) to perform all or part of the methods described in the embodiments of the present invention. And the aforementioned storage medium includes: various media capable of storing program codes, such as a removable storage device, a ROM, a magnetic disk, or an optical disk.

The present invention is not limited to the above-mentioned embodiments, but is intended to be limited to the following embodiments, and any modifications, equivalents and modifications can be made to the above-mentioned embodiments without departing from the scope of the invention.

Claims (7)

Translated fromChinese

1.融合邻域搜索变异和差分进化的停机位分配方法，其特征在于，包括以下步骤：1. A parking slot allocation method that integrates neighborhood search mutation and differential evolution, which is characterized by including the following steps:S1：获取机场进离港航班和停机位数据；S1: Obtain airport arrival and departure flight and parking space data;S2：构建停机位分配数学模型，包括目标函数模型、约束条件模型以及多目标无量化处理模型；所述目标函数模型根据机场现实运营环境确定，采用差分进化方法进行求解；S2: Construct a mathematical model for parking bay allocation, including an objective function model, a constraint model and a multi-objective non-quantified processing model; the objective function model is determined based on the actual operating environment of the airport and solved using the differential evolution method;所述目标函数模型包括以下几个方面：The objective function model includes the following aspects:（1）旅客步行时间最短：(1) Passengers’ walking time is the shortest:（1）； (1);式中，M_pq为被分配到停机位q上的航班p中旅客的转移人数，D_q为旅客到达停机位q的距离，Z为0-1变量，Z=0代表航班，Z=1代表停机位，Z_pq为0-1变量，Z_pq=0代表航班，Z_pq=1代表停机位，P为航班个数，Q为停机位个数；In the formula, M_pq is the number of transferred passengers on flightp assigned to parking spaceq ,D_q is the distance for passengers to arrive at parking spaceq ,Z is a 0-1 variable,Z =0 represents the flight, andZ =1 represents Parking space,Z_pq is a 0-1 variable,Z_pq =0 represents a flight,Z_pq =1 represents a parking space,P is the number of flights,Q is the number of parking spaces;（2）停机位空闲时间最均衡化：(2) The parking space idle time is most balanced:（2）； (2);式中，T_pq为p航班到达停机位q时停机位q的空闲时间，t_q为机位闲置时间；In the formula,T_pq is the idle time of parking positionq when flightp arrives at parking positionq , andt_q is the idle time of parking position;（3）航班－机位匹配差异最小：(3) Flight-seat matching difference is minimal:（3）； (3);Rho_pq为当前停机位q所能停靠的最大的机型与航班本应该对应的机型的差异度，A表示最大机位；Rho_pq is the difference between the largest aircraft model that can be parked at the current parking spaceq and the aircraft model that the flight should correspond to.A represents the maximum aircraft space;（4）大型机位最充分利用：(4) Maximum utilization of large machine seats:（4）； (4);H_pq为大型停机位上停靠小型飞机以及中型机位停靠的飞机数量；H_pq is the number of small aircraft parked at large parking bays and the number of aircraft parked at medium-sized parking bays;（5）基于机位占用率最高：(5) Based on the highest seat occupancy rate:（5）； (5);式中，为航班p离开停机位q的时间，/>为航班p到达停机位q的时间，K代表24h，Z为0-1变量，Z=0代表航班，Z=1代表停机位，Z_pq为0-1变量，Z_pq=0代表航班，Z_pq=1代表停机位，P为航班个数，Q为停机位个数；In the formula, is the time when flightp leaves parking spaceq ,/>is the time for flight p to arrive at parking space q, K represents 24h,Z is a 0-1 variable,Z =0 represents the flight,Z =1 represents the parking space,Z_pq is a 0-1 variable,Z_pq =0 represents the flight,Z_pq =1 represents the parking space,P is the number of flights,Q is the number of parking spaces;所述目标函数采用无量化处理，采用加权法将多目标问题转换成单目标问题，引入权重因子；The objective function adopts non-quantification processing, uses weighting method to convert multi-objective problems into single-objective problems, and introduces weight factors ;（10）； (10);（11）； (11);设，/>，则经过无量化处理后的目标函数为：set up ,/> , then the objective function after non-quantization processing is:（12）； (12);最终的目标函数如下：The final objective function is as follows:（13）； (13);式中，r₁、r₂、r₃、r₄、r₅均为权重因子，为/>，/>为/>，/>为/>，/>为，/>为/>；In the formula,r₁ ,r₂ ,r₃ ,r₄ ,r₅ are all weight factors, for/> ,/> for/> ,/> for/> ,/> for ,/> for/> ;所述约束条件模型包括以下几方面：The constraint model includes the following aspects:（1）机位唯一性：(1) Uniqueness of the aircraft position:（6）； (6);为航班p被分配到停机位，/>为航班p被分配到停机坪； Flightp is assigned to a parking space,/> Flightp is assigned to the tarmac;（2）机位匹配约束：(2) Camera location matching constraints:（7）； (7);Q_t为机位类型，Q_t为飞机类型；Q_t is the seat type,Q_t is the aircraft type;（3）安全间隔约束：(3) Safety interval constraints:（8）； (8);为上一个飞机p+1到达停机位q的时间，/>为current飞机离开停机位q的时间，sep是安全间隔； is the time when the previous aircraftp +1 arrived at the parking positionq ,/> is the time whenthe current aircraft leaves parking positionq ,sep is the safety interval;（4）近机位优先被分配约束：(4) Constraints on priority allocation of seats near the aircraft:（9）； (9);为近机位，/>远机位，/>为停机坪； It is a position close to the aircraft,/> Remote aircraft position,/> for the apron;S3：随机生成初始化种群，设置参数：包括确定迭代次数、种群大小、初始化代数以及所求问题维数；S3: Randomly generate the initialization population and set parameters: including determining the number of iterations, population size, initialization generation and desired problem dimension;S4：初始化种群；以搜索空间上下限为界，先随机初始化种群再将种群编码为二进制个体；S4: Initialize the population; taking the upper and lower limits of the search space as boundaries, first randomly initialize the population and then encode the population into binary individuals;S5：种群变异、机位交叉、选择优化；计算目标函数值并排序，将排名前60%的个体组成邻域，通过邻域搜索变异机制生成新的优秀个体进入下一代；S5: Population mutation, camera crossover, selection optimization; calculate the objective function value and sort, form a neighborhood with the top 60% of individuals, and generate new outstanding individuals into the next generation through the neighborhood search mutation mechanism;S6：执行“差生升级”策略和个体优化策略使种群得到优化；所述“差生升级”策略为：S6: Implement the "poor student upgrade" strategy and individual optimization strategy to optimize the population; the "poor student upgrade" strategy is:完成变异、交叉和选择后重新计算得到种群适应值再取均值定义为，当前个体X_l的适应值定义为/>，如果/>，则将X_l定义为当前“差生”，然后将X_l升级，如果升级后的“差生”无法确保比当前个体优秀，则将“差生”的位置用当前个体替换；After completing mutation, crossover and selection, recalculate the population fitness value and then take the mean value and define it as , the fitness value of the current individualX_l is defined as/> , if/>,_thendefine_{_}S7：循环S5和S6步骤指定训练轮次，输出最优结果。S7: Loop through steps S5 and S6 to specify training rounds and output the optimal results.2.根据权利要求1所述的融合邻域搜索变异和差分进化的停机位分配方法，其特征在于，S4中，将种群编码为二进制个体的具体方法为：2. The parking space allocation method integrating neighborhood search mutation and differential evolution according to claim 1, characterized in that, in S4, the specific method of encoding the population into binary individuals is:将初始种群由0-1代替原先的浮点型，生成随机数组；Replace the original floating point type with 0-1 in the initial population and generate a random array;用搜索空间上下限规范化随机矩阵，得到维度N×D的随机数组ND；Use the upper and lower limits of the search space to normalize the random matrix to obtain a random array ND of dimension N×D;根据判别条件将每一个向量转换为0-1分布的二进制编码，形成二进制种群x_ij；Convert each vector into a binary code of 0-1 distribution according to the discriminant conditions to form a binary populationx_ij ;随机数组表达式：Random array expression:（14）； (14);搜索空间上下限规范化随机矩阵的表达式为：The expression of the normalized random matrix for the upper and lower limits of the search space is:（15）； (15);随机数组ND为：The random array ND is:（16）； (16);判别条件的表达式为：The expression of the discriminant condition is:（17）； (17);式中，i的大小由种群大小N决定，j的大小由维度D决定，radom_array是由随机函数生成的大小为N×D的随机矩阵，rand( )是一个0-1之间的随机数，lamb是服从高斯分布的随机数，为以行数为N、列数为D的矩阵，radom为返回随机生成的一个实数，它在[0,1)范围内，shape为返回矩阵的维度，up和low为搜索空间的上下限。In the formula, the size ofi is determined by the population sizeN , the size ofj is determined by the dimensionD ,radom_array is a random matrix of size N×D generated by the random function,rand () is a random value between 0-1 number,lamb is a random number obeying Gaussian distribution, is a matrix with N rows and D columns,radom returns a randomly generated real number in the range [0,1), shape is the dimension of the returned matrix, andup andlow are the upper and lower limits of the search space.3.根据权利要求1所述的融合邻域搜索变异和差分进化的停机位分配方法，其特征在于，S5中，种群变异交叉的具体方法为：3. The parking space allocation method integrating neighborhood search mutation and differential evolution according to claim 1, characterized in that, in S5, the specific method of population mutation crossover is:将当前一代的适应值升序，选出排名前60%的个体组成邻域，以扩大邻域搜索变异的力度，数学表达式为：Sort the fitness values of the current generation in ascending order, and select the top 60% of individuals to form a neighborhood to expand the intensity of neighborhood search for variation. The mathematical expression is:（18）； (18);其中，Theta、分别为与迭代次数相关且服从指数分布的参数，/>为第g次迭代邻域内的第m个优秀个体，/>为第g次迭代邻域内第m个变异个体，m、m₁和m₂为取自[1,N-1]之间的随机整数且互不相同；/>、/>分别为第g次迭代邻域内的第m₁、第m₂个优秀个体；/>为当前全局最优的个体，被选入邻域后，指导邻域内个体向最优秀的个体聚拢，进而推动全局优化。Among them,Theta , are parameters related to the number of iterations and obeying exponential distribution,/> is them- th outstanding individual in the g-th iteration neighborhood,/> is them- th mutant individual in theg -th iteration neighborhood,m ,m₁ andm₂ are random integers taken from [1, N-1] and are different from each other;/> ,/> They are them₁ andm₂ outstanding individuals in the g-th iteration neighborhood respectively;/> As the current global optimal individual, after being selected into the neighborhood, it guides the individuals in the neighborhood to gather towards the best individuals, thereby promoting global optimization.4.根据权利要求1所述的融合邻域搜索变异和差分进化的停机位分配方法，其特征在于，S5中，所述机位交叉和选择优化的方法如下：4. The parking space allocation method integrating neighborhood search mutation and differential evolution according to claim 1, characterized in that, in S5, the method of parking space crossover and selection optimization is as follows:机位交叉操作：对于相邻两个停机位－航班对，执行停机位交叉操作，即对其中某两个或者多个停机位交换位置，改变基因序列；Stand crossover operation: For two adjacent parking bays-flight pairs, perform a parking bay crossover operation, that is, exchange positions of two or more parking bays and change the genetic sequence;选择优化操作：将交叉操作后得到的基因序列放入S2中的约束条件模型，判断其是否符合约束条件，然后进行停机位分配模型的目标函数值评估。Select optimization operation: Put the gene sequence obtained after the crossover operation into the constraint model in S2, determine whether it meets the constraint conditions, and then evaluate the objective function value of the parking space allocation model.5.根据权利要求1所述的融合邻域搜索变异和差分进化的停机位分配方法，其特征在于，S6中，所述“差生升级”策略的计算公式如下：5. The parking space allocation method integrating neighborhood search mutation and differential evolution according to claim 1, characterized in that, in S6, the calculation formula of the "differential upgrade" strategy is as follows:(19)； (19);(20)； (20);式中，X_l为当前“差生”，X_m为更新后的“差生”，为最优个体对应的适应值，为最差个体对应的适应值，/>，/>是两个随机抽取的个体，/>，/>，分别为随机抽取个体对应的适应值。In the formula,X_l is the current "poor student",X_m is the updated "poor student", is the fitness value corresponding to the optimal individual, is the fitness value corresponding to the worst individual,/> ,/> are two randomly selected individuals,/> ,/> , They are the fitness values corresponding to randomly selected individuals.6.根据权利要求1所述的融合邻域搜索变异和差分进化的停机位分配方法，其特征在于，所述个体优化策略基于正态分布，计算公式如下：6. The parking space allocation method integrating neighborhood search mutation and differential evolution according to claim 1, characterized in that the individual optimization strategy is based on normal distribution, and the calculation formula is as follows:（21）； (twenty one);(22)； (twenty two);其中，如果</>，将X_u定义为优秀个体，Up，Low为搜索空间的上下限，/>为当前一代全体种群适应值的均值；X_b为个体优化策略后更新得到的个体；X为种群中的普通个体，X服从正态分布；μ表示期望，δ为方差，N表示服从正态分布；公式(21)代表优秀的个体被选中在搜索空间上下限范围内做数学变换，通过比较/>和/>，其中更好的被保留进入下一代。Among them, if </> , defineX_u as an excellent individual,Up and Low are the upper and lower limits of the search space, /> is the meanvalue ofthe fitness valueof theentire population in the current generation;X_b is the individual updated after the individual optimization strategy; ; Formula (21) represents that excellent individuals are selected to undergo mathematical transformation within the upper and lower limits of the search space, through comparison/> and/> , the better of which are retained into the next generation.7.融合邻域搜索变异和差分进化的停机位分配装置，其特征在于，包括至少一个处理器和一个存储器；所述存储器存储有可被所述至少一个处理器执行的指令，所述指令被所述至少一个处理器执行，以使所述至少一个处理器能够执行权利要求1至6中任一项所述的融合邻域搜索变异和差分进化的停机位分配方法。7. A stop allocation device that integrates neighborhood search mutation and differential evolution, characterized in that it includes at least one processor and a memory; the memory stores instructions that can be executed by the at least one processor, and the instructions are The at least one processor executes to enable the at least one processor to execute the parking position allocation method that fuses neighborhood search mutation and differential evolution according to any one of claims 1 to 6.