Hostname: page-component-cd9895bd7-p9bg8 Total loading time: 0 Render date: 2024-12-25T06:12:21.550Z Has data issue: false hasContentIssue false
  • English
  • Français

New flight trajectory optimisation method using genetic algorithms

Published online by Cambridge University Press:  09 March 2021

R.I. Dancila  and
R.M. Botez Open the ORCID record for R.M. Botez [Opens in a new window]
R.I. Dancila
Affiliation:
Université du Québec École de Technologie Supérieure Laboratory of Research in Active Control, Avionics, and Aeroservoelasticity LARCASE MontréalQuebec, H3C 1K3Canada
R.M. Botez*
Affiliation:
Université du Québec École de Technologie Supérieure Laboratory of Research in Active Control, Avionics, and Aeroservoelasticity LARCASE MontréalQuebec, H3C 1K3Canada
*
[email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper presents a new flight trajectory optimisation method, based on genetic algorithms, where the selected optimisation criterion is the minimisation of the total cost. The candidate flight trajectories evaluated in the optimisation process are defined as flight plans with two components: a lateral flight plan (the set of geographic points that define the flight trajectory track segments) and a vertical flight plan (the set of data that define the altitude and speed profiles, as well as the points where the altitude and/or speed changes occur). The lateral components of the candidate flight plans are constructed by selecting a set of adjacent nodes from a routing grid. The routing grid nodes are generated based on the orthodromic route between the flight trajectory’s initial and final points, a selected maximum lateral deviation from the orthodromic route and a selected grid node step size along and across the orthodromic route. Two strategies are investigated to handle invalid flight plans (relative to the aircraft’s flight envelope) and to compute their flight performance parameters. A first strategy is to assign a large penalty total cost to invalid flight profiles. The second strategy is to adjust the invalid flight plan parameters (altitude and/or speed) to the nearest limit of the flight envelope, with priority being given to maintaining the planned altitude. The tests performed in this study show that the second strategy is computationally expensive (requiring more than twice the execution time relative to the first strategy) and yields less optimal solutions. The performance of the optimal profiles identified by the proposed optimisation method, using the two strategies regarding invalid flight profile performance evaluation, were compared with the performance data of a reference flight profile, using identical input data: initial aircraft weight, initial and final aircraft geographic positions, altitudes and speed, cost index, and atmospheric data. The initial and final aircraft geographic positions, and the reference flight profile data, were retrieved from the FlightAware web site. This data corresponds to a real flight performed with the aircraft model used in this study. Tests were performed for six Cost Index values. Given the randomness of the genetic algorithms, the convergence to a global optimal solution is not guaranteed (the solution may be non-optimal or a local optima). For a better evaluation of the performance of the proposed method, ten test runs were performed for each Cost Index value. The total cost reduction for the optimal flight plans obtained using the proposed method, relative to the reference flight plan, was between 0.822% and 3.042% for the cases when the invalid flight profiles were corrected, and between 1.598% and 3.97% for the cases where the invalid profiles were assigned a penalty total cost.

Keywords

flight trajectory optimisationflight planlateral flight planvertical flight planrouting gridBADAatmospheric data modelGRIB2accelerated flight simulationaccelerated flight performance calculationgenetic algorithmflight plan crossoverflight plan mutationtotal costcost index
Type
Research Article
Information
The Aeronautical Journal , Volume 125 , Issue 1286 , April 2021 , pp. 618 - 671
Copyright
© The Author(s), 2021. Published by Cambridge University Press on behalf of Royal Aeronautical Society

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

ICAO. ICAO Long-Term Traffic Forcasts, 2018. URL https://www.icao.int/sustainability/Documents/LTF_Charts-Results_2018edition.pdf/ Google Scholar
ICAO. Forecasts of Scheduled Passenger and Freight Traffic. URL https://www.icao.int/ sustainability/Pages/eap-fp-forecast-scheduled/pasenger-traffic.aspx Google Scholar
IATA. IATA Forecasts Predicts 8.2 billion Air Travelers in 2037. 2018, URL https://www.iata.org/en/pressroom/pr/2018-10-24-02 Google Scholar
Dancila, B.D., Botez, R. and Labour, D. Fuel burn prediction algorithm for cruise, constant speed and level flight segments, Aeronaut. J, 2013, 117, (1191), pp 491–504. doi: 10.1017/S0001924000008149.CrossRefGoogle Scholar
Bronsvoort, J., Mcdonald, G., Potts, R. and Gutt, E. Enhanced descent wind forecast for aircraft, In 9th USA/Europe Air Traffic Management Research and Development Seminar (ATM2011), 2011, Berlin, Germany. URL http://atmseminar.org/seminarContent/ seminar9/papers/25-Bronsvoort-Final-Paper-4-6-11.pdf.Google Scholar
Torres, S. and Delpome, K.L. An integrated approach to air traffic management to achieve trajectory based operations. In 2012 IEEE/AIAA 31st Digital Avionics Systems Conference (DASC), Williamsburg, VA, October 2012, pp 3E6-1-3E6-16. doi: 10.1109/DASC.2012.6382325.CrossRefGoogle Scholar
Cate, K. Challenges in achieving trajectory-based operations. In 51st AIAA Aerospace Sciences Meeting including the New Horizons Forum and Aerospace Exposition, Grapevine (Dallas/Ft. Worth), TX, January 2013, pp 443. doi:10.2514/6.2013-443.CrossRefGoogle Scholar
Rodionova, O., Sibihi, M., Delahaye, D. and Mongeau, M. Optimization of aircraft trajectories in North Atlantic oceanic airspace, ICRAT 2012, 5th International Confernce on Research in Air Transportation, May 2012, Berkley, CA. URL https://hal-enac.archives-ouvertes.fr/hal-00938895/.Google Scholar
Chaimatanan, S., Delahaye, D. and Mongeau, M. A methodology for strategic planning of aircraft trajectories using simulated annealing, ISIATM 2012, 1st International Conference on Interdisciplinary Science for Air traffic Management, Daytona Beach, FL. URL https://hal-enac.archives-ouvertes.fr/hal-00912772/ Google Scholar
Matsuno, Y. and Tsuchiya, T. Stochastic 4D Trajectory Optimization for Aircraft Conflict Resolution, In 2014 IEEE Aerospace Conference, Big Sky, MT, March 2014, pp 1–10. doi: 10.1109/AERO.2014.6836275.CrossRefGoogle Scholar
Soler, M., Olivares, A. and Staffetti, E. Multiphase optimal control framework for commercial aircraft four-dimensional flight-planning problems, J. Aircr., 52, (1), 2015, pp 274–286. doi: 10.2514/1.C032697.CrossRefGoogle Scholar
Soler, M., Olivares, A. and Staffetti, E. Hybrid optimal control approach to commercial aircrafts 3d multiphase trajectory optimization, In AIAA Guidance, Navigation and Control Conference. Toronto, ON, August 2010, pp 8453. doi: 10.2514/6.2010-8453.CrossRefGoogle Scholar
Jardin, M.R. and Bryson, JR, A. E. Methods for computing minimum-time paths in strong winds, J. Guid. Control, Dyn., 2012, 35, (1), pp 165–171. doi: 10.2514/1.53614.CrossRefGoogle Scholar
Park, S.G. and Clarke, J.P.B. Fixed RTA fuel optimal profile descent based on analysis of trajectory performance bound, In 2012 IEEE/AIAA 31st Digital Avionics Systems Conference (DASC), October 2012, Williamsburg, VA, pp 3D3-1–3D3-13. doi: 10.1109/DASC.2012.6382316.CrossRefGoogle Scholar
Villaroel, J. and Rodrigues, L. Optimal control framework for cruise economy mode of flight management systems, J. Guid. Control Dyn., 2016, 39, (5), pp 1022–1033. doi: 10.2514/1.G001373.CrossRefGoogle Scholar
Soler, M., Olivares, A. and Staffetti, E. Hybrid optimal control approach to commercial aircraft trajectory planning, J. Guid. Control Dyn., 2010, 33, (3), pp 985–991. doi: 10.2514/1.47458.CrossRefGoogle Scholar
Bonami, P., Olivares, A., Soler, M. and Staffetti, E. Multiphase mixed-integer optimal control approach to aircraft trajectory optimization, J. Guid. Control Dyn., 2013, 36, (5), pp 1267–1277. doi: 10.2514/1.60492.CrossRefGoogle Scholar
Di Vito, V., Corraro, F., Ciniglio, U. and Verde, L. An overview on systems and algorithms for on-board 3D/4D trajectory management, Recent Patents Eng., 2009, 3, (3), pp 149–169. doi: 10.2174/187221209789117744.CrossRefGoogle Scholar
Yu, X. and Zhang, Y. Sense and avoid technologies with applications to unmanned aircraft systems: review and prospects, Prog. Aerosp. Sci., 2015, 74, pp 152–166. doi: 10.1016/j.paerosci.2015.01.001.CrossRefGoogle Scholar
Ceruti, A., Voloshin, V. and Marzocca, P. Heuristic algorithms applied to multidisciplinary design optimization of unconventional airship configuration, J. Aircr., 2014, 51, (6), pp 1758–1772. doi: 10.2514/1.C032439.CrossRefGoogle Scholar
Ceruti, A., Fiorini, T., Boggi, S. and Mischi, L. Engineering optimization based on dynamic technique for order preference by similarity to ideal solution fitness: application to unmanned aerial vehicle wing airfoil geometry definition, J. Multi-Criteria Decis. Anal., 2018, 25, (3–4), pp 88–100. doi: 10.1002/mcda.1637.CrossRefGoogle Scholar
Zillies, J., Kuenz, A., Schmitt, A., Schwoch, G., Mollwitz, V. and Edinger, C. Wind optimized routing: an opportunity to improve european flight efficiency? In 2014 Integrated Communications, Navigation and Surveillance Conference (ICNS) Conference Proceedings, April 2014, Herndon, VA), pp X3-1-X3-9. doi: 10.1109/ICNSurv.2014.6820029.CrossRefGoogle Scholar
Ceruti, A. and Marzocca, P. Heuristic optimization of Bezier curves based trajectories for unconventional airships docking, Aircr. Eng. Aerosp. Technol., 2017, 89, (1), pp 76–86. doi: 10.1108/AEAT-11-2014-0200.CrossRefGoogle Scholar
Qu, Y., Zhang, Y. and Zhang, Y. Optimal flight path planning for UAVs in 3-D threat environment. In 2014 International Conference on Unmanned Aircraft Systems (ICUAS), May 2014, Orlando, FL), pp 149–155. doi: 10.1109/ICUAS.2014.6842250.CrossRefGoogle Scholar
Casado, E., Goodchild, C. and Vilaplana, M. Sensitivity of Trajectory Prediction Accuracy to Aircraft Performance Uncertainty”, In AIAA Infotech@ Aerospace (I@ A) Conference, August 2013, Conference, Boston, MA, p. 5045. doi: 10.2514/6.2013-5045.CrossRefGoogle Scholar
Gillet, S., Nuic, A. and Mouillet, V. Enhancement in realism of ATC simulations by improving aircraft behaviour models”, In 29th Digital Avionics Systems Conference, October 2010, Salt Lake City, UT), pp 2.D.4-1–2.D.4-13. doi: 10.1109/DASC.2010.5655482.CrossRefGoogle Scholar
Lee, A.G., Weygandt, S.S., Schwartz, B. and Murphy, J.R. Performance of Trajectory Models with Wind Uncertainty”, In AIAA modeling and simulation technologies conference, August 2009, Chicago, Illinois, p. 5834. doi: 10.2514/6.2009-5834.CrossRefGoogle Scholar
Dancila, B.D. and Botez, R.M. Geographical area selection and construction of a corresponding routing grid used for in-flight management system flight trajectory optimization, Proc. Inst. Mech. Eng. G, 2016, 231, (5), pp 809–822. doi: 10.1177/0954410016643104.CrossRefGoogle Scholar
Dancila, B.D. and Botez, R.M. Vertical flight path segments sets for aircraft flight plan prediction and optimization, Aeronaut. J., 2018, 122, (1255), pp 1371–1424. doi: 10.1017/aer.2018.67.CrossRefGoogle Scholar
Franco, A. and Rivas, D. Minimum-cost cruise at constant altitude of commercial aircraft including wind effects, J. Guid. Control Dyn., 2011, 34, (4), pp 1253–1260. doi: 10.2514/1.53255.CrossRefGoogle Scholar
Chamseddine, A., Zhang, Y. and Rabbath, C.A. Trajectory planning and re-planning for fault tolerant formation flight control of quadrotor unmanned aerial vehicles, In 2012 American Control Conference (ACC), June 2012, Montreal, QC), pp 3291–3296. doi: 10.1109/ACC.2012.6315363.CrossRefGoogle Scholar
Zhou, Z., Duan, H., Li, P. and Di, B. Chaotic differential evolution approach for 3D trajectory planning of unmanned aerial vehicle,” In 2013 10th IEEE International Conference on Control and Automation (ICCA), June 2013, Hangzhou, China), pp 368–372. doi: 10.1109/ICCA.2013.6565043.CrossRefGoogle Scholar
, R.S.F., Berrou, Y. and Botez, R.M. New methods of optimization of the flight profiles for performance database-modeled aircraft, Proc. Inst. Mech. Eng. G, 2015, 229, (10), pp 1853–1867. doi: 10.1177/0954410014561772.CrossRefGoogle Scholar
, R.S.F. and Botez, R.M. Flight trajectory optimization through genetic algorithms for lateral and vertical integrated navigation, J. Aerosp. Inform. Syst., 2015, 12, (8), pp 533–544. doi: 10.2514/1.I010348.CrossRefGoogle Scholar
Murrieta-Mendoza, A., Beuze, B., Ternisien, L. and Botez, R.M. New reference trajectory optimization algorithm for a flight management system inspired in beam search, 2017, Chin. J Aeronaut., 30, (4), pp 1459–1472. doi: 10.1016/j.cja.2017.06.006.CrossRefGoogle Scholar
Murrieta-Mendoza, A., Beuze, B., Ternisien, L. and Botez, R.M. Aircraft vertical route optimization by beam search and initial search space reduction, J. Aerosp. Inform. Syst., 2018, 15, (3), pp 157–171. doi: 10.2514/1.I010561.CrossRefGoogle Scholar
Murrieta-Mendoza, A., Botez, R.M. and Bunel, A. Four-dimensional aircraft en route optimization algorithm using the artificial bee colony, J. Aerosp. Inform. Syst., 2018, 15, (6), pp 307–334. doi: 10.2514/1.I010523.CrossRefGoogle Scholar
Murrieta-Mendoza, A., Hamy, A. and Botez, R.M. Four- and three-dimensional aircraft reference trajectory optimization inspired by ant colony optimization. J. Aerosp. Inform. Syst., 2017, 14, (11), pp 597–616. doi: 10.2514/1.I010540.CrossRefGoogle Scholar
Robertson, B. Fuel conservation strategies: cost index explained. Boeing Aero Mag., 2007, 26, (2), pp 26–28.Google Scholar
Robertson, W., Root, R. and Adams, D. Fuel conservation strategy: cruise flight. Boeing Aero Mag., 2007, 28, (4), pp 22–27.Google Scholar
Dejonge, M.K. and Syblon, W.H. Application of cost index to fleet hub operation”, American Control Conference, June 1984, San Diego, CA), pp 179–183. doi: 10.23919/ACC.1984.4788373.CrossRefGoogle Scholar
EUROCONTROL. BADA: aircraft performance model. URL https://simulations.eurocontrol. int/solutions/bada-aircraft-performance-model/.Google Scholar
Nuic, A., Poles, D. and Mouillet, V. BADA: an advanced aircraft performance model for present and future ATM systems, Int. J Adapt. Control Signal Process., 2010, 24, (10), pp 850–866. doi: 10.1002/acs.1176.CrossRefGoogle Scholar
EUROCONTROL. Documents for BADA Version 3.7. URL https://www.eurocontrol.int/eec/ public/standard_page/proj_BADA_documents_37.html.Google Scholar
Nuic, A. User Manual For Base Of Aircraft Data (BADA) Revision 3.8”, Eurocontrol Experimental Centre, EEC Technical/Scientific Report (2010-003), 2010. URL https://www.eurocontrol.int/sites/default/files/library/007_BADA_User_Manual.pdf.Google Scholar
Botez, R. GPA-745: Introduction á l’avionique: notes de laboratoire GPA-745., Programme de Baccalauréat et Maîtrise en génie. Montréal: école de Technologie Supérieure, 2006, multiple pagination 99 p.Google Scholar
Stohl, A. Computation, accuracy and applications of trajectories - a review and bibliography. Atmos. Environ., 1998, 32, (6), pp 947–966. doi: 10.1016/S1352-2310(97)00457-3.CrossRefGoogle Scholar
Schwartz, B.E., Benjamin, S.G., Green, S.M. and Jardin, M.R. Accuracy of RUC-1 and RUC-2 wind and aircraft trajectory forecasts by comparison with ACARS observations, Weather Forecast., 2000, 15, (3), pp 313–326. doi: 10.1175/1520-0434(2000)015<0313:AORARW>2.0.CO;2.2.0.CO;2>CrossRefGoogle Scholar
Vaddi, V.V., Tandale, M.D. and Lin, S. Spatio-Temporally Correlated Wind Uncertainty Model for Simulation of Terminal Airspace Operations, In 2013 Aviation Technology Integration and Operations Conference, August 2013, Los Angeles, CA), pp 4404. doi:10.2514/6.2013-4404.CrossRefGoogle Scholar
Cole, R.E., Green, S., Jardin, M., Schwartz, B. and Benjamin, S. Wind prediction accuracy for air traffic management decision support tools., In 3rd USA/Europe Air Traffic Management R&D Seminar, June 2000, Napoli, Italy.Google Scholar
Environment Canada. Global Deterministic Prediction System. URL http://data.ec.gc.ca/ data/weather/products/global-deterministic-prediction-system/?lang=en.Google Scholar
Environment Canada. What is GRIB? URL https://weather.gc.ca/grib/what_is_GRIB_e.html.Google Scholar
NOAA. NCEP WMO GRIB2 Documentation. URL http://www.nco.ncep.noaa.gov/pmb/docs/ grib2/grib2_doc/.Google Scholar
Environment Canada. GDPS data in GRIB2 format: 25 km, URL https://weather.gc.ca/ grib/grib2_glb_25km_e.html.Google Scholar
Environment Canada. GDPS data in GRIB2 format: 66 km. URL https://weather.gc.ca/ grib/grib2_glb_66km_e.html.Google Scholar
Stohl, A., Wotawa, G., Seibert, P. and Kromp-Kolb, H. Interpolation errors in wind fields as a function of spatial and temporal resolution and their impact on different types of kinematic trajectories, J Appl. Meteorol., 1995, 34, (10), pp 2149–2165. doi: 10.1175/1520-0450(1995)034<2149:IEIWFA>2.0.CO;2.2.0.CO;2>CrossRefGoogle Scholar
Zhang, Y. and Mcgovern, S. Application of the rapid update cycle (RUC) to aircraft flight simulation, Proceedings of the ASME 2008 International Mechanical Engineering Congress and Exposition, 2008, 14, pp 45–53. doi: 10.1115/IMECE2008-66518.CrossRefGoogle Scholar
Jensen, L., Tran, H. and Hansman, J.R. Cruise Fuel Reduction Potential from Altitude and Speed Optimization in Global Airline Operations”, In Eleventh USA/Europe Air Traffic Management Research and Development Seminar (ATM2015), June 2015, Lisbon, Portugal. URL http://www.atmseminar.org/seminarContent/seminar11/papers/481-Jensen_0126150437-Final- Paper-5-7-15.pdf.Google Scholar
Wynnyk, C.M. Wind analysis in aviation applications, In 2012 IEEE/AIAA 31st Digital Avionics Systems Conference (DASC), October 2012, Williamsburg, VA), pp 5C2-1–5C2-10. doi:10.1109/DASC.2012.6382366.CrossRefGoogle Scholar
Rubio, J.C. and Kragelund, S. The trans-pacific crossing: long range adaptive path planning for UAVs through variable wind fields, In 22nd Digital Avionics Systems Conference, DASC 03., October 2003, Indianapolis, IN), pp 8.B.4-81-12. doi: 10.1109/DASC.2003.1245898.CrossRefGoogle Scholar
Wickramasinghe, N.K., Harada, A. and Miyazawa, J. Flight trajectory optimization for an efficient air transportation system, In 28th International Congress of the Aeronautical Science (ICAS 2012), December 2012, Birsbane, Australia. URL http://www.icas.org/ICAS_ARCHIVE/ICAS2012/PAPERS/910.PDF.Google Scholar
Soler, M., Olivares, A., Staffetti, E. and Bonami, P. En-route optimal flight planning constrained to pass through waypoints using MINLP, In 9th USA/Europe Air Traffic Management Research and Development Seminar, June 2011, Berlin, Germany. URL https://pdfs.semanticscholar.org/2290/cef6aca66fadfb4fadd8dfb8c3564502b756.pdf.Google Scholar
Fukuda, Y., Shirakawa, M. and Senoguchi, A. Development and Evaluation of Trajectory Prediction Model, In Proceedings of the 27th International Congress of the Aeronautical Sciences, September 2010, Nice, France. URL http://www.icas.org/ICAS_ARCHIVE/ICAS2010/PAPERS/818.PDF.Google Scholar
Jin, L., Cao, Y. and Sun, D. Investigation of potential fuel savings due to continuous-descent approach, J. Aircr., 2013, 50, (3), pp 807–816. doi: 10.2514/1.C032000.CrossRefGoogle Scholar
Environment Canada. Regional Deterministic Prediction System. URL http://data.ec.gc.ca/ data/weather/products/regional-deterministic-prediction-system/?lang=en. Google Scholar
Altus, S. Effective flight plans can help airlines economize, Boeing Aero Mag., 2009, (35), Quarter 03, pp 27–30. URL https://www.boeing.com/commercial/aeromagazine/articles/qtr_03_09/pdfs/AERO_Q309_article08.pdf.Google Scholar
FAA. FAA Flight Planning Information. URL https://www.faa.gov/about/office_org/headquarters_offices/ato/service_units/air_traffic_services/flight_plan_filing/. Google Scholar
Lenart, A.S. Orthodrome and Loxodromes in Marine Navigation, J. Navig., 2017, 70, (2), pp 432–439. doi: 10.1017/s0373463316000552.CrossRefGoogle Scholar
FlightAware, Swiss 40, 2019. URL https://flightaware.com/live/flight/SWR40/history/20190225/1220Z/LSZH/KLAX.Google Scholar
Carlton-Wippern, K.C. On loxodromic navigation, J. Navig., 1992, 45, (2), pp 292–297. doi: 10.1017/s0373463300010791.CrossRefGoogle Scholar
Karney, C.F. Algorithms for geodesics, J. Geodesy, 2013, 87, (1), pp 43–55. doi: .CrossRefGoogle Scholar
Schreur, J.M. B737 Flight management computer flight plan trajectory computation and analysis, Proceedings of the 1995 American Control Conference ACC’95, 1995, 5, pp 3419–3424. doi: 10.1109/ACC.1995.532246.CrossRefGoogle Scholar
Janssen, V. Understanding coordinate reference systems, datums and transformations, Int J Geoinform., 2009, 5, (4), pp 41–53. URL https://eprints.utas.edu.au/9575/.Google Scholar
FAA. Airplane Upset Recovery High Altitude Operations, 2018. URL https://www.faa.gov/other_ visit/aviation_industry/airline_operators/training/media/Appendix_3-E_HighAltOperations.pdf.Google Scholar
Schmitt, L.M. Theory of genetic algorithms, Theor. Comput. Sci., 2001, 259, (1–2), pp 1–61. doi: 10.1016/s0304-3975(00)00406-0.CrossRefGoogle Scholar
Lipowski, A. and Lipowska, D. Roulette-wheel selection via stochastic acceptance, Physica A, 2012, 391, (6), pp 2193–2196. doi: 10.1016/j.physa.2011.12.004.CrossRefGoogle Scholar
FlightAware. FlightAware ADS-B Coverage Map. URL https://flightaware.com/adsb/coverage#data-coverage.Google Scholar
FlightAware. Multilateration (MLAT) Overview. URL https://flightaware.com/adsb/mlat/.Google Scholar
FAA. Part 91 – General Operating And Flight Rules. Electronic Code of Federal Regulations, Title14: Aeronautics and Space. URL.Google Scholar
Young, T.M. Performance of the Jet Transport Airplane: Analysis Methods, Flight Operations, and Regulations, John Wiley &Sons Inc, 2017, Hoboken, NJ. 688 p. ISBN-10: 1118384865, ISBN-13: 978-1118384862.CrossRefGoogle Scholar