俞武扬, 简 悦

(杭州电子科技大学 管理学院,浙江 杭州 310018)

0 引言

竞争设施选址问题(CFLP)广泛存在于我们的日常生活中，包括购物中心，配送中心和仓库等设施的选址。该问题是为了在已经存在或即将发生竞争的市场中，选择一个或多个设施的位置，使得目标函数值最优。竞争选址的问题研究的求解目标是通常最优化类型目标，其中利润型目标，需求型目标和费用型目标是选址问题中的求解重点。目前已存在许多解决该问题的模型，为了贴近复杂多变的市场情况，逐渐衍生出许多变体，包括设施之间的预算分配，带有预见性的竞争，加入阈值等[1]。

为贴近真实的顾客选择行为，学者们将阈值的概念引入了竞争设施选址问题模型中。Serra等[2]在模型中假设为了生存，设施存在一个必须达到的需求阈值，只有捕获的需求量达到该阈值水平时该设施才能开放，否则不能在该位点开设新设施。Colomé等[3]不仅考虑了需求阈值，还将概率约束加入模型中，只有当分配给设施的总需求高于阈值的概率达到预期时，设施才能开放。Fernández等[4]提出了部分概率选择规则，该规则假设顾客只会光顾对其吸引力达到阈值的设施。Suárez等[5]不仅考虑了吸引力阈值，还将消费者的偏好添加到模型中，考虑了不同顾客的不同吸引力阈值。

在传统的竞争设施选址模型中，通常认为设施可以被所有需求点感知，但在实际生活中顾客并不会光顾所有设施。Drezner等[6]提出了竞争设施选址问题的覆盖模型，假设每个竞争设施都具有一个由其吸引力水平决定的“覆盖范围”，并且位于服务范围内的顾客将被该设施吸引。与传统模型不同，此模型允许丢失一些需求。当需求点不在任何设施的服务范围内时，需求就会丢失。Drezner等[7]使用了基于服务半径的模型，并将预算添加到模型中。Qi等[8]发现当服务半径达到一定值时，如果服务半径继续增加，解决方案将保持稳定。

国内随着物流行业，零售行业的蓬勃发展，近些年也有学者开展了竞争设施选址问题的相关研究。张曦等[9]针对企业扩张和并购问题进行了深入研究，建立了利益最大以及吞并最小的双目标竞争设施选址模型。吴国莹[10]用logit效用函数来表示顾客选择设施的概率，建立了以利润最大化为目标的竞争选址模型。肖剑[11]将费用约束加入到目标函数的约束条件中，并建立了DEA评价模型下的物流中心再选址模型。刘雄杰[12]探讨了网格平面上门店选址问题的选址和设计的双重决策问题。李蕾[13]考虑了物流中心的固定建设费用和运营费用，并建立了使新建物流中心总成本最小，所有顾客总费用最少的双层规划模型。

可以发现基于服务半径的模型比其它模型更贴近实际的顾客选择行为，但是在现实生活中，顾客不仅会光顾便利半径内的设施，也同样会光顾便利半径以外，但有较高质量的设施。因此，通过分析现实中的顾客光顾行为，本文针对这类顾客选择行为模式，研究了考虑质量阈值和顾客便利半径的竞争设施选址问题。

1 数学模型

1.1 模型描述

本文提出了一种新的顾客选择规则用来描述以下顾客选择行为：顾客不仅会光顾位于便利半径内的设施，同样也会光顾在便利半径以外，但高质量的设施。该规则定义如下：对于位于顾客便利半径以内或质量超过给定阈值的设施，顾客将根据其受到的吸引力的比例来选择光顾这些设施。质量阈值是否存在对顾客选择行为的影响如图1所示(左图不考虑质量阈值，右图考虑质量阈值)。

图1 质量阈值和便利半径对顾客选择行为的影响

在图1中，矩形代表需求点，三角形代表超过质量阈值的设施，菱形代表没有超过质量阈值的设施，位于顾客便利半径以内的区域用虚线包围的圆圈表示。对于质量不超过阈值的设施而言，设施的服务半径与顾客的便利半径一致，而质量超过阈值的设施服务半径可以认为是无穷大。从图1可知，如果仅考虑顾客的便利半径，则顾客只会选择光顾虚线箭头所指的四个设施。若顾客根据便利半径和质量阈值来进行选择，同样会选择光顾虚线圆以外的三角形设施，即顾客会光顾实心箭头所指的七个设施。

1.2 模型构建

假设一家新公司计划通过开设新设施进入该市场，而该市场中已经存在其他竞争设施。本文基于静态竞争，假设当前现有的公司未对新进入者采取任何行动。模型相关参数和变量设置如下：

i,I：需求点的索引和集合;j,J：现有设施的索引和集合;Wi：需求点i的需求量;diu：需求点i到设施u的距离;Qu：设施u的质量;δ：质量阈值;s：新设施的数量;β：顾客的便利光顾半径;x,X：新设施的索引和集合 (X⊆IJ)。

引力模型被广泛用于竞争设施选址问题，需求点所感知到的设施吸引力取决于设施的质量以及它们之间的距离。因此，对于需求点i，设施u(可以是现有设施或新设施)的吸引力由下式给出：

(1)

(2)

需求点i访问现有设施j的概率如下:

(3)

需求点i到访新设施x的概率为:

(4)

为了避免分母为零的情况，在分母中加入了一个参数ε,通常ε设置为一个非常小的数字。因此考虑便利半径和质量阈值的竞争设施选址问题可以表述为:

(5)

2 算法设计

对于小规模实例，竞争设施选址问题可以使用穷举法或商用优化软件如Lingo，CPLEX等来解决竞争设施选址问题。但是，在大规模实例中，这一问题的求解变得极为困难。由于大多数设施选址问题都是NP-hard问题，因此近年来大量研究致力于提出解决竞争设施选址问题的有效算法。

Fernández等[14]提出了两种基于排序的算法来解决静态设施选址问题，并证明了算法的有效性。基于排序的离散优化算法是邻域搜索算法的一种变体，只有在邻域搜索过程得到的解所获得的目标值优于当前解的目标值时才接受新解。为了更好地解决静态竞争设施选址问题，本文将排序算法和传统遗传算法相结合，得到了一种基于排序的遗传算法(RGA)。算法的符号和描述如表1所示。

表1 算法符号和描述

基于排序的遗传算法(RGA)流程:

生成初始解集合Y0, 令Y←Y0，rk=1,∀k=1,2,…|L|,Z*=0,Y*←Ø

While未达到迭代次数:

Ynew←Ø

For每两个相邻的染色体X1,X2∈Y//交叉算子

Ifpc>rand(0-1之间的随机数)

End If

End for

For每个解决方案X∈Y//变异算子

If pm>rand

随机选择x∈X,c∈C,交换x和c产生新解X′，

令Ynew←Ynew∪X′，Y←Y∪Ynew

End If

End for

While终止规则未满足://基于排名的邻域交换

For每个解决方案X∈Y

选择候选位点c∈C,交换x和c生成新的X′和C′，

IfM(X′)>Mmax

Mmax←M(X′),X←X′,C←C′，rk=c←rk=c+2,rk∈X′c←rk∈X′c+1

End If

End for

IfMmax>Z*,令Z*←Mmax,Y*←X,End If

End while

(4)选择

从Y中选择anum个解决方案并更新Y, 即|Y|=anum

End while

步骤1是交叉操作，假设有两个候选解X1,X2∈Y，解的长度(染色体的长度)等于新设施数s。随机选择r1,r2∈[1,s]，使r1

图2 候选解的交叉过程

步骤(2)和(3)都是基于邻域交换，它们之间的区别在于步骤(2)的突变具有一定的概率，并且可以接受比当前解更差的解决方案。且步骤(2)的邻域交换过程仅执行一次，并且每次生成的新解都会添加到现有解决方案集合Y中。步骤(3)是对Y中的所有可行解执行多次邻域交换。只有在交换的解所获得的目标值更优才接受新解，并且Y的大小不会因产生新的解决方案而增加。

3 计算结果与分析

3.1 RGA算法的性能

本节通过测试随机正态分布，泊松分布以及位于二维平面中的均匀分布这三种不同分布的实例来检测算法的有效性。所有测试实例都是随机生成，假设市场上有|J|个已有设施，一家新公司即将进入市场并开放s个新设施，除现有设施外的所有需求点所在位置都可以视为新设施的潜在位置。

首先针对小规模算例评估算法RGA的有效性，将RGA算法结果与穷举法找到的最优结果进行比较。RGA算法的参数设置如下：染色体种群anum的数量设置为10，每代基于排名的搜索的迭代次数为100，pc=0.8,pm=0.2，并运行10代，即进行了10,000次功能评估。为了提高结果的准确性，每个算例进行了10次测试，MRGA表示RGA算法的平均结果，穷举法最优解用Mopt表示如表2所示。

表2 RGA算法的最优性测试(β=20,δ=60,|J|=s=5)

从表2可以明显看出，任意一种分布情况下RGA算法都可以获得最佳解决方案。并且RGA算法可以在短时间内(小于6秒)解决小规模实例，而当需求点数为60时，穷举法用时已达到100秒以上。

表3 GA,RDOA,RGA算法在大型实例上的结果对比

观察表3可得,GAP1的值不超过0.6%，即RGA算法在大型实例上也能获得较为稳定的结果。进一步观察发现，RGA算法的性能在这三种算法中表现最优，RDOA也可以得到令人满意的解决方案，但它的求解结果比RGA算法稍差，而传统GA算法效果最不理想。

3.2 实例分析

最后，本文使用了浙江省杭州市江干区九堡50个小区的真实地理数据和坐标数据，以2020年8月小区楼盘价格和小区总户数给出了一个仿真实例。在该实例中每个小区作为一个需求点，目标是在这些小区中建立给定数量的设施，使得这些设施获取的市场份额最大，其中需求量与小区总户数成正比，设施的质量则与小区的楼盘价格成正比。数据集的部分参数在表4中展示。

表4 数据集中的部分参数

在该实例中，顾客遵循具有便利半径和质量阈值的比例规则，已有设施位于人口最稠密的位置。本文考虑了当β=800，δ=35000时设施数量对市场份额的影响。注意，只要确定参数δ，就可以确定预设质量超过阈值的设施数量(由参数U表示)和质量超过阈值的已有设施数量(由参数E表示)。确定新设施位置后，参数N表示超出质量阈值的新设施数量。表5显示了每种实例的最佳解决方案。

表5 设置不同|J|和s时的最优解(β=800,δ=35000,U=8)

如表5所示，在仅改变新设施数量的情况下，市场份额随着设施数量的增加而增加。新设施数量相同时，市场份额会随着已有设施数量的增加而减小。进一步观察可知，新设施总会选择超过质量阈值的设施从而能够吸引更多的顾客。

为了研究质量阈值对市场份额的影响，令δ以步长为1000从35000增长到40000,分别计算新进企业在给定质量阈值下所获得的市场份额，并与没有质量阈值(δ=∞)的实例进行比较。假定现有设施和新设施的数量相同(|J|=s=3),距离限制β= 800,对应于不同阈值的最佳解决方案如表6所示。

表6 质量阈值δ对市场份额的影响(|J|=3,s=3, β=800)

从表6中可以看出，若模型中添加了质量阈值，只要存在质量超过质量阈值的设施，所有顾客的需求就可以得到满足，但仅考虑距离限制时，情况并非如此。值得一提的是，质量阈值与市场份额没有直接关系，而是通过影响质量高于阈值的设施数量而间接影响市场份额，参数U通常随着质量阈值的降低而增加。当δ=38000和39000时，即使更改参数δ，如果U的值不变，目标函数的值也不会改变。当δ=36000和37000时，新设施放置位点相同，但市场份额不同，表明即使设施放置地点相同，当参数U改变时，目标函数的值也会改变。图3展示了不同质量阈值时的最优解。其中，三角形和正方形分别表示现有设施和新进设施，未超过质量阈值的设施所能吸引的需求位点在图中用直线连接，而超过质量阈值的设施的没有服务半径的约束，可以被所有需求点感知。

图3 不同质量阈值(|J|=s=3, β=800,左图δ=35000,右图δ=40000)

观察图3发现，当δ=35000时，新公司选择在其中两个位置放置新设施，另外一个设施放置在已有设施附近，以抢占已有设施的市场份额。同样，当δ=40000时，新公司选择在其中一个超过质量阈值的位点放置新设施，而其余两个设施放置在邻近已有设施的区域。这意味着只要有可放置的高质量位点，新的设施必会放置在超过质量阈值的位点上，以吸引全部的需求点，而那些未超过质量阈值的设施通常会选择已有设施附近的位点以抢占更多的市场份额。

下面研究在设置不同参数δ时，新公司的市场份额如何随着不同的便利半径而变化。考虑了以下三种情况：δ=35000(U=8,E=1)，δ=40000(U=2,E=0)和δ=∞，市场份额随参数β的变化如表7所示。

表7 服务半径β对市场份额的影响(|J|=s=3)

分析模型可知，参数δ影响超过质量阈值的设施数量，参数β影响不超过质量阈值设施的服务半径。观察表7发现，当δ=35000时，随着β的增加，新设施获取的市场份额先减小后增大，这是因为随着覆盖半径的增加，现有的未超过质量阈值的设施吸引了更多的客户，这导致新进入公司的市场份额下降，进一步增加覆盖半径后，新进公司可以获得更多需求，其获得的市场份额开始上升。当δ=40000时，由于不存在超过质量阈值的已有设施，市场份额随覆盖半径的变化规律与δ=35000时相同，但其所获得的市场份额明显高于δ=35000时的情形。而当δ=∞，即不存在质量阈值时，新设施获得的市场份额会随着覆盖半径的增加明显增大。这是由于不存在质量阈值时，所有设施的服务范围都由服务半径β决定，增加β能够增大设施吸引的需求量，从而使得设施获得的市场份额增大。

4 结论

本文提出了一个考虑质量阈值和顾客便利半径的顾客选择行为，这是对基于便利半径选择行为的扩展。针对该选择行为下的竞争设施选址问题，提出了一种改进RGA算法。通过不同规模的数值实验研究了RDOA算法的有效性，发现RGA算法可以获得稳定的结果，并且优于RDOA和GA算法。通过一个仿真实例研究，发现质量阈值对市场份额至关重要，只要存在超过质量阈值的设施，就可以满足所有需求点的需求。值得注意的是，质量阈值本身并不与市场份额直接相关，而是通过控制超过阈值的设施数量来影响市场份额。