多周期竞争性设施选址问题优化研究

李进

关键词：多周期；设施选址；模型

1 引言

考虑到企业所面临的市场需求与外部竞争复杂多变，静态单周期的设施选址模型无法有效应对，本文在最大选址覆盖模型的基础上扩展构建了一个多周期的竞争性设施选址决策优化模型。模型将决策维度划分为多个时间周期，并允许各周期内各潜在位置服务设施可重新或关闭以应对市场变化。多周期选址问题已在中心选址[1]、应急救援物流[2]，闭环物流网络[3-4]等多个领域得到了广泛的研究。为解决共享模式下在线设施资源的波动，徐小峰等将单周期决策转变为多周期决策，数据结果验证多周期方案可有效降低设施的选址成本[5]。已有研究虽考虑到市场需求的周期性变动，但却忽略了外部竞争的变动。为此，本文聚焦于企业服务设施的网络布局，考虑到市场需求与外部竞争周期性变动，以最小化成本与最大化覆盖需求为双目标，建立一个多周期的竞争性设施选址优化模型，对设施位置进行多周期维度的决策优化。为求解问题模型，文章采用并改进了NSGA-Ⅱ算法进行求解，并通过数据实验来验证模型与算法有效性。

2 问题与模型

2.1 问题描述与研究假设

某企业计划在新市场进行产品销售或服务，备选服务设施位置信息已知，潜在顾客需求点信息已知，且竞争者门店位置信息已知。市场环境是动态变化的，顾客需求与外部竞争情况将在不同时间周期内出现变化。外部竞争情况的变化表现在新竞争者设施的开放与原竞争者设施的关闭。为应对市场变化实现最小化成本与最大化覆盖需求的双目标，决策者需在不同的时间周期内重新调整各设施位置的运营状态。此外，模型做出如下一般性假设：（1） 企业与竞争者所售产品或服务无显著差别；（2） 设施对顾客的吸引力由距离决定；（3） 各潜在顾客需求点的需求基于吸引力大小按比例分配至多个设施；（4） 门店的开放、关闭在决策周期开始阶段立即生效；（5） 各周期内，设施的开放运营或关闭均需支付成本；（6） 各周期决策前，顾客需求与竞争者设施位置信息已知。

2.2 模型符号

1） 集合：

2.3 需求与成本的推导计算

本问题模型假定设施对顾客吸引力由距离效用决定，即uijt = f （dij ）（1），f （dij ）为顾客关于距离的效用函数，如公式（1）所示，其中R 为设施的服务距离上限。

考虑到设施的建立是一项长期投入，为此本模型进一步区分了設施建立成本c1 与运营成本c2。设施建立与运营的先后关系为：设施建立后才可运营，且各备选位置设施的建立至多只需一次，即在设施首次开放时建立支付建立成本c1与运营成本c2，后续周期中若继续开放运营只需支付运营成本c2。因考虑了全周期维度的建立成本，若设施建立后有若干周期未开放运营仍需分摊建立成本，因此模型忽略周期内的设施关闭成本。为此，引入参数Yj表示位置j设施是否被建立。

2.4 最优化模型

目标函数：

3 算法设计

为解决所构建的双优化目标决策模型，本文将改进NSGA-Ⅱ算法进行求解。NSGA-Ⅱ算法以遗传算法为基础，是一种较为成熟的启发式算法，特别的NSGA-采用了快速非支配排序算法，降低了求解多目标模型时的复杂度，同时采用拥挤度比较算子和精英选择策保证了子代种群的多样性，有效避免了优化迭代过程中局部收敛。具体的算法流程如下：

步骤1. 初始化参数，输入种群规模N、最大迭代次数，交叉与变异率；

步骤2. 生成初代种群，gen = 1；

步骤3. 进行非支配排序，计算种群个体的适应度、拥挤度，并进行排序；

步骤4. 依据选择策略，生成新子代种群，且gen =gen + 1；

步骤5. 判gen 是否小于最大迭代次数，若小于转入Step 3，否则结束算法。

算法关键步骤详细设计如下：

1） 染色体编码：为对应多周期决策，染色体采用矩阵编码。算法初始化时随机若干矩阵，一个染色体矩阵即表示一个可行解，其中矩阵的行数对应决策周期，列数对应备选设施位置编号。基因值表示其开闭决策，值为0即关闭，值为1则开放。

2） 交叉变异：算法针对染色体的矩阵编码方式，采用了子矩阵交叉方式。首次，从父代种群内选择两个不相同的染色体，然后决定一个子矩阵位置，最后交换子矩阵内基因得到新解。染色体变异操作时，首先从染色体矩阵中选择若干位置，然后改变其取值。

3） 选择策略：算法将结合组合选择与精英选择策略，子代种群将由三部分组成。第一部分比例为α%，由父代种群内排序前α%的染色体解构；第二部分占比β%，从交叉变异后的备选染色体池中采用精英选择策略选出占种群数量为β%的个体；第三部分比例为（1 - α% - β%），由算法重新随机生成的新建构成。

4） 染色体接受规则：算法在交叉变异流程中将不断产生新染色体，为确保新染色体符合问题约束，需对可行性进行判断，若可行则选入，若不可行则拒绝新解，仍继续保留原父代解。

4 算例实验

4.1 算例背景

为验证模型与算法有效性，本节选用案例数据进行数值实验。数据集经处理后，共有10个备选设施位置点，5个竞争者设施，50个潜在顾客需求点，且市场共三个周期阶段，即T = 3。备选设施位置信息见表1所示，竞争者设施位置与开闭信息见表2所示，顾客点位置与需求见表3所示。

4.2 算例结果与分析

算法参数设置如下，种群数为30，最大迭代数为200，且染色体的交叉概率为0.3，变异概率为0.1；种群选择规则中第一部分比例为20%，第二部分比例为60%，第三部分为20%。企业计划各周期内均开放6个服务设施，即M1 = M2 = M3 = 6。建店成本c1 为15，周期运营成本c2 为5。算法关于覆盖需求与总成本目标的收敛图见图1所示，覆盖需求目标值在80代左右收敛，而总成本目标值先升后降，收敛结果表明算法有效实现了双目标同时优化。最后，选取帕累托等级为1的解集组合中需求目标适应度最高的解作为备选最优解，具体结果见图1所示，其覆盖需求目标值为844.99，总成本为180。

5 总结

本文考虑了一个多周期竞争市场中的企业设施选址问题，以覆盖需求最大化与总成本最小化为优化目标，建立一个多周期竞争性设施选址决策模型，并改进NSGA-Ⅱ算法用以问题模型的求解，最后的数据实验验证了模型与算法的有效性。本研究仅聚焦于设施位置对顾客效用的影响，现实的竞争市场中设施的质量设计、库存水平等因素都将对顾客效用与行为选择产生影响，这些方面在未来的研究仍需进一步讨论。