, 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

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:

AB, CD, EF, GH, IJ, KLM, NOP for total cost 6.25

ABCDEF, GHIJ, KLMNOP for total cost 6.00

Is there a cheaper combination available? In order to be certain, we would have to check all pairings. Let's suppose we could list all pairings. We can http://mat.gsia.cmu.edu/mstc/decomp/img14.gif be 1 if we use pairing j. This leads to the following integer program:

http://mat.gsia.cmu.edu/mstc/decomp/img115.gif

Subject to The preceding example was quoted from Trick, M. "Airline Crew Scheduling" 1996, (http://mat.gsia.cmu.edu/mstc/decomp/node5.html)

Improvements and innovations have been developed to further improve crew-pairing optimization. For example, CALEB technologies (Computer Applications in Logistics Engineering and Business has developed several systems for the solution of scheduling problems (Business Wire, 2001). These systems include the OpsSolver and CrewSolver systems, which assist airlines in quickly rescheduling crew and aircraft following disruptions in service, as well as the ManpowerSolver and PairingSolver systems, which optimize the planning and scheduling of flight crews for both the short- and long-term (Business Wire, 2001). As technology continues to progress and improve, so will systems that maximize the efficiency and minimize costs through effective scheduling of airline crews.

Reference

Trick, M.A."Airline Crew Scheduling." A Consultants Guide to Solving Large Problems September 11, 1996, http://mat.gsia.cmu.edu/mstc/decomp/node5.html.

AirTran Airways Selects PairingSolver Software From CALEB Technologies; Revolutionary Crew Planning System Boosts Operating Efficiency." Business Wire. December 17, 2001.

Anbil, R., Tanga, R., Johnson, E.L. "A global Approach to Crew-Pairing Optimization." IBM Systems Journal 31 (1992): 62-70.