论文部分内容阅读
给出了停机位分配问题顶点着色模型及其分解算法.通过改良一种时间冲突算法,构建了航班使用停机位的时间冲突集合.以“先到先服务”原则为基础,把停机位分配问题转化为顶点着色问题,并建立了相应模型.利用笔者独创的分解算法,停机位的作业能力可得到改善.算法的计算复杂度为O(n2).该算法的特点在于:1)将顶点、颜色划分为若干个不同等级的集合;2)将顶点按照所属集合的等级、度进行分解,得到顶点的分解序列.在用一种颜色ck(1≤k≤K;K是可用颜色数)给顶点着色时,优先给这样一个顶点着色:该顶点能被着ck色,且其分解序列号最大.最后将该算法应用于一个算例,得到了最优解.
The vertex shading model of parking lot allocation and its decomposition algorithm are given.The time conflict set of flight parking lot is constructed by improving a time conflict algorithm.According to the principle of first arrival first service, The assignment problem is transformed into the vertex coloring problem, and the corresponding model is established.Using the author’s original decomposition algorithm, the working ability of the parking lot can be improved.The computational complexity of the algorithm is O (n2) .The algorithm is characterized by: 1) Vertex, color is divided into a number of different levels of collection; 2) The vertices in accordance with their level of aggregation, degree decomposition, get the decomposition of the vertex sequence in a color ck (1 ≤ k ≤ K; K is the number of available colors ) To color a vertex, give priority to a vertex coloring: the vertex can be ck color, and the decomposition of the largest serial number. Finally, the algorithm is applied to an example, the optimal solution.