Tactical Scheduling for Precision Air Traffic Operations: Past Research and Current Problems

Abstract

No AccessSurvey PaperTactical Scheduling for Precision Air Traffic Operations: Past Research and Current ProblemsD. R. Isaacson, A. V. Sadovsky and D. DavisD. R. IsaacsonAviation Systems Division, NASA Ames Research Center, Moffett Field, California 94035-0001*Aerospace Engineer, Aviation Systems Division, Mail Stop 210-6; .Search for more papers by this author, A. V. SadovskyAviation Systems Division, NASA Ames Research Center, Moffett Field, California 94035-0001†Aerospace Engineer, Aviation Systems Division, Mail Stop 210-6. Member AIAA.Search for more papers by this author and D. DavisDepartment of Mathematics, University of California, Los Angeles, Los Angeles, California 90095-1555‡Department of Mathematics.Search for more papers by this authorPublished Online:25 Apr 2014https://doi.org/10.2514/1.I010119SectionsRead Now ToolsAdd to favoritesDownload citationTrack citations About References [1] “Concept of Operations for the Next Generation Air Transportation System,” Ver. 2.0, Joint Planning and Development Office, 2007. Google Scholar[2] “European ATM Master Plan: The Roadmap for Sustainable Air Traffic Management,” SESAR Joint Undertaking, Belgium, 2012, http://www.sesarju.eu/news-press/documents/european-atm-master-plan-edition2 [retrieved 8 April 2014]. Google Scholar[3] “Asia/Pacific Seamless ATM Status and Strategies: Version 0.9b of the Draft Seamless ATM Plan,” Fourth Meeting of the ICAO Asia/Pacific Seamless ATM Planning Group (APSAPG/4), ICAO Asia and Pacific Office, Bangkok, June 2013. Google Scholar[4] Isaacson D. R., Robinson J. E.,, Swenson H. and Denery D., “A Concept for Robust, High Density Terminal Air Traffic Operations,” 10th AIAA Aviation Technology, Integration, and Operations (ATIO) Conference, AIAA Paper 2010-9292, 2010. LinkGoogle Scholar[5] Robinson J. E., and Kamgarpour M., “Benefits of Continuous Descent Operations in High-Density Terminal Airspace Under Scheduling Constraints,” 10th AIAA Aviation Technology, Integration, and Operations (ATIO) Conference, AIAA Paper 2010-9115, 2010. LinkGoogle Scholar[6] Bellman R., Esogbue A. O. and Nabeshima I., Mathematical Aspects of Scheduling and Applications, Pergamon, London, 1982, pp. 1–22, 48–58. CrossrefGoogle Scholar[7] Dear R., “The Dynamic Scheduling of Aircraft in the Near Terminal Area,” Massachusetts Inst. of Technology Flight Transportation Lab. Rept. R76-9, Cambridge, MA, 1976. Google Scholar[8] Kotnyek B., “An Annotated Overview of Dynamic Network Flows,” Inst. National de Recherche en Informatique et en Automatique, Rocquencourt, France, 2003, http://hal.inria.fr/docs/00/07/16/43/PDF/RR-4936.pdf [retrieved 8 April 2014]. Google Scholar[9] Cormen T., Leiserson C. and Rivest R., Introduction to Algorithms, MIT Press, Cambridge, MA, 1990, pp. 714–727. Google Scholar[10] Jung J. B. and Ghrist R., “Pareto Optimal Multi-Robot Coordination with Acceleration Constraints,” IEEE International Conference on Robotics and Automation, IEEE, Piscataway, NJ, May 2008, pp. 1942–1947. doi:https://doi.org/10.1109/ROBOT.2008.4543491 Google Scholar[11] Ghrist R., O'Kane J. M. and LaValle S. M., “Computing Pareto Optimal Coordinations on Roadmaps,” International Journal of Robotics Research, Vol. 24, No. 11, 2005, pp. 997–1010. doi:https://doi.org/10.1177/0278364905059057 IJRREL 0278-3649 CrossrefGoogle Scholar[12] Sadovsky A., Swenson H., Haskell W. and Rakas J., “Optimal Time Advance in Terminal Area Arrivals: Throughput vs. Fuel Savings,” IEEE 30th Digital Avionics Systems Conference (DASC), IEEE, Piscataway, NJ, 2011, pp. 2D2-2–2D2-5. Google Scholar[13] Sadovsky A., Davis D. and Isaacson D., “Optimal Routing and Control of Multiple Agents Moving in a Transportation Network and Subject to an Arrival Schedule and Separation Constraints,” NASA TM-2012-216032, 2012. Google Scholar[14] Sadovsky A., Davis D. and Isaacson D., “Efficient Computation of Separation-Compliant Speed Advisories for Air Traffic Arriving in Terminal Airspace,” NASA TM-2012-216033, 2012. Google Scholar[15] “General Operating and Flight Rules,” Federal Aviation Administration Code of Federal Regulations Title 14, Pt. 91, U.S. Dept. of Transportation, Washington, D.C., 2012. Google Scholar[16] “Air Traffic Control,” Federal Aviation Administration Order JO 7110.65U, Dept. of Transportation, Washington, D.C., 2012. Google Scholar[17] Kiselev A. P. and Givental A., Kiselev’s Geometry: Stereometry. Sumizdat, El Cerrito, CA, 2008, p. 76. Google Scholar[18] Arnol’d V., Ordinary Differential Equations, Springer, New York, 1992. Google Scholar[19] “Airline Deregulation Act,” U.S. Government, 92 Statute 1705, 1978. Google Scholar[20] “Digital Terminal Procedures,” Aeronautical Charting Office, Federal Aviation Administration, 2012. Google Scholar[21] Lan C.-T. E. and Roskam J., Airplane Aerodynamics and Performance, Roskam Aviation and Engineering Corp., Lawrence, KS, 1980, pp. 31–33, 499–506. Google Scholar[22] Debreu G., Theory of Value: An Axiomatic Analysis of Economic Equilibrium, Wiley, New York, 1959, pp. 51–52. Google Scholar[23] Papadimitriou C. H. and Steiglitz K., Combinatorial Optimization; Algorithms and Complexity, Dover, New York, 1998, pp. 20–25, 433–438. Google Scholar[24] Swenson H. N., Thipphavong J., Sadovsky A., Chen L., Sullivan C. and Martin L., “Design and Evaluation of the Terminal Area Precision Scheduling and Spacing System,” 9th USA/Europe ATM R&D Seminar (ATM2011), FAA, Eurocontrol, Berlin, 2011, http://www.atmseminar.org/seminarContent/seminar9/papers/40-Swenson-Final-Paper-4-14-11.pdf [retrieved 8 April 2014]. Google Scholar[25] “Traffic Flow Management in the National Airspace System,” Federal Aviation Administration Air Traffic Organization, U.S. Dept. of Transportation, Washington, D.C., 2009. Google Scholar[26] Leemis L.M., Reliability: Probabilistic Models and Statistical Methods, Prentice–Hall, Upper Saddle River, NJ, 2009, Chaps. 3–4, 6–11. CrossrefGoogle Scholar[27] Aeronautical Information Manual, Federal Aviation Administration. U.S. Dept. of Transportation, Washington, D.C., Feb. 2012. Google Scholar[28] Korn G. A. and Korn T. M., Mathematical Handbook for Scientists and Engineers: Definitions, Theorems, and Formulas for Reference and Review. McGraw–Hill, New York, 1961, pp. 146–150, 358. Google Scholar[29] Arnold V., Mathematical Methods of Classical Mechanics, 2nd ed., Springer, New York, 1997, pp. 77–78. Google Scholar[30] Jung Y., Hoang T., Montoya J., Gupta G., Malik W., Tobias L. and Wang H., “Performance Evaluation of a Surface Traffic Management Tool for Dallas/Fort Worth International Airport,” 9th USA/Europe ATM R&D Seminar (ATM2011), FAA, Eurocontrol, Berlin, 2011, http://www.atmseminar.org/seminarContent/seminar9/papers/92-Jung-Final-Paper-4-8-11.pdf [retrieved 8 April 2014]. Google Scholar[31] “Department of Defense World Geodetic System 1984: Its Definition and Relationships with Local Geodetic Systems,” National Imagery and Mapping Agency TR-TR8350.2, St. Louis, MO, Jan. 2000, http:/earth-info.nga.mil/GandG/publications/tr8350.2/tr8350_2.html [retrieved 8 April 2014]. Google Scholar[32] Dmitruk A. and Kaganovich A., “Maximum Principle for Optimal Control Problems with Intermediate Constraints,” Computational Mathematics and Modeling, Vol. 22, No. 2, 2011, pp. 180–215. doi:https://doi.org/10.1007/s10598-011-9096-8 CMMOEA 1046-283X CrossrefGoogle Scholar[33] Bryson A. E. and Ho Y. C., Applied Optimal Control, Blaisdell, New York, 1969, p. 288. Google Scholar[34] Neuman F. and Erzberger H., Analysis of Delay Reducing and Fuel Saving: Sequencing and Spacing Algorithms for Arrival Traffic, NASA TM-103880, 1991. Google Scholar[35] “Facility Operation and Administration: Section 8. Monitor Alert Parameter,” Federal Aviation Administration Order JO 7210.3X, U.S. Dept. of Transportation, Washington, D.C., 2013. Google Scholar[36] “Operating Requirements: Domestic, Flag and Supplemental Operations,” Federal Aviation Administration Code of Federal Regulations Title 14, Pt. 121, Sec. 141, U.S. Dept. of Transportation, Washington, D.C., 2012. Google Scholar[37] Nolan M. S., Fundamentals of Air Traffic Control, 3rd ed., Aviation Series, Brooks/Cole, New York, 1999, pp. 22–40. Google Scholar[38] Higgins L. O. and Mpontsikaris P., “Evaluation of Air Traffic Control Models and Simulations,” Federal Aviation Administration, U.S. Dept. of Transportation, Washington, D.C., June 1971. Google Scholar[39] “Capacity Needs in the National Airspace System, 2007–2025,” Federal Aviation Administration, Dept. of Transportation, Washington, D.C., May 2007. Google Scholar[40] Sölveling G., “Stochastic Programming Methods for Scheduling of Airport Runway Operations Under Uncertainty,” Ph.D. Thesis, Georgia Inst. of Technology, Atlanta, 2012. Google Scholar[41] Bianco L., Ricciardelli S., Rinaldi G. and Sassano A., “Scheduling Tasks with Sequence-Dependent Processing Times,” Naval Research Logistics, Vol. 35, No. 2, 1988, pp. 177–184. doi:https://doi.org/10.1002/1520-6750(198804)35:2<177::AID-NAV3220350203>3.0.CO;2-V NRLOEP 1520-6750 CrossrefGoogle Scholar[42] Beasley J. E., Krishnamoorthy M., Sharaiha Y. M. and Abramson D., “Scheduling Aircraft Landings: The Static Case,” Transportation Science, Vol. 34, No. 2, 2000, pp. 180–197. doi:https://doi.org/10.1287/trsc.34.2.180.12302 TRSCBJ 0041-1655 CrossrefGoogle Scholar[43] Abela J., Abramson D., Krishnamoorthy M., De Silva Y. A. and Mills G., “Computing Optimal Schedules for Landing Aircraft,” Proceedings 12th National ASOR Conference, Adelaide, Australia, 1993, pp. 71–90. Google Scholar[44] Psaraftis H. N., “A Dynamic Programming Approach for Sequencing Groups of Identical Jobs,” Operations Research, Vol. 28, No. 6, 1980, pp. 1347–1359. doi:https://doi.org/10.1287/opre.28.6.1347 OPREAI 0030-364X CrossrefGoogle Scholar[45] Venkatakrishnan C. S., Barnett A. and Odoni A. R., “Landings at Logan Airport: Describing and Increasing Airport Capacity,” Transportation Science, Vol. 27, No. 3, 1993, pp. 211–227. doi:https://doi.org/10.1287/trsc.27.3.211 TRSCBJ 0041-1655 CrossrefGoogle Scholar[46] Balakrishnan H. and Chandran B., “Scheduling aircraft Landings Under Constrained Position Shifting,” AIAA Guidance, Navigation, and Control Conference and Exhibit, AIAA Paper 2006-6320, 2006. LinkGoogle Scholar[47] Dear R. and Sherif Y., “An Algorithm for Computer Assisted Sequencing and Scheduling of Terminal Area Operations,” Transportation Research Part A: General, Vol. 25, Nos. 2–3, 1991, pp. 129–139. doi:https://doi.org/10.1016/0191-2607(91)90132-A CrossrefGoogle Scholar[48] Brinton C. R., “An Implicit Enumeration Algorithm for Arrival Aircraft Scheduling,” Eleventh Digital Avionics Systems Conference, IEEE Paper 0-7803-0820-4/92, 1992, pp. 268–274. Google Scholar[49] Erzberger H., “Ctas: Computer Intelligence for Air Traffic Control in the terminal Area,” NASA TM-103959, 1992. Google Scholar[50] Sokkappa B. G., “The Impact of Metering Methods on Airport Throughput,” Journal of Air Traffic Control, Vol. 31, No. 3, 1989, pp. 45–48. Google Scholar[51] Wong G., “The Dynamic Planner: The Sequencer, Scheduler, and Runway Allocator for Air Traffic Control Automation,” NASA TM-209586, 2000. Google Scholar[52] Adacher L., Pacciarelli D. and Pranzo M., “A Graph-Theoretical Model for the Aircraft Sequencing Problem,” Università Degli Studi Roma Tre, Dipartimento di Informatica e Automazione, Rept. RT-DIA-79-2003, 2003. Google Scholar[53] Robinson J., and Isaacson D., “A Concurrent Sequencing, and Deconfliction Algorithm for Terminal Area Air Traffic Control,” AIAA Guidance, Navigation, and Control Conference, AIAA Paper 2000-4473, 2000. LinkGoogle Scholar[54] Isaacson D. and Robinson J.,, “A Knowledge-Based Conflict Resolution Algorithm for Terminal Area Air Traffic Control Advisory Generation,” AIAA Guidance, Navigation, and Control Conference, AIAA Paper 2001-4116, 2001. LinkGoogle Scholar[55] Huang H. and Tomlin C. J., “A Network-Based Approach to En-Route Sector Aircraft Trajectory Planning,” 2009 AIAA Conference on Guidance, Control, and Navigation, AIAA Paper 2009-6169, 2009. LinkGoogle Scholar[56] Cole R. E., Richard C., Kim S. and Bailey D., “An Assessment of the 60 km Rapid Update Cycle (Ruc) with Near Real-Time Aircraft Reports, MIT Lincoln Laboratory, NASA/A-1, Lexington, MA, 1998. Google Scholar[57] Ren L., Reynolds T. G., Clarke J. B., Hooper D. A., Parton G. A. and Dore A. J., “Meteorological Influences on the Design of Advanced Aircraft Approach Procedures for Reduced Environmental Impacts,” Meteorological Applications, Vol. 18, No. 1, 2011, pp. 40–59. doi:https://doi.org/10.1002/met.206 CrossrefGoogle Scholar[58] Mondoloni S. and Liang D., “Improving Trajectory Forecasting Through Adaptive Filtering Techniques,” 5th USA/Europe ATM R&D Seminar, FAA, Eurocontrol, 2003, http://www.atmseminar.org/seminarContent/seminar5/papers/p_015_DS.pdf [retrieved 8 April 2014]. Google Scholar[59] Glover W. and Lygeros J., “Simplified Multi-Aircraft Models for Conflict Detection and Resolution Algorithms,” HYBRIDGE Project Deliverable D1.4, Contract IST-2001-32460 of the European Commission, 2004, http://hybridge.nlr.nl [retrieved 8 April 2014]. Google Scholar[60] Paielli R. A. and Erzberger H., “Conflict Probability Estimation Generalized to Non-Level Flight,” Air Traffic Control Quarterly, Vol. 7, No. 3, Oct. 1999, pp. 195–222. ATCQER 1064-3818 LinkGoogle Scholar Previous article