For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A Heuristic Algorithm for Solving the Aircraft Landing Scheduling Problem with a Landing Sequence Division
Wen SHI Shan JIANG Xuan LIANG Na ZHOU
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2019/08/01
Online ISSN: 1745-1337
Type of Manuscript: PAPER
Category: Intelligent Transport System
air traffic management, aircraft landing scheduling, heuristic,
Full Text: FreePDF(2MB)
Aircraft landing scheduling (ALS) is one of the most important challenges in air traffic management. The target of ALS is to decide a landing scheduling sequence and calculate a landing time for each aircraft in terminal areas. These landing times are within time windows, and safety separation distances between aircraft must be kept. ALS is a complex problem, especially with a large number of aircraft. In this study, we propose a novel heuristic called CGIC to solve ALS problems. The CGIC consists of four components: a chunking rule based on costs, a landing subsequence generation rule, a chunk improvement heuristic, and a connection rule. In this algorithm, we reduce the complexity of the ALS problem by breaking it down into two or more subproblems with less aircraft. First, a feasible landing sequence is generated and divided into several subsequences as chunks by a chunking rule based on aircraft cost. Second, each chunk is regenerated by a constructive heuristic, and a perturbative heuristic is applied to improve the chunks. Finally, all chunks constitute a feasible landing sequence through a connection rule, and the landing time of each aircraft is calculated on the basis of this sequence. Simulations demonstrate that (a) the chunking rule based on cost outperforms other chunking rules based on time or weight for ALS in static instances, which have a large number of aircraft; (b) the proposed CGIC can solve the ALS problem up to 500 aircraft optimally; (c) in dynamic instances, CGIC can obtain high-quality solutions, and the computation time of CGIC is low enough to enable real-time execution.