The Airline Crew Scheduling Problem can be defined as the problem of finding a set of feasible rotations so that the total cost is minimum and all the flight legs are assigned exactly once. Our group has been developing advanced optimization approaches for vehicle routing and crew scheduling at GERAD and CRT in Montréal for the past ten years. A major achievement of the group has been the development of GENCOL, a mathematical column generation based software whose specialization in different areas has enabled us to optimally solve large problems. Specialized version of GENCOL are being used commercially to solve problems in such areas as school busing, transportation of the handicapped, urban transit crew scheduling, truck dispatching, as well as airline crew scheduling. Members of our group have been involved in airline crew scheduling since 1984 when they participated in the development of ICARE for Air France. They have worked on enhancements to ICARE and since 1989 have participated in the development of the newest version of ICARE which incorporates GENCOL. When solving the problem of designing rotations, the column generation approach allows for substantial economies. The reduction is approximately 5% with respect to manual solutions provided by experienced schedulers. These results, obtained over a large number of runs, are for medium and long haul, and schedules of one and two weeks. The majority of these runs involved 300 to 500 flight legs but several runs of over 1000 flight legs were executed. At Northwest Airlines, the preliminary results we have obtained are very encouraging. Tests are currently being conducted on two December 90 problems. For the A-320 case (a 313 flight leg problem), the GENCOL schedule shows, on the ratio of credited hours to block hours, a solution at 8.7% which is an improvement of 4.0% over the Unisys' ALPPS schedule. For the MD-80 case (a 282 flight leg problem), the results are more striking. Here the GENCOL schedule shows a 9.1 improvement (25.7% - 16.1%). These results are even more significant when considered in terms of the annual dollar savings they represent. With regard to airline crew scheduling, we have made a breakthrough: GENCOL is the first software capable of producing optimal solutions to large scale problems. This breakthrough will raise the standard of solution quality expected by airline companies. Our results also demonstrate that mathematical theories and computer power have already reached a level of development which permits software systems to reach optimal solutions to large real life problems.
Published March 1991 , 18 pages
This cahier was revised in April 1991