κ-層有容量約束設(shè)施選址問題的近似算法.pdf

1、北京工業(yè)大學(xué)碩士學(xué)位論文κ層有容量約束設(shè)施選址問題的近似算法姓名：王星申請(qǐng)學(xué)位級(jí)別：碩士專業(yè)：運(yùn)籌學(xué)與控制論指導(dǎo)教師：薛毅徐大川20090501北京工業(yè)大學(xué)理學(xué)碩士學(xué)位論文AbstractThisthesisconsidersthe忌levelcapacitatedfacilitylocationproblem(k—CFLP)The后一CFLPisNP—hardandunifiesseveralexistingfacilitylocat

2、ionproblemswhichhavebeenstudiedfromapproximationalgorithmpointsofview，suchastheuncapacitatedfacilitylocationproblem(UFLP)，thellevelcapacitatedfacilitylocationproblem(1一CFLP)andthekleveluncapacitatedfacilitylocationproble

3、m(七一FLP)Inthisthesis，weintroducethemultiexchangelocalsearchalgorithm(MLS)andLP—basedapproximationalgorithmforthe1一CFLP；wealsointroducetheparameterizedpathreductionandgreedyalgorithm，thesplitandrecursivepathalgorithmandth

4、erandomizedroundingalgorithmforthe尼一FLPInthisthesis，wepresentacombinatorialapproximationalgorithmforthe尼一CFLPAttheprocessofalgorithmdesignfirstlyforanyinstanceMofthe后一CFLP，wedefineaninstanceMk一1of(k—1)一CFLPandallinstance

5、Sof1一CFLP；secondly，solveSbytheMLSalgorithmtoobtainafeasiblesolutionforS，solveMk一1recursivelytoobtainafeasiblesolutionforMk一1；thirdly，foreachclient歹∈Dconstructatransportationproblem，bysolvingthisproblem，weseehowtotransfer

6、thedemandfromthefirstleveltothepathset；finallyconstructasolutionforinstanceMAttheprocessofalgorithmanalysis，weapplytherecursivemethodandobtainthefirst(combinatorial)approximationalgorithmwithaperformancefactorofk2、／畫FF翻F