| 机场停机位分配问题的图着色模型及其算法 |
| |
| 引用本文： | 文军,李冰,王清蓉,杜文. 机场停机位分配问题的图着色模型及其算法[J]. 系统管理学报, 2005, 14(2): 136-140 |
| |
| 作者姓名： | 文军 李冰 王清蓉 杜文 |
| |
| 作者单位： | 1. 西南交通大学,交通运输学院,成都 610031;中国民航飞行学院,空管学院,广汉,618307
2. 西南交通大学,交通运输学院,成都,610031 |
| |
| 基金项目： | 中国民航飞行学院青年科研基金资助项目 |
| |
| 摘 要： | 停机位分配作业关系到整个机场的系统运作,其作用相当重要。通过对停机位分配的分析,把停机位的分配转化为图着色,建立停机位分配问题的图着色模型,并引入时间片算法确定航班使用机位的时间冲突集合,根据"先到先服务"的原则给出了停机位分配的顶点序列着色算法,该算法的计算复杂性为O(n2k2),最后将该算法应用于一个算例。
|
| 关 键 词： | 停机位分配 机场 图论 图着色 算法 |
| 文章编号： | 1005-2542(2005)02-0136-05 |
| 修稿时间： | 2003-09-08 |
Graph Coloring Model and Algorithm of Gate Assignment in Airport |
| |
| WEN Jun,LI Bing,WANG Qing-rong,DU Wen. Graph Coloring Model and Algorithm of Gate Assignment in Airport[J]. Systems Engineering Theory·Methodology·Applications, 2005, 14(2): 136-140 |
| |
| Authors: | WEN Jun LI Bing WANG Qing-rong DU Wen |
| |
| Abstract: | 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. |
| |
| Keywords: | gate assignment airport graph theory graph coloring algorithm |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
