TY - JOUR
T1 - An efficient ant colony system based on receding horizon control for the aircraft arrival sequencing and scheduling problem
AU - Zhan, Zhi Hui
AU - Zhang, Jun
AU - Li, Yun
AU - Liu, Ou
AU - Kwok, S. K.
AU - Ip, W. H.
AU - Kaynak, Okyay
N1 - Funding Information:
Manuscript received March 22, 2009; revised November 2, 2009 and February 11, 2010; accepted February 12, 2010. Date of publication April 1, 2010; date of current version May 25, 2010. This work was supported in part by the National Natural Science Foundation of China Joint Fund with Guangdong under Key Project U0835002 and in part by the National High-Technology Research and Development Program (“863” Program) of China under Grant 2009AA01Z208. The Associate Editor for this paper was M. Brackstone.
PY - 2010/6
Y1 - 2010/6
N2 - The aircraft arrival sequencing and scheduling (ASS) problem is a salient problem in air traffic control (ATC), which proves to be nondeterministic polynomial (NP) hard. This paper formulates the ASS problem in the form of a permutation problem and proposes a new solution framework that makes the first attempt at using an ant colony system (ACS) algorithm based on the receding horizon control (RHC) to solve it. The resultant RHC-improved ACS algorithm for the ASS problem (termed the RHC-ACS-ASS algorithm) is robust, effective, and efficient, not only due to that the ACS algorithm has a strong global search ability and has been proven to be suitable for these kinds of NP-hard problems but also due to that the RHC technique can divide the problem with receding time windows to reduce the computational burden and enhance the solution's quality. The RHC-ACS-ASS algorithm is extensively tested on the cases from the literatures and the cases randomly generated. Comprehensive investigations are also made for the evaluation of the influences of ACS and RHC parameters on the performance of the algorithm. Moreover, the proposed algorithm is further enhanced by using a two-opt exchange heuristic local search. Experimental results verify that the proposed RHC-ACS-ASS algorithm generally outperforms ordinary ACS without using the RHC technique and genetic algorithms (GAs) in solving the ASS problems and offers high robustness, effectiveness, and efficiency.
AB - The aircraft arrival sequencing and scheduling (ASS) problem is a salient problem in air traffic control (ATC), which proves to be nondeterministic polynomial (NP) hard. This paper formulates the ASS problem in the form of a permutation problem and proposes a new solution framework that makes the first attempt at using an ant colony system (ACS) algorithm based on the receding horizon control (RHC) to solve it. The resultant RHC-improved ACS algorithm for the ASS problem (termed the RHC-ACS-ASS algorithm) is robust, effective, and efficient, not only due to that the ACS algorithm has a strong global search ability and has been proven to be suitable for these kinds of NP-hard problems but also due to that the RHC technique can divide the problem with receding time windows to reduce the computational burden and enhance the solution's quality. The RHC-ACS-ASS algorithm is extensively tested on the cases from the literatures and the cases randomly generated. Comprehensive investigations are also made for the evaluation of the influences of ACS and RHC parameters on the performance of the algorithm. Moreover, the proposed algorithm is further enhanced by using a two-opt exchange heuristic local search. Experimental results verify that the proposed RHC-ACS-ASS algorithm generally outperforms ordinary ACS without using the RHC technique and genetic algorithms (GAs) in solving the ASS problems and offers high robustness, effectiveness, and efficiency.
KW - Air traffic control (ATC)
KW - Ant colony system(ACS)
KW - Arrival sequencing and scheduling (ASS)
KW - Receding horizoncontrol (RHC)
UR - http://www.scopus.com/inward/record.url?scp=77953120128&partnerID=8YFLogxK
U2 - 10.1109/TITS.2010.2044793
DO - 10.1109/TITS.2010.2044793
M3 - Article
AN - SCOPUS:77953120128
SN - 1524-9050
VL - 11
SP - 399
EP - 412
JO - IEEE Transactions on Intelligent Transportation Systems
JF - IEEE Transactions on Intelligent Transportation Systems
IS - 2
M1 - 5440937
ER -