Heuristic Mixed Integer Linear Programming For Flight Conflict Resolution

With the rapid development of the global economy,as well as IT and e-commerce,the global civil aviation industry also has entered a period of rapid development with the explosive growth of air transport volume.In the case of limited airspace,the contradiction between the surge of air traffic flow and limited airspace resources is becoming increasingly prominent under the current air traffic control mode.In order to resolve the problems of insufficient airspace,increase of air traffic flow,heavy burden of air traffic controllers and uncertainty of the air traffic safety,Next Generation Air Transportation System(NextGen)and Single European Sky ATM Research(SESAR),as the new air traffic control system proposed by the United States and Europe respectively,focus on trajectory-based operation(TBO)and transform the existing airspace-based operation mode to trajectory-based operation mode.For the newly proposed trajectory-based operation,the flight trajectory of each aircraft needs to be planned uniformly,so it is necessary to provide a better flight conflict resolution approach.How to improve the solving efficiency and decrease the resolution cost to take full advantage of the limited airspace is the focus of current research.In this paper,the above issues are studied,the main contents and research results are as follows:(1)The background and research status of the existing flight conflict resolution problem,including the usage of different objective functions as indicators for measuring the optimality of conflict resolution problem,and different strategies for modelling conflict resolution problem are reviewed.A phased solution strategy based on the idea of dynamic programming is proposed.Firstly,a phased solution strategy is adopted.This approach provides an optimal flight rate for each aircraft.The optimal results obtained by this method are taken as a new search domain.The mixed integer linear programming problem established by Antonio et al.is introduced and further solved.The results are much lower than those of the discretization strategy of angle range proposed by Antonio et al.The solution time is reduced and the cost of conflict resolution is slightly increased.The advantages and disadvantages of this method are further analyzed and demonstrated.(2)It is necessary to improve the rapidity of the previously proposed heuristic approach based on dynamic programming for meeting the requirement of real-time.Since the problem of directional conflict cannot be solved only by changing the speed,a near real-time conflict resolution strategy for multi-aircraft flight is proposed based on the idea of calculating the optimal heading angle by stages.The idea not only ensures the resolution of the conflict resolution problem,but also improves the solution efficiency and can solve most of the flight conflict problems in the first stage.(3)Compared with the angle range discretization method proposed by Antonio et al.,the optimality of near real-time multi-aircraft conflict resolution strategy is slightly insufficient.In order to compensate the optimality,the idea of grouping to solve the optimal heading angle is introduced,and then the multi-aircraft conflict resolution strategy of "grouping method" is proposed.The number of aircrafts at each stage is optimized from one to a group,and aircraft in each group uses the same deflection angle.This method restores the partial optimality of conflict resolution,makes the cost of resolution more obviously optimized,and still guarantees the rapidity of conflict resolution.Finally,the main work of this paper is summarized,some ideas and methods for the further study of flight conflict resolution are discussed.