具有设施容量选择的两阶段设施选址问题研究.pdf

Operations Research TransactionsVol.27No.3Sep.,20232023年9 月运筹学学报第2 7 卷第3 期DOI:10.15960/ki.issn.1007-6093.2023.03.006具有设施容量选择的两阶段设施选址问题研究吴廷映1王瑶1周支立2任亚婷1摘要设施位置与设施容量是影响供应链长期运营成本和服务质量的重要因素，也是企业获得竞争优势的两个决定性因素。针对设施选址及容量选择优化问题，本文提出以最小化成本为目标的混合整数规划模型，对工厂和仓库的位置及容量，工厂到仓库的产品流和客户到仓库的分配进行优化。根据模型特点设计拉格朗日松弛算法对其进行求解，为了提高解的质量，本文开发混合模拟退火禁忌搜索算法对拉格朗日松弛算法的求解结果进行改进。本文利用随机生成的大量具有不同规模及参数的实例对算法的有效性进行检验，数值实验表明该算法适用于同时优化设施选址及容量选择问题。关键词两阶段设施选址，设施容量，拉格朗日松弛算法，混合模拟退火禁忌搜索算法中图分类号0 2 2 1.1,0 2 2 1.42010数学分类号9 0 C05,90C10,90C59A two-echelon facility location problem withchoice of facility sizeWU Tingyingl.tWANGYaolZHOU Zhili2REN YatinglAbstract The facility location and size are important factors that affect operationcost and service quality of supply chain,and also two decisive factors for enterprises togain competitive advantage.In order to optimize facility location and size simultaneously,a mixed integer programming model is formulated to minimize the total costs,and todecide the location of plants and depots,select sizes for the plants,determine the productfows from the plants to the depots and assign the customers to the depots.Accordingto characteristics of the problem model,a Lagrangian relaxation algorithm is designed tosolve the problem,and a hybrid simulated annealing tabu search algorithm is developedto further improve the solution quality.To test the validity of the proposed algorithm,a large number of randomly generated instances of different sizes and parameters areprovided.The numerical results indicate that the proposed algorithm is effective andefficient for the two-echelon facility location problem with choice of facility size.Keywords two-echelon facility location problem,facility size,Lagrangian relax-ation algorithm,hybrid simulated annealing tabu search algorithmChinese Library Classification0221.1,0221.42010 Mathematics Subject Classification 90C05,90C10,90C59收稿日期：2 0 2 0-0 7-301.上海大学管理学院，上海2 0 0 444;School of Management，Sh a n g h a i U n i v e r s i t y,Sh a n g h a i 2 0 0 444,China2.西安交通大学管理学院，陕西西安7 10 0 49;School of Management，X i a n Ji a o t o n g U n i v e r s i t y,X i a n710049,Shaanxi,China十通信作者E-mail:8427卷吴廷映，王瑶，周支立，任亚婷如何设计供应链网络使得产品及时、高效地配送到客户，是当今竞争环境中企业战略决策的关键问题，供应链网络中的设施选址对企业利润和竞争力有着重大影响。因此，设施选址问题（facilitylocation problem，FL P）从196 3年被Cooper1提出至今，仍然是众多学者的研究热点之一。FLP可分为：单阶段和多阶段设施选址，无容量和有容量限制设施选址，单源和多源设施选址，详细内容可参考ReVelle等 2 和Melo等 3 的综述论文。作为单阶段设施选址问题（single stage facilitylocation problem，SSFL P）的扩展，两阶段设施选址问题（twostagefacilitylocationproblem，T SFL P）需要确定工厂和仓库的位置，使得产品从工厂流向仓库，然后通过仓库将产品配送给客户来满足客户的需求，其目标是最大限度地减少总成本。Klose4,5针对两阶段有容量限制的设施选址问题(two stagecapacitated facility location problem，T SCFL P)，提出了一种基于线性规划松弛的启发式方法 4 和拉格朗日松弛切割法 5。对于该问题,Fernandes等 6 提出了一种有效的遗传算法来对其求解。金莉等 7 采用嵌入拉格朗日启发式算法的分支定界来求解。Yang等 8 结合割平面法、局部分支法、内核搜索法和分割求解法，设计了一种混合算法来求解。张震等 9 考虑到商品退货的现实情况，构建了多商品多来源的集成设施选址库存模型，并设计了改进的混合差分进化算法进行求解。上述的研究都仅侧重于确定设施位置以及从设施到客户的产品流。然而，设施选址问题还涉及到所选设施的容量决策。设施容量不仅极大地影响其固定开设成本，还因规模经济而影响单位生产或处理成本。基于此，越来越多的学者开始关注设施选址及容量选择优化问题，但是目前大部分研究集中在SSFLP上。例如,Harkness 等 10 研究了单位生产成本与产出量成正比的设施选址问题，提出了四种不同的优化模型并利用分支定界算法对其进行求解；Carrizosa 等 11 研究了目标函数为非线性的设施选址问题，在该问题中，设施开设成本是开设设施数量的非线性递增函数，其目标是最小化设施开设成本和运输成本之和，并提出了两种拉格朗日松弛方法求解该问题。由于规模经济的影响，不同设施容量下单位生产或处理成本都将不同。TSFLP问题作为SSFLP问题的扩展，比SSFLP更为复杂，如何在TSFLP问题中同时考虑工厂和仓库的容量选择，以及不同容量下不同的单位生产成本和处理成本，将大大增加模型的复杂性，使得该问题更难求解。据本文作者所知，在TSFLP中鲜有考虑设施容量选择的研究。因此，本文在TSCFLP的基础上，研究具有容量选择的两阶段设施选址问题（two echeloncapacitated facility location problem with choice of facility size,TECFLP-CF)。该问题中,每个备选的工厂和仓库均有若干种不同的容量可供选择。在充分考虑设施容量对总成本影响的基础上，构建以设施开设成本、生产和处理成本以及运输成本之和最小化为目标的混合整数规划模型。由于TECFLP-CF属于NP-hard问题，故首先采用拉格朗日松弛算法求解该模型的较满意的解，其次，为了提高解的质量，设计混合模拟退火禁忌搜索算法，进一步改进拉格朗日松弛算法求得的最佳上界解。最后基于随机生成的大量具有不同规模及参数的实例验证所提出算法的有效性。1问题描述与模型TECFLP-CF需在若干候选点中确定工厂和仓库的位置及容量，以及从工厂流向仓库的产品流和客户到仓库的分配方案，以便在满足客户的需求同时，使得设施固定开设成本、工厂的生产成本、仓库的处理成本、工厂到仓库的运输成本以及客户的分配成本之853期具有设施容量选择的两阶段设施选址问题研究和最小。1.1符号定义集合和参数：I：工厂集合，J：仓库集合，K:客户集合，SP:工厂iEI可以选择的容量类型集合，SD;:仓库iEJ可以选择的容量类型集合，cpim:工厂iEI的容量类型为mESP,的最大容量，cdjin:仓库jEJ的容量类型为nESD,的最大容量，dk:客户kEK的需求，fpim：工厂ieI的容量类型为mESP,的固定开设成本，fdin:仓库jEJ的容量类型为nESD,的固定开设成本，Pim:工厂iEI的容量类型为mESP,的单位生产成本，hin：仓库jEJ的容量类型为nESD,的单位处理成本，ti：工厂iEI到仓库jEJ的单位运输成本，Cjk:客户kEK到仓库iEJ的单位分配成本，决策变量：uim:工厂iEI的容量类型为mESP,开设时为1,否则为0,Uin:仓库jEJ的容量类型为nESD,开设时为1,否则为0,aimjn:从工厂i的容量类型为mSP运输到仓库J的容量类型nESD,的产品流,2ink：客户kEK分配给仓库jEJ的容量类型nESD,时为1。1.2数学模型TECFLP-CF模型如下：minZ Z_ fpim Lim+Z(pim+ta)LimjniEI mESPiiEImESPijEJnESDj+ZZfdimujn+)ZZ(hjn+Cjk)dkzink(1)jEJnESD;jEJnESD,kEKS.t.CimjncpimUim,ViEI,mESPi,(2)jEJnESD;8627卷吴廷映，王瑶，周支立，任亚婷uiml,ViEI,(3)mESPiCimin-dkZjnk=O,VjEJ,nESDj,(4)iEImESPikEKdkZinkcdjnUjin,VjEJ,nESDj,(5)keKum1,viEJ.(6)nESDjzjnk=1,Vk EK,(7)jEJnESD;uimE(0,1,ViEI,mE SPi,(8)Ujn E(0,1),VjEJ,nESDj,(9)aimjn0,VieI,mESPi,jeJ,n ESD,(10)zink E(0,1),VjEJ,nESDj,kEK。(11)模型的目标是使总成本最小，包括工厂开设成本，在工厂生产产品并将产品从工厂运输到仓库的成本，仓库开设成本和处理仓库中的产品并将客户分配给仓库的成本，即式(1)。式(2）确保从工厂运出的总产品流量不超过该工厂容量，如果工厂未开设，则该总产品流量为零。式（3）表示一个工厂最多可以选择一种容量类型，或者任何容量类型都不选择，即该工厂未开设。式（4）为仓库处的流量平衡约束。式（5）确保分配给仓库的客户需求不能超过该仓库容量，并且没有客户被分配给关闭的仓库。式（6）表示一个仓库最多可以选择一种容量类型，或者任何容量类型都不选择，即该仓库未开设。式（7）确保每个客户只被分配给一个仓库。式(8)(11)为相关变量的非负整数约束。2拉格朗日松弛算法拉格朗日松弛算法（Lagrangianrelaxationalgorithm，L R A）是求解混合整数线性规划问题的最有效方法之一，其基本原理是通过引入拉格朗日乘数将难以处理的复杂约束松弛到目标函数中，从而将原问题分解成易于求解的子问题。该方法已广泛应用于求解大规模设施选址问题 5,10 。因此，本文采用该算法来快速求解该问题的上下界。2.1TECFLP-CF的拉格朗日松弛算法松弛TECFLP-CF模型的不同约束条件可以得到不同的拉格朗日松弛问题，例如松弛约束（4)和（7)，(2）和（7)，或（4)和(5)。选择合适的松弛可以得到更好的上界和下界。作者通过对比松弛（4）和（7)，（2）和（7)，（4）和（5）后的效果，发现松弛（2）和（7）比松弛（4）和（7）或（4）和（5）效果更好。所以，本文采用引入非负拉格朗日乘数im(iEI,mESP）和k(kEK）来松弛约束条件(2)和（7)，得到拉格朗日松弛问题LR(,)利87具有设施容量选择的两阶段设施选址问题研究3期如下：LR(,)=min(fpim-Qim).uimiEImESPi(pim+tij+Qim/cpim)aimjniEImESPijEJnESD+ZZfdjinUin+)(hjn dk-Cijk dk-u)2jinkjEJnESD;jEJnESD,kEKk(12)kEKs.t.(3)(6),(8)(11)。根据上述模型的特性，LR(,）可以被转化为以下两个相互独立的子问题：LRi()LR2(,)。LRi()=min(fpim-im).uim(13)ieImESPis.t.(3),(8)。该问题通过观察即可精确求解，对于每一个iEI，设m为fpim一im白的最小值对应的容量类型，即m=argminmeSP（(f p i mQ i m)eg/cpeg)。如果fpim一Qim小小于0,则设uim=1，u i m=0，mE SP，mm；如果fpim-Qim大于等于0,则令uim=0,Vm E SPi。LR2(,)=min(pim+tij+Qim/cpim)LimjniEImESPjEJnESDj+ZZfdjinUinjEJnESDj(hin dk-Cjk dk-k)2jink,(14)jEJnESD,kEKs.t.(4)(6),(9)(11)。在该子问题中，变量 zimin和zjink之间的唯一联系是约束条件（4)。在LR2(,B)的最优解中，容量为n的仓库必定由唯一的供货成本最低的工厂供货，设,m）=argminiel,meSP(pim+tij+Qim/cpm),则在最优解中,必定满足 aimjn=Zkek dk-zjnk(j eJ,nESDi)，i m i n=O,i i,m m,则该子问题转化为如下形式：LR2(,)=minfdjnUjnjEJnESDj(hjn dk+Wim dk-Cjk dk-k)zink,(15)jEJnESD,kEKs.t.(5),(6),(9),(11),其中Wim=miniel,meSP.(pim+ti+im/cpim)。该问题可进一步分解为|JSD,|个独立的0-1背包问题，即可用Pisinger12提出的MINKNAP求其最优解。TECFLP-CF的下界LR(,)即为LRi()和LR2(,)的目标值与ZkEK之和。8827卷吴廷映，王瑶，周支立，任亚婷2.2次梯度优化次梯度优化是一种迭代优化的方法，其使用当前次梯度信息来更新拉格朗日乘数，如果满足给定的停止准则，则终止该过程。为了求解LR(,)，本文采用次梯度优化近似求解相应的拉格朗日对偶问题。拉格朗日松弛问题的对偶问题如下：D:max LR(,)。(16)0,设(al,0,2)为第1次选代时 LR(al,Bl)的最优解。令m=jsnesDCimjncpim-m，Vi e I,mSPi，n k=1-D j e h，Vk K，则第I+1茨送代中的拉格朗日乘数更新如下：1+11=max(alim+0 lim,0,(17)Qiml+1=B%+0l.nk。(18)其中0 l=入(BUB-LB(al,)/(ZielmesP(im）+h e k(m),表示第|次选代时的步长,BUB和BLB分别表示第1-1次迭代中产生的最佳上界和最佳下界。入为（0,2)上的一个参数，若对于给定的NLag次连续迭代中，最佳下界没有得到改进，则该值减半，即入:=入/2。设LLag为最大迭代次数，ELag 为给定的大于零的最小常数。次梯度优化的具体步骤如下：Step 0 初始化 NLag,LLag,Ao 和 eLag。令 BUB:=+0,BLB:=-00,Qim=0,Vi EI,m E SPi,=0,Vk E K,入:=入o 及 l:=0。Step 1若lLLag且入 ELag，求子问题LRi(l）和 LR2(l,l）的最优解。令LB=LB(,)，若LBBLB,设BLB:=LB,若在 NLag次连续选代中BLB未得到改进，设入：=入/2；否则停止。Step2基于LRA构建TECFLP-CF的可行解（第2.3节)。令UB为当前解的目标值。若UBT时，初始化TM。如果lt=Lt，令T：=n T,lt:=0。令当前解=C*，局部解：=C*，m t:=0,n t=0,重复Step2.12.3。Step2.1当mtMt且ntNt时，随机选取满足仓库容量约束的转移或交换算子，计算不同算子下的成本变化,令mt:=mt+1。若f(S)+f(S)，或 0 且该算子不违反禁忌条件，或 e-/T(随机参数均匀分布在（0,1）上）且该算子不违反禁忌条件，则执行所选算子更新当前解C，更新TM，且令nt：=n t+1。若f(C）f(C*)，令lt:=lt+1，否则通过求解由u和 组成的相应运输问题来确定新的流量，由此获得由u、r 和 组成的新的解。如果 F(s)F(s*)，令$*:=$,$*:=S,lt:=0,否则lt:=lt+1。Step 2.3降温,T:=T。4算例分析由于TECFLP-CF是一个新问题，尚未有标准的算例，故本文使用随机生成的算例。算法在 Intel CoreTM 2 2.33 GHz Quad CPU Q8200,2GB RAM,Microsoft Windows 7 操作系统下运行，使用C+进行编程。本文首先测试了50 个算例，通过与CPLEX结果比较来评估LRA和HSATS的求解速度和解的质量。此外，本文还测试了具有不同参数的180个算例，例如工厂容量与客户需求的比率，仓库容量与客户需求的比率，工厂容量的数量和仓库容量的数量，来评价LRA和HSATS的求解速度和解的质量。4.1算例生成结合有容量限制的设施选址问题15和有容量限制的两阶段设施选址问题5的特点，本文通过以下方式生成随机算例。备选工厂，备选仓库和客户的坐标均在单位正方形内随机选取。单位运输成本为两点之间欧式距离的10 倍。Ua，b 表示在区间a，b 上的均匀分布，客户的需求dk在U5,，35上生成。假设cpipcpig，如果p，首先在U10,160上生成每个工厂的容量cpiSP:|及每个仓库的容量cdjisDjl，然后利用比率Repd=Zie CPalsPl/Zkek dk和 Redd=DjeJ CdjisD,l/Zhek dh 缩放容量。对于每个mSPil，令cpim=mcpilsP-lo/SPil(参数。在U0.9,1.1上随机选择)，对于每个n1和n1,利用U0.9,0.95上选择的随机参数分别乘以生产成本 pi(m-1)和处理成本hj(n-1)可得到 pim 和 hjn。每个容量的工厂或仓库的固定开设成本由其容量乘以U20,25上选择的随机参数确定。4.2算例求解次梯度优化的参数设置为：LLag=3000,eLag=10-4,NLag=40和入o=1.5。H SA T的参数设置为：TLmin=15,TLmax=20,To=200,=0.97,Lt=20,P1=100,29227卷吴廷映，王瑶，周支立，任亚婷Mt=100K|，P2=2，即Nt=100K|，n=1.1,t=0.01。采用CPLEX12.5求解MIP。U BLa g 和LBLag分别表示LRA求得的最佳上界和最佳下界，UBH表示HSATS求得的上界，UB表示CPLEX求得的最佳上界。计算结果如表15所示，表中的列标题含义为：I|J|K:算例规模，其中|为工厂数，IJI为仓库数，K|为客户数，GLag:UBLag 和 LBLag 之间的相对偏差，即(UBLag-LBLag)/LBLag 100,GH:UBH和LBLag之间的相对偏差,即(UBH-LBLag)/LBLag100,GHC:UBH与UBc之间的偏差，即(UBH-UBc)/UBc100,TLag:LRA 的 CPU时间,TH:HSATS 的 CPU时间,TLagH:LRA和HSATS的CPU时间,TLag+TH,Tc:CPLEX的 CPU 的时间,Avg:平均偏差或平均CPU时间，Max:最大偏差或最大CPU时间。为了测试LRA和HSATS的效率和稳定性，本文用CPLEX的求解结果进行比较。其中，Repd=2.0,Redd=2.0,SP=3及|SD;l=3。由表1可知，CPLEX只能求得第一组算例的最优解，LRA上界与下界之间的平均偏差为0.7 4%2.0 0%，最大偏差为2.42%，HSATS上界与LRA下界之间的平均偏差为0.51%1.7 5%，最大偏差为2.35%。显然，LRA为TECFLP-CF求得了很好的上界和下界，而且HSATS效果也很好。与CPLEX相比而言，HSATS上界与CPLEX上界之间的平均偏差为-0.45%0.7 0%，并且随着问题规模的增加该平均偏差会逐渐减小。因此，对于较大规模问题，HSATS可以求得比CPLEX更好的解。而且CPLEX比LRA和HSATS花费更多时间。由此可见，相对于CPLEX，LRA和HSATS能够更有效地求解TECFLP-CF问题。表1LRA、H SA T S和CPLEX结果对比GLagGHGHCTLagTHTLagHTc算例I|J KAvgMaxAvgMaxAvgAvgAvgAvgAvg1510402.002.42 1.752.350.589.67.417.01980.8210 x20 x801.742.341.38 1.920.4023.617.140.712312.4315x301201.622.061.291.840.7043.828.171.96998.2420401601.371.721.001.400.4075.444.4119.85052.7525x502001.171.460.851.320.31143.852.2196.05 429.6630602400.991.170.620.840.16217.261.6278.87819.4735702800.881.010.640.880.23355.282.2437.48141.6840 x803200.810.980.570.71-0.24514.6 109.2623.86017.8945903600.780.870.520.62-0.31675.9229.4905.37000.910501004000.74 0.840.510.62-0.45982.1332.71314.85 651.6Average1.210.910.18表2 展示了LRA和HSATS求解不同工厂容量和不同规模算例的性能。其中,Redd=.0,ISPl=3,ISD;l=3。由表2 可知,LRA上界与下界之间的平均偏差为0.6 2%1.17%，93具有设施容量选择的两阶段设施选址问题研究3期最大偏差为1.6 0%，HSATS上界与LRA下界之间的平均偏差为0.37%0.8 6%，最大偏差为1.11%。显然，LRA和HSATS表现良好，对求解不同工厂容量的算例是有效的。此外，对于相同规模的算例,LRA上界和下界之间的平均偏差，以及HSATS上界和LRA下界之间的平均偏差都会随着Repd的增加而增加，而且LRA和HSATS的CPU时间也随着Repd增加而增加。由此可见，对于较小的Repd，LRA 和HSATS的求解效果更好。表2不同工厂容量的算例结果GLagGHTLagTHTLagH算例I|J KRcpdAvgMaxAvgMaxAvgAvgAvg135702801.50.881.110.620.80281.486.3367.7235702802.00.97 1.090.660.84325.287.7412.9335702802.51.001.130.680.83387.778.3466.0435702803.01.171.600.861.11503.582.0585.5550100 4001.50.620.750.370.48805.3155.8961.16501004002.00.720.870.510.68880.2148.61028.87501004002.50.821.120.540.791124.7148.91273.58501004003.00.951.120.640.761441.1146.51587.6Average0.890.61表3不同仓库容量的算例结果GLagGHTLagTHTLagH算例II J|KReddAvgMaxAvgMaxAvgAvgAvg135702801.50.891.100.600.83342.4122.2464.6235702802.00.94 1.030.680.76348.680.6429.2335702802.51.021.260.660.76323.273.1396.3435702803.00.981.180.670.79330.267.3397.55501004001.50.760.940.480.67975.0182.21157.2650 100 4002.00.831.010.540.59907.9125.11033.0750 100 4002.50.77 1.010.540.80947.497.31044.78501004003.00.810.910.550.70777.4105.2882.6Average0.880.59表3展示了LRA和HSATS求解不同仓库容量和不同规模算例的性能，其中Repd=2.0,ISPil=3，ISD l=3。由表3可知，LRA上界与下界之间的平均偏差为0.7 6%1.02%，最大偏差为1.2 6%，HSATS的上界与LRA下界之间的平均偏差为0.48%0.6 8%，最大偏差为0.8 3%。显然，LRA和HSATS表现良好，对求解不同仓库容量的算例是有效的。此外，Redd对解的质量和CPU时间没有重大影响。表4展示了LRA和HSATS求解不同工厂容量数量的算例的性能。其中，Repd=2.0,Redd=2.0,ISD;l=3。由表4可知,LRA上界和下界之间的平均偏差为0.7 4%0.93%,最大偏差为1.2 0%，HSATS的上界与LRA下界之间的平均偏差为0.49%0.6 9%，最大偏差为0.90%，LRA和HSATS表现良好。此外，仓库容量的数量对解的质量影响不大，但是随着仓库容量数量的增加，LRA和HSATS的CPU时间会有规律地增加，由此可见，对于LRA和HSATS来说，求解工厂容量个数较多的算例比求解工厂容量个数较少的算例更加困难。9427卷吴廷映，王瑶，周支立，任亚婷表4不同工厂容量数量的算例结果GLagGHTLagTHTLagH算例I|J K|ISP:lAvgMaxAvgMaxAvgAvgAvg1357028020.931.200.660.80273.882.2356.0235x7028030.891.030.580.71349.787.1436.83357028040.911.130.590.72382.875.8458.64357028050.881.110.60 0.83437.887.9525.75357028060.93 1.100.690.90498.277.0575.265010040020.780.840.550.65832.1150.8982.975010040030.750.850.490.55898.7173.41072.185010040040.78 0.880.490.531030.2164.71194.995010040050.740.850.520.621191.0186.01377.0105010040060.750.890.490.611296.4177.71 474.1Average0.830.57表5不同仓库容量数量的算例结果GLagGHTLagTHTLagH算例II|IJ|K|ISD;1AvgMaxAvgMaxAvgAvgAvg1357028020.891.050.580.83248.674.1322.72357028030.941.100.650.70345.593.6439.13357028040.881.030.590.87421.271.9493.14357028050.831.190.630.83509.177.2586.35357028060.861.040.610.79631.677.3708.965010040020.760.960.490.54712.6138.0850.6750100 x40030.730.910.500.57872.8123.7996.585010040040.720.790.490.541143.0152.21295.295010040050.800.930.570.671222.1115.71337.8105010040060.760.870.500.661509.0165.91674.9Average0.820.56表5展示了LRA和HSATS求解不同仓库容量数量的算例的性能。其中，Repd=2.0,Rcdd=2.0,ISPil=3。由表5可知，LRA上界和下界之间的平均偏差为0.7 2%0.94%，最大偏差为1.19%，HSATS的上界和LRA下界之间的平均偏差为0.49%0.6 5%，最大偏差为0.8 7%,LRA和HSATS表现良好。与表4类似，仓库容量的数量对解的质量没有重大影响，但是随着仓库容量数量的增加,LRA和HSATS的CPU时间会有规律地增加。由此可见，对于LRA和HSATS来说，求解仓库容量个数较多的算例比求解仓库容量个数较少的算例更困难。5结论与展望设施选址和及其容量选择是企业长期战略决策的重要内容，它关系到企业未来的生产运作成本。而在传统设施选址问题中常常忽略设施的容量选择，基于此，本文针对TECFLP-CF建立了混合整数规划模型，由于TECFLP-CF属于NP-hard问题，故设计了LRA和953期具有设施容量选择的两阶段设施选址问题研究HSATS进行求解并评价其有效性。数值实验表明，所提出的算法能在不同算例规模和参数下以合理的时间求得满意解，平均偏差低于1.7 5%，即使是对于多达50 个备选工厂且有6 个不同工厂容量，10 0 个备选仓库且有6 个不同仓库容量，和40 0 个客户的算例。将来的研究可尝试设计有效的元启发式方法，同时优化设施位置，从而扩大解的搜索空间并提高解的质量。另外，可以将LRA和HSATS与分支定界框架相结合来寻找TECFLP-CF的最优解。参考文献1 Cooper L.Location-allocation problems J.Operation Research,1963,11(3):331-343.2 Revelle C S,Eiselt H A,Daskin M S.A bibliography for some fundamental problem categories indiscrete location science J.European Journal of Operational Research,2008,184(3):817-848.3 Melo M T,Nickel S,Saldanha-da-Gama F.Facility location and supply chain management-Areview J.European Journal of Operational Research,2009,196(2):401-412.4 Klose A.An LP-based heuristic for two-stage capacitated facility location problems J.Journalof the Operational Research Society,1999,50(2):157-166.5 Klose A.A Lagrangean relax-and-cut approach for the two-stage capacitated facility locationproblem J.European Journal of Operational Research,2000,126(2):408-421.6 Fernandes D R M,Rocha C,Aloise D,et al.A simple and effective genetic algorithm for thetwo-stage capacitated facility location problem J.Computers&Industrial Engineering,2014,75:200-208.7金莉，朱云龙，申海三级物流网络选址-路径问题建模与求解算法研究J控制与决策，2 0 10,25(08):1195-1200,1206.8 Yang Z,Chen H,Chu F,et al.An effective hybrid approach to the two-stage capacitated facilitylocation problem J.European Journal of Operational Research,2019,275(2):467-480.9张震，李延晖，张琦考虑退货的多商品多来源闭环选址库存问题模型与算法J.工业工程与管理，2018,23(06):137-146.10 Harkness J,Revelle C.Facility location with increasing production costs J.European Journalof Operational Research,2003,145(1):1-13.11 Carrizosa E,Ushakov A,Vasilyev I.A computational study of a nonlinear minsum facilitylocation problem J.Computers&Operations Research,2012,39(11):2625-2633.12 Pisinger D.An expanding-core algorithm for the exact 0-1 knapsack problem J.EuropeanJournal of Operational Research,1995,87(1):175-187.13 Swarnkar R,Tiwari M K.Modeling machine loading problem of FMSs and its solution method-ology using a hybrid tabu search and simulated annealing-based heuristic approach Jj.Robotics&Computer Integrated Manufacturing,2004,20(3):199-209.14 Kucukoglu i,Ozturk N.An advanced hybrid meta-heuristic algorithm for the