Data processing: financial – business practice – management – or co – Automated electrical financial or business practice or... – Operations research or analysis
Reexamination Certificate
1999-07-30
2002-06-18
Hafiz, Tariq R. (Department: 2163)
Data processing: financial, business practice, management, or co
Automated electrical financial or business practice or...
Operations research or analysis
C705S002000, C705S002000, C701S202000
Reexamination Certificate
active
06408276
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to decision support tools generally, and more particularly to an automated, real time system for curing crew problems arising from irregular airline operations as well as for analysis under any what-if scenarios.
BACKGROUND OF THE INVENTION
Airline operations may be disrupted by numerous perturbations including weather problems, aircraft mechanical problems, and air traffic control (ATC) problems. When under the influence of such perturbations, the airline is said to experience irregular operations, which may result in flight delays, flight cancellations, flight diversions, equipment substitutions, and crew rescheduling.
The crew rescheduling involves matching crews with a recovery flight schedule and acceptable fleet type as soon as possible in a cost effective way, while ensuring conformance with crew legalities such as the FARs (Federal Aviation Regulations), union contracts, and company policies.
The following published articles are of general interest: “Optimization Model and Algorithm for Crew Management During Airline Irregular Operations”, by Guo Wei, Gang Yu, and Mark Song, Journal Of Combinatorial Optimization, Kluwer Academic Publishers (1997); and “A Decision Support Framework for Crew Management During Airline Irregular Operations”, by Mark Song, Guo Wei, and Gang Yu, Operations Research In The Airline Industry, Kluwer Academic Publishers (1998).
The algorithms described in the above publications are very similar. The main features of these algorithms are their use of the space-time network model, in which problems with irregular operation can be physically represented by a network using four types of nodes and five types of network arcs. As a result of this network representation, a mathematical model can be formulated to reflect the problem at hand.
For relatively small problems (number of cities less than 10, number of pairings less than 5, number of flights less than 20), use of the model can achieve an optimal solution. If the size of a problem increases, however, a heuristic method has to be applied in order to get an acceptable solution. The heuristic methods described in these two publications are centered at the decomposition of the given problem, so that a large problem can be divided into a number of smaller problems such that each smaller problem contains exactly one broken pairing.
For each smaller problem, the algorithm calls for setting up a sub-network, solving a shortest path network and using a depth-first search method to fix a broken pairing. 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 decision making in a real time environment.
In the current invention, Directly-Connected and Indirectly Connected, and Extend-Out Methods are used to first preprocess a problem. These preprocessing methods prove to be very effective in reducing problem size by fixing a large portion of problems. Swap Methods also are used to further fix a problem and improve solution quality. A problem is decomposed into smaller problems by either looking at a pairing of broken parings, or a group of three parings to fix. Finally, the current invention sets up a network of open flights, and uses the depth-first-search algorithm to match the solutions from the decomposed problem to yield solutions for the overall problem. Also, a shortest path method is applied iteratively to generate open pairings based on the open flights. However, the network is generated only once, and during each iteration only the costs of the network need to be reset. This approach is far more efficient than regenerating the entire network as proposed by the above publications. Also, due to the effectiveness of the preprocessing, and the swap method, only a small number of open flights left at the final stage of generating open pairings. Thus, only a small number of iterations necessary. Comparatively, the current invention is far more effective and efficient than the processes proposed in the above publications.
SUMMARY OF THE INVENTION
An automated real time crew optimization engine for repairing crew problems including open flights, open pairings, and broken crews in airline operations, which generates multiple solutions in conformance with solution constraints by preprocessing the crew problems to generate potential solutions, and optimizing the potential solutions to provide optimized solutions.
In one aspect of the invention, the preprocessing includes the use of self-connection methods, skipping-leg methods, and an extend-out-broken crew method.
In another aspect of the invention, the self-connection methods include a self-directly-connected method, and a self-indirectly connected method.
In a further aspect of the invention, the skipping-leg methods include a forward leg skipping method and a backward leg skipping method.
In a still further aspect of the invention, swap methods including a one-way swap method, a two-way swap method, and a three-way swap method also are used to generate potential solutions.
In yet a further aspect of the invention, a depth-search-first algorithm, and a shortest path algorithm are applied to the potential solutions to find optimal solutions.
In still another aspect of the invention, a network of open flights is created, and through use of the shortest path algorithm, a flight sequence that involves as many open flights as possible, and which avoids as many deadhead flights as possible is saved as an open pairing. Thereafter, reserve crews assignments to the open pairings are optimized.
REFERENCES:
patent: 6253147 (2001-06-01), Greenstein
patent: 1072991 (2001-07-01), None
Vance, Pamela H. et al. airline crew scheduling: A new formulation and desomposition algorithm. Operations Research to appear, 1994, pp: 1-32.*
Vance, Pamela H. et al. A heuristic branch-and-price approach for the airline crew scheduling problem., Jan-00-1900.*
Anderson, Erik et al. Crew pairing optimization. in operations Research in the Airline Industry, ed. Yu Gang, 1998 chapter 1.*
Anbil, Ranga et al. Recent advances in crew-pairing optimization at American Airlines. Interfaces, 1991, v21, pp. 62-74.*
Anbil, Ranga et al. Column generation and the airline crew scheduling problem. Documenta Mathematica Extra Volume ICM, 1998, pp. 677-686.
Guo Wei, gang Yu, and Mark Song, “Optimization Model and Algorithm for Crew Management During Airline Irregular operations”, Journal of Combination Optimization 1, pp. 305-321, Kluwer Academic Publishers (1997), The Netherlands.
Mark Song, Guo Wei, and Gang Yu, “A Decision Support Framework For Crew Management During Airline Irregular Operations”, Operations Research In The Airline Industry, pp. 259-286, Kluwer Academic Publishers (1998), United States.
Song Gao
Yu Gang
CALEB Technologies Corp.
Hafiz Tariq R.
Lester Gerald E.
Robertson D.
LandOfFree
Crew optimization engine for repair of pairings during... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Crew optimization engine for repair of pairings during..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Crew optimization engine for repair of pairings during... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2944198