多周期竞争性设施选址问题优化研究_李进.pdf

交叉与综合Computer Knowledge and Technology电脑知识与技术第19卷第4期(2023年2月）第19卷第4期(2023年2月）本栏目责任编辑：李雅琪多周期竞争性设施选址问题优化研究李 进（华南理工大学，广东 广州 510641)摘要：市场的复杂多变给企业服务设施的选址带来新的挑战，设施选址决策需考虑市场的动态特性进行多周期维度的决策优化。文章构建了一个多周期的设施竞争选址模型，以覆盖需求最大化为目标，对设施位置与进行决策优化，并选用NSGA算法对双目标模型进行求解，算例结果验证了算法与模型的有效性。关键词：多周期；设施选址；模型中图分类号：TP3文献标识码：A文章编号：1009-3044(2023)04-0127-03开放科学（资源服务）标识码(OSID)：1 引言考虑到企业所面临的市场需求与外部竞争复杂多变，静态单周期的设施选址模型无法有效应对，本文在最大选址覆盖模型的基础上扩展构建了一个多周期的竞争性设施选址决策优化模型。模型将决策维度划分为多个时间周期，并允许各周期内各潜在位置服务设施可重新或关闭以应对市场变化。多周期选址问题已在中心选址1、应急救援物流2，闭环物流网络3-4等多个领域得到了广泛的研究。为解决共享模式下在线设施资源的波动，徐小峰等将单周期决策转变为多周期决策，数据结果验证多周期方案可有效降低设施的选址成本5。已有研究虽考虑到市场需求的周期性变动，但却忽略了外部竞争的变动。为此，本文聚焦于企业服务设施的网络布局，考虑到市场需求与外部竞争周期性变动，以最小化成本与最大化覆盖需求为双目标，建立一个多周期的竞争性设施选址优化模型，对设施位置进行多周期维度的决策优化。为求解问题模型，文章采用并改进了NSGA-算法进行求解，并通过数据实验来验证模型与算法有效性。2 问题与模型2.1 问题描述与研究假设某企业计划在新市场进行产品销售或服务，备选服务设施位置信息已知，潜在顾客需求点信息已知，且竞争者门店位置信息已知。市场环境是动态变化的，顾客需求与外部竞争情况将在不同时间周期内出现变化。外部竞争情况的变化表现在新竞争者设施的开放与原竞争者设施的关闭。为应对市场变化实现最小化成本与最大化覆盖需求的双目标，决策者需在不同的时间周期内重新调整各设施位置的运营状态。此外，模型做出如下一般性假设：(1)企业与竞争者所售产品或服务无显著差别；(2)设施对顾客的吸引力由距离决定；(3)各潜在顾客需求点的需求基于吸引力大小按比例分配至多个设施；(4)门店的开放、关闭在决策周期开始阶段立即生效；(5)各周期内，设施的开放运营或关闭均需支付成本；(6)各周期决策前，顾客需求与竞争者设施位置信息已知。2.2 模型符号1)集合：顾客位置集合：I；企业设施备选位置集合：J1；竞争者设施位置集合：J2；决策周期集合：T；其中Jo Jc=,即企业与竞争者设施位置无重合。2)参数符号：Mt:t周期内，计划开放设施的数量；Q:门店服务容量上限；wit:t周期时，顾客点i处需求量,i I；c1:设施开放建立的成本；c2:各周期内，设施的运营成本；dij:顾客i至设施j的距离,i I,j Jo Jc；uijt:t周期时，设施 j 对顾客 i 需求的吸引力,i I,j Jo Jc;pijt:t周期时，顾客i需求分配至设施j的比例,i I,j Jo Jc;决策变量：Xjt:t周期，位置j处设施是否开放j J1;收稿日期：2022-11-02作者简介：李进(1998)，男，安徽定远人，研究生，主要研究方向为供应链决策设计。E-mail：http：/Tel：+86-551-65690963 65690964ISSN 1009-3044Computer Knowledge and Technology电脑知识与技术Vol.19,No.4,February2023127DOI:10.14004/ki.ckt.2023.0207交叉与综合Computer Knowledge and Technology电脑知识与技术第19卷第4期(2023年2月）第19卷第4期(2023年2月）本栏目责任编辑：李雅琪2.3 需求与成本的推导计算本问题模型假定设施对顾客吸引力由距离效用决定，即uijt=f(dij)(1)，f(dij)为顾客关于距离的效用函数，如公式(1)所示，其中R为设施的服务距离上限。f()dij=d-2ij,when dij R0,when dij R(1)基于比例分配规则6，t周期时，顾客i所受总吸引力为j J1 J2uijt，那么设施j可占顾客i的需求比例pijt=uijt/j J1 J2uijt(2)。考虑到设施的建立是一项长期投入，为此本模型进一步区分了设施建立成本c1与运营成本c2。设施建立与运营的先后关系为：设施建立后才可运营，且各备选位置设施的建立至多只需一次，即在设施首次开放时建立支付建立成本c1与运营成本c2，后续周期中若继续开放运营只需支付运营成本c2。因考虑了全周期维度的建立成本，若设施建立后有若干周期未开放运营仍需分摊建立成本，因此模型忽略周期内的设施关闭成本。为此，引入参数Yj表示位置j设施是否被建立。2.4 最优化模型目标函数：MAX=t Tj Joi IwitpijtMINC=t Tj JoXjtc1+j JoYjc2约束：t Ti Iwitpijt Q,j Joj JoXjt=Mt,t TMYj=Mt TXjt,j JoYj=0,1Xjt=0,1(2)(3)(4)(5)(6)(7)(8)式(2)与式(3)为目标函数，模型以最小化成本支出与最大化覆盖需求为优化目标；式(4)式(8)为相关约束；式(4)为设施的服务容量上限约束；式(5)为各周期内开放设施的数量约束；式(6)与式(7)为Yj的取值 约 束，约 束 公 式(7)中M为 一 个 极 大 值，当t TXjt 0，Yj=1时左右同为极大值相等，或左右同为0时亦相等，式(8)为决策变量的二元取值的约束。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所示。表1企业备选设施位置信息编号12345经纬度99.96,49.5642.9246.338.5363.7497.8688.0740.638.61编号678910经纬度4.6721.6536.3339.3581.0291.027.339.355.9753.5128交叉与综合Computer Knowledge and Technology电脑知识与技术第19卷第4期(2023年2月）第19卷第4期(2023年2月）本栏目责任编辑：李雅琪表2竞争者设施位置与开闭信息编号1112131425经纬度86.8,59.0626.5595.928.1337.2411.5945.0398.9541.97周期1开 放开 放开 放关 闭关 闭周期2开 放开 放关 闭开 放关 闭周期3开 放关 闭关 闭关 闭开 放表3顾客点位置与需求信息编号26277475经纬度86.8,59.0626.5595.9211.5945.0398.9541.97周期1915213周期26882周期363864.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。表4设施位置决策结果备选设施编号周期1周期2周期3110120113010411151106101701081119000101015 总结本文考虑了一个多周期竞争市场中的企业设施选址问题，以覆盖需求最大化与总成本最小化为优化目标，建立一个多周期竞争性设施选址决策模型，并改进NSGA-算法用以问题模型的求解，最后的数据实验验证了模型与算法的有效性。本研究仅聚焦于设施位置对顾客效用的影响，现实的竞争市场中设施的质量设计、库存水平等因素都将对顾客效用与行为选择产生影响，这些方面在未来的研究仍需进一步讨论。参考文献:1 Gden H,Sral H.The dynamic p-Median problem with mobilefacilitiesJ.Computers&Industrial Engineering,2019,135:615-627.2 宋英华,苏贝贝,霍非舟,等.考虑动态需求的应急物资配送中心快速选址研究J.中国安全科学学报,2019,29(8):172-177.3 Shi J M,Chen W Y,Zhou Z B,et al.A bi-objective multi-periodfacility location problem for household e-waste collectionJ.International Journal of Production Research,2020,58(2):526-545.4 杨晓华,郭健全.模糊环境下多周期多决策生鲜闭环物流网络J.计算机应用,2019,39(7):2168-2174.5 徐小峰,郑瑶,邓忆瑞.考虑同时取送货需求带模糊容量限制的在线设施动态选址问题J.系统工程理论与实践,2020,40(9):2438-2449.6 Aboolian R,Berman O,Krass D.Optimizing facility location and designJ.European Journal of Operational Research,2021,289(