Journal
TRANSPORTATION RESEARCH PART C-EMERGING TECHNOLOGIES
Volume 95, Issue -, Pages 570-581Publisher
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.trc.2018.07.031
Keywords
Aircraft sequencing problem; 0-1 mixed-integer programming; Asymmetric traveling salesman problem with time-windows; Data-splitting algorithm; Runway throughput; Runway optimization
Categories
Funding
- ATMRI (NTU-CAAS) Grant [M4061216]
Ask authors/readers for more resources
In this research, we present a data-splitting algorithm to optimally solve the aircraft sequencing problem (ASP) on a single runway under both segregated and mixed-mode of operation. This problem is formulated as a 0-1 mixed-integer program (MIP), taking into account several realistic constraints, including safety separation standards, wide time-windows, and constrained position shifting, with the objective of maximizing the total throughput. Varied scenarios of large scale realistic instances of this problem, which is NP-hard in general, are computationally difficult to solve with the direct use of commercial solver as well as existing state-of-the-art dynamic programming method. The design of the algorithm is based on a recently introduced data-splitting algorithm which uses the divide-and-conquer paradigm, wherein the given set of flights is divided into several disjoint subsets, each of which is optimized using 0-1 MW while ensuring the optimality of the entire set. Computational results show that the difficult instances can be solved in real-time and the solution is efficient in comparison to the commercial solver and dynamic programming, using both sequential, as well as parallel, implementation of this pleasingly parallel algorithm.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available