Optimization engine for flight assignment, scheduling and routing of aircraft in response to irregular operations

• US 6,314,361 B1
• Filed: 07/30/1999
• Issued: 11/06/2001
• Est. Priority Date: 07/30/1999
• Status: Expired due to Term

• Current Assignee: GE Aviation Systems Taleris Ltd. (GE Aerospace), GE Flight Efficiency Services, Inc.
• Original Assignee: Caleb Technologies Corp.
• Inventors: Arguello, Michael Francis, Yu, Gang
• Primary Examiner(s): Beaulieu, Yonel
• Application Number:
  US09/364,157
• Time in Patent Office: 830 Days
• Field of Search: 701/120, 701/200, 701/202, 703/13, 703/22, 705/5, 705/6, 705/8, 707/1, 709/100
• US Class Current: 701/120
• CPC Class Codes: G06Q 10/02 Reservations, e.g. for tickets, services or events
• CPC Class Codes: G06Q 10/025 Coordination of plural reservations, e.g. plural trip segments, transportation combined with accommodation
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G08G 5/0026 located on the ground
• CPC Class Codes: G08G 5/0043 Traffic management of multiple aircrafts from the ground G08G5/003 takes precedence; data processing specially designed for resource management, e.g. scheduling or allocating time, human or machine resources G06Q10/06

Abstract

An automated, real-time decision support system for reassigning, rescheduling, and rerouting aircraft in response to flight operation disruptions, in which sets of optimal solutions are provided through use of evaluation statistics to assist operations management in selecting the optimal solution best conforming to operational constraints and user requirements. Solutions are generated through the execution of unary operations, binary operations, three-way operations, and reverse binary operations on grounded aircraft routes, available aircraft routes, and phantom routes which implicitly cancelled flights. Solutions are evaluated for feasibility with respect to operations constraints and user requirements. Marginal value calculators are used to differentiate feasible solutions and identify optimal solutions. The marginal value calculators are dynamic, hierarchical calculators that permit use of multiple, prioritized, and weighted route and operation attributes in comparing solution values. Marginal value calculators are selected by means of a decision tree.

Claims

1. An automated, real-time aircraft optimization engine for generating multiple solutions to repair disruptions in aircraft routes, which comprises:

a memory system having stored therein memory objects defining an existing flight environment;

an optimization server receiving an aircraft problem specification including user requirements from a user;

a microprocessor in electrical communication with said memory system and said optimization server, and receiving said memory objects and said aircraft problem specification, for generating multiple solutions through use of plural marginal value calculators and an integrated combination of operations on grounded aircraft routes and available aircraft routes to effect flight leg moves, flight leg swaps, flight leg cancellations creating phantom routes, flight leg delays, and flight leg creations as required, to produce reparations for said grounded aircraft routes comprising at least one of modified grounded aircraft routes, modified available aircraft routes, phantom routes, and modified phantom routes, and thereafter determining feasibility and marginal values of said reparations, and comparing said marginal values of feasible said reparations to provide optimal solutions that repair all said grounded aircraft routes specified in said aircraft problem specification.

2. The automated, real-time aircraft optimization engine of claim 1, wherein said integrated combination of operations includes at least one of unary operations, binary operations, three-way operations, and reverse binary operations.

3. The automated, real time aircraft optimization engine of claim 2, wherein said unary operations include at least one of do-nothing operations, cancel operations, uncancel operations, and cancel and uncancel operations.

4. The automated, real time aircraft optimization engine of claim 2, wherein said binary operations include move operations, swap operations, move and cancel from source operations, move and cancel from target operations, move and cancel from source and target operations, move and uncancel to source operations, move and uncancel to target operations, swap and cancel from source operations, swap and cancel from target operations, swap and cancel from source and target operations, swap and uncancel to source operations, and swap and uncancel to target operations.

5. The automated, real time aircraft optimization engine of claim 1, wherein said feasibility of said multiple solutions is determined by compliance with user requirements and operations constraints.

6. The automated, real time aircraft optimization engine of claim 1, wherein said marginal values are determined through a decision tree selection of one of said plural marginal value calculators for application to feasible ones of said multiple solutions.

7. The automated, real time aircraft optimization engine of claim 1, wherein said plural marginal value calculators are dynamic, hierarchical calculators that permit use of multiple, prioritized, and weighted route and operation attributes in comparing said marginal values to select said optimal solutions.

8. The automated, real time aircraft optimization engine of claim 1, wherein said microprocessor streamlines generation of said multiple solutions through application of solution conditions.

9. The automated, real time aircraft optimization engine of claim 1, wherein said flight leg creations include ferry flights.

10. The automated, real time aircraft optimization engine of claim 1, wherein said flight leg cancelations are stored in phantom routes for use in uncancel operations.

18. The automated method of claim 3, wherein said uncancel operations include the steps of:

receiving an insertion point in one of said grounded aircraft routes during execution of said unary operations;

selecting a phantom route;

selecting a sequence of flights from said phantom route;

removing said sequence of flights from said phantom route and inserting said sequence of flights into said one of said grounded aircraft routes at said insertion point;

evaluating a data set comprising said one of said grounded aircraft routes as modified, and said phantom route as modified to determine feasibility, and if feasible calculating a marginal value of said data set through use of one of plural marginal value calculators, and replacing an incumbent solution if said marginal value of said data set exceeds that of said incumbent solution;

repeating selection of sequence of flights from said phantom route and repeating the above steps beginning with the step of removing a sequence of flights until all sequences of flights in said phantom route are selected;

repeating selection of phantom route and repeating above steps beginning with the step of selecting a sequence of fights until all phantom routes are selected.

11. An automated method of repairing airline flight schedules in real time, which comprises the steps of:

receiving memory objects from a memory system which depict current, entire flight environments for at least one airline;

receiving an aircraft problem specification from a user by way of a user interface;

selecting through decision tree logic one of plural marginal value calculators;

selecting a grounded aircraft route from said aircraft problem specification as a first available aircraft route;

creating an incumbent solution which during a first cycle of said automated method for said grounded aircraft route is set to null;

applying unary operations to said grounded aircraft route to generate first reparations comprising at least one of a first modified grounded aircraft route, first phantom routes, and first modified phantom routes, evaluating feasibility of said first reparations, applying said one of said plural marginal value calculators to said first reparations, and replacing said incumbent solution if marginal value of said first reparations exceeds that of said incumbent solution;

selecting a second available aircraft route from said memory objects;

applying binary operations to said grounded aircraft route and said second available aircraft route to generate second reparations comprising second modified grounded aircraft routes, first modified second available aircraft routes, second phantom routes, and second modified phantom routes, evaluating feasibility of said second reparations, applying said one of said plural marginal value calculators to said second reparations, and replacing said incumbent solution if marginal value of said second reparations exceeds that of said incumbent solution;

selecting a third available aircraft route from said memory objects;

applying three-way operations to said grounded aircraft route, said second available aircraft route, and said third available aircraft route to generate third reparations comprising third modified grounded aircraft routes, second modified second available aircraft routes, and first modified third available aircraft routes, evaluating feasibility of said third reparations, applying said one of said plural marginal value calculators to said third reparations, and replacing said incumbent solution if marginal value of said third reparations exceeds that of said incumbent solution;

if additional available aircraft routes exist, select one of said additional available aircraft routes as said third available aircraft route, and repeat the step of applying three-way operations until all of said additional available aircraft routes are processed as said third available aircraft route;

if said additional available aircraft routes exist, select any one of said additional available aircraft routes as said second available aircraft route, and repeat the above steps beginning with the step of applying binary operations until all of said additional available aircraft routes are processed as said second available aircraft route;

committing said incumbent solution to repair said grounded aircraft route and form a solution;

if additional grounded aircraft routes exist, select another grounded aircraft route as said first available aircraft route and repeat the above steps beginning with the step of applying unary operations until all of said additional grounded aircraft routes are processed and repaired as said first available aircraft route to form one solution which repairs all grounded aircraft routes;

if additional solutions are desired, select through said decision tree logic another one of said plural marginal value calculators and repeat the above steps beginning with the step of selecting said grounded aircraft route; and

outputting all solutions to said user.

12. The automated method of claim 11, further including after the step of applying binary operations, the step of applying reverse binary operations to said grounded aircraft route and said second available aircraft route to generate fourth reparations comprising fourth modified grounded aircraft routes, third modified second available aircraft routes, third phantom routes, and third modified phantom routes, evaluating feasibility of said fourth reparations, applying said one of said plural marginal value calculators to said fourth reparations, and replacing said incumbent solution if marginal value of said fourth reparations exceeds that of said incumbent solution.

13. The automated method of claim 12, wherein solution conditions in said flight environments, operations constraints, and user requirements are applied to streamline execution of said unary operations, said binary operations, said reverse binary operations, and said three-way operations to avoid generating infeasible routes, and to accelerate repair of said grounded aircraft route.

14. The automated method of claim 11, wherein said feasibility evaluator and said plural marginal value calculators act in concert to seek feasible optimal solutions which affect as few available aircraft routes as possible.

15. The automated method of claim 11, wherein the step of applying three-way operations includes the steps of:

selecting a first sequence of flights from said grounded aircraft route;

selecting a second sequence of flights from said second available aircraft route;

selecting a third sequence of flights from said third available aircraft route;

replacing said first sequence of flights in said grounded aircraft route with said second sequence of flights from said second available aircraft route;

replacing said second sequence of flights from said second available aircraft route with said third sequence of flights from said third available aircraft route;

replacing said third sequence of flights from said third available aircraft route with said first sequence of flights removed from said grounded aircraft route;

evaluating a data set comprising said grounded aircraft route as modified, said second available aircraft route as modified, and said third available aircraft route as modified to determine feasibility, calculating marginal value of said data set through use of said one of said plural marginal value calculators, and replacing said incumbent solution if marginal value of said data set exceeds that of said incumbent solution;

repeating selection of said third sequence of flights from said third available aircraft route and then repeating the above steps beginning with the step of replacing said second sequence of flights until all sequences of flights from said third available aircraft route are selected;

repeating selection of said second sequence of flights from said second available aircraft route and repeating the above steps beginning with the step of selecting said third sequence of flights until all sequences of flights from said second available aircraft route are selected; and

repeating selection of said first sequence of flights from said grounded aircraft route and repeating the above steps beginning with the step of selecting said second sequence of flights from said second available aircraft route until all sequences of flights from said grounded aircraft route are selected.

16. The automated method of claim 11, wherein the step of selecting through decision tree logic includes the steps of:

selecting a base marginal value calculator;

generating a solution using said base marginal value calculator;

comparing attributes of said solution to decision-making criteria to select a next marginal value calculator from said plural marginal value calculators;

generating a next solution using said next marginal value calculator, and if desired, comparing attributes of said next solution to decision-making criteria to select another marginal value calculator, and repeating steps of generating and comparing until a desired quantity of solutions is generated.

17. The automated method of claim 12, wherein the step of applying said one of said plural marginal value calculators includes the steps of:

determining attributes of a reparation as created;

applying highest objective of said one of said plural marginal value calculators to said attributes to calculate a marginal value of said reparation;

comparing said marginal value of said reparation to a marginal value of said incumbent solution, and replacing said incumbent solution if said marginal value of said reparation exceeds that of said incumbent solution;

if, for said highest objective, neither said reparation nor said incumbent solution can be determined to have a greater marginal value, remove said highest objective and repeat the above steps beginning with the step of applying highest objective using a next highest remaining objective; and

if, for said highest objective, said incumbent solution is determined to have greater marginal value than said reparation, cease operation.

19. An automated, real-time aircraft optimization engine for generating multiple solutions to repair disruptions in aircraft routes, which comprises:

a memory system having stored therein memory objects defining an existing flight environment;

an optimization server receiving an aircraft problem specification including user requirements from a user; and

a microprocessor in electrical communication with said memory system and said optimization server, and receiving said memory objects and said aircraft problem specification, for generating multiple solutions through use of a marginal value calculator and an integrated combination of operations on grounded aircraft routes and available aircraft routes to provide optimal solutions that repair all said grounded aircract routes specified in said aircraft problem specification.

20. An automated, real-time aircraft optimization engine for generating multiple solutions to repair disruptions in aircraft routes, which comprises:

a memory system having stored therein memory objects defining an existing flight environment;

an optimization server receiving an aircraft problem specification including user requirements from a user;

a microprocessor in electrical communication with said memory system and said optimization server, and receiving said memory objects and said aircraft problem specification, for generating multiple solutions through use of plural marginal value calculators and an integrated combination of operations on grounded aircraft routes, and thereafter determining feasibility and marginal values of said reparations, and comparing said marginal values of feasible ones of said reparations to provide optimal solutions that repair all said grounded aircraft routes specified in said aircraft problem specification.

21. A method of generating multiple solutions to repair disruptions in grounded aircraft routes in real time, which comprises the steps of:

receiving flight environment data and user requirements;

applying an integrated combination of operations to said grounded aircraft routes and available aircraft routes to produce reparations for said grounded aircraft routes;

determining feasibility of said reparations by comparing said reparations with said flight environment data and said user requirements;

determining marginal values of feasible ones of said reparations; and

comparing said marginal values of said feasible ones to provide optimal solutions that repair all said grounded aircraft routes.