Multi-objective dynamic programming algorithm for aircraft arrival sequencing and runway scheduling

Optimization of runway scheduling for aircraft landings plays an important role in modern air traffic control, by maximizing throughput of an airport and minimizing fuel cost of aircrafts. As a nondeterministic polynomialcomplete(NP-C) problem, the runway scheduling of a considerable number of aircrafts in a multirunway airport hasn't been effectively solved. Because of considerable computation required by the traditional dynamic programming algorithm under constrained position shifting(CPS), we can only sequence aircrafts and schedule the time of arrival in a single-runway airport. This paper presents a new dynamic programming algorithm by changing the way of recurrence and combining the traditional one with several other methods including a greedy algorithm. Our algorithm can solve the problem of multirunway scheduling with multi-object efficiently and effectively. A large number of experiments show that the complexity of the algorithm is almost linearly proportional to the number of aircrafts, and the algorithm can optimize both throughput and landing cost simultaneously in a short period of time.