Premium
Exact solution of crew scheduling problems using the set partitioning model: Recent successful applications
Author(s) -
Marsten Roy E.,
Shepardson Fred
Publication year - 1981
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230110208
Subject(s) - crew scheduling , benders' decomposition , subgradient method , lagrangian relaxation , mathematical optimization , crew , computer science , scheduling (production processes) , implementation , heuristic , operations research , relaxation (psychology) , integer programming , set (abstract data type) , lagrangian , decomposition , mathematics , engineering , psychology , social psychology , aeronautics , programming language , ecology , biology
The set partitioning model of the crew rotation problem has been well known for many years. This paper focuses on recent developments that have made this model more attractive and have resulted in several successful implementations. These developments include improved problem conceptualizations and decompositions, as well as new solution techniques employing Lagrangian relaxation and subgradient optimization. Experience is reported from The Flying Tiger Line, Pacific Southwest Airways, Continental Airlines, and Helsinki City Transport. A case is made for work on heuristic decomposition methods to break large problems into moderate sized pieces that can be solved exactly.