AIRCRAFT LANDING PROBLEM: AN
EFFICIENT ALGORITHM FOR A GIVEN LANDING SEQUENCE
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.
Published in:
Date of
Conference:
3-5 Dec. 2013
Page(s):
20 - 27
INSPEC Accession
Number:
14145809
Conference
Location :
Sydney, NSW
Digital Object
Identifier :
Publisher:
IEEE
