年12月交通运输工程学报

86200812JournalofTrafficandTransportationEngineeringVol18No16Dec.2008:2008209209:(70525004,70121001,60736027);(20060401003);(06JK099):(19702),,,,:(19622),,,:167121637(2008)06201102061,2,1,3,4(11,710049;21,710021;31,710049;41,3125):,,2,,2:,3;,2;2:;;;;:U492:AOnlineselectionmodelandcompetitiveanalysisofvehicleroutingingridtransportationnetworkSUBing1,2,XUYin2feng1,3,YUShui4(1.SchoolofManagement,XipanJiaotongUniversity,Xipan710049,Shaanxi,China;2.SchoolofEconomicsandManagement,XipanTechnologicalUniversity,Xipan710021,Shaanxi,China;3.StateKeyLaboratoryforManufacturingSystemsEngineering,XipanJiaotongUniversity,Xipan710049,Shaanxi,China;4.SchoolofEngineeringandInformationTechnology,DeakinUniversity,Melbourne3125,Victoria,Australia)Abstract:Inordertoanalyzethevehicleroutingproblemundersuddenroadblockageingridtransportationnetwork,avehicleroutingmodelwasproposedbyusingthemethodsofonlineproblemandcompetitivestrategy,directiongreedystrategyandmulti2alternativemovingstrategyweredesigned,andthecompetitiveratiosoftwostrategieswerecomputed.Analysisresultindicatesthatthecostofdirectiongreedystrategyis3timesthantheoptimalcostundersuddenroadblockagestate,multi2alternativemovingstrategyhasagoodperformancewithpracticalrestrictionfordifferentcases,thecostofmulti2alternativemovingstrategyis2timesthantheoptimalcostintheworstcase,thecompetitiveratiosoftwostrategiesarenotmorethantheinfimumofthecompetitiveratioforunexpectedblockageproblemingeneralnetworks.3figs,17refs.Keywords:traffictransportation;gridtransportationnetwork;vehiclerouting;onlineproblem;competitiveanalysisAuthorresumes:SUBing(19702),female,PhD,[phone],[e-mail];XUYin2feng(19622),male,professor,[phone],[e-mail].0,,,,,,,,,,[1][2][3][4][5][6],,,,,,,,,,1,,,,()[728],,,,,,,k2[7][9],[10][11]()PAPADIMITRIOU1989,PSPACE2complete,[12]2003,[13],:,2k+12k+1-1,,2k+1,[14216],,[13216],,,2k+1,1,3,3,24,,,11Fig.1Citygridtransportationnetworks2.1,m+1n+1G,GE={e(vi,j,vi,j+1)e(vi,j,vi+1,j)}i=0,1,,m;j=0,1,,nG1,,()1116,:,,(1)k,R=(e1,e2,,el,,ek)(2)(3)e(vi,j,vi,j+1)e(vi,j,vi+1,j);e(vi,j,vi,j+1)e(vi+1,j,vi+1,j+1);e(vi,j,vi+1,j)e(vi,j+1,vi+1,j+1)(4)Copt(R),();CA(R)A,CA(R)Copt(R)A,A,,,,,,1,2.2(1)v0,0,v0,n,P=(v0,0,v0,1,,v0,j,,v0,n)nG,Gv0,0v0,nPP,G,P,v0,0v0,nn+2PP,v0,0v0,nn+2,,,n+2(2)v0,0,vm,n(0mn),v0,0vm,n,m+n,m+n,,m+n3,,,,3.1,v0,0,vm,n,mn1:v0,0,vi,j,e(vi,j,vi,j+1),vi,jvi,j+1;vi,je(vi,j,vi,j+1),vi,jvi+1,jvi,ji=mjn,vm,je(vm,j,vm,j+1),vm,jvm,j+1;vi,je(vm,j,vm,j+1),vm,jvm-1,jvi,jj=nim,e(vi,n,vi+1,n),vi,nvi+1,n;vi,je(vi,n,vi+1,n),vi,nvi,n-12:1,i=m,j=n,vi,jimjn,,1,1vi,ji=mjnvi,jj=nim,vi,jvm,n,vm,je(vm,j,vm,j+1),vm,jvm-1,j1,1,(3),e(vm-1,j,vm-1,j+1)2112008,vm-1,j+1,1,vm-1,j+1imjn,1,1vm-1,nvm,n-1,(4),vm,n,,,3.21:,3:2(1)v0,0,v0,n,P,,P,nPP,,v0,jv1,jv1,jv0,j2k,2(a)PM,v0,0v0,nn+2kn+2kn+2=1+2(k-1)n+2kn,n+2kn+21,kn,n+2kn+23,,3(2),v0,0vm,0,,vm,0,vm,0vm,n,vm,0e(vm,0,vm,1),vm,0vm-1,0,vm,jvm-1,jvm-1,jvm,j2k,2(b)PM,v0,0vm,nm+2k,,m+2km+nknm,m+2km+n2;knmn,m+2km+n1.5,,2(1)(2),3,4,,2Fig.2Competitiveanalysisfordirectiongreedystrategy,,,,vi,jvm,n(m-i+n-j)!(m-i)!(n-j)!N(i,j)vi,jvm,n,N(i,j+1)N(i+1,j),vi,j+1vm,nvi+1,jvm,n,[17],,,,4.1m-i=n-jvi,jv0,0,vm,n,mn1:v0,0vi,j,m-in-jvi,je(vi,j,vi,j+1),vi,jvi,j+1;vi,je(vi,j,vi,j+1),vi,jvi+1,jm-in-jvi,je(vi,j,vi+1,j),vi,jvi+1,j;vi,je(vi,j,vi+1,j),vi,jvi,j+1m-i=n-j,vi,jvi+1,jvi,jvi,j+12:1,i=m,j=n,,4.22:,3116,:vi,jm-i=n-j,1;vi,jm-i=n-j,2:2(1)v0,0v0,n,v0,n-1vi,jm-i=n-j,1(1),(2),2vi,jm-i=n-j,,v0,0vm,nm+n,:vm-1,n-1,(4),,vm,n;vm-2,n-2e(vm-2,n-2,vm-1,n-2),vm-2,n-1,(3),e(vm-2,n-1,vm-1,n-1),vm-1,n-1,,vm,n;,vi,jm-i=n-j,v0,0vm,nm+n,3(a)PM,,,vi,jm-i=n-j,1,13Fig.3Competitiveanalysisformulti2alternativemovingstrategy,v0,0,,,1,3(b)PM,vi,jm-i=n-j,vm,jjnvi,nim,vm,j,,v0,0vm,j,m,vm,jj=m;vm,jvm,n,n-m,v0,0vm,n2n,,vi,jm-i=n-j,2nm+n,mn,2nm+n1,m,2nm+n2,2,2,vi,jm-i=n-j,,,;,5,,,,2:,,3,,,1,;,2,,(),,,,,,:References:[1],.[J].4112008,2007,7(1):1112115.HEZhu2qing,SUNLin2yan.Modelandalgorithmofvehicleroutingproblemunderdynamictraffic[J].JournalofTrafficandTransportationEngineering,2007,7(1):1112115.(inChinese)[2]THANGIAHSR,OSMAMIH,SUNT.Hybridgeneticalgorithmsimulatedannealingandtabusearchmethodsforvehicleroutingproblemwithtimewindows[R].SlipperyRock:SlipperyRockUniversity,1994.[3],,.[J].,2004,17(1):79281.ZHANGBo,YEJia2wei,HUYu2cong.Applicationofopti2mizingthepathbysimulatedannealing[J].ChinaJournalofHighwayandTransport,2004,17(1):79281.(inChinese)[4],,.[J].:,2006,26(3):80283.HUDa2wei,HUYong,ZHUZhi2qiang.Solvinglocationroutingproblembasedonspacefillingcurveanddynamicpro2gramming[J].JournalofChangpanUniversity:NaturalScienceEdition,2006,26(3):80283.(inChinese)[5],,,.[J].,2007,7(1):1062110.LIBing,ZHENGSi2fa,CAOJian2dong,etal.Methodofsolvingvehicleroutingproblemwithcustomerspdynamicrequests[J].JournalofTrafficandTransportationEngineering,2007,7(1):1062110.(inChinese)[6],,.[J].,2005,5(1):1022105.YANGRui2chen,ZHOUYong2fu,YUNQing2xia.Hybridalgorithmforvehiclepsoptimalroute[J].JournalofTrafficandTransportationEngineering,2005,5(1):1022105.(inChinese)[7]MANASSEMS,MCGEOCHLA,SLEATORD