Data processing: vehicles – navigation – and relative location – Vehicle control – guidance – operation – or indication – Traffic analysis or control of aircraft
Reexamination Certificate
1999-07-30
2001-11-06
Beaulieu, Yonel (Department: 3661)
Data processing: vehicles, navigation, and relative location
Vehicle control, guidance, operation, or indication
Traffic analysis or control of aircraft
C701S117000, C701S202000, C709S241000, C705S005000, C705S006000, C703S013000, C703S022000
Reexamination Certificate
active
06314361
ABSTRACT:
FIELD OF THE INVENTION
The invention is related to decision support systems for assisting in the rerouting and rescheduling of aircraft in light of flight schedule disruptions, and more particularly to an automated, real time, interactive decision support system which provides sets of optimal aircraft assignments, schedules, and routes for evaluation by operations management in the event of a flight schedule problem.
BACKGROUND OF THE INVENTION
Airlines must regularly develop flight schedules for each of their aircraft, with each flight requiring the designation of an originating city, a departure time, a destination, and an arrival time. The ordered sequence of flights to which an aircraft is assigned is called an aircraft route. The goal is to develop a collection of aircraft routes that use available aircraft to service all scheduled flights. When an aircraft is unexpectedly diverted, delayed or grounded, aircraft must be reassigned, rescheduled, and rerouted within an as short as possible recovery period to minimize lost revenues, passenger inconvenience, and operational costs.
Prior publications of general interest as background information include the following: “Model To Reduce Airline Schedule Disturbances”, by Dusan Teodorovic and Goran Stojkovic, Journal of Transportation Engineering, July/August (1995); “Swapping Applications In A Daily Airline Fleet Assignment”, by Kalyan T. Talluri, Transportation Science, Vol. 30, No.3, August (1996); “Optimization And Persistence”, by Gerald G. Brown, Robert F. Dell, and R. Kevin Wood, Institute For Operations Research, Interfaces 27: 5 September-October, pp. 15-37 (1997). “Real-Time Decision Support For Integration Of Airline Flight Cancellations And Delays Part I: Mathematical Formulation”, by Jia-Ming Cao and Adib Kanafani, Transportation Planning and Technology, Vol.20, pp. 183-199 (1997); “Real-Time Decision Support For Integration Of Airline Flight Cancellations And Delays Part II: Algorithm And Computational Experiments”, by Jia-Ming Cao and Adib Kanafani, Transportation Planning and Technology, Vol. 20, pp. 201-217 (1997); “A Lagrangian Relaxation Approach to Assigning Aircraft to Routes in Hub and Spoke Networks”, by Mark S. Daskin and Nichlaos D. Panayotopoulos, Transportation Science, vol.23, pp. 91-99, (1989); “System Operations Advisor: A Real-Time Decision Support System for Managing Airline Operations at United Airlines” by Ananda Rakshit, Nirup Krishnamurthy and Gang Yu, Interfaces 26: 2 March-April, pp.50-58, Institute for Operations Research and the Management Sciences (1996); “Model For Operational Daily Airline Scheduling”, by Dusan Teodorovic and Goran Stojkovic, Transportation Planning and Technology, vol. 14, pp.273-285, Gordon and Breach Science Publishers Inc. (1990); “Optimal dispatching strategy on an airline network after a schedule perturbation”, by Dusan Teodorovic and Slobodan Guberinic, North-Holland European Journal of Operational Research 15, pp. 178-182, Elsevier Science Publishers B.V. (1984); “American Airlines Arrival Slot Allocation System (ASAS)”, by Alberto Vasquez-Marquez, Interfaces 21: 1 January-February, pp. 42-61, The Institute of Management Sciences (1991); “The Multi-Airport Ground-Holding Problem In Air Traffic Control”, by Peter B. Vranas, Dimitris J. Bertsimas, and Amedeo R. Odoni, Operations Research, vol. 42, No. 2, March-April, Operations Research Society of America (1994); “Airline Scheduling for the Temporary Closure of Airports”, by Shangyao Yan and Chung-Gee Lin, Transportation Science, vol. 31, No. 1, pp. 72-82, Institute for Operations Research and the Management Sciences (1997); “Multifleet routing and multistop flight scheduling for schedule perturbation”, by Shangyao Yan and Yu-ping Tu, European Journal of Operational Research 103, pp. 155-169 (1997); “A Decision Support Framework For Handling Schedule Perturbation”, by Shangyao Yan and Dah-Hwei Yang, Transprn.-B, vol. 30, No. 6, pp.405-419, Elsevier Science Ltd. (1996); “A Decision Support Framework For Multi-Fleet Routing And Multi-Stop Flight Scheduling”, by Shangyao Yan and Hwei-Fwa Young, Transpn. Res.-A, vol. 30, No. 5, pp. 379-398, Elsevier Science Ltd. (1996); “Real-Time Mission-Critical Decision Support Systems for Managing and Controlling Airlines' Operations”, by Gang Yu, Proceedings of International Conference On Management Science and The Economic Development of China (Hong Kong, 1996); and “On the Airline Schedule Perturbation Problem Caused by the Ground Delay Program”, by Songjun Luo and Gang Yu, Transportation Science, vol. 31, No. 4, November 1997, Institute for Operations Research and the Management Sciences (1997).
In “Models And Methods For Managing Airline Irregular Operations”, by Michael F. Arguello, Jonathan F. Bard, and Gang Yu, Operations Research In The Airline Industry, pp 1-45, Kluwer Academic Publishers, (1998); and “A GRASP for Aircraft Routing in Response to Groundings and Delays”, by Michael F. Arguello, Jonathan F. Bard, and Gang Yu, Journal of Combinatorial Optimization 5, pp 211-228 (1997), a greedy randomized adaptive search procedure (GRASP) including GRASP operations “simple circuit cancellation”, “flight route augmentation”, and “partial route exchange” are presented. Further, the above publications provide a framework for testing feasibility and calculating marginal values.
The present invention is an improvement over the teachings of the above publications in that a new operation, the Uncancel Operation, as well as combined operations have been created to afford a more diverse and valuable set of solutions . In particular, the Cancel and Uncancel Operation, the Move and Cancel from Source Operation, the Move and Cancel from Target Operation, the Move and Cancel from Source and Target Operation, the Move and Uncancel to Source Operation, the Move and Uncancel to Target Operation, the Swap and Cancel from Source Operation, the Swap and Cancel from Target Operation, the Swap and Cancel from Source and Target Operation, the Swap and Uncancel to Source Operation, the Swap and Uncancel to Target Operation, and the Three-Way Swap Operation afford a user a much broader neighborhood of operations from which more numerous solutions may be generated.
Although the above GRASP publication discloses the use of a marginal value calculator having a simple cost minimization objective., the marginal value calculator used in the current invention, by way of contradistinction, is defined as a dynamic hierarchical calculator that permits the use of multiple, prioritized, and weighted objectives for determining the value of one solution with respect to another.
As a further difference, the above GRASP publication describes a coarse neighborhood search procedure, whereas the method embodied in the current invention is a direct and more comprehensive procedure for deriving a set of solutions.
Furthermore, the above GRASP publication describes a search procedure that visits many solutions, but requires stopping criteria in order to terminate. In addition, the use of a restricted candidate list, and a randomized selection from the list to choose a new solution is described. The current invention does not use a restricted candidate list, has no randomization techniques, and terminates for each marginal value calculator selected upon generation of a first solution that repairs every Grounded Aircraft Route. Further, in the current invention multiple solutions are generated through the use of multiple marginal value calculators, and a decision tree is used for selection among plural marginal value calculators.
In “An Optimization Model for Airlines' Irregular Operations Control”, by Gang Yu, Proceedings Of The International Symposium On Optimization Applications In Management And Engineering (Beijing, 1995), the author presents a model for re-routing aircraft in response to irregular operations, but no method for solving the model. The model is a pure mathematical model for multi-commodity network flow with side constraints. Although the model permits canceling, delaying, and swapping of flig
Arguello Michael Francis
Yu Gang
Beaulieu Yonel
CALEB Technologies Corp.
Lester Gerald E.
LandOfFree
Optimization engine for flight assignment, scheduling and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Optimization engine for flight assignment, scheduling and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimization engine for flight assignment, scheduling and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2609176