多车场物流配送车辆调度研究

华中科技大学硕士学位论文多车场物流配送车辆调度研究姓名：熊浩申请学位级别：硕士专业：企业管理指导教师：徐天亮20060425IIMultiple-DepotVehicleRoutingProblemMDVRPMDVRPIIIAbstractWiththedevelopmentofmodernbusiness,thetrendofcorporationbecomebigandglobalandtheacquirementofscalelogistics,whichimpelthenecessityofbuildingmorethanonedistributioncenters.SoMultiple-DepotVehicleRoutingProblem(MDVRP)willbecomeanewimportantbranchofvehicleroutingproblem.But,uptillnowmanystudyaboutVRPareemphasizedonsingledepotjustalittleareaboutmulti-depotVRP.Multi-depotVRPmeanstherearemorethanonedepotfromwhichvehiclescangoouttodistribution.Thispapertrytodosomeresearchfromthreeaspects:Heuristicalgorithmofone-wayMDVRP,MDVRPofthetransshipmentinTwo-EchelonSystemandintheCyclingLogisticssystem.Therearefivepartconsistofthepaper.Thefirstparttellsomegroundandthemotilityoftheresearch,aswellastheliteraturereview.ThenparttwointroducesthenewtrendofdistributionandbasicconceptaboutMDVRP.AndthethirdpartstudythemathematicformulationandHeuristicalgorithmofthepickupordeliveryofMDVRP,aexampleprovetheHeuristicalgorithmiswell.AndthenpartfourexpandsthewaytotheproblemofbothpickupanddeliveryMDVRP,whichincludetheTwo-EchelonSystemandCyclingLogisticssystem.AndthemathematicformulationandtheHeuristicalgorithmhavealsobeengiven.Keywords:logisticsdistribution,vehicleroutingproblemMultiple-depotproblem,heuristicalgorithmI(“”)::::111.120400010530011199014200170112[1]12121.250%Multiple-DepotVehicleRoutingProblemMDVRP31.31.3.1G.DantzingJ.Ramser1959VehicleRoutingProblemVehicleSchedulingProblemVRPVSPVRP1.3.21983BodinGolden700Christofides1985Golden4Assad1988AltinkernerGavish(1991)Laporte1992Salhi1993BodinChristofidesGoldenAssadBallLaporteRinnooyKanLenstraDesrosiersDesrochers[2-13]VRP(TravelingSalesmanProblemTSP)(ChinesePostmanProblem,CPP)(DirectedChinesePostmanProblemDCPP)MDVRP520012001sweepsaving[14]δ2004[15]2004[16]1997SAClarke-Wright[17]2004[18]1.41.4.1:152MDVRP3451.4.22MDVRP3462MDVRP2.12.1.172.1.212.()198981019922.2MDVRPMDVRPVRP2.2.1MDVRPHokeyMin1998LRPLRP[19]LRPMDVRPMDVRPLRPLocationRoutingProblemMDVRP2121MDVRPAB12345678*9*9211MDVRP23456MDVRPVSPVSPVSPVSP710892.2.2VRPNPMDVRPVRPNPMDVRPMDVRP1BranchandboundTai-Hsi[20]GaborNagy[21]2(Dynamicprogramming)Muyldermans[22](3)(Cuttingplanes)11NPMDVRPAverbakhBerman199422MDVRPILPMILP[23]22LPMLPNMK0101222382744145742282539244113633264159288156316103354011715763806241544150833110158011251647204423881049023248019002577501015545101.259E15554004495055076MDVRPMDVRP22RoutingFirst-ClusterSecond(ImprovementandExchange)12221sweepsavingTSP[2]VSPIDGiosa2002[24]2SSalhiGNagy1997[25]23LinGaborNagy200523[21]13On61433.13.2MqKmm1MNigii=1,Ngiq1512NN1N2NM1ik0mkiy=m1ijmk0mkijx=:1111minmKNMNMMmkijijijmkZcx++=====∑∑∑∑311,1,2,,1,2,NmkiimigyqmMkK=≤==∑……3211,1,2,mKNmkimikyKmM==≤=∑∑…33111,1,2,mKMmkimkyiN====∑∑…341,1,2,;1,2,;1,2,NMmkmkijjmixyjNmMkK+=====∑………351,1,2,;1,2,;1,2,NMmkmkijimjxyiNmMkK+=====∑………36''111,1,2,;1,2,;1,2,NNmkmkijjijjmxximNNNMmMkK===≤==+++==∑∑………37110,1,2,;1,2,;1,2,NMNMmkmkijjijNjNmxximNNNMmMkK++=+=+====+++==∑∑………3801,,;1,2,,mkijmxijNkK==……=0,1,23901,;1,2,,mkimyiNkK==……=0,1,231016ijcij1i00101,iiccctil=+=…2i10,0,1,ijijcctijl=≠=…1c0c3132333435363738393103.33.3.112001sweetassignmentsaving'depdepddδ=172assignmentbyclusters3cyclicassignmentccIDGiosa(2002)[24]3.3.2C-W1,2,3104,…,133118311122823705534324760454170100445645352240806712010054112154757836531026344801538975513380113405310491035288365696312735751011603253751006583803047111210376561071426746128289549121361484810143899812173553764131CWr(i)3232r(i)i45678910111213minDi32412254363328325648subminDi477035100535135537648r(i)0.680.590.630.540.70.650.80.60.741=0.7r(i)3333i4567911113332r(i)r(i)181012sij(t)(i,j=8,10,12;t=1,2,3)341934S8,10(1)S10,12(3)S8,10(2)S10,12(2)S10,12(1)S8,12(1)S8,12(2)S8,12(3)S8,10(3)Sij(t)221412-31-65-70-70-86-9234810112313d5,10(13)=29d11(13)=53d6,12(13)=8629131510458101311126791233671293145131081211251324106123135351421036542.569.5907116113.564.5849.56491977.56336.51167.539.5591210585.561.5138151.568.536311145821011133691272036114210369542.569.597.77116113.560.7849.56495.31167.539.549.31210585.550.3138151.5703721421011369542.579.797.77116103.360.7849.569.395.31210573.350.3138146.770383145210113697128.7103.360.7847.769.395.312117.373.350.31368.346.77039414521011133697128.7101.9760.7847.782.295.312117.370.97550.3213105145821011133697134.78101.9760.712119.970.97550.3311614582101113369127134.78101.9757VRP145812101113236712935203.3.431311nnmmnm222123312110210/34106123312141085611139127210116413985127369131171241058313140.781013101013313j45678910111213r(j)15291346131872120075111294681013r(i)0.680.590.630.540.70.650.80.60.741751169481210132311458121123671293314315108134132115314581012131123671293511314114455881221110689060341043131301001201461353315336677121299310124115176142125131151121161098821013316317145821136791214582101113367912VRP145812101113236712935203161458211367912105137.588.61381.542.574.43171458210113679121381.546.6774.4243.3.41231337511694812101327511312357113183181521137662.55048.5336799440.542.72291143867.370.7114585