Runway sequencing with holding patterns

被引:41
作者
Artiouchine, Konstantin [1 ,2 ]
Baptiste, Philippe [1 ]
Durr, Christoph [1 ]
机构
[1] Ecole Polytech, LIX, F-91128 Palaiseau, France
[2] Domaine Corbeville, Thales TRT, F-91404 Orsay, France
关键词
air-traffic control; scheduling; mixed integer programming;
D O I
10.1016/j.ejor.2006.06.076
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
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. (C) 2007 Elsevier B.V. All rights reserved.
引用
收藏
页码:1254 / 1266
页数:13
相关论文
共 20 条
[1]   SCHEDULING JOBS WITH FIXED START AND END TIMES [J].
ARKIN, EM ;
SILVERBERG, EB .
DISCRETE APPLIED MATHEMATICS, 1987, 18 (01) :1-8
[2]  
Baptiste P., 1999, Journal of Scheduling, V2, P245, DOI 10.1002/(SICI)1099-1425(199911/12)2:6<245::AID-JOS28>3.0.CO
[3]  
2-5
[4]  
Baptiste P., 2001, CONSTRAINT BASED SCH
[5]  
BARNIER N, P 2 INT C EXH PRACT
[6]  
Bayen AM, 2003, P AMER CONTR CONF, P4620
[7]  
BAYEN AM, MILP FORMULATION POL
[8]  
BAYEN AM, P 43 IEEE C DEC CONT
[9]  
CARLIER J, 1984, THESIS U PARIS, V6
[10]   Scheduling jobs of equal length: Complexity, facets and computational results [J].
Crama, Y ;
Spieksma, FCR .
MATHEMATICAL PROGRAMMING, 1996, 72 (03) :207-227