摘要
停机位分配作业关系到整个机场的系统运作,其作用相当重要。通过对停机位分配的分析,把停机位的分配转化为图着色,建立停机位分配问题的图着色模型,并引入时间片算法确定航班使用机位的时间冲突集合,根据"先到先服务"的原则给出了停机位分配的顶点序列着色算法,该算法的计算复杂性为O(n2k2),最后将该算法应用于一个算例。
Gate assignment plays an important role and has significant impact on the operation of an airport system. A graph coloring model of gate assignment in airport is set up by analyzing the characteristics of time intervals set that the scheduled flights use the gates. And, a time slice algorithm is introduced to determinate the set of the time conflict of gate assignment. The vertex sequence coloring algorithm is presented according to the rule 'First-In-First-Out'. The computerizing complexity of this algorithm is (O(n^2k^2).) Finally, an example is analyzed to demonstrate the application of this algorithm.
出处
《系统工程理论方法应用》
北大核心
2005年第2期136-140,共5页
Systems Engineering Theory·Methodology·Applications
基金
中国民航飞行学院青年科研基金资助项目
关键词
停机位分配
机场
图论
图着色
算法
gate assignment
airport
graph theory
graph coloring
algorithm