Multi-dimensional route optimizer

Details Multi-dimensional route optimizer Multi-dimensional route optimizer

1998-12-31

2001-07-24

Zanelli, Michael J. (Department: 3661)

Data processing: vehicles, navigation, and relative location

Navigation

Determination of travel data based on the start point and...

C701S209000

Reexamination Certificate

active

06266610

ABSTRACT:

TECHNICAL FIELD
Disclosed is a method and system for optimizing the path of a vehicle in multi-dimensional space. In particular, aircraft flight path optimization is disclosed.
COPYRIGHT NOTICE AND PERMISSION
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent disclosure, as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all copyright rights whatsoever. The following notice applies to the software and data as described below and in the drawings hereto: Copyright© 1998, Honeywell, Inc., All Rights Reserved.
BACKGROUND ART
For safety and efficiency reasons, aircraft routing is commonly along predetermined air routes or great circle routes. Predetermined air routes are often aligned with ground-based navigational aids. In some cases, air routes circumvent geographical regions. Great circle routes, on the other hand, promise shorter flight distances.
Weather affects both the efficiency and the safety of a particular flight. Aircraft efficiency improves with favorable winds. In suitable tailwinds, ground speed increases and fuel consumption drops. Reduced fuel consumption often means that additional revenue-generating payload can be carried. Increased ground speed means that flight times are reduced resulting in operational cost savings.
Similarly, hazardous weather can impose a wide variety of costs on aircraft operations. Such costs can range from an uncomfortable ride for passengers at the low end, to structural damage, and even loss of aircraft and lives, at the other extreme. Aircraft operators typically go to great length to avoid hazardous weather.
In addition, certain geographical and political regions are covered by restricted airspace. Certain regions are preferably avoided by aircraft because costly over flight fees may be imposed.
Achieving a desired arrival time is important because it allows the operator to more accurately schedule flights and enjoy greater operational efficiency. Aircraft operating on pre-determined air routes or great circle routes may be forced to make costly adjustments to airspeed in order to meet scheduling requirements.
Typical flight path routing fails to consider operational costs associated with atmospheric phenomena, hazardous weather avoidance, region avoidance and arrival time constraints. There exists a need for a system that addresses these shortcomings.
SUMMARY
The invention determines an optimized route between a starting location and a destination by minimizing a cost function. The cost function is based on factors including fuel consumed, time, over-flight fees and penalty fees associated with restricted airspace. The invention implements an optimization algorithm for determining both lateral and vertical planes. The routes may be displayed over a global map with data including overlays depicting wind fields and restricted regions. Global databases may provide the data for wind conditions, weather, and temperature profiles.
In one embodiment, the invention determines the lateral path using a dynamic programming algorithm. In one embodiment, the algorithm operates by constructing a rectangular grid that overlays both the origin and destination location. Determination of the optimal lateral path proceeds in stages beginning with the initial, or origin location. At each stage, the algorithm examines the transition cost from the current node to each of a set of possible nodes. Optimization of the transition costs for each stage proceeds until the destination location has been reached.
The vertical path is determined using calculus of variations methods. Calculus of variations methods is a generalized optimization technique and is known in the art. In one embodiment, the vertical path is based on predetermined data stored as a function of parameters including wind speed, aircraft weight and cost index.
A filter is used to smooth the route while it is being generated. Filtering improves the quality of the route by minimizing the effects of quantization. Quantization of the calculation may result in an optimal route that requires excessive heading and altitude changes.
The user can select from among various routing choices. For example, wind-optimization routing results in substantially maximizing the favorable effects of tailwinds and substantially minimizing the detrimental effects of headwinds. Region avoidance routing provides an optimal route that circumvents specified geographical regions. Similarly, over-flight routing provides an optimal route that considers over-flight costs in calculating a route. Required time of arrival routing provides an optimal route that achieves a desired arrival time.


REFERENCES:
patent: 3566060 (1971-02-01), Phillips et al.
patent: 4774670 (1988-09-01), Palmieri
patent: 4812990 (1989-03-01), Adams et al.
patent: 5041982 (1991-08-01), Rathnam
patent: 5051910 (1991-09-01), Liden
patent: 5086396 (1992-02-01), Waruszewski, Jr.
patent: 5255190 (1993-10-01), Sznaider
patent: 5265024 (1993-11-01), Crabill et al.
patent: 5408413 (1995-04-01), Gonser et al.
patent: 5445021 (1995-08-01), Cattoen et al.
patent: 5457634 (1995-10-01), Chakravarty
patent: 5521826 (1996-05-01), Matsumoto
patent: 5574647 (1996-11-01), Liden
patent: 5615118 (1997-03-01), Frank
patent: 5878368 (1999-03-01), DeGraaf
patent: 5884223 (1999-03-01), Tognazzini
patent: 5899955 (1999-05-01), Yagyu et al.
patent: 5916299 (1999-06-01), Poppen
patent: 6005494 (1999-12-01), Schramm
patent: 6085147 (2000-07-01), Myers
patent: 6112141 (2000-08-01), Briffe et al.
patent: 2138092 (1995-06-01), None
patent: 3126891 (1983-01-01), None
patent: 19621437 (1996-12-01), None
patent: 2723219A (1996-02-01), None
patent: 8061974 (1996-03-01), None
patent: 8313290 (1996-11-01), None
patent: 8321000 (1996-12-01), None
patent: 9201905A (1992-02-01), None
patent: 9518498 (1995-07-01), None
patent: 9728423 (1997-08-01), None
patent: 97/47947 (1997-12-01), None
Aho, A.V., et al., “Date Structures And Algorithms—Section 6.3 The Single Shortest Path”, Addison—Wesley Publishing Company, Menlo Park, California, (1983).
Bellman, R., “On a Routing Problem”,Quarterly of Applied Mathematics 16(1) : 87-90, (1958).
Bellman, R.E., et al., “Applied Dynamic Programming—Section 24—A Routing Problem”,In Applied Dynamic Programming: 229-231, Princeton University Press, Princeton, New Jersey, (1962).
Denton, R.V., et al., “Applications of Autopath Technology to Terrain Obstacle Avoidance”, Naecon Conference Proceedings: 1373-1376, (1982).
Denton, R.V., et al., “Optimal TF/TA Route Planning Using Digital Terrain Elevation Data”, CH1839-0/83/000-0061 1983IEEE: 14.3.1-14.3.6, (1983).
Johnson, D.B., “Efficient Algorithms for Shortest Paths in a Sparse Network”,Journal of the ACM 24(1) : 1-13, Mar. 1977, 1-13, (1977).
Kriegel, E.K., et al., “Technology and Standards for a Common Air Mission Planner, Air Vehicle Mission Control and Management”, AGARD Conference Proceedings 504, 1992: 19-1 through 19-17, MITRE Corporation, Burlington Road Bedford, Massachusetts 01730 USA, (1992).
Schultz, R.L., “Three Dimensional Trajectory Optimization For Aircraft”,AIAA Journal of Guidance, Control, and Dynamics; vol. 13; No. 6; Nov.-Dec. 1990: 936-943, (1990).
Schultz, R.L., et al., “Aircraft Performance Optimization”,Journal of Aircraft; vol. 9; No. 2; Feb. 1972: 108-114, (1972).

Affiliated with

Also associated with

Rating

Multi-dimensional route optimizer does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Multi-dimensional route optimizer, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multi-dimensional route optimizer will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2528888