EFFICIENT HEURISTIC SOLUTIONS FOR THE AIRLINE CREW SCHEDULING PROBLEM

n this dissertation, efficient heuristic solution procedures are proposed, developed and tested for the airline crew scheduling problem. Airline crew scheduling involves the formation of crew schedules, called pairings, which supply flight crew personnel for each of the airlines' aircraft flights. Each pairing consists of a sequence of airborne trips between origin/destination city pairs. Each airborne trip is called a flight leg. The first flight leg in the pairing must depart from the crew member's home base; the last flight leg must return to that base. In addition, each pairing must be constructed so that no Federal Aviation Regulations, labor agreements, or company policies are violated. Given a method of assigning a cost to each crew pairing, the airline crew scheduling problem is to find the set of legal crew pairings which covers all the aircraft flight legs at a minimum total cost.;(DIAGRAM, TABLE OR GRAPHIC OMITTED...PLEASE SEE DAI); c(,j) = cost of pairing j; x(,j) = 1, if pairing j is used in the solution;Traditionally, the airline crew scheduling problem has been formulated as the following set covering model:; = 0, otherwise; n = number of pairings; a(,ij) = 1, if flight leg i is used on pairing j; = 0, otherwise; m = number of flight legs;The optimal solution to this model for problems of 1000 flight legs requires several hours of computing time. In order to produce near-optimal results in one hour of computing time on a Burroughs 6700 mainframe, heuristic solution procedures need to be employed.;These procedures are heuristic in the sense that optimality is neither claimed nor proved for the solutions which are obtained. Experience with crew pairing problems has shown, however, that many different pairing configurations may yield optimal or near-optimal results. This research demonstrates that heuristic procedures may be used to generate near-optimal results and that significant cost savings can be obtained.;Using aircraft flight schedules and operational constraints supplied by the Federal Express Corporation, crew pairing solution procedures were developed for two distinct air route network configurations. The first network represents the single hub/single domicile system currently in use at Federal Express. In this system all aircraft and flight crews are based at a central hub: Memphis, Tennessee. The aircraft routes of this system extend radially from Memphis in a pattern which resembles the hub and spokes of a wheel. By exploiting this special structure, crew scheduling heuristics were developed which can generate near-optimal solutions to 1000 flight leg problems in less than one hour of computer time. Computational results are presented in which the solution produced by the scheduling model was 3658 credit minutes per week less than the schedule actually operated by Federal Express. At a cost of ;The second network configuration considered was a multiple hub/multiple domicile system. Since, at the present time, the final version of the Federal Express multiple hub system is not formally defined, several two, four, and five hub data sets were evaluated. Within the conventional set covering formulation of the crew pairing problem, a heuristic set covering algorithm and solution improvement techniques were used to obtain near optimal results within the one hour time constraint. Computational results for the various multiple hub scenarios are presented. In the case of the four hub system the solution produced by the scheduling model was 639 credit minutes per week less than the solution produced by a commercially available crew scheduling code. For this system of B727 flights, each crew credit minute costs approximately...