文章编号:1001-9081(2012)01-0153-05 doi:10.3724/SP.J.1087.2012.00153
摘 要:针对应急系统中的多点库存共享问题,研究了需求为随机模糊变量情形下的应急调货策略。考虑一个三级多品种的应急供应系统,当缺货发生时,各供应点之间可依据就近应急转运的原则共享部分库存,据此建立了有需求满足时间约束和各供应点库容空间限制的系统总费用随机模糊期望值模型,提出了一种粒子群优化算法和模拟退火算法相结合的先进计算方法(PSO-SA算法)对模型进行了求解,结合算例分析了转运点、就近转运时间、单位物品库容空间等因素变动对部分转运的影响,并验证了算法的有效性和模型的适用性。
关键词:部分转运;随机模糊;粒子群优化;退火算法;时间约束;库容空间限制;就近原则
中***分类号: TP18;F253.4 文献标志码:A
Abstract: To solve the multi-spot inventory sharing problem in an emergency system, emergency transportation strategy was studied in a system with random fuzzy demand in this paper through a multi-product and three-echelon emergency supply system. When the stockout happened, the nearest emergency lateral transshipment principle and partial inventory sharing strategy among the spots were permitted to satisfy the demand, and the model for the total cost expectation of random fuzzy demand was developed according to it, taking account of the service time constraints and the spots storage space limitation. An advanced computing method combining Particle Swarm Optimization (PSO) and Simulated Annealing (SA) algorithm, called PSO-SA algorithm, was proposed to calculate the model, and the effects on the partial transshipment with the variation of the transshipment trigger inventory level, the per-item transshipment time and the inventory storage space were analyzed through a numerical example. The availability of the proposed algorithm and the model applicability were verified at last.
Key words: partial transshipment; random fuzzy; Particle Swarm Optimization (PSO); Simulated Annealing (SA) algorithm; time constraint; storage space limitation; proximity principle
0 引言
应急转运问题是应急供应系统研究中的一个重点问题,通过应急转运进行库存共享,可以极大地提高应急供应系统的整体绩效水平。Allen[1]关于预防性转运和Krishnan等[2]关于反应性转运问题的研究奠定了转运问题研究的基石,Lee[3]对完全转运和Kchel等[4]对部分转运的研究开创了当代转运研究的热点,zdemir等[5]对转运能力有限制的研究,Yang等[6]对虚拟转运问题的研究,Hu等[7]对转运系统中总供给不确定的研究,Kutanoglu等[8]对就近转运和时限转运问题的研究,Olsson[9]对转运系统服务水平的多角度刻画的研究都充分体现了当代转运研究的趋势:转运问题的研究越来越细化,转运系统模型的设计和考量也越来越实用。例如,以上的研究[5-9]在应急系统服务水平中多考虑了时间约束,还有一些考虑了供给能力的限制,但却都没有将二者同时进行考虑。
此外,目前的研究大多考虑了随机性,且各种数据和信息都被假定为绝对精确,目标和约束也被严格地定义并有良好的数学表示,而应急系统的需求往往是不确定的。鉴于系统的复杂性,仅仅用随机变量来进行刻画是不够的,需考虑变量的模糊性。Sommer[10]最先将模糊集理论引入供应链管理问题。此后,Gen等[11]解决连续盘点的库存控制问题时考虑了模糊变量,Ouyang等[12]考虑了提前期内需求服从正态分布情形下损失销售率为模糊变量的问题,Gao等[13]考虑了多物品、多阶段的模糊库存问题。而在专门的应急转运的研究中,考虑模糊变量的却并不多,并且在实际的不确定因素中,往往同时包含了随机性和模糊性,但目前的应急转运研究中,同时考虑随机性和模糊性的文献则几乎没有。
本文考虑的是一个多产品的三级应急供应系统,需求是随机模糊的,对整个系统的服务水平给予了时间约束,并同时考虑了系统供给能力的库容空间限制。当某供应点发生缺货时,可依据就近应急运输的原则要求其他供应点对其进行转运,而其他供应点出于自身需求考虑,仅以库存物品的一部分提供转运,本文对这一转运策略中用于转运的物品比例进行了分析,据以建立了系统总费用的随机模糊期望值模型。最后设计了粒子群和模拟退火混合(Particle Swarm Optimization and Simulated Annealing, PSO-SA)算法[14]对模型进行了求解,结合算例分析了相关因素变动对部分转运策略的影响。
1 模型假设和描述
1.1 模型假设
考虑一个三级应急供应系统,总部向中央仓库供应能够组装成最终成品的模块,然后中央仓库再向下级各个供应点供应各类模块。模块在各个供应点根据所在地客户的需求组装成不同配置的成品,模块和成品的种类都是多种的。各个供应点之间采用部分转运策略,当某个供应点的某种模块缺货时,首先通过其他供应点向其提供部分应急转运来满足需求(即作为该供应点转运源的其他供应点出于自身需求考虑,对各种模块都设定一定的转运点,只有库存量超过该模块的转运点时,才对该供应点提供转运);当其他的供应点都无法向其应急转运该模块时,该供应点需要向中央仓库请求应急直送该模块;而中央仓库库存量也是有限的,当中央仓库也缺货时,该供应点被允许通过其他该模块库存不为零的供应点应急转运,即使作为应急转运源的其他供应点该模块库存量低于其设定的转运点;当中央仓库和所有的供应点的该模块库存量都为零时,需要从总部应急调运该模块到该供应点。各个供应点之间的距离不相同,所以当某供应点模块缺货的时候,首先考虑距离其最近的可转运供应点,本文中,将上述距离远近转化为运输时间长短来考虑。
1.2 符号说明
1)参数说明如下。
j(j=1,2,…, J)表示模块。
k(k=1,2,…,K)表示成品。
nkj表示成品k包含模块j的个数,nkj∈N。
i(i=1,2,…,I)表示供应点。
qr表示具有第r级转运优先级的供应点q,运输时间越短,优先级越高,
即供应点i在其余可提供转运的供应点中,按照与其运输时间的长短排列,最终选出的具有第r级优先级的供应点qr作为其应急转运源,即一旦供应点i发生缺货,其将最先被具有第r级优先级的转运源qr通过应急转运满足。
pji表示供应点i的模块j的转运点所占S ji的比例,0
Hji表示供应点i的模块j的转运点,Hji=「S ji•pji。
S j0表示中央仓库模块j的存储量。
j=∑Ii=1S ji+S j0。
Tiqr表示从供应点qr应急转运模块j到供应点i的单位时间, ajiqr为该时间的平均。
Tj0i表示从中央仓库应急直送模块j到供应点i的单位时间。
Fj0i表示从总部应急调运模块j到供应点i的单位时间。
Wmaxi表示供应点i的客户对所有成品的平均等待时间的上限。
zj表示从总部到中央仓库正常运输单位模块j的费用。
ζji表示从总部到中央仓库,再从中央仓库到供应点i的正常运输单位模块j的费用。
Tfiqr表示从供应点qr应急转运单位模块j到供应点i的费用,与Tiqr成正比,即Tfiqr=ρTiqr。
η ji表示从中央仓库应急直送单位模块j到供应点i的费用。
ε ji表示从总部应急调运单位模块j到供应点i的费用。
hj表示单位模块j的存储费。
δk表示单位成品k的组装费。
v j表示单位模块j所占的存储空间。
Vmaxi表示供应点i的库容空间上限。
2)主要变量如下。
ki表示供应点i的客户对成品k的需求率,为随机模糊变量。
ji表示供应点i的客户对模块j的需求率,
ji=∑Kk=1kinkj。
μj表示供应点模块j的到达率,服从正态分布。
ji表示供应点i的模块j依靠自身库存满足需求的比例。
1ji表示供应点i模块j的库存量高于转运点的比例,1ji
ji表示供应点i的模块j依靠应急转运满足需求的比例。
ji表示供应点i的模块j依靠从中央仓库应急直送满足需求的比例。
ji表示供应点i的模块j依靠从总部应急调运满足需求的比例。
ji(m)表示供应点i的模块j的库存量为m的概率。
ji表示供应点i因作为其他供应点的应急转运源而增加的对模块j的需求率。
jiqr表示将供应点q作为供应点i应急转运模块j的第r级优先转运来源地的概率。
Sji表示供应点i的模块j的存储量,为决策变量。
2 模型建立和变量计算
2.1 1ji、ji、 ji、ji、ji和ji等变量的计算过程
当供应点i的模块j库存量小于等于转运点Hji单位时,供应点i不会向其他供应点应急转运模块j,而仅用于满足自身需求;当供应点i的模块j库存量大于等于Hji+1单位时,供应点i也可以为其他需要应急转运的供应点应急转运模块j。
设j为所有供应点对模块j的总需求率,即j=∑Ii=1ji,fji为供应点i对模块
j的需求所占所有供应点总需求的比例,fjij为供应点i对模块j实际需求。则fjij可以用以下两种方式计算:
fjij=jiji+1jiji+(1-ji)0最后是乘以“0”吗?请明确。回复:贵刊PDF中的注释1-注释3:确实都是0,以上3个0没有数值运算的意义,是为了建模上的逻辑缜密性;
以及
fjij=jiji+∑Iq=1,q≠i(jqi jqjq)
由此可以得出:
ji=11ji∑Iq=1,q≠i(jqi jq jq)
(1)
同时jiqr=jiqr∏r-1r′=1(1-jiqr′),供应点i采取的是一一订货策略,需求是连续需求方式,转运策略为部分转运,所以可以得出供应点i的模块j库存量变化情况如***2。
根据***2,设ji=ji+ji,根据有限两
状态马尔可夫过程,可以得到(推导过程略):
ji(m)=ji(Hji+1)•(S ji-Hji-1)!(μj)m-Hji-1(S ji-m)!(ji)m-Hji-1;
Hji+1≤m≤S ji
(2)
ji(m)=ji(Hji+1)•1∏H jiκ=m(S ji-κ)jiμjHji+1-m;
0≤m≤Hji
(3)
所以,有式(4):
ji(Hji+1)原文中有“+1”,现在补充上了,请核实。=
∑S jim=H ji+1(S ji-H ji-1)!(μj)m-H ji-1
(S ji-m)!( ji)m-H ji-1+
∑H jim=01∏H jiκ=m(S ji-κ)jiμjH ji+1-m-1
(4)
供应点i可以依靠自身库存满足需求的比例为:
ji=1-ji(0)
(5)
而供应点i模块j的库存量高于转运点的比例应为:
1ji=∑S jiH ji+1ji(m)
(6)
当所有的供应点和中央仓库的模块j库存量均为0时,才需要从总部应急调运以满足需求,所以此时j1=j2=…=jI=j,且
j=∑ jm=0 j!( j-m)!μjjm-1
(7)求和公式中的,m的初值为多少?请补充。
当供应点i的模块j的库存量为0,且其他的供应点对模块j的库存量低转运点时,该供应点的模块j才会从中央仓库应急直送。所以:
ji=∏Iqr=1,qr≠i(1-1jqr)ji(0)-j
(8)
根据公式ji+ji+ji+ji=1,得出:
ji=1-ji-ji-ji
(9)
根据式(1)~(9)迭代计算,可以得出ji、 ji、ji、ji、ji的数值。
2.2 需求等待时间的限制
在应急系统中,需求常常被限定在一定的时间内满足。本文中在成品的组装时间忽略不计的情况下,用以组装成成品的各类模块的等待时间就是成品需求的等待时间,这一时间由各供应点模块依靠自身库存满足需求的时间、依靠其他供应点应急转运满足需求的时间、依靠中央仓库应急直送满足需求的时间和依靠总部应急调运满足需求的时间组成,计算如下:
供应点i的模块j依靠自身库存满足需求的时间为ji0乘以0,是否正确,请明确?;
依靠其他供应点应急转运满足需求的平均时间为 ajiqr=∑I-1r=1jiqrTiqr;
依靠中央仓库应急直送满足需求的时间为jiTj0i;
依靠总部应急调运满足需求的时间为jiFj0i;
因此,供应点i所有成品的平均等待时间期望为:
Wi=E∑Kk=1kiimaxnkj≥0(ji0也是乘以数字“0”是否为下标,或者书写错误,请明确。+∑Iqr=1jiqr ajiqr+jiTj0i+jiF j0i)
(10)
2.3 库容空间的限制
每种模块都有一定的体积,而各供应点的库容空间有限,所以,需要考虑各供应点的库容空间对其供应能力的限制。下面计算供应点i的模块j的库容空间,
供应点i的模块占据的库容空间为:
Vi=∑Jj=1S jiv j
(11)
2.4 相关费用计算
三级应急供应系统中的费用包括供应点的模块存储费用、供应点的成品组装费用、供应点之间的模块应急转运费用、从中央仓库到供应点的模块应急直送费用、从总部到供应点的模块应急调运费用、从总部到中央仓库的模块正常供应运输费用、从总部到供应点的模块正常供应运输费用,计算如下。
供应点的模块的存储费用期望:
TCH=E(∑Jj=1∑Ii=1∑S jim=1mji(m)hj)
(12)
供应点的成品组装费用期望:
TCU=E(∑Kk=1∑Ii=1τkiδk)
(13)
供应点之间的模块应急转运费用期望:
TCZ=E(∑Jj=1∑Ii=1∑Iqr=1, qr≠i ji jijiqr ρTiqr)
(14)
从中央仓库到供应点的模块应急直送费用期望:
TCW=E(∑Jj=1∑Ii=1jijiη ji)
(15)
从总部到供应点的模块应急调运费用期望:
TCG=E(∑Jj=1∑Ii=1jijε ji)
(16)
从总部到中央仓库的模块正常供应运输费用期望:
TCM=∑Jj=1S j0zj
(17)
从总部到供应点的模块正常供应运输费用期望:
TCY=E(∑Jj=1∑Ii=1jijiζji)
(18)
因此三级应急物流系统部分转运策略总费用期望模型:
minTC=TCH+TCU+TCZ+TCW+TCG+TCM+TCY
s.t. Wi≤Wmaxi
Vi≤Vmaxi(19)
3 算法分析与求解
由于ji、 ji、ji、ji和ji是迭代计算的,所以很难通过解析解来求出最优解。所以本文准备用智能算法来求解,随机模糊变量使用数值模拟的方法。
3.1 相关算法
3.1.1 粒子群算法
粒子群算法同遗传算法类似,但是它没有遗传算法用的交叉(crossover)以及变异(mutation),而是粒子在解空间里面追随最优的粒子进行搜索。目前已广泛应用于函数优化、神经网络训练、模糊系统控制以及其他遗传算法的应用领域。
PSO初始化为一群随机粒子(随机解),然后通过迭代找到最优解。在每一次迭代中,粒子通过跟踪两个“极值”来更新自己:一个就是粒子本身所找到的最优解,这个解叫做个体极值pBest;另一个极值是整个种群目前找到的最优解,这个极值是全局极值gBest。
在找到这两个最优值时,粒子根据式(20)~(21)来更新自己的速度和新的位置:
Υ这个字符可以用别的字符来替换,如希腊字符“γ”或“υ”、“Υ”等?请明确。回复:可以用别的字符来代替。=w•Υ+c1•rand()•(pBest-Present)+c2•rand()•(gBest-Present)
(20)
Present=Present+Υ
(21)
其中:Υ是粒子的速度,Present是粒子的当前位置。rand()是(0,1)的随机数,c1和c2被称做学习因子。w是加权系数(惯性权重),取值在0.1~0.9。粒子通过不断学习更新,最终飞至解空间中最优解所在的位置,搜索过程结束。最后输出的gBest就是全局最优解。在更新过程中,粒子每一维的最大速率被限制为Υmax,如果某一维更新后的速度超过设定的Υmax,那么这一维的速度就被限定为Υmax。
3.1.2 模拟退火算法
模拟退火(Simulated Annealing, SA)算法也称为模拟冷却法、统计冷却法、Monte-Carlo退火法、随机松弛法和概率爬山法等。SA算法往好的方向走的同时,偶尔也往差的方向走,这使得算法可能陷入局部最优值,但只要经过足够长的时间后也可跳出来,收敛到全局最优解。1982年,Kirkpatrick等将退火思想引入组合优化的领域,提出了一种用于求解大规模组合模拟问题的退火算法:在某一初温下,伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解,在局部优解处能概率性地跳出并最终趋于全局最优。
模拟退火算法的标准流程如下。
步骤1
初始化,任选初始解,d∈S,给定初始温度T0(选择T0时,要足够高,使Ed/Tx0),终止温度Tf,令迭代指标x=0,Tx=T0。
步骤2
随机产生一个邻域解,e∈N(d),N(d)表示d的邻域,计算目标值增量Δf=f(e)-f(d)。
步骤3
若Δfξ,则令d=e(e比d好,有条件转移)。
步骤4
若达到热平衡(内循环次数大于n(Tx))转步骤5;否则转步骤2。
步骤5
x=x+1,降低Tx,若Tx
3.1.3 PSO-SA算法
PSO-SA算法的基本实现思想是,在标准PSO算法每次迭代搜索到当前全局最优点pBest时,利用SA算法的概率突跳特性,产生新解,提高算法跳出局部最优的能力。每执行完一次标准PSO算法之后,再使用SA算法,搜索更优解。
PSO-SA算法流程如***3所示。
3.2 算例模拟
3.2.1 算例求解
设:J=3;I=4;K=3;
ki~N(1.8-0.1•i,0.01•i),i为三角随机模糊变量,其中:
i=(ai,1.5ai,2ai);
a=(a1,a2,a3,a4)=(0.6,0.7,0.8,0.7);
μj=N(1-0.1•j,0.01•j);η ji=50•ζji;
ε ji=2•η ji;δ=(δ1,δ2,δ3)=(2,3,1);
h=(h1,h2,h3)=(30,40,35);
z=(z1,z2,z3)=(2,3,2);
ρ=2,T0i=(T10i,T20i,T30i)且
T01=T02=T03=T04=(4,5,6);
F0i=(F10i,F20i,F30i);
F01=F02=F03=F04=(6,7,8);
Wmax=(Wmax1,Wmax2,Wmax3,Wmax4)=(1.2,1.1,1,1.2);
V=(Vmax1,Vmax2,Vmax3,Vmax4)=(30,35,29,40);
v=(v1,v2,v3)=(1,1.5,2);
S0=(S10,S20,S30)=(2,2,2);
pi=(p1i,p2i,p3i);
p1=p2=p3=p4=(0.2,0.3,0.3);
n=231312223;
ζ=91088979108786;
T=0132102332012310
随机模糊变量用Liu等[15]的模拟方法进行模拟,使用PSO-SA算法进行计算,设算法中的学习因子c1=c2=2,惯性权重w=0.8,初始化群体个体数目N=5;产生的新粒子解加权系数为0.8,可接受概率达0.99;退火操作中温度预设值η=0.001,退火速率λ=0.9。迭代计算100次,得出结果如***4。
从***4中可以看出PSO-SA的收敛速度比较快,说明PSO-SA是对于本模型计算是很适合的。
以下分析供应点之间相互应急转运单位模块的费用的变化对相关费用期望的影响,首先通过改变ρ,对Tfiqr进行改变。
当ρ=3时,
S ji=3154153103512333;
当ρ=2时,S ji=373812131233339
;
当ρ=1时,S ji=3917333333151011。
从表1可以看出,随着ρ的减小,TC也减少,TCH、TCY、TCZ和TCW也逐步减小,TCU和TCM保持不变。从S ji中,可以看出导致表1成本变动的原因。
3.2.2 关键参数变动分析
以下改变模型中的一些关键的参数,看一下它们对总费用期望和其他费用期望的影响。关键参数包括Pi、V这两个是矢量、向量吗?还是一般的变量?请明确。和Tiqr。
从***5~7中可以看出,供应点模块的转运点所占库存量的比例、供应点之间相互应急转运模块时间和单位模块所占的空间、供应点之间单位模块的应急转运费用减小,都会引起总费用期望的减小。
3.2.3 模型适用性分析
本文的模型具备较强的适用性,根据pji的不同,作简单变换,可以变为多种库存共享策略,本文所讨论部分转运策略是在0
当采用完全转运策略时,不存在1ji,上述模型中只需令pji=0时,Hji=0,即只要供应点i自身持有库存不为0,其就可以对其他需要的供应点进行转运。由此带来ji、ji(m)、ji(0)、j等一系列参数发生相应的变化。本文中,采取上述变换,在模拟数据和分析方法不变的情况下,即可对比分析三级应急供应系统部分转运策略和完全转运策略总费用期望的差别,故本文的模型在转运策略的研究中具备较强的适用性,可以根据不同的实际需要用于各种库存共享策略的对比和选择。
4 结语
本文研究了不确定环境下三级应急供应系统的部分转运策略,考虑供应点面临的需求是随机模糊的,且物品的种类是多种的,与此同时考虑了需求满足时间的限制和各供应点库容空间的限制。最后采用了随机模糊模拟技术计算随机模糊变量的期望值,利用POS-SA算法求解相应模型,验证了该模型和算法在解决该类问题时具有很强的适用性和有效性。但是,本文的研究还存在很多的不足:比如只考虑了供应点对成品的需求为随机模糊变量的情况,未考虑运输费用和存储费用都为随机模糊变量的情况;只考虑了供应点的存储费用,未考虑中央仓库的存储费用;只考虑了三级应急供应系统,未考虑多级应急供应系统等,这些都将成为本文后续研究中需要拓展的方向。
参考文献:
[1]
AllEN S G. Redistribution of total stock over several user locations [J]. Naval Research Logistics Quarterly, 1958, 5(4): 337-345.
[2]
KRISHNAN K, RAO V. Inventory control in N warehouses [J]. Journal of Industrial Engineering, 1965, 16(3): 212-215.
[3]
LEE H L. A multi-echelon inventory model for repairable items with emergency lateral transshipments [J]. Management Science, 1987, 33(10): 1302-1316.
[4]
KCHEL P. On queuing models for some multi-location problems [J]. International Journal of Production Economics, 1996, 45(1/2/3): 429-433.
[5]
ZDEMIR D, YCESAN E, HERER Y T. Multi-location trans-shipment problem with capacitated transportation [J]. European Journal of Operational Research, 2006, 175(1): 602-621.
[6]
YANG J, QIN Z. Capacitated production control with virtual lateral transshipments [J]. Operations Research, 2007, 55(6): 1041-1119.
[7]
HU X, DUENYAS I, KAPUSCINSKI R. Optimal joint inventory and transshipment control under uncertain capacity [J]. Operations Research, 2008, 56(4): 881-897.
[8]
KUTANOGLU E, MAHAJAN M. An inventory sharing and allocation method for a multi-location service parts logistics network with time-based service level [J]. European Journal of Operational Research, 2009, 194(3): 728-742.
[9]
OLSSON F. An inventory model with unidirectional lateral transshipments [J]. European Journal of Operational Research, 2010, 200(3):725-732.
[10]
SOMMER G. Fuzzy inventory scheduling [M]. New York: Pergamon Press, 1981, VI: 3052-3060.
[11]
GEN M, TSUJIMURA Y, ZHENG D. An application of fuzzy set theory to inventory control models [J]. Computers and Industrial Engineering, 1997, 33(3): 553-556.
[12]
OUYANG L-Y, CHANG H-C. The variable lead time stochastic inventory model with a fuzzy backorder rate [J]. Journal of the Operations Research Society of Japan, 2001, 44(1): 19-33.
[13]
GAO JINWU, FENG XUEQIN. A hybrid intelligent algorithm for fuzzy dynamic inventory system[J]. Journal of Information and Computing Sciences, 2006,1(4): 235-244.
[14]
焦巍,刘光斌,张艳红.求解约束优化的模拟退火PSO算法[J].系统工程与电子技术,2010,32(7):1533-1536.
[15]
LIU Y-K, LIU BAODING. Expected value operator of random fuzzy variable and random fuzzy expected value models [J]. International Journal of Uncertainty, Fuzziness and Knowledge-based Systems, 2003, 11(2): 195-215.
[16]
刘学恒,汪传旭,许长延.二级物资供应系统中不同应急调货策略的比较分析[J].工业工程,2011,14(2):11-15.
收稿日期:2011-05-30;修回日期:2011-07-08。
基金项目:国家自然科学基金资助项目 (70973074);
上海海事大学博士创新能力培养专项资金资助项目 (yc2010020)。
作者简介:
刘学恒(1980-),男,江苏淮安人,讲师,博士研究生,CCF会员(E200020043G),主要研究方向:物流与供应链管理、计算机仿真优化;
许长延(1985-),男,山东聊城人,硕士研究生,主要研究方向:物流与供应链管理、计算机仿真优化;
汪传旭(1967-),男,安徽安庆人,教授,博士生导师,博士,主要研究方向:物流与供应链管理、港口与航运管理。
转载请注明出处学文网 » 不确定环境下三级应急系统部分转运策略