Skip to main content
Skip to article control options
No AccessFull-Length Paper

Aircraft Vertical Route Optimization by Beam Search and Initial Search Space Reduction

Published Online:https://doi.org/10.2514/1.I010561

This paper describes an optimization algorithm that provides an economical vertical navigation profile by finding the combinations of climb, cruise, and descent speeds, as well as altitudes, for an aircraft to minimize flight costs. The computational algorithm takes advantage of a space search reduction methodology to reduce the initial number of available speed and altitude combinations. The optimal solution was found by implementing the beam search algorithm. A bounding function that correctly estimates the flight cost by considering step climbs was developed to reduce the number of calculations required by the beam search algorithm. The full-flight fuel burn cost was obtained using a performance database-based method. The algorithm uses a numerical performance model instead of equations of motion to compute fuel burn. The database was developed by using flight experimental data. To validate the algorithm, its results were compared to those of three other algorithms: an exhaustive search, beam search, and search space reduction. The solution provided by the algorithm was also compared to the solution provided by a flight management system. Following this comparison, the algorithm systematically found the optimal solutions, which were better in terms of flight cost than those provided by the flight management system.

References

  • [1] Vision 2050, International Air Transport Association, Singapore, 2011, p. 87. Google Scholar

  • [2] Aviation’s Contribution to Climate Change, International Civil Aviation Organization, Montreal, 2010, p. 260. Google Scholar

  • [3] Williams P. D., “Transatlantic Flight Times and Climate Change,” Environmental Research Letters, Vol. 11, No. 2, 2016, Paper 024008. doi:https://doi.org/10.1088/1748-9326/11/2/024008 CrossrefGoogle Scholar

  • [4] Green J. E., “The Potential for Reducing the Impact of Aviation on Climate,” Technology Analysis and Strategic Management, Vol. 21, No. 1, 2009, pp. 39–59. doi:https://doi.org/10.1080/09537320802557269 CrossrefGoogle Scholar

  • [5] Crutzen P. J., “The Influence of Nitrogen Oxides on the Atmospheric Ozone Content,” Quarterly Journal of the Royal Meteorological Society, Vol. 96, No. 408, 1970, pp. 320–325. doi:https://doi.org/10.1002/(ISSN)1477-870X QJRMAM 0035-9009 CrossrefGoogle Scholar

  • [6] Toxicological Profile for Total Petroleum Hydrocarbons, U.S. Dept. of Health and Human Services, Public Health Service, Atlanta, GA, 1999, p. 4. Google Scholar

  • [7] Black D. A., Black J. A., Issarayangyun T. and Samuels S. E., “Aircraft Noise Exposure and Resident’s Stress and Hypertension: A Public Health Perspective for Airport Environmental Management,” Journal of Air Transport Management, Vol. 13, No. 5, 2007, pp. 264–276. doi:https://doi.org/10.1016/j.jairtraman.2007.04.003 CrossrefGoogle Scholar

  • [8] Sabatini R., Gardi A., Ramasamy S., Kistan T. and Marino M., “Modern Avionics and ATM Systems for Green Operations,” Encyclopedia of Aerospace Engineering, Wiley, 2010, pp. 4–6. doi:https://doi.org/10.1002/9780470686652.eae1064 Google Scholar

  • [9] Ashok A., Dedoussi I. C., Yim S. H. L., Balakrishnan H. and Barrett S. R. H., “Quantifying the Air Quality-CO2 Tradeoff Potential for Airports,” Atmospheric Environment, Vol. 99, 2014, pp. 546–555. doi:https://doi.org/10.1016/j.atmosenv.2014.10.024 CrossrefGoogle Scholar

  • [10] Beginner’s Guide to Aviation Biofuels, Air Transportation Action Group, Geneva, Switzerland, 2009, p. 24. Google Scholar

  • [11] Nojoumi H., Dincer I. and Naterer G. F., “Greenhouse Gas Emissions Assessment of Hydrogen and Kerosene-Fueled Aircraft Propulsion,” International Journal of Hydrogen Energy, Vol. 34, No. 3, 2009, pp. 1363–1369. doi:https://doi.org/10.1016/j.ijhydene.2008.11.017 IJHEDX 0360-3199 CrossrefGoogle Scholar

  • [12] Vincent J.-B. and Botez R., “Systemic Modeling and Design Approach for Morphing Wing Aileron Controller Using Matlab/Simulink,” AIAA Modeling and Simulation Technologies Conference, AIAA Paper 2015-0904, 2015. doi:https://doi.org/10.2514/6.2015-0904 LinkGoogle Scholar

  • [13] Nangia R., “Operations and Aircraft Design Towards Greener Civil Aviation Using Air-to-Air Refuelling,” Aeronautical Journal, Vol. 110, No. 1113, 2006, pp. 705–721. doi:https://doi.org/10.1017/S0001924000001585 CrossrefGoogle Scholar

  • [14] McConnachie D., Wollersheim C. and Hansman R. J., “The Impact of Fuel Price on Airline Fuel Efficiency and Operations,” 2013 Aviation Technology, Integration, and Operations Conference, AIAA Paper 2013-4291, 2013. LinkGoogle Scholar

  • [15] Aviation Benefits Beyond Borders, Air Transport Action Group, Geneva, Switzerland, 2014, p. 22. Google Scholar

  • [16] Balakrishnan H., “Control and Optimization Algorithms for Air Transportation Systems,” Annual Reviews in Control, Vol. 41, 2016, pp. 39–46. doi:https://doi.org/10.1016/j.arcontrol.2016.04.019 CrossrefGoogle Scholar

  • [17] Jensen L., Hansman J. R., Venuti J. and Reynolds T., “Commercial Airline Altitude Optimization Strategies for Reduced Cruise Fuel Consumption,” 14th AIAA Aviation Technology, Integration, and Operations Conference, AIAA Paper 2014-3006, 2014. LinkGoogle Scholar

  • [18] Jensen L., Hansman J. R., Venuti J. C. and Reynolds T., “Commercial Airline Speed Optimization Strategies for Reduced Cruise Fuel Consumption,” 2013 Aviation Technology, Integration, and Operations Conference, AIAA Paper 2013-4289, 2013. doi:https://doi.org/10.2514/6.2013-4289 LinkGoogle Scholar

  • [19] Jensen L., Tran H. and Hansman J. R., “Cruise Fuel Reduction Potential from Altitude and Speed Optimization in Global Airline Operations,” Proceedings of the 11th USA/Europe Air Traffic Management Research and Development Seminar, The European Organisation for Safety of Air Navigation (EuroControl), Brussels, Belgium, 2015, pp. 497–506. Google Scholar

  • [20] Turgut E. T., Cavcar M., Usanmaz O., Canarslanlar A. O., Dogeroglu T., Armutlu K. and Yay O. D., “Fuel Flow Analysis for the Cruise Phase of Commercial Aircraft on Domestic Routes,” Aerospace Science and Technology, Vol. 37, Aug. 2014, pp. 1–9. doi:https://doi.org/10.1016/j.ast.2014.04.012 CrossrefGoogle Scholar

  • [21] Jackson M. R. C., “Role of Avionics in Trajectory Based Operations,” Proceedings of the 27th IEEE/AIAA Digital Avionics Systems Conference, SAE International, 2008, pp. 3.A.1-1–3.A.1-9. doi:https://doi.org/10.1109/dasc.2008.4702792 Google Scholar

  • [22] Gardi A., Sabatini R., Ramsamy S., Marino M. and Kistan T., “Automated ATM System Enabling 4DT-Based Operations,” Proceedings of the SAE 2015 AeroTech Congress & Exhibition, Vol. 2015-01-2539, 2015, p. 7. doi:https://doi.org/10.4271/2015-01-2539 Google Scholar

  • [23] Kwok-On T., Daniel B. and Anthony W., “Development of Continuous Descent Arrival (CDA) Procedures for Dual-Runway Operations at Houston Intercontinental,” 6th AIAA Aviation Technology, Integration and Operations Conference, AIAA Paper 2006-7750, Sept. 2006. doi:https://doi.org/10.2514/6.2006-7750 Google Scholar

  • [24] Kwok-On T., Anthony W. and John B., “Continuous Descent Approach Procedure Development for Noise Abatement Tests at Louisville International Airport, KY,” AIAA’s 3rd Annual Aviation Technology, Integration, and Operations (ATIO) Forum, AIAA Paper 2003-6772, Nov. 2003. Google Scholar

  • [25] Clarke J. P., Brooks J., Nagle G., Scacchioli A., White W. and Liu S. R., “Optimized Profile Descent Arrivals at Los Angeles International Airport,” Journal of Aircraft, Vol. 50, No. 2, 2013, pp. 360–369. doi:https://doi.org/10.2514/1.C031529 LinkGoogle Scholar

  • [26] Stell L., “Flight Management System Prediction and Execution of Idle-Thrust Descents,” Proceedings of the IEEE/AIAA 28th Digital Avionics Systems Conference, IEEE Publ., Piscataway, NJ, 2009, pp. 1.C.4-1–1.C.4-12. doi:https://doi.org/10.1109/dasc.2009.5347570 Google Scholar

  • [27] Novak D., Buckai T. and Dadisic T., “Development, Design and Flight Test Evaluation of Continuous Descent Approach Procedure in FIR Zagreb,” Scientific Journal on Traffic and Transportation Research, Vol. 21, No. 5, 2009, pp. 319–329. doi:https://doi.org/10.7307/ptt.v21i5.247 CrossrefGoogle Scholar

  • [28] Sprong K. R., Klein K. A., Shiotsuki C., Arrighi J. and Liu S., “Analysis of AIRE Continuous Descent Arrival Operations at Atlanta and Miami,” Proceedings of the IEEE/AIAA 27th Digital Avionics Systems Conference, IEEE Publ., Piscataway, NJ, 2008, pp. 3.A.5-1–3.A.5-13. doi:https://doi.org/10.1109/dasc.2008.4702796 Google Scholar

  • [29] Johnson C. M., “Analysis of Top of Descent (TOD) Uncertainty,” Proceedings of the 2011 IEEE/AIAA 30th Digital Avionics Systems Conference, IEEE Publ., Piscataway, NJ, 2011, pp. 2E3-1–2E3-10. doi:https://doi.org/10.1109/dasc.2011.6096041 Google Scholar

  • [30] Stell L., “Predictability of Top of Descent Location for Operational Idle-Thrust Descents,” 10th AIAA Aviation Technology, Integration, and Operations (ATIO) Conference, AIAA Paper 2010-9116, Sept. 2010. doi:https://doi.org/10.2514/6.2010-9116 LinkGoogle Scholar

  • [31] Murrieta-Mendoza A., Botez R. and Ford S., “Estimation of Fuel Consumption and Polluting Emissions Generated During the Missed Approach Procedure,” Proceedings of the 33nd IASTED International Conference on Modelling, Identification, and Control, ACTA Press Paper  809-040, Calgary, Canada, 2014. doi:https://doi.org/10.2316/P.2014.809-040 Google Scholar

  • [32] Dancila R., Botez R. M. and Ford S., “Fuel Burn and Emissions Evaluation for a Missed Approach Procedure Performed by a B737-400,” 2013 Aviation Technology, Integration, and Operations Conference, AIAA Paper 2013-4387, 2013. doi:https://doi.org/10.2514/6.2013-4387 LinkGoogle Scholar

  • [33] Chamseddine A., Zhang Y., Rabbath C. A., Join C. and Theilliol D., “Flatness-Based Trajectory Planning/Replanning for a Quadrotor Unmanned Aerial Vehicle,” IEEE Transactions on Aerospace and Electronic Systems, Vol. 48, No. 4, 2012, pp. 2832–2848. doi:https://doi.org/10.1109/TAES.2012.6324664 IEARAX 0018-9251 CrossrefGoogle Scholar

  • [34] Chamseddine A., Zhang Y., Rabbath C. A. and Theilliol D., “Trajectory Planning and Replanning Strategies Applied to a Quadrotor Unmanned Aerial Vehicle,” Journal of Guidance, Control, and Dynamics, Vol. 35, No. 5, 2012, pp. 1667–1671. doi:https://doi.org/10.2514/1.56606 JGCODS 0731-5090 LinkGoogle Scholar

  • [35] Chen Y., Yu J., Mei Y., Zhang S., Ai X. and Jia Z., “Trajectory Optimization of Multiple Quad-Rotor UAVs in Collaborative Assembling Task,” Chinese Journal of Aeronautics, Vol. 29, No. 1, 2016, pp. 184–201. doi:https://doi.org/10.1016/j.cja.2015.12.008 CJAEEZ 1000-9361 CrossrefGoogle Scholar

  • [36] Filippone A., “On the Benefits of Lower Mach Number Aircraft Cruise,” Aeronautical Journal, Vol. 111, No. 1122, 2007, pp. 531–542. doi:https://doi.org/10.1017/S0001924000004772 AENJAK 0001-9240 CrossrefGoogle Scholar

  • [37] Wieland F., Hunter G. and Schleicher D., “The Implication of New Aircraft Types on the Next Generation Air Transportation System,” Proceedings of the IEEE/AIAA 27th Digital Avionics Systems Conference, IEEE Publ., Piscataway, NJ, 2008, pp. 2.C.2-1–2.C.2-8. doi:https://doi.org/10.1109/dasc.2008.4702781 Google Scholar

  • [38] Bonnefoy P. and Hansman R. J., “Operational Implications of Cruise Speed Reductions for Next Generation Fuel Efficient Subsonic Aircraft,” Proceedings of the 27th Congress of the International Council of the Aeronautical Sciences, International Council of the Aeronautical Sciences (ICAS), Stockholm, Sweden, 2010, pp. 4921–4931. Google Scholar

  • [39] Lovegren J. A., “Estimation of Potential Aircraft Fuel Burn Reduction in Cruise via Speed and Altitude Optimization Strategies,” Massachusetts Inst. of Technology Rept.  ICAT-2011-03, Cambridge, MA, 2011, p. 97. Google Scholar

  • [40] Valenzuela A. and Rivas D., “Optimization of Aircraft Cruise Procedures Using Discrete Trajectory Patterns,” Journal of Aircraft, Vol. 51, No. 5, 2014, pp. 1632–1640. doi:https://doi.org/10.2514/1.C032041 LinkGoogle Scholar

  • [41] Pargett D. M. and Ardema M. D., “Flight Path Optimization at Constant Altitude,” Journal of Guidance, Control, and Dynamics, Vol. 30, No. 4, 2007, pp. 1197–1201. doi:https://doi.org/10.2514/1.28954 JGCODS 0731-5090 LinkGoogle Scholar

  • [42] Franco A. and Rivas D., “Minimum-Cost Cruise at Constant Altitude of Commercial Aircraft Including Wind Effects,” Journal of Guidance, Control, and Dynamics Vol. 34, No. 4, 2011, pp. 1253–1260.doi:https://doi.org/10.2514/1.53255 JGCODS 0731-5090 LinkGoogle Scholar

  • [43] Franco A. and Rivas D., “Optimization of Multiphase Aircraft Trajectories Using Hybrid Optimal Control,” Journal of Guidance, Control, and Dynamics, Vol. 38, No. 3, 2015, pp. 452–467.doi:https://doi.org/10.2514/1.G000688 JGCODS 0731-5090 LinkGoogle Scholar

  • [44] Ng H. K., Sridhar B. and Grabbe S., “Optimizing Aircraft Trajectories with Multiple Cruise Altitudes in the Presence of Winds,” Journal of Aerospace Information Systems, Vol. 11, No. 1, 2014, pp. 35–47. doi:https://doi.org/10.2514/1.I010084 LinkGoogle Scholar

  • [45] Miyazawa Y., Wickramasinghe N. K., Harada A. and Miyamoto Y., “Dynamic Programming Application to Airliner Four Dimensional Optimal Flight Trajectory,” AIAA Guidance, Navigation, and Control (GNC) Conference, AIAA Paper 2013-4969, 2013. doi:https://doi.org/10.2514/6.2013-4969 LinkGoogle Scholar

  • [46] Hagelauer P. and Mora-Camino F., “A Soft Dynamic Programming Approach for On-Line Aircraft 4D-Trajectory Optimization,” European Journal of Operational Research, Vol. 107, No. 1, 1998, pp. 87–95. doi:https://doi.org/10.1016/S0377-2217(97)00221-X EJORDT 0377-2217 CrossrefGoogle Scholar

  • [47] Villarroel J. and Rodrigues L., “Optimal Control Framework for Cruise Economy Mode of Flight Management Systems,” Journal of Guidance, Control, and Dynamics, Vol. 39, No. 5, 2016, pp. 1022–1033. doi:https://doi.org/10.2514/1.G001373 LinkGoogle Scholar

  • [48] Sadovsky A. V., “Application of the Shortest-Path Problem to Routing Terminal Airspace Air Traffic,” Journal of Aerospace Information Systems, Vol. 11, No. 3, 2014, pp. 118–130. doi:https://doi.org/10.2514/1.I010074 LinkGoogle Scholar

  • [49] Rippel E., Bar-Gill A. and Shimkin N., “Fast Graph-Search Algorithms for General-Aviation Flight Trajectory Generation,” Journal of Guidance, Control, and Dynamics, Vol. 28, No. 4, 2005, pp. 801–811. doi:https://doi.org/10.2514/1.7370 JGCODS 0731-5090 LinkGoogle Scholar

  • [50] Cobano J. A., Alejo D., Heredia G. and Ollero A., “4D Trajectory Planning in ATM with an Anytime Stochastic Approach,” Proceedings of the 3rd International Conference on Application and Theory of Automation in Command and Control Systems, IRIT Press, Toulouse, France, 2013, pp. 1–8. doi:https://doi.org/10.1145/2494493.2494494 Google Scholar

  • [51] Murrieta-Mendoza A., Demange S., George F. and Botez R. M., “Performance Database Creation Using a Flight D Simulator for Cessna Citation X Aircraft in Cruise Regime,” Proceedings of the 34th IASTED International Conference on Modelling, Identification, and Control, ACTA Press Paper  826-028, Calgary, Canada, 2015. doi:https://doi.org/10.2316/P.2015.826-028 Google Scholar

  • [52] Dancila B., Botez R. M. and Labour D., “Fuel Burn Prediction Algorithm for Cruise, Constant Speed and Level Flight Segments,” Aeronautical Journal, Vol. 117, No. 1191, 2013, pp. 491–504. CrossrefGoogle Scholar

  • [53] Gagné J., Murrieta-Mendoza A., Botez R. and Labour D., “New Method for Aircraft Fuel Saving Using Flight Management System and Its Validation on the L-1011 Aircraft,” 2013 Aviation Technology, Integration, and Operations Conference, AIAA Paper 2013-4290, 2013. doi:https://doi.org/10.2514/6.2013-4290 LinkGoogle Scholar

  • [54] Félix-Patrón R. S., Botez R. M. and Labour D., “New Altitude Optimisation Algorithm for the Flight Management System CMA-9000 Improvement on the A310 and L-1011 Aircraft,” Aeronautical Journal, Vol. 117, No. 1194, 2013, pp. 787–805. doi:https://doi.org/10.1017/S0001924000008459 AENJAK 0001-9240 CrossrefGoogle Scholar

  • [55] Sidibé S. and Botez R. M., “Trajectory Optimization of FMS-CMA 9000 by Dynamic Programming,” Proceedings of the ASI AÉRO 2013 Conference, 60th Aeronautics Conference and AGM, Canadian Aeronautics and Space Institute (CASI), Ontario, Canada, 2013, pp. 631–641. Google Scholar

  • [56] Félix-Patrón R. S., Oyono Owono A. C., Botez R. M. and Labour D., “Speed and Altitude Optimization on the FMS CMA-9000 for the Sukhoi Superjet 100 Using Genetic Algorithms,” 2013 Aviation Technology, Integration, and Operations Conference, AIAA Paper 2013-4257, 2013. LinkGoogle Scholar

  • [57] Murrieta-Mendoza A., Félix-Patrón R. S. and Botez R. M., “Flight Altitude Optimization Using Genetic Algorithms Considering Climb and Descent Costs in Cruise with Flight Plan Information,” Proceedings of the SAE 2015 AeroTech Congress and Exhibition, SAE International, Seattle, WA, 2015, p. 9. doi:https://doi.org/10.4271/2015-01-2542 Google Scholar

  • [58] Murrieta-Mendoza A. and Botez R. M., “Lateral Navigation Optimization Considering Winds and Temperatures for Fixed Altitude Cruise Using the Dijkstra’s Algorithm,” Advances in Aerospace Technology, Vol. 1, No. 46421, 2014, Paper V001T01A054. doi:https://doi.org/10.1115/IMECE2014-37570 CrossrefGoogle Scholar

  • [59] Félix-Patrón R. S., Kessaci A. and Botez R., “Horizontal Flight Trajectories Optimisation for Commercial Aircraft Through a Flight Management System,” Aeronautical Journal, Vol. 118, No. 1210, 2014, p. 20. AENJAK 0001-9240 Google Scholar

  • [60] Murrieta Mendoza A., Bunel A. and Botez R., “Aircraft Lateral Flight Optimization Using Artificial Bees Colony,” Proceedings of the International Conference on Air Transport INAIR 2015, Center for Applied Research Technology, Amsterdam Univ. of Applied Science, Amsterdam, 2015. Google Scholar

  • [61] Murrieta-Mendoza A., “Vertical and Lateral Flight Optimization Algorithm and Missed Approach Cost Calculation,” M.S. Thesis, École de Technologie Supérieure, Montreal, 2013, p. 114. Google Scholar

  • [62] Félix-Patrón R. S. and Botez R. M., “Flight Trajectory Optimization Through Genetic Algorithms Coupling Vertical and Lateral Profiles,” Advances in Aerospace Technology, Vol. 1, No. 46421, 2014, Paper V001T01A048. CrossrefGoogle Scholar

  • [63] Félix-Patrón R. S., Berrou Y. and Botez R. M., “New Methods of Optimization of the Flight Profiles for Performance Database-Modeled Aircraft,” Proceedings of the Institution of Mechanical Engineers, Part G: Journal of Aerospace Engineering, Vol. 229, No. 10, 2014, pp. 1853–1867. doi:https://doi.org/10.1177/0954410014561772 CrossrefGoogle Scholar

  • [64] Murrieta-Mendoza A., Hamy A. and Botez R. M., “Mach Number Selection for Cruise Phase Using the Ant Colony Optimization Algorithm with RTA Constrains,” Proceedings of the International Conference on Air Transport, Center for Applied Research Technology, Amsterdam Univ. of Applied Science, Amsterdam, 2015. Google Scholar

  • [65] Murrieta-Mendoza A. and Botez R. M., “Methodology for Vertical-Navigation Flight-Trajectory Cost Calculation Using a Performance Database,” Journal of Aerospace Information Systems, Vol. 12, No. 8, 2015, pp. 519–532. doi:https://doi.org/10.2514/1.I010347 LinkGoogle Scholar

  • [66] Murrieta-Mendoza A. and Botez R. M., “Vertical Navigation Trajectory Optimization Algorithm for a Commercial Aircraft,” AIAA/3AF Aircraft Noise and Emissions Reduction Symposium, AIAA Paper 2014-3019, 2014. doi:https://doi.org/10.2514/6.2014-3019 LinkGoogle Scholar

  • [67] Sabuncuoglu I. and Bayiz M., “Job Shop Scheduling with Beam Search,” European Journal of Operational Research, Vol. 118, No. 2, 1999, pp. 390–412. doi:https://doi.org/10.1016/S0377-2217(98)00319-1 EJORDT 0377-2217 CrossrefGoogle Scholar

  • [68] Murrieta-Mendoza A., Beuze B., Ternisien L. and Botez R., “Branch & Bound-Based Algorithm for Aircraft VNAV Profile Reference Trajectory Optimization,” 15th AIAA Aviation Technology, Integration, and Operations Conference, AIAA Paper 2015-2280, 2015. doi:https://doi.org/10.2514/6.2015-2280 LinkGoogle Scholar