（应用数学专业论文）网络上的竞争选址问题研究.pdf

北京化工大学硕土学位论文 摘要 摘要 选址问题主要研究如何选定一个或多个设施的地理位置使得所考 虑的目标达到最优的问题，它在生产生活、物流、军事等领域中都有 非常广泛的应用。竞争选址是选址问题中一类非常重要的问题，其研 究已经引起了广泛的关注。 本文主要研究了网络上的竞争选址问题。首先，详细介绍了选址 和竞争选址的基本知识，并提出了一个反映聚集效应的竞争选址新模 型，给出了两种算法；其次，研究了两类双目标竞争选址模型，给出 了它们的性质、关系以及解法；接着，探讨了预先抢占市场模型的一 些性质和计算技巧；最后，对未来的研究方向给出了一些建议。 本文的主要创新工作为：( 1 ) 给出了一个竞争选址新模型。该模 型既包含了选址费用，又反映了聚集效应，同时给出了两种求解方法 一分支定界法和贪婪算法。最大市场份额模型是我们模型的一个特例； ( 2 ) 提出了两个双目标竞争选址模型。一个模型的目标为市场份额最 大、费用最小，另一个模型的目标是利润最大、利润率也最大。文中 研究了它们的性质与关系，并将它们化为同一个单目标参数整数规划 模型，给出了求解精确和近似有效解集的方法；( 3 ) 讨论了预先抢占 市场问题的特殊情况。本文不仅改善了垄断选址模型的生存条件，而 且研究了模型的性质和树网络上该问题的计算技巧。 关键词：竞争选址，多目标规划，0 1 规划，分支定界法，交换算法 北京化工人学硕士学位论文摘要 r e s e a r c ho nc o m p e t l t i v el o c a t i o n p r o b l e m so nan e t w o r k a b s t r a c t l o c a t i o np r o b l e m sm a i n l yd e a lw i t h 血el o c a t i o no fo n eo rm o r e f a c i l i t i e si naw a ym a to p t i m i z e sac e n a i no b j e c t i v es u b j e c tt os o m e c o n d i t i o n s t h e yh a v eb e e nw i d e l y印p l i e d i n m a n yf i e l d s ， s u c ha s p r o d u c t i o n s ，l i v e s ，l o g i s t i c sa n dm i l i t a 巧a f r a i r sa n ds oo n c o n l p e t i t i v e l o c a t i o ni sav e qi i n p o r t a n tp r o b l e mo fl o c a t i o nr e s e a r c h ，a n di th a s o b t a i n e de x t e n s i v ec o n c e m s t h i sd i s s e r t a t i o nm a i n l ys t u d i e sc o m p e t i t i v el o c a t i o np r o b l e m so na n e t w o r k f i r s t l y ，t l l eb a s i ck n o w l e d g eo fl o c a t i o np r o b l e m sa i l dc o m p e t i t i v e 1 0 c a t i o n p r o b l e m si sg 沁e ni nd e t a i l ，a 1 1 d an e wm o d e l 也a tr e n e c 乜 a s s e m b l i n ge 脯c tf o r ac l a s so fc o m p e t i t i v el o c a t i o np r o b l e m sa i l di t s a l g o r i m m sa r ep r e s e n t e d ；s e c o n d l y ；t w ok i n d so fb i - o b j e c t i v ec o n l p e t “i v e 1 0 c a t i o nm o d e l sa j l dm e i rp r o p e r t i e s ，r e l a t i o n sa i l ds 0 1 u t i o n sa r es t u d i e d ； t h i r d l y ，s o m ep r o p e n i e sa r l da na l g o r i t l l m i ct e c l l l l i q u ef o rt l l ep r e e m p t i v e c 印t u r em o d e la r ed i s c u s s e d ；a l l df i n a l l y ，s o m es u g g e s t i o n sa r em a d ef o r i i 北京化u t 大学顽十学位论义 摘要 p o s s i b l ed i r e c t i o n so f 血t u r er e s e a r c h 0 u rm a i nn o v e lw o r ki s ：( 1 ) an e wm o d e lf o rac l a s so fc o m p e t i t i v e l o c a t i o np r o b l e m si sg i v e n t h i sm o d e ln o to n l yi n c l u d e sf i x e dc h a 培eb u t a l s or e n e c t sa s s e m b l i n ge f 凳c t t w dm e t l l o d st os o l v et l l em o d e la r e p r e s e m e d ：ab r a n c h a 1 1 d - b o u n dm e t l l o da i l d ag r e e d ya l g o r i t l l m t h e o r i g i n a lm a ) ( i m u mc 印t u 】em o d e l i sas p e c i a lc a s eo fo u rm o d e l - ( 2 ) 1 w o k i n d so fb i - o b j e c t i v ec o m p e t i t i v el o c a t i o nm o d e l sa r ep r e s e n t e d 0 n ei s a b o u tm a x i m i z i n gm a r k e ts h a r e 锄dm i n i m i z i n gc o s t ，a i l dt l l eo t l l e ri sa b o u t m a x i m i z i n gp r o f i ta i l dp r o f i t 雠u q g i n t h e i rp r o p e r t i e sa 1 1 dr e l a t i o n sa r e s t u d i e d ，a n d “i sp r o v e dm a ts o l v i n gas i n g l eo b j e c t i v ep a r 啪e 订i c i m e g e r - p r o g r a n u n i n gp r o b l e mc 鲫s o l v et 1 1 e m ，a n dt 1 1 e nw ep r o v i d e a i l e x a c ta n da i la p p r o x i m a t e 印p r o a c ht 0o b t a i n 廿1 es e to fe 伍c i e ms o l u t i o n s ( 3 ) as p e c i a lc a s eo f t h ep r e e m p t i v ec 印t u r em o d e l i ss t u d i e d w en o to m y i m p r o v em em o d e lo fm o n o p o l i s t i cl o c a t i o n ，b u t a l s o p r e s e n t s o m e p r o p e n i e so fm ei m p r o v e dm o d e l ，a n di n t r o d u c ean e wt e c l l l l i q u et 0s p e e d u ps o l v i n gt 1 1 ei m p r o v e dm o d e lo n 廿e en e 栅o r k s k e yw o r d s ：c o m p e t i t i v el o c a t i o n m u l t i o b j e c t i v ep r o g r a m m m g ，0 - 1 p r o g r 锄m i n g b r a i l c ha n d b o u i l dm e t l l o d ，e x c h a n g ea l g o r i t l l 】 n i i i 北京化工大学硕士学位论文 符号说明 符号说明 需求点的指标与指标集 候选设施点的指标与指标集 f 点的需求量( 单位) ，点的选址费用( 元) ，设为整数 公司b 的设施点的指标集 公司b 最靠近需求点f 的设施点 点f 与点，的距离( 公里) 点锺 | | 最近的b 公司设施的距离 集合 广k ( 1 一口) 集合 w j k 哆酽 集合 w j k = ，卵 集合 w ，l 吒 3 则为抽象选址，其实质和实物选址相似，但确定的一般不是 实物的位置，而是事物的一些特征参数或属性等f 1 0 1 。有很多文献研究了决策空间 是1 维的线段或直线的情况，通常比较简单，2 维的平面选址是生活中最普遍的一 种选址，但从数学的观点看，通常会很复杂，甚至难于处理，有时选址区域内还 可能存在障碍物如湖泊、高山或建筑物等，这更增加了问题的难度。3 维的空间选 址也是实际中的一种选址，如海水中、空中某种设施的选址，或卡车、火车、飞 机上运送箱子的长度宽度高度的确定。3 维以上的抽象选址往往很复杂，这不仅是 维数灾的原因，还因为事物特征或属性的选取比较复杂，而且这些特征或属性还 可能是相互关联的。另外一种选址空间是网络，在现实中城市街道和公路都是一 个网络的形式，设施可以安置在网络的任何地方或顶点，若设施只能安置在网络 的顶点或离散点集上，就称为是离散选址，模型属于组合优化，形式通常是整数 规划或0 1 规划。有时决策空间也可能是混合空间，即一部分是连续空间，一部分 是网络或离散点集。 ( 2 ) 距离 两点之间的距离也是选址中非常重要的要素，模型的建立和做出决策都要依 赖于距离，选取的距离不同，选址的结果一般会不同。通常用范数定义两点之间 的距离。对于网络模型，距离可以任意定义，通常街区距离即厶距离比较常用， 北京化t 火学硕士学位论文第一章概述 在平面选址和高维空间的选址中，三。范数距离用的较多，特别是平面选址中用欧 氏距离厶比较直观，用得也最多。在抽象选址中，距离的含义就不是很直观和易 于理解，如确定待考察的产品属性点与最优的属性点之间的距离，h a m m i n g 距离厶 对应于属性差别的累加，c h e b y s h e v 距离l 对应于把两个点属性差的最大值作为 两个点的距离。t h i s s e 、w a r d 和w j n d e l l 把各种范数分为圆范数( r o u n dn 伽l s ) 和 块范数( b l o c kn o m s ) ，凡是在范数七下单位球曰= x 后( x ) l 的围线是多胞形，就 称t 为块范数，凡是在范数七下单位球b 的围线不包含平点，就称i 为圆范数。 ( 3 ) 顾客及需求 顾客与需求也是影响选址的重要因素，顾客的重要特征是他的分布和购买行 为，购买力等。在平面选址中一般假定顾客的分布是均匀的，在网络选址和离散 选址中，通常假定顾客均匀分布在网络的弧上或以顾客群的形式集中在网络顶点 或其他离散点上。顾客的购买行为是选址要重点考虑的因素，它与下面要提到的 吸引函数有密切的关系，顾客光顾设施时是按距离的远近还是设施规模的大小或 是服务质量、交通状况而定，当两个设施对顾客的吸引力相同时，他是保守的光 顾旧的设施，还是新奇的光顾新设施，或是无所谓。顾客的需求与设施及服务质 量和销售策略是否有关，是弹性的还是非弹性的，是均匀分布还是其他分布，这 些都会影响到选址。 ( 4 ) 吸引函数 吸引函数是设施对于顾客吸引程度的度量。由于它影响着顾客的消费行为， 所以对于选址有着极其重要的影响。吸引函数通常是指顾客与最近设施的距离， 距离越大，吸引力越小。距离越小，吸引力越大。有时吸引函数也可以是设施的 某种权重，权重越大，吸引力越大，权重越小，吸引力越小。不同的选址权重含 义往往不同，对于商店或超市，权重可以是卖场的面积、商品的种类，服务的质 量、停车的便利等，对于产品属性的设计，权重可以是产品对顾客的知名度。常 用的吸引函数有1 1 0 l ： 纠黼】- l 器器， = 最大吸引力一【吸引系数】【距离】。 北京化工大学硕士学位论文第一章概述 ( 5 ) 设施 设施的属性有很多，如设施是期望设施还是有害的设施，期望设施离顾客或 公众越近越好，有害设施离公众越远越好，设施是公用设施还是私有设施，待安 置的设施数是确定的还是不确定的，设施是部分合作的还是竞争性的，设施是分 等级的还是同级的，各点的设施选址费用是相同还是不同，设施的服务能力是有 限还是无限，设施是买还是租，设施之间是否相互影响，设施之问越近越好还是 越远越好，设施的大小相对于选址空间是忽略不计作为一个点看待还是设施太大 要作为一个区域看待，设施提供的产品或服务是单产品或服务还是多种产品或服 务等等。 ( 6 ) 目标 选址的目标分为最优化类型的目标和非最优化类型的目标，我们主要关注最 优化类型的目标，最自然的目标有利润型、费用型、需求型、环境型等，利润型 有利润最大、利润率最大、市场份额最大、产出最大等，费用型有选址总费用最 小、选址总费用与运作费用之和最小( 运作费可能是服务费用、可变成本、运费 或它们的和) 、距离之和最小、总运输时间最少、设施数最小等，需求型有覆盖最 大、重复覆盖最大、满足的需求最大、最大照离最小等，环境型有污染最小、 空气质量降低最小、危险最小、舒适度最大、最小距离最大等。有时目标还可能 有多个，它们可以属于同种类型或不同类型。选址目标还将在1 1 4 专门介绍。 ( 7 ) 市场 市场可能是竞争性的或是非竞争性的，各点的市场环境可能是相同或不同的， 市场原来可能是空的，即没有同类设施，也可能已有同类设施，后者称为条件选 址问题。所有的设旋可能是一次性安置完毕也可能是逐次安置，设施能否重新安 置，新的设施进入市场时是否有进入壁垒等。 ( 8 ) 决策变量 既然是选址问题，设施的位置必定是决策变量。模型的决策变量可以只是设 施的位置，或是既要确定设施位置又要确定设旌的数目，或者是既确定设施的位 置又确定设旌的权重，这里的权重可以是设施的大小、服务的质量、产品的产量、 产品的价格、产品的种类等。还可能是既确定设施位置又确定需求的分配，或者 既确定设施位置又确定行车路线等，此外，还可以把其他与设施位置密切相关的 量也作为决策变量。当然，决策变量越多，问题越复杂，越难于求解。 北京化工人学硕士学位论文 第一章概述 ( 9 ) 参数 模型中涉及到的很多参数往往并不能准确的知道，带有明显的不确定性，很 多参数带有统计或预测的成分，如现在及未来顾客的需求、顾客的分布、未来竞 争者要安置的设施数、顾客光顾各设施的概率等，还有一些参数带有明显的动态 性和主观性，如：需求随时间变化、竞争者选址随时间变化、适当的选址总费用， 适当的设施数、较大的市场份额、设施有较大的吸引力等，参数的随机性、模糊 性和动态性使得选址模型成为随机规划模型、模糊规划模型和动态规划模型。 1 1 2 选址问题的分类 按照选址要素选址问题有很多的分类方法，根据设施允许安置的空间，可分 为连续选址、网络选址和离散选址【13 1 。连续选址又称为平面选址，它允许在可行 的连续空间的任何地方选址，多半采用解析方法。网络选址允许在指定网络的顶 点与边上选址，而离散选址只允许在指定的一些离散点集上选址，后两者主要用 组合方法研究。根据模型目标的多少，选址问题还可以分为单目标选址与多目标 选址；根据目标的类型可分为最大型、最小型、最大最小型和最小最大型等；根 据选址的市场环境是竞争性的还是非竞争性的，即市场中有无竞争设施，可分为 竞争选址和非竞争选址：根据设施的属性，可分为受欢迎的设施选址与不受欢迎 的设施选址等；根据设施是属于私人的还是公共的分为私有设施选址问题和公共 设施选址问题；根据设旌是分层的还是不分层的分为分层选址问题和单层选址问 题；根据待安置设施的数目分为单设施选址和多设旖选址；根据输入的参数是随 时间变化的还是不变化的分为静态选址和动态选址；根据输入的参数是确定性的 还是不确定性的分为确定型选址和概率型选址；根据设施的服务能力是有限还是 无限分为有限服务能力设施选址和无限服务能力设施选址。其他分类方法可参见 文献 1 4 ，1 5 】。 1 1 3 选址研究中的典型问题 选址研究中的w 曲e r 问题、中值问题、覆盖问题、中心问题、多目标选址【1 2 1 、 竞争选址、不受欢迎的设施选址【15 1 、选址分配问剧1 7 。19 1 、选址路线问题【2 0 搬垮典 北京化t 大学硕士学位论文 第一章概述 型问题，都是引起广泛关注和深入研究的热点课题，研究的也较为成熟，b 舢d e a u 和c h i u 综述了5 0 多种有代表性的选址问题【1 4 ) 。由于很多选址问题都是m d - 完全的， 所以算法的研究有很大的余地，现在的研究也大多集中在算法的设计与改进上， 尤其是用现代启发式算法求解选址问题的研究。模型的研究主要是对已有模型改 进，使得更适合某些现实情况。 中值问题、覆盖问题、中心问题是最基本、最典型、最有代表性的选址问题， 研究的较早，也比较成熟，其成果为选址研究奠定了坚实的理论和方法基础，现 有的很多问题和模型都有它们的影子，了解了它们对于了解其他的选址问题大有 裨益，下面简要介绍一下这三类问题。文献 1 ，2 3 2 8 】综述了这三种基本的选址问题。 ( 1 ) 口中值选址问题 p 一中值选址问题是选定p 个设施的位置，使全部或平均性能最优的问题。通常 是使成本最小，如使总( 平均) 运输距离最小，使总( 平均) 需求权距离最小， 使总运输时间最少，或者使总运输费用最小等，故又称为最小和问题。这里的距 离指需求点与最近设旌之间的距离，需求权距离指需求点的需求量和该需求点与 最近设施的距离的乘积。这种目标通常在企业问题中应用，如工厂、仓库的选址 等，所以又叫“经济效益性”目标【2 9 1 。公共设施的选址也可以采用这个标准衡量 选址的效率，如学校、图书馆、邮局的选址等，故有人也称之为“集体福利性” 目标。 网络上的口中值问题是由h a k i i i l i 首先提出的【4 】，他同时给出一个著名的顶点 最优性质：网络上的p 中值问题至少有一个最优解完全由网络的顶点构成h ，30 1 。这 个性质把求解网络选址问题在某种意义上归结为求解离散选址问题，从而大大缩 小了搜索空间。k a r i v 和h a l 【i m i 证咀了一般网络上的沙中值问题是p 一完全的【1 3 】。 ( 2 ) 覆盖选址问题 设施a 覆盖需求点b 是指a 能在规定的时间或距离内服务b 。覆盖问题主要 有两种基本的模型：集合覆盖模型和最大覆盖模型。集合覆盖模型是1 9 7 1 年 t o r e g a s 、s w a i n 和r e v e l l e 首先提出的( 3 l 】，即用最少的设施安置费去覆盖所有需求 点，当每个设施的安置费相同时，问题简化为用最少的设施覆盖所有的需求点， 通常研究后者。由于离散和网络情况下的集合覆盖模型可能会有多个解，文献 3 2 ，3 3 】又分别提出了第二个目标：使新设施数最少和使重复覆盖最大。由于集合覆 盖模型要覆盖所有的需求点，所需设施数往往过大而超过实际承受能力，而且没 北京化t 大学硕士学位论文 第一章概述 有区分各需求点，人们自然会想到先固定设施数目，再确定它们的位置使得覆盖 尽可能多的需求点或需求量，这就是c h u r h 和r e v e l l e 提出的最大覆盖模型【3 4 j 。 h a k i m i 的顶点最优性质对两种覆盖模型都不成立，c h u r c h 和m e a d o w s 给出了一个 很类似顶点最优性质的伪顶点最优性质【3 5 】：对任何网络，存在顶点的一个有限扩 充集合( 很容易找到) 至少包含集合覆盖或最大覆盖模型的一个最优解。和集合 覆盖模型一样，最大覆盖模型也可能有多个解，d a s h n 把重复覆盖最大作为第二 目标，并引入了设施忙的概率，目标是确定给定数目的设施的位鼍，使得设施覆 盖需求的期望数最大，故又称为最大期望覆盖模型3 6 1 。和p 中值问题一样，一般 网络上的集合覆盖问题和最大覆盖问题都是 = p 完全的。 ( 3 ) p 中心问题 p 中心问题是指选定p 个设施的位置，使最坏的情况最优，如使最大反应时间 最小、使需求点与最近设施的最大距离最小或使最大损失最小等，所以也叫极小 化极大问题，最优目标值也叫p 半径。这是一种保守的方法，通常在军队、医院、 紧急情况和有服务标准承诺的服务行业( 如比萨店承诺半小时内把订餐送到) 中 使用，有时也称作“经济平衡性”目标【2 9 】。 网络上的p 一中心问题也是h a b m i 首先提出的【4 30 1 ，和覆盖问题一样，h a l 【i m i 的顶点最优性质对p 冲心问题也未必正确，m i n i e k a 【3 7 1 、k a r i v 和h a k i m i 口8 1 给出了 p 中心问题的伪顶点最优性质：对任何网络，存在顶点的一个有限扩充集合至少包 含绝对p 中心问题的一个最优解。 若p 是定值，顶点p 冲心问题和绝对p 冲心问题都可在多项式时间内求解【”】， 一般网络上的卢中心问题也是p 完全的p 踟，为算法研究指明了方向。 1 1 4 选址问题的目标 选址问题的目标对于选址结果有着重大的影响，c l l r r e m 、m i l l 和s c h i l l i n g 把 选址的目标分为四类i l2 l ：费用最小、利润( 率) 最大、需求型目标、环境目标， 这四个目标也可能会重叠。费用通常以运输距离代替，费用最小也可用总运输距 离最小代替，它是选址模型中的传统目标，很多经典的单目标选址都是最小化费 用，如简单工厂选址 3 9 】以最小化运输费用和选址费用为目标，集合覆盖选址问题 以最小化设施数目为目标从而以最小化费用为目标。私有企业除了关心满足需求 北京化丁大学硕士学位论文 第一章概述 和费用最小外，常常还要考虑收益，如要求选址的利润最大或利润率最大，所以 这类目标在私有企业中比较流行。需求型目标往往用在重视市场份额或服务质量 的情形，它最优化被服务的需求，如覆盖度最大，获得需求或市场最大等。由于 人们越来越关注环境，对于不受欢迎或造成污染的设施以及造成心理不适的设施 的选址，如核电站、化工厂、传染病医院的选址等，人们往往要考虑设施附近的 空气质量、人们生活质量、人们受到的影响以及各种污染和潜在的危险，目标可 以为使空气质量与国家空气质量标准的正偏差最小化，使生活质量最大化，使潜 在危险最小化等。 若把选址模型的目标和物理中的力模拟，选址问题的目标还可分为“拉”目 标、“推”目标和平衡目标三大类【4 0 】。拉目标适用于期望设施类型，设施离顾客越 近越好，如最小化加权距离或最大化利润等都是拉目标，最优化目标就好像是有 某种力强迫把设施拉近顾客一样，w 曲e r 问题、中值问题、中心问题和覆盖问题都 属于这类问题。推目标适用于不受欢迎设施的选址问题，设施离顾客或公众越远 越好，最大化加权距离就是推目标，反w 曲e r 问题、反中值问题、反中心问题和 反一覆盖问题( 反i 习题的目标和原来的目标相反) 等都属于这类问题。推目标就好 像是有某种力迫使设施远离顾客或公众一样。拉目标和推目标实现的是整体的最 优效果，但可能会使得个别顾客离设旌很远( 期望设施) 或很近( 不受欢迎的设 施) ，这样对这些顾客或公众就会很不公平，平衡目标的主要目的是要达到某种社 会平等或法律公平，使各顾客到最近设施的距离差距不会太大，就好像有某种力 量在调节平衡设施与各顾客或公众的距离。但这种目标单独使用往往会出现一些 奇异的结果，与实际明显不符，所以最好再附加第二目标，正因如此，这个目标 目前还存在争议。 1 2 竞争选址问题 所谓竞争选址，是指在竞争环境下的选址问题。这里的竞争环境指一些公司 在市场中已安置设施，并将有或可能有另一些公司在市场中安置新设施与其竞争 市场份额。竞争选址问题是工业布局、空间经济、区域科学和运筹学领域中的主 流研究课题，它的研究始于h o t e l l i n g 的种子论文f 3 j ，他讨论了在海滩上两个卖冰 北京化工大学硕士学位论文 第一章概述 激凌的小商贩的摊位选址问题，这里的市场是一个连续的线段，尽管这个市场的 形状过于简单，但它却能给出一些富有启发性的结果，并反映了竞争选址的一些 性质。在随后的几十年里，很多新的工作沿用h o t c l l i n g 的研究思路研究了其他几 何形状的市场，如圆形市场、三角形市场等，甚至还引入了其他一些策略，如设 施逐次进入市场【，尽管这种情况比较容易求解但与现实还是有较大差距。 1 2 1 竞争选址问题的分类 竞争选址可分为连续空间竞争选址、网络竞争选址和离散竞争选址；也可分 为静态竞争选址问题和动态竞争选址问题，静态竞争选址考虑的是一个阶段的最 优化问题，即假设一个公司选址后在别的竞争公司做出反应前有足够的时间获利， 动态竞争选址则考虑的是多个阶段的问题，认为公司对别的竞争公司的选址反应 时间为零，通常用s t a c k e l b e r g 博弈或n a s h 博弈研究。所谓s t 踮k e l b e r g 博弈是指参 与人的行动有先后的顺序，先行动者能预见到后者的行动，并且后行动者能在自 己行动之前观测到先行动者的行动，先行动者称为领导，后行动者称为随从。n a s h 博弈引入n a s h ( 纳什) 均衡的概念，其基本思想是，在一个解集中所有参与者的 策略都是对其他参与者所用策略的最佳对策，没有人能够通过单单改变自己的策 略提高收益。竞争选址研究大致分为两类：一类是从后来竞争者的角度出发，在先 来的公司已经安置设施的情况下，研究如何选址才能获得最大的市场份额或利润； 另一类是从最早进入市场的公司的角度出发，研究如何选址才能在后来的竞争者 进入同一市场时仍获利最大，比较极端的情况是使后进入者无利可图，从而垄断 市场。我们称第二类问题为预先抢占市场选址问题( p r e _ e l n p t i v ec 印t u r cp r o b l e m ) 。 有关竞争选址的文献综述有 1 0 ，4 l 一4 5 。 1 2 2 竞争选址模型 竞争选址问题有很多基础模型和扩展模型，如最大市场份额模型、预先抢占市 场模型及其它们的扩展等。 ( 1 ) 最大市场份额模型及其扩展 r e v e l k 于1 9 8 6 年提出的最大市场份额模4 6 】是一种很有前途的竞争选址模型， 9 - 北京化工人学硕士学位论文 第一章概述 被f r i e s z 称为很可能是未来竞争网络选址模型的三个基础模型之一【4 5 。这种模型 是从将要进入市场的公司的角度出发，考虑在市场中已有一些竞争设施的情况下， 如何在网络上选定p 个设施的位置，才能获得最大的市场份额。 该模型假设：各公司销售的产品或提供的服务是无差别的；顾客的光顾行为 取决于与设施的距离而不是价格；各公司单位产品或服务的成本相同：需求位于 网络的顶点，设施的选址也限定在网络的顶点；如果需求点到两个最近竞争设施 的距离相等，则两设旌平分该点的需求。对于像零售商店及类似设施，最大市场 份额目标等价于最大化利润。 最大市场份额模型基于c h l l r c h 和r e v e l l e 的最大覆盖选址模型，它很像p 中 值选址模型，我们把新进入的公司称为a ，市场中原有的公司由于与a 有相同的 竞争关系，我们通称为公司b ，下面要为a 选址，模型的数学形式如下【4 l 】： n 擒x q 咒+ 鲁z 盯只_ 协， ( 1 2 1 ) z ，一 v f ( 1 2 2 ) e q ( 掣) 只+ 刁1 v f ， ( 1 2 3 ) _ = p ( 1 2 4 ) j = i _ ，卫，弓 o ，1 ) v i j ，w j ( 1 2 5 ) 其中，q ：f 点的需求量( 单位) ；6 0 ：公司b 最靠近需求点f 的设施点 q ：_ ，点的选址费用( 元) ： i ( 酽) = w ，i 吒 钿 ： 选址变量： 分配变量 吒：点f 与点_ ，的距离( 公里) ； q ( 酽) = w j i 矗= 钿，且，酽 f l ，如果公司a 在_ ，点安置设施 巧2 1 0 ，否则 f 1 ，如果浦的需求完全分配给公司a 的设施 m 2 1 0 ， 否则 北京化丁大学硕士学位论文第一章概述 f 1 ，如果f 的需求分配给不在同一点的两个竞争设旌 1 i o 否则 模型的目标是公司a 获得的市场份额最大化，目标的第一项为单独由公司a 服务的市场份额总和，第二项为当需求点与a 、b 的最近设施距离相等时，公司a 获得的市场份额总和，约束( 1 2 1 ) 规定了f 点的需求完全分配给公司a 的条件，即 只有在( 卵) 中安置了a 的设施，f 点的需求才能完全分配给公司a ；约束( 1 2 2 ) 规 定只有在口( 酽) 中的某点安置了公司a 的设施，f 点需求的一半才能分配给公司a ， 约束( 1 2 3 ) 说明点f 的需求完全分配给了公司a ( m = 1 ，z j = o ) ，或者一半分配给了 a ( 咒= l ，= 1 ) ，或者完全分配给了b ( m = = o ) ；约束( 1 2 4 ) 是要安置p 个设施； 约束f 1 2 5 ) 是0 1 约束。 由于最大市场份额模型假定各设施权重相同，是静态和确定性的选址。有很 多模型对这些假设做了松弛，出现了很多扩张模型。e i s e l t 和l a p o n e 研究了各设 施权重不相同的情况【4 7 1 ，他们的模型不仅要确定最优选址还要确定各设施的最优 权重。r e v e l l e 和s e r r a 研究了设施可以重新安置的情况【柏】，s c 玎a 、m a r i a n o v 和 r e v e l l e 研究了设旌分为不同等级的情况，b e n a l i f 5 研研究了顾客成分混杂的情况， b e n a i i 和h a n s e n 研究了顾客光顾行为不确定，但可以用随机效用函数刻画的情 况，s h i o d e 和d r e z n e r 【5 2 1 研究了树网络上需求点的购买力是随机的情况，s e m 、 r e v e l l e 和r o s e i n g l 5 3 】研究了带有“经济存活”约束的情况，即每个设施获得的市 场份额必须达到一个最低标准，这里的标准是确定的，c o l o m 6 、l o u r e l l c o 和s e r r a 5 4 】 则研究了最低标准是随机的情况，建立了一种机会约束模型。s e r r a 和r e v e l l e 研 究了模型参数不确定的情况h “，如某点的需求或顾客数不确定，但可以假定它依 赖于经济的活力或社区的成长。他们利用了经典的情景方法( s c e n 撕oa p p m a c h ) ，也 就是需求和竞争者的选址在各种可能的情况下是不同的，尽管具体哪种情况会发 生是不确定的，但新进入的公司至少可以用两种不同的准则选址，一个是最大最 小准则，另一个是最小遗憾值准则。设t 是情况，s 是情况的总数，分别 代表第女种情况下f 点的需求和分配变量。注意这里的d j ，与情况女有关，所以记 北京化工人学硕士学位论文 第一章概述 最大最小准则的数学形式m 1 1 为： m a x 删 “只。+ 譬m v 七= l ，j( 1 _ 2 6 ) x v f ，v 后= 1 ，j( 1 2 7 ) e j t z ，t x j v f ，v 后= 1 ，j( 1 - 2 8 ) ，e q y * + z 陆l v f ，v 七= 1 ，s( 1 2 9 ) x ，= p ( 1 2 4 ) ，e j y 气， o ，1 v f ，w k ，v j j = l ，s ( 1 2 - l o ) 目标和约束( 1 2 6 ) 就是最大最小准则，其余约束的含义基本和最大市场份额模 型的相同。 如果是最小遗憾值目标，则模型的数学表达形式为： m i n 【， j f y n x j v f ，v 七= 1 ，s( 1 2 7 ) ：* x ， v f ，v t = l ，一，s( 1 2 8 ) j e t j a y + z n l v f ，v 后= 1 ，j( 1 2 9 ) x ，= p ( 1 2 4 ) j e j ，= x o ，1 ) v f j ，w 蜀，v = l ，s ( 1 2 1 0 ) z 。一口。y o 一半z 。u v i = 1 ，j( 1 _ 2 1 1 ) ，e“；j 其中，参数互表示在情况t 时为p 个设施最优选址获得的最大市场份额，也就 是要计算s 个最大市场份额问题，每一个对应一种情况。约束( 1 2 1 1 ) 的左边是各种 情况下给定公司a 的设旆选址时市场份额与最大市场份额的偏差。目标和约束 ( 1 2 1 1 ) 就是使遗憾值最小。 如果定义c ，为点的选址费用，则可建立如下的双目标选址，第二目标为选址 费用最小。 m a x 叫，+ 鲁。 m i n c j x ， j 占f ( 1 2 1 ) ，( 1 2 2 ) ，( 1 2 3 ) ，( 1 2 5 ) 北京化t 大学硕士学位论立第一章概述 既然是在总的市场份额和总的选址费用之间权衡，这里安置设施的数目约束 ( 1 2 4 1 将被去掉。 若定义h 为潜在的销售额，那么这个双目标问题可以转化为如下的单目标问题【4 l j ： m a x q 以+ 粤0 一勺_ i e tj d 厶 j e j 5 j ( 1 2 1 ) ，( 1 2 2 ) ，( 1 2 3 ) ，( 1 2 5 ) 但这时由于设施的数目不是固定的，若用原来用于求解最大市场份额的交换 方法来求解该问题将会失效。我们还可以考虑最大市场份额问题的其他扩展，比 如对于生产工厂的选址，我们还可以确定产品的价格和产量等。由于竞争者的进 入，需求的分配发生了变化，设施的重新选址和关闭也是竞争选址中值得注意的 一种重要情况，如公司a 原有p 个设施，由于竞争者的进入改变了原有的分配格 局，现要重新安置其中的r 个设施，新增s 个设施，则约束( 1 2 1 0 ) 变为 刁= p + 只巧= p 其中，t ，一是原有的p 个设施的集合。 j “ i e j ( 2 ) 预先抢占市场模型及其扩展 预先抢占市场选址问题首先由s e f r _ a 和r e v c l l e 研究，他们假设市场中只有 一个公司，比如说是公司a ，暂时还没有其他竞争者，公司a 要安置p 个设施， 而且知道未来将有个或多个竞争者进入市场，唯一的信息是知道竞争者共要安 置g 个竞争设施，现在考虑公司a 如何安置p 个设施，才能使得自己在竞争设旌 的各种最优安置情况下获利最大，也就是使得公司b 获得的平均晟大市场份额最 小，模型的数学表达式为： m a x ”。+ 鲁毛 s ，j ，x v f ， ( 1 2 1 ) z 算j v f ， ( 1 2 2 ) 扣d ( 蚪) y ，+ z 。墨l v f ， ( 1 2 3 ) x ，= p ( 1 2 4 ) x ，y ，：， o ，1 ) v f ，w ，( 1 2 5 ) 该模型形式和最大市场份额模型形式非常相似，主要的区别在于m ，q 的不同 北京化t = 大学颁士学位论文 第一章概述 最大市场份额模型中竞争者在网络上的选址是事先知道的，所以m ，c 也是明确知 道的，而对于预先抢占市场模型，由于竞争者还没有安置设旌，所以公司a 事先 不知道，q ，但是竞争者是在公司a 选址后进入的市场，他们当然知道a 的选址， 也就知道自己的m ，q ，从而可用最大市场份额模型选址以获得最大的市场份额， 公司a 的目标就是确定自己设施的位置使得竞争者获得的最大市场份额最小。这 个模型有个关键的性质陋5 1 ，即若公司a 、b 都安置p 个设旌，则在公司b 选址后， 公司a 获得的市场份额将不超过5 0 ，而公司b 获得的市场份额往往超过5 0 ， 比如公司b 如果完全和公司a 的选址相同，则将获得5 0 的市场份额。 由于预先抢占市场模型假定公司a 事先知道竞争者的选址数目，这个假设较 强，下面的模型松弛了这个假设，假定公司a 事先知道竞争者的最大选址数目为玎， 则模型的数学形式4 1 1 为： m a x z 。= m i n 喜妻( 喜q y ：+ 喜罟 s j y ：略 v f e ，七= 1 ，g( 1 2 1 2 ) z m x 鼻 v f ，七= 1 ，- 一，口 ( 1 2 1 3 ) y ：+ z 琅s 1 v f e ，七= 1 ，一，g( 1 2 1 4 ) x 盖= | j 七= l ，g( 1 2 1 5 ) y ：，x 盖 o ，1 ) v f j ，w e ，七= 1 ，g ( 1 2 1 6 ) 其中，z 4 ：公司a 获得的市场份额 g ：竞争者安置设施的最大数目： 碟= 舻黔邱媚外鬻痈糯拣蚴麟b = 舻黝和媚阶霈椭徘龇邝黝 壤= 舻凇和媚p 嚣魄脯翅溅 北京化工人学硕士学位论文 第一章概述 1 2 3 竞争选址模型的解法 尽管h a k i m i 证明了一般网络上的最大市场份额问题是n p 。难的【”】，但是对于 网络上规模比较小的这类问题，比如3 0 点以下的网络，r e v e l l e 利用了线性规划和 分支定界的方法求解。事实上，在很多情况下，几乎很少使用或根本不用分支定 界，这大概是由于最大市场份额问题和最大覆盖问题之间存在着密切的联系【3 4 】， 对于规模较大的问题，可以利用基于t i e t z 和b a r t 方法【5 7 l 的1 一交换启发式方法， 要求设施数必须已知。具体步骤是，先给出一个初始解，即p 个设施的初始位置。 再从中选一个设施移动到一个没有设施的点( 称为空点) ，若目标值改善，则把该 设旌安置在空点，否则取消此移动，把设施移到另外一个空点，重复上述操作， 当把该点移动到任何一个空点目标值都不改善时，就移动另一个设施，反复进行， 直到移动所有的设施目标值都不改善时，即得到问题的满意解。从计算时间上看， 这个计算方法非常有效，但是这个方法不能保证求得最优解。 对于最大市场份额模型的扩展模型，可以用松弛线性规划和分支定界方法求 解，也可以利用s e r r e 和r c i 、，e l l e 提出的两阶段启发式方法1 4 l l 求解，该方法也是基 于t i e t z 和b a n 方法的1 交换方法。第一阶段先分别求解每种情况，并选根据目标 选取一个初始解，第二阶段利用1 交换方法改善这个解。 对于上面的预先抢占市场模型，如规模较小，可以枚举a 的选址，然后用最 大市场份额模型求得竞争者的选址，从中选使竞争者获得市场份额最小的选址。 如规模较大，可采用启发式方法【4 ”。第一阶段，先用任何方法选定公司a 的p 个 设施的位置，然后利用最大市场份额模型求解竞争者的选址( 可用线性松弛和分 支定界求解) 。第二阶段，利用1 交换方法改进公司a 的选址，直到无法改善为止。 若为了减少计算，还可以在第一阶段求竞争者的选址时也利用1 交换方法。 和预先抢占模型一样，其扩展模型一般也不能求得最优解，但可以把求解预 先抢占模型的方法修改来求解其扩展模型。第一阶段，先用任何方法选定公司a 的p 个设_ 旖的位置，然后求解g 个最大市场份额问题分别确定1 ，2 ，七，g 个公司 b 的设施位置，并计算初始目标。第二阶段，公司a 利用1 - 交换方法通过调整设 施的位置改善第一阶段所得的解，转第一阶段。反复进行，直到无法再改善时停 止，所求得的解即为公司a 的近似最优选址1 4 ”。 北京化工大学硕士学位论文 第章概述 1 3 本文的主要内容和结构 本文主要研究了三类网络上的竞争选址问题，第二章提出了一个竞争选址新 模型，该模型既包含选址费用，又通过引入两个参数反映了聚集效应，同时给出 了两种求解方法一分支定界法和贪婪算法，最大市场份额模型是我们模型的一个 特例。第三章研究了双目标竞争选址问题，提出了两个模型，研究了它们的性质 与关系，并给出了一种精确算法和一种启发式算法。第四章研究了预