Method and system for conducting fleet operations

• US 20050027579A1
• Filed: 07/31/2003
• Published: 02/03/2005
• 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
• Granted Patent: US 7,668,744 B2
• Time in Patent Office: Days
• US Class Current: 705/8
• 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 with an optimization engine using recovery operations, the method comprising the steps of:

periodically loading schedule data into the optimization engine;

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

generating a plurality of solutions by using a local search algorithm in at least two phases,

wherein a first phase has an artificially modified cost and a second phase has normal costs that reflect policies and monetary values associated with corresponding activities.

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

3. A method according to claim 1, wherein the artificially modified cost is a monetary amount associated with an activity.

4. A method according to claim 1, wherein the optimization engine operates on aircraft schedules and the artificially modified cost is set 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 the 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 local search algorithm starts from a randomly selected location.

10. A method according to claim 1, wherein the local search algorithm is 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 the step of selecting and implementing one of the plurality of solutions.

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, wherein the schedule data is downloaded every two minutes.

15. A method according to claim 1, further comprising the step of stopping processing after a predetermined amount of time.

16. A method according to claim 15, further comprising the step of stopping processing after a user selected number of solutions are generated.

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 method for decomposing a disruption within an airline to facilitate generating optimal solutions on a day of operations involving a schedule coordinating fleet resources, crew resources and passengers, the method comprising the steps of:

providing an integration server in communication with fleet, crew and passenger optimization engines;

preprocessing based upon the schedule the crew and passenger optimization engines to generate initial data, wherein the initial data includes penalty cost values based upon hard and soft constraints plus costs based upon operations to the schedule;

providing the initial data to the fleet optimization engine;

receiving a disruption specification at the integration server;

forwarding the disruption specification to the fleet optimization engine; and

creating a plurality of solutions with the fleet optimization engine based upon the disruption specification and the initial data.

20. A method according to claim 19, wherein the initial data includes cost data based upon hard and soft constraints.

21. A method according to claim 19, creating a first plurality of solutions based upon the disruption specification wherein only fleet resources are rescheduled.

22. A method according to claim 21, further comprising the step of terminating the method if one of the first plurality of solutions is acceptable.

23. A method according to claim 19, further comprising the step of providing the plurality of solutions generated by the fleet optimization engine to the crew and passenger optimization engines for cost evaluation.

24. A method according to claim 19, wherein the initial data generated by the passenger optimization engine includes flight values, passengers per class, connection constraints for passengers and cancellation penalty value costs.

25. A method according to claim 19, wherein the initial data generated by the crew optimization engine includes crew limitations.

26. A method according to claim 25, wherein a crew limitation is latest departure times.

27. A method according to claim 19, further comprising the step of preprocessing on the schedule by the fleet optimization engine to generate initial data that is provided to the crew and passenger optimization engines.

28. A method according to claim 27, wherein initial data generated by the fleet optimization engine is provided to the crew and passenger.

29. A method according to claim 28, wherein the initial data generated by the fleet optimization engine is latest departure times for aircraft directly affected by the disruption.

30. A method according to claim 19, further comprising the steps of:

generating, by the fleet optimization engine, a plurality of solutions by using a local search algorithm in at least two phases, wherein a first phase has an artificially relaxed cost and the second phase has normal costs that reflect policies and dollar values associated with corresponding activities;

evaluating the plurality of solutions; and

providing at least a portion of the plurality of solutions to the integration server.

31. A method according to claim 19, further comprising the steps of generating, by the fleet optimization engine, a plurality of solutions by using a local search algorithm from random points within a cost space based upon the schedules.

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

first means for loading schedule data into the optimization engine;

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

third means for generating a plurality of solutions by using a local search algorithm in a first and second phase, wherein the first phase has a modified cost and the second phase has costs that reflect policies associated with corresponding activities.

33. A system as recited in claim 32, wherein the first means is a user interface in communication with memory, and the second and third means are an optimization engine in communication with the first means.