Research On Hub Airport Gate And Runway Combinatorial Optimization Model And Algorithms

Gates and runways are important resources to inbound and outbound flights of a civil aviation airport.It's of great significance to optimize gate and runway assignment to reduce flights' taxiing time for improving the airport's operating efficiency,and reducing operating costs of airlines and flight delays.Gate and runway combinatorial assignment is a typical combinatorial optimization problem for which it is difficult to find an optimum solution using the traditional deterministic algorithms(such as branch and bound,dynamic programming,etc.).Therefore,a feasible approach is to use heuristic intelligent optimization algorithms.These methods can find an optimal solution in polynomial time.Particle swarm optimization algorithm has been successfully used to solve many NP-hard problems such as job shop scheduling problem.It has a great potential in solving combinatorial optimization problems.Therefore,this paper has studied gate and runway combinatorial optimization on the basis of particle swarm optimization.This paper,from the perspective of reducing the average taxi time of the flight,considers the gates and runways allocation strategy.Based on a variety of constraints,a gate and runway combinatorial optimization model is proposed.Inspired by simulated annealing and the genetic algorithm,a hybrid discrete particle swarm algorithm based on flight sequence encoding scheme and a discrete particle swarm algorithm based on gate and runway combinational sequence vector encoding scheme are separately proposed by redefining the position vector,speed and location update strategy.Experiments using simulation data and real data are separately performed,the result of which has verified the rationality of the model and the effectiveness of both algorithms.Comparisons have been made between both algorithms.Then,real-data experiment is performed on the parameters characteristics of the discrete particle swarm algorithm based on gate and runway combinational sequence vector encoding scheme and guidelines of parameters selection are provided.