航空公司飞机排班问题模型及算法研究

《航空公司飞机排班问题模型及算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、西南交通大学博士学位论文航空公司飞机排班问题：模型及算法研究姓名：孙宏申请学位级别：博士专业：交通运输规划与管理指导教师：杜文20030530西南交通火学博士研究擞学位论文第i页摘要航空公司的生产计划编制怒一项非常艰巨丽重要的工作，其实质在于通过爨爨瓣缓织窝精确葭计划，实凝各生产资溪要素赘优亿聚菱，它兹溪量窝效率关系到生产遮麓的安全、正常和效益。本文在深入分析当前国内各航空公司，土产计划工作现状的基础J二，选择了1{I机排班计划作为研究课题，通过系统分撰飞礁捧爨工终熬滚程秘要求，提嵩了接述飞枧蓑}班闽题懿数学模型。由于该问题是多目标、菲线

2、性的，因此寻找一种统一的能够适应各种具体要求，并且满足工程应用需爱的多项式算法存在理论上和技术上的困难。为此论文在借鉴手：：：E编制摊班计划经验的基硪上，将一个具体的飞枧摊班闻题，归结为三静典黧群班模式中的～秘，酃：基于飞祝调度指令要求的擗班问题，基于飞机使用均衡要求的排班问题和基于最少需用飞机数的排班问题，对于每种典型的飞机排班模式，在对次要的约束条件进行箍化、松驰的董愁t构造出辕应静麓够潇跫z程应雳要求敬扁发式算法，著分析了簿法的复杂性。该项研究为研制飞机排班决策支持系统软件奠定了理论基础。论文的主要创新工作在于：l+投摆当瓣强肉蕊空

3、公司瓣运营蓬织竣式特点，戮及飞祝蓑}斑i￡{睾豹实际需求，提出了描述飞机排班问题的数学模型，并通过将一·般形式的飞机排班问题归结为三种典型的飞机排班模式，构造出相应的启发式算法，填补了国内在此领域的磷究空白。2·在解决基予飞机调度指令要求的飞机排班阉题时，本文提出的分阶段指派算法较好地克服了标号算法的缺陷，该算法能普遍地应用于处理类似的固定工件排序问题。3-在解决菠飞祝均衡爱穗的飞季晁簿爨闻楚时，奉文利用航班节的网络模型将原问题转化为一个使目标函数最小的航班节编组问题，在此基础上构造了～个模拟退火算法。4．在解决最少震雳飞橇数要求的飞瓿骛

4、瑷阀题时，本文将寻找救班节衔接方案问题，描述成～个二：部蹦的匹配问题，进而通过解两个二部图的最————————————————————————————————————————————————————————————————一一一西南交通大学博士研究生学位论文第ii页小权最大匹配，寻找需用飞机数最少的飞机调度方案。关键词：飞机排班问题，航班节，启发式算法，航班节网络模型，算法复杂性西南交通大学博士研究生学位论文第iii页ABSTRACTAirlineoperationalplanningisveryhardandimportantwork，

5、whichqualityandefficiencyisconcernedwiththesafetyandbenefitofairlineoperation．Theessenceofthisworkisoptimizingtheconfigurationofprimaryairlineresourcesbypreciseorganizingandplanning，Basedonanalyzingthestatusofdomesticairlineoperationalplanningsystem，thisdissertationdeterm

6、inesthestudysub3ectasTail—Number—Assignment(TNA)Problem．Firstly，a0-1IntegerprogrammingmathematicalmodelisconstructedtodescribeTail—Number—Assigningworkhappenedindomesticairline，sincetheproblemisNPC，aunifiedpolynomialalgorithmwhichsatisfiesengineeringrequirementisunavailab

7、le．Illuminatedbythepracticalexperience，aspecificTNAproblemisclassifiedintooneofthreetypicalTNAmodes：TNAbased0nfleetdispatchingcommands，TNAbasedonfleetbalanceapplication，TNAbasedonminimumfleetrequirement；Secondly，bysimplifyingandrelaxingsomeminorconstraints，correspondingma

8、thematicalmodelsandheuristicalgorithmsarereconstructedforeachtypicalTNAmode；Finally，computingcom