基于受限位移约束的蚁群算法在航班着陆调度问题中的应用研究.pdfVIP

管 理 工 程 学 报 Vr01．30．No．1 JonrnalofIndustrial 2016年第1期 Engineering／EngineeringManagement 基于受限位移约束的蚁群算法在航班着陆调度 问题中的应用研究 马卫民1，一，杨文娟1，徐博2 (1．西安工业大学经济管理学院，陕西西安710021：2．同济大学经济与管理学院，上海200092) 摘要：航班着陆调度问题是机场跑道调度中的重要问题，合理的调度策略将极大的减少航班延误。本文提出 基于受限位移约束的蚁群算,：L-(CPS．AC)，该算法利用了蚁群算法高效的全局有哪些信誉好的足球投注网站能力，同时结合CPS确保调度 的可操作性和公平性，能够为实际的空中交通流量管理提供理论方法和依据。数值模拟实验结果表明，CPS．AC 算法明显优于经典的先到先服务(FCFS)boi,罔度方法和标准的蚁群算法(AC)，能在较短时间内有效减少着陆航班的 总延迟时间，且具有较好的收敛性。这些对于减少航班延误，提高着陆容量具有推动作用。 关键词：受限位移约束(CPS)：蚁群算法；航班着陆调度 中图分类号：V351．11文献标识码：A 文章编号：1004．6062(2016)01—0191．06 DoI：10．13587巧．cnki．jieem．2016．01．024 0引言 领域，如单机调度问题、车辆调度等。Randall第一次将蚁群 近年来，随着我国民航产业的迅速发展，空域拥堵问题 算法应用于跑道调度问题“…。随后Bencheikh等多次利用蚁 也越来越严重，由此引起的航班延误问题不仅给航空公司造 群算法去生成最初的解来处理单跑道和多跑道的调度问题 成巨大的经济损失，而且严重威胁到机场及空域的安全。合 Horizon “6’1“。Zhan等结合滚动时域控制原理(Receding 理调度到达航班对于保障飞行安全、降低延误损失以及提高 Contr01)对机场实时跑道调度问题进行了研究“…。在国内，胡 顾客满意度等具有重大意义。 祥培等”刖对蚁群算法的相关领域进行了评述。此外，许多学 传统的对到达航班流的调度方式通常采用先到先服务 者也将蚁群算法应用到航班着陆调度问题中。”…。 (FCFS)策略。它基于管制员的工作经验，在满足各种限制条 本文结合上述的受限位移约束和蚁群算法，提出基于受 件下按照先到先下降的策略为到达航班制定着陆次序和着 限位移约束的蚁群算法(CPS．AC)来解决航班着陆调度问题。 陆时间，使队列中航班的总延误时间最小。在交通繁忙时， 这样一方面利用蚁群算法强大的全局有哪些信誉好的足球投注网站能力，另一方面结 FCFS策略往往导致跑道利用效率低下，空中滞留航班过多合CPS确保了调度的可操作性和公平性，能够较好的应用于 而危及飞行安全。为解决这些问题，国内外学者提出了许多 实际的交通管理系统中。更重要的是，蚁群算法结合CPS进 优化方法“。51。 行研究，可以弥补以往对CPS研究的不足。这是因为，用经 比较突出的两种方法是受限位移约束(CPS)和蚁群算典的动态规划方法求解CPS模型，只能解决当飞机的最大受 法。Dear等人首次提出受限位移约束的思想”3，即在调度时，限位移k较小时的情形。随着求解问题的规模的增大(飞机 相对于飞机初始在FCFS中的位置，只允许其向前或者向后允许前后移动的最大位置k变大)，动态规划方法求解的算 移动k个位置(k为最大受限位移)。这一做法可以大大缩小法复杂度将呈指数增加“…，从而不能得到一个较好的解。而 有哪些信誉好的足球投注网站空间，同时使可操作性更强。随后大量的学者在CPS的 CPS．AC算法能够在这种情况下给出一个不错的可行解，从 框架下设计新的算法”。1…。其中，必威体育精装版的研究成果是 而拓展了经典CPS模型的求解适用范围。