Airline crew scheduling: A new formulation and decomposition algorithm
成果类型：
Article
署名作者：
Vance, PH; Barnhart, C; Johnson, EL; Nemhauser, GL
署名单位：
Massachusetts Institute of Technology (MIT); University System of Georgia; Georgia Institute of Technology
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.45.2.188
发表日期：
1997
页码：
188-200
关键词：
摘要：
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.