This work proposes a framework to compute the optimal flight sequencing and runway assignment for arrivals and departures of a general runway system in any configuration. Towards this, an algorithm to compute the minimum makespan defined as the time difference between the start and end of a given set of operations, is proposed. The proposed algorithm is based on a branch-and-bound technique and allows for the efficient computation of the best runway assignment and sequencing of arrival and departure operations that minimizes the makespan at a given airport. The lower and upper bounds of the cost of each branch for the best first search in the branch- and-bound algorithm are computed based on the minimum separation standards between arrival and departure operations set by the Federal Aviation Administration. The optimal objective value is mathematically proved to lie between these bounds and the algorithm uses these bounds to efficiently find promising branches and discard all others and terminate with at least one sequence with the minimal makespan. The proposed algorithm is analyzed and validated through real traffic operations data at the Hartsfield-Jackson Atlanta International Airport.
展开▼