Branch Bound Global-Search Algorithm for Aircraft Ground Movement Optimization

摘要

Optimal aircraft ground scheduling is a well known NP-Hard problem and hence heuristics are often used to generate schedules within realistic run-times. These heuristics are designed to run fast, but often do not promise any guarantee about the solution quality. This paper introduces a Branch & Bound based aircraft routing and scheduling approach with guaranteed global optimality; as a real-time decision support tool for Air Traffic Controllers. The benchmarking results of the algorithm on two problems, one by Roling et al. and another by Baijal et al. on the active map of Mumbai International Airport have been illustrated. The globally optimal nature of the solution generated by this algorithm exhibits a distinct improvement over the respective solutions while maintaining minimal run-times. An illustration of the performance of this algorithm on the complete map of the Mumbai International Airport with its unique crisscross runway configuration is also included.