资源描述：
《Solving Capacitated Vehicle Routing Problem with Branch-and-cut Methods》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、1/28SolvingCapacitatedVehicleRoutingProblemwithBranch-and-cutMethodsMatkoBotinˇcanDepartmentofMathematics,UniversityofZagrebBijeniˇckacesta30,10000Zagreb,CroatiaJJE-mail:mabotinc@math.hrIIJIBackClose2/28Overviewofthepresentation•IntroductiontoVRP•Definitio
2、nofCVRP•Somepolyhedraltheory•Polyhedralcuttingplanealgorithm•Branch-and-cut•IPformulationofCVRP•Exampleofheuristicseparationalgorithm•ImplementationJJIIJIBackClose3/28IntroductiontoVRPTheVehicleRoutingProblem(VRP)—classofproblemsinwhichasetofroutesforaflee
3、tofdeliveryvehiclesbasedatoneorseveraldepotsmustbedeterminedforanumberofcustomers.MainobjectiveofVRP—serveknowncustomerdemandsbyaminimum-costvehicleroutesoriginatingandterminatingatadepot.Everyvehiclehasalimitedcapacity→CapacitatedVRP(CVRP).JJIIJIBackClos
4、e4/28JJIIFigure1:VRPinputJIBackClose5/28JJIIFigure2:VRPoutputJIBackClose6/28DefinitionofCVRPLetG=(V,E)beacompletegraphwithvertexsetV={0,...,n}andedgesetE.•vertices1,...,ncorrespondtothecustomers;•vertex0correspondstothedepot;•anonnegativecostcijisassociate
5、dwitheachedge(i,j)∈Erep-resentingthetravelcostbetweenverticesiandj.(coststructureisassumedtobesymmetric,i.e.cij=cjiandcii=0.)JJIIJIBackClose6/28DefinitionofCVRPLetG=(V,E)beacompletegraphwithvertexsetV={0,...,n}andedgesetE.•vertices1,...,ncorrespondtothecus
6、tomers;•vertex0correspondstothedepot;•anonnegativecostcijisassociatedwitheachedge(i,j)∈Erep-resentingthetravelcostbetweenverticesiandj.(coststructureisassumedtobesymmetric,i.e.cij=cjiandcii=0.)Eachcustomeri∈{1,...,n}isassociatedwithaknowndemandJJdi≥0tobed
7、elivered(thedepothasafictitiousdemandd0=0).IIJIBackClose6/28DefinitionofCVRPLetG=(V,E)beacompletegraphwithvertexsetV={0,...,n}andedgesetE.•vertices1,...,ncorrespondtothecustomers;•vertex0correspondstothedepot;•anonnegativecostcijisassociatedwitheachedge(i,j
8、)∈Erep-resentingthetravelcostbetweenverticesiandj.(coststructureisassumedtobesymmetric,i.e.cij=cjiandcii=0.)Eachcustomeri∈{1,...,n}isassociatedwithaknowndemandJJdi≥0tobedelivered(thedepothasafictitiousdemandd0=0).IIJ
