Method and system for routing mobile vehicles and scheduling maintenance for those vehicles related application

• US 7,006,903 B2
• Filed: 10/15/2002
• Issued: 02/28/2006
• Est. Priority Date: 02/28/2002
• Status: Expired due to Term

• Current Assignee: CAE Flight Services USA Incorporated
• Original Assignee: Sabre Incorporated (Sabre Corp.)
• Inventors: Smith, Barry C., Clarke, Michael, Nespoulous, Eric
• Primary Examiner(s): Hernandez, Olga
• Application Number:
  US10/270,000
• Publication Number:
  US 20030167110A1
• Time in Patent Office: 1,232 Days
• Field of Search: 701/3, 701/1, 701/14, 701/25, 701/30, 701/36, 701/2, 701/29, 340/945, 340/500, 340/635, 340/501, 340/540, 340/999, 244/1.R
• US Class Current: 701/3
• 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

Methods and systems for routing and scheduling maintenance for aircraft. An aircraft routing and maintenance scheduling system generates an aircraft routing proposal based on information describing a possible flight of an aircraft and a maintenance scheduling proposal that corresponds to the aircraft based on information describing a possible maintenance schedule of the aircraft. The system determines a proposed flight assignment and proposed maintenance scheduling assignment based on the aircraft routing proposal and maintenance scheduling proposal. Thereafter, the system produces a flight assignment plan and maintenance scheduling plan using the proposed flight assignment and proposed maintenance scheduling assignment when the proposed flight assignment and proposed maintenance scheduling assignment meet a decision criterion describing requirements for aircraft routing and maintenance scheduling.

Claims

1. A method to be used in a computer system for routing and scheduling maintenance for aircraft, comprising:

generating an aircraft routing proposal based on information describing a possible flight of an aircraft;

generating a maintenance scheduling proposal that corresponds to the aircraft based on information describing a possible maintenance schedule of the aircraft, wherein the information describing a possible maintenance schedule of the aircraft at least includes maintenance station capacity information;

determining a proposed pre-flight assignment and proposed maintenance scheduling assignment based on the aircraft routing proposal and maintenance scheduling proposal;

determining whether the proposed pre-flight assignment and proposed maintenance scheduling assignment meet a decision criterion describing requirements for aircraft routing and maintenance scheduling;

optimizing, based on a determination that the decision criterion is not met, the proposed pre-flight assignment and proposed maintenance scheduling assignment so that the decision criterion is met; and

generating a pre-flight assignment plan and maintenance scheduling plan using the proposed pre-flight assignment and proposed maintenance scheduling assignment that met the decision criterion wherein the generating, determining and optimizing steps are performed by a processor.

2. The method of claim 1, wherein the aircraft routing proposal and maintenance scheduling proposal are generated based on constraint programming techniques.

3. The method of claim 1, wherein the aircraft routing proposal and maintenance scheduling proposal are generated subject to constraints.

4. The method of claim 3, wherein the constraints include at least one of aircraft constraints, operational constraints, maintenance constraints, hangar constraints, vehicle constraints, spacial sequence constraints, temporal constraints, and vehicle compatibility constraints.

5. The method of claim 1, wherein the aircraft routing proposal and maintenance scheduling proposal are generated based on search goals.

6. The method of claim 1, wherein the optimizing comprises:

producing refinement information;

generating an additional aircraft routing proposal and an additional maintenance scheduling proposal;

determining a revised flight assignment and a revised maintenance scheduling assignment based on the additional aircraft routing proposal and additional maintenance scheduling proposal; and

deciding whether the revised flight assignment and revised maintenance scheduling assignment meet the decision criterion.

7. The method of claim 6, wherein the proposed flight assignment and maintenance scheduling assignment are generated using a revised simplex algorithm and the refinement information is generated from dual variables found in the revised simplex algorithm.

8. The method of claim 7, wherein the decision criterion is met when no more additional aircraft routing proposals and additional maintenance scheduling proposals are determined based on the refinement information.

9. The method of claim 1, wherein the information describing the possible flight of the aircraft includes at least one of flight information, aircraft information, and maintenance event information.

10. The method of claim 9, wherein the flight information includes at least one of flight origin, destination, start time, end time, block time, booked passenger loads, passenger revenue/fare, assigned aircraft family type, assigned crew rating, minimum equipment list restrictions, and operating restrictions.

11. The method of claim 9, wherein the aircraft information includes at least one of tail identification, aircraft maintenance group, hourly operating cost, current location, ready time, remaining flight time, passenger capacity, aircraft family type, crew rating, and maintenance equipment list capability.

12. The method of claim 9, wherein the maintenance event information includes at least one of aircraft tail, type of maintenance check, scheduled location, start time, and end time.

13. The method of claim 1, wherein the information describing a possible maintenance schedule of the aircraft includes at least one of maintenance counter information, maintenance rule information, and maintenance station capability information.

14. The method of claim 13, wherein the maintenance counter information includes at least one of aircraft tail, type of maintenance check, calendar date, block dine, flying time, and remaining flying cycles.

15. The method of claim 13, wherein the maintenance rule information includes at least one of aircraft maintenance group, type of maintenance check, maintenance event duration, physical capacity, required man power, calendar date) block time, flying time, and flying cycles between checks.

16. The method of claim 13, wherein the maintenance station capability information includes at least one of airport code, physical capacity, man power capacity, effective date, and discontinuous date.

17. The method of claim 1, wherein the maintenance station capacity information includes at least one of airport code, airport maintenance group, maintenance check type, effective date, and discontinuous date.

18. The method of claim 1, wherein the flight assignment plan and maintenance scheduling plan are generated using a branch and bound method.

19. A method to be used in a computer system for routing and scheduling maintenance for aircraft, comprising:

receiving information describing a possible flight of an aircraft and a possible maintenance schedule of the aircraft, wherein the information describing a possible maintenance schedule of the aircraft at least includes maintenance station capacity information;

generating a set of aircraft routing proposals and maintenance scheduling proposals based on the received information;

inputting the proposals into an optimization-based model; and

producing a pre-flight assignment plan and maintenance scheduling plan by solving the optimization-based model wherein the receiving, generating, inputting and producing steps are performed by a processor.

20. An apparatus for routing and scheduling maintenance for aircraft, comprising:

means for receiving information describing a possible flight of an aircraft and a possible maintenance schedule of the aircraft, wherein the information describing a possible maintenance schedule of the aircraft at least includes maintenance station capacity information;

means for generating a set of aircraft routing proposals and maintenance scheduling proposals based on the received information;

means for inputting the proposals into an optimization-based model; and

means for producing a pre-flight assignment plan and maintenance scheduling plan by solving the optimization-based model wherein the means for receiving, generating, inputting and producing are performed by a processor.

21. A method to be used in a computer system for routing and scheduling maintenance for aircraft, comprising:

generating an aircraft routing proposal based on information describing a possible flight of an aircraft;

generating a maintenance scheduling proposal that corresponds to the aircraft based on information describing a possible maintenance schedule of the aircraft, wherein the information describing a possible maintenance schedule of the aircraft at least includes maintenance station capacity information;

determining a proposed pre-flight assignment and proposed maintenance scheduling assignment based on the aircraft routing proposal and maintenance scheduling proposal; and

producing a pre-flight assignment plan and maintenance scheduling plan using the proposed pre-flight assignment and proposed maintenance scheduling assignment when the proposed pre-flight assignment and proposed maintenance scheduling assignment meet a decision criterion describing requirements for aircraft routing and maintenance scheduling wherein the generating, determining and producing steps are performed by a processor.

22. An apparatus for routing and scheduling maintenance for aircraft, comprising:

means for generating an aircraft routing proposal based on information describing a possible flight of an aircraft;

means for generating a maintenance scheduling proposal that corresponds to the aircraft based on information describing a possible maintenance schedule of the aircraft, wherein the information describing a possible maintenance schedule of the aircraft at least includes maintenance station capacity information;

means for determining a proposed pre-flight assignment and proposed maintenance scheduling assignment based on the aircraft routing proposal and maintenance scheduling proposal;

means for determining whether the proposed pre-flight assignment and proposed maintenance scheduling assignment meet a decision criterion describing requirements for aircraft routine and maintenance scheduling;

means for optimizing, based on a determination that the decision criterion is not met the proposed pre-flight assignment and proposed maintenance scheduling assignment so that the decision criterion is met; and

means for generating a pre-flight assignment plan and maintenance scheduling plan using the proposed pre-flight assignment and proposed maintenance schedule that met the decision criterion wherein the means for receiving, generating, optimizing and determining are performed are performed by a processor.

23. The apparatus of claim 22, wherein the aircraft routing proposal and maintenance scheduling proposal are generated based on constraint programming techniques.

24. The apparatus of claim 22, wherein the aircraft routing proposal and maintenance scheduling proposal are generated subject to constraints.

25. The apparatus of claim 24, wherein the constraints include at least one of aircraft constraints, operational constraints, maintenance constraints, hangar constraints, vehicle constraints, spacial sequence constraints, temporal constraints, and vehicle compatibility constraints.

26. The apparatus of claim 22, wherein the aircraft routing proposal and maintenance scheduling proposal are generated based on search goals.

27. The apparatus of claim 22, wherein the means for optimizing comprises:

means for producing refinement information;

means for generating an additional aircraft routing proposal and an additional maintenance scheduling proposal;

means for determining a revised flight assignment and a revised maintenance scheduling assignment based on the additional aircraft routing proposal and additional maintenance scheduling proposal; and

means for deciding whether the revised flight assignment and revised maintenance scheduling assignment meet the decision criterion.

28. The apparatus of claim 27, wherein the proposed flight assignment and maintenance scheduling assignment are generated using a revised simplex algorithm and the refinement information is generated from dual variables found in the revised simplex algorithm.

29. The apparatus of claim 28, wherein the decision criterion is met when no more additional aircraft routing proposals and additional maintenance scheduling proposals are determined based on the refinement information.

30. The apparatus of claim 22, wherein the information describing the possible flight of the aircraft includes at least one of flight information, aircraft information, and maintenance event information.

31. The apparatus of claim 30, wherein the flight information includes at least one of flight origin, destination, start time, end time, block time, booked passenger loads, passenger revenue/fare, assigned aircraft family type, assigned crew rating, minimum equipment list restrictions, and operating restrictions.

32. The apparatus of claim 30, wherein the aircraft information includes at least one of tail identification, aircraft maintenance group, hourly operating cost, current location, ready time, remaining flight time, passenger capacity, aircraft family type, crew rating, and maintenance equipment list capability.

33. The apparatus of claim 30, wherein the maintenance event information includes at least one of aircraft tail, type of maintenance check, scheduled location, start time, and end time.

34. The apparatus of claim 22, wherein the information describing a possible maintenance schedule of the aircraft includes at least one of maintenance counter information, maintenance rule information, and maintenance station capability information.

35. The apparatus of claim 34, wherein the maintenance counter information includes at least one of aircraft tail, type of maintenance check, calendar date, block time, flying time, and remaining flying cycles.

36. The apparatus of claim 34, wherein the maintenance rule information includes at least one of aircraft maintenance group, type of maintenance check, maintenance event duration, physical capacity, required man power, calendar date, block time, flying time, and flying cycles between checks.

37. The apparatus of claim 34, wherein the maintenance station capability information includes at least one of airport code, physical capacity, man power capacity, effective date, and discontinuous date.

38. The apparatus of claim 22, wherein the maintenance station capacity information includes at least one of airport code, airport maintenance group, maintenance check type, effective date, and discontinuous date.

39. The apparatus of claim 22, wherein the flight assignment plan and maintenance scheduling plan are generated using a branch and bound method.

40. A computer-readable medium containing instructions for performing a method for routing and scheduling maintenance for aircraft, the method comprising:

generating an aircraft routing proposal based on information describing a possible flight of an aircraft;

generating a maintenance scheduling proposal that corresponds to the aircraft based on information describing a possible maintenance schedule of the aircraft wherein the information describing a possible maintenance schedule of the aircraft at least includes maintenance station capacity information;

determining a proposed pre-flight assignment and proposed maintenance scheduling assignment based on the aircraft routing proposal and maintenance scheduling proposal;

determining whether the proposed pre-flight assignment and proposed maintenance scheduling assignment meet a decision criterion describing requirements for aircraft routing and maintenance scheduling;

optimizing, based on a determination that the decision criterion is not met, the proposed pre-flight assignment and proposed maintenance scheduling assignment so that the decision criterion is met; and

generating a pre-flight assignment plan and maintenance scheduling plan using the proposed pre-flight assignment and proposed maintenance schedule that met the decision criterion wherein the generating, determining and optimizing steps are performed by a processor.

41. An apparatus for performing a method for routing and scheduling maintenance for aircraft, comprising:

a memory having a program that;

generates an aircraft routing proposal based on information describing a possible flight of an aircraft;

generates a maintenance scheduling proposal that corresponds to the aircraft based on information describing a possible maintenance schedule of the aircraft, wherein the information describing a possible maintenance schedule of the aircraft at least includes maintenance station capacity information;

determines a proposed pre-flight assignment and proposed maintenance scheduling assignment based on the aircraft routing proposal and maintenance scheduling proposal;

determines whether the proposed pre-flight assignment and proposed maintenance scheduling assignment meet a decision criterion describing requirements for aircraft routing and maintenance scheduling;

optimizes, based on a determination that the decision criterion is not met, the proposed pre-flight assignment and proposed maintenance scheduling assignment so that the decision criterion is met; and

generates a pre-flight assignment plan and maintenance scheduling plan using the proposed pre-flight assignment and proposed maintenance schedule that met the decision criterion; and

a processor that runs the program.

42. An apparatus for routing and scheduling maintenance for aircraft, comprising:

means for generating an aircraft routing proposal based on information describing a possible flight of an aircraft;

means for generating a maintenance scheduling proposal that corresponds to the aircraft based on information describing a possible maintenance schedule of the aircraft, wherein the information describing a possible maintenance schedule of the aircraft at least includes maintenance station capacity information;

means for determining a proposed pre-flight assignment and proposed maintenance scheduling assignment based on the aircraft routing proposal and maintenance scheduling proposal; and

means for producing a pre-flight assignment plan and maintenance scheduling plan using the proposed pre-flight assignment and proposed maintenance scheduling assignment when the proposed pre-flight assignment and proposed maintenance scheduling assignment meet a decision criterion describing requirements for aircraft routing and maintenance scheduling wherein the generating, determining and producing steps are performed by a processor.

43. A computer-readable medium containing instructions for performing a method for routing and scheduling maintenance for aircraft, the method comprising;

receiving information describing a possible flight of an aircraft and a possible maintenance schedule of the aircraft, wherein the information describing a possible maintenance schedule of the aircraft at least includes maintenance station capacity information;

generating a set of aircraft routing proposals and maintenance scheduling proposals based on the received information;

inputting the proposals into an optimization-based model; and

producing a pre-flight assignment plan and maintenance scheduling plan by solving the optimization-based model wherein the receiving, generating, inputting and producing steps are performed by a processor.

44. A computer-readable medium containing instructions for performing a method for routing and scheduling maintenance for aircraft, the method comprising:

generating an aircraft routing proposal based on information describing a possible flight of an aircraft;

generating a maintenance scheduling proposal that corresponds to the aircraft based on information describing a possible maintenance schedule of the aircraft, wherein the information describing a possible maintenance schedule of the aircraft at least includes maintenance station capacity information;

determining a proposed pre-flight assignment and proposed maintenance scheduling assignment based on the aircraft routing proposal and maintenance scheduling proposal; and

producing a pre-flight assignment plan and maintenance scheduling plan using the proposed pre-flight assignment and proposed maintenance scheduling assignment when the proposed pre-flight assignment and proposed maintenance scheduling assignment meet a decision criterion describing requirements for aircraft routing and maintenance scheduling wherein the generating, determining and producing steps are performed by a processor.

45. An apparatus for routing and scheduling maintenance for aircraft, comprising:

a memory having a program that receives information describing a possible flight of an aircraft and a possible maintenance schedule of the aircraft, wherein the information describing a possible maintenance schedule of the aircraft at least includes maintenance station capacity information;

generates a set of aircraft routing proposals and maintenance scheduling proposals based on the received information;

inputs the proposals into an optimization-based model; and

produces a pre-flight assignment plan and maintenance scheduling plan by solving the optimization-based model; and

a processor that runs the program.

46. An apparatus for routing and scheduling maintenance for aircraft, comprising:

a memory having a program that;

generates an aircraft routing proposal based on information describing a possible flight of an aircraft;

generates a maintenance scheduling proposal that corresponds to the aircraft based on information describing a possible maintenance schedule of the aircraft, wherein the information describing a possible maintenance schedule of the aircraft at least includes maintenance station capacity information;

determines a proposed pre-flight assignment and proposed maintenance scheduling assignment based on the aircraft routing proposal and maintenance scheduling proposal; and

produces a pre-flight assignment plan and maintenance scheduling plan using the proposed pre-flight assignment and proposed maintenance scheduling assignment when the proposed pre-flight assignment and proposed maintenance scheduling assignment meet a decision criterion describing requirements for aircraft routing and maintenance scheduling; and

a processor that runs the program.