搜索
175Vol.17,No.5200810OPERATIONSRESEARCHANDMANAGEMENTSCIENCEOct.2008:2008201217:(70431003);(60521003);(2006BAH02A09);(70801012):(19802),,,,,;(19482),,,,,,;(19792),,,,,,1,2,1,3(1.,110004;2.,110004;3.,110004):,,,,,:;;;:F224.33:A:100723221(2008)0520073207Multi2objectivePathSelectionModelforEmergencyEvacuationTakingintoAccountthePathComplexityYUANYuan1,WANGDing2wei2,JIANGZhong2zhong1,SHENGYing3(1.SchoolofBusinessAdministration,NortheasternUniversity,Shenyang110004,China;2.SchoolofInforma2tionScienceandEngineering,NortheasternUniversity,Shenyang110004,China;3.CollegeofSciences,North2easternUniversity,Shenyang110004,China)Abstract:Pathselectionisoneofthemostfundamentalproblemsinevacuationplanning.Takingintoaccountthefactorsofevacuationtimeandpathcomplexity,amulti2objectivepathselectionmodelisbuiltforemergencye2vacuation.Theobjectivesofthemodelaretominimizethetotalevacuationtimeandtominimizethecomplexityofthepath.Thetravelspeedonthearcoftheevacuationnetworkisrepresentedasacontinuousdecreasefunc2tionwithrespecttotimeunderreal-timeeffectofdisasterextension.Anantcolonyoptimizationalgorithmisproposedtosolvethemodel.Simulationresultsshowtheeffectivenessandfeasibilityofthemodelandalgorithm.Keywords:managementoperationalresearch;evacuationplanning;optimizationmodel;pathselection0,,[1,2],,[3,4],,[59],,,,,[10,11],,,,,,,,,,11.1(1)G(V,A),V=(v1,v2,,vn),A,AAVVv1,v2,,vn,v1,,vn,(2)lijvivj,(vi,vj)A(3)s0ij(vi,vj),sij(t),t(vi,vj),,sij(t)=s0ijije-ijt:ij,ij,sij(t),(vi,vj)(4)tij(vi,vj);tivi,tj(vi,vj)vj,tij=tj-ti(5),xij=01,xij=1(vi,vj);xij=0(vi,vj)(6):P,P,pkP,P(vp1,vp2,,vpk,,vpK),1pkn,kvpkPp1=1,pK=n,P,,P(7):P=(vp1,vp2,,vpk),1vpknvp1vpkPvpk,ET(P,vpk),ET(P,vpk)=k-1m=1tpmpm+1=(tp2-tp1)+(tp3-tp2)++(tpk-tpk-1)=tpk1.2,P=vp1,vp2,,vpk,,vpK,tp1=t1=0(1)tpkpk-1Spk-1pk(t)dt=lpk-1pk,2kK(2)47200817(2),tpk-1spk-1pk(t)lpk-1pk,tpk(2),P,Ppk(1pkn)tpk1.3,,,,,,minf1=ni=1nj=1tijxij(3),,,,[12],,,[10,11],,,,[13],[14];,[15],,,,,minf2=ni=1nj=1xij(4)1.4,minf1=ni=1nj=1tijxij(5)minf2=ni=1nj=1xij(6)s.t.tjtisij(t)dt=lij(7)tij=tj-ti(8)t1=0(9)sij(t)=s0ijije-ijt(10)nj=1j1xij-nj=1j1xji=1i=1-1i=n0(11)nj=1j1xij1in=0i=n(12)xij=0,1,i=1,2,,n;j=1,2,,n(13),(5)(6);(7)(8)(9),tijsij(t)(vi,vj);(10);(11)xijv1vn;(12);(13)xij2(AntColonyOptimization,ACO)Dorigo2090575,:,(AntSystems,AS)[16]TSP,,[17],1,,,,,,,2.1,,(Pareto),,minF=r1f1-f31f31+r2f2-f32f32(14)s.t.(7)-(13),f_3=(f31,f32)T;r_R={r_|ri0ri=1,i=1,2},;,:(1)(5),(7)-(13),f31(2)(6),(7)-(13),f32(3)f_(f31,f32)T(14),(14),(7)-(13),,,2.2(SOPS-ACO)SOPS2ACO(ACOtoSolveSingle2ObjectivePathSelectionModel),:Step1(NC=0)ACO,:NCmax,M(vi,vj)ij(0)=cij=0;Step2Mi,mjpmij=ijijnj=1ijij(vi,vj)A0(15),ij,,ij,m,M,2,3;Step367200817mij=QLm,m(vi,vj)0,(16)ij=Mm=1mij(17)ij(NC+1)=(1-)ij(NC)+ij(18),Lm,Step4NCNCmax,NC+1NC,Step2;,2.3,,,,,SOPS2ACOStep1SOPS2ACO(5),(7)-(13),f311ij=s0ijije-ij(vi,vj)A0(19),,,,,(16)Lm1,m,Step2SOPS2ACO(6),(7)-(13),f322ij=1(vi,vj)A0(20),,(16)Lm2,mStep3f_3=(f31,f32)T(14),SOPS2ACO(14),(7)-(13)Step2,Step1,3ij=s0ijije-ij(vi,vj)A0(21)(16)Lmm,Lm=r1fm1-f31f31+r2fm2-f32f32(22),fm1fmmm123150106,1,50,3(),ij(0.6,0.7),(0.7,0.8),(0.8,0.9),ij(0.1,0.15),(0.05,0.1),(0,0.05),lijs0ijij,ij1775,:11(vi,vj)(lij,s0ij,ij,ij):(m,m/min,-,-)(vi,vj)(lij,s0ij,ij,ij):(m,m/min,-,-)(vi,vj)(lij,s0ij,ij,ij):(m,m/min,-,-)(1,2)(95,130,0.6926,0.1135)(14,32)(35,120,0.7904,0.0991)(30,38)(65,140,0.8055,0.0305)(1,3)(65,120,0.6976,0.1434)(14,33)(50,130,0.7674,0.0954)(30,39)(95,170,0.8914,0.0129)(1,4)(95,140,0.6956,0.1393)(14,37)(80,150,0.7502,0.0628)(31,29)(35,110,0.8630,0.0205)(1,5)(80,130,0.6342,0.1253)(15,19)(50,130,0.7683,0.0734)(31,41)(80,150,0.8481,0.0089)(1,6)(125,150,0.6558,0.1286)(15,23)(35,100,0.7409,0.0825)(32,36)(50,130,0.7265,0.0533)(2,8)(80,170,0.6217,0.1123)(15,24)(20,100,0.7139,0.0698)(32,44)(155,170,0.7066,0.0959)(2,16)(50,130,0.6532,0.1231)(15,32)(65,140,0.7577,0.0770)(33,43)(80,140,0.7492,0.0663)(2,17)(20,100,0.6576,0.1028)(16,15)(50,140,0.7823,0.0831)(34,40)(20,100,0.8795,0.0094)(3,2)(20,100,0.6388,0.1096)(16,19)(65,140,0.7565,0.0534)(34,45)(80,150,0.8158,0.0386)(3,4)(20,110,0.6883,0.1302)(17,18)(125,160,0.7924,0.0887)(34,46)(140,170,0.8935,0.0485)(4,8)(35,130,0.6811,0.1340)(17,19)(80,140,0.7528,0.0834)(35,39)(50,120,0.8162,0.0311)(4,9)(50,120,0.6676,0.1341)(18,19)(35,100,0.7860,0.0531)(36,34)(35,110,0.7450,0.0639)(5,4)(20,110,0.6975,0.1499)(18,25)(20,100,0.7359,0.0894)(36,44)(80,140,0.7197,0.0601)(5,6)(35,120,0.6369,0.1277)(18,26)(35,100,0.7080,0.0999)(37,43)(35,110,0.7609,0.0829)(5,9)(65,160,0.6889,0.1228)(18,27)(65,140,0.7664,0.0698)(37,44)(65,130,0.7364,0.0694)(5,10)(80,140,0.6010,0.1148)(19,25)(35,110,0.7979,0.0519)(38,39)(80,150,0.8851,0.0076)(6,7)(50,130,0.6752,0.1448)(19,28)(95,160,0.7413,0.0659)(39,42)(35,120,0.8037,0.0470)(6,10)(65,140,0.6268,0.1489)(20,21)(95,160,0.6293,0.1344)(39,46)(65,140,0.8119,0.0217)(6,20)(110,170,0.6807,0.1419)(21,33)(95,160,0.7731,0.0604)(40,44)(20,100,0.8255,0.0465)(7,20)(50,130,0.6489,0.1072)(22,14)(35,120,0.7146,0.0902)(40,48)(65,130,0.8298,0.0175)(8,12)(20,100,0.6371,0.1217)(22,32)(50,120,0.7593,0.0666)(41,42)(20,100,0.8515,0.