Title 
Algorithms of Scheduling Aircraft Landing Problem 
Author

Wen, Min (Department of Informatics and Mathematical Modeling, Technical University of Denmark, DTU, DK2800 Kgs. Lyngby, Denmark)

Supervisor

Clausen, Jens (Department of Informatics and Mathematical Modeling, Technical University of Denmark, DTU, DK2800 Kgs. Lyngby, Denmark) Larsen, Jesper (Department of Informatics and Mathematical Modeling, Technical University of Denmark, DTU, DK2800 Kgs. Lyngby, Denmark)

Institution 
Technical University of Denmark, DTU, DK2800 Kgs. Lyngby, Denmark 
Thesis level 
Master's thesis 
Year 
2005 
Abstract 
This thesis addresses the problem of scheduling aircraft landings at an airport. Given a set of planes and runways, the objective is to minimize the total (weighted) deviation from the target landing time for each plane. There are costs associated with landing either earlier or later than a target landing time for each plane. Each plane has to land on one of the runways within its predetermined time windows such that separation criteria between all pairs of planes are satisfied. This type of problem is a largescale optimization problem, which occurs at busy airports where making optimal use of the bottleneck resource (the runways) is crucial to keep the airport operating smoothly.
This thesis is the first attempt to develop a branchandprice exact algorithm for the Aircraft Landing Problem (ALP), in which the column generation method is applied to solve the linear relaxation problem for each branch node throughout the branchandbound procedure. We formulate the ALP as a set partitioning problem with side constraints on the number of available runways. We also present a mixed integer formulation for the subproblem in column generation, which can be used to generate the columns with the minimum negative reduced cost. Then a branchandbound method is developed to find the optimal integer solution for the ALP. Finally, the branchandprice exact algorithm is implemented and tested on the public data from OR Library involving up to 50 aircraft and 4 runways. The computational results show that the algorithm can solve the problem optimally in acceptable CPU time. Furthermore, the optimal solutions can be achieved with less than 500 columns generated and 12 branch nodes explored. 
Imprint 
Department of Informatics and Mathematical Modeling, Technical University of Denmark, DTU : DK2800 Kgs. Lyngby, Denmark 
Pages 
92 
Fulltext 

Admin 
Creation date: 20060622
Update date: 20121217
Source: dtu
ID: 185882
Original MXD
