搜索
200444:100026788(2004)04201302061,2,1,11.,430074;2.,430070):(PSO)(VRPTW),,,L,,L:;;:O221.1;U116.2:AParticleSwarmOptimizationforVehicleRoutingProblemwithTimeWindowsLINing1,2,ZOUTong1,SUNDe2bao1(1.DepartmentofAutomaticControl,HuazhongUniversityofScience&Technology,Wuhan430074,China;2.SchoolofComputerScience&Technology,WuhanUniversityofTechnology,Wuhan430070,China)Abstract:ThispaperintroducesaproposaltoextendtheheuristiccalledParticleSwarmOptimization(PSO)todealwiththeVehicleRoutingProblemwithTimeWindows(VRPTW),andproposesanovelParticlepresentationforthevehicleroutingproblem.ThePSOiscomparedwithGAinthesameVRPTWinexperiments.ExperimentalresultsindicatethatthePSOcaneffectivelyandquick2lygetoptimalresolutionofVRPTW,soitisprovedtobeaneffectivemethodforVRPTW.Keywords:vehicleroutingproblem;particleswarmoptimization;optimization:2003204230:.:(1972-),(),,,:;(1941-),(),,,,:1(VehicleRoutingProblem,VRP)DantzigRamser1959,(),,,,(,)[1],NP,L(VehicleRoutingProblemWithTimeWindows,VRPTW)VRPLVRPTW(),,L,[1]L(PSO,ParticleSwarmOptimization)[2],,[3]LPSO,L2:,K,qk(k=1,2,,K);L,1,2,,LZigi(i=1,2,,L),(max(g)iFmax(qi)),i()Ti,i[ETi,LTi],ETii,LTiiZiETi,i;LTi,iZZZ:1)VRPVRP,,L2)VRPVRP,:ETii,,;LTii,,Z[1],0,1,2,,L,i(i=0,1,,L)Z:yki=1ik0xijk=1kj0cijij,Zsii,pEETii,pLLTii;ETii,pE(si-ETi),LTii,pL(LTi-si)Z:minz=6i6j6kcijxijk+pE6li=1max(ETi-si,0)+pL6li=1max(si-LTi,0)(1)s.t.6igiykiFqkPk(2)6kyki=1i=1,2,,L(3)6ixijk=ykjj=0,1,,L;Pk(4)6jxijk=ykii=0,1,,L;Pk(5)X=(xijk)S(6)xijk=01i,j=0,1,,L;Pk(7)yki=01i=0,1,,L;Pk(8)(1)pE=pL,VRPZ,;Z,ZZ,,Z(1)ETi=0,LTi,VRPTWVRP;,TSP;(2),mTSPTWZ13143(ParticleSwarmOptimization)KennedyEberhart1995,,LPSO,(Particle),(),,LPSO(ShiandEberhart)[3]:D,nZiXi=(xi1,xi2,,xiD);i()Pi=(pi1,pi2,,piD),gPgPi(i=1,2,,n);i()Vi=(vi1,vi2,,viD)Z():vid(t+1)=wvid(t)+c1rand()[pid(t)-xid(t)]+c2rand()[pgd(t)-xid(t)](9)xid(t+1)=xid(t)+vid(t+1)1FiFn;1FdFD(10),c1,c2,;rand()[0,1];w,w(exploration),w(exploitation)Zd(1FdFD)[-XMAXd,XMAXd],[-VMAXd,VMAXd],ZMauriceClerc,PSO[4]Z,(9)(10),L,(Global),(Local)Pl,(9)PgdPldZPSO:(Particle);DoFor(eachparticle)(1);IfThen(Pi)(Xi);End();If()Then()Pg(orPl);For(9)Vi;(10)Xi;EndWhileL,PSO[3]L44.1,,Z[5],2LLVRP,:23120044k,krZ,2LXL:Xv()Xr()Z,VRP7,3,X::1234567Xv:1222233Xr:1431221:1:0102:0453203:0760VVvVrZ,,Z,PSO[6],,Z4.2PSO,VRP,L:1L;Xv1K(),Xr1L();Vv-(K-1)(K-1)(),Vr-(L-1)(L-1);Eval;Pi,PlPgZ2,Z,(9)VvVr;(9)XvXr,Xv;VXZEval;,,Pi;,PlPgZ,Z,E2val:1)(1)Z,Xr,Z2)XrZ,:Xv:1222233Xr:53.26.21.22.50.54.2Xr:13412125,MatLab6.1VRPTW(GA)LP41.7G256MRAMWin2000L,GA[1]3314;PSO[4]L1[1]VRP,7,1L101234567(18,54)(22,60)(58,69)(71,71)(83,46)(91,38)(24,42)(18,40)(gi)0.890.140.280.330.210.410.570,q=1.0,3Z(217.81)GA:n=40;Pc=0.6;Pm=0.2;,200ZPSO:n=40;2,22,2(1ö10);w=0.729;c1=c2=1.49445;200Z50,2Z3PSOZ21GAPSO(s)GA321853.932.3PSO50028.363.0431PSO723217717137411928113314212311718224135836201038565359215762567305592921638943148129379,PSO100%,GA64%,GA10LPSOGAL[5]GAPSOL2[1]VRPTW,8(1,2,,8),gi[ETi,LTi]4Z038,5,50,1,:pE=50,pL=50Z412345678(gi)21.54.531.542.53Ti121322.530.8[ETi,LTi][1,4][4,6][1,2][4,7][3,5.5][2,5][5,8][1.5,4]:1:06402:031203:08570Z=910ZGAPSO50,1,6L,PSO46%,GA24%L,,PSOGALPSOGAL,VRPTW,GA43120044PSO,L.1),LVRPTW,()L,VRP,68,90%;VRP,10;5012345678004060759020010016080140065401005075110100260650751001007575753754075010050909015049010010010001007575100520050100501000709075610075759075700701007160110759075907001008801007515010075100100062GAPSOGA24%993.618.41sPSO46%940.58.532),24;3),1ö101ö20;4)56,50,L[6]PSO,;w,LVRPTW,w,L6PSO,GAL1),;2),(elitism);3),,L,PSO,,L:[1],.[M].:,2001.[2]KennedyJ,EberhartRC.Particleswarmoptimization[A].ProcIEEEInternationalConferenceonNeuralNet2works,IV[C].Piscataway,NJ:IEEEServiceCenter,1995.1942-1948.[3]EberhartRC,ShiY.Particleswarmoptimization:developments,applicationsandresources[A].ProcCongressonEvolutionaryComputation2001[C].Piscataway,NJ:IEEEPress,2001.81-86.[4]MauriceClerc,JamesKennedy.Theparticleswarm2explosion,stability,andconvergenceinamultidimensionalcomplexspace[J].IEEETransactiononEvolutionaryComputation,2002,6(1):58-73.[5]AyedSalmen,ImtiazAhmad,SabahAl-Madani.Particleswarmoptimizationfortaskassignmentproblem[J].Mi2croprocessorsandMicrosystems,2002,26:363-371.[6]ShiY,EberhartRC.Empiricalstudyofparticleswarmoptimization[A].Proceedingsofthe1999CongressonEvo2lutionaryComputation[C].Piscataway,NJ:IEEEServiceCenter,1999.1945-1950.5314