Method and system for conducting fleet operations

• US 7,668,744 B2
• Filed: 07/31/2003
• Issued: 02/23/2010
• Est. Priority Date: 07/31/2003
• Status: Active Grant

• Current Assignee: The Boeing Co.
• Original Assignee: The Boeing Co.
• Inventors: Utriainen, Tapani Ensio, Hang, Darren Dejun, Garsell, Andreas Patrik, Johansson, Fredrik Ingemar, Tiourine, Serguei Romualdovich
• Primary Examiner(s): Boswell; Beth V
• Assistant Examiner(s): Anderson; Folashade
• Application Number:
  US10/631,600
• Publication Number:
  US 20050027579A1
• Time in Patent Office: 2,399 Days
• Field of Search: 705/8
• US Class Current: 705/7.37
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G06Q 10/06311 Scheduling, planning or task assignment for a person or group
• CPC Class Codes: G06Q 10/06312 Adjustment or analysis of established resource schedule, e.g. resource or task levelling, or dynamic rescheduling
• CPC Class Codes: G06Q 10/06375 Prediction of business process outcome or impact based on a proposed change
• CPC Class Codes: G06Q 10/0639 Performance analysis of employees; Performance analysis of enterprise or organisation operations
• CPC Class Codes: Y02P 90/80 Management or planning

Abstract

A fleet engine, a crew engine, a passenger engine and an integration engine that communicate with a distributed computer network via two-way communication channels to monitor and repair disruptions to schedules particularly in the airline industry. When a disruption occurs, the method will produce a plurality of solutions that are structurally different for evaluation by the controller or operations manager. The method of generating solutions includes two phases. A first phase with artificially relaxed costs and a second phase with costs that reflect the policies and actual costs of the relevant activities. Upon creating structurally different solutions, the method evaluates the solutions and presents summary information about the solutions to the operations manager. If a violation of a rule occurs in a solution, an alert is generated to notify a user of the rule violation.

Claims

1. A method for generating a plurality of structurally different solutions using recovery operations, the method comprising the steps of:

periodically loading schedule data into a plurality of optimization engines, each engine in communication via a computer network and configured to optimize disposition of one or more resources corresponding to the engine;

each of the optimization engines preprocessing the loaded schedule data and a plurality of user-specified penalty value costs to predefine one or more penalty value costs associated with disposition of the one or more resources associated with the engine;

receiving a disruption specification and request for rescheduling from a user;

one or more of the optimization engines generating a plurality of solutions, the generating performed in a plurality of phases by;

in a first phase, reducing one or more of the penalty value costs predefined by the engines to flatten a cost space for a neighborhood of possible schedules, and, using a first local search algorithm, traversing the flattened cost space to find a first local minimum representing a relaxed cost solution; and

in a second phase, reinstating the one or more reduced penalty value costs to restore the cost space, and using a second local search algorithm, searching the restored cost space from the relaxed cost solution to find one or more second local minima representing one or more solutions for evaluation;

one or more of the optimization engines evaluating the one or more solutions for evaluation generated by another of the engines, the evaluating performed relative to one or more resource-specific rules of the evaluating optimization engine underlying the one or more penalty value costs; and

based on the evaluating, updating the schedule data.

2. A method according to claim 1, wherein the cost space includes a penalty value cost associated with violation of a policy.

3. A method according to claim 1, wherein the cost space includes a monetary amount associated with an activity.

4. A method according to claim 1, wherein one of the optimization engines operates on aircraft schedules and the cost space is modified to favor a desirable operation over a less desirable operation as determined by one of a passenger and crew optimization engine such that a preferred operation by the passenger and crew optimization engines is more likely to be utilized by a portion of the plurality of solutions.

5. A method according to claim 4, wherein the operations used by the aircraft optimization engine are flight delay, flight cancellation, aircraft type change and aircraft registration change.

6. A method according to claim 1, further comprising the steps of:

receiving an alert generation request;

evaluating the plurality of solutions based upon at least one rule for violations of the at least one rule; and

generating an alert for each violation of the at least one rule.

7. A method according to claim 1, wherein the second phase uses a different local search algorithm from the first phase.

8. A method according to claim 1, wherein during a third phase, partial banning of operations is utilized.

9. A method according to claim 1, wherein the first local search algorithm starts from a randomly selected location.

10. A method according to claim 1, wherein the local search algorithm include a steepest-descent algorithm.

11. A method according to claim 1, further comprising the steps of:

monitoring operation of the schedule;

defining a scope of the disruption; and

pruning a neighborhood of potential solutions.

12. A method according to claim 1, further comprising a first of the engines generating a partial solution;

and a second of the engines evaluating the partial solution and proposing an alternative solution.

13. A method according to claim 1, further comprising the step of synchronizing the schedule data upon receipt of the disruption specification.

14. A method according to claim 1, further comprising modifying the cost space to obtain solutions in different areas of the cost space.

15. A method according to claim 11, wherein pruning the neighborhood comprises predetermining which of a plurality of possible swaps and/or insertions are beneficial and eliminating the other possible swaps and/or insertions.

16. A method according to claim 1, wherein the one or more solutions for evaluation include one or more partial solutions, the method further comprising one or more of the optimization engines completing a partial solution from another of the engines.

17. A method according to claim 1, further comprising the steps of evaluating the plurality of solutions and providing at least a portion of the plurality of solutions to the user.

18. A method according to claim 1, wherein the disruption specification includes a planning horizon.

19. A system for generating a plurality of structurally different solutions using recovery operations, the system comprising:

a fleet optimization engine, a crew optimization engine, and a passenger optimization engine in communication via a computer network, the optimization engines configured to periodically receive schedule data for preprocessing by the engines with a plurality of user-specified penalty value costs to predefine one or more penalty value costs associated with disposition of resources associated with the optimization engines; and

an integration engine for receiving a disruption specification and request for rescheduling from a user;

each of the optimization engines configured to generate a plurality of solutions in a plurality of phases, each optimization engine configured to;

in a first phase, reduce one or more of the penalty value costs predefined by the engines to flatten a cost space for a neighborhood of possible schedules, and, using a first local search algorithm, traverse the flattened cost space to find a first local minimum representing a relaxed cost solution; and

in a second phase, reinstate the one or more reduced penalty value costs to restore the cost space, and using a second local search algorithm, search the restored cost space from the relaxed cost solution to find one or more second local minima representing one or more solutions for evaluation;

each of the optimization engines further configured to evaluate, relative to one or more resource-specific rules of the evaluating optimization engine underlying the penalty value costs, solutions for evaluation generated by the other engines;

the integration engine configured to select any or all of the optimization engines to generate at least some of the solutions.