Crew pairing at Air France

被引:110
作者
Desaulniers, G
Desrosiers, J
Dumas, Y
Marc, S
Rioux, B
Solomon, MM
Soumis, F
机构
[1] ECOLE POLYTECH, DEPT MATH & GENIE IND, MONTREAL, PQ H3C 3A7, CANADA
[2] ECOLE HAUTES ETUD COMMERCIALES, MONTREAL, PQ, CANADA
[3] AD OPT TECHNOL INC, MONTREAL, PQ, CANADA
[4] AIR FRANCE, PARIS, FRANCE
[5] NORTHEASTERN UNIV, COLL BUSINESS ADM, MANAGEMENT SCI GRP, BOSTON, MA 02115 USA
基金
加拿大自然科学与工程研究理事会;
关键词
crew pairing; integer nonlinear programming; multi-commodity flow model; Dantzig-Wolfe decomposition; set partitioning;
D O I
10.1016/S0377-2217(96)00195-6
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
In the airline industry, crew schedules consist of a number of pairings, These are round trips originating and terminating at the same crew home base composed of legal work days, called duties, separated by rest periods, The purpose of the airline crew pairing problem is to generate a set of minimal cost crew pairings covering all flight legs, The set of pairings must satisfy all the rules in the work convention and all the appropriate air traffic regulations, The resulting constraints can affect duty construction, may restrict each pairing, or be imposed on the overall crew schedule. The pairing problem is formulated as an integer, nonlinear multi-commodity network flow problem with additional resource variables. Nonlinearities occur in the objective function as well as in a large subset of constraints. A branch-and-bound algorithm based on an extension of the Dantzig-Wolfe decomposition principle is used to solve this model. The master problem becomes a Set Partitioning type model, as in the classical formulation, while pairings are generated using resource constrained shortest path subproblems, This primal approach implicitly considers all feasible pairings and also provides the optimality gap value on a feasible solution. A nice feature of this decomposition process is that it isolates all nonlinear aspects of the proposed multi-commodity model in the subproblems which are solved by means of a specialized dynamic programming algorithm. We present the application and implementation of this approach at Air France. It is one of the first implementations of an optimal approach for a large airline carrier We have chosen a subproblem network representation where the duties rather than the legs are on the arcs, This ensures feasibility relative to duty restrictions by definition, As opposed to Lavoie, Minoux and Odier (1988), the nonlinear cost function is modeled without approximations. The computational experiments were conducted using actual Air France medium haul data. Even if the branch-and-bound trees were not fully explored in all cases, the gaps certify that the computed solutions are within a fraction of one percentage point of the optimality. Our results illustrate that our approach produced substantial improvements over solutions derived by the expert system in use at Air France, Their magnitude led to the eventual implementation of the approach.
引用
收藏
页码:245 / 259
页数:15
相关论文
共 35 条
[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]  
ARABEYRE J., 1969, TRANSPORT SCI, V3, P140, DOI [10.1287/trsc.3.2.140, DOI 10.1287/TRSC.3.2.140]
[4]  
Baker E. K., 1985, TRANSPORTATION POLIC, V3, P95
[5]   A GRAPH PARTITIONING APPROACH TO AIRLINE CREW SCHEDULING [J].
BALL, M ;
ROBERTS, A .
TRANSPORTATION SCIENCE, 1985, 19 (02) :107-126
[6]   DEADHEAD SELECTION FOR THE LONG-HAUL CREW PAIRING PROBLEM [J].
BARNHART, C ;
HATAY, L ;
JOHNSON, EL .
OPERATIONS RESEARCH, 1995, 43 (03) :491-499
[7]  
BARUTT J, 1990, SIAM NEWS, V23, P20
[8]  
BARUTT J, 1990, SIAM NEWS, V23, P1
[9]  
BORNEMANN DR, 1982, 22 AGIFORS CREW MAN
[10]  
CARTER H, 1995, BANG BRANCH GENERATE