停机位分配问题的顶点着色模型及算法

作者：罗荣武; 谢如鹤; 张得志

来源：系统工程理论与实践, 2007, (11): 148-152.

• 停机位分配
• 机场
• 图论
• 顶点着色
• 算法

给出了停机位分配问题顶点着色模型及其分解算法.通过改良一种时间冲突算法,构建了航班使用停机位的时间冲突集合.以"先到先服务"原则为基础,把停机位分配问题转化为顶点着色问题,并建立了相应模型.利用笔者独创的分解算法,停机位的作业能力可得到改善.算法的计算复杂度为O(n2).该算法的特点在于:1)将顶点、颜色划分为若干个不同等级的集合;2)将顶点按照所属集合的等级、度进行分解,得到顶点的分解序列.在用一种颜色ck(1≤k≤K;K是可用颜色数)给顶点着色时,优先给这样一个顶点着色:该顶点能被着ck色,且其分解序列号最大.最后将该算法应用于一个算例,得到了最优解.

• 出版日期2007-11-15
• 单位中南大学; 广州大学