Multi-dimensional route optimizer

• US 6,266,610 B1
• Filed: 12/31/1998
• Issued: 07/24/2001
• Est. Priority Date: 12/31/1998
• Status: Expired due to Term

• Current Assignee: Honeywell Incorporated (Honeywell International Inc.)
• Original Assignee: Honeywell International Inc.
• Inventors: Schultz, Robert L., Shaner, Donald A.
• Primary Examiner(s): Zanelli, Michael J.
• Application Number:
  US09/223,846
• Time in Patent Office: 936 Days
• Field of Search: 701/201, 701/202, 701/209, 701/211, 701/204
• US Class Current: 701/201
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G05D 1/0005 with arrangements to save energy
• CPC Class Codes: G05D 1/106 Change initiated in response to external conditions, e.g. avoidance of elevated terrain or of no-fly zones
• CPC Class Codes: G05D 1/1062 specially adapted for avoiding bad weather conditions
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G08G 5/0034 Assembly of a flight plan

Abstract

A system and method of optimizing a multi-dimensional route, such as an aircraft flight path, using a lateral path optimizer and a vertical path optimizer. The lateral path is determined by searching for a path among nodes that minimizes a cost function. The vertical path is determined by reference to pre-determined data generated as a function of aircraft parameters and wind speed. The optimized route is filtered as it is being generated. The optimized route is not limited by pre-determined waypoints.

Claims

1. A method of determining a route between an origin and a destination comprising:

beginning at the origin, determining multiple feasible segments from the origin to a node at the end of each feasible segment wherein at least one segment is not directed toward the destination;

iteratively determining further segments from the nodes to create multiple segment paths between the origin and the destination; and

determining the segment path between the origin and destination having the least cost.

2. The method of claim 1 wherein the determination of least cost is a function of weather conditions.

3. The method of claim 1 wherein the determination of least cost is a function of time.

4. The method of claim 1 wherein up to three feasible segments are determined from each node.

5. The method of claim 1 wherein up to nine feasible segments are determined from each node.

6. The method of claim 1 wherein the segments are constrained to lie within a grid logically constructed to contain the origin and destination.

7. The method of claim 6 wherein the nodes are uniformly dispersed within the grid, and the segments are defined to span between selected nodes.

8. The method of claim 1 wherein determining the segment path between the origin and destination having the least cost comprises evaluating a cost function.

9. The method of claim 1 wherein determining the segment path between the origin and destination having the least cost comprises minimizing a cost function.

10. The method of claim 1 wherein determining the segment path between the origin and destination having the least cost comprises minimizing a weighted cost function.

11. The method of claim 1 wherein determining the segment path between the origin and destination having the least cost comprises minimizing a weighted cost function, and further comprising establishing a weight for a term of the weighted cost function.

12. The method of claim 1 wherein each segment path has a heading, and further comprising filtering to minimize the number of segment path heading changes.

13. The method of claim 1 wherein each segment path has a length, and further comprising filtering to reduce the length of the segment path.

14. A method of selecting a flight path from an origin to a destination, the method comprising:

defining a plurality of nodes in a lateral plane, wherein the plurality of nodes comprises the origin and destination;

generating a plurality of possible lateral flight paths from the origin to the destination, wherein the plurality of possible lateral flight paths comprise segments, further wherein each of the segments connects two of the plurality of nodes;

generating an optimized lateral flight path, wherein the optimized lateral flight path is one flight path of the plurality of possible lateral flight paths that satisfies a desired optimization criteria, further wherein the desired optimization criteria comprises at least one criteria selected from the group consisting of wind-optimization, region avoidance, over-flight fee minimization and required time of arrival; and

filtering the optimized lateral flight path while it is being generated.

15. The method of claim 14 further comprising generating an optimized vertical flight path from the origin to the destination, wherein the optimized vertical flight path is a function of predetermined parameters, further wherein the predetermined parameters include aircraft weight, wind speed and a cost index.

16. The method of claim 15 further comprising selecting the filtered optimized lateral flight path and the optimized vertical flight path as the flight path.

17. The method of claim 14 wherein filtering the optimized lateral flight path while it is being generated comprises reducing the length of the optimized lateral flight path as a function of the distances between a set of nodes.

18. The method of claim 14 wherein generating an optimized lateral flight path comprises determining the cost, as a function of the direction of approach, associated with transit to selected nodes.

19. The method of claim 14 wherein defining a plurality of nodes in a lateral plane comprises defining nodes in a geometrically ordered arrangement.

20. The method of claim 14, wherein generating an optimized lateral flight path comprises accessing data selected from the group consisting of atmospheric data, wind field data, restricted airspace data and over-flight fee data.

21. The method of claim 14, further comprising displaying the filtered optimized lateral flight path on a visual display.

22. The method of claim 14 further comprising generating an optimized vertical flight path between the origin and the destination using a generalized optimization technique on predetermined data.

23. The method of claim 14 further comprising generating an optimized vertical flight path between the origin and the destination using a calculation of variations method on predetermined data.

24. The method of claim 14 further comprising generating an optimized vertical flight path between the origin and destination using predetermined data, the predetermined data comprising wind speed, weight and a cost index.

25. The method of claim 14 wherein filtering comprises minimizing the number of flight path heading changes.

26. The method of claim 14 wherein filtering comprises reducing the length of the flight path.

27. A computer-implemented method of selecting an optimized flight path from an origin location to a destination location, such that the selected flight path satisfies specified optimization criteria, the method comprising:

defining a grid that encompasses the location of origin and the location of destination, wherein the grid comprises a plurality of nodes of which the origin and destination are nodes therein;

generating a lateral flight path by selecting a set of nodes, such that the selected set of nodes satisfies the optimization criteria;

generating a vertical flight path within the grid as a function of wind speed, weight of an aircraft operated on the flight path and a cost index;

adjusting the lateral flight path while generating the lateral flight path to reduce the length of the lateral flight path; and

selecting the adjusted lateral flight path and the vertical flight path as the flight path.

28. The method of claim 27 wherein generating a lateral flight path by selecting a set of nodes that satisfies the optimization criteria comprises generating a lateral flight path by selecting a set of nodes that substantially satisfies a criteria selected from the group consisting of minimizing a cost function, minimizing the fuel consumed by the aircraft, minimizing the time en route, minimizing over-flight fees associated with specified airspace, avoiding a specified region, and satisfying a required time of arrival.

29. The method of claim 27 wherein the grid includes a plurality of uniformly spaced nodes and generating a lateral flight path includes evaluating the optimization criteria at selected nodes.

30. The method of claim 27 wherein generating a lateral flight path by selecting a set of nodes, such that the selected set of nodes satisfies the optimization criteria includes accessing data selected from the group consisting of atmospheric data, wind field data, restricted airspace data and over-flight fee data.

31. A flight path optimizing system for selecting an optimal flight path, that satisfies specified criteria, from an origin location to a destination location, the system comprising:

a location database, wherein the contents of the location database corresponds to locations of origin and destination;

a data file, wherein the contents of the data file comprises data corresponding to the location database and the contents of the data file corresponds to data selected from the group consisting of atmospheric data, wind field data, restricted airspace data and over-flight fee data;

a vehicle model file, wherein the contents of the vehicle model file corresponds to data representative of fuel flow rates and vehicle performance;

a lateral path solver, wherein the lateral path solver includes programming to cause the system to search a lateral region for a lateral path that satisfies the specified criteria;

a vertical path solver, wherein the vertical path solver includes stored data representative of fuel flow rate, altitude and vehicle speed as a function of vehicle weight, wind speed and cost index; and

a display member to display the lateral path and vertical path.

32. The system of claim 31 further including a filter wherein the filter reduces the length of the lateral path.

33. The system of claim 31 wherein the wind field data comprises wind speed at a specified location and altitude.

34. The system of claim 31 wherein the vehicle is an aircraft.

35. A method of determining a route, comprising:

receiving an origin node;

receiving a destination node, the destination node located a distance from the origin node;

creating a grid comprising the origin node, the destination node, and a plurality of en route nodes;

determining the cost to transition to the destination node and each of the plurality of en route nodes including transitions to nodes not directed toward the destination node; and

selecting a subset of nodes from the plurality of en route nodes, the subset of nodes having the least total cost to transition from the origin node to the destination node.

36. The method of claim 35 wherein receiving an origin node comprises receiving an origin node expressed in global coordinates and receiving a destination node comprises receiving a destination node expressed in global coordinates, and further comprising:

transforming the global coordinates of the origin node into a coordinate system wherein the origin lies on an equator; and

transforming the global coordinates of the destination node into a coordinate system wherein the destination lies on the equator.

37. The method of claim 35 wherein receiving an origin node comprises receiving a user-selected origin node and receiving a destination node comprises receiving a user-selected destination node.

38. The method of claim 35 wherein determining the cost to transition comprises evaluating a cost function.

39. The method of claim 35 wherein determining the cost to transition comprises evaluating a user-specified cost function.

40. The method of claim 35 further comprising receiving a weighting factor for a cost function and wherein determining the cost to transition comprises evaluating the cost function.

41. The method of claim 35 further comprising receiving a user-specified weighting factor for a cost function and wherein determining the cost to transition comprises evaluating the cost function.

42. The method of claim 35 wherein determining the cost to transition comprises evaluating a cost function, the cost function comprising a factor for fuel.

43. The method of claim 35 wherein determining the cost to transition comprises evaluating a cost function, the cost function comprising a factor for time.

44. The method of claim 35 wherein determining the cost to transition comprises evaluating a cost function, the cost function comprising a factor for over-flight fees.

45. The method of claim 35 wherein determining the cost to transition comprises evaluating a cost function, the cost function comprising a factor for hazard costs.

46. The method of claim 35 further comprising displaying the route on a map.

47. The method of claim 35 further comprising determining the time of arrival at the destination node and each of the plurality of en route nodes, and selecting a subset of nodes comprises selecting a subset of nodes yielding a desired time of arrival at the destination node.

48. The method of claim 35 wherein determining the cost to transition to the destination node and each of the plurality of en route nodes comprises accessing wind information associated with the destination node and each of the plurality of en route nodes.

49. The method of claim 35 wherein determining the cost to transition to the destination node and each of the plurality of en route nodes comprises accessing over-flight fee information associated with each of the plurality of en route nodes.

50. The method of claim 35 wherein determining the cost to transition to the destination node and each of the plurality of en route nodes comprises accessing at least one of airspace classification information, weather information, political information, and environmental information associated with each of the plurality of en route nodes.

51. The method of claim 50 further comprising displaying at least one of the route and airspace classification information, weather information, political information, and environmental information on a map.

52. The method of claim 35 wherein selecting a subset of nodes from the plurality of en route nodes comprises iteratively calculating the cost to transition from each node to each of a plurality of subsequent nodes.

53. The method of claim 35 further comprising receiving a vehicle performance model and wherein determining the cost to transition to the destination node and each of the plurality of en route nodes comprises accessing the vehicle performance model.

54. A method of determining a route, comprising:

receiving an origin node;

receiving a destination node, the destination node remote from the origin node;

selecting a plurality of intermediate nodes;

each of the plurality of intermediate nodes remote from the origin node and the destination node, and each of the plurality of nodes lying on one or more non directed routes between the origin node and the destination node;

determining a transition cost for each of the plurality of intermediate nodes and the destination node; and

selecting a route from the one or more routes, the route selected having the lowest transition cost.

55. The method of claim 54 wherein determining a transition cost for each of the plurality of intermediate nodes and the destination node comprises determining transition costs as a function of arrival direction for each of the plurality of intermediate nodes and the destination node.

56. The method of claim 54 wherein determining a transition cost for each of the plurality of intermediate nodes and the destination node comprises determining transition costs as a function of departure direction for each of the plurality of intermediate nodes and the origin node.

57. The method of claim 54 wherein determining a transition cost for each of the plurality of intermediate nodes and the destination node comprises determining transition costs for each of the plurality of intermediate nodes and the destination node using an iterative calculation process.

58. The method of claim 54 wherein determining a transition cost for each of the plurality of intermediate nodes and the destination node comprises identifying a subset of the plurality of intermediate nodes and the destination node as active and determining transition costs as a function of arrival direction for each of the active nodes.

59. The method of claim 54 wherein the transition cost associated with a node is a function of one of the location of the node and a function of the weather at a node.

60. The method of claim 54 wherein the transition cost associated with a node is a function of an overflight fee associated with the node.

61. The method of claim 54 further comprising selecting a vertical path as a function of wind speed, wind direction, vehicle weight and a cost index.

62. The method of claim 54 further comprising smoothing the selected route.

63. The method of claim 54 further comprising displaying the selected route on a monitor.

64. A method of selecting a lateral route, comprising:

receiving an origin node;

receiving a destination node, the destination node remote from the origin node;

defining a plurality of paths, each path originating at the origin node and terminating at the destination node and traversing one or more intermediate nodes, wherein at least a portion of the non directed path is not directed toward the destination;

determining the cost associated with traversing each of the plurality of paths; and

selecting the path that satisfies a predetermined cost function.

65. The method of claim 64 wherein defining a plurality of paths comprises defining a plurality of intermediate nodes.

66. The method of claim 64 wherein determining the cost associated with traversing each of the plurality of paths comprises iteratively calculating costs associated with each intermediate node.

67. The method of claim 64 wherein selecting the path that satisfies a predetermined cost function comprises selecting the path having the least cost of arriving at the destination node.

68. The method of claim 64 wherein selecting the path that satisfies a predetermined cost function comprises selecting the path that satisfies a required time of arrival at the destination node.

69. The method of claim 64 wherein selecting the path that satisfies a predetermined cost function comprises selecting the path that satisfies a required time of arrival at the destination node, wherein satisfaction of the required time of arrival comprises iteratively adjusting the cost function.

70. The method of claim 69 wherein iteratively adjusting the cost function comprises adjusting a weight factor for time.

71. The method of claim 64 further comprising selecting a vertical path as a function of aircraft weight, wind conditions associated with each intermediate node, and a cost index.

72. The method of claim 64 wherein selecting the path that satisfies a predetermined cost function comprises evaluating the predetermined cost function for each intermediate node.

73. The method of claim 64 wherein the predetermined cost function comprises a weighted term and wherein selecting the path that satisfies a predetermined cost function comprises establishing a weight for a term in the predetermined cost function.

74. A method of determining a route between an origin and a destination for a vehicle taking into account variables as it moves along the route, the method comprising:

establishing a plurality of nodes in a grid encompassing the origin and destination;

beginning at the origin node, determining costs of moving the vehicle to multiple nodes in a non directed manner proximate to the origin node;

from each of the multiple nodes, determining transition costs of moving to further multiple nodes as a function of the variables; and

repeatedly determining further costs from the nodes to create multiple routes between the origin and the destination.

75. The method of claim 74 and further including tracking the total cost from the origin to each of the nodes for which a cost is determined from a previous node.

76. The method of claim 75 and further including repeating the determination of costs to move to further nodes from a node previously reached only if the total cost to reach the node is less than the previous total cost to reach the node.