Airline Crew Scheduling Problem Airlines

Airline Crew Scheduling Problem

Airlines employ tens of thousands of employees that work on hundreds of aircraft flying to thousands of destinations throughout the world. Efficiency is of the utmost importance when it comes to the utilization of a method for airline crew scheduling. Due to the large number of employees that must be organized to work on various flights, crew costs for airlines are generally in the billions, and run second only to the cost of fuel (Anbil et al., 1992). In order to minimize costs and maximize efficiency, systems must find pairings, or tours of duty, that are within legal requirements and also cover every flight leg with the smallest expenditure of money. This problem is known as crew-pairing optimization, and the cost and legal factors involved are determined by complex requirements set by employee contracts and the Federal Aviation Agency (FAA) (Anbil et al., 1992). Researchers have developed certain methodologies for the solution of this complex problem.

There are certain difficulties associated with the construction of crew pairings that is necessary for crew-pairing optimization. These are mainly due to the numerous complex rules set out by the FAA, which govern the legal factors involved in a pairing and the penalties associated with it (Anbil et al., 1992). Many of these rules concern the duration and flying time of a duty period, which is usually restricted to eight hours of flying time within a period of 12 hours of total time on-duty. In addition, between duty periods there is a minimum duration that must be exceeded for overnight rest or layovers

Beyond the legal rules that must be adhered to, there is also a complex cost structure, of which pay and credit are the main components. These pay and credit components encompass the hours of pay that are guaranteed minus the actual number of hours worked, which results in the calculation of several pay guarantees for employees (Anbil et al., 1992). Furthermore, according to Anbil et al. (1992) there are three main causes for costly pay and credit. The first cause is frequent or lengthy breaks within a period of duty. The second cause is extended rests overnight between periods of duty. The final cause of expensive pay and credit is deadheading, where inefficiencies in crew scheduling results in the necessity of crew to travel on flights as passengers from one place to another.

Anbil et al. (1992) explained how crew-pairing optimization requires the consideration of several factors, of which cost and legality are but two. Other considerations for crew scheduling include the number of employees that are available at the various bases of operation, which is known as crew balance. This crew balance is commonly expressed as a minimum and maximum number of available hours per month at each crew base. Another consideration is the general preference to keep crews on the same plane throughout a duty period in order to incur penalties that are administered when crew change plans. A final consideration during the crew optimization process is the general preference for shorter crew-pairings, since longer pairings present difficulties in rescheduling due to unforeseen events, and longer pairings have not been demonstrated to lower operational costs (Anbil et al., 1992). The problem presented by crew-pairing optimization is generally deadheading encountered on a monthly basis, due to adjustments to flight schedules that are required mid-month and schedule transitions from the end of one month to the beginning of the next (Anbil et al., 1992).

Older technology for the process of crew-pairing optimization entailed the solution of several problems sequentially (Anbil et al., 1992). The first problem to be solved was known as the daily problem, which assumed that the flight segments are flown on a daily basis. The examination of this daily problem allowed the overall problem to become more tractable and it also contributed to crew assignment regularity (Anbil et al., 1992).

Beyond the solution of the daily problem, other parts of the overall crew-pairing optimization process included the meeting of crew base constraints, the factoring of weekly exceptions, and the planning of the transition period (Anbil et al., 1992). However, the daily problem was the most central component of the crew-pairing optimization process. The first step in the solution of the daily problem involved the use of a code that that attempted to adapt the daily solution from previous months into the month at hand. Then, another code was used to select and solve a sub-problem so that the initial solution could be improved upon. This latter step consisted of three sub-phases (Anbil et al., 1992). First is the selection of the subproblem, which is instigated by choosing a number of pairings that cover the daily flight segments from all the available pairings. This results in the sub-problem consisting of segments that are covered by the newly chosen set of pairings, which leads to the second phase, pairing generation. This phase takes the smaller number of segments from the first phase and generates all possible pairings. At this phase, legality and cost are factored in to the solution of the problem. The final phase of improving the initial solution is the actual optimization phase, in which new pairings that are more effective and less costly replace the older pairings (Anbil et al., 1992).

A simple example of the methodology involved in the solution of airline crew scheduling problems is demonstrated in the following excerpt borrowed from Trick (1996):

Suppose an airline has three planes based in Atlanta...One plane goes between Atlanta and Miami with the following schedule:

A: Atl -- Mia 8:30-9:30

B: Mia -- Atl 10:00-11:00

C: Atl -- Mia 11:30-12:30

D: Mia -- Atl 1:00-2:00

E: Atl -- Mia 2:30-3:30

F: Mia -- Atl 4:00-5:00

The second plane flies between Atlanta and New York on the following schedule:

G: Atl -- N.Y. 9:30-11:30

H: N.Y. -- Atl 12:00-2:00

I: Atl -- N.Y. 2:30-4:30

J: N.Y. -- Atl 5:00-7:00

Finally, the third plane goes on a Atlanta, New York, Memphis, Atlanta trip as follows:

K: Atl -- N.Y. 9:00-11:00

L: N.Y -- Mem 11:30-12:30

M: Mem -- Atl 12:45-2:00

N: Atl -- N.Y. 2:30-4:30

O: N.Y. -- Mem 5:00-6:00

P: Mem -- Atl 6:15-7:30

Here are a few possible pairings.

AB with cost.75

KLM with cost 1.00

KLMNOP with cost 2.00

Here are two schedules: