The operational airline crew scheduling problem

被引:76
作者
Stojkovic, M [1 ]
Soumis, F
Desrosiers, J
机构
[1] Grp Etud & Rech Anal Decis, Montreal, PQ H3T 1V6, Canada
[2] Ecole Polytech, Montreal, PQ H3T 1V6, Canada
[3] Ecole Hautes Etud Commerciales, Montreal, PQ H3T 1V6, Canada
关键词
D O I
10.1287/trsc.32.3.232
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
This paper describes the operational airline crew scheduling problem and represents a first published attempt to solve it. The problem consists of modifying, as necessary, personalized planned monthly assignments of airline crew members during day-to-day operations. It requires covering, at minimal cost, all flight segments from a given time period with available crew while minimizing the disturbances of crew members. To generate modified pairings for selected crew members, both the classical crew pairing problem and the problem of constructing personalized monthly assignments must be treated simultaneously. An. optimization approach is proposed for the problem in which the flight schedule is fixed and represents input data. The problem is mathematically formulated as a Set Partitioning type problem, and a column generation method embedded in a branch-and-bound search tree has been implemented to solve it. Good results, from the point of view of both solution times and achieved objectives, have been obtained on generated test problems. Because the solution time is reasonable, several different scenarios of the same problem may be solved. A final decision can, then be made by considering all scenarios and choosing the one whose solution is the best in the given situation.
引用
收藏
页码:232 / 245
页数:14
相关论文
共 30 条
[1]   RECENT ADVANCES IN CREW-PAIRING OPTIMIZATION AT AMERICAN-AIRLINES [J].
ANBIL, R ;
GELMAN, E ;
PATTY, B ;
TANGA, R .
INTERFACES, 1991, 21 (01) :62-74
[2]  
[Anonymous], 1994, Optimization in industry
[3]  
Baker E. K., 1985, TRANSPORTATION POLIC, V3, P95
[4]   A GRAPH PARTITIONING APPROACH TO AIRLINE CREW SCHEDULING [J].
BALL, M ;
ROBERTS, A .
TRANSPORTATION SCIENCE, 1985, 19 (02) :107-126
[5]   DEADHEAD SELECTION FOR THE LONG-HAUL CREW PAIRING PROBLEM [J].
BARNHART, C ;
HATAY, L ;
JOHNSON, EL .
OPERATIONS RESEARCH, 1995, 43 (03) :491-499
[6]  
BYRNE J, 1988, AGIFORS S P, V28, P87
[7]  
CAPRARA A, 1995, MODELS ALGORITHMS CR
[8]  
CRAINIC TG, 1987, INFOR, V25, P136
[9]   Crew pairing at Air France [J].
Desaulniers, G ;
Desrosiers, J ;
Dumas, Y ;
Marc, S ;
Rioux, B ;
Solomon, MM ;
Soumis, F .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1997, 97 (02) :245-259
[10]  
Desaulniers G, 1998, FLEET MANAGEMENT AND LOGISTICS, P57