1993 Lagrangean heuristics for location problems

《1993 Lagrangean heuristics for location problems》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、EuropeanJournalofOperationalResearch65(1993)383-399383North-HollandTheoryandMethodologyLagrangeanheuristicsforlocationproblemsJ.E.BeasleyTheManagementSchool,ImperialCollege,LondonSW72AZ,England,UKReceivedSeptember1988;revisedMarch1991Abstract:InthispaperwepresentaframeworkfordevelopingLagrangeanhe

2、uristics(heuristicsbaseduponLagrangeanrelaxationandsubgradientoptimisation)withrespecttolocationproblems.Computa-tionalresultsaregivenforfourdifferentlocationproblems:p-median,uncapacitatedwarehouselocation,capacitatedwarehouselocationandcapacitatedwarehouselocationwithsinglesourcecon-straints.The

3、seresultsindicatethattheframeworkpresentedinthispaperisrobust,i.e.itgivesgoodqualitysolutionsforeachofthesedifferentlocationproblems.Keywords:Lagrangeanheuristic;LocationI.IntroductionAlowerboundfortheaboveprogramcanbefoundbyintroducingaLagrangemultiplierma-Itiswell-knownthatinrecentyearsapopulart

4、rixs(>0)for(2)togettheLagrangeanlowertechniquefortheoptimalsolutionofstructuredboundprogram(LLBP)givenby:pure(ormixed)zero-oneintegerprogramshasbeentheuseoftreesearchprocedureswithminimise(c-sA)x+sb(4)boundstocurtailthesearchbeingfoundviasubjecttox~(0,1).(5)Lagrangeanrelaxationandsubgradientoptimi

5、sa-ItisclearthatLLBPcanbeeasilysolvedtotion(e.g.seeFisher[26,27]).giveasolutionXwithacorrespondinglowerLagrangeanrelaxationandsubgradientoptimi-boundgivenby(c-sA)X+sb.Applyingsubgra-sationcanalsobeusedhowever,inaverysimilardientoptimisation(aniterativeprocedure)gener-manner,toproduceeffectiveheuri

6、sticalgorithmsatesasequenceofLagrangemultipliersinan(lagrangeanheuristics).attempttomaximisethelowerboundobtainedInordertoillustratetheconceptofaLa-fromLLBP.grangeanheuristicconsiderthefollowinggeneralThebasicideabehindaLagrangeanheuristiczero-oneintegerprogram(expressedinmatrixisthattheinformatio

7、ncontainedinLLBPatnotation):eachsubgradientiterationcanbeusedinanminimisecx(1)attempttoconstructafeasiblesolutiontothesubjecttoAx>b,(2)originalproblem(equations(1)-(3)above).Forexample,thesolutionXtoLLBPmayx~(0,a