Research And Implement On Air Traffic Rerouting System Based On DRDG Model

In the air traffic management, rerouting is a special kind of resource allocation and scheduling problem. Rerouting includes determining the departure time and searching the shortest path for flights, and its target is minimizing the total delay. In this paper, the research focuses rerouting problem, and establishes DRDG (Dynamic Rerouting Dynamic Ground holding) model. Reroute is a NP-Hard problem, thus we solving it with the hybrid heuristic algorithm in this paper.Due to rerouting needs to decide the departure time and the shortest path, we invent multiple rerouting algorithm, which combines genetic algorithm with the MDA* algorithm, and uses the two algorithms to solves the sub problem dividedly. Considering the interaction between the two sub problems, the reciprocal of result which calculated by MDA* is used as the fitness function of the genetic algorithm. In the end, we use the hybrid multiple rerouting algorithm to solve the model, and get the global optimal solution in a certain probability.In the issue of finding the shortest path, first we prove that the air traffic map meets the FIFO principle according to the rules of air traffic. Then we resolve the air holding issue. At last we settle the shortest path problem with MDA* algorithm. At the issue of determine the departure time, first we divide the monitor time into several time slots. Then we divide the time slot into several time slices according to MIT (Miles-In-Trail). On the final, we encode the ground delay based on the Slot window mechanism, and combine MDA* algorithm with determine departure time for flights.At the end of this paper, we implement the reroute system with the VC compiler. By using the real flight data and aeronautical charts, we test and verify the algorithm mentioned above. On the other hand, we solve this model with CPLEX. Comparing the time and results between multiple rerouting algorithm and CPLEX. We get the following conclusions:â‘ Multiple rerouting algorithm has advantage in solving the time;â‘¡when the weather change abruptly, Multiple rerouting algorithm has advantage in total delay.