Airline crew scheduling: A new formulation and decomposition algorithm

被引:98
作者
Vance, PH
Barnhart, C
Johnson, EL
Nemhauser, GL
机构
[1] MIT,CAMBRIDGE,MA 02139
[2] GEORGIA INST TECHNOL,ATLANTA,GA 30332
关键词
D O I
10.1287/opre.45.2.188
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
Airline crew scheduling is concerned with finding a minimum cost assignment of flight crews to a given flight schedule while satisfying restrictions dictated by collective bargaining agreements and the Federal Aviation Administration. Traditionally, the problem has been modeled as a set partitioning problem. in this paper, we present a new model based on breaking the decision process into two stages. In the first stage we select a set of duty periods that cover the flights in the schedule. Then, in the second stage, we attempt to build pairings using those duty periods. We suggest a decomposition approach for solving the model and present computational results for test problems provided by a major carrier. Our formulation provides a tighter linear programming bound than that of the conventional set partitioning formulation but is more difficult to solve.
引用
收藏
页码:188 / 200
页数:13
相关论文
共 25 条
[1]   APPLYING INTEGER LINEAR-PROGRAMMING TO THE FLEET ASSIGNMENT PROBLEM [J].
ABARA, J .
INTERFACES, 1989, 19 (04) :20-28
[2]   RECENT ADVANCES IN CREW-PAIRING OPTIMIZATION AT AMERICAN-AIRLINES [J].
ANBIL, R ;
GELMAN, E ;
PATTY, B ;
TANGA, R .
INTERFACES, 1991, 21 (01) :62-74
[3]  
ANBIL R, 1991, IBM SYST J, V31, P71
[4]  
ANBIL R, 1993, OPTIMIZATION IND, P31
[5]  
[Anonymous], THESIS GEORGIA I TEC
[6]  
ARABEYRE J., 1969, TRANSPORT SCI, V3, P140, DOI [10.1287/trsc.3.2.140, DOI 10.1287/TRSC.3.2.140]
[7]  
BARNHART C, 1995, TELECOMMUN SYST, V3, P239
[8]  
BARNHART C, 1994, OPTIMIZATION IND, V2
[9]  
BARUTT J, 1990, SIAM NEWS, V23, P19
[10]  
CPLEX Optimization Inc., 1990, US CPLEX LIN OPT