基于优先级的进离港航班排序优化问题研究.docx

? ? 基于优先级的进离港航班排序优化问题研究 ? ? 　　0 引言 　　近年来，随着我国民航产业的迅速发展，空中交通流量显著增加，由此引起的机场终端区的拥堵现象日益严重。这不仅导致许多繁忙机场的跑道利用率低下，而且给航空公司带来的巨大的延误损失。因此，对终端区到达和起飞航班进行合理的调度已成为当前亟待解决的问题。传统的对于进离港航班的排序多采用先到先服务方法（FCFS），也就是管制员按照航班的预计降落或起飞时间安排其先后顺序。FCFS方法虽简单易行，但在机场繁忙时极易造成大量飞机的延误，降低空域利用率。为解决该问题，国内外学者提出了许多优化方法，但大多数针对分离的着陆队列排序问题[1-3]或起飞队列排序问题[4-6]。为进一步提高跑道利用率，近年来越来越多的机场采用混合起降跑道，即跑道的两端均可以起飞或降落，但关于混合起降飞机排序问题的研究成果则相对较少。在国外，Al-Salem等将多跑道混合起降飞机排序问题与非对称旅行商问题进行对比，提出求解该问题的混合整数规划[7]。Ghoniem等建立关于该问题的加强型模型，并用分支定界算法求解[8]。Hancerliogullar提出贪婪算法和启发式算法来求解该问题[9]。在国内，也有一些学者对终端区进离港航班排序问题进行了研究[10-12]。然而上述大多数研究均没有考虑到在进离港航班排序问题中，不同运行方式、不同飞机类型以及不同重要程度的航班所带来的延误损失是不同的，也就是说未能考虑到各航班在调度中不同的优先性。 　　鉴于上述分析，本文根据各航班不同的运行方式、飞机种类以及是否为连续航程航班设计三维优先级表，并将优先级转化为各架飞机的延误成本系数。此外，设置允许延误的航班架次约束、邻边约束以及限制位置约束来减轻管制人员的工作负荷。提出改进蚁群算法（GJAC）求解该问题，并通过最后的仿真实验验证所提算法能够在考虑航班不同的优先级以及上述约束条件下有效减少进离港队列的总延误成本，从而为现实空中交通流量管理提供一定的理论依据。 　　1 进离港航班排序优化模型 　　1.1 模型描述 　　进离港航班排序优化问题是指对于给定的进离港队列以及预计降落或起飞时间，如何排序使整个队列的总延误成本最小。具体来说，对于等待起飞或降落的n架航班，按预计到达或起飞时间的先后顺序分别记为航班1，2，…，n，且航班i的预计降落或起飞时间为。假设调度后的队列为ω，ω（i），为队列中的第i架航班，为航班ω（i）的调度后降落或起飞时间。考虑到混合起降队列中任三架航班之间不一定满足三角不等式关系，具体见2.2.1，本文参考文献[8]按如下公式计算各架航班的调度后降落或起飞时间。 　　 　　1.2 约束条件 　　1.2.1 最小时间间隔约束 　　在终端区进离港航班排序问题中，应该满足的最重要的约束即为安全约束，也就是最小时间间隔约束，见表1。在分离的着陆航班排序问题或起飞航班排序问题中，任三架航班的最小时间间隔满足三角不等式约束，因此每架航班只需保证与其紧前航班满足最小时间间隔约束。对于混合起降队列，若任连续的三架航班的运行方式不同，即这三架航班中既有降落航班又有起飞航班，则不一定满足三角不等式。因此，为保证最小时间间隔约束，本文对于每架航班的降落或起飞时间的计算，均考虑与其紧前的三架航班的最小时间间隔。 　　 　　1.2.2 最大允许延迟时间约束 　　最大允许延迟时间，即每架航班的延误时间要控制在一定的范围内。为实现该约束，为每架航班设定最晚起飞或降落时间LT，即对于航班i，有 　　 　　1.2.3 最大偏移位置约束和邻边约束 　　最大偏移位置约束，为保证调度的公平性，令每架航班在调度时相对于其初始位置最多只能偏移k个位置。本文取k=2。 　　此外，对于相邻的两架航班i和j（i在前），若其预计时间之差与最小时间间隔相差较小，即，其中δ为以较小的常数。邻边约束即为对于如上预计时间之差与最小时间间隔相差较小的两架相邻航班应尽量保持该两架航班的顺序，即将航班j直接安排在航班i之后。最大偏移位置约束和邻边约束均能够在一定程度上减少管制人员的工作负荷。 　　1.2.4 允许延误航班的架次约束 　　为减轻管制人员的工作负荷，本文考虑添加允许延误航班的架次约束。也就是说，确保一部分的航班按照其预计降落或起飞时间降落。具体的实现过程见第3章的改进蚁群算法描述。 　　1.3 优先级表的设计 　　基于优先级的调度方法更多的应用于各种实时调度系统中，其主要调度规则为：根据各任务的特征参数（如任务重要程度和截止期），计算其优先级指数，并且优先级指数越高，安排越早。在此，本文将基于优先级的调度规则引入静态的进离港航班排序问题中。参考文献[13]，对于每架航班考虑3个特征参数，即航程是否连续，运行方式（起飞或降落）以及飞机类型来设计三维优