Scheduling Problem For Landing Aircraft Based On Genetic Simulated Annealing Algorithm

With the continuous development of national economy and the increasing popularity that China gets in the world, the number of civil aviation grows rapidly in China. And the phenomenon of air crowding becomes more and more serious. Especially in some busy airport, flight delays often happen. These not only bring great economic losses and reputation losses to the airlines, but also affect passengers’travel safety. In order to solve the increasingly serious phenomenon of air traffic congestion, this paper introduced the mathematical modeling of flight scheduling problem which is based on genetic algorithm. The flight scheduling problem of single runway get full analysis and research.On the basis of referring to domestic and foreign related researches, this paper mainly sets up model for single runway flight scheduling problem. This article first introduces the related knowledge of traffic management in terminal area, including basic concepts of terminal area, flight process, flight scheduling etc. Second, on the basis of considering the minimization of flight delay cost, flight scheduling mathematical programming model is established. And then it carries on the simulation analysis and the the evaluation by using the first come first service algorithm. Finally, it sets up the flight scheduling model based on genetic simulated annealing algorithm. Main design thoughts of genetic simulated annealing algorithm are shown as the following:(1) It adopts the way of integer serial number coding in genetic algorithm, with the actual landing order of flight as chromosome’s gene values. And then decode chromo-somes to generate actual arrival time of flights. The main idea of decoding is shown as follows. For any chromosome chrom= (χ1; χ2,···χN), in order to ensure that the total loss is minimum, set the actual arrival time of the flight χ1which is the first to land to be its object arrival time; And then, for the flight χ2 which is the second to land, delete the time which can not meet the time interval with the flight χ1 from the earliest arrive time and the latest arrive time. Then, select the time which has the minimum distance with the target arrival time of flight χ2 from the above time as the real arrival time of flight χ2;And then,for the flight x3 which is the third to land, delete the time which can not meet the time interval with the flight χ1,and the flight χ2 from the earliest arrive time and the latest arrive time. Then, select the time which has the minimum distance with the target arrival time of flight χ3 from the above time as the real arrival time of flight χ3; We can deduce the rest from this to get real arrival times of all the flights. So, the job of decoding chromosomes chrom is done. At last, solve the objective function value objv of the individual reach after decoded.(2) Use the the selection, crossover and mutation operations and so on for the initial population of chromosomes. Selection operation uses random traversal sampling algorithm SUS. Sets the number of offspring chromosomes to Nsel. The specific means of SUS is shown as below. Randomly arrange the fitness of population and generate a random number as a pointer in [0, SUM/Nsel], and generate Nsel pointers apart SUM/Nsel,and then select the individual fitness which range on the pointer. Relative to the roulette wheel selection operation, SUS algorithm not only has lower time complexity, but also the optimal zero deviation, minimum individual extensions.(3) The crossover operation use the method of two-point crossover. First, use of the principle of two matching two pairs to match the chromosomes in offspring. Then, determine whether or not they can use the crossover operation, on the next, generate two random integer as cross location,and exchange of genes in cross position for the chromosomes through crossover probability Pc. Finally, by using the method of part mapping, eliminate duplicate genes in chromosome to end up with feasible chromosomes.(4) The mutation operation adopt the method of single point mutation. Exchange the genes in certain two position of the chromosome through mutation probability Pm(5) Decode the new individual Selch through the selection, crossover and mutation operation. Solve the objective function value newobjv of the individual newreach de-coded. And then, adjust the individual decoded and calculate the new objective function value.(6) through the use of genetic operation above, the simulated annealing algorithm is added. Use Metropolis criteria to judge the new solution. The current solution is reachi The new solution is newreachi. The current temperature is T. The objective function value of solutions are respectively objv, newobjv. The increment df= newobjvi-objviThe Metropolis criterion is shown as below. If df> 0,accept the new solution in probability 1; Otherwise, accept the new solution in the probability of exp(-T/df),abandoning the old solution.Based on the above consideration and design, this paper has established the flight landing scheduling model based on genetic simulated annealing algorithm. Through the simulation analysis of single runway flight scheduling problem, it proves the effectiveness of the genetic simulated annealing algorithm. Compared with the first come first service algorithm, genetic simulated annealing algorithm can reduce the cost of flight delays much better. And the adaptability of the algorithm is wider, and it can be suitable for different objective functions and constraint conditions and so on.