基于并行GRASP的不正常航班调度算法

《基于并行GRASP的不正常航班调度算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第25卷第5期2016年10月运筹与管理0PERATl0NSRESEARCHANDMANAGEMENTSCIENCEV01．25，No．5Oct．2016基于并行GRASP的不正常航班调度算法张力菠，鲍和映(南京航空航天大学经济与管理学院，江苏南京211106)摘要：将并行计算与GRASP结合，设计了一种新的基于并行GRASP的不正常航班调度算法，给出了详细的算法流程与步骤；同时考虑了使用备用飞机、延误航班与取消航班等不正常航班调度策略，通过并行GRASP算法优化了构造的飞机路线和取消路线组成的初始解，给出了每架飞机新的

2、航班路线和航班取消路线。国内一家中等规模航空公司实际算例的结果证明了算法能有效降低以往算法的时间复杂度，明显提升运算效率，可用于较大规模的不正常航班调度运算。关键词：服务运营计划；并行贪婪随机自适应搜索算法；不正常航班；调度中图分类号：N945．15文章标识码：A文章编号：1007—3221(2016)05-0196-10doi：10．12005／orms．2016．0182IrregularFlightSchedulingAlgorithmBasedonParallelGRASPZHANGLi—bo，BAOHe-yin

3、g(InstituteofEconomics&Management，Na彬ngUniversityofAeronautics&Astronautics，Nanjing211106，China)Abstract：Inordertoimprovetheefficiencyofalgorithmsfordisruptedairlineschedulesandreducethetimecomplexityofthosealgorithms，thispaperintroducesparallelcomputingandGRASP(

4、GreedyRandomizedAdap—tiveSearchProcedure)intooptimizationofirregularflightscheduling．AnewirregularflightschedulingalgorithmbasedonparallelGRASPisproposed，whichconsiderssuchaschedulingpolicyasspareplanes，delayingflightsandcancellingflights．Theinitialsolutionconstr

5、uctedforirregularflightbyflightcancellationsandflightdelaysisoptimizedbytheparallelGRASPalgorithm，andthenewflightrouteandrouteofflightcancellationsofeachplaneispresentedinthispaper．Anexampleofamediumscaleairlinesflightplanisgiventodemonstratethevalidityandfeasibi

6、lityoftheschedulingalgorithm．TheresultsshowthatthenewalgorithmissignificantlyhigherandmoreefficientinsolutiontimethanserialGRASPalgorithmandcanalsosolvealarge．scaleirregularflightproblemeffectively．Keywords：serviceoperationsscheduling；parallelGRASP；irregularfligh

7、t；flightscheduling0引言由于天气、机械故障、旅客、航空管制及航空公司自身因素等诸多原因而导致正常设定的航班无法按原计划执行时，将不得不面临航班延误、取消或备降等问题，此类不正常航班问题不仅带来巨大的延误成本，而且也给旅客带来诸多不便，甚至造成较大的社会影响。据统计，2007年我国国内航班总延误成本近30亿元，预计2020年将达到76亿元¨。。而另一方面，近年来我国飞机与航班的规模随着经济发展而不断扩大，不正常航班班次总数也逐年增长。因此，如何有效应对不正常航班问题，实现不正常航班的及时调度与恢复成为航空

8、公司面临的重要课题。因为飞机计划对航空公司收益的影响最大，故不正常航班的调度与恢复首要的是及时恢复飞机计划嵋“1。在飞机资源利用最大化的目标前提下，航空公司不正常航班调度可能涉及飞机与机组的可行性、航线限制以及地勤人员、补给和登机口的调配等诸多不确定因素，故不正常航班调度是一个复杂的收稿日期：2014—03—06基金