实现航班计划优化的动态规划模型

18220046JOURNALOFSHANGHAIUNIVERSITYOFENGINEERINGSCIENCEVol.18No.2Jun.2004:1009444X(2004)02013506,(,200336):,;MonteCarlo,,,:;;;:F562.1;F560.1:ADynamicProgrammingModelforAirlineOptimizationZHANGBo2sheng,LIUFei(CollegeofManagement,ShanghaiUniversityofEngineeringScience,Shanghai200336,China)Abstract:Onthebasisoftheanalysisofthebenefitofairline,amodelisconstitutedunderacertainworkingtimeandairlineschedule.Itsobjectistomaximizethebenefitoftheairline.Thesolutionmethodisfirstlytodeterminetheval2ueofstochasticvariablebycomputersimulationwithMonteCarlomethod,thentransferthemodelintonon2linearinte2gerprogramming,andthenmodeloptimizationissolvedbyusingalgorithmsofresource2allocationofdynamicprogram2ming.Thusalloptimizationairlineprogrammingisarranged.Keywords:airlineproject,dynamicprogramming,airlinebenefit,optimization.:20040312:(02FK05):(1946),,,,.90%,,,,:,,,,,,,,,90%,1,,,11Fig.1Blockdiagramofairlineoptimization2,,,,,,2.1,,,,,,,,,,,,,,,,:,,,,,,,,,:(),,(,)2.2,,,,(IE),,,,,2.3,,,63118,,2.4,,,,,,,,,,,,,,Cij=aij+Lijbij+Fijdij,Cijji;aijji;Lijji;Fijji;bijji;dijji,2.5==(---)=(---)-;==(---)=-,,,,,0,,,,,,,,;,3,,,,3.1,,,,,:i:,i=1,2,,mm;j:,j=1,2,,nn,j,;Xij:,ji,,1;G:;Gij:ji;REVGij:jiXij,;EEVBij:jiXij,;LPi:i(P);7312,:FPi:i(P);LGij:ji;LBij:ji;Nj:j;LFGij:ji;LFBij:ji;Hj:j;QGi:i;QBi:i;VGi:i;VBi:i;LKGi:i,;LKBi:i,;LKFGi:i,;LFKBi:i,;Cij:ji,;CGvij:ji;CBvij:ji;aij:ji;bij:ji;dij:ji;Tij:ji,;Tj:j;nj:j;Rj:j;fi:();S:;YZij:;3.2,==(---)mi:maxG=mi=1Gij()(1)mi=1XijF()(2)mi=1TijXijT()(3)LijNjS+LFijHjYZij()(4)Xij0(5):Gij=(REVGij+REVBij)(1-5%-3.75%)-Xij(CGvij+CBvij)(6)REVGij=Xij(LPiLGijNj+LFPiLFGijHj)(7)REVBij=Xij(LPiLBijNj+LFPiLFBijHj)(8)CGvij=aij+LGijbij+LFGijdij(9)CBvij=aij+LBijbij+LFBijdij(10)LGij=LKGiXijHj+VGj(11)LFGij=LFKGiXijHj+VGi(12)LBij=LKBiXijNj+QQBi(13)LFBij=LFKBiXijHj+VBi(14)3.2,,,,,,,,,,,83118,,,,,,,,ij,;,,,,,i,,,,,,4,6,,AB1,AB2,AB3,AB4,AB5AB6,6,6A;B1,B2,,B6,AiBi,,,,:;;,,,,:MAXG=Gi=1Gij:Gi=1Xij130;Gi=1TijXij300;Xij0,LKGiN(Gi,(2i)G)()LKBiN(Bi,(2i)B)(i=1,2,,6),MonteCarlo,LKGi,LKBi(i=1,2,6)A1,A2,j=1,j=2,A3,A4j=3,j=4,A5,A6,j=5,j=6,MonteCarloLKGi6,1,()1Tab.1ModelnumberusedinairlineA1A2A3A4A5A6j=1j=2j=3j=4j=5j=6,:2Tab.2DataaboutthebenefitofairlinePhPPP-B767-3002.00.5333148758010CGv11LGv111026X11-B757-2002.00.745866293314CGv22LGv221270X22-B737-8001.750.964964131832CGv33LGv331163X33-B737-7002.00.20426390CGv44LG44935X44-B737-3001.250.794119971331CGv55LG55673X55-CRJ-2001.50.83439840CGv66LG66878X66-B767-3002.00.8489138557460CBv11LB111026X11-B757-2002.00.350951512575CBv22LB221270X22-B737-8001.750.633354751564CBv33LB331163X33-B737-7002.00.77506900CBv44LB44935X44-B737-3001.250.917018691246CBv55LB55673X55-CRJ-2001.50.12667980CBv66LB66878X669312,:MAXG=(1-5%-3.45%)1026X11(LG11+LB11)N11-X11(CCv11+CBv11)+(1-5%-3.45%)1270X22(LG22+LB22)N2-X22(CGv22+CBv11)+(1-5%-3.45%)1163X33(LG33+LB33)N3-N33(CGv33+CBv33)+(1-5%-3.45%)935X44(LG44+LB44)N4-X44(CGv44+CBv44)+(1-5%-3.45%)673X55(LG55+LB55)N5-X55(CGv55+CBv55)+(1-5%-3.45%)878X66(LG66+LB66)N6-X66(CGv66+CBv66):X112+X222+X331.75+X442+X551.25+X661.5300;X11+X22+X33+X44+X55+X66130;X11,X22,X33,X44,X55,X66;:LGii=LKGiXiiNi+Qi;LBii=LKBiXiiNi+Qi;CGVii=aii+LGiibii;CBVii=aii+LBiibiiQi,aii,bii,Ni,(i=1,2,,6),,,33Tab.3ResultofairlinesoptimizationFlightScheduleCount()3944151735flight()B767-300B757-200B737-800B737-700B737-300CRJ-200Gij(P)33983123499603388529394970335861452435G()84697135,,,,,,,,,,,,,:,,(,),(,),,,,,,,,:[1].[J].,2001,19(3):4243,47.[2].[J].,2001,19(6):1922,26.[3],.[J].,1999,31(4):475479.[4],.[J].,2000,9(3):5663.[5].[J].,1995,4(2):2327.[6].[J].,1999,(6):1923.[7].[J].,2000,(2):3740.04118