| 停机位分配问题的顶点着色模型及算法 |
| |
| 引用本文： | 罗荣武,谢如鹤,张得志.停机位分配问题的顶点着色模型及算法[J].系统工程理论与实践,2007,27(11):148-152. |
| |
| 作者姓名： | 罗荣武 谢如鹤 张得志 |
| |
| 作者单位： | 1. 中南大学,交通运输工程学院,长沙,410075
2. 广州大学,商学院,广州,510006 |
| |
| 摘 要： | 给出了停机位分配问题顶点着色模型及其分解算法.通过改良一种时间冲突算法,构建了航班使用停机位的时间冲突集合.以"先到先服务"原则为基础,把停机位分配问题转化为顶点着色问题,并建立了相应模型.利用笔者独创的分解算法,停机位的作业能力可得到改善.算法的计算复杂度为O(n2).该算法的特点在于:1)将顶点、颜色划分为若干个不同等级的集合;2)将顶点按照所属集合的等级、度进行分解,得到顶点的分解序列.在用一种颜色ck(1≤k≤K;K是可用颜色数)给顶点着色时,优先给这样一个顶点着色:该顶点能被着ck色,且其分解序列号最大.最后将该算法应用于一个算例,得到了最优解.
|
| 关 键 词： | 停机位分配 机场 图论 顶点着色 算法 |
| 文章编号： | 1000-6788(2007)11-0148-05 |
| 修稿时间： | 2006年3月28日 |
Vertex Coloring Model and Algorithm of Gate Assignment |
| |
| LUO Rong-wu,XIE Ru-he,ZHANG De-zhi.Vertex Coloring Model and Algorithm of Gate Assignment[J].Systems Engineering —Theory & Practice,2007,27(11):148-152. |
| |
| Authors: | LUO Rong-wu XIE Ru-he ZHANG De-zhi |
| |
| Abstract: | |
| |
| Keywords: | gate assignment airport graph theory vertex coloring algorithms |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《系统工程理论与实践》浏览原始摘要信息 |
| 点击此处可从《系统工程理论与实践》下载免费的PDF全文 |
|
