Method and system for generating optimal solutions for open pairings through one-way fixes and matching transformations

Abstract

Open Pairings occurring during airline operations are repaired n at a time (where n is an integer) in near real time through use of two solution paths, one involving one-way fixes, and the other matching transformations. From the resulting multiple solutions, one is selected which is of least cost to the airline.

Description

RELATED APPLICATION[0001]U.S. patent application Ser. No. 09 / 364,154, now U.S. Pat. No. 6,408,276 for “Crew Optimization Engine For Repair Of Pairings During Irregular Aircraft Operations”, assigned to the assignee of the present invention.FIELD OF THE INVENTION[0002]The invention relates generally to decision support tools, and more particularly to a method and system for generating optimized solutions in near real time to cure irregularities in n crew / flight pairings through two solution paths, namely an integer program data structure and a matching transformation.BACKGROUND OF THE INVENTION[0003]Major U.S. airlines operate up to 5,000 flights per day, and have to contend with crew recovery problems when a scheduled pairing of crew members with a sequence of flights is broken. Such broken pairings may occur when crew members do not report to work due to illness or other circumstances, restrictions on flight time are exceeded by a crew member, a flight is delayed or canceled, a fli...

AI Technical Summary

Benefits of technology

[0033]In another aspect of the invention, upon determining all deadhead paths among the n pairings, all possible partial self-fix solution components based upon the above deadhead paths are determined among the n pairings. Next, all possible one-way fix solution components are determined. The resulting problem model is operated upon by an integer program for formatting the problem into the integer program data structure for solution by an optimization solder. The above formatting reduces an open pairing problem of high complexity which may be insolvable, into a less complex open pairing problem which is readily solvable.

[0034]In still another aspect of the invention, upon determining all deadhead paths among the n pairings, all possible one-way and two-way swaps based upon such deadhead paths are generated. A matching transformation then is applied to the resulting open pairing problem model to provide a simplified weighted matching problem from which solutions complying with the legalities may more easily be generated.

Problems solved by technology

Major U.S. airlines operate up to 5,000 flights per day, and have to contend with crew recovery problems when a scheduled pairing of crew members with a sequence of flights is broken.

In going through each of these iterations for any normal airline irregular operation problem, the costs in terms of solving time can be very expensive and impractical to support a decision making in a real time environment.

Problems with crew members, however, are detected as the result of current operation analysis.

Since flights f13 and f14 are left open without a crew, however, such a solution may be too costly for an airline.

The cost to the airline would include the deadhead costs as well as the cost of the open flights in P2.

The above methods as presented in U.S. patent application Ser. No. 09 / 364,156 are limited in the number of pairings which may be called upon to provide solutions, and are subject to a condition where due to the limited resources, deadhead paths may not be available to effect a one-way, two-way, or three-way swap.

Further, as in the example illustrated by FIG. 3 above, a three-way swap may prove too costly to an airline.

A further deficiency in the above system is that with an ever increasing need for more rapid solution generation, improvements over decision tree selection processes, and depth-first-search and shortest-path algorithms is needed.

Images