基于多目标分阶段的跑道调度计划算法-计算机应用研究.PDF

第２９卷第４期 计 算 机 应 用 研 究 Ｖｏｌ．２９Ｎｏ．４ ２０１２年４月　 ＡｐｐｌｉｃａｔｉｏｎＲｅｓｅａｒｃｈｏｆＣｏｍｐｕｔｅｒｓ Ａｐｒ．２０１２ 基于多目标分阶段的跑道调度计划算法 刘期建，何元清 （中国民航飞行学院计算机学院，四川 广汉６１８３０７） 摘　要：针对多条跑道环境下离港飞机调度问题，提出了一种基于多目标、两阶段算法。算法第一阶段以飞机 重量类型为主要分解参数，生成离港飞机序列。该参数在跑道调度计划问题上比其他参数更具影响力和稳定 性。算法第二阶段从离港飞机队列池中选取可用序列，将特殊航班指配到目标类型序列中，生成优化的飞行航 班时刻表。实验表明，采用两阶段跑道调度计划算法进行多跑道离港飞机调度比采用先来先服务算法调度在跑 道总吞吐量上有明显改善，能有效降低机场航班延误，提高跑道运营效率。 关键词：跑道调度计划；多目标；两阶段算法；重量类型序列；离港优化 中图分类号：ＴＰ３０１　　　文献标志码：Ａ　　　文章编号：１００１３６９５（２０１２）０４１２６７０３ ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１３６９５．２０１２．０４．０１８ Ｍｕｌｔｉｏｂｊｅｃｔｉｖｅａｎｄｄｅｃｏｍｐｏｓｉｔｉｏｎｂａｓｅｄｏｐｔｉｍｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍｆｏｒ ｒｕｎｗａｙｏｐｅｒａｔｉｏｎｓｐｌａｎｎｉｎｇ ＬＩＵＱｉｊｉａｎ，ＨＥＹｕａｎｑｉｎｇ （ＣｏｌｌｅｇｅｏｆＣｏｍｐｕｔｅｒ，ＣｉｖｉｌＡｖｉａｔｉｏｎＦｌｉｇｈｔＵｎｉｖｅｒｓｉｔｙｏｆＣｈｉｎａ，ＧｕａｎｇｈａｎＳｉｃｈｕａｎ６１８３０７，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｉｓｐａｐｅｒｐｒｏｐｏｓｅｄａｍｕｌｔｉｏｂｊｅｃｔｉｖｅａｎｄｔｗｏｓｔａｇｅｂａｓｅｄａｌｇｏｒｉｔｈｍｔｏｓｏｌｖｅｔｈｅｄｅｐａｒｔｕｒｅｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍｏｆ ｍｕｌｔｉｒｕｎｗａｙｓｉｔｕａｔｉｏｎ．Ｉｎｔｈｅｆｉｒｓｔｓｔａｇｅ，ｇｅｎｅｒａｔｅｄａｎｄｒａｎｋｅｄｓｅｑｕｅｎｃｅｓｏｆｄｅｐａｒｔｕｒｅａｉｒｃｒａｆｔｓｂｙｗｅｉｇｈｔｃｌａｓｓ，ｗｈｉｃｈｗａｓａｐｒｉ ｍａｒｙｄｅｃｏｍｐｏｓｅｄｐａｒａｍｅｔｅｒ．Ｉｔｗａｓｍｏｒｅｄｏｍｉｎａｎｔａｎｄｓｔａｂｉｌｉｚｅｄａｓｆｏｒｔｈｅｒｕｎｗａｙｏｐｅｒａｔｉｏｎｓｐｌａｎｎｉｎｇｔｈａｎｏｔｈｅｒｐａｒａｍｅｔｅｒｓ．Ｉｎ ｔｈｅｓｅｃｏｎｄｓｔａｇｅ，ｐｏｐｕｌａｔｅｄｔｈｅｔａｒｇｅｔｃｌａｓｓｓｅｑｕｅｎｃｅｓｗｉｔｈｓｐｅｃｉｆｉｃｆｌｉｇｈｔｓｆｒｏｍｔｈｅｐｏｏｌｏｆａｖａｉｌａｂｌｅａｉｒｃｒａｆｔｓｔｏｇｅｎｅｒａｔｅｏｐｔｉ ｍｉｚｅｄａｉｒｃｒａｆｔｓｃｈｅｄｕｌｅｓ．Ｔｈｅｅｘｐｅｒｉｍｅｎｔｓｈｏｗｓｔｈａｔｔｈｅｎｅｗａｌｇｏｒｉｔｈｍｉｓｍｏｒｅｅｆｆｅｃｔｉｖｅｉｎｔｈｅｔｏｔａｌｔｈｒｏｕｇｈｐｕｔｔｈａｎｔｈｅａｌｇｏｒｉｔｈｍ ｏｆｆｉｒｓｔｃｏｍｅｆｉｒｓｔｓｅｒｖｅ．Ｉｔｃａｎｒｅｄｕｃｅｔｈｅａｉｒｐｌａｎｅｄｅｌａｙｓａｔｔｈｅａｉｒｐｏｒｔａｎｄｉｍｐｒｏｖｅｔｈｅｅｆｆｉｃｉｅｎｃｙｏｆｒｕｎｗａｙｏｐｅｒａｔｉｏｎｓ． Ｋｅｙｗｏｒｄｓ：ｒｕｎｗａｙｏｐｅｒａｔｉｏｎｓｐｌａｎｎｉｎｇ；ｍｕｌｔｉｏｂｊｅｃｔｉｖｅ；ｔｗｏｓｔａｇｅａｌｇｏｒｉｔｈｍ；ｗｅｉｇｈｔｃｌａｓｓｓｅｑｕｅｎｃｅｓ；ｄｅｐａｒｔｕｒｅ ｏｐｔｉｍｉｚａｔｉｏｎ 　　跑道调度计划（ｒｕｎｗａｙｏｐｅｒａｔｉｏｎｓｐｌａｎｎｉｎｇ，ＲＯＰ）是指在给 队模型，以便提供更多细节来评估起飞调度计划的有效性。 ［７］采用的启发式算法实际上是一种针对着陆间隔放行 定的时间段内，针对多条跑道上飞机起飞、着陆和