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

2007年11月 系统工程理论与实践 第1l期 文章编号：1000．6788(2007)11-0148—05 停机位分配问题的顶点着色模型及算法 罗荣武1，谢如鹤2，张得志1 (1．中南大学交通运输工程学院，长抄410075；2广州大学商学院，广州510006) 摘要：给出了停机位分配问题顶点着色梗型及其分解算法．通过改良一种时间冲突算法．构建了航班 使用停机位的时同冲突集合．以“先到先服务”原则为基础，把停机位分配问题转化为顶点着色问题，并 建立了相应模型利用笔者独创的分解算法，停机位的作业能力可得到改善．算法的计算复杂度为O (n2)．该算法的特点在于：1)将顶点、颜色划分为若干个不同等级的集合；2)将顶点按照所属集台的等 级、度进行分解，得到硬点的分解序列。在用一种颜色屯(1≤^≤K；式是可用颜色数)给顶点着色时，优 先给这样一个顶点着色：该顶点能被着c。色，且其分解序列号最大．最后将该算法应用于一个算倒，得 到了最优解． 关键词：停机位分配；机场；图论；顶点着色；算法 中国分类号：V351．11：U291．3 文献标志码：A Vertex Modeland ofGate Coloring AlgorithmAssignment LUO Ru—he2，ZHANGDe．zhil Rong．wul，XIE of (1．SchoolTraffic＆TransportationEngineedng，cen耐SouthUniversity，Changsha410075，China；2．BusinessSchool，Guangzhou University，Guangzhou510006，China) Abstract：Vertexmodeland of is n coloring decomposingalgorilhmgate∞iFLmemproblemoⅡe删．Byimproving oftime setofthetimeconnjctofthe Olithe“firstinfirst algorithmconflict．the scheduledmght^面coT哦呲ted．Based istransferredto and modelis assignment vertex-coloringproblemtcorresponding out’principle．gateproblem constructed authors’innovative is to also．Byutilizing decomposealgorithm，itpoⅢfibleimpmvegates’operation andthe O(矿)．The蜘i血Ⅲ’5characteristici6thatI)itdivides ability algorithm’9computationalcomplexityis are verticesandcolorsintodifferentlevels’船b．and2)ve而ce8decomposedtothesetlevelthat