HYBRID HEURISTIC NATIONAL AIRSPACE FLIGHT PATH OPTIMIZATION

• US 20090105935A1
• Filed: 10/17/2008
• Published: 04/23/2009
• Est. Priority Date: 10/17/2007
• Status: Active Grant

• Current Assignee: Lockheed Martin Corporation (Martin Marietta Corporation)
• Original Assignee: Lockheed Martin Corporation (Martin Marietta Corporation)
• Inventors: Suchkov, Alexander, Tibichte, Abderrazak, Zhang, Jingqiao, Crook, Ian, Subbu, Rajesh Venkat, Lizzi, John Michael, Jha, Pratik D.
• Granted Patent: US 8,185,298 B2
• Time in Patent Office: Days
• US Class Current: 701/120
• CPC Class Codes: G08G 5/0034 Assembly of a flight plan
• 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

Hybrid-heuristic optimization of competing portfolios of flight paths for flights through one or more sectors of an airspace represented by an air traffic system. In one embodiment, a hybrid-heuristic optimization process (100) includes one or more heuristic based processes (110), a genetic optimization process (120), an evaluation process involving an approximation model (130), an optimal portfolio selection process (140) and a validation process involving simulation (150) of the air traffic system.

Claims

1. A method for optimizing a plurality of competing portfolios of flight paths for flights through one or more sectors of an airspace represented by an air traffic system, said method comprising:

executing at least one heuristic-based process to construct successive portfolios of the flight paths for consideration, wherein the at least one heuristic-based process includes one or more configurable parameters that are applied in selecting the successive portfolios;

applying a genetic optimization process to identify the at least one heuristic-based process according to its one or more configurable parameters;

evaluating each successive portfolio constructed by the at least one heuristic-based process with an approximation model that approximates the air traffic system;

selecting an optimal portfolio of the flight paths from among the plurality of competing portfolios of flight paths based on results of said evaluating step; and

utilizing a simulation of the air traffic system to validate the optimal portfolio of flight paths selected in said selecting step.

2. The method of claim 1 wherein said step of utilizing a simulation of the air traffic system comprises operating an air traffic simulator.

3. The method of claim 1 wherein said executing at least one heuristic-based process comprises:

receiving one or more flight path options for each flight and an order of preference associated with the flight path options for each flight;

assigning flights their first flight path option until a demand capacity imbalance is calculated using the approximation model; and

after a demand capacity imbalance is calculated, evaluating one or more additional flight path options for the flights until demand capacity balance is recovered or there are no remaining flight path options.

4. The method of claim 1 wherein said executing at least one heuristic-based process comprises:

assuming a projected future airspace demand, wherein the future airspace demand includes a plurality of sector-time periods;

identifying sector-time periods wherein demand capacity imbalances occur within the projected future airspace demand;

selecting flights that fly through problematic sector-time periods for re-planning;

evaluating alternative flight path options for the selected flights based upon a contribution of each flight path option to the identified demand capacity imbalance.

5. The method of claim 1 wherein the one or more configurable parameters included in the at least one heuristic-based process include a heuristic-type and one or more threshold parameters.

6. The method of claim 1 further comprising:

executing computer program code on at least one computer processor to perform said steps of executing at least one heuristic-based process, applying a genetic optimization process, evaluating each successive portfolio, selecting an optimal portfolio, and utilizing a simulation of the air traffic system.

7. The method of claim 6 further comprising:

outputting information identifying the flight paths included in the optimal portfolio on an output device in communication with the computer processor.

8. The method of claim 6 further comprising:

executing at least a portion of the computer program code in parallel within a multiprocessor computing environment or a distributed computing environment to perform at least one of said steps of executing at least one heuristic-based process, applying a genetic optimization process, evaluating each successive portfolio, and selecting an optimal portfolio, and utilizing a simulation of the air traffic system.

9. The method of claim 1 wherein the genetic optimization process comprises a multi-objective genetic optimization process.

10. A system that optimizes a plurality of competing portfolios of flight paths for flights through one or more sectors of an airspace represented by an air traffic system, said system comprising:

at least one heuristic-based filter that constructs successive portfolios of the flight paths for consideration, wherein the at least one heuristic-based filter includes one or more configurable parameters that are applied in selecting the successive portfolios;

a genetic optimizer that identifies the at least one heuristic-based filter according to its one or more configurable parameters;

an approximation model of the air traffic system that is usable to evaluate each successive portfolio constructed by the at least one heuristic-based filter, wherein results of the evaluations of each successive portfolio by the approximation model are used to select an optimal portfolio of the flight paths from among the plurality of competing portfolios of flight paths; and

a simulation of the air traffic system usable to validate the optimal portfolio of flight paths selected in accordance with results of the evaluations of each successive portfolio by the approximation model.

11. The system of claim 10 wherein said simulation of the air traffic system comprises an air traffic simulator.

12. The system of claim 10 wherein said at least one heuristic-based filter receives one or more flight path options for each flight and an order of preference associated with the flight path options for each flight, assigns flights their first flight path option until a demand capacity imbalance is calculated using the approximation model, and, after a demand capacity imbalance is calculated, evaluates one or more additional flight path options for the flights until demand capacity balance is recovered or there are no remaining flight path options.

13. The system of claim 10 wherein said at least one heuristic-based filter assumes a projected future airspace demand that includes a plurality of sector-time periods, identifies sector-time periods wherein demand capacity imbalances occur within the projected future airspace demand, selects flights that fly through problematic sector-time periods for re-planning, and evaluates alternative flight path options for the selected flights based upon a contribution of each flight path option to the identified demand capacity imbalance.

14. The system of claim 10 wherein the one or more configurable parameters included in the at least one heuristic-based process include a heuristic-type and one or more threshold parameters.

15. The system of claim 10 further comprising:

at least one computer processor; and

computer readable program code executable by said computer processor, said computer readable program code implementing said at least one heuristic-based filter, said genetic optimizer, said approximation model of the air traffic system, and said simulation of the air traffic system.

16. The system of claim 15 further comprising:

an output device in communication with said at least one computer processor by which information identifying the flight paths included in the optimal portfolio is output.

17. The system of claim 15 wherein said at least one computer processor is included within a multiprocessor computing environment or a distributed computing environment and wherein at least a portion of the computer program code is simultaneously executable on at least one other processor of the multiprocessor computing environment or the distributed computing environment to implement parallel instantiations of at least one of said at least one heuristic-based filter, said genetic optimizer, said approximation model of the air traffic system, and said simulation of the air traffic system.

18. The system of claim 10 wherein the genetic optimization process comprises a multi-objective genetic optimization process.

19. An approximation model of an air traffic simulation system representing an airspace, wherein said approximation model is usable in optimizing competing portfolios of flight paths for flights through one or more sectors of the airspace represented by the air traffic system, said approximation model comprising:

a fine-grained demand matrix generated directly from a four-dimensional traffic information set including information about which sectors of the airspace are crossed during which of a plurality of first time periods for selected flight paths of the flights included in a competing portfolio of flight paths, wherein the fine-grained demand matrix comprises a two-dimensional matrix having rows or columns corresponding to the sectors of the airspace and columns or rows corresponding to first time periods with numerical elements indicating the total number of the flights that cross each sector during each of the first time periods; and

a coarse-grained demand matrix comprising a two-dimensional matrix having rows or columns corresponding to the sectors of the airspace and columns or rows corresponding to second time periods with numerical elements representing an amount of the flights that cross each sector during each of the second time periods, wherein each second time period comprises an aggregate of more than one of the first time periods.

20. The approximation model of claim 19 wherein the coarse-grained demand matrix is generated directly from the four-dimensional traffic information set.

21. The approximation model of claim 19 wherein the coarse-grained demand matrix is calculated from the fine-grained demand matrix.

22. The approximation model of claim 21 wherein each second time period corresponds with a plurality of first time periods, and wherein each numerical element of the coarse-grained demand matrix for a second time period is calculated as a function of the numerical elements in the corresponding first time periods of the fine-grained demand matrix.

23. The approximation model of claim 22 wherein the function that calculates each numerical element of the coarse-grained demand matrix comprises the maximum value of the numerical elements in the corresponding first time periods of the fine-grained demand matrix.

24. The approximation model of claim 19 wherein the competing portfolios of flight paths are to be optimized for a period of twenty-four hours and wherein there are 480 first time periods of three minutes each and there are 96 second time periods of fifteen minutes each.

25. The approximation model of claim 19 further comprising:

computer readable program code executable by a computer processor, said computer readable program code when executed calculating said fine-grained and coarse-grained demand matrices.