Paper Info
Title
Aircraft Landing Problem: An Efficient Algorithm for a Given Landing Sequence
Abstract
In this paper, we investigate a special case of the static aircraft landing problem (ALP) with the objective to optimize landing sequences and landing times for a set of air planes. The problem is to land the planes on one or multiple runways within a time window as close as possible to the preferable target landing time, maintaining a safety distance constraint. The objective of this well-known NP-hard optimization problem is to minimize the sum of the total penalty incurred by all the aircraft for arriving earlier or later than their preferred landing times. For a problem variant that optimizes a given feasible landing sequence for the single runway case, we present an exact polynomial algorithm and prove the run-time complexity to lie in O(N^3), where N is the number of aircraft. The proposed algorithm returns the optimal solution for the ALP for a given feasible landing sequence on a single runway for a common practical case of the ALP described in the paper. Furthermore, we propose a strategy for the ALP with multiple runways and present our results for all the benchmark instances with single and multiple runways, while comparing them to previous results in the literature.
Year
DOI
Venue
2013
10.1109/CSE.2013.14
C3S2E
Keywords
Field
DocType
optimisation,preferred landing time,np-hard optimization problem,landing sequence optimization,preferable target landing time,multiple runways,feasible landing sequence,multiple runway,problem variant,single runway,time window,aircraft landing problem,common practical case,well-known np-hard optimization problem,static aircraft landing problem,computational complexity,efficient algorithm,alp,exact polynomial algorithm,landing sequence,run-time complexity,aircraft landing guidance,landing time,safety distance constraint
Computer science,Aircraft landing,Algorithm,Linear programming,Runway,Polynomial algorithm,Optimization problem,Special case,Computational complexity theory
Conference
Volume
ISSN
Citations 
abs/1311.2880
1949-0828
6
PageRank 
References 
Authors
0.47
6
3
Name
Order
Citations
PageRank
Abhishek Awasthi193.27
Oliver Kramer230438.42
Jörg Lässig317522.53