An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts

《An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、Math.Program.,Ser.A(2008)115:351385DOI10.1007/s10107-007-0178-5FULLLENGTHPAPERAnexactalgorithmforthevehicleroutingproblembasedonthesetpartitioningformulationwithadditionalcutsRobertoBaldacci·NicosChristofides·AristideMingozziReceived:1August2006/Accepted:26June2007/Publi

2、shedonline:1August2007©Springer-Verlag2007AbstractThispaperpresentsanewexactalgorithmfortheCapacitatedVehicleRoutingProblem(CVRP)basedonthesetpartitioningformulationwithadditionalcutsthatcorrespondtocapacityandcliqueinequalities.Theexactalgorithmusesaboundingprocedureth

3、atfindsanearoptimaldualsolutionoftheLP-relaxationoftheresultingmathematicalformulationbycombiningthreedualascentheuristics.Thefirstdualheuristicisbasedontheq-routerelaxationofthesetpartitioningformula-tionoftheCVRP.ThesecondonecombinesLagrangeanrelaxation,pricingandcutgen

4、eration.Thethirdattemptstoclosethedualitygapleftbythefirsttwoproceduresusingaclassicalpricingandcutgenerationtechnique.Thefinaldualsolutionisusedtogenerateareducedproblemcontainingonlytherouteswhosereducedcostsaresmal-lerthanthegapbetweenanupperboundandthelowerboundachiev

5、ed.Theresultingproblemissolvedbyanintegerprogrammingsolver.Computationalresultsoverthemaininstancesfromtheliteratureshowtheeffectivenessoftheproposedalgorithm.KeywordsVehiclerouting·Setpartitioning·Dualascent·ValidinequalitiesMathematicsSubjectClassification(2000)90C27·4

6、9M29·90C39R.Baldacci(B)DEIS,UniversityofBologna,ViaVenezia52,47023Cesena,Italye-mail:rbaldacci@deis.unibo.itN.ChristofidesCentreforQuantitativeFinance,ImperialCollege,ExhibitionRoad,LondonSW72PG,UKe-mail:n.christofides@imperial.ac.ukA.MingozziDepartmentofMathematics,Unive

7、rsityofBologna,ViaSacchi3,47023Cesena,Italye-mail:mingozzi@csr.unibo.it123352R.Baldaccietal.1IntroductionTheCapacitatedVehicleRoutingProblem(CVRP)consideredinthispaperisdescri-bedasfollows.AnundirectedgraphG=(V
,E)isgivenwhereV
={0,1,...,n}isthesetofn+1verticesandEisthe

8、setofedges.Vertex0representsthedepotandthevertexsetV=V
{0}correspondstoncustomers.Anonnegativecostdijisassoci