竞争环境下的网络设施合作选址研究

华中科技大学 博士学位论文 竞争环境下的网络设施合作选址研究 姓名：王丹 申请学位级别：博士 专业：管理科学与工程 指导教师：杨超 2010-04-24 华 中 科 技 大 学 博 士 学 位 论 文 华 中 科 技 大 学 博 士 学 位 论 文 I 摘摘 要要 竞争的加剧和建立企业核心竞争力的要求使得虚拟企业广泛存在，企业间功能 相互渗透，竞争与合作并存成为企业必需面对的复杂环境，在全球竞争越来越激烈 的环境下，合作的重要性也越来越高。选址作为供应链设计和管理的重要部分，也 是企业战略决策的最重要方面，更是企业战略成功的保证。合作选址问题涉及到两 个以企业间的重大决策问题，是选址决策中考虑的要素最多的选址问题，决策的好 坏不仅影响到企业服务设施建设成本的高低，而且决定企业将来运营成本和竞争力 的大小。如何结合合作理论和合作竞争理论进行选址研究具有重要的理论和实践价 值，对于竞争环境下企业在竞争中的生存和发展有重要的作用。论文以几个基本的 合作选址问题的入手，从合作、合作竞争和网络设施覆盖选址等理论出发，研究合 作选址和合作竞争选址模型的建立、求解和应用问题，将合作和合作竞争理论的思 想用于选址决策。 论文首先介绍了研究背景和意义，在对国内外文献进行分析、总结的基础上， 提出了要研究的问题。 其次总结了与本文研究中将要涉及到的相关理论基础。介绍了经典选址模型中 集覆盖选址问题和最大覆盖选址问题的定义和最初应用领域，并给出了模型基本表 达式的形式及其含义；介绍了合作理论与合作竞争理论类型、机理和合作竞争的成 功要素及效应分析；在网络覆盖选址常用算法中介绍了贪婪算法、拉格朗日松弛算 法、遗传算法以及其他一些常用智能算法的基本原理和在选址问题中的基本应用技 巧。 第三，研究了行程时间不确定性风险在合作选址模型的应用及举例。对行程时 间风险函数进行了定义并给出了拟合行程时间风险函数的建议；分析了合作选址问 题中的计算方法并给出了商业优化软件选择的建议；通过对一个随机行程时间的选 址问题及遗传算法的实现介绍了智能算法和行程风险函数在网络覆盖选址问题中的 应用技巧。 第四，研究了竞争设施与合作设施并存的两个网络设施合作选址问题。介绍了 竞争环境下利用目标市场中已有的联盟企业设施进行选址的一些背景，并定义了模 型变量；建立了一类竞争与合作设施并存的最大覆盖选址问题和集覆盖选址问题模 华 中 科 技 大 学 博 士 学 位 论 文 华 中 科 技 大 学 博 士 学 位 论 文 II 型，给出了求解步骤并根据实际选址项目抽象出一个数值算例，对多种预算方案、 市场容量约束方案及其可能的结果进行了演算。 第五，研究了基于合作竞争的三个网络设施覆盖选址问题。介绍了合作竞争环 境下选址的一些背景并定义了模型变量；从纯竞争、部分合作和完全合作三种不同 方式之间的效益和成本差异出发，分析了双方均要求覆盖所有顾客、新进入者覆盖 部分顾客两种情况的合作竞争问题，分别建立了基于集覆盖和最大覆盖的合作竞争 选址模型；此外，还建立了基于帕雷托改进的合作竞争最大覆盖模型，模型可以较 好地处理基于合作竞争的设施选址投入及补偿的帕雷托改进问题。 第六，研究了一个基于品牌竞争的汽车服务设施选址合作伙伴选择问题。根据 汽车行业和选址合作竞争的要求，建立了汽车服务设施合作竞争选扯伙伴选择的评 价指标体系，介绍了各个指标的含义和评价过程中需要注意的事项；根据汽车业销 售数据量大，统计费时的特点，提出了基于索引的海量数据相关分析时样本的统计 算法，并建立了合作伙伴组合的最优确定模型；以华东某汽车公司合作伙伴选择为 案例，介绍了汽车业合作竞争选址合作伙伴选择的过程及模型应用技巧。 第七章对全文内容及研究结论和创新之处进行了总结，并对文中有待进一步深 入研究的地方提出日后研究的方向和展望。 关键词关键词：设施选址 覆盖问题 合作竞争 华 中 科 技 大 学 博 士 学 位 论 文 华 中 科 技 大 学 博 士 学 位 论 文 III Abstract Increased competition and the requirements for establishing enterprises core competitive ability make the virtual enterprise widely spreaded, and more and more functions of enterprise penetrated with each other. Competition and cooperation are developed as a complexed environment in which a company has to survive. Cooperation are playing a more and more important role in an increasingly competition global economy. Location decision is an important part of supply chain design and management, and it is the most important aspect of strategic decision-making, which can ensure the success of corporate strategy. Cooperative location problem is a critical decision-making problem involves two or more enterprises, and it is the one of considering most aspects among all location problems. Therefore, the quality of a cooperative location decision not only decides the enterprises facility construction costs, but also decides the future operation costs as well as enterprises competitive advantage. As a result, how to do location research combining with cooperation and coopetition theories has an important value theoretically and practically, which will play important parts for an enterprise to survive and develop in a competitive environment. Starting with some basic cooperative location problems, and on the basis of theories of cooperation, coopetition and Network Facility Covering Location Problem, the paper studies the modeling, solving and application issues of cooperation and coopetition location problems, which will make use of cooperation and coopetition ideology within location decision-making procedure. Firstly, this paper introduces the backgrounds and significance of study. Based on the review of literatures, the problem to be studied is proposed. Secondly, some relevant basic theories that will be involved in the following research are summarized. The paper introduces the definitions and initial application fields of Set Covering Location Problems and Maximal Covering Location Problems in classical location problems, and gives the basic expression, as well as the meaning of the model. The paper also introduces the taxonomy, fundamentals, success factors and effect analysis of cooperation and coopetition theory. In the section of commonly used algorithms in Network Covering Location Problems, the paper gives a brief introduction to the fundamental principles and some basic application skills of greedy heuristics, Lagrangian relaxation algorithm, genetic algorithm and other intelligent algorithms. Thirdly, the application of stochastic travel time risk in cooperative location modeling 华 中 科 技 大 学 博 士 学 位 论 文 华 中 科 技 大 学 博 士 学 位 论 文 IV is studied. After giving the definition of travel time risk function and some pieces of advices on the choosing of curve fitting methods, the paper analyzes the algorithm of cooperative location problem and gives some suggestions on the choosing of optimization software. This paper illustrated the application tactics of intelligent algorithm and travel time risk function on the Network Covering Location Problems by implementing of a stochastic travel time location problem solved by genetic algorithm. Fourthly, two location problems with coexistence of competitive and cooperative facilities are investigated. After introducing some backgrounds of locating facility in the target market where there have some alliance facilities, and giving some definition of model variables, a Maximal Covering Location Problem and a Set Covering Location Problem with coexistence of competitive and cooperative facilities are presented respectively. A solution strategy, as well as a numerical example based on a practical location project is proposed. The paper analyzes the model and algorithms with a variety of budget and market capacity constraints, as well as its possible results of the calculations. Fifthly, three Network Facility Covering Location Problems based on coopetition is scrutinized. After describing the coopetitive environment and defining the model variables, the paper scrutinizes the differences of earnings and costs among pure competition, partial cooperation and pure cooperation, and analyzes two kinds of coopetition problems which are two partners both require to cover all customers, the new entrants to cover part of the customers, with two models based on Set Covering Location Problem and Maximal Covering Location Problem, respectively, are proposed. Moreover, a coopetitive Maximal Covering Location model on basis of Pareto improvement is also developed, the Pareto improvement on the issues of investment and compensation involved in coopetitive facility location problems can be well handled by the model. Sixthly, a cooperation partner evaluation and selection problem on basis of brand-based competitive auto service facility location is introduced. According to the requirements of automotive industry and coopetition on location decision-making, an automotive service facility location coopetitive partner selection evaluation system is proposed. At same time, the definitions and significances of each index, as well as the issues need to be considered in the evaluation processes are illuminated. On account of the fact that the quantity of auto industry sales is enormously and the statistical procedure is time-consuming, an index-based algorithm of statistical samples for correlation analysis from mass data is proposed, and a coopetitive partner combination optimization model is 华 中 科 技 大 学 博 士 学 位 论 文 华 中 科 技 大 学 博 士 学 位 论 文 V also developed. In addition, the paper takes an East-China automobile companys coopetitive partner selection project as a case to illustrate the coopetitive location partner selection procedure and model application skills in automobile industry Finally, the paper gives conclusion to the contents and the innovative achievements of the research, and presents the future scope, the purpose and the prospect of this topic in further studies. Key words：Facility Location Covering Problem Coopetition 独创性声明独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本人完全意识到，本声明的法律结果由本人承担。 学位论文作者签名： 日期： 年 月 日 学位论文版权使用授权书学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。 本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密 ，在_年解密后适用本授权书。 不保密。 （请在以上方框内打“” ） 学位论文作者签名： 指导教师签名： 日期： 年 月 日 日期： 年 月 日 本论文属于 华 中 科 技 大 学 博 士 学 位 论 文 华 中 科 技 大 学 博 士 学 位 论 文 1 1 导导 论论 1.1 研究背景及意义研究背景及意义 1.1.1 选址研究的重要性选址研究的重要性 网络设施选址问题是研究如何在网络系统中最优地确定网络服务设施的位置、 数目、规模、时机等，来为用户提供所需的服务，也就是如何在网络中确定顾客和 服务设施等关键节点的问题。网络设施选址是相对于平面设施选址而言的，但网络 是大多数设施选址主体进行选址决策的载体，并且可以映射到很多管理问题当中， 比平面设施选址更有实际意义(ReVelle et al., 2008a)。这里的“设施”具有广泛的含 义，可以是售后服务站、配送中心、分销中心、特许加盟店、终端卖场等等，也可 以延伸到机场、港口、工厂、消防站、检查站、收费站、学校、医院、汽车站、变 电站、交换机、机器设备、计算机终端、警报器、卫星、产品属性、人际关系网络 中的关键人物等等(马云峰，2005)。 自上世纪初韦伯提出仓库选址问题以来，设施选址问题不仅已经成功地运用在 诸如交通、军事、物流、通信、电力等多个传统领域(Berman et al., 2002)，而且最近 在许多非传统领域也得到了很好的应用，比如产品定位、供应商选择、聚类分析等 实践和理论领域(ReVelle et al., 2005)。选址决策已经证明为对生产领域的制造成本、 在制品库存、生产提前期等有显著的影响(Drira et al.,2007)，在设施布置领域的仿真 研究也是通过评价给定的选址方案进行的(Aleisa Fehr and Fischbacher, 2004)，在 回报比较多(Pommerehne et al., 1994)或允许学习的(Fehr and Gachter, 2000)情况下， 利 他主义可以很容易得以保持，很多学者认为人类本性中的一些东西驱使主体走向合 作(Caporael et al., 1989)。 在管理实践中，最多的合作关系来自于企业内部的各个团队之间或团队成员之 间(Nils et al., 2009; Cecily, 2009)，这种合作的重要性和机制、方法得到广泛的认知和 研究(Falkinger et al., 2000; Sausgruber and Tyran, 2007; Levati et al., 2007)。 近十几年来 供应链理论的提出及广泛运用，伴随着核心竞争力、战略联盟等管理思想被越来越 多的管理者接受和虚拟企业这种组织形式的普及，企业组织之间的合作也逐渐增多 (Serguey and David, 2009; Osteloh and Rota, 2007)。 无论是在理论还是实践上， 企业间 的合作更多地局限在供应链上下游企业和供应链伙伴之间(LaLonde, 1997; Mentzer et al., 2001; Mingming Leng, 2005)。 近年来合作竞争理论(cooperation- competition theory) 的提出(Brandenburger and Nalebuff, 1996; Zineldin Mosad, 2004; Yadong Luo, 2007)， 将企业间的合作推广到具有竞争关系的企业，尽管相关的研究和实践不是很多，在 竞争日趋激烈的时代，无疑为组织内各级决策人员进行决策和学者们进行理论研究 提供了更广阔的空间。 1.1.3 本文的研究意义本文的研究意义 一方面，在全球竞争越来越激烈的环境下，合作的重要性也越来越高。另一方 面选址问题是供应链设计和管理的重要部分(马士华 等, 2001)， 选址作为企业战略决 策的最重要方面之一，是企业战略成功的保证。近年来，考虑竞争因素的选址问题 在国际上得到了足够的重视和较为广泛的研究(Tammy et al., 2002; Hosum etal., 2003; Plastria F, 2008)， 国内一些学者也开始了对竞争选址问题的探讨(张曦 等, 2009; 卢晓 珊 等, 2009)。总的来说，在竞争环境下考虑合作的研究虽然相对较多，但都集中供 应链上下游伙伴之间的合作 (Frans et al., 2007)， 目前不论是国内还是在国外，无论 在哪一个合作领域，现有的选址文献很少有明确涉及到选址决策过程如何进行合作 华 中 科 技 大 学 博 士 学 位 论 文 华 中 科 技 大 学 博 士 学 位 论 文 3 的研究，更没有在选址模型中如何量化各种合作方法或合作战略的研究。因此，如 何结合合作理论和合作竞争理论进行决策具有重要的价值。也就是说，本文的研究 意义在于选址研究本身对于理论和实践的重要性，更重要的在于合作在竞争环境下 对于企业在竞争中生存和发展的重要作用，论文最主要的意义在于二者之间交叉形 成的研究空白。在实践上，面临激烈的竞争，每个企业都在各个环节努力降低成本， 提高竞争能力，在企业设施选址这一战略环节，急需找到一种既能对竞争合作伙伴 的选择提供建议，又能考虑到合作双方利益分配的系统的解决方案。 因此，本文的 研究不论是在选址理论上，还是在企业管理实践上都有重要的意义。 1.2 国内外研究综述国内外研究综述 1.2.1 合作与合作竞争研究综述合作与合作竞争研究综述 合作(cooperation; collaboration)是个人与个人、 群体与群体之间为达到共同目的， 彼此相互配合的一种联合行动。我国民间流传的大量俗语、谚语和名人名言都十分 强调合作的重要性，比如：“天时不如地利，地利不如人和”(孟子)；“团结就是力 量”(谚语)；“单丝不成线，独木不成林”(俗语)；“二人同心，其力断金”(易经)。 国外民间也保有相当多同样脍炙人口、提倡合作的名言或寓言留世，这些名言和寓 言基本上都是用来警世后人通过合作对抗竞争的，突出了竞争环境下合作的重要地 位，比如：“一致是强有力的，而纷争易于被征服”(伊索)；“若不团结，任何力量 都是弱小的”(拉封丹)。 关于合作理论， 理论和实践上都倍受关注， 现存有大量的成果， Ralph et al.(2007) 对此进行了比较完整的综述。现代社会对合作的认识和研究主要集中在工业和商业 界所面临的竞争和合作问题。实证或实验研究显示在避免滥竽充数的情况下，群体 之间的合作可以明显提高参与合作的各群体的竞争能力，这一结论不论是在争夺公 共产品服务(Kugler et al., 2006)，产品生产(von Hippel, 1987,1988)还是在产品研发 (Nuvolari, 2004; Cowan and Jonard, 2003)或软件开(Meyer, 2002; von Hippel and Krogh, 2003; Osteloh and Rota, 2007)，或其他商业领域(Bornstein, 2003; Meyer, 2003)都是成 立的。Teece(2007)研究了在竞争环境下制定经营和企业发展战略过程中新设备和新 产品的技术诀窍的合作问题。Serguey and David(2009)研究了在高度竞争的环境中如 何在公司之间自发地形成合作关系，并通过建立模型来解释，他们的基本观点是竞 华 中 科 技 大 学 博 士 学 位 论 文 华 中 科 技 大 学 博 士 学 位 论 文 4 争越激烈的市场，如果能形成类似邻居关系而互相帮助的企业之间的成本就会越低， 并以绵纺工业为例进行了说明。 竞争的加剧和建立企业的核心竞争力的要求使得虚拟企业广泛存在，企业间功 能相互渗透，竞争与合作并存成为企业必需面对的复杂环境。在这样的环境下，耶 鲁大学管理学教授Nalebuff和哈佛大学企业管理学教授Brandenburger最早提出的合 作竞争理论(Brandenburger and Nalebuff, 1996)， 近年来成为战略管理专家的研究重点 和企业高层管理者进行战略决策的重要依据。事实上，早在Nalebuff他们提出合作竞 争理论之前，网微(Novell)公司首席执行官Ray Noorda在实践过程中形成了合作竞争 的概念，把把合作(Cooperation)和竞争(Competition)两个单词合在一起，形成了合作 竞争(Coopetition)这个新的词汇，他经常提到的一句话是：“为了使一个组织或行业 有所发展，你必须同时竞争和合作”(Davis, 1993)。 合作竞争是为了双方或多方的共同利益，在某一层次上进行合作，而在其他方 面进行竞争(Brandenburger and Nalebuff, 1996; Bengtsson and Kock, 2000)。合作竞争 就是伙伴之间为了共同的目标或为获得共同的战略优势在竞争的同时进行合作 (Zineldin, 2004)。 尽管合作、竞争这两个概念在商业领域已经是非常成熟的思想了，正式的合作 竞争思想在企业和学术界还是相对较新的。在上世纪90年代之前，竞争与合作一般 被看作是两个极端状态，不可能有交点。随着竞争的进一步加剧，为了获得商业上 的成功并保持竞争优势，企业组织需要同时发展和利用竞争与合作战略(Lado et al., 1997)。从战略的观点来看，合作竞争就是以在开拓市场或降低成本使组织成功为目 标建立的既包括合作也包括竞争的模型(Chien and Peng, 2005)，为了组织的成功，合 作竞争要求组织间的共同的愿景和目标，相互信任，信息共享，风险共担，收益共 得(Zineldin, 2004)。组织间合作和竞争的特征及形势影响与竞争者之间的合作，并作 用于组织间合作竞争的结果(Theresa, 2007)。竞争会涉及到资源、基于价值链的市场 定位及战略、知识流、竞争优势、影响力、市场份额等方面的欺骗(Luo 2003; Bartlett and Ghoshal, 1989)。而合作为是另外一种情况，包括技术、运营、组织、财务等。影 响合作的关键因素包括战略的独立性和技术间的关联(Luo, 2005; Tsai, 2001; Ghoshal and Bartlett, 1988)。合作和竞争的强度可以通过个体或组织间合作、竞争的接触频率 来度量，实证研究已经建立了相关的合作竞争强度测量方法(Luo etal., 2006)。合作竞 争关系的建立必需谨慎，可能的粗心会使自己丧失竞争优势。成功因素包括一个清 华 中 科 技 大 学 博 士 学 位 论 文 华 中 科 技 大 学 博 士 学 位 论 文 5 晰的双赢形势，合作的开放和清楚的定义退出条款(Anslinger and Jenk,2004; Hansen and Nohria, 2004; Perry et al., 2004)。 近年来我国学者也在合作竞争领域开始研究，虽然相关文献不多，但在多个领 域也都出现了一些研究成果。 夏青(2008)在全球化与信息化环境下研究了企业合作竞 争中存在的风险及其防范。张军、王丽敏(2007)对网络组织中存在的企业合作竞争风 险问题进行了研究，阐述了网络组织中合作竞争风险产生的机理。曹永峰(2009)对制 造业合作竞争机制进行了探讨。邓文潇、张汉江(2008) 研究了两条供应链之间信息 不对称时的供应链合作竞争问题，建立了信息共享机制。张少杰、任伶(2009)根据创 新中合作与竞争的特性，提出了一套信息主体间合作竞争的绩效指标体系，并建立 了以Sharply值为权重的评价模型。汪传旭、蒋良奎(2009)根据港口服务价格、服务时 间及港口之间的影响，提出港口需求的函数表达式，并在此基础上考虑港口服务时 间可靠性约束，提出港口合作竞争的分析模型和港口合作利润的分配机制。高江舟、 王素娟(2007)从企业生态理论角度出发，对现代企业合作竞争理论进行了研究。 总的来说，国内外在合作及合作竞争战略理论上都有较充分的研究，但是针对 执行层如何有效实现这一战略思想的研究存在着大量需要解决的问题，特别是在选 址研究领域，没有检索到与之有较高相关度的研究文献。 1.2.2 网络选址研究综述网络选址研究综述 网络设施选址是相对于平面设施选址而言的，是顾客需求点只可能在网络的结 点上出现，服务设施候选点也只能在网络的结点或网络的边上出现，并且服务设施 候选点对顾客需求点提供的服务必须经过网络边的选址问题(ReVelle et al., 2008a, 马云峰 2005)。 （1）关于选址的起源和分类）关于选址的起源和分类 对设施选址问题的研究最早可以追溯到17世纪Pierre de Fermat，Evagelistica Torricelli 和 Battista Cavallieri他们各自独立提出的基本的欧几里德空间中位问题， 也称为费马问题。而现代选址研究起源于1909年著名的韦伯问题，韦伯问题是一个 仓库选址问题，目的是如何确定单个仓库的位置，使其到多个顾客间的总距离最小。 韦伯问题和费马问题在本质上是同一个问题，所以造成了后人对这个问题的混淆。 早期的选址研究还包括Chrystal、Hotelling H、Weiszfeld等学者的研究。上世纪六十 年代中期Hakimi(1964)通过对网络P-中位选址问题的研究带来选址研究的复兴。基本 华 中 科 技 大 学 博 士 学 位 论 文 华 中 科 技 大 学 博 士 学 位 论 文 6 选址问题可以分为覆盖问题（covering problems） 、P-中位问题（p-median problems） 和P-中心问题（p-center problems）三类，在此基础上产生的扩展问题可以参见最近 的综述(ReVelle, 2005; 马云峰, 2005; 唐凯, 2008; 何波, 2008) （2） 关于竞争环境的选址研究关于竞争环境的选址研究 设施竞争选址是根据所设立的服务设施是否存在同行业竞争的情况。选址决策 的时候存在同行业或潜在竞争者的设施选址问题称为竞争选址问题；与设施竞争选 址相对的选址问题是设施垄断选址问题。考虑竞争的设施选址问题近年来也有大量 的文献研究。设施竞争选址问题是考虑市场上存在两个或两个以上的同类产品或服 务的提供者，或服务站提供多个产品或服务。当前关于设施竞争选址问题的研究主 要集中在静态的选址问题上，研究所涉及到的行业背景大多以连锁超市等零售业为 主。静态随机竞争设施选址问题是在 Huff(1964)的重力模型的基础上展开研究的。 Nakanishi 和 Cooper(1974)、Drezner(1994)、Drezner et al.(1996)通过效用函数的运用 来处理不同服务设施的吸引力问题，对顾客选择服务站的概率和市场份额等有关选 址问题的参数处理进行了基础研究。在此基础上，Marianov et al.(1999)研究了竞争条 件下无容量限制的 Hub 设施选址模型，Drezner et al.(2002)提出了应用模拟退火和 Ascent 相结合的混合启发式算法求解新建服务设施市场份额期望值最大的竞争设施 选址问题。 近年来，国内越来越多的学者也开始研究竞争环境下的选址问题。李志强和傅 明化(2009)研究了基于中心地模型竞争条件下的商圈和连锁站的选址问题。 华国伟等 (2007)研究了多目标竞争选址问题，建立了市场份额最大、费用最小和利润最大、利 润率也最大的两类双目标竞争选址模型，给出有效解集的精确求解方法和近似求解 方法。肖怡然，等(2009) 在加油站的应用选址问题中考虑了客户加油成本等因素， 并利用阿德兰启发算法求解。赖志斌，等(2009)在研究零售商业网点的竞争选址问题 中，给合 GIS 提出了一种基于权重设置的选址评价模型。卢晓珊，等(2009)研究了一 个在竞争环境下使获利最大的竞争选址双层规划模型，其中上层模型做出选址决策， 下层模型确定产品的纳什均衡价格，并利用贪婪算法和禁忌搜索算法求解。张曦， 等(2009)考虑在竞争的环境下新设施的选址问题， 建立了使连锁企业市场份额最大和 企业内已存设施市场吞并最小的双目标模型，并给出了遗传算法和算例。孙会君、 高自友(2002)研究了有竞争的物流配送中心问题，建立了一个选址决策模型，把求解 的问题归结为无约束的非线性规划问题，并给出了迭代算法。 华 中 科 技 大 学 博 士 学 位 论 文 华 中 科 技 大 学 博 士 学 位 论 文 7 总结国内外在选址理论上的研究文献，在合作竞争选址方面的文献主要集中在 竞争选址领域，尚未有文献明确提出合作选址或合作竞争选址问题。 1.2.3 选址算法研究综述选址算法研究综述 由于基本网络设施选址问题都是混和整数规划模型，这类问题的复杂性使得无 法应用“精确算法(Exact Algorithm)”来求解，加之风险、时间、成本等参数的不确 定性及某些选址决策的频繁性对算法的健壮性也提出了更高的要求。ReVelle et al. (2008b)在设施最大覆盖选址问题中，用多种启发式算法同确算法进了对比，结果显 示，启发式算法的解在接近最优的情况下所用的计算时间有相当大的优越性。赵秋 红和谢稳(2006)运用 Lagrangian 松驰算法求解一类分销系统健壮选址问题， 一定程度 考虑了决策者的风险偏好问题。Berman 和 Drezner (2006)在研究一类节点需求随其 同服务站距离曾指数递减的容量限制选址问题中，对单设施选址问题给出了 O(n3)的 算法，对于多设施选址问题，用顶点替代算法和模拟退火算法对 40 多个问题进行了 计算实验。Drezner et al. (2006)在一个具有五个目标的多目标选址问题中，运用顶点 替代算法和禁忌搜索算法求解。Camargo et al. (2008)用 Benders 分解法求解无容量限 制的多设施枢纽选址问题。 由于基本的网络设施选址问题已被证明是 NP-困难问题， 在现有的计算技术条件 下难以求得最优解，因此，利用启发式算法寻求决策问题的满意解成为仅有的选择。 对网络设施选址问题常用求解的启发式算法主要贪婪算法、禁忌搜索算法、遗传算 法等近十种，根据设施选址问题的属性而选择不同的启发式算法或组合应用这些启 发式算法。 “贪婪算法”在设施选址问题中有着十分重要的地位（Grossman and Wool(1997; 马云峰 2005） ，对多种规模、类型的选址问题中都可以得到较好质量的解，尤其在 覆盖问题中，合理运用贪婪算法往往可以得到多种算法中最好质量的解。 “遗传算法（Genetic Algorithms, GA） ”是模拟自然选择和淘汰的生物进化过程 的计算模型。GA 的研究历史比较短，是由美国密执根大学的 Holland 教授于 1975 年首次提出 Holland(1975)，遗传算法是一种新的全局优化搜索算法，因其原理简单， 且通用性和鲁棒性强，特别适于并行处理。Wen Toregas, 1971)。 SCLP 是在一个有限的设施候选 服务站集中找到一个总的建设成本最小的服务设施集，使得所有的顾客需求点至少 被一个服务设施覆盖一次。 早期对集设施覆盖问题的研究者有 Minieka(1970)、 Moore 华 中 科 技 大 学 博 士 学 位 论 文 华 中 科 技 大 学 博 士 学 位 论 文 15 和 ReVelle(1982)等。Plane 和 Hendrick(1977)、Daskin 和 Stern(1981)建立了服务设施 个数最小和备用覆盖的顾客需求最大的双目标集设施覆盖选址问题。Heung-Suk Huang(2004)研究了产品或服务会随着时间的发展变坏或变好时的动态集设施覆盖选 址问题。 若定义 j f 为设施候选点 j 的服务设施固定的建设费用，再定义设施建设与否的 决策变量 j X如下： 1 0 j j X = 如果在服务站候选点 处建站 否则 可以建立集设施覆盖选址问题的数学模型表达如下： Min jj j f X (2.1) s.t. 1 ijj j c X i (2.2) 0,1 j X = j (2.3) 模型的目标函数式(2.1)是最小化所选择建设的服务设施集的总的建设成本；约 束式(2.2)保证所有顾客需求点至少被一个设施服务点覆盖一次； 约束式(2.3)是对所有 服务设施建设与否的决策变量的 0-1 约束。 2.1.2 最大设施覆盖选址问题最大设施覆盖选址问题 从上节的集设施覆盖选址问题模型表达式可以看出，集设施覆盖选址问题是要 求在企业覆盖所有顾客需求点的前提下确定在哪个候选位置建立服务设施，和确定 建设服务设施具体数量的问题。集设施覆盖选址问题不加区别地看待不同需求量的 各个需求点，在资金预算有限的情况下将无法满足所有顾客的要求或达到企业的市 场目标，因此，如果把决策目标转变为在在既定的资源下（有限的服务站数目约束 下）企业服务设施覆盖服务尽可能多的顾客需求点，这样的问题就是最大设施覆盖 选址问题。 最大设施覆盖选址问题（MFCLP）或 P-设施覆盖选址问题是研究在企业服务设 施的数目和设施服务半径已知的条件下，如何设立 P 个服务设施使得可接受服务的 顾客需求最大的选址问题。同其它基本选址问题一样，最大设施覆盖选址问题也是 华 中 科 技 大 学 博 士 学 位 论 文 华 中 科 技 大 学 博 士 学 位 论 文 16 NP-困难问题(Daskin, 1995)。 最初的最大设施覆盖选址问题是由 Church RL 和 ReVelle C(1974)提出的。 Church 和 Meadows 提出了最大设施覆盖选址问题的伪 Hakimi 特性， 并给出了详细的证明。 Benedict(1983)，Hogan 和 ReVelle(1986)，Daskin(1983)研究 了服务系统拥挤条件下的最大设施覆盖选址问题。Haldun 和 Saydam(2002)用遗传算 法来求解大规模的最大期望设施覆盖选址问题。 Jorge et al(2002)在对选址问题的遗传 算法应用研究时介绍了最大设施覆盖选址问题遗传算法的求解步骤和操作策略。 在给出最大设施覆盖选址问题的数学表达式之前，对以下几个有关变量符号进 行定义： i h = 顾客需求点i的需求量 p = 企业准备建设的服务设施个数，可以从预算限制中得出 1 0 i i Z = 如果需求点 被覆盖 否则 决策变量 j X和 ij c的定义同前节，则最大设施覆盖选址问题可以描述如下： Max ii i hZ (2.4) s.t. ijji j c XZ i (2.5) j j Xp= (2.6) 0,1 j X = j (2.7) 0,1 i Z = i (2.8) 模型的目标函数式(2.4)是使被企业覆盖的总顾客需求量最大； 约束式(2.5)是保证 某个潜在顾客需求点至少被一个决定设立的服务设施覆盖的情况下，这个需求点上 的需求才能算是被满足， 也就是该需求点上的顾客可以成为企业的顾客； 约束式(2.6) 是确保设立设施服务点的个数为p个；约束式(2.7) 和约束式(2.8)是对是否设立某服 务站和是否覆盖某需求点的决策变量的 0-1 约束。 华 中 科 技 大 学 博 士 学 位 论 文 华 中 科 技 大 学 博 士 学 位