航班环上的飞机尾号分配问题

《航班环上的飞机尾号分配问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、航班环上的飞机尾号分配问题刘山，郝立东，张林玲，曹盛文(中国民航大学计算机科学与技术学院，天津300300摘要：飞机尾号分配问题是航空公司生产运营过程中一项重要工作，其结果直接影响到航空公司的运营成本和飞行安全等，首先以飞机维修机会最大为目标建立了航班环生成模型，利用列生成算法和Flo)7d最短路算法的结合生成了满足3天维修计划的多维修基地航班环；其次．利用分支定界算法得到了航班环生成模型的0一l最优解；再次．采用KM算法完成了飞机与航班环的完美匹配，实现了航班环的动态分配；最后，通过对一个算例的分析．验证了所提出方法的正确性和有效性关键词：航班

2、环；列生成算法；Flov(j算法；KM完美匹配中图分类号：F560文献标志码：A文章编号：1674—5590(2013)02—0057—06Tailassignmentproblembasedonnight—loopLlbSh帆．HAoLi—dong，ZHA^GLin—liIlg，CAOSheng—u’en(国!如ge够白mP“艇r5fr搪ncP＆nc是删抽签’，CA(，C，死Ⅲ巧in3003∞．C坛m1Abstract：Tailassi冀【lnlentislhebasi(·workintheairline111anufacturillgoper

3、atjon8process．butitfjirectlyinlPa(‘tstheroslsoftheairline(’pera【ingan(1thesafotyofni苎11【．InthjsartIcle，nrstly，wefi)u11({lheintegPrpro芒fdnlIllillgnlodel(】ffljght—l()《’I)cI)11stnJcfionainlingf(】ITla、jmunllhemaintPnan(’Pf’ppt)r【unityandnla(1Pu，tII)ffhectJmbi¨a“(1n()fthe(、()lunln

4、gellerati()nandF】oydshones【patha】go“thnltogPneratPlhenighl一100I)()fnlullj—nlainfPnanrPhasp．SPPondly，wPl】sP(1programbyMatlabofbranch—an(1一h(1un(】loohlain0一ltlptimalsoIutionof1)mgrammmgmodel．T

5、1en，ad01)1P({theKMajgorithmt1)(、onlI、1eteI}1Pperfetltnlaf【’hof1heairrraftan(1night一10

6、0pandrealizeflthe(iynanlicall()(．ation1)fthenight一100p．Finallj．Ihr(1ughanalyseofanjnsIanrewe、‘alidaledthe(‘on’P(tnP，sandeffjciencvofthenleth‘】<1．Keywor{量s：night—loop；(‘olumngener乱itmalgo^thm；F1‘Ⅳlalgo“thm；KM1)erfet’im8{(。h飞机尾号分配问题是航空公司在生产计划方面的重要课题，也是航空公司运行控制中的主要内容之一：进行尾号分配时，不

7、仅要考虑航班计划，还要考虑飞机的维修要求：现有的维修汁划优化手段都是打乱现有的计划航班，这会对航空公司的市场需求造成影响。如何在不改变计划航班的前提下，进行公司航线网络的维修计划优化是亟待解决的问题：在国外，飞机尾号分配问题一直是一个热点问题。在这方面的研究工作有：Gopalan．R⋯通过构造航班维护路径图，并在其上寻找EulerTou，·的方法建立了一种解决3天维修路径问题的多项式算法：Nikolaos㈦提出了一个飞机航线整合模型，运用Benders分解算法使模型的规模减小了，达到_厂减小航线费用的目的二samiGabfen一采用混合列生成和限

8、制规划算法对飞机尾号排班模型进行求解二在国内主要研究有：肖东喜和朱金福提{}{了单维修基地航班环动态构建的方法㈩=孙宏等人提出了捕述单枢纽航线结构下飞机排班问题的数学模型，将一个具体的飞机排班问题归结为基于飞机调度指令要求的排班问题、基于最少需用飞机数的排班问题和基于飞机使用均衡要求的排班问题三种典型排班模式中的一种，针对基于飞机调度指令要求的排班问题提J【}{了标号算法和分阶段指派算法弼；对于最少需用飞机数的排班问题将寻我航班节衔接方案转化为一个二部图的匹配问题㈣；对于飞机使用均衡要求的排班问题，通过航班节网络模型将原问题转化为航班节编组问题，

9、构造了模拟退火算收稿日期：2012一06一lO；修回日期：2012—07一ll作者简介：刘IjI(1955一)。男、天津人、教授．号I基