基于协同多任务分配的飞机排班模型与算法

《基于协同多任务分配的飞机排班模型与算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、航空学报ActaAeronauticaetAstrOnauticaSinicaDec．252011V01．32No．122293．2302ISSN1000．6893CN11．1929／Vhttp：Hhkxb．buaa．edu．cnhkxb@buaa．edu．cn文章编号：1000一6893(2011)12—2293—10基于协同多任务分配的飞机排班模型与算法周琨，夏洪山*南京航空航天大学民航学院，江苏南京210016摘要：航空公司的航班运行一直存在安全与成本的矛盾：既要严格按规定完成飞机例行检修，优先保障运行安全，又要尽可能提高飞机El利用

2、率，以降低运行成本。为此，研究基于协同多任务分配的飞机排班问题。分析例行检修约束，建立最优化飞机El利用率的数学模型，运用分枝定价算法进行求解。分枝定价算法引入检修节点和虚拟飞机节点的定义，将分配的航班飞行任务和例行检修任务表示为飞机路径，通过迭代求解由部分飞机路径构成的限制主问题，以及寻找飞机路径以改进目标值的定价问题，获得线性松弛问题的最优解；基于最先失败原则选择路径变量，采用路径分枝策略划分解空间，从而删除分数解、生成飞机排班计划。实验结果表明，该方法能够有效求解飞机排班问题。关键词：空中交通管制；排班；多任务分配；分枝定价算法；列生

3、成；约束满足中图分类号：V355．2文献标识码：A航空公司飞机排班需要根据航班计划要求、飞机技术特征与技术状态等诸多因素，为每一架飞机分配每天的航班飞行任务和必要的例行检修任务，以保证航班计划顺利执行。这种安排。首先必须考虑安全因素，能够在规定的检修间隔时间内完成例行检修任务；其次，在确保运行安全的基础上需要考虑成本因素，能够以较高的飞机日利用率完成航班飞行任务。因此，合理进行飞机排班，对保障航班运行安全、降低航班运行成本有着决定性作用，因而倍受业界广泛关注。飞机排班可以根据约束条件分为两类问题：一是飞机检修路径问题(AircraftRou

4、tingProb-lem，ARP)，二是飞机任务指派问题(TailAs—signmentProblem，TAP)。ARP主要研究如何生成飞机检修路径，使得飞机每3天或4天至少有一次在检修基地过夜，以便执行例行检修，即满足“3／4天检修规则”。关于ARP，国内外学者探讨了多种求解方法：文献[1]和文献[2]建立LOF(Lines—of-Flight)有向图，将飞机检修路径视为欧拉圈，分别设计多项式时间算法，生成满足“3天检修规则”和“4天检修规则”的路径。文献[3]将ARP归结为带有边约束的旅行商问题，运用拉格朗日松弛算法求解。文献[4]采用

5、多商品流问题的数学模型描述ARP，并设计了启发式解法。文献[5]以3天内飞机检修机会最大化为目标函数，建立基于航班环的数学模型，使用列生成算法求解。文献[6]将ARP求解方法归结为基于strings模型、bigcycle模型和one-dayroute模型进行求解。但ARP未考虑飞机技术特征约束(Ta订Constraints)，存在分配的航班飞行任务与飞机技术特征相冲突的情况[718]。而TAP为每架飞机指派满足检修约束的航班飞行任务，并要求飞机执飞航班时必须满足相应技术特征的约束条收稿日期：2011-05-16；退修日期：2011．06-1

6、4；录用日期：2011-07—21；网络出版时间：20”-08-1517：16网络出版地址：WWW．cnki．net／kcms／detail／111929．V．20110815．1716．003．htmIDOI：CNKI：11-1929／V．201108151716003基金项目：国家软科学研究计划(2008GXQ6814”*通讯作者．Tel．：025—84891165E-mail：xhsca@nuaa．edu．0"1葶l用撂式l周琨．夏洪山．善于协同多任务分配的飞机撵班模型与算法￡J]．航空学报．20¨．32(12)：2293-2302Z

7、houKun．XiaHongshan．Optimizationmodelandalgorithmforaircraftschedulingproblembasedoncooperativemulti-taskassignment[7JJ．ActaAeronauticaetAstronauticaSinica．2011．32(12)：2293—2302．航空学报Dec．252011VoI．32No．12件。此类研究主要有：文献[7]～文献[9]采用列生成算法求解TAP，并利用约束满足技术改善算法性能；文献[10]运用约束满足技术求解了该问题；

8、文献[11]将其分解为基于飞机调度指令、满足飞机使用均衡要求和最少需用飞机数的子问题，分别给出求解算法。但上述研究均未考虑飞机技术状态因素，使得无法依据飞机的实际技术状态，充分利