Skip to main content

Advertisement

SpringerLink
Log in

A genetic local search algorithm with a threshold accepting mechanism for solving the runway dependent aircraft landing problem

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

As the demand for air transportation continues to grow, some flights cannot land at their preferred landing times because the airport is near its runway capacity. Extra fuel consumption and air pollution are then caused by the landing delays. Moreover, such delays may possibly yield extra costs for both passengers and airline companies that result from rescheduling transfer passengers and crew members. Consequently, how to increase the handling efficiency of congested airports is a crucial management issue. Building new runways at existing airports is often not feasible due to environmental, financial and geographical constraints. Therefore, devising a method for tackling the aircraft landing problem (ALP) in order to optimize the usage of existing runways at airports is the focus of this paper. This paper aims to develop a solution procedure based on a genetic local search (GLS) algorithm for solving the ALP with runway dependent attributes. A set of numerical experiments were conducted to test the validity of the proposed algorithm based on five test instances created and investigated by previous studies. The numerical results showed that the proposed GLS algorithm can effectively and efficiently determine the runway allocation, sequence and landing time for arriving aircraft for the five test cases by minimizing total delays under the separation constraints in comparison with the outcomes yielded by previous studies.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Airports Council International: Annual traffic data, http://www.airports.org/ (2009). Accessed 24 September 2009

  2. Beasley J.E., Krishnamoorthy M., Sharaiha Y.M., Abramson D.: Scheduling aircraft landings—the static case. Trans. Sci. 34, 180–197 (2000)

    Article  MATH  Google Scholar 

  3. Bräysy O., Porkka P.P., Dullaert W., Repoussis P.P., Tarantilis C.D.: A well-scalable metaheuristic for the fleet size and mix vehicle routing problem with time windows. Expert Syst. Appl. 36, 8460–8475 (2009)

    Article  Google Scholar 

  4. Cheng, V.H.L., Crawford, L.S., Menon, P.K.: Air traffic control using genetic search techniques. In: Proceedings of the 1999 IEEE International Conference on Control Appliacations, Hawaii, USA (1999)

  5. Davis L.: Handbook of Genetic Algorithms. Van Nostrand Reinhold, New York (1991)

    Google Scholar 

  6. Dueck G., Scheuer T.: Threshold accepting: a general purpose optimization algorithm appearing superior to simulated annealing. J. Comput. Phys. 90, 161–175 (1990)

    Article  MATH  MathSciNet  Google Scholar 

  7. Essafi I., Mati Y., Dauzere-Peres S.: A genetic local search algorithm for minimizing total weighted tardiness in the job-shop scheduling problem. Comput. Oper. Res. 35, 2599–2616 (2008)

    MATH  MathSciNet  Google Scholar 

  8. Goldberg D.E.: Genetic Algorithms in Search, Optimization, and Machine learning. Addison-Wesley, Reading (1989)

    MATH  Google Scholar 

  9. Hamzacebi C.: Improving genetic algorithms’ performance by local search for continuous function optimization. Appl. Math. Comput. 196, 309–317 (2008)

    Article  MATH  Google Scholar 

  10. Hansen J.V.: Genetic search methods in air traffic control. Comput. Oper. Res. 31, 45–59 (2004)

    Article  Google Scholar 

  11. Holland J.H.: Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. MIT Press, Boston (1992)

    Google Scholar 

  12. Ishibuchi H., Murata T.: A multi-objective genetic local search algorithm and its application to flowshop scheduling. IEEE Trans. Syst. Man Cybern. Part C 28, 392–403 (1998)

    Article  Google Scholar 

  13. Lardeux F., Saubion F., Hao J.K.: GASAT: a genetic local search algorithm for the satisfiability problem. Evol. Comput. 14, 223–253 (2006)

    Article  Google Scholar 

  14. Lee D.S., Vassilios S., Vassiliadis J.M., Park J.M.: A novel threshold accepting meta-heuristic for the job-shop scheduling problem. Comput. Oper. Res. 31, 2199–2213 (2004)

    Article  MATH  Google Scholar 

  15. Liu Y.-H.: A hybrid scatter search for the probabilistic traveling salesman problem. Comput. Oper. Res. 34, 2949–2963 (2007)

    Article  MATH  Google Scholar 

  16. Liu Y.-H.: Diversified local search strategy under scatter search framework for the probabilistic traveling salesman problem. Eur. J. Oper. Res. 191, 332–346 (2008)

    Article  MATH  Google Scholar 

  17. Liu Y.-H.: Different initial solution generators in genetic algorithms for solving the probabilistic traveling salesman problem. Appl. Math. Comput. 216, 125–137 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  18. Marimuthu S., Ponnambalam S.G., Jawahar N.: Threshold accepting and ant-colony optimization algorithms for scheduling m-machine flow shops with lot streaming. J. Mater. Process. Tech. 209, 1026–1041 (2009)

    Article  Google Scholar 

  19. Nikolakopoulos A., Sarimveis H.: A threshold accepting heuristic with intense local search for the solution of special instances of the traveling salesman problem. Eur. J. Oper. Res. 177, 1911–1929 (2007)

    Article  MATH  Google Scholar 

  20. Ombuki B.M., Ventresca M.: Local search genetic algorithms for the job shop scheduling problem. Appl. Intell. 21, 99–109 (2004)

    Article  MATH  Google Scholar 

  21. Pardalos, P.M., Korotkikh, V. (eds): Optimization and Industry: New Frontiers. Kluwer, Dordrecht (2003)

    MATH  Google Scholar 

  22. Pardalos, P.M., Resende, M.G.C. (eds): Handbook of Applied Optimization. Oxford University Press, New York (2002)

    MATH  Google Scholar 

  23. Pardalos, P.M., Romeijn, E. (eds): Handbook of Global Optimization, vol. 2. Kluwer, Dordrecht (2002)

    MATH  Google Scholar 

  24. Pinol H., Beasley J.E.: Scatter search and bionomic algorithms for the aircraft landing problem. Eur. J. Oper. Res. 171, 439–462 (2006)

    Article  MATH  Google Scholar 

  25. Silberholz J., Golden B.: Comparison of metaheuristics. In: Gendreau, M., Potvin, J.-V. (eds) Handbook of Metaheuristics, 2nd edn, Springer, Heidelberg (2010)

    Google Scholar 

  26. Soomer M.J., Franx G.J.: Scheduling aircraft landings using airlines’ preferences. Eur. J. Oper. Res. 190, 277–291 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  27. Tarantilis C.D., Kiranoudis C.T., Vassiliadis V.S.: A list based threshold accepting algorithm for the capacitated vehicle routing problem. Int. J. Comput. Math. 79, 537–553 (2002)

    Article  MATH  Google Scholar 

  28. Tarantilis C.D., Kiranoudis C.T., Vassiliadis V.S.: A threshold accepting metaheuristic for the heterogeneous fixed fleet vehicle routing problem. Eur. J. Oper. Res. 152, 148–158 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  29. Zahrani M.S., Loomes M.J., Malcolm J.A., Ullah A.Z.M.D., Steinhofel K., Albrecht A.A.: Genetic local search for multicast routing with pre-processing by logarithmic simulated annealing Comput. Oper. Res. 35, 2049–2070 (2008)

    Article  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Civil Engineering, National Chi Nan University, No. 1, University Road, Puli, Nantou Hsien, 54561, Taiwan

    Yu-Hsin Liu

Authors
  1. Yu-Hsin Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yu-Hsin Liu.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Liu, YH. A genetic local search algorithm with a threshold accepting mechanism for solving the runway dependent aircraft landing problem. Optim Lett 5, 229–245 (2011). https://doi.org/10.1007/s11590-010-0203-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-010-0203-0

Keywords

Search

Navigation