吕宗磊，王 舳

(1.中国民航大学 计算机科学与技术学院，天津 300300；2.中国民航大学 中国民航信息技术科研基地，天津 300300)

0 引 言

飞机排班是依据一定业务规则为飞机分配航班任务的过程，是航空公司运输活动开展的核心。在建模方面，旅行商问题模型、多商品网络流模型[1,2]、整数规划[3]、0-1整数规划模型、时空网络模型[4]等都可以作为飞机排班问题的基础模型，M Lindner等[5]考虑飞机老化对燃油消耗的影响拟定航班计划，最大限度降低运营成本。在求解策略方面，朱星辉等[1]采用了列生成法对飞机排班模型进行求解。针对飞机使用均衡的飞机排班问题，范永俊等[6]提出了基于分支定界法的求解方案，刘婧、贾宝惠[7]用启发式构造可行的解决方案，D’Ariano A等[8]尝试使用调度规则、启发式算法和分支定界法进行问题的求解并且进行了对比。文献[9]尝试使用贪婪随机自适应搜索过程生成新的邻域解以解决不正常航班的恢复问题。它将飞机的执行过程当作一个整体，将飞机的独立延误时间看作正态分布进行正常性的计算，做出了一些探索性的尝试。但实际上，航班的飞行时间很难准确表示成典型性分布。

现有的研究主要以成本、收益、飞机利用率等作为优化目标，航班正常性是民航局关注的焦点问题之一，现有的研究很少着眼于这个方面。考虑加入到飞机执行航班的过程中，由同一架飞机执行的航班，前序航班的延误影响到后续航班的运行，所以面向正常性的飞机排班较之其它目标更为复杂。……