基于图着色模型飞机智能化排班算法的研究

飞机排班问题关系到航空公司的系统运作,作用十分重要。通过对飞机排班问题的分析,把飞机分配问题转化为图着色,应用图着色理论,建立了飞机分配问题的图着色模型,引入时间片算法确定了航班使用飞机的时间冲突集合,根据"先到先服务"的原则给出了飞机分配的顶点序列着色算法。用一个具体的算例,验证了飞机智能化排班比现有航空公司调度员人工排班更先进、更实用、更加节省资源,使资源配置更加合理。

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

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

机场停机位分配问题的图着色模型及其算法

停机位分配作业关系到整个机场的系统运作,其作用相当重要。通过对停机位分配的分析,把停机位的分配转化为图着色,建立停机位分配问题的图着色模型,并引入时间片算法确定航班使用机位的时间冲突集合,根据"先到先服务"的原则给出了停机位分配的顶点序列着色算法,该算法的计算复杂性为O(n2k2),最后将该算法应用于一个算例。