Constraint guided search for aircraft sequencing. (15th March 2019)

• Record Type: Journal Article
• Authors: Riahi, Vahid; Newton, M.A. Hakim; Polash, M.M.A.; Su, Kaile; Sattar, Abdul
• Is Part Of: Expert systems with applications. Volume 118(2019)
• Page Start: 440
• Page End: 458
• Publication Date: 2019-03-15
• Subjects: Aircraft sequencing -- Runway operations -- Local search; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2018.10.033
• Languages: English
• ISSNs: 0957-4174

Abstract

Highlights: An effective heuristic and search algorithm for aircraft sequencing problem. Advance the algorithms by exploiting the problem specific structural knowledge. Outperforms state-of-the-art algorithms on well-known benchmark problem sets. Abstract: Aircraft sequencing problem (ASP) is an NP-Hard problem. It involves allocation of aircraft to runways for landing and takeoff, minimising total tardiness. ASP has made significant progress in recent years. However, within practical time limits, existing incomplete algorithms still either find low quality solutions or struggle with large problems. One key reason behind this is the typical way of using generic heuristics or metaheuristics that usually lack problem specific structural knowledge. As a result, existing such methods use either an exhaustive or a random neighbourhood generation strategy. So their search guidance comes only from the evaluation function that is used mainly after the neighbourhood generation. In this work, we aim to advance ASP search by better exploiting the problem specific structural knowledge. We use the constraint and the objective functions to obtain such problem specific knowledge and we exploit such knowledge both in a constructive search method and in a local search method. Our motivation comes from the constraint optimisation paradigm in artificial intelligence, where instead of random decisions, constraint-guided more informed optimisation decisions are of particular interest. We run our experiments on a range of standard benchmark problem instances that include instances from real airports and instances crafted using real airport parameters, and contain scenarios involving multiple runways and both landing and takeoff operations. We show that our proposed algorithms significantly outperform existing state-of-the-art aircraft sequencing algorithms.