（应用数学专业论文）k层无容量限制的设施选址问题的一种算法.pdf

k 一层无容量限制的设施选址问题的一种算法 k 一层无容量限制的设施选址问题的一种算法 摘要 选址问题是广泛应用在运筹学和管理科学中的一类重要问题， 并在近似算法方面引起了很大的关注。在k 一层无容量限制的设施选 址问题中，我们假定，为设施的集合，d 为顾客的集合，每个顾客 的需求是已知的，他需要k 个不同的设施为其服务，且每个设施属 于不同的层。这里所说的设施没有容量限制，且建造这些设施对应 一个建造费用，设施给顾客提供服务时也会对应一个服务费用( 连 接费用) ，我们假设这些连接费用满足非负性、对称性和三角不等式。 问题的目标是确定在哪里建造设施，以及每个顾客由哪k 个设施形 成的路径为其服务，才能满足顾客的需求且使总的建造设施的费用 和连接费用之和达到最小。 无容量限制的设施选址问题属于n p - h a r d 问题，人们已经证明 近似算法对于解决长期以来实际中难处理的n p - h a r d 组合优化问题 是一个能产生较优解的有效算法。s h m o y s 首次给出了解决无容量限 制的设施选址问题的常数近似算法，该算法基于线性规划随机取整 以及l i n 和v i t t e r 提出的对偶拟合技术，得到了3 1 6 的近似比。最 近a a r d a l ，c h u d a k ，s h m o y s 又将这一结果进行扩展应用到求解k 一层 无容量限制的设施选址问题中并得到了最多不超过最优值3 倍的结 果。 由于k 一层无容量限制的设施选址问题是n p - h a r d 的，因而对它 的研究大部分还是集中在近似算法上，多年来有关k 一层无容量限制 的设施选址问题的算法研究工作还是非常少见的。因此，结合实践 应用，分析k 一层无容量限制的设施选址问题，进而设计有效的求解 算法成为本文一个重要的研究课题。 本文主要研究了k 一层无容量限制的设施选址问题以及解决设 施选址问题的各种算法，受这些算法的启发，我们设计了解决露一层 无容量限制的设施选址问题的一种随机取整算法。利用该算法时， 首先将原问题进行松弛求解得到松弛问题的最优解，由松弛问题的 最优解通过具体的随机取整算法进而得到原问题的整数解。为了测 试这一算法的性能，我们采用数值计算的方法取k = 2 时用一组算例 进行验证，算例的结果表明：1 在所给的算例中，随着顾客和设施 北京邮电大学硕十研究生论文 个数的不断增加，近似比可能会增大，但总体变化不是很大，即近 似比与顾客和设施的总数没有必然的联系；2 该算法所求得的近似 比均不超过1 4 6 3 且得到的原问题的整数解所对应的函数值大部分 都能较好地接近松弛问题的最优值，同时相对于s h m o y s 的随机取整 算法，该算法能在很大程度上节省计算时间，提高算法的效率，因 此该算法是求解k 一层无容量限制的设施选址问题的一种较好的方 法。 关键词：设施选址近似算法随机取整k 一层 k 一层无容量限制的设施选址问题的一种算法 a na l g o r 【t mf o r ，】 i 硇呕k i j 瓯厂e i i d 汜a l ! a c i t a t e dl 魄c i l i t yl o c a i 】旧叮n p r o b l e m 疵a n t so ft h ef a c i l i t yl o c a t i o np r o b l e mh a v eb e e ns t u d i e d e x t e n s i v e l y i nt h e o p e r a t i o n s r e s e a r c ha n dm a n a g e m e n ts c i e n c e l i t e r a t u r e sa n dh a v er e c e i v e d c o n s i d e r a b l ea t t e n t i o ni nt h ea r e ao f a p p r o x i m a t i o na l g o r i t h l i 塔i n t h ek l e v e lu n c a p a c i t a t e d f a c i l i t y l o c a t i o np r o b l e m ，w ea l eg i v e nas e tfo ff a c i l i t i e s ，as e tdo fc l i e n t s ，1 1 坞d e m a n do fe a c hc l i e n ti sk n o w n 。a n de a c hc l i e n ti st ob es e r v i c e db y as e q u e n c eo fkd i f f e r e n tf a c i l i t i e s ，e a c ho fw h i c hb e l o n g st oad i s t i n c t l e v e l t h e r ea r cn oc a p a c i t yr e s t r i c t i o n so nt h ef a c i h t i 骼t h e r ei sa p o s i t i v ef i x e dc o s to fs e t t i n gu paf a c i l i t y , a n dap 贸u n i tc o s to fs h i p p i n g g o o d sb e t w e e ne a c hp a i ro fl o c a t i o n s 。眙a s s u m et h a tt h e s ed i s t a n c e sa r e a l ln o n n e g a t i v e ，s y m m e t r i ca n ds a t i s f yt h et r i a n g l ei n e q u a l i t y 耽e p r o b l e mi st o 丘n da l la s s i g n m e n to fe a c hc l i e n tt oas e q u e n c eo fk f a c i l i t i e s ，o n ea te a c hl e v e l ，s ot h a tt h ed e m a n do fe a c hc l i e n ti ss a t i s f i e d ， f o rw h i c ht h es u mo ft h es e t u pc o s t sa n dt h e 翻删c o s t si sm i n i m i z e d s i n c et h e u n c a p a c i t a t e df a c i l i t y l o c a t i o np r o b l e mi sn p - h a r d ， a p p r o x i m a t i o na l g o r i t h m s f o ra 只h a r dc o m b i n a t o r i a l o p t i m i z a t i o n p r o b l e m sh a v ep r o v e nt ob eap a r t i c u l a r l ys u c c e s s f u lw a yt og e n e r a t e e x c e l l e n ts o l u t i o n sf o rp r o b l e m sl o n gc o n s i d e r e di n t r a c t a b l ei np r a c t i c e f o rt h eu n c a p a c i t a t e df a c i l i t yl o c a t i o np r o b l e m , t h ef i r s tc o n s t a n t a p p r o x i m a t i o na l g o r i t h mw a sg i v e nb ys h m o y s t h ea l g o r i t h mw a sb a s e d o nl p r o u n d i n ga n dt h ef i l t e r i n gt e c h n i q u ep r o p o s e db yl i na n dv i t t e r a n da c h i e v e da i la p p r o x i m a t i o nf a c t o ro f3 16 眈i sr e s u l tw a sr e c e n t l y e x t e n d e db ya a r d a l ，c h u d a ka n ds h m o y st oa 3 一a p p r o x i m a t i o n a l g o r i t h mf o rt h ek - l e v e lf a c i l i t yl o c a t i o np r o b l e m a st h ek - l e v e lu n c a p a c i t a t e df a c i l i t yl o c a t i o np r o b l e mi sn p h a r d 。 m u c he f f o r th a sb e e nd e v o t e dt od e s i g n i n ga p p r o x i m a t i o na l g o r i t h m sf o r 北京邮电大学硕士研究生论文 l t f o rm a n yy e a r s ，t h e r ei sn os t i l ls a t i s f a c t o r ym e t h o df o rt h ek l e v e l u n c a p a c i t a t e df a c i l i t y l o c a t i o n p r o b l e m s od e s i g n i n g a ne f f e c t i v e a l g o r i t h mi np r a c t i c eh a sb e c o m ea ni m p o r t a n tr e s e a r c ht o p i ci nm y t h e s i s i nt h i sp a p e rw es t u d yt h ek - l e v e lu n c a p a c i t a t e df a c i l i t yl o c a t i o n p r o b l e ma n dt h ea l g o r i t h m sf o rs o l v i n gt h eu n c a p a c i t a t e df a c i l i t y l o c a t i o np r o b l e m i n s p i r e db yt h e s ea l g o r i t h m s ，w ed e s i g nar a n d o m i z e d r o u n d i n ga l g o r i t h mf o rt h e k - l e v e l u n c a p a c i t a t e df a c i l i t yl o c a t i o n p r o b l e m 。缪台c a np r o d u c e a l l o p t i m a l s o l u t i o nf o rt h el i n e a r p r o g r a m m i n gr e l a x a t i o nu s i n gt h ea l g o r i t h ma n dt h e ng e tt h ei n t e g r a l s o l u t i o ni nt h er o u n d i n gs t e p w eg i v ea l le x a m p l eo fk = 2i no r d e rt o t e s tt h ep e r f o r m a n c eo ft h ea l g o r i t h m , t h er e s u l t so ft h ee x a m p l es h o w t h a t ：1 i nt h eg i v e ne x a m p l e ，w i t ht h en u m b e ro fc l i e n t sa n df a c i l i t i e s i n c r e a s i n g ，t h ea p p r o x i m a t er a t i om a yi n c r e a s e ，b u to v e r a l ln o tab i g c h a n g e ，t h a ti s t h ea p p r o x i m a t er a t i oa n dt h et o t a ln u m b e ro fc u s t o m e r s a n df a c i l i t i e sa r en o tn e c e s s a r i l y r e l a t e d ；2 t h ea p p r o x i m a t er a t i o o b t a i n e db yt h e a l g o r i t h mi s n o tm o r et h a n1 4 6 3a n dt h es o l u t i o n a c h i e v e db yt h ea l g o r i t h mi sc l o s et ot h eo p t i m u m c o s t ，a tt h es a m et i m e o u ra l g o r i t h mh a sal o w e rr u n n i n gt i m ea n di m p r o v e st h ee f f i c i e n c yo f t h ea l g o r i t h mc o m p a r e dt ot h ea l g o r i t h mo fs h m o y s s ow ec a np r o v i d e ab e t t e rm e t h o df o rs o l v i n gt h ek l e v e lu n c a p a c i t a t e df a c i l i t yl o c a t i o n p r o b l e m s k e yw o r d s ：f a c i l i t yl o c a t i o n a p p r o x i m a t i o na l g o r i t h m r a n d o m i z e d r o u n d i n g k - l e v e l i i 北京邮电人学硕士研究生论文 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中 不包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或 其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：宣】塾4 生日期：独墨，兰! ! 里 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权 保留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅 和借阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印 或其它复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密 论文注释：本学位论文不属于保密范围，适用本授权书。 本人签名： 导师签名： 日期：塑翌：主! ! 翌 日期：j 竭l 址三一 北京邮电大学硕上研究生论文 第一章绪论 在哪里建造一个超市? 在哪里建造一个仓库? 或者说在一个网络中选择哪 个机器作为路由器? 随着分布产品与供应中心这一商业化的出现，类似这样的 问题存在于社会生活的方方面面。一般地，可以将这些供应中心理解为要建造 的设施，而建造这些设施需要一个固定的建造费用，且建造每个设施之后都有 相应的顾客从该设施取得服务，并对应一个固定的服务费用，我们可以将其理 解为连接费用。对于日常生活中这样的问题我们要解决的是需要建造多少设施 以及在什么位置建造这些设施才能够满足顾客的需求且使得建造设施的费用和 连接费用之和达到最小。这就是本文要研究的设施选址问题。 1 i 设施选址问题的起源 尽可能有效地利用有限的资源，合理配置它们使其发挥最大作用，这是自 然科学中许多学科领域面临的问题。经济领域中许多经济决策也都涉及到设施 选址问题，选址决策是经济或社会活动区位的决定行为，选址决策正确与否主 要取决于选址决策后能否带来经济利益、个人或社会的满足以及社会价值等， 而这一切又都取决于各种影响因素，即如何降低费用( 或成本) 、扩大销售、增 加利润，以及保持最大的稳定性或得到最大的满足度等。能够满足或符合上述 条件的位置选择就可称为是最佳位置。但是，这种经济行为决策具有滞后性， 一旦形成很难再进行更改。 设施选址问题是在运筹学和管理科学领域普遍存在的决策问题。这一问题 是研究如何选择设施的数目和最优位置来为用户提供相应的服务。这里的“设 施”具有广泛的意义，可以是：机场、港口、工厂、零售网点、学校、医院、 汽车站、变电站、计算机的集线器和终端、警报器和卫星等。 选址问题可以应用到交通、物流、零售连锁业、通讯行业、公用设施等很 多领域。设施选址决策过程是一个复杂的经济行为和社会行为过程，它与相关 设施的历史、类型、运营现状、资金、竞争者、经济环境和经营者的能力等有 关。 设施选址的重要性体现在： ( 1 ) 设施选址是一项长期性投资 与建造设施所需的人、财、物、信息等因素相比，位置的选择具有长期性 和稳定性的特点，是各个要素中最不灵活的一个因素。当外部的环境发生变化 k 一层无容量限制的设施选址问题的一种算法 时，其他因素可以随之进行相应的调整。而位置确定后再变动会很困难，因为 建造者不能随意放弃已建成的工程；再者，位置变动会牵一发而动全局，牵涉 到其他因素的变动，比如位置不同，土地价格及开发费用就不同。位置一旦确 定，一般不能轻易更改，否则会带来资源的巨大浪费。 ( 2 ) 位置选择是对市场定位的选择 位置在某种程度上决定了经营网点的客流量多少、顾客购买力大小及消费 结构、网点对潜在顾客的吸引程度及其竞争力的强弱。选址适当，就占有“地 利优势，能吸引大量顾客，生意就能兴旺发达。 ( 3 ) 设旌选址应方便顾客，符合顾客的购物习惯 设施位置的选择直接反映经营网点为顾客服务的观念。网点位置方便顾客， 且符合顾客对不同商品的需求特点和购物习惯，才能吸引顾客，获得理想的经 济、社会效益。 ( 4 ) 设旋位置是制定经营战略及目标的重要依据 各种设施经营战略、目标的确定，首先须考虑所在区域的社会环境、地理 环境、人口状况、交通条件及市政建设等因素，依据这些因素明确目标市场， 按目标顾客构成及需求特点，确定经营商品构成，制定包括广告宣传、服务措 施在内的各项促销策略。 实践证明，商品构成、服务水平基本相同的设施会因位置的不同而使经济 效益出现明显的差异。不理会设施周围的市场及竞争状况，任意或仅凭直观经 验建立起来的设施，是难以经受考验，获得经验效果的。目前应用最广泛的离 散设施选址问题即所谓的无容量限制的设施选址问题，从2 0 世纪6 0 年代开始 对这类问题就有了集中研究。 1 2 设施选址问题及其分类 1 9 6 3 年c o o p e r 正式提出了设施选址问题，即f a c i l i t yl o c a t i o np r o b l e m ， 给定两个集合f = 石，正，z ) 和d = 如，c 2 ，c i ) 。z o 表示在f 上建造设施所 需要的费用，q ，表示顾客c ，d 连接到f 上设施接受服务的费用，简称连接费 用或服务费用。问题的目标是从f 中选择要建造的设施集合彳sf ，使得d 中 每个顾客都有设施为其提供服务并且总的连接费用与建造x 中设施费用之和 达到最小。 最初的设施选址问题对一个位置上可同时存在的设施数量以及每个设施可 2 北京邮电大学硕士研究生论文 同时连接的客户数量没有加以限制，因此在研究过程中人们有时也称其为无容 量限制的设施选址问题，即u n c a p a c i t a t e df a c i l i t yl o c a t i o np r o b l e m ，简称 u f l p 。u f l p 有着广泛的应用背景，因此日渐受到人们的重视。例如：城市公 共设施的建造与选址问题。城市公共设施的选址差别将对居民生活质量，城市 的生产效率等多个方面产生重要的影响，因此在现代社会的新城建设1 日城改造 方面，该问题有着重要的实际意义。再如，物流设施的选址问题，物流设施在 实现企业延迟制造战略、增强企业柔性程度、满足顾客个性化的需求方面扮演 着非常重要的角色，物流设施与企业总部之间、物流设施与顾客之间以及物流 设施相互之间的联系中既有信息的交换，也有物的流动，信息流是可以以光速 传递的，所以物流的速度或效率就成了企业服务水平的瓶颈，而制约物流速度 重要的因素之一就是物流设施的位置。近年来，随着互联网的成熟发展，研究 者又发现了u f l p 在网络环境下的几种新应用，如：路由器和缓冲服务器的网 络分布，数据与通信流量的拥塞控制问题，内容分布网络中副本服务器的安置 问题等。在越来越多新应用的推动下，自上世纪六十年代起，u f l p 逐渐成为 运筹学和计算机科学领域的热点问题之一，在回顾有关它的相关研究进展之前， 我们需要对u f l p 问题以及它的几个重要子问题进行介绍。 ( 1 ) 度量距离空间中的设施选址问题： 在研究u f l p 时，人们通常情况下假定问题中连接费用满足三角不等式， 即所谓的度量距离空间( m e t r i c ) 中的u f l p ，简称m e t r i cu f l p 。 事实上，u f l p 中集合，和d 的元素可以被看作某种距离空间中的点，任 意三点u ，v s ，咋f u d 之间距离满足：q ，+ - c s t 。 ( 2 ) 相关子问题 随着人们对唧问题认识的加深，以及有关它的各种新应用不断涌现， u f l p 衍生出很多子问题，它们同样引起了研究者的兴趣。常见的u f l p 子问题 如下： ( a ) k 中间点问题，简称k m e d i a n 问题， 同样给定集合f = 研，正，z ) 和d = 0 表示顾客c ，d 与f 上设施之间的连接费用。问题目标是选择 x ，但x 中设施的个数不超过k 个，使得d 中顾客与解工中设施连接，总 连接费用与建造设施费用之和最小。这就是k m e d i a n 问题。 ( b ) 弱容量限制设施选址问题 即c a p a c i t a t e df a c i l i t yl o c a t i o np r o b l e mw i t hs o f tc a p a c i t e s 问题，简称 s c f l p ，输入条件同u f l p ，对i 上设施的连接能力加以限制，即i 上每个设施 3 k 一层无容量限制的设施选址问题的一种算法 至多可以同时连接从 0 个顾客，但f 上允许同时存在多个设施，它们的设施费 用均为f 0 。问题目标是确定一组位置以及每个位置上的设施数量，使得d 中 顾客与解中设施连接，总连接费用与设施费用之和最小。 ( c ) 强容量限制设施选址问题 即c a p a e i t a t e df a c i f i t yl o c a t i o np r o b 彪mw i t hh a r dc a p a c i t e s ，简称 h c f l p ，输入条件同u f l p ，i 上只能建造个设施，且它至多可以同时连接 鸬 0 个顾客，问题目标是选择x f ，使得d 中顾客与x 中设施连接，总连 接费用与x 中设施费用之和最小。 ( d ) 鲁棒的设施选址问题 即r o b u s tf a c i l i t yl o c a t i o np r o b l e m ，简称r 弛p ，输入条件同卿。问 题目标是确定x f ，给定一个数z 时，使得d 中仅i d 一，个顾客与x 中距离其 最近的设施连接，总连接费用与建造x 中设施费用之和达到最小。 通过上面对无容量限制的设施选址问题介绍之后，我们接着来看一下关于 设施选址问题的分类，设施选址问题的分类方法很多，不同的评价标准会有不 同的分类方式： ( 1 ) 根据模型目标的多少可以分为单目标选址与多目标选址。 ( 2 ) 根据设施选址的数量分类 可将选址问题分为单一设施选址问题和多设施选址问题。 ( a ) 单一设施选址无需考虑竞争力、设施之间需求的分配、设施成本与数量 之间的关系，主要考虑运输成本。 ( b ) 多设施选址主要考虑到设施的建造成本与运输成本之间的权衡。因此， 单一设施选址问题相比多设施选址问题而言，模型与求解都比较简单。 ( 3 ) 根据设施的属性可分为受欢迎的设施选址与不受欢迎的设施选址。 ( 4 ) 根据设施是分层的还是不分层的分为分层选址问题和单层选址问题。 ( 5 ) 根据设施允许安置的空间或是决策变量的特征，可将设施选址问题分 为连续选址、网络选址和离散选址，而这三种选址问题有如下所述： ( a ) 连续选址 又称为平面选址，它允许在可行的某一平面内连续选取位置值。平面上连 续选址模型主要有两大特征：一是决策变量是连续的，即可以将设施建造在平 面上的任何一点；二是采用适当的度量方法度量距离，如比较常用的厶距离( 也 称直线距离) 、厶距离( 也称欧氏距离) 和瓦模距离。韦伯提出的w e b e r 问题就是 一个典型的连续选址问题。 c o ) 离散选址 离散选址问题即候选设施点的区位是离散的，决策变量是在有限点集中取 4 北京邮电人学硕士研究生论文 值。此类问题往往假定设施点与需求点都位于网格节点上。其中，需求点的区 位是确定的，需求点有需求量，需求点与候选设施点之间有连线( 如交通线路、 网线) 相连。最经典的无容量限制的设施选址问题( t h eu n c a p a c i t a t e df a c i l i t y l o c a t i o np r o b l e m ，卿) ，有容量限制的设施选址问题( t h ec a p a c i t a t e d f a c i l i t yl o c a t i o np r o b l e m ，c f l p ) 等都是离散选址问题。 ( c ) 网络选址 网络选址问题在物流设施规划、通讯系统设计等诸多领域都有十分广阔的 应用背景。网络选址问题要求在某个网络上设置若干个服务中心，以达到特定 的目的。例如，城市中设置若干个1 2 0 救护站，以使得到达最远的需要救护的 病人的时间尽可能的短；又如物流配送中心的选址，以便配送商品到达所有超 市的总的距离最短。网络选址允许在指定网络的定点与边上选址，而离散选址 只允许在指定的一些离散点集上选址，两者主要用组合优化的方法进行研究。 网络选址下的中值问题、覆盖问题、中心问题是网络选址的三个基础选址问题。 ( 1 ) 根据选址问题的决策策略分类 决策策略是指为达到决策总目标所采取的制定决策的指导思想和行动。即 如何在选址问题的备选方案中选择一个合适的方案。 ( a ) 最优化策略 最优化是采用统计决策论和运筹学的方法，采用结构化的优化模式和步骤： 首先确定一个明确的目标函数，以便测定决策结果的优劣；其次拟出所有的备 选方案；再次建立数学模型，把目标函数备选方案中一些变量的关系定量表述 清楚；最后确定求解最优解的算法，以便从备选方案中选出一个按目标函数来 看是最佳的方案。大多数设施选址的理论模型属于这种。 ( b ) 满意化策略 由于种种条件的限制，无论个体决策还是组织决策，大多数都是寻找和选 择满意方案的过程；只有在例外情况下，才是选择最优方案的过程。这是因为 客观世界的极端复杂性和局限性。面对这种复杂性，在设施选址过程中，对于 那些得不到最优解的问题，只能寻求能产生足够好的答案的求解过程。 ( c ) 平衡策略 有些物流设施选址决策问题所面临的是多元化的局面，目标是多元的，价 值标准是多元的，影响决策成果的因素是多元的等等。当决策目标或价值标准 多元化时，由于无法用单一明确的价值尺度去比较不同的备选方案，而且极少 有能够在所有的目标或价值标准上都达到最好的“绝对最优方案 ，实际上所拟 定的一些备选方案中都“各有千秋。此时，除了采用平衡策略外就别无其他策 略。在多目标决策中，从非劣解集合中寻求最终解的各种办法实际上采用的都 5 k 一层无容量限制的设施选址问题的一种算法 是平衡策略。 ( 2 ) 根据选址约束分类 根据选址问题的约束种类，可以分为有能力约束的选址问题和无能力约束 的选址问题，以及有不可行区域与无不可行区域的选址问题。 ( a ) 有能力约束与无能力约束 如果设施的能力没有限制，那么选址问题就是无能力约束的选址问题；反 之，就是有能力约束的选址问题。 ( b ) 不可行区域约束 如果在目标区域内有些区域不适合作为选址地点，那么这个选址问题就包 含了不可行区域的约束。 1 3 设施选址问题的研究进展 u f l p 及其子问题的研究成果最早常见于六七十年代运筹学领域的各种文 献中7 】。起初，研究者们试图利用各种直观启发式方法得到问题的最优解， 如贪心方法和搜索交换法。然而，实际表明利用这些求解策略不一定总是可以 找到问题的最优解。后来，人们又从最坏情况分析、概率分析、多面体组合数 学和经验启发式方法等方面对它们进行了研究。 从复杂性角度考虑，u f l p 被证明是异常难解的n p h a r d 组合优化问题， 这表明在多项式时间内没有算法可以找到它的最优解。该结论一经得出，计算 机科学领域的众多算法工作者随即对它产生了浓厚的兴趣，自上世纪六十年代 起，他们利用各种技术设计了卿的多种求解算法，详见文献【l 引，其中以近 似算法研究成果最为突出。 1 9 8 2 年，h o c h b a u m 1 9 】首次研究了一般距离空间中的u f l p ，即问题中连 接费用不满足三角不等式，利用贪心技术设计了u f l p 正式提出后的第一个近 似算法，算法的平均近似度达到o ( 1 0 9 m ) ，其中m 是问题实例设施集合中的元 素数。在沉寂了十五年之后，1 9 9 7 年s h m o y s 等人【2 0 】利用l i n 和v i t t e r 2 1 】的 f i l t e r i n g 技术和线性规划随机取整方法，设计了m e t r i c ( 秘，p 的第一个常数因子 近似算法，算法近似度3 1 6 ；此后，g u h a 和k h u l l e r 2 2 】利用增广贪心技术将 s h m o y s 算法的近似度改进到2 4 0 8 ；c h u d a k 和s h m o y s 1 8 】【2 3 1 再次使用线性规划 随机取整方法设计了近似度1 + 2 e = 1 7 3 6 的m e t r i c 唧多项式时间近似算 法。由于受到求解线性规划的制约，当问题实例规模较大时，上述算法的运行 时间漫长，导致很多情况下不能满足实际应用的需求。 利用原始与对偶方法，1 9 9 9 年j a i n 和v a z i r a n i1 2 4 1 1 2 5 】设计了第一个基于该方 6 北京邮电大学硕上研究生论文 法的m e t r i cu f l p 拟线性时间近似算法，算法近似度是3 ，它同样可以用来求解 卿的若干子问题，如f a u r t o l e r a n tf a c i l i t yl o c a t i o n 问题【2 6 j ，f a c i l i t y l o c a t i o nw i t ho u t l i e r s 问题f 2 7 1 ，七一m e d i a n 问题【2 8 】【2 9 】【3 0 】；2 0 0 0 年m e t t u 和 p l a x t o n 3 1 】借助贪心技术设计了另一个近似度为3 的m e t r i cu f l p 算法，简称 m p 算法，他们改进了彪砌和v a z i r a n i 算法的时间复杂度，此后a r c h e r ， r a j a g o p a l a n 和s h m o y s 3 2 】证明脚算法的本质仍基于原始与对偶算法；2 0 0 1 年，t h o r u p 3 3 】证明在具有m 条边的二分图上，u f l p 可以利用m p 算法在伙聊) 的时间内求解。 局部搜索方法作为算法设计与分析的基本常用技术，同样也被人们用来设 计各种u f l p 算法。1 9 6 3 年k u e h n 和h a m b u r g e r 【l 】基于此方法设计了一个 u f l p 算法，1 9 9 8 年k o r u p o l u 等人【3 4 】证明该算法的时间复杂度和近似度分别达 到o ( n 6l o g n 8 ) 和( 5 + 6 ) ，其中占 0 ，甩= m a x ( i v l ，i c l ) ；2 0 0 1 年，a r y a 等人【3 5 】 进一步研究并给出了严格的分析，证明k u e h n 和h a m b u r g e r 的局部搜索算法的 近似度可以达到3 + s ；1 9 9 9 年c h a r i k a r 和g u h a 2 9 1 利用一个贪心局部搜索过 程，设计实现了m e t r i cu f l p 近似度2 4 1 4 的拟线性时间近似算法，他们同时尝 试将c o s ts c a l i n g 、线性规划随机取整、原始与对偶方法、局部搜索和增广贪心 技术进行各种组合，期望设计得到更加出色的u f l p 近似算法，终于，1 9 9 9 年 利用c o s ts c a l i n g 和增广贪心技术，他们将c h u d a k 和s h m o y s 【1 8 】【2 3 】的算法结果 近似度由1 7 3 6 改进到1 7 2 8 ，与此同时证明使用类似方法可以把施加和 v a z i r a n i 2 4 】【2 5 】算法的结果近似度由3 改进到1 8 5 3 。 研究人员也曾试图利用其他技术设计更好的u f l p 及其子问题的近似算 法。2 0 0 2 年，s v i r i d e n k o 3 6 】基于线性规划取整技术，利用p i p a g er o u n d i n g 方法 设计了m e t r i cu f l p 近似度1 5 8 2 的多项式时间算法。对于网络应用环境中出现 的一类u f l p 子问题，即o n l i n e u f l p ，其中顾客集合c 不固定，随着时间的推 移，c 中顾客可以增加、减少的情况，m e y e r s o n 3 7 】贝i j 给出了一个随机竞争算法。 2 0 0 2 年，m a h d i a n 等人【3 8 】又利用c o s ts c a l i n g 和增广贪心技术设计了 m e t r i cu f l p 的近似度1 5 2 的多项式时间算法。g u h a 和k h u l l e r1 3 9 】证明了 m e t r i cu f l p 是m a xs n p h a r d 的，且不存在求解m e t r i cu f l p 的近似性能比小 于1 4 6 3 的多项式时间算法，否则n p d t i m e ( n d ( 1 a 9 1 0 9 ”) ，即任意胛问题在 o ( 1 0 9 l o g n ) 的多项式时间内可以求解。这一结果揭示了m e t r i c 卿的复杂性， 使得研究人员对它有了更进一步的认识，同时也为许多新研究成果的诞生奠定 了基础。 下表1 1 总结了u f l p 的一些重要近似算法及研究结果，表中所列算法的时 间复杂度依赖问题实例的输入大小。即m = o ( i v l ，l c i ) ，为了方便比较，假定 7 k 一层无容量限制的设施选址问题的一种算法 f i = d ( i c i ) ，个别算法的时间复杂度与求解相应线性规划问题的时间有关。 表1 1 ：部分已知汜已p 近似算法研究结果 p 文献方法运行时间 i n n c h o c h b 删m 【1 9 】 贪心算法 o ( m l o g m ) 3 1 6 s h m o y s ，t a r d o s 【2 0 】；三魂，玩f 幼【2 l 】随机取整，滤除算法依赖求解线性规划 2 4 1 c r u h a ，k h u l l e r 1 3 9 1 随机取整，贪婪算法 依赖求解线性规划 1 7 3 6 c h u d a k ，s h m o y s 【2 3 】 随机取整依赖求解线性规划 5 k o r u p o l u ，p l a x t o n ，r a j a r a m a n 3 4 1 局部搜索技术 o ( m 3l o g m ) 3 j a n ，v a z i r a n i 4 0 l 原始对偶算法 o ( m l o g m ) 3 m e t t u ，p l a x t o n 3 q 贪心算法 o ( m l o g m ) 原始对偶算法， o ( m l 5 ) 1 8 5 3 c h a r i k a r ，g u h a 【2 9 】 贪婪算法 随机取整，原始对偶 1 7 2 8 c h a r i k a r ，g u h a 1 2 9 1 依赖求解线性规划 算法，贪婪算法 1 8 6 1 m a h d i a n ，m a r k a k i s ，s a b e r i t 4 1 1 对偶拟合 o ( m l o g m ) 1 6 l 比切，m a h d i a n ，s a b e r i 4 2 1 对偶拟合，贪婪算法 o ( m l o g m ) 对偶拟合， 1 5 8 2s v i r i d e n k o 3 6 1 依赖求解线性规划 线性规划取整 1 5 2 m a h d i a n ，y e , z h a n g 【3 3 】 对偶拟合，贪婪算法 o ( m l o g m ) 1 5 b y r k a 【4 3 1 随机取整，对偶拟合 o ( m l o g m ) 2 0 0 3 年驰【4 3 】利用c o s t 跏慨和增广贪心技术并结合国豁f 4 2 】方法得到 了u f l p 的1 5 0 一近似比，这是目前在m e t r i c 空间中u f l p 最好的近似算法研究 结果。值得注意的是，1 5 0 的近似比已经非常接近于g u h a 和k h u l l e r 给出的 m e t r i c 卿1 4 6 3 的不可近似结果，这说明算法研究者对该问题的认识水平已 经具有相当的深度。 8 北京邮电大学硕上研究生论文 1 4 设施选址问题的研究意义 计算机理论科学领域存在大量的尸一h a r d 问题，这类问题在当前计算机模 型一图灵机模型的体系结构范围内，在p 脚的假设下，被认为是不能计算的： 其最优解的计算时间是随着实例输入规模成指数速度增长，不能在多项式时问 内完成。为解决这些问题，一方面人们试图摆脱当前计算机体系的束缚，研究 新一代计算机体系结构，如量子计算机、生物计算机等；另一方面仍在当前体 系结构下，从算法分析设计的方法上寻找解决这类问题的可行办法。其中一种 主要方法是降低解的精度，在可以接受的时间内寻求近似解，即设计n p h a r d 问题的近似算法。本文就是针对k 一层无容量限制的设施选址问题给出一种在很 大程度上可以节省计算时间的近似算法，并通过算例验证该算法也具有较好的 性能。 近似算法是求解p h a r d 问题的有效方法之一，我们称这样一个近似算法 为p 一近似算法，如果该算法在解决具有非负目标函数的最小化问题时，能够 在多项式时间内得到一个可行解，且可行解对应的费用最多不超过最优值对应 的费用的p 倍。对近似算法的研究可以从正反两方面开展，即一方面设计求解 问题的优秀近似算法，并通过理论证明给出算法的近似性能比；另一方面，分 析给定问题的复杂性，证明问题算法的不可近似性结果。上述两方面的研究成 果对于认识问题，设计更加有效的近似算法至关重要。 自从提出了k 一层无容量限制的设施选址问题，由于度量空间下的 k l f l p 也是胛一j j l 口以的，因而对它的研究工作也是集中在近似算法上。相 比度量空间中的u f l p 问题研究成果，k 一层无容量限制的设施选址问题 ( t h ek 一，胱，u n c a p a c i t a t e df a c i l i t yl o c a t i o np r o b l e mk l f l p ) 的算法研究工作 多年来还是非常少见的。因此，结合实践应用，分析k 一层无容量限制的设施选 址问题，进而设计有效的求解算法成为一个重要的研究课题。本文就是在研究 k 一层无容量限制的设施选址问题的基础上，通过学习已有的各种近似算法，受 这些算法的启发给出了求解k 一层无容量限制的设施选址问题的一个快速有效 的算法，并取k = 2 时给出一组算例来验证该算法的性能，如果利用该算法所求 得的性能比小于不可近似比1 4 6 3 时，我们则认为该算法具有不错的性能比。