Methods and systems for routing mobile vehicles

• US 20030167109A1
• Filed: 02/28/2002
• Published: 09/04/2003
• Est. Priority Date: 02/28/2002
• Status: Active Grant

• Current Assignee: Flight Operations Holdings LLC
• Original Assignee: Sabre Incorporated (Sabre Corp.)
• Inventors: Smith, Barry C., Clarke, Michael D. D.
• Granted Patent: US 7,228,207 B2
• Time in Patent Office: Days
• US Class Current: 701/3
• CPC Class Codes: G06Q 10/0631 Resource planning, allocation, distributing or scheduling for enterprises or organisations
• CPC Class Codes: G06Q 10/063116 Schedule adjustment 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/06316 Sequencing of tasks or work
• 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

The present invention relates to methods and systems for routing mobile vehicles under maintenance and operational constraints. In the case of aircraft, the methods and systems may generate an aircraft routing proposal based on information describing a possible flight of an aircraft, determine a proposed flight assignment for the aircraft based on the generated aircraft routing proposal and complying with the information describing the possible flight of the aircraft, and determine whether the proposed flight assignment meets a decision criterion describing requirements for aircraft routing. If the decision criterion is unmet, the methods and systems may optimize the proposed flight assignment such that the proposed flight assignment meets the decision criterion. The methods and systems may also generate a flight assignment plan using the proposed flight assignment that meets the decision criterion.

Claims

1. An aircraft routing method comprising:

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

determining a proposed flight assignment for the aircraft based on the generated aircraft routing proposal and complying with the information describing the possible flight of the aircraft;

determining whether the proposed flight assignment meets a decision criterion describing requirements for aircraft routing;

if the decision criterion is unmet, optimizing the proposed flight assignment such that the proposed flight assignment meets the decision criterion; and

generating a flight assignment plan using the proposed flight assignment that meets the decision criterion.

2. The method of claim 1, wherein optimizing the proposed flight assignment comprises:

generating refinement information;

generating an additional aircraft routing proposal based on the refinement information;

determining a revised flight assignment for the aircraft based on the generated aircraft routing proposal and complying with the information describing the possible flight of the aircraft; and

determining whether the revised flight assignment meets the decision criterion.

3. The method of claim 2, wherein the proposed flight assignment is generated using a revised simplex algorithm and wherein the refinement information is generated from dual variables found in the revised simplex algorithm.

4. The method of claim 3, wherein the decision criterion is met when no more additional aircraft routing proposals can be determined based on the generated refinement information and complying with the information describing the possible flight of the aircraft.

5. 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 information.

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

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

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

9. The method of claim 1, wherein the information describing the possible flight of the aircraft is organized into a flight network for the aircraft and the aircraft routing proposal is generated using the flight network.

10. The method of claim 9, wherein the aircraft routing proposal is generated using a shortest path algorithm.

11. The method of claim 10, wherein the shortest path algorithm is a generalized permanent labeling algorithm.

12. The method of claim 10, wherein the shortest path algorithm is at least one of a generalized permanent labeling algorithm, a LP-based shortest path algorithm, a K-shortest path algorithm, and a Dijkstra algorithm.

13. The method of claim 1, wherein the proposed flight assignment is generated using a revised simplex algorithm.

14. The method of claim 1, wherein the flight assignment plan is generated using a branch and bound method.

15. An aircraft routing system comprising:

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

means for determining a proposed flight assignment for the aircraft based on the generated aircraft routing proposal and complying with the information describing the possible flight of the aircraft;

means for determining whether the proposed flight assignment meets a decision criterion describing requirements for aircraft routing;

means for optimizing the proposed flight assignment such that the proposed flight assignment meets the decision criterion if the decision criterion is unmet; and

means for generating a flight assignment plan using the proposed flight assignment that meets the decision criterion.

16. The system of claim 15, wherein the means for optimizing the flight assignment comprises:

means for generating refinement information;

means for generating an additional aircraft routing proposal based on the refinement information;

means for determining a revised flight assignment for the aircraft based on the generated aircraft routing proposal and complying with the information describing the possible flight of the aircraft; and

means for determining whether the revised flight assignment meets the decision criterion.

17. The system of claim 16, wherein the proposed flight assignment is generated using a revised simplex algorithm and wherein the refinement information is generated from dual variables found in the revised simplex algorithm.

18. The system of claim 17, wherein the decision criterion is met when no more additional aircraft routing proposals can be determined based on the generated refinement information and complying with the information describing the possible flight of the aircraft.

19. The system of claim 15, wherein the information describing the possible flight of the aircraft includes at least one of flight information, aircraft information, and maintenance information.

20. The system of claim 19, wherein the flight information includes at least one of origin, destination, start time, end time, block time, booked passenger loads, passenger revenue/fare, assigned aircraft family type, assigned crew rating, and minimum equipment list restriction.

21. The system of claim 19, wherein the aircraft information includes at least one of tail identification, hourly operating cost, current location, ready time, remaining flight time, passenger capacity, family type, crew rating, and minimum equipment list capability.

22. The system of claim 19, wherein the maintenance information includes at least one of aircraft tail, type of check, scheduled location, start time, and end time.

23. The system of claim 15, wherein the information describing the possible flight of the aircraft is organized into a flight network for the aircraft and the aircraft routing proposal is generated using the flight network.

24. The system of claim 23, wherein the aircraft routing proposal is generated using a shortest path algorithm.

25. The system of claim 24, wherein the shortest path algorithm is a generalized permanent labeling algorithm.

26. The system of claim 24, wherein the shortest path algorithm is at least one of a generalized permanent labeling algorithm, a LP-based shortest path algorithm, a K-shortest path algorithm, and a Dijkstra algorithm.

27. The system of claim 15, wherein the proposed flight assignment is generated using a revised simplex algorithm.

28. The system of claim 15, wherein the flight assignment plan is generated using a branch and bound method.

29. A method for generating an aircraft routing proposal, the method comprising:

receiving information describing a possible flight of an aircraft, wherein the information includes maintenance and operational constraints;

generating a flight network from the received information;

modeling at least one of the maintenance and operational constraints; and

determining an aircraft routing proposal for the aircraft that satisfies the received information.

30. The method of claim 29, wherein modeling at least one of the maintenance and operational constraints includes generating a flow balance constraint for each node in the flight network.

31. The method of claim 29, wherein modeling at least one of the maintenance and operational constraints includes generating a swapping criterion constraint.

32. The method of claim 29, wherein modeling at least one of the maintenance and operational constraints includes generating a flying time constraint.

33. The method of claim 29, wherein modeling at least one of the maintenance and operational constraints includes generating a number of cycles on the aircraft before performing maintenance test constraint.

34. The method of claim 29, wherein modeling at least one of the maintenance and operational constraints includes generating a occurrence of scheduled maintenance check constraint.

36. The system of claim 33, wherein the modeling means generates a flow balance constraint for each node in the flight network.

37. The system of claim 33, wherein the modeling means generates a swapping criterion constraint.

38. The system of claim 33, wherein the modeling means generates a flying time constraint.

39. The system of claim 33, wherein the modeling means generates a number of cycles on the aircraft before performing maintenance test a constraint.

40. The system of claim 33, wherein the modeling means generates an occurrence of scheduled maintenance check constraint.

35. A system for generating an aircraft routing proposal, the system comprising:

means for receiving information describing a possible flight of an aircraft, wherein the information includes maintenance and operational constraints;

means for generating a flight network from the received information;

means for modeling at least one of the maintenance and operational constraints; and

means for determining an aircraft routing proposal for the aircraft that satisfies the received information.

41. A mobile vehicle routing method comprising:

generating a vehicle routing proposal based on information describing a possible arc of a vehicle;

determining a proposed arc assignment for the vehicle based on the generated vehicle routing proposal and complying with the information describing the possible arc of the vehicle;

determining whether the proposed arc assignment meets a decision criterion describing requirements for vehicle routing;

if the decision criterion is unmet, optimizing the proposed arc assignment to meet the decision criterion; and

generating an arc assignment plan using the proposed arc assignment that meets the decision criterion.