A Polynomial Time Algorithm for Aircraft Landing Problem

Sang-Un, Lee

Journal of The Korea Society of Computer and Information

Abbr : JKSCI
2014, 19(9), pp.161-168
Publisher : The Korean Society Of Computer And Information
Research Area : Computer Science

Sang-Un, Lee ¹

¹강릉원주대학교

ABSTRACT

The optimal solution ofminimumcost for aircraft landing problem(ALP) is very difficult problembecause theapproached aircraft are randomtime interval. Therefore this problemhas been applied by variousmetaheuristicmethods. This paper suggests O(ｎlogｎ) polynomial time heuristic algorithm to obtain the optimalsolution for ALP. This algorithm sorts the target time of aircraft into ascending order. Then weapply the optimization of change the landing sequence take account of separation time and the costof landing. For the Airland1 through Airland8 of benchmark data of ALP, we choose 25 data untilthe number of runway ｍ that the total landing cost is 0. We can be obtain the optimal solution forall of the 25 data. Especially we can be improve the known optimal solution for ｍ=1 of Airland8.
KEYWORDS

Aircraft landingproblem, Target time, Cost function, Separationtime, Landingsequenceoptimization
REFERENCES (13)

[journal] J. E. Besley / 2000 / Scheduling Aircraft Landings - The Static Case / Transportation Science 34(2) : 180~197

[journal] J. E. Besley / 2004 / Displacement Problemand Dynamically Scheduling Aircraft Landings / Journal of the Operational Research Society 55(1) : 54~64

[thesis] B. C. Fiss / 2010 / GRASP Applicado ao Problema de Aterrissagemde Aviões / Universidade Federal do Rio Grande do Sul,

[confproc] I. Moser / 2007 / Solving Dynamic Single-Runway Aircraft Landing Problems with Extremal Optimisation / Proceedings of the IEEE SymposiumonComputational Intelligence inScheduling : 206~211

[confproc] A. Awasthi / 2013 / Aircraft Landing Problem: Efficient Algorithmfor a Given Landing Sequence / 16thIEEEInternational Conference on Computational Science and Engineering in Data Structures and Algorithms : 1~16

[journal] IMoser / 2007 / Scheduling Aircraft Landings Dynamically Using Stochastic and Deterministic Elements / International Journal of Information Technology and Intelligent Computing 2(1) : 1~21

[journal] J. Xie / 2013 / A Hybrid Metaheuristic forMultipleRunways Aircraft Landing ProblemBased on Bat Algorithm / Journal of Applied Mathematics 2013 : 1~8

[journal] G. Bencheikh / 2011 / Improved Ant Colony Algorithm to Solve the Aircraft Landing Problem / International Journal of Computer Theory and Engineering 3(2) : 224~233

[journal] S. Yu / 2011 / A Real-time Schedule Method for Aircraft Landing Scheduling ProblemBased on Cellular Automation / Applied Soft Computing 11(4) : 3485~3493

[journal] G. Bencheikh / 2009 / Hybrid Method for Aircraft Landing Scheduling Based on a Job Shop Formulation / International Journal of Computer Science and Network Security 9(8) : 78~88

[web] J. E. Beasley / 2013 / OR-Library: Equitable Partitioning Problem / http://people.brunel.ac.uk/~mastjjb/jeb/orlib/eppinfo.html

[journal] X. B. Hu / 2011 / A Ripple- Spreading GeneticAlgorithmfor theAircraft SequencingProblem / Evolutionary Computation 19(1) : 77~106

[confproc] K. Kahn / 2011 / TheMulticriteria Aircraft Landing Problem / The 21st International Conference onMultiple Criteria DecisionMaking (MCDM) : 1~32
KCI Citation (1)

KJC Korea
Journal Central

Statistics

Tools