论文研究-随机中断情境下的离散型设施选址问题研究.pdf

所需积分/C币:10 2019-09-08 03:25:58 637KB .PDF
4
收藏 收藏
举报

针对传统的供应链设施选址模型大多是基于静态背景下的确定性选址问题研究,而较少考虑中断风险因素的情况,基于随机中断情境,建立了混合整数规划模型表述的设施可靠性选址问题模型,采用拉格朗日松弛算法进行求解。通过构建的算例,求解了问题模型的最优解并验证了该算法的求解性能。
王继光,李景峰:随机中断情境下的离散型设施选址问题研究 2015,51(17) FRLP的定义和符号: 点只能配置部署可靠设施或不可靠设施当中的一个;约 N表示所有设施备选点的集合 束条件(5)表明所有的设施中至少有一个节点设施是可 h,表示节点的需求,i∈M; 靠设施(意即,不可能出现所有设施均为不可靠设施的 表示将一项不可靠设施配置到节点/的固定成情况)约束条件(6 )~(7)为完整性约東 本,该设施存在中断风险,j∈N 3.3求解方法 ∥表示将一项可靠设施配置到节点的固定成 很多优化问题随着问题规模的增大都会变成NP-hard 本,该项设施不存在中断风险,∈N; 题,几乎无法获得解析解,而只能通过一些近似算法 获得近似解。因此,寻找高精度的次优解同样有着重要 ;表示节点j的不可靠设施发生中断的概率(限于 的意义。相应地,催生了求解此类问题的各种近似算 篇幅,有关中断风险概率如何确定不在本文深入讨论范法。根据求解问题的类型梳理,近似算法通常包括拉格 围,模型中作为已知条件给出) 朗口松弛法、遗传算法、粒子群算法、模拟退火算法以及 d表示设施节点j为初始分配设施点时,从需求禁忌搜索法等。 节点i到设施节点j的单位运输成本,氵∈M,∈N; 以遗传算法( Genetic Algorithm)为例,该算法是通 d8表示某初始分配设施节点发生中断后,设施j过模拟生物进化过程中的遗传选择与淘汰而发展出的 作为备份的可靠设施点时,从需求节点倒设施节点/一种全局优化搜索算法。该算法概率化的寻优规则实 的单位运输成本,∈M∈N;考虑到供应链节点设施现了白动获取和指导优化搜索空间,从而适应调整搜 中断后启用备用设施所发生的应急成本以及可能的违索方向,而不需要确定的规则。该算法作为现代有关智 约成本因此假设dB≥d 域中用于解决最优化问题的一种较好的搜索启发式算法 决策变量: 然而随着时代发展,该算法已经不能很好地解决 X=1,表示一项不可靠设施被配置部署在节点 大规模计算量问题,其不是之处也逐渐显现。首先是 0表示未被部署在该节点 该算法的编程过程比较复杂,其次是由于遗传算法局部 X=1,表示一项可靠设施被配置鄙署在节点j;搜索能力较差,进化后期搜索效率较低,同时在适应度 0表示未被部署在该节点; 函数选择不当的情况下易产生“早熟收敛”( Premature y=1,表示节点i的需求被初始分配全节点/的 convergence)的问题,实际应用中有可能铰早收敛于局 设施(可靠或不可靠均可能);0表小未被分配在该节点 部最优,而尢法达到全局最优。由此,在同时满足使优 yB=1,表示节点/的需求在原分配点不可靠设施良个体得以保留并维持群体的多样性的前提下,采用何 屮断后被紧急分配至作为备份分配的可靠设施节点j, 种选择方法一直是遗传算法中较难解决的问题◇。 本文将釆用拉格朗日松池算法对该目标函数进行 0表示未被分配在该节点。 近似求解。在数学优化领域,拉格朗日松弛算法是一·种 基于以上变量描述,构建FRLP目标函数 在原问题函数无法荻得精确解析解的情况下,比如一个 min ∑fX+∑f8x 包含n个变量和k个约東条件的优化问题,通过松弛引 ∑∑0-g)h+∑∑914B(1)起计算难度的约束条件并添加到目标函数中将其转化 为一个有n+k个变量的变量不受任何约束且易于求解 ∑-1.∑Y=1.i∈M (2)的问题,并引入拉格朗口乘数,即约束方程梯度的线性 yB≤xF+x,YB≤xF,YiEM,∈N (3)组合里每个向量的系数,从而在保持原函数线性特征的 前提下实现对原问题进行近似优化求解 x}+X;≤1,vj∈N (4) 对于一种近似算法的评价,通常可以通过比较其所 ≥1 (5)计算的H标值(近似值)同最优H标值的差别。具体言 可以通过计算下界,用上界和下界的差来评价其计 X,X∈{0,1}.V∈N (6) 算效果。本文所采用的拉格朗H松弛算法就是求解下 ∈{0,1},i∈M,j∈N (7) 界的一种方法。该方法不仅较易实现而且有较好的性 约東条件(2)分别表示节点i需求或者被初始分配质。既可以评价算法的效果,同时可以提高算法的效 至某节点设施,或在初始分配的不可靠设施中断后被紧率。此外,使用该方法求解时,山于随着数据规模的增 急分配至某备份可靠设施;约東条件(3)表明节点需加,拉格朗日松弛法的计算量仅呈现近似线性增长,从 求的初始分配有可能分配至两类设施的任一种,而备份而克服了其他优化方法常常遇到的“维数灾”的缺陷,得 任务必须分配至可靠设施;约束条件(4)表明在某设施到比较好的次优解 015,51(17) Computer Engineering and Applications计算机工程与应用 首先,本文通过引入拉格朗日乘子和x以松弛约 步骤4根据上述变量赋值,可以计算v=∑mn0 束条件(2),从而获得新的目标函数: max min∑X+∑fX+ aB,an+2)。在得到和v之后,就可以计算位 置变量的H标值。在松弛约束条件(5),即暂不考虑该 (1-qd2-2)yP+ 条件的情况下,可得到: ∑∑(h42-1)+∑21+∑1(8) 如果F+广0=min(y+广,F+)<0,则有x=1 如果V+f<+,而且+12<0,则有x=1 式(3)-(7) 如果不符合上述条件,则有X=XR=0。 根据初始决策变量X和Y,试图最小化目标函数, 并利用引入的拉格朗日乘子4和z以最大限度地提高 步骤5在设定位置变量后,如果∑X≥1,则下界 的目标函数最小值,因此目标函数(1)可以改写如下: 间题可解。如果∑x=0.则需进一步修正位置变 max min ieN ∑∑B"+∑4-∑兀 (9 X 其中n=(1-9)4-4,B0=91h1B一x;。 1=min+/-y+/) 需要指出的是,即使约束条件(5)不满足,即不具备 任何可靠运行设施的情况下,通过放宽约束条件(2)都 j,=argmin( R+/R-(+, ) 会使该求解方法变得可行。 相应地,令: 34求解过程 miner GR,jo=arg min(v 拉格眀日松弛算法通过不断调整拉格朗日乘子λ 最终,可得: 和z直到使其上下界之间的问隔满足预先设定的一个 如果V1<则有X=1和x=0;如果V≥V,则 水平,或其他终止条作。此时,求解结果即为近似最优解。 有 34.1计算下界 对于拉格朗日乘了和x的固定值而言,改写后的 旦有了位置变量值,则只需利用上述关系表述提 H标函数(9)给原H标函数(1)提供了下界。基于此,求取位置变量。 解目标函数的步骤如下: 342计算上界 步骤!将所有决策变量x,X,y,Y的初始值 同样首先将决策变量A,XR的初始值设为0,其 设为0 取值和上文所述下界计算过程中有关X,X的取值计 步骤2确定每个节点上配置部署不可靠设施的算过程相同。令,所有需求节点的初始分配Y被分配 决策变量值(比如,x=1)。 至最近的设施(可靠设施或不可靠设施)完成,即 进而根据约束条件(3)中的y≤X+x,如果a=令,所有需求节点的备份分配y被分配至最近的可靠 (1-q42-<0.则设Y=1,这样做有利于使改写后设施完成,即YB=1。由此,可以计算原目标函数(1)的 日标函数(9)实现最小化。除固定设施成本外,假设上界。此时,位置变量x,X不一定是原目标函数的 X-1之后则有: 最佳选址结,但是其上界。 min(0,2) min(0,d-g:h, d-A) 3.4.3拉格朗凵乘子的梯度优化 步骤3以同样的方式确定每个节点j上配置部署 初始化:通过如下公式给拉格朗口乘子A和x进行 可靠设施的决策变量值(比如,x=1)。鉴于这样做会初始赋值 对约東条作(3)产生影响,因此本步骤要比步骤2复杂 图+x”一点+ 些。当X=1,则会通过设定Y,YB的值实现目标函 迭代:拉格朗日乘子在每次迭代时采用标准梯度优 数相应部分的最小化。具体而言 化法及搜宗方向修正法,即方向迭代。梯度优化法是更 如果a1=min(an,B1,an+月)<0,则有Y=1 新乘了λ和π的过程,公式(10)给出了第n+1次方向 如果B min( a Bn,an+B)<0,则有yB=1; 迭代时乘子和x的表达式 如果a+B=min(a月2a,+月2)<0,则有y=FB=1; 22=maxo. 1: +t 0).xO 如果不符合上述条件则有Y=F=0。 mnax10,+·(m) (10) 王继光,李景峰:随机中断情境下的离散型设施选址问题研究 2015,51(17) 其中,和分别代表乘子λ和π在第n次迭代, 表1计算结果 步长为m"时的迭代方向参数。步骤如下 设施状态 q=0.05 步骤1首先计算第n次迭代参数 覆盖需求点状 覆盖需求 1,2,3,4,5,6,7,13,1411,2,3,4,5,6,8,9 8,9,10,11,12,1 23,10,13,14,15,17 (1-SY)+e 16,17,18,19,20,21 16,18,19.20,21, j=4 其中,e是为了在迭代过程中防止出现死循环而引入的 22,23,24,2 22.23.24,28 25,26,27,29,30,31 25,26,27,29,30 阻尼系数。通常设e=0.3,:0=2:0=0()。 32,33,34 31,32 步骤2其次,计算第n次迭代步长t =6235,36,37,38,39,40 UB- LB) ∑ 0 其中,a是迭代n次时的一个常数,UB是到第n次迭 最小期望成木 83359375 99364250 为止找到的最小的上界值,设LB是迭代n次时找到 注:没施状态:“0”表示未选中;“1”表示选定为不可靠设 的下界值。a的初始值a一般设为2。设定如果连施点;“2”表示选定为可靠设施点 续迭代30次之后仍未能有效改善下界时,则对a进行 q=0.05时,设施点1、2、4、5、6被选中,其中设施点 二等分,即减为1。进而重新计算迭代步长,并修止乘 6为可靠设施点,其余为不可靠设施点。计算期望总成 子,进行步骤3。 本为83359375。进而在其他参数不变情况下,将风险 步骤3最后,继续用公式(10)更新乘子λ和z,进因子调高至q=0.2,设施点1、3、4、5、6、7被选中,其中 行第n+1次迭代,直到达到终止条件为止。 设施点3、7为可靠设施点,其余为不可靠设施点。计算 344迭代终止条件 的期望总成本为99364250,比q=0.05时的总成本提 当满足下列任一条件吋,该计算终止 高了192%。如图1所示 (1)最优上下界间隔:当上下界问隔趋近于0时,即 UB-LB <E,其中E为一给定的极小正数 LB (2)迭代最大次数:迭代次数达到预先设定的最 大次数nm时,即n>nx,通常在计算机辅助条件下将 迭代上限可以设置较大的数值,比如设置为n=1000。 (3)步长常数:当步长常数a趋近于0。 ■可靠设施 4模拟算例 口不可靠设施 需求点 假设某设施选址问题由40个需求点和8个备选设 图1(a)q=0.05时的最优选址图 施点组成,各需求点需求量以及各需求点与设施节点两 两距离分别作为原始数据给出。 在上文分析过程中,本文假设每一个备选址点的建 设成本和其中断概率均不相同,但在本馍拟算例中,为 突出相关叁数变化对最优选址结果的影响,因此本算例 中对每个具体的设施选址点的选址成和不可靠设施 的中断概率做∫一般化处理,即将可靠节点和不可靠节 点的固定建设成本分别设定为f=900000和 60000;所有不可靠设施的屮断概率均相同;运输成 ∫■可靠设施 口不可靠设施 本dp=0.50,d3=0.75。 需求点 (1)分别计算q=0.05和q=0.2时最优选址结果。 图1(b)q=0.2时的最优选址图 根据前文计算过程,借助 Matlab7.0软件编写的计 (2)其他参数不变的情况下,假设运输成本分别| 算程序计算q=0.05和q=0.2时的最优选址结果经过整倍,即d=1,dB=1.5时,分别计算q=005和q=0,2 理列示在表1中。 时的最优选址结果。如表2所示。 6 015,51(17) Computer Engineering and Applications计算机工程与应用 表2计算结果 表3计算结果 设施状态 4 覆盖需求点状态覆盖需求点 设施状态 覆盖需求点状态 覆盖需求点 1,2.3,4,5,6 9,10,13,14,15 1,2,3,4,5,6.7,8 1,2,3,4,5,6,7,8, 8,9,10,l1,12 219,10,11,12,13,15,19,10,11,12,13,15, j-3 0 16,18,19,20,21, 16,17,18,19,21 j=30 22,23,24,28 21,22,23,24,28 14,16,17,18,19,2 25,26,27,29,30, 25,26,27,29,30, 120,21,22,23,24 j=5 21,2223,24,28 31,32,33,3 31.32.33.34 28,29,30,31 11,12,35,36,37 25,26,27,29,30,31, 235,36,37,38,39,402 38,39,40 32,33,34,35,36,38 j-7 60 最小期望成本 ll79100 12194000 34,35.36,38,39 当运输成本分别上涨一倍之后,在q=0.05时,设施最小期望成本1104500 122926500 点1、2、3、4、5、6被选中,其中设施点1、4、6为可靠设 施点,其余为不可靠设施点。计算的期望总成本为 q=0.05时,设施点24、7被选中,其中设施点7为 1191009=02时,设施点24、5、6被选中,而且可靠设施点,设施点2、4为不可靠设施点。计算的期望 全部为可靠设施点。计算的期望总成本为121940000, 总成本为110094500:q=0.2时,设施点2、4、5被选 比q=0.05时的总成本提高了34%。如图2所示。 中,其中设施点5为可靠设施太,设施点24为不可靠设 施点。计算的期望总成本为122926500,比q=0.05时 的总成本提高了11.65%。如图3所示。 「可靠设施 %厂口不可苹设施 ↓可靠设施 图2(a)q=0.05时的最优选址图 口不可靠设施 需求点 图3(a)q=0.05时的最优选址图 ■可靠设施 口不叫靠设施 需求点 ■可靠设施 图2(b)q=0.2时的最优选址图 口不可靠设施 需求点 (3)原运输成本不变(d=0.5,dB=0.75)可靠节点 图3(b)q=0.2时的最优选址图 和不可靠节点的同定成本分别调整为f=180000 从模拟算例的运算情况来看,本模型有着良好的计 和∫=120000分别计算g=0.05和q=0.2时的最算性能。根据以上6种不同情况的最优选址结果分析: 优选址结果。如表3所示。 (1)从图1(a)和图1(b),图2(a)和图2(b),图3(a) 王继光,李景峰:随机中断情境下的离散型设施选址问题研究 2015,51(17) 和图3(b)三组结果中最优解的变化情况看,在其他参数定供应链各节点的中断概率是独立的,而事实上,供应 不变的情况下,模型计算结果对风险因子的变化非常敏链各节点的中断概率也可能是非独立的。由此,这将促 感。三组数据中因风险因了的变化而导致总成本的增使能够构建一个更具鲁棒性的供应链网络以抵御更坏 加比例分别为192%,34%和11.65%。同时,随着中断的风险情境 风险因子q值的变大,相应地有部分不可靠设施升级为 可靠设施以确保同时满足目标函数期望成本最小以及参考文献: 供应链的可靠性。 [1 Snyder L V Facility location under uncertainty: a reviewJ] (2)从图1(a)和图2(a),图1(b)和图2(b)两组结果 IIE Transactions. 2006.38(7):547-564 中最优解的变化情况看,在其他参数不变的情况下,模「2 I Chen PS, Wu m ta modified failure mode and effects 型计算结果对运输单价的变化非常敏感。运输单价提 analysis method for supplier selection problems in the 高之后,期望总成本有显著增加,分别为41.45%(g=0.05) supply chain risk environment: a case study[]. Computers 和2272%(q=0.2)。随着运输单价的提高,设施建设成 Industrial Engineering, 2013, 66(4): 634-642 本在总成本中的比重相对下降,在权衡目标函数期望成3 Santoso ta stochastic programming approach for supply 本最小以及供应链的可靠性前提下,可靠设施的数量显 chain network design under uncertainty[J]. European Jour nal of Operational Research, 2005, 167(1): 96-115 著増加,以诚轻中断情形下不可靠设施中断后所带来的 [4] Pishvaee M S, Rabbani M, Torabi s A. A robust optimi- 高额运费对供应整休运行的影响。 zation approach to closed-loop supply chain network design (3)从图1(a)和图3(a),图1(b)和图3(b)两组结果 under uncertainty[J] Applied Mathematical Modelling, 2011 中最优解的变化情况看,在其他参数不变的情况下,模 35(2):637-649 型计算结果对设施建设成本的变化同样非常敏感。设]徐家旺市场不确定环境下供应链运作的鲁棒优化模型研 施建设成本提高之后,总成本显著提高了32.07%(=0.05) 究[D]沈阳:东北大学,2007:1-11 和2371%(q=0.2)。同时,随着设施建设成本的大幅增[6晏妮娜,黄小原,马龙龙需求不确定环境下多个零售商竞 加,设施选址数量显著降低。此时,运输成本比重则变 争的鲁棒随机优化模型[中国管理科学,2008,16(4): 得相对较低,而设施中断造成的是运输成本在一定程度 50-54 上的增加。因此随着模型中设施建设成本增加,设施[]辛玉红供应链系统鲁棒性研究D北京:北京信息控制研 选址情况对中断风险因子q值变化的敏感度就会相应 究所,2008:1-12 降低。因此相对于图1(a)和图1(b)中数据,图3(a)和 8]桂云苗,龚本刚,程幼明不确定条件下供应链网络鲁棒优 图3(b)数据组中设施基建成本更大,故中断风险因子q 化与算法[统计与决策,2011(8):172-174 值的变化并没有引起设施数量和类型的明显改变,而仅 [9 Snyder I. V, Daskin M SReliability modcls for facility location: the expected failure cost case[J].Transportation 改变了设施选址位置。 Science,2005,39(3):400-416 [10] Cui T, Ouyang Y, Shen Z J M Reliable facility loca 5结束语 tion design under the risk of disruptions[J]. Operations 本文研究了设施随机屮断情境下的设施可靠性选 Research,2010,58:998-10ll 址问题(FRLP),通过构建混合簦数规划模型,并基于拉[1 erian,O, Krass,D, Menezes M B C Facility reliability 格朗日松弛算法求解∫该模型,求解∫不可靠设施和可 issues in network P-median problems: strategic central- 靠设施的最优选址结果。作为一种有效的求解工具,拉 ization and co-location effects[J].Operations Research 格朗囗松弛算法越来越多地运用在大型约束规划应用 2007,5(2):332-350 问题上。当原H标函数求解最优值非常凶难时,在保证「2 Hakimi S L. Optimum locations of switching centers 保持目标函数的线性的前提下,将引起原冋题求解难度 and the absolute centers and medians of a graph[U].Oper- 的约東条件松弛进而将其添加到目标函数中,将其转化 ations Research, 1964, 12(3): 450-459 为一个易于求解的近似问题,使得原问题的求解难度大 [13]You F, Wassick J M, Grossmann I E Risk management 大降低,有着很高的实用性。 for a global supply chain planning under uncertainty 研究发现:考虑了中断风险因素的情况下,在满足 modcls and algorithms[J].AIChE Journal, 2009, 55(4) 931-946 期望成本最小的前提下,设施选止的最优结果会随着没 [14] Guillen G Multi-objective supply chain design under 施建设成本、运输成本、风险参数因素的变化而变化: uncertainty[J]. Chemical Engineering Science, 2005, 60(6) 这将为供应链决策者的选址决策提供建设性的帮助 1535-1553 但本模型的不是之处在于模型假定某节点设施只[15]王艳敏基于可靠性的供应链设施选址问题的优化模型] 有两种状态,即正常和中断,没考虑局部中断,而局部中 科学技术与工程,2012,12(11):1-4 断这种情况也许更贴近现实ε此外,有待进一·步拓展的口16]王银年,葛洪伟求解TSP问题的收进模拟退火遗传算法[J 是模型中供应链中断概率的假定,在本文的模型中,假 计算机工程与应用,2010,46(5):44-47.

...展开详情
试读 7P 论文研究-随机中断情境下的离散型设施选址问题研究.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
weixin_38744153 欢迎大家使用并留下宝贵意见
2019-09-08
  • 至尊王者

    成功上传501个资源即可获取
关注 私信 TA的资源
上传资源赚积分or赚钱
    最新推荐
    论文研究-随机中断情境下的离散型设施选址问题研究.pdf 10积分/C币 立即下载
    1/7
    论文研究-随机中断情境下的离散型设施选址问题研究.pdf第1页
    论文研究-随机中断情境下的离散型设施选址问题研究.pdf第2页

    试读结束, 可继续读1页

    10积分/C币 立即下载 >