（计算机软件与理论专业论文）多产品选址问题的算法设计与分析.pdf

摘要 选址问题是组合优化领域中的一类重要问题，它是对于一些网络 服务器、核电站或者物流中心等有限且重要的资源进行选址决策，在 生产管理与调度，网络通信，理论计算机科学等方面有广泛的应用。 本文研究了设施选址中的一类模型：多产品选址模型 ( k p u f l p ) 。h u a n g 和l i ( 2 0 0 7 ) 首先提出了一类在度量空间特性 下的多产品选址模型，并给出了一个近似比不超过2 k 一1 的启发式算 法。本文的主要工作如下： 第一章是绪论部分，简单地介绍了选址问题的相关定义、记号及 相关知识，描述了多产品选址模型的一些特性。 第二章研究了多产品选址问题的整数及线性模型。对于 k p u f l p n ( k 2 ) ，提出了一个改进的算法m e ，并证明了该算法最 坏性能比不超过昙七一1 。另外，对于算法m e 求解2 - p u f l p n ，给出 z 了2 是该算法紧界的证明。并讨论了它的线性规划问题的松驰的整数 间隙。 第三章对两类算法落到树结构上的性能进行了分析和讨论，通过 找到一个反例，给出了算法m e 的解落到树结构上不是最优解的推理 过程。 文章末，对工厂选址问题做出总结和研究展望。 关键词：选址问题，近似算法，最坏性能比，整性间隙，紧界 a b s t r a c t l o c a t i o np r o b l e mi sak i n do fi m p o r t a n tc o m b i n a t o r i a lo p t i m i z a t i o n p r o b l e ma n dh a v ee x t e n s i v ea p p l i c a t i o n sw i t h i np r o d u c t i o nm a n a g e m e n t ， n e t w o r kc o m m u n i c a t i o na n dc o m p u t e rt h e o r y i tc a nm a k ed e c i s i o na b o u t t h el o c a t i o no ft h en e t w o r ks e r v e r ，n u c l e a rp o w e rp l a n ta n dl o g i s t i c s c e n t e r w es t u d y k - p r o d u c t i o nu 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 ( k p u f l p ) w h i c hw a sf i r s t l yp r o p o s e db yh u a n ga n dl i ( 2 0 0 7 ) b a s e do n m e t r i cs p a c ei nt h i sp a p e r h u a n ga n dl ia l s os h o wa2 k 1h e u r i s t i c a l g o r i t h m i ns e c t i o no n e ，t h i sp a p e rb r i e f l yi n t r o d u c e ss o m ed e f i n i t i o n s ， n o t a t i o n sa n dr e l a t e di n f o r m a t i o na b o u t f a c i l i t yl o c a t i o na n dd e s c r i b e s s e v e r a lc h a r a c t e r i s t i c so fk p u f l p n s e c t i o nt w om a i n l ys t u d i e st h ei n t e g e rm o d e la n dl i n e a rm o d e lo f k - p r o d u c tu n c a p a c i t a t e dl 。c a t i o np r 。b l e m a 三七一1i m p r 。v e da l g 。r i t h m f o rs o l v i n gt h ek - p u f l p n ( k 2 ) h a sb e e np r o p o s e db yu s w ea l s o d i s c u s st h ei n t e g r a l i t yg a po ft h e2 - p u f l p n sl i n e a rp r o g r a m m i n g i nt h ee n d ，w e s u m m a r ya n dp r o s p e c tt h ef a c i l i t yl o c a t i o np r o b l e m k e yw o r d s ：l o c a t i o np r o b l e m ，a p p r o x i m a t i o na l g o r i t h m ，w o r s t c a s e p e r f o r m a n c er a t i o ，i n t e g r a l i t yg a p ，t i g h tb o u n d 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不含任何其他个人或集体已经发表或撰写过的作品成果。对本文的 研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人 完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 沙降易月f 砂日 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权湖南师范大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密口。 ( 请在以上相应方框内打“”) 作者签名： 国次日期：加繇备6 月l 、日 剥瞄红翩嗍游6 刖 | 多产品一l ：厂选址问题的算法设计与分析 1 绪论 本章主要介绍选址址问题的研究背景、研究现状以及分类。并对 选址问题这类n p 问题的常用分析方法进行了介绍。 1 1 设施选址问题 选址问题( l o c a t i o np r o b l e m ) 是组合优化中一类有着重要理论 意义和广泛实际背景的问题，其实质是寻求对需求完成分配任务的合 理安排以得到某种意义下的最优结果。它在网络设施的安放、网格服 务点的分布、核电站的建址等诸多方面有着大量的应用。同时，它与 理论计算机科学和离散组合数学也存在着密切的联系。近几十年来， 选址问题得到了运筹学、工程学、管理学和计算机科学界的极大关注， 并且随着对经典选址问题研究的日趋深入，大量具有实际应用背景的 新问题不断涌现。设施选址是众多选址问题的一个重要研究领域。本 文所研究的多产品选址问题就是属于其范畴中。研究方法主要依靠组 合优化、运筹学等计量方法，这也是设施选址与其他选址问题的重要 区别。 。 设施选址是一个十分古老而又经典的问题，古代的选址决策往往 以经验、制度为依据，缺乏科学性。1 9 0 9 年德国学者韦伯第一篇选址 论文的发表标志着设施选址问题进入到科学研究的时代。在其发展的 百年历史上，各时期研究侧重点各有不同。按时间可分为三个阶段： 硕十学位论文 ( 1 ) 零散研究阶段( 1 9 0 9 1 9 6 0 年) 。该阶段研究侧重于解决生产、 生活中的各种实际问题，内容零散。早在19 0 9 年德国经济学家韦伯 ( a l f r e dw e b e r ) 在其工业区位论文中研究如何使单个仓库到不同客 户总距离最短。该文是最早的设施选址论文。另一个早期设施选址问 题研究学者h o t e l l i n g 在其1 9 2 9 年发表的论文【3 6 】中考虑两个竞争供应 商在一条直线上的区位选择并构建选址模型。随后s m i t h i e s ( 1 9 4 1 ) 【3 刀、 s t e v e n s ( 1 9 6 1 ) 【3 8 】对此问题进行了更深入的研究。上世纪5 0 年代，越 来越多的研究者偏重于设施选址的实际应用，包括电话网络程控交换 设备选址、网络服务网点的分布与设计、铁路货运编组站选址等。( 2 ) 系统研究阶段( 1 9 6 0 一1 9 8 0 ) 。h a k i m i 于1 9 6 4 年发表的关于网络多设 施选址的论文【3 9 】是设施选址问题发展为一个系统、科学理论的里程 碑。此后，选址问题被引入一个更宽广的领域，包括生产中心选址、 交通枢纽选址、变电站选址等等。研究方法也更集中于数学分析、运 筹学等。( 3 ) 不确定性问题研究阶段( 1 9 8 0 至今) 。进入上世纪8 0 年代，随着市场变化加剧，实际生产、生活中运输时间、需求量、需 求空间分布以及设施建造成本等输入变量不确定性加强，以往静态、 确定性选址模型与方法已不能适应选址研究的发展。随机选址问题已 成为众多学者关注的焦点。l o u v e a u x ( 1 9 8 6 ) 【4 0 】、w e a v e r 与c h u r c h ( 1 9 8 3 ) 【4 1 】等学者在对不确定中值问题研究时均将运输时间与需求设 为随机变量。b e r m a n 与o d o n i ( 19 8 2 ) 【4 2 1 、b e r m a n 与l e b l a n c ( 19 8 4 ) 4 3 1 将运输时间或运输成本设为不确定系统变量研究随机网络的交通问 题。 多产口1i ：厂选址问题的算法设计与分析 近些年来，对于设施选址问题大致分为两大发展方向【5 2 】：( 1 ) 模 型构建( 2 ) 算法设计。首先在构建模型上，a ) 有很多的研究者结合 现代市场理念与思想构建模型。供应链管理思想的出现为设施选址问 题提供了新的研究角度。与过去选址文章只考虑单方利益不同，供应 链管理的目标是降低“整条链”的运营成本，在“链与链”的现代市场竞 争中取得优势。研究者结合库存论、供应链利益协调机制，建立多级 的选址模型。b ) 对模型的假设多样化。在很多情况下，需求是指数分 布或是离散分布，如一些服务系统的需求为指数分布。对于交通运输 时间的不确定性，大多数学者假设运输时间为离散概率分布，这种假 设使研究对象理论化、抽象化，便于计算，但同时也有不足，即缺乏 精确性。c ) 模型系统参量内涵应更具体、明确。有些模型系统参量内 涵过于宽泛，一个变量表示运输成本等多项内容，虽简化了模型，但 和实际情况不太吻合。算法设计方面，a ) 现有的算法不能满足求解某 些复杂选址问题的需要，因此有必要提供有效的快速算法。b ) 在积极 寻找其他研究方法的同时，继续对算法复杂性进行研究，构造快速算 法。选址问题很多是n p 难题，解决这一问题的关键在于寻找更具一 般性的、高效的启发式算法。 1 2 选址问题的分类和特点 离散选址问题即设施点被选址的地点是离散的。此类问题往往设 定设施点与需求点都位于在网络节点上，需求点区位确定，需求点与 其他一些节点作为设施被选点，需求点与设施被选点之间有连线相 硕十学佗论文 连。离散选址问题纷繁复杂，随着实际问题的变化，模型也有很大的 不同。b r a n d e a u ( 1 9 8 9 ) 【1 1 1 对离散选址问题进行了分类，在国外学者 的研究基础上，我们认为主要的离散选址问题有：中值问题、覆盖问 题、中心问题、多产品问题、动态选址问题、路径选址、多目标选址 与网络中心选址问题 1 2 1 离散选址问题的分类 1 1 中值问题 h a k i m i ( 1 9 6 4 ) 最早提出中值问题，中值问题的目标是使所有 需求点到设施的平均权重距离最短( 距离也可用交通、运输时间表 示) 。其文章假设每个节点是需求点同时也是设施点，网络中的线路 表示交通线路。作者提出对于任一给定设施数p ，总存在至少一个最 优解使得总距离最小。c o o p e r 的模型不仅在网络中选择设施区位， 而且确定设施在网络中的服务范围。g o l d m a n 研究在树状网上如何选 择一个设施点的中值问题，具体方法为首先任选一个节点，计算该点 的权重是否超过所有权重一半，如果是则为中值点。如果不是则该点 t 权重被计算在相邻点上，直到找到中值点为止。 在上世纪7 0 年代末以前，绝大多数学者构建的中值问题模型都 为确定型，即客户需求、运输时间、建设成本等系统变量为确定值， 这一假设与实际情况往往不符。而后很多学者将确定性模型拓展为不 确定模型，假设上述系统变量为随机变量，以随机需求与运输时间的 研究为主。中值问题随机模型主要可分为概率模型、排队模型和情景 多产品t 厂选址问题的算法设计与分析 模型三类。( 1 ) 概率模型。概率模型可分为需求随机模型与交通运输 随机模型两类( 对这两类模型的具体研究，可参考m i r c h a n d a n i ( 1 9 8 0 ) t 4 8 】 和m i r c h a n d a n i 与o d o n i ( 19 7 9 ) t 4 9 】的文献资料) 。( 2 ) 情景模型。情景 模型是研究在一系列具有发生概率的情况下的设施可靠区位的选址 问题。有些文献假设所有情景发生的概率是相等，一些文献中的情景 概率需要计算得出。通过比较情景条件下的最优值与可靠值( r o b u s t ) 得出遗憾值( r e g r e t ) 。( 3 ) 排队模型。概率模型中的一些参量引进排队 模型理论。l a r s o n 5 0 】首先将排队论应用到选址模型中，主要研究紧急 救助组织的车辆区位与服务范围。作者假设区内、区际间呼救时间呈 p o i s s o n 概率分布、服务时间服从指数分布，构建一个多服务者排队 系统。b r a n d e a u 与c h i u t 5 1 1 研究单个设施的随机排队区位问题，考虑 排队与交通时间延迟情况下服务客户的最短反应时间。 2 ) 覆盖问题 中值问题的应用非常广泛，但是在某些情况下以降低总运输成本 ( 总距离) 作为目标不太适宜。例如城市的消防车、医疗急救车辆要 求必须在特定时间内到达事故现场，此类设施点必须布置在与需求点 特定距离之内才能满足特别的需要。对覆盖问题的研究分两类：完全 覆盖问题与最大覆盖问题。完全覆盖与最大覆盖问题都假设网络上设 施被选点是有限的，但即使网络上的被选点是连接( 无限) ，该问题 也可转化为有限被选点问题研究。 3 、) 中心问题 完全覆盖问题目标方程求在特定距离( 时间) 内满足所有需求应 硕十学何论文 修建的最小设施数。与此不同，中心问题虽然也要求满足所有需求， 但设施数是给定，求任一需求点到与它最近设施的最小最大距离，即 最小最大化问题。 4 ) 多产品问题 需求点对服务与产品的需求往往不是单一的，零售商通常要提供 多种产品才能满足顾客或企业的正常需要。g e o f f r i o n 与g r a v e s 建立 了多产品的二级选址模型，即不同产品从工厂到分销商再到零售商 ( 需求点) 的物流过程n 3 f 。 5 ) 动态选址问题 一般而言，分销中心、配送中心、消防站、急救中心等设施一旦 修建要服务很长时间。但影响选址决策的因素如需求、运输成本是变 化的，再次规划、建设新的设施点成本太高，动态选址问题应运而生。 b a l l o u 在于1 9 6 8 年发表了第一篇关于动态选址问题文章m ，文章假 设在不同时段内设施可重新选址。他利用动态规划确定了一系列潜在 的最优仓库区位，这些仓库区位能最大化其服务区域。d r e z n e r 与 w e s o l o w s k y 1 4 1 的研究侧重于城市人口的变化对设施区位的影响，作者 假设随时间变化的城市人口的增长是可预测的( 但是用确定性的方 法) ，目标方程求为特定区域服务的单设施最小期望建设成本，同时 检验了不同时期重新布置设施点的概率。文章不仅重新选择设施区 位，而且确定重新选址的时间。上述模型都研究网络中单设施区位问 题，后来很多学者考虑多设旌选址的动态规划。s c o t t 1 5 3 研究问题为在 每个时段内布置一个设施点，一旦设施点被选定，它只为一个特定的 多产品t ：厂选址问题的算法设计与分析 区域服务。w e s o l o w s k k y 与t r u s c o t t 1 6 1 扩展了上述模型，决策者可根 据预测的需求变化重新布置设施点。作者构建了整数规划模型，在约 束条件中加上了一个时期内可重新选址的次数。s h e p p a r d 1 刀从更广泛 的时间与空间领域对动态选址问题进行研究。他的模型不仅要确定多 个设施的区位，而且确定设施的规模，还要确定修建设施的时间与扩 建时间。e r l e n k o t t e r 18 】的文章侧重于算法，他比较了几种启发式算法 求解动态规划的有效性，认为不同的启发式算法相结合对多阶段选址 问题求解是非常有效的。研究动态选址问题的学者还有 f r a n t z e s k a k i s 19 1 、s h u l m a n 2 0 】等。 6 ) 多目标选址问题 通常情况下，不论是公共部门还是私人企业，囿于资源所限，设 施选址都不会只设定单一目标，经常将运输( 交通成本) 、投资成本 ( 建设成本) 、客户服务水平( 在特定时间、距离为客户提供服务) 、 设施能力的“平衡利用”等目标综合考虑。构建此类模型最常用的方 式是将成本最小化作为总目标，将要实现的目标做为限制条件。h e l l e r ( 1 9 8 9 ) 【4 5 1 研究医疗服务设施的中值问题，平均运输成本最小己不是 唯一目标，同时必须在特定时间内为病人提供服务。r e v e l l e 与 l a p o r t e 2 1 1 所构建的模型中有两个目标：最小化成本与特定时间内最大 程度满足需求。 7 ) 路径选址问题 路径选址问题的核心就是要寻找最佳的车辆安排时间表、路径同 时确定设施数量与区位。其目标就是使货物处于连续、不间断地运输 硕十学位论文 中，并降低成本，增加效益。最早进行路径选址问题概念性研究的是 v o n b o v e n t e r 等，虽然早期的研究是对综合路径选址问题的研究，但 将选址和运输问题隔离开来。l a t e r 和c o o p e r 认识到运输一选址问题 主要是找到供应商的最佳位置和从源头到目的地的最小的运输成本， t a p i e r o 综合了有关时间的复杂因素，建立了运输一选址模型，使该 项研究更精确、更深入。w a t s o n g a n d y 和d o h r n 是最先在运输一选 址问题框架内考虑多仓库车辆路径种类的学者，在其模型中增加了巡 回的任务，使路径选址疸问题求解比一般求解更复杂乜2 。2 引。 8 ) 网络中心选址问题 随着网络技术的发展，网络中心选址问题也受到很多学者的关 注。网络中心选址问题可描述为在无向网络中所有节点集合为k ，网 络中心为一个子集，另一个子集为终端( 非网络中心) ，所有终端与 网络中心相连。任何一条边如果有信息流通过，则这条边的端点至少 有一个为网络中心。与中值问题相似，此类模型目标寻求平均距离( 时 间) 最短。与中值问题区别在于信息流在网络中心之间的传输费用与 其在网络中心与终端间的传输费用不等。k l i n c e w i c z 嘶1 ，e r n s t 与 k r i s h n a m o o r t h y 2 6 - 与m a y e r 和w a g n e r 他7 3 研究无能力限制网络中心选 址问题的算法。a y k i n 瞳8 1 与o w e n n 2 1 等对有能力限制的网络中心选址模 型的算法进行研究。 1 2 2 设施选址问题的特点 在相互作用的设施网络中，实际上根据设施点的需求类型以及实 多产品r 厂选址问题的算法设计与分析 际应用的模型特点不同，不同类型在选址上的主要考虑因素不尽相 同。主要可以划分成下列三种特点的设施选址： 产品型 这种类型的设施网络是指以某一种或某一系列产品为中心，分别 建立不同的设施。例如：家电公司的电饭锅厂、电熨斗厂等，日用化 学品公司的护肤用品厂、洗涤用品厂等等。这种类型的主要目的是为 了能够进行大批量生产，各个厂分别面向所有的市场区域，运费是其 次的。这种类型的设施在选址时较注重接近原材料产地或供应商，在 可能的条件下，也应考虑产品外运的方便和低成本。 市场地区型 这种类型的设施网络是指各个设施分别面向各自一定的市场区 域。这种设置方法主要考虑的是运输问题( 运费、运输时间) ，常用 于体积、重量较大的产品。例如造纸、塑料、玻璃、管道等等制造业， 这些产品在每一地区均有需求，因此对于规模较大的企业来说，往往 以区域需要为中心来设置不同的生产设施。此外，为了以“快速交货” 为主要竞争重点，有时也采用这种方式布置设施。例如，在西方很多 国家都有的承诺“3 0 分钟以内送货上门”的快餐店，其选址自然选在 目标市场附近。 生产工艺型 这种类型的设施网络是指，以企业整个生产环节中的某一环节为 中心，分别建立不同的设施或工厂。每个厂有各自的生产工艺和技术， 分别负责整个生产过程的几个阶段，然后把其产品供应给装配总厂。 硕十学位论文 这种设施选址的方法使得各个不同厂的生产均可达到一定批量，以取 得规模经济效果。这种设置方法的各个设施之间的相互作用、相互依 赖性是最强的。 1 3 设施选址的方法 曲启发式方法( h e u r i s t i c s ) 启发式方法只寻找可行解，而不是最优解。负荷距离法中的重心 法就是一种启发式方法。有许多计算机化了的启发式方法，可解决m ， n 达几百、几千的问题。早在6 0 年代，就有人提出了用启发式方法 解决大型设施选址问题。今天，启发式方法已经广泛在很多场合应用。 b ) 模拟方法( s i m u l a t i o n ) 模拟是试图通过模型重现某一系统的行为或活动，而不必实地去 建造并运转一个系统，那样会造成巨大的浪费，或根本没有可能实地 去进行运转实验。模拟方法有许多种应用，在选址问题中，模拟可以 使分析者通过反复改变和组合各种参数，多次试行来评价不同的选址 方案，模拟方法可描述多方面的影响因素，因此比运输表法有更大的 实用意义。这种方法还可进行动态模拟，例如，假定各个地区的需求 是随机变动的，通过一定时间长度的模拟运行，可以估计各个地区的 平均需求，从而在此基础上确定流通中心、生产中心的分布，还可通 过需求的变动模拟出库存的变动水平，用于帮助决定生产规模、生产、 运输出、仓储费用等。这种方法常用来求解较大型的、无法手算的问 题。例如，某公司有1 3 7 个需求中心，5 个地区性的配送中心，4 个 多产品i ：厂选址问题的算法设计j 分析 生产工厂，通过动态模拟计算分析得出的结论时，如果把现有的5 个 配送中一t l , 归并成3 个，可是总成本最小，该方案得到了实施，实施后 每年可节约1 3 万美元。这是7 0 年代的一个真实事例。 c ) 优化方法( o p t i m i z a t i o n ) 运输表法实际上就是一种优化方法，虽然只是某一方位问题的最 优。这种方法求出的不是可行解、满意解，而是最优解，即：在所有 可能的方案中，不会有比它更好的了。但是由于这种方法要从理论上 证明是最优，所以它在使用上有两大局限性：1 ) 模型必须较抽象、 较简单，否则得不出解。但由此而使模型的描述距实际较远；2 ) 很 多定性因素被忽略掉了，因此不可能得出在考虑定性条件下可能得出 的很多结论。总之，在设施选址中，有很多方法可以应用，特别是计 算机技术的发展使得设施选址的方法更加多样化了，但这些方法仅只 是用来支持决策，使决策更方便也更节省时间、费用，不可能完全依 赖之。 d ) 简单的中线模式法 简单的中线模式法是一种厂址选择的方法。这种方法有其局限 性。这种方法只假设坐标上最优的点( 即是使总的运输距离最短的点) 是一个可行的建厂点，并不考虑在那里现在是否有道路，也不考虑自 然地形、人口密度，以及其他许多在布点时应考虑的重要事项。 e ) 德尔菲分析模型 典型的布置分析考虑的是单一设施的选址，其目标有供需之间的 运输时间或距离极小化，成本的极小化，平均反应时间的极小化。但 硕十学位论文 是，有些选址分析涉及多个设施和多个目标，其决策目标相对模糊， 甚至带有感情色彩。解决这类选址问题的一个方法是使用德尔菲分析 模型，该模型在决策过程中考虑了各种影响因素。使用德尔菲分析模 型涉及三个小组，即协调小组、预n d , 组和战略小组。每个小组在决 策中发挥不同的作用。使用该模型的步骤如下： i 成立两个小组。内外部的人员组成顾问团，充当协调者， 负责设计问卷和指导德尔菲调查。顾问闭中选出一部分人 成立两个小组。一个小组负责预测社会的发展趋势和影响 组织的外部环境( 预n d , 组) ；另一小组确定组织的战略 目标及其优先次序( 战略小组) 。战略小组的成员从组织 中各部门的高层经理人员中挑选； i i j 识别存在的威胁和机遇。经过几轮问卷调查后，协调小组 应该向预n d , 组询问社会的发展趋势、市场出现的机遇以 及组织面临的威胁。这一阶段，要尽可能听取多数人的意 见； i i i 确定组织的战略方向与战略目标。协调小组将预n d , 组的 调查结果反馈给战略小组。战略小组利用这些信息来确定 组织的战略方向与战略目标； i v 提出备选方案。一旦战略小组确定了长期目标，就应集中 精力提出各种备选方案； v 优化备选方案。步骤4 中提出的备选方案应提交给战略小 组中的有关人员，以获得他们对各方案的主观评价；在考 多产品 ：厂选址问题的算法设计与分析 虑组织优势和劣势的基础上，该模型可识别出组织的发展 趋势和机遇。此外，该模型还考虑了企业的战略目标，在 现代公司中被作为一种典型的综合性群体决策方法广泛 使用； 1 4 近似算法和性能比分析 选址问题的算法( a l g o r i t h m ) 是指一个预先制定执行的程序，对 其算法对应求解类型中的任何一个具体实例( i n s t a n c e ) ，按照这个 程序操作后都可以得到一个可行的供应商指派。算法求解问题是需要 时间的，通常算法所用的时间是指算法中所含的加、减、乘、除、比 较等基本运算次数。而算法所用的时间与实例的规模有关，为此我们 用工厂集和客户集中元素个数以及产品种类来刻画实例的规模 将实例通过某种规则编码后输入计算机所占用的字节数称为该 实例的输入长度。对某一个可能的输入长度，算法解此输入长度的最 坏可能实例所需要的基本运算次数称为该算法的时间复杂性( 函数) 。 如果存在一个多项式函数p ( n ) ，使用算法的时间复杂性为o ( p ( n ) ) ， 那么称该算法为多项式时间算法，否则称为指数时间算法。还有一类 算法叫做伪多项式时间算法，它的时间复杂性是关于实例输入长度n 和实例中最大数的二元多项式函数。在二进制编码下，伪多项式时间 算法并不是多项式时间算法，而是指数时间算法。由此出发，可以导 出计算复杂性理论的一系列重要概念和结论1 i 。 计算复杂性理论兴起于2 0 世纪6 0 年代，和算法的设计与分析密 硕+ 学位论文 切相关。通过几十年来人们在计算复杂性方面的研究，现今p n p 的 猜想已被基本接受。在此前提下，所谓的n p h a r d 问题就不可能在多 项式时间内找到最优解。从而，我们在解决方法的有效性、精确性和 时间可行性上寻求平衡。这样，一个自然的想法就是放弃对最优解的 寻找，而把研究的重点转向寻找能在较短时间( 多项式时间) 内得到 接近于最优解的可行解，称为近似解。这种寻求近似解的算法也就是 如前所述的近似算法。同时n p h a r d 问题中有一类更难的问题，称为 强n p h a r d ( s t r o n g l yn p h a r d ) 问题，这类问题不存在伪多项式时间 最优算法阳1 。 我们衡量近似算法的优劣可从两个方面来看，一是算法的时间复 杂性，二是算法得到的解的值与最优解的值的接近程度。另外一个在 实际中常用的方法是对n p h a r d 问题作一些限制从而得到一些子问 题，使其具有有多项式时间算法。这是因为一个问题是n p h a r d 的， 并不能排斥它的一些特殊子问题是多项式时间可解的。 由于绝大多数选址问题都是n p h a r d 问题，其最优解很难找到， 而且在实际应用中往往也没有必要去找到最优解，只需要找到满足一 定要求的启发式解或近似解。因此研究选址问题主要有两个方向。一 是对p 问题，即可解( s o l v a b l e ) 问题，寻找多项式时间算法( 又称 为有效算法) 来得到问题的最优解，或者对n p 难题在特殊情况下寻 找有效算法也就是研究难题的可解情况。二是设计性能优良的启发式 算法和近似算法。 衡量算法优劣有三种办法：数值算例计算、最坏情况分和析和概 多产品r 厂选址问题的算法设计与分析 率分析2 j 。这三种办法各有优点也各有不足。在理论分析( 最坏情况 分析和概率分析) 之前进行大量数值计算是非常有用的方法，一则可 以对理论分析给出估计和提供思路；再者可以与已有的算法进行实际 比较。最坏情况分析是分析算法在最坏情况下的形态，概率分析是分 析算法的“平均”形态，算法的概率分析可以参考考著b 3 i 。目前在理 论上用得最多的是最坏情况分析，对于使目标函数f 为最小的优化问 题，记i 是这个优化问题的一个实例，p 是所有实例的全体；并记“i ) 是实例i 的最优目标函数值，厶( ，) 是算法h 解实例i 的目标函数值。 如果存在一个实数r ( r 1 ) ，对于任何i p 有厶( ，) 2 ) ，提出了一个改进的算法m e ，并给出了该算法最 坏性能比的数学推导、证明过程。另外，对于算法m e 求解2 - p u f l p n ， 给出了2 是该算法紧界的证明及实例说明。 文章末，对工厂选址问题做出总结和研究展望。 多产品f ：厂选址问题的算法设计与分析 2 1k p u f l p 多种产品工厂选址问题 实际生活中，多种产品的工厂选址模型常常被用到。例如：有些 客户往往希望被提供多种产品，或有些客户需要不同的产品。 k l i n c e w i c z 等( 1 9 8 6 ) 阳1 、k l i n c e w i c z 和l u s s ( 1 9 8 7 ) 瞄1 都曾经就一个厂 址可以提供多种产品服务的模型提出过启发式算法和求最优解的算 法。f i s h e r 乜1 等证明了工厂只供应一种产品下的k 种产品工厂选址问题 满足下模集函数( s u b m o d u l a rs e tf u n c t i o n ) 的条件。h u a n g 和“ ( 2 0 0 7 ) 1 首先讨论了在度量空间里每个客户需要k 种产品，而每个 厂址只能用来供应一种产品的工厂选址模型，即一个客户需要由k 个工厂来提供后种产品的模型。这种问题被称为k 种产品的工厂选址 问题( k p u f l p ) 。h u a n g 和l i ( 2 0 0 7 ) 1 证明了当建厂费用为零时 的2 种产品的工厂选址问题( 即2 p u f l p n ) 是一个强n p 完全问题， 并对任意的k ，当建厂费用为零时的k 种产品的工厂选址问题( 即 k p u f l p n ) 给出了一个最坏性能比不大于2 k 一1 的启发式算法，而对 建厂费用不为零时的k 种产品的工厂选址问题( 即k p u f l p ) ，利用 对线性规划问题分数解进行整数化的方法给出了一个最坏性能比不 大于2 k + l 的近似算法。本章中，对于k p u f l p n 提出了一种改进算 法m e ，并且通过定理证明，该算法将性能比提高到三七一1 。当k = 2 时， z 该算法求解2 p u f l p n 的紧界为2 。 坝十字何论文 在本文中，我们规范术语，把产品供应商统一称为- l - ) - - ( f a c i l i t y ) ， 工厂集合用f = i f , ，五，五) 来表示。把有产品需求的结点统一称为客户 ( c l i e n t ) ，客户集合用d = h e 2 ， 来表示。工厂，在第l 层的建 厂费用为z 7 ，两点之间的运输费用为q ，o 对某个给定的目标函数我 们希望能够找到一个可行的工厂集划分( c u t ) 使其满足所有客户对 商品需求的同时，总服务费用达到最小( 建厂费用为零的选址模型) ， 或总服务费用和建厂费用之和达到最小( 带建厂费用的选址模型) 。 2 1 1k p u f l p 的数学模型 问题描述：设西表示客户的集合，表示所有可能建立的工厂集 合。现有k 种产品p l ，= 1 ，2 ，k ，对于任意工厂f f 最多只能提供其中 一种产品给客户。设z 。，i f , 1 ，七表示工厂i 供应产品p t 时所需的建 厂费用。任意两个地址f ，_ ，f u d 之间的运输费用为c 0 。对于v f f ，工 厂i 只能用来供应一种产品，因而对于任意客户d 都必须由尼个工 厂来分别提供k 种产品。我们要确定f 的七个非空且互不相交的子集 互，i = 1 ，2 ，k ，里的厂址用来供应产品p i ，并使总费用达到最小。 在本章中，如果没有特别指出的话，我们总假设下面的条件成立： ( 1 ) 、z 7 0 ，v f f ，= 1 ，2 ，七； ( 2 ) 、c o o ，v i ，_ ，u d ； ( 3 ) 、c ：f = c ，v i ，f w d ；服务费用满足对称关系 ( 4 ) 、勺+ ，v i ，j ，是ef u d ；服务费用满足三角不等式关系 y s l 变量弓，对于v f f ，d 且， 1 2 ，七) ，如果工厂f 向客户供 多产品f i 厂选址问题的算法设计与分析 应产品易，则令取值为1 ，否则弓取值为0 。定义变量，如果工 厂f 被建立用来向客户供应产品所，则令彰取值为1 ，否则取值为0 。 下面是k - p u f l p 的整数规划模型： ( p ) s t 七七 r a i n z 。+ c ：f f 弓 l = 1i fl - ll f j e d 菇= l ，w d ，l = 1 2 ，七； 2 f e ， 弓一，v f f ，j e d ，l = 1 ，2 ，七； 3 七 1 ， f = l o ，1 ) ， v i f ，je 巧， 1 ，2 ，7 ，七) 5 4 一 o ，l ，7v i f ，l e 1 2 ，k 6 上述模型中，约束2 保证了客户的每种产品只能由一个工厂供应。 约束3 说明如果客户能从工厂f 接收到产品易，则有工厂f 肯定被建 立并供应产品所的前提成立。约束4 则确保了每一个被建立的工厂最 多只能供应k 种产品中的一种产品。 2 2k p u f l p n 设所有工厂的建厂费用为零，即2 0 , v i ，= 1 2 ，缸。我们将 此类问题称为k - p u f l p n 。很显然，由于建厂费用为零，因此，所有 的厂址上都可以建立工厂而无须考虑费用的增加。下面是k - p u f l p n 的线性模型： ( p k ) r a i n 勺弓 7 硕十学位论文 s t 巧= 1 ， i e f 艺， = 1 ， ，= l 菇0 ， o ， d ，= 1 ，2 ，尼；8 v f f ，j d ，= 1 ，2 ，后；9 i f1o v i f ，d ， 1 ，2 ，七) 11 v i f ，j 1 ，2 ，后 1 2 2 2 1k p u f l p n 的近似算法介绍 在进一步讨论近似算法之前，我们先分析p 。的分数最优解。后续 的近似算法都是基于分数最优解的基础上进行的。 引理通过以下步骤，我们能得到( p k ) 的分数最优解 第一步：令2 去，v l 1 ，2 ，七) ，f f 第二步：对于任意的客户_ ，d ，由离_ 最近的前| j 个工厂来供应 每种产品的i l 。若，之，l 是客户的前七个最近工厂，我们令 ，2 ，2 = ，2 去，v ， 1 ，2 ，日 毛= o ，v ief ，f 仨 f l ，f 2 ，屯) ， 1 2 ，七 证明：首先，可以很容易地发现被定义的解( z ，j ，) 满足线性规划模 型( 既) 的所有约束条件。并且在这个解中，客户- 的运输费用就 等于前尼个离歹最近的工厂到，的供应费用的总和。很显然，解( x ，y ) 是 ( p k ) 的最优解。 我们把由定理所求得的解作为寻一分数最优解。同时，把前七个离 多产。u 1r 厂选址问题的算法设计与分析 客户最近的工厂，s = 1 ，2 ，尼作为向提供去产品的工厂。很显然， 在这个i 1 一分数解中客户的服务费用是气，+ 气j + - + 气。 2 2 2 一类解决k p u f l p n 的启发式算法( d ) 在本币里，我们将介缁一荚求觯n p 元全i 叫趑k - p u f l p n 的届友 式算法( d ) 。该启发式算法( d ) 是由h u a n g & l i 等提出的【3 1 。通 过介绍该算法，我们能对求解k p u f l p n 问题的算法设计思路有新的 了解和认识，介绍该算法更必要的一点是，本文中的创新点之一改进 算法( m e ) 也是基于这类启发式算法基础之上提出的。 算法是基于己求解出n 紫的i 1 一最优解( 二，多) 基础上给出的，算 法( o - ) 如下：w d ， 设e v = ：。计勺毛。初始化零： 西：= d ，墨= 是= = s x = 矽。在第f 轮迭代中，选择一个客户je d 且 三，= 耐n 三一，i 西) 。令z 表示在第，轮迭代中被选中的客户并且将它 做为本轮迭代的中心客户。令表示为客户z 提供产品的七个工厂组 成的集合 ， e = ，fi 虿= 妻，v ，“2 ，矗好 ， 口= - ，面ij f e ， 1 2 ，矗) ，且虿= 昌。很显然，口一定不为空集，因 为至少工口。令f = ，f 2 ， ，s - s 。u f f ，v le 1 ，2 ，尼 ，万：= _ d ， 将口作为第r 轮迭代的簇。接着，继续下一轮迭代。直虱j b = m ，循环 结束。 对于i ( u 是s ) ，可以将i 放到任意s ( ，= l ，2 ，k ) 中。 坝十宁何论又 _ 一 最后，令所有y ；，ies l 值为1 ，否则值为0 。对d ，令= i ， 否则：o ，当f f ，( ，) ，其中，it ( ) 是s ，1 = 1 ，2 ，七中离客户最近的 工厂。 i 算法( d ) 的性能分析 定理1算法( d ) 产生的可行整数解的费用不超过最优费用的 2 后一l 证明：通过将算法( d ) 的可行整数解与线性模型求解出的最优 解进行比较，来证明该结论成立。 首先，分析每轮迭代中费用的变化。假设e = f l ，f 2 ，) ，在簇口中， 中心客户z 的整数解与最优解费用同为邑。对于其它j 口，j ：j t ，令 e ，： f fi 焉：吾， 1 ，2 ，七) ) = 礼瓦，矗) ，的分数解费用为：。气，。 由于，_ ，d ，说明c 中至少有一个工厂为客户提供月垦务。即 fr 、f a 。不失一般性，假设；。：。客户的整数解费用为：。c f ( ， 其中( ) 是s ，1 ：i ，2 ，尼中离_ ，最近的七个工厂，利用三角不等式性质， 有如下推导成立： lk c ) j q ， ，；i，= i 七 气+ ( 气 + + c 6 ，) 1 = 2 k = c j z + ( 七一2 ) 气 + 吆， l = l 七七 ( 尼一1 ) 气工+ 尼q 。j 因此，产生的可行整数解的费用不超过分数解( ；，歹) 费用的2 七一l 。 多产品t i 厂选址问题的算法设计与分析 有关启发式算法与本文所提出的改进算法( m e ) 在树结构上的相关 性质，将在第三章里进一步展开讨论。 2 2 3 当k 兰2 时，一种新的改进算法( m e ) 一种新的提局了性能比的近似算法( m e ) 在上一节中，介绍了解决n p 完全问题k p u f l p n 的启发式算法 ( d ) 。并且通过理论分析，证得该算法的最坏性能比为2 k 一1 。但是， 算法在每轮迭代中对于f 中的k 个工厂，没有在继续进行细致的分析。 因此，在h u a n g & l i 等研究者工作的基础上，本节中提出了一个新 的近似算法m e ，该算法进一步对每轮所构造的z 以及每轮d f 的构造 进行了分析及改进。并且，通过数学理论的分析证明，该算法把性能 比从2 尼