Portal de Periódicos da CAPES

Runway sequencing with holding patterns

2007; Elsevier BV; Volume: 189; Issue: 3 Linguagem: Inglês

10.1016/j.ejor.2006.06.076

1872-6860

Konstantin Artiouchine, Philippe Baptiste, Christoph Dürr,

Constraint Satisfaction and Optimization

We study a scheduling problem, motivated by air-traffic control. When aircraft reach the final descent in the “Terminal Radar Approach CONontrol” area (tracon), a set of disjoint time windows in which the landing is possible, can be automatically assigned to each aircraft. The objective is then to determine landing times, within these time windows, which maximize the minimum time elapsed between consecutive landings. We study the complexity of the problem and describe several special cases that can be solved in polynomial time. We also provide a compact Mixed Integer Programming formulation that allows us to solve large instances of the general problem when all time windows have the same size. Finally, we introduce a general hybrid branch and cut framework to solve the problem with arbitrary time windows. Experimental results show that our approach outperforms earlier formulation of the problem.