物流配送路径优化问题的研究与应用

太原理工大学硕士学位论文物流配送路径优化问题的研究与应用姓名：王永亮申请学位级别：硕士专业：计算机软件与理论指导教师：段富20090301I(AntConlonyAlgorithms,ACA)(ACA)IIIIIRESEARCHANDAPPLICATIONONOPTIMIZINGLOGISTICDISTRIBUTIONROUTINGPROBLEMABSTRACTLogisticdistributionisanoperationlinkingwithconsumerdirectly,andtakesaccountforconsiderableproportioninvariablecostsinlogistics.Theplanningofvehicleroutingindistributionwilltakegreateffectontheefficiency,costandbenefit,especiallyindistributingformulticonsumer.Ascientificandreasonablemethodtovehicleschedulingisanimportantoperationinlogisticdistribution.Exploringthedistributionroutinealwaysbasesontheshortpath.Therearelotsoffactorswhichinfluencetheproblem.thispapermainlyAimatoptimizationthechoiceofthedistributionroutine,analysissomefactorswhichrelatetotheproblem,thispaperestablishesthemathematicsmodelwhichmatchesthefactandconvertsthequalitativeproblemintoquantitativeproblem.Theantcolonyalgorithm(ACA)isanewmethodforoptimization,whichisbasedontheresearchontheantcolony.Ititeratestothebestansweraccordingtoselectivestrategyandpheromonewhichproducedbyantindividuals.OwingIVtoitspositivefeedbackandeffectiveparallelizationandstronglustiness,ACAhasbeenappliedinmanyfields.Itistheimportantresearchproblemsofthispaperthatapplyingantcolonyalgorithmtosolvetheoptimizationoflogisticsdistributionroutineproblem.Onthebasisofresearchingtheoptimizingmodelonlogisticsvehiclescheduling,thispaperintroducesAntConlonyAlgorithms(ACA)intothemodelofthevehicleschedulingproblemtoestablishanoptimizingmodelonlogisticsvehicleschedulingproblemforDaTongNewTongFeng(Group)Company.TheresultofexperimentalcalculationsdemonstratethattheoptimalornearlyoptimalsolutionstothelogisticvehicleschedulingproblemcanbeeasilyobtainedbyusingAntConlonyAlgorithms,avoidunreasonableroutinefordriversandprovidesomesuggestionstologisticsenterprises.KEYWORDSLogisticsDistributionOptimizingRoutingVehicleSchedulingAntColonyAlgorithm(ACA)1234511.1VRP(VehicleRoutingProblem)1.1.1[1]907%GDP20003.6[2]19981999:1460154071%53%2001219000GDP20%20%10%GDPGDPGDP1.1.2:(1)(2)3NP1.21959DantzigRamser[3]1.2.11983BodinGolden[4]IBMVSPXVSSHpCAD[5]3(1)2070804(2)(3)1.2.22090(TravelingSalesmanProblemTSP)(ChinesePostmanProblemCPP)[6]TSPVRP[7][8]1.31.3.1()51.3.21.3.3VRP62.1LK:1);2);3)()2-1Fig.2-1ThepatternofLogisticsDistribution72-1:153132331332.2(l)(2)Internet21CD(3)82.3[9](1)(2)(3)(4):(5)()(6):92.4(1)(2)()()()(3)()()()()(4)()()(5)()[9]102.5(1)(2)(3)(1)(2)(3):(1)(2)11(3)(4)(5)(6)(7)2.6[10]2-2:2-2Fig.2-2TheFlowChartofLogistieDistribution(l)(2)12(3)(4)(5)(6)2.7:2.7.1(TbauSearchTS)Glover1986[11].13TS(TabuList)2.7.2(simulatedAnnealingSA):Metropolis80[12]:O114:exp(c/T)cT()12.7.31975J.Holland(GeneticAlgorithmsGA)GA[13]GA153.1ACAM.Dorigo21(MMAS)TSPTSP3.2(Pheromone)163.1NFDBDADC2ABBC130NA30FC2/t=0AC30AD(CD)15AB(CB)AD=DC=2AB=2CB1ABCBADDCt=130ACAB(CB)AD(CD)20103-1Fig.3-1SketchmapofantfindingfoodroutinePheromone()PheromoneN(nest)F(food)BDACd=2d=1d=1d=2173.3TSPTSPTSPTSP():n{012n-1}TSPiVTSPnHamiltonnTSPm:(1)(2)(3):(3-1)ijijTSPijkallowedk:ijCjV(01,01,)ijCinjnij≤≤−≤≤−≠ijP=,()()()()ijijkisisjallowedttttαβαβτητη∈∑⋅⋅0otherwiseijτijη1/ijijdη=18(3-2)n1-01kijM.Dorigo:(Ant-CycleSystem):(3-3)(Ant-DensigySystem)(3-4)(Ant-QuantitySystem)(3-5)QkLkd(ij)ijAnt-CycleQ/kLQ/d(ij)Q3.4m(C)tabuNCmax1()()(1)mkkijijijtntττρτρ=∆∑+=⋅+−⋅kijτ∆(0)ijCτ=kijτ0kkijQkLτ∆=0kijQkτ∆=(,)0kijQkdijτ∆=191Ant-CycleSysetm:Sett=0NC=0mnFork=1tomdoktbauk(kl)RepeatuntiltabulistisfullFork=1tomdokj,jtabu(k,j)allowed(k,j)0Fork=1tomdokFork=1tomdoSett=t+nSetNC=NC+1SetIf(NCNCmax)and()thentabuGotoElse(0)ijcτ=0ijτ∆=kijpkl()ijtnτ+0ijτ∆=202Ant-CycleSysetm3-2Fig.3-2Processofantcolonyalgorithm3.521mQ(1)1-O1-1-1-Ant-CycleSystem0.5[14](2)mTSPm()()()()Omnn/2(n)(2)()22=1-5=1-5(4)QQQQ=1003.63.6.1(1)()(2)Agent(3)23(4)(5)3.6.2(1)(2)243.6.3ThomasStutzleMMASL.M.GambardellaHASMMAS(Max-MinAntSystem)[15]MMAS[tmintmax]tmintmaxL.M.GambardellaHASMAS(MutatedAntSyestm)[16]2-[17]254.14.1.1,()(),:(1);(2);(3);(4)4.1.2[9]01Li:(4-1)(4-2)1010ijkikkijxiky==0001min,1,2,llmijijkijkliikiZcxgyqkm=====≤=⋅⋅⋅∑∑∑∑26(4-3)(4-4)(4-5)(4-6)(4-7)(4-8)ij(l)(2)k(3)i(4)0m(5)(6)(7)(8)4.1.3()4.2()101001,1,2,,1,2,,1,2,,1,2,,1,2,()01,,0,1,2,,1,2,mikkmkklijkjkilijkjkjijkijkyilymxyjlkmxyjlkmXxSxijlkm======⋅⋅⋅===⋅⋅⋅=⋅⋅⋅==⋅⋅⋅=⋅⋅⋅=∈==⋅⋅⋅=⋅⋅⋅∑∑∑∑ijc274.2.1:(1)(2)(3)(4)(5)28(6)4.2.2Lq(i)ii=1,2,khd(i,j)iji,j=0,d(0,3)3i,j=0,1,2,khKQkkk=12,K;Dkkk=1K;nkknk=0Rkknk=0Rk;nk0ki,k=1,2K4.2.3(l):(4-9)(2):}}{{12,,,1,2,,knkkkkRrrrL=⋅⋅⋅⊆⋅⋅⋅ikr1,0kiknrkkiqQn=≤≠∑101,0kiinkkkknkkrrriddDn−=+≤≠∑29(4-10)(3):(4-11)(4):(4-12)4.2.4:(1)S(4-13)(2)TR(4-14)Z(4-15)x1x211*2*()ZxSxTR=+1212,kkRRkk=∅≠I}{111,2,,0KkkkKkkRLnLnL===⋅⋅⋅≤≤=∑U1011()kiinkkkknKrrrkiSdd−===+∑∑11LiiKkkqTRQ===∑∑304.2.511*2*()ZxSxTR=+Q/ZQZ(1)Step1Step2ki,iktabuStep3kp(i,j)kjStep4ijqsumqsum=qmaxStep6Step5jkpathStep331Step6allowedStep3allowedStep7Step8NCmaxStep2(2)324-1Fig.4-1TheFlowChartofAlgorithmqsum=qmaxkpathkallowedpathkNC=NCmax?k=1tomkpathk=1tom,k335.1WindowsXPVB.net2003MicrosoftSQLServer20005-1345-1Fig.5-1TheWorkingFlowchartofSystem5.235(1)(2)(3)365-2Fig.5-2ThechartofSystemFun