System and method for generating optimal flight plans for airline operations control

• US 6,134,500 A
• Filed: 06/03/1999
• Issued: 10/17/2000
• Est. Priority Date: 06/03/1999
• Status: Expired due to Term

• Current Assignee: United Airlines, Inc. (United Airlines Holdings, Inc.)
• Original Assignee: United Air Lines Incorporated (United Airlines Holdings, Inc.)
• Inventors: Mukherjee, Amit, Tang, Baoxing
• Primary Examiner(s): Cuchlinski, Jr., William A.
• Assistant Examiner(s): Beaulieu, Yonel
• Application Number:
  US09/324,687
• Time in Patent Office: 502 Days
• Field of Search: 701/3-5, 701/7, 701/10, 701/11, 701/200, 701/201, 701/202, 701/203, 701/205, 342/26, 342/34, 244/158 R, 73/178 R
• US Class Current: 701/202
• CPC Class Codes: G05D 1/0005 with arrangements to save energy
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem

Abstract

A system and method for generating a minimum-cost airline flight plan from a point of origin through a set of fix points to a destination point. A set of navigation airways from the point of origin to the destination point, including predefined fix points and vectors for high altitude flight, and a set of predetermined flight planning altitudes is stored in a database. Operational data for the flight and weather data for the flight is also stored in the database, as well as station data, station approach and departure procedures, predefined flight restricted areas, and flight performance data. The predefined fix points are transformed from the Cartesian plane onto a new coordinate system based on the great circle route between the origin and the destination. Each transformed fix point is assigned an ordinal value, and an acyclic network is constructed based on the ordinal values and within a feasible search region which excludes any flight restricted areas. Using dynamic programming techniques and shortest path optimization, a minimum cost flight path from the point of origin through a plurality of predefined navigation fix points to a destination point is calculated. The minimum cost flight path calculations take into account weather data for predetermined flight planning altitudes, aircraft weight and payload data, and performance data. The system comprises a general purpose computer having a memory, a database stored in the memory, and a means executing within the general purpose computer for determining the minimum cost flight path from a point of origin through a set of predefined navigation fix points to a destination point.

Claims

1. A method for generating a minimum-cost airline flight plan from a point of origin through a plurality of fix points to a destination point, comprising the steps of:

storing in at least one database navigation data, including a plurality of fix points, aircraft performance data, operational flight data, a plurality of flight planning altitudes, and weather data;

constructing a two-dimensional rectangular macro region bounded by a normal to the great circle route between the point of origin and the destination point, where the normal intersects the origin, a normal to the great circle route intersecting the destination, a first horizontal bound perpendicular to said normals and located a specified distance from the great circle route, and a second horizontal bound parallel to the first bound and located an equal distance from the great circle route as the first bound;

transforming each point in the plurality of fix points from a point on a Cartesian plane to a point, expressed as an ordered pair of an x-value and a y-value, on an alternate coordinate system where the origin of the alternate coordinate system is the point of origin of the flight and the destination point of the flight is on one of the axes of the alternate coordinate system;

determining a two-dimensional feasible region within the macro region;

constructing a feasible acyclic network which includes only those arcs of a first acyclic network of the macro region which lie within said feasible region and outside of flight restricted areas; and

generating a minimum-cost flight plan from the point of origin through said plurality of fix points to the destination point.

2. The method of claim 1, wherein the step of determining a two-dimensional feasible region further comprises the step of:

constructing said first acyclic network comprising a plurality of arcs in the macro region.

3. The method according to claim 2, wherein the step of determining a two-dimensional feasible region further comprises the step of determining a wind distance of each arc in the acyclic network at each altitude of the plurality of altitudes.

4. The method of claim 3, wherein the step of determining a two-dimensional feasible region further comprises the step of computing the shortest path from the point of origin to the destination point for each of the plurality of altitudes, where the cost of each arc is the wind distance of the arc at the altitude specified.

5. The method of claim 4, wherein the step of determining a two-dimensional feasible region further comprises the step of determining the point having a maximum positive y-value over all shortest path calculations at all altitudes, and the point having a minimum negative y-value over all shortest path calculations at all altitudes.

6. The method of claim 5, wherein the step of determining a two-dimensional feasible region further comprises forming a rectangular boundary for the feasible region, the boundary comprising the normal to the great circle route at the point of origin, the normal to the great circle route at the destination point, a first horizontal bound parallel to the great circle route and intersecting the point having the maximum positive y-value, and a second horizontal bound parallel to the great circle route and intersecting the point having the minimum possible y-value.

7. The method of claim 1, wherein the fix points are expressed prior to transformation as an ordered pair of latitude and longitude values.

8. The method of claim 7, wherein the step of transforming each fix point further comprises the steps of:

determining an orientation representing the angle between the point of origin of the flight and the destination point of the flight;

determining a longitudinal distance between the fix point and the point of origin of the flight;

determining a latitudinal distance between the fix point and the point of origin of the flight;

determining a transformed x-coordinate of the fix point; and

determining a transformed y-coordinate of the fix point.

9. The method of claim 8, wherein a point of interception on the great circle route between the point of origin and the destination point is determined for each transformed navigation fix point by drawing a normal from the transformed fix point to said great circle route.

10. The method of claim 9, wherein the transformed navigation fix points from origin to destination are sorted in an ascending rank by sorting the intercept points in order of ascending x-coordinate value, wherein each of said intercept points is associated with one transformed navigation fix point.

11. The method of claim 10, wherein the acyclic network contains only those arcs that connect a point of lower rank to a point of higher rank.

12. The method of claim 9, wherein a first normal intersects with the point of origin, and a second normal intersects with the destination point.

13. The method of claim 1, wherein said macro region is bounded on a first side by a normal to the great circle route intersecting the point of origin and on a second side by a normal to the great circle route intersecting the destination point.

14. The method of claim 13, wherein said macro region is bounded on a third side and a fourth side by two lines parallel to and equidistant from the great circle route between the point of origin and the destination point at a predetermined distance.

15. The method of claim 1, further comprising the step of receiving flight performance data.

16. The method of claim 1, wherein the step of generating the minimum-cost flight plan from the point of origin through said plurality of fix points to the destination point further comprises the steps of:

computing a final descent path;

computing a cruise path; and

computing an initial climb path.

17. The method of claim 16, wherein the step of computing the final descent path and the cruise path further comprises the steps of:

computing backwards, starting from the destination point, the shortest wind distance path from the point of origin of the flight to the destination point of the flight, where the value of each arc is the shortest wind distance at 18000 feet;

determining the descent distance for each flight planning altitude, where said descent distance represents the contour of points around the destination point from which the aircraft can descend;

determining for each point on the shortest path from the point of origin to the destination point a first descent distance that is closest in value to the actual shortest wind distance and a second descent distance that is second closest in value to the actual shortest wind distance;

storing a contour flag value for each transformed fix point in the feasible region if the shortest wind distance from a fix point to the destination point is less than the larger of the first or second descent distances but greater than or equal to the smaller of the first or second descent distances; and

examining each fix point in the feasible acyclic network as a first fix point.

18. The method of claim 17, wherein the step of examining a first fix point comprises the steps of:

adding to the final descent path an arc from the first fix point to a second fix point, if the arc is on the shortest wind distance path from the first fix point to the destination point at 18000 feet, and the contour flag of the first point corresponds to the lowest flight planning altitude;

adding to the final descent path an arc from the first fix point to a second fix point, if the arc is on the shortest wind distance path from the first fix point to the destination point at 18000 feet and the altitude corresponding to the contour flag for the first fix point is greater than the lowest flight planning altitude and is also greater than the altitude corresponding to the contour flag for the second fix point;

considering for cruise computation an arc from the first fix point to a second fix point, if the arc is not on the shortest wind distance path from the first fix point to the destination point at 18000 feet, but the altitude corresponding to the contour flag for the first fix point is greater than the lowest flight planning altitude and is also greater than the altitude corresponding to the contour flag for the second fix point; and

considering for cruise computation an arc from the first fix point to a second fix point, if the altitude corresponding to the contour flag for the first fix point is equal to the altitude corresponding to the contour flag for the second fix point, and both of these altitude values are greater than the lowest flight planning altitude.

19. The method of claim 18, wherein the step of considering an arc from a first fix point to a second fix point for cruise computation comprises the steps of:

finding the vector minima for each arc over all flight planning altitudes, and then finding the fix minima if the first fix point has multiple arcs emanating from it to points with a higher ordinal value;

computing a cruise path along said single arc if the first fix point has a single arc from it to points with a higher ordinal value but said arc is not a short segment; and

computing a cruise path along said short segment if the first fix point has a single arc from it to points with a higher ordinal value and said arc is a short segment.

20. The method of claim 19, wherein the step of computing a cruise path along a single arc comprises the steps of:

dividing the arc into a plurality of stages;

for each stage, storing a set of state variables, where each state variable corresponds to a flight planning altitude;

computing at each stage a cruise cost value and a climb cost value, going backwards from the second fix point; and

selecting the minimum of the cruise cost value and the climb cost value in order to determine whether to cruise or climb to the next stage.

21. The method according to claim 20, wherein the stages are separated by intervals of 50 nautical miles, with any remaining distance added to the stage nearest the second fix point.

22. The method of claim 20, wherein the step of computing a climb cost value comprises the following steps:

determining the distance to the next stage at the same flight planning altitude;

determining a step climb distance to go to the next stage and the next higher flight planning altitude;

determining an excess cruise distance which is the difference between the step climb distance and the distance to the next stage;

determining the nautical air miles value using the aircraft performance data and aircraft weight data;

calculating the nautical ground miles value using the nautical air miles value, mach air speed for the arc, true air speed for the arc, and the wind value for the arc;

calculating a step climb fuel burn value based on the aircraft performance data and aircraft weight data;

calculating a remaining fuel burn value for cruise using the nautical ground miles value and the excess cruise distance value;

determining a fuel burn value by adding the step climb fuel burn value to the remaining fuel burn value for cruise;

calculating a step climb flight time value based on the aircraft performance data and the aircraft weight data;

calculating a remaining flight time value for cruise using the true air speed for the arc, the wind value for the arc, and the excess cruise distance value;

determining a flight time by adding the step climb flight time value to the remaining flight time value for cruise;

multiplying the fuel burn by a predetermined fuel cost value;

multiplying the flight time by a predetermined time cost value; and

adding the product of the fuel burn and the fuel cost and the product of the flight time and the time cost to the cost value of the previous stage.

23. The method of claim 20, wherein the step of computing a cruise cost value comprises the following steps:

determining the distance to the next stage at the same flight planning altitude;

calculating the nautical ground miles value;

calculating the fuel burn;

calculating the flight time;

multiplying the fuel burn by a predetermined fuel cost value;

multiplying the flight time by a predetermined time cost value; and

adding the product of the fuel burn and the fuel cost and the product of the flight time and the time cost to the cost value of the previous stage.

24. The method of claim 19, wherein the step of computing a cruise path along a short segment comprises the steps of:

for each flight planning altitude, storing a state variable;

computing a cruise cost value;

computing a climb cost value;

selecting the minimum of the cruise cost value and the climb cost value in order to determine whether to cruise or climb at the next stage and the cost value of the next stage; and

storing the minimum value in the state variable.

25. The method of claim 24, wherein the step of computing a cruise cost value along a short segment comprises the steps of:

determining the distance to the second fix point at the same flight planning altitude;

calculating the nautical ground miles value;

calculating the fuel burn;

calculating the flight time;

multiplying the fuel burn by a predetermined fuel cost value;

multiplying the flight time by a predetermined time cost value; and

adding the product of the fuel burn and the predetermined fuel cost value to the product of the flight time and the predetermined time cost value.

26. The method of claim 24, wherein the step of computing a climb cost value along a short segment comprises the steps of:

determining the distance to the next stage at the same flight planning altitude;

determining the step climb distance to go to the next stage and the next higher flight planning altitude;

determining an excess cruise distance which is the difference between the step climb distance and the distance to the next stage;

determining the nautical air miles value using the aircraft performance data and the aircraft weight data;

determining the nautical ground miles value using the nautical air miles value, mach air speed for the arc, true air speed for the arc, and the wind value for the arc;

calculating a step climb fuel burn value based on the aircraft performance data and the aircraft weight data;

calculating an excess fuel burn value using the nautical ground miles value and excess cruise distance;

determining a fuel burn value by subtracting the excess fuel burn value from the step climb burn value;

calculating a step climb flight time value based on the aircraft performance data and the aircraft weight data;

calculating an excess flight time value using the true air speed for the arc, the wind value for the arc, and the excess cruise distance value;

determining a flight time by subtracting the excess flight time value from the step climb flight time value;

multiplying the fuel burn by a predetermined fuel cost value;

multiplying the flight time by a predetermined time cost value; and

adding the product of the fuel burn and the predetermined fuel cost value to the product of the flight time and the predetermined time cost value.

27. The method of claim 16, wherein the step of computing the initial climb path further comprises the steps of:

computing forward, starting from the point of origin, a set of shortest wind distance paths from the point of origin of the flight to each fix point in the feasible region, where the value of each arc is the shortest wind distance at 18000 feet; and

computing an optimal climb path.

28. The method of claim 27, wherein the step of computing an optimal climb path comprises the steps of:

computing a set of climb distances for each flight planning altitude, from the origin to each feasible climb point, where each feasible climb point is connected to the origin by an arc in the feasible acyclic network, where said arc is used in a feasible path from the point of origin to the destination point, and the climb distances are calculated using the optimal fuel burn specified for that fix point and altitude value;

determining, for each flight planning altitude and for all first fix points in the feasible acyclic network, whether the climb distance computed using the fuel weight at each first fix point is greater than the climb distance computed using the fuel weight at a second fix point, where the first and second fix points are consecutive fix points connected by an arc in the feasible acyclic network, and the point of origin is connected to the first fix point by an arc in the feasible acyclic network;

determining, for each flight planning altitude and for all feasible arcs connected to the point of origin, whether an arc is a valid climb by determining whether a wind distance from the point of origin to each first fix point connected to it by a feasible arc is less than a climb distance computed using the fuel weight at each first fix point, and whether a wind distance from the point of origin to a second fix point is greater than said climb distance, where the first and second fix points are consecutive fix points connected by an arc in the feasible acyclic network, and the point of origin is connected to the first fix point by an arc in the feasible acyclic network;

calculating a takeoff weight for each feasible arc connected to the origin;

determining the optimal climb by determining the feasible arc connected to the point of origin that is a valid climb and that has the lowest climb distance;

determining if the takeoff weight is valid in comparison with a set of predetermined weight limits; and

returning a valid flight plan if the takeoff weight is valid, or an error message if the takeoff weight is invalid.

29. The method of claim 1, further comprising the step of storing the weather data in the form of a 3-tuple of wind direction, wind value, and temperature for each altitude.

30. The method of claim 1, wherein the step of determining the feasible region further comprises the steps of:

determining the shortest path in said acyclic network from the origin to the destination at each of said set of predetermined altitudes;

for each said shortest path at each said specified altitude, determining the transformed fix point which is the largest y-value;

determining the transformed fix point with the largest y-value across all specified altitudes;

for each said shortest path at each said specified altitude, determining the transformed fix point which has the minimum y-value;

determining the transformed fix point with the minimum y-value across all specified altitudes; and

forming a region bounded on a first side by the normal to the great circle route intersecting the destination, on a second side by the normal to the great circle route intersecting the origin, on a third side by a line parallel to the great circle route which intercepts the maximum y-value plus a predetermined buffer value, and a fourth side by a line parallel to the great circle route which intercepts the minimum y-value subtracted by said predetermined buffer value.

31. The method of claim 30, wherein the cost of each arc in said acyclic network at a specified altitude is the wind distance of the arc at said specified altitude.

32. The method of claim 31, wherein the wind distance of an arc from a first fix point to a second fix point at a specified altitude is determined by:

retrieving a value for ground distance of the arc from the database in the general purpose computer;

determining a mach air speed for said arc at said specified altitude;

determining a true air speed for said arc at said specified altitude; and

determining the wind distance for said arc at said specified altitude.

33. A system for generating a minimum-cost airline flight plan from a point of origin through a plurality of fix points to a destination point, comprising:

a land-based general purpose computer having a memory;

at least one database stored in the memory, comprising navigation data, including a Plurality of fix points, operational flight data, a plurality of flight planning altitudes, and weather data;

means executing within the general purpose computer for determining the minimum-cost airline flight path from a point of origin through a plurality of fix points to a destination point so that the path is constructed in an acyclic network that is constructed within a feasible region that is determined within the boundaries of a two-dimensional rectangular macro region, wherein said feasible region is bounded on a first side by the normal to the great circle route intersecting the destination, on a second side by the normal to the great circle intersecting the origin, on a third side by a maximum deviation from the great circle plus a predetermined buffer value, and on a fourth side by a minimum deviation from the great circle region minus a predetermined buffer value.

34. The system of claim 33, further comprising:

means executing within the general purpose computer for transforming each point in the set of navigation fix points in the database from a point on a Cartesian plane to a point on an alternate coordinate system where the origin of the alternate coordinate system is the point of origin of the flight and the destination point of the flight in one of the axes of the alternate coordinate system, and where each transformed fix point is expressed as an ordered pair of a x-coordinate value and a y-coordinate value;

means executing within the general purpose computer for sorting the set of transformed fix points in an ascending ordinality;

means executing within the general purpose computer for constructing an acyclic network that contains all arcs that connect a transformed fix point of lower ordinality to a point of higher ordinality;

means executing within the general purpose computer for determining a shortest path in the acyclic network from the origin to the destination at each altitude in the set of predetermined altitudes;

means executing within the general purpose computer for determining for each said shortest path at each specified altitude, the transformed fix point which is the smallest y-coordinate value; and

means executing within the general purpose computer for determining the transformed fix point with the smallest y-coordinate value across all specified altitudes.

35. The system of claim 34, further comprising:

means executing within the general purpose computer for determining for each said shortest path at each said specified altitude the transformed fix point which is the largest y-coordinate value; and

means executing within the general purpose computer for determining the transformed fix point with the largest y-coordinate value across all specified altitudes.

36. The system of claim 33, wherein each navigation fix point in the at least one database prior to transformation is expressed as an ordered pair of latitude and longitude values.