Pruning Rules for Optimal Runway Sequencing

Geert De Maere (), Jason A. D. Atkin () and Edmund K. Burke ()
Additional contact information
Geert De Maere: Automated Scheduling, Optimisation and Planning, School of Computer Science, University of Nottingham, Nottingham NG8 1BB, United Kingdom
Jason A. D. Atkin: Automated Scheduling, Optimisation and Planning, School of Computer Science, University of Nottingham, Nottingham NG8 1BB, United Kingdom
Edmund K. Burke: School of Electronic Engineering and Computer Science, Queen Mary University of London, London E1 4NS, United Kingdom

Transportation Science, 2018, vol. 52, issue 4, 898-916

Abstract: This paper investigates runway sequencing for real-world scenarios at one of the world’s busiest airports, London Heathrow. Several pruning principles are introduced that enable significant reductions of the problem’s average complexity, without compromising the optimality of the resulting sequences, nor compromising the modeling of important real-world constraints and objectives. The pruning principles are generic and can be applied in a variety of heuristic, metaheuristic, or exact algorithms. They could also be applied to different runway configurations, as well as to other variants of the machine scheduling problem with sequence dependent setup times, the generic variant of the runway sequencing problem in this paper. They have been integrated into a dynamic program for runway sequencing, which has been shown to be able to generate optimal sequences for large-scale problems at a low computational cost, while considering complex nonlinear and nonconvex objective functions that offer significant flexibility to model real-world preferences and real-world constraints. The results shown here clearly demonstrate that, by exploiting the problem structure, complex runway sequencing problems can be solved exactly.

Keywords: dynamic programming; runway sequencing; machine scheduling; sequence dependent setup times (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1287/trsc.2016.0733 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:52:y:2018:i:4:p:898-916

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().