Constraint guided search for aircraft sequencing

• Published in: Expert systems with applications 2019-03, Vol.118, p.440-458
• Main Authors: Riahi, Vahid, Newton, M.A. Hakim, Polash, M.M.A., Su, Kaile, Sattar, Abdul
• Format: Article
• Language: English
• Subjects: Air traffic control; Aircraft; Aircraft components; Aircraft landing; Aircraft sequencing; Airports; Algorithms; Artificial intelligence; Decisions; Expert systems; Local search; Optimization; Runway operations; Runways; Search methods; State of the art; Takeoff; Theory of constraints
• ISSN: 0957-4174; 1873-6793
• DOI: 10.1016/j.eswa.2018.10.033

•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. 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.