竞争型连锁经营网点选址模型与遗传算法解，本文主要内容关键词为：算法论文,网点论文,连锁经营论文,模型论文,竞争论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
一、问题的提出
竞争型连锁经营网点选址模型，用于帮助企业解决多个新增网点的选址问题，使该企业能 获取原有和新增网点市场份额之和的最大化。其内含的假设前提为，企业经营利润是市场份 额的递增函数，因而，市场份额最大化等价于利润最大化。
假设某一消费区域，内含若干消费者集聚点，另有若干服务网点，如零售店、餐饮店和其 他服务设施，分别隶属于不同的企业。服务网点对消费者的吸引力可归纳为两个方面，一是 服务网点与消费点之间的距离，二是服务网点的综合服务品质，分别简称为距离引力和品质 引力。两种引力之间存在互相替代的关系，如消费者为了得到较好的综合服务，愿意到较远 的服务网点去消费。
采用引力模型，可以计算出服务网点对消费者形成的距离引力和品质引力，以及所获得的 市场份额。通过优化新增服务网点的布局和调整对新增网点的投资预算，可实现该企业的市 场份额最大化。
二、参数与建模
设某消费区域，内含n个消费者集聚点，其坐标为(a[,i]，b[,i])，i=1，……，n。另现有k个 服务网点，其中隶属于某公司的网点有c个(0≤c≤k)。该公司计划新增p个连锁网点，其坐 标为(X[,m9]，Y[,m])，m=1，……，p。
设d[,ij]为第i个消费点至第j个现有网点之间的距离，i=1，……，n；j=1，……，k。d[,i] (X[,m]，Y[,m])为第i个消费点至第m个新增网点之间的距离，i=1，……，n，m=1，…，p。
。E[,j]和A[,m]分别为现有网点和新增网点的品质引力系数，j=1，…，k，m=1，…，p。
根据引力模型，设服务网点所实现的购买力，与其品质引力成正比，与该服务网点至消费 点之间的距离的λ次方呈倒数关系，λ为距离系数。因而，第i个消费点在第j个现有服务网 点上实现的购买，为
，
在第m个新增服务网点上实现的购买，为
。第i个消费点在第m个新增网点实现的购买，占所有现有和新增网点实现购买的比重，用
T[,m]表示，见下式。
设某公司在该消费区域，拥有现有服务网点c个，计划投资新增网点p个。投资实施之后， 该企业所获得的市场份额合计为T，可用下式计算：
其中，W[,i]是第i个消费点的购买力占整个消费区域购买力总额的比重。另该地区其他企业 获得的市场份额为F，可以导出F为：
令
，由于G[,i]和H[,i]均为现有网点的参数，故在决策优化模型中表现为常 量。因而，F可以表示为：
由于T+F=
，即整个消费区域总购买力为常数。由此，该公司投资决策中自身 市场份额T的最大化，等价于其他企业市场份额F的最小化。设B为企业新增服务网点的投资 总预算，B[,m]为第m新增网点的投资预算，m=1，…，P。若取投资预算为主要约束条件，该 优 化模型可以细分为两种情况。
1.预算固定分配—选址优化模型
预算固定分配，即预先规定新增网点的数量P（常数），规定各新增网点的投资预算B[,m]， 总的投资预算约束满足
。例如，取B[,m]=B/P，即在P个新建网点中均分总的 投资预算。将投资预算B[,m]，可换算为品质引力系数，A[,m]=A(B[,m])。令F最小化为预算固 定分配模型的目标函数，有：
决策变量为(X[,m]，Y[,m])，m=1，2，…，P。(X,Y)为新增网点选址的区域范围，若选址区域 为所有实数范围，事实上为无约束的非线性优化问题。
2.预算可变分配— 选址优化模型
设新增网点的投资预算β与品质引力系数A之间，存在某种函数关系，取函数A=A(β)。据 经验判定，该函数应为单调递增函数，其经济含义为若对某新增网点的投资越大，该新增网 点的服务环境和条件越好，品质引力越大。预算可变分配类型中的投资预算约束的表达式为 
。预算可变分配选址模型的表达式为：
决策变量为B[,m]，m=1，2，…，p；以及(X[,m],Y[,m])，m=1，2，…，p。
预算固定分配和预算可变分配两种类型，其共同特点为：①为非线性规划问题。②属于连 续型选址模型。③涉及多个网点优化选址。在优化过程中，可选择不同的p，通过运算得到 相对应的优化解。两种模型之间的主要区别为：前者为无约束的网点选址优化问题；后者为 含网点选址和预算分配且有约束的优化问题。由于目标函数F非凸，可能存在一个或多个局 部优化解。解决该类非线性规划问题的常用方法，是设计一种能够识别全局和局部优化解的 算 法，如采用启发式的算法。
三、基于Weiszfeld的启发式算法
1.Weiszfeld算法
Weiszfeld(1936)曾提出解决单一新增网点选址问题的算法，即令目标函数F的一阶偏导数 为零，导出单一网点选址的循环计算优化解。将多网点的选址(X[,m],Y[,m])，改写为单一网点 的选址(x，y)，用A代替A[,m]，在F（公式4）的右端，分子分母同乘d[λ](x，y)，可得到单一 选址优化模型，见下式：
取F(x，y)—阶偏导数，有：
令
。当满足
2.预算固定分配选址模型的求解
当推广求解多个新增网点选址问题，具体思路是采用变量分析，即假定其他新增网点的选 址为常量，一次只优化一个新增网点的位置。逐个计算优化后，即可得到p个新增网点的一 组优化解。根据优化初始值选取方式和应用Weiszfeld法的不同，可以细分为两种启发式计 算方法。
启发式—算法1，逐个随机产生p个新增网点的地址，应用Weiszfeld法加以优化，直至产生 p个新增网点的地址。得到p个新增网点地址之后，为了求得进一步的整体改善，逐个采用We iszfeld法再循环计算一遍，得到较优的一组解。
启发式—算法2，随机同时产生p个新增网点的地址，用Weiszfeld法逐个循环计算一遍，得 到一组优化解。第二次再随机产生一组p个新增网点的初始条件，用Weiszfeld法计算一遍， 得到第二组优化解。多次重复以上步骤，可得到多组优化解，从中选取较优一组解。
3.预算可变分配选址模型的求解
启发式—算法3，首先，为p个新增网点选择某种预算分配方式。例如，设B[,m]=B/P，随即 转变为预算固定分配的选址问题，可用算法1，或算法2求解。其次，假设新增网点布局不变 ，嵌入拉格郎日乘数，优化各新增网点的预算分配问题。经过多次重复运算，使目标函数逐 步优化，直至目标函数值的改善，小于预先给定的容差范围为止。
启发式算法的优点便于理解，计算过程较为直观。然而，由于非线性规划问题可能同时存 在全局优化解和局部优化解，采用上述算法，由于初始值选取的不同，在循环运算中，可能 落入局部优化解的陷阱。
四、基于遗传算法的求解
遗传算法是一种基于生物自然选择与遗传机理的随机搜索算法。遗传算法通过保持一个潜 在解的种群进行多方向搜索。这种种群对种群的搜索有能力跳出局部最优解，将搜索引向解 空间中最可能获得改进的区域。根据选址模型的要求，考虑基本计算步骤为：
①选择染色体v和基因表达形式。取染色体ν[,k]的实数表示X[k]=(X[,1]，Y[,1]，…，X[,p],Y[,p])，随机选择染色体初始种群ν[,k]，k=1，2，…，
为种群规模。
②染色体适值评估和父代选择。计算目标函数值f(X[k])，将其转换为适值函数eval(ν[,k] )，eval(ν[,k])=f(X[k])。采用正比选择策略，根据与适值成正比的概率选出新种群。计 算种群中所有染色体的适值和
，分别计算选择概率P[,k]和累计概率q[,k]
，然后产生一个随机数，根据累计概率q[,k]，逐次选择出父代染色体ν[',k]。
③交叉和变异。确定交叉率P[,c]，o≤P[,c]≤1。根据交叉率P[,c]，随机选出用于交叉的 父代染色体，采用凸组合交叉方法，产生后代染色体。计算乘子为λ[,1]+ λ[,2]=1，λ[,1]＞
0，λ[,2]＞0。考虑用黄金分割的方式确定λ[,1]，令λ[,1]=0.618。确定变异率P[,m]，0≤P[,m]≤1。以随机方式选取变异基因，采用精细变异和强烈变异的方法，对选出的基因进行 变异。精细变异，即对选出的基因（地址），加减一个随机的小正数ε。强烈变异则加减一个 随机的较大正数δ。可事先规定一个精细变异率，精细变异率和强烈变异率两者之和为1。
④确定采样空间，产生下一代的新种群。为保持后代的不断进化，采用扩大的采样空间， 双亲和后代有同样的生存竞争机会。具体采用(μ+λ)选择，指μ个父代和λ个后代同时竞 争 生存，最后选出μ个最好的父代和后代，构成下一代，并保持种群规模
不变 。
⑤遗传和进化。经过若干代的遗传和进化，使适值函数（目标函数）不断优化，逐步找出最 优解。笔者采用VB6.0语言，编写了遗传算法的计算机程序，以实现上述计算过程。
五、计算实例与算法比较
1.计算实例的输入变量
设有一正方型的消费区域，内部存在均匀分布的100个消费点。各消费点的位置坐标，参见 图1。各消费点占整个消费区域购买力总额的比重(W[，i])均为1，整个消费区域的购买力，总 计为100。该消费区域内现有商业网点7个(k=7)，坐标见图1。各商业网点的品质引力系数(
E[j])均为1。现有的商业网点均不属于新进入的公司(C=0)。另取距离系数λ=2。设新进入的 公司投资总预算为B，采用预算固定分配模型，对各网点平均分配总预算，即B[,m]=B/P，各 网点形成的品质引力系数值为A[,m]=1/P。
2.计算结果与比较
在采用遗传算法的计算中，取交叉率P[,c]=0.24，令λ[,1]=0.618，变异率P[,m]=0.4，精 细变异率为0.66。当新增网点数P不断增大，染色体的基因数量(2×P)也不断增大，为了保 证计算精度，需要加大种群规模和遗传代数。
从计算结果看，采用遗传算法，取得了较为理想的计算效果。当新增网点数P不断加大，决 策变量增多，计算难度和复杂性加大，采用遗传算法计算结果，仍具有良好稳定和精度，参 见表1。另，当P=10，采用遗传算法得到的10个新增网点的地址，分别为(7.35，3.59)，(1.50，3.44)，(7.48，5.46)，(3.47，1.57)，(8.54，7.51)，(2.53，7.52)，(1.54，1.48) ，(5.55，2.49)，(5.56，8.53)，(4.50，5.48)，获得的市场份额T=22.716，坐标图参见图 1。
六、结 论
本文分析了竞争型连锁经营网点选址模型，以及启发式计算法1、算法2和算法3，提出了采 用 遗传算法求解的基本思路和计算步骤。计算实例表明，应用遗传算法，方法可行，计算结果 稳定，精度良好。因而，设计供应链前端网点配置和配送中心的决策支持系统，在优化数学 工具箱中，可以增加遗传算法部分，以提供新的效率较高的计算方法。
表1 基于遗传算法的计算结果
网点 遗传算法(1)启发式算法(2) 比较(T)
数P 种群大小 遗传代数
市场份额T
算法1(T)算法2(T)
(1)-(2)
1
20
200
12.933
12.93
12.93 相同
2
20
200
15.363
15.36
15.36 相同
3
20
200
16.675
16.50
15.68 相同
4
20
300
17.680
17.58
17.68 相同
5
20
300
18.765
18.50
18.59 +0.175
6
20
300
19.577
19.22
19.43 +0.147
7
20
800
20.328
19.84
20.25 +0.058
8
30
800
21.330
20.77
21.16 +0.173
9
50
1000 22.031
21.39
21.79 +0.241
10
60
1200 22.716
22.12
22.53 +0.186
注：启发式算法1和启发式算法2的计算结果，取自有关文献