An efficient ant colony system based on receding horizon control for the aircraft arrival sequencing and scheduling problem

Zhi Hui Zhan, Jun Zhang, Yun Li, Ou Liu, S. K. Kwok, W. H. Ip, Okyay Kaynak

Research output: Contribution to journalArticle

Abstract

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.

Original languageEnglish
Article number5440937
Pages (from-to)399-412
Number of pages14
JournalIEEE Transactions on Intelligent Transportation Systems
Volume11
Issue number2
DOIs
Publication statusPublished - 1 Jun 2010

Fingerprint

Scheduling
Aircraft
Scheduling algorithms
Polynomials
Air traffic control
Genetic algorithms

Keywords

  • Air traffic control (ATC)
  • Ant colony system(ACS)
  • Arrival sequencing and scheduling (ASS)
  • Receding horizoncontrol (RHC)

Cite this

@article{074425fd2b524b949fd894c4c64d291e,
title = "An efficient ant colony system based on receding horizon control for the aircraft arrival sequencing and scheduling problem",
abstract = "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.",
keywords = "Air traffic control (ATC), Ant colony system(ACS), Arrival sequencing and scheduling (ASS), Receding horizoncontrol (RHC)",
author = "Zhan, {Zhi Hui} and Jun Zhang and Yun Li and Ou Liu and Kwok, {S. K.} and Ip, {W. H.} and Okyay Kaynak",
year = "2010",
month = "6",
day = "1",
doi = "10.1109/TITS.2010.2044793",
language = "English",
volume = "11",
pages = "399--412",
journal = "IEEE Transactions on Intelligent Transportation Systems",
issn = "1524-9050",
publisher = "IEEE",
number = "2",

}

An efficient ant colony system based on receding horizon control for the aircraft arrival sequencing and scheduling problem. / Zhan, Zhi Hui; Zhang, Jun; Li, Yun; Liu, Ou; Kwok, S. K.; Ip, W. H.; Kaynak, Okyay.

In: IEEE Transactions on Intelligent Transportation Systems, Vol. 11, No. 2, 5440937, 01.06.2010, p. 399-412.

Research output: Contribution to journalArticle

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

PY - 2010/6/1

Y1 - 2010/6/1

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

UR - https://ieeexplore.ieee.org/document/5440937

U2 - 10.1109/TITS.2010.2044793

DO - 10.1109/TITS.2010.2044793

M3 - Article

VL - 11

SP - 399

EP - 412

JO - IEEE Transactions on Intelligent Transportation Systems

JF - IEEE Transactions on Intelligent Transportation Systems

SN - 1524-9050

IS - 2

M1 - 5440937

ER -