物流业是支撑国民经济发展的基础性、战略性产业。物流的本质是服务,物流活动不仅强调节约成本,更加重视服务质量。物流配送网络是物流活动的基础设施,其运行效率的高低直接影响物流的服务质量。此外,作为生产者和消费者之间的桥梁,物流配送网络也是经济活动的重要支撑系统,它的失效有可能导致商品供应的中断甚至崩溃,进而直接影响人们的日常生活。因此,物流配送网络可靠性也越来越为管理者所重视。
从建模的角度,物流配送网络常常用有向边和节点来表示,其中每个节点代表货源地、配送中心或市场,每条边代表两点之间的运输线。受随机性因素的影响(如运输工具、天气、道路等),每条边上的配送能力是一个随机变量。因此,物流配送网络常常被建模为一个多状态流网络模型(multi-state flow network,MFN)
[1 4 ] 。在多状态流网络模型中,网络的每条边都具有多种不同的容量状态,且容量状态通过容量概率分布来描述。给定需求水平
d ,网络可靠性是指网络能够将
d 单位的商品流从源点(货源地)成功输送到汇点(市场)的概率,该可靠性指标用来评估网络的输送能力。
在物流活动中,运输费用也是衡量物流配送网络服务质量的重要方面,因此,有研究者提出了费用约束的可靠性指标。费用约束的可靠性是指,配送网络能够将
d 单位的商品流从货源地成功输送到市场,且总的运输费用不超过给定的费用约束
B 的概率。费用约束的网络可靠性可以利用费用约束的极小容量向量来计算。该方法的基本思路是,首先求解费用约束的极小容量向量,然后利用不交和算法计算费用约束的网络可靠性,其中,如何求解费用满足费用约束的极小容量向量是研究的重点。Lin
[5 ] 最早利用极小路构建了满足费用约束的极小容量向量搜索模型,其中,极小路是由网络中的边组成的集合,集合中的边构成一条从源点到汇点的通路,但去掉集合内的任何一条边,剩下的都不能构成一条从源点到汇点的通路,该模型会产生重复的满足费用约束的极小容量向量,即多个完全一样的容量向量。为此,Lin等
[6 ] 提出利用比较法识别重复的满足费用约束的极小容量向量,但随着网络规模的增加,比较法的识别效率较低。后来,Forghani-elahabad等
[7 ] 提出了一种更高效的去重方法。为了提升可靠性计算效率,Niu等
[8 ] 利用边的容量下界构建了一个新的满足费用约束的极小容量向量搜索模型。最近,Niu等
[9 ] 提出利用最小费用循环流方法求解满足费用约束的极小容量向量。徐秀珍等
[10 ] 将运输成本和运输损耗同时纳入物流配送网络可靠性分析。张国晨等
[11 ] 在明确原料物流成本和收储点位置的前提下,构建生物质原料物流网络模型,得到最优的原料调度方案。注意到以上研究都只考虑了配送中心的中转功能,没有考虑配送中心的仓储功能。在商品配送过程中,为了更好地满足客户需求,销售商大多将一定数量的商品存储至配送中心,以此提升配送能力和配送时效
[12 ] 。相对于货源地,配送中心距离市场较近,其库存会对网络的配送能力产生影响,进而影响网络可靠性。因此,有必要将配送中心库存纳入物流配送网络可靠性分析,从而更加全面评估物流配送网络的服务能力和运行状态。
在物流配送网络中,由于配送中心与市场的距离较货源地更近,管理者常常采用配送中心库存优先供应市场的策略;当配送中心无法满足市场需求,再考虑从货源地向市场供应商品。此外,还要考虑按商品流实际占有体积来计算运输成本。基于以上考虑,在考虑配送中心库存优先供应市场以及运输费用约束的基础上,将物流配送网络可靠性定义为,网络从配送中心或货源地输送到特定市场的商品能够满足需求,且总的运输费用不超过给定的费用上限的概率。根据配送中心库存、市场需求之间的关系,提出基于极小容量向量的可靠性评估方法。通过算例分析对可靠性评估方法进行了验证,并分析了不同的库存组合对网络可靠性的影响。
1 网络模型
用G (N , A )表示一个多源点单汇点物流配送网络,N = {v 1 , v 2 ,…, vo , t 1 ,t 2 , …, tm , T }是所有节点的集合,其中ve (e = 1, 2, …, o )表示货源地,tg (g =1, 2, …, m )表示配送中心,T 为一个确定的市场;A = {a 1 , a 2 , …, an }是所有边的集合。如前所述,将物流配送网络建模为一个多状态流网络模型,因此,每条边ai 有πi 种容量状态(配送能力),即0 = bi1 < bi2 < …<biπi (i = 1, 2, …, n ),其中bir 为ai 的第r 个配送容量(r = 1, 2, …, πi )。X = (x 1 , x 2 , …, xn )是由各边的容量状态组成的容量向量,其中xi 为边ai 当前所处的容量状态,且取值属于集合{bi1 , bi2 , …, biπi }。用M = (b1π1 , b2π2 , …, bnπn )表示网络中的最大容量向量,其中bnπn 表示边an 的最大容量。
在网络可靠性分析中,极小路是常用的工具,极小路是指网络中从源点到汇点的一条不包含有向圈的路径,其中,源点可以是货源地,也可以是配送中心,汇点代表市场。例如,在
图1 所示的网络中,从货源地
v 1 到市场
T 的极小路有两条:{
a 1 ,
a 5 }和{
a 2 ,
a 6 };从配送中心
t 1 到市场
T 的极小路为{
a 5 }。假设从所有货源地和配送中心到市场的极小路总数量为
μ ,用
${P}_{k}^{i\left(T\right)}$ 表示从货源地或配送中心
i 到市场
T 的一条极小路,且该条极小路在所有极小路中的序号为
k (
k = 1, 2,…,
μ ),用
${f}_{k}^{i\left(T\right)}$ 表示经过极小路
${P}_{k}^{i\left(T\right)}$ 的流(即商品流)。仍以
图1 中的网络为例,从所有货源地和配送中心到市场的极小路总数量为6,分别为:
${P}_{1}^{{v}_{1}\left(T\right)}$ ={
a 1 ,
a 5 },
${P}_{2}^{{v}_{1}\left(T\right)}$ ={
a 2 ,
a 6 },
${P}_{3}^{{v}_{2}\left(T\right)}$ ={
a 3 ,
a 5 },
${P}_{4}^{{v}_{2}\left(T\right)}$ ={
a 4 ,
a 6 },
${P}_{5}^{{t}_{1}\left(T\right)}$ ={
a 5 },
${P}_{6}^{{t}_{2}\left(T\right)}$ ={
a 6 }。
本文网络模型满足如下的假设条件:①网络G (N , A )中的商品流满足流守恒定律;②商品流为非负整数值;③不同边的容量状态在统计上相互独立;④配送中心的库存优先供应市场;⑤商品在运输途中没有损耗。
2 商品流分配与费用约束
2.1 商品流分配
假设网络中共设有m 个配送中心,第g 个配送中心分配的库存量为zg (g = 1, 2, …, m ),库存总量为S ,即$\sum _{g=1}^{m}$ zg = S 。由于假定配送中心的库存优先供应给市场,因此,需要分析库存与市场需求之间的关系,并以此确定市场需求的商品是由配送中心单独供应,还是由配送中心和货源地共同供应。
(1)库存总量S 大于等于市场需求d 。如果库存总量S 大于等于市场需求d ,且从m 个配送中心到市场的极小路能够承载d 单位的商品需求量,则根据优先供应规则,此时不需要货源地向市场供应商品。因此,配送中心向市场供应的商品流满足如下条件:
(1) ${\sum }_{k}^{}$ {${f}_{k}^{{t}_{g}\left(T\right)}$ │${P}_{k}^{{t}_{g}\left(T\right)}$ ∈E (tg , T )} ≤zg ,g =1,2,…,m
(2) ${\sum }_{g}^{}{\sum }_{k}^{}$ {${f}_{k}^{{t}_{g}\left(T\right)}$ │${P}_{k}^{{t}_{g}\left(T\right)}$ ∈E (tg , T )} =d
式中:E (tg , T )表示从第g 个配送中心tg 到市场T 的所有极小路的集合;${\sum }_{k}^{}$ ${f}_{k}^{{t}_{g}\left(T\right)}$ ${P}_{k}^{{t}_{g}\left(T\right)}$ E (tg , T )}表示从第g 个配送中心tg 供应到市场T 的总商品流;${\sum }_{g}^{}{\sum }_{k}^{}$ ${f}_{k}^{{t}_{g}\left(T\right)}$ ${P}_{k}^{{t}_{g}\left(T\right)}$ E (tg , T )}表示从所有配送中心供应到市场T 的总商品流。式(1)表示从第g 个配送中心tg 供应到市场T 的商品数量不能超过该配送中心的库存量;式(2)表示所有配送中心供应到市场T 的总商品数量等于市场需求d ,此时,货源地不需要为市场T 供应商品。
(2) 库存总量S 小于市场需求d 。如果库存总量S 小于市场需求d ,则说明配送中心库存不能够满足市场需求,此时,需要货源地向市场供应商品,此时,网络中的商品流满足如下约束条件:
(3) ${\sum }_{k}^{}$ {${f}_{k}^{{t}_{g}\left(T\right)}$ │${P}_{k}^{{t}_{g}\left(T\right)}$ ∈E (tg , T )}=zg ,g =1,2,…,m
(4) ${\sum }_{e}^{}{\sum }_{k}^{}$ {${f}_{k}^{{v}_{e}\left(T\right)}$ │${P}_{k}^{{v}_{e}\left(T\right)}$ ∈E (ve , T )} =d - S
式中:${\sum }_{e}^{}{\sum }_{k}^{}$ ${f}_{k}^{{v}_{e}\left(T\right)}$ ${P}_{k}^{{v}_{e}\left(T\right)}$ E (ve , T )}表示从所有货源地供应到市场T 的总商品。式(3)表示从第g 个配送中心tg 供应到市场T 的商品数量等于该配送中心的库存量,由于库存总量S =$\sum _{g=1}^{m}$ zg ,即配送中心供应到市场T 的商品数量等于库存总量S ;式(4)表示货源地向市场供应的商品数量等于市场需求d 减去配送中心库存总量S 。
2.2 可行流向量
如前所述,假设网络中共有μ 条从货源地ve 或配送中心tg 到市场T 的极小路,流向量F = (f 1 , f 2 , …, fμ )是由每条极小路上的商品流所组成的向量。给定一个流向量F ,当且仅当F 满足如下条件,称F 在M 下是可行流向量。即
(5) 「ω [${\sum }_{e}^{}{\sum }_{k}^{}$ {${f}_{k}^{{v}_{e}\left(T\right)}$ │ai ∈${P}_{k}^{{v}_{e}\left(T\right)}$ }+${\sum }_{g}^{}{\sum }_{k}^{}$ {${f}_{k}^{{t}_{g}\left(T\right)}$ │ai ∈${P}_{k}^{{t}_{g}\left(T\right)}$ }]⌉≤biπi ,i =1, 2,…,n
式(5)中:ω 为单位商品流实际占用的容量。式(5)表示经过边ai 的商品流不能超过该边的最大容量。当只有配送中心向市场供应商品时,货源地至市场的极小路上没有商品流,此时,第一项${\sum }_{e}^{}{\sum }_{k}^{}$ ${f}_{k}^{{v}_{e}\left(T\right)}$ ai ∈${P}_{k}^{{v}_{e}\left(T\right)}$ ${\sum }_{e}^{}{\sum }_{k}^{}$ ${f}_{k}^{{v}_{e}\left(T\right)}$ ai ∈${P}_{k}^{{v}_{e}\left(T\right)}$
给定容量向量X = (x 1 , x 2 , …, xn ),类似地,称流向量F 在X 下是可行流向量,如果F 满足如下条件:
(6) 「ω [${\sum }_{e}^{}{\sum }_{k}^{}$ {${f}_{k}^{{v}_{e}\left(T\right)}$ │ai ∈${P}_{k}^{{v}_{e}\left(T\right)}$ }+${\sum }_{g}^{}{\sum }_{e}^{}$ {${f}_{k}^{{t}_{g}\left(T\right)}$ │ai ∈${P}_{k}^{{t}_{g}\left(T\right)}$ }]⌉≤xi ,i =1, 2,…,n
式(6)表示通过边ai 的商品流所占有的容量不能超过边ai 当前的容量状态。为了方便起见,令UX = {F 在X 下是可行流向量}。
2.3 费用约束条件
在可靠性评估中,主要考虑运输费用,且总的运输费用等于各条边上的运输费用之和,而每条边的运输费用等于经过该边的商品流占有容量乘以单位容量运输费用。如果其满足如下两个条件,称流向量F 满足市场需求d 和费用约束B 。即
(7) ${\sum }_{e}^{}{\sum }_{k}^{}$ {${f}_{k}^{{v}_{e}\left(T\right)}$ │${P}_{k}^{{v}_{e}\left(T\right)}$ ∈E (ve , T )}+${\sum }_{g}^{}{\sum }_{k}^{}$ {${f}_{k}^{{t}_{g}\left(T\right)}$ │${P}_{k}^{{t}_{g}\left(T\right)}$ ∈E (tg , T )}≥d
(8) $\sum _{i=1}^{n}$ ci 「ω [${\sum }_{e}^{}{\sum }_{k}^{}$ {${f}_{k}^{{v}_{e}\left(T\right)}$ │ai ∈${P}_{k}^{{v}_{e}\left(T\right)}$ }+${\sum }_{g}^{}{\sum }_{k}^{}$ {${f}_{k}^{{t}_{g}\left(T\right)}$ │ai ∈${P}_{k}^{{t}_{g}\left(T\right)}$ }]⌉≤B
式中:ci 为边ai 的单位容量运输费用,i =1, 2,…,n 。式(7)表示从配送中心和货源地向市场供应的商品总数量要大于等于市场需求d ;式(8)表示总的运输费用不能超过费用约束B 。因此,当存在满足市场需求d 和费用约束B 的流向量F ∈UX 时,称容量向量X 满足条件(d , B )。
3 可靠性计算
3.1 网络可靠性Rd , B
在已知各配送中心库存分配量条件下,给定市场需求d 以及费用约束B ,可靠性Rd , B T 的商品量大于等于d ,且总的运输费用不超过B 的概率。如前所述,给定容量向量X ,当存在满足市场需求d 和费用约束B 的流向量F ∈UX 时,称X 满足条件(d , B )。因此,定义Φ 为满足条件(d , B )的所有容量向量的集合,即Φ = {X │X 满足条件(d , B )},则显然有Rd , B ${\sum }_{X\in \Phi }^{}$ P r (X )。
对所有的容量向量逐一进行枚举是计算Rd , B Rd , B
(1)Y ≤ X :(y 1 , y 2 , …, yn ) ≤ (x 1 , x 2 , …, xn ),对任意i 都有yi ≤ xi 。
(2)Y < X :(y 1 , y 2 , …, yn ) < (x 1 , x 2 , …, xn ),对任意i 都有yi ≤ xi ,且至少存在一个j 使得yj < xj 。
定义 如果对于Y < X 的任意容量向量Y ,都有Y ∉Φ ,则称Φ 中的容量向量X 是极小容量向量[简称(d , B )-MCP]。
假设有
σ 个(
d ,
B )-MCP:
X 1 ,
X 2 , …,
Xσ ,令A
1 ={
X |
X ≥
X 1 },
A 2 ={
X |
X ≥
X 2 }, …,
Aσ ={
X |
X ≥
Xσ },则根据(
d ,
B )-MCP的定义,
Rd , B 可由不交和方法
[10 ] 计算,即
(9) Rd , B P r (A 1 ∪A 2 ∪…∪Aσ )= P r {[A 1 ∪(A 2 -A 1 )]∪…∪Aσ ∪(Aσ -${\cup }_{j=1}^{\sigma -1} $ Aj )]}$\sum _{i=1}^{\sigma }$ Pr(Bi )
式(9)中:B 1 = A 1 , $B_{i}=A_{i}-\cup_{j=1}^{i-1} A_{j}$, i =1, 2, …, σ ;P r (Bi ) =${\sum }_{x\in {B}_{i}}^{}$ P r (X ), P r (X )= $\sum _{q=1}^{n}$ xq )。
3.2 (d , B )-MCP的理论模型
下面给出寻找(d , B )-MCP的理论基础。
定理1 如果容量向量X = (x 1 , x 2 , …, xn )是(d , B )-MCP,则至少存在一个满足市场需求d 和费用约束B 的流向量F ,使得xi = bir ≥ 「ω [${\sum }_{e}^{}$ $\underset{k}{\times }$ ${f}_{k}^{{v}_{e}\left(T\right)}$ ai ∈${P}_{k}^{{v}_{e}\left(T\right)}$ ${\sum }_{g}^{}{\sum }_{k}^{}$ ${f}_{k}^{{t}_{g}\left(T\right)}$ ai ∈${P}_{k}^{{t}_{g}\left(T\right)}$ ir-1 , r = 1, 2, …, πi , ∀i 。
证明: 如果X = (x 1 , x 2 , …, xn )是(d , B )-MCP,则意味着存在满足市场需求d 和费用约束B 的流向量F ∈UX 。假设存在某条边aσ 满足xσ > bσr ≥ 「ω [${\sum }_{e}^{}{\sum }_{k}^{}$ ${f}_{k}^{{v}_{e}\left(T\right)}$ ai ∈${P}_{k}^{{v}_{e}\left(T\right)}$ ${\sum }_{g}^{}{\sum }_{k}^{}$ ${f}_{k}^{{t}_{g}\left(T\right)}$ ai ∈${P}_{k}^{{t}_{g}\left(T\right)}$ σr-1 , xi = bir ≥ 「ω [${\sum }_{e}^{}{\sum }_{k}^{}$ ${f}_{k}^{{v}_{e}\left(T\right)}$ ai ∈${P}_{k}^{{v}_{e}\left(T\right)}$ ${\sum }_{g}^{}{\sum }_{k}^{}$ ${f}_{k}^{{t}_{g}\left(T\right)}$ ai ∈${P}_{k}^{{t}_{g}\left(T\right)}$ ir-1 (i ≠ σ )。令Y = (y 1 , y 2 , …, yn ),其中yσ = bσr ≥ 「ω [${\sum }_{e}^{}{\sum }_{k}^{}$ ${f}_{k}^{{v}_{e}\left(T\right)}$ ai ∈${P}_{k}^{{v}_{e}\left(T\right)}$ ${\sum }_{g}^{}{\sum }_{k}^{}$ ${f}_{k}^{{t}_{g}\left(T\right)}$ ai ∈${P}_{k}^{{t}_{g}\left(T\right)}$ σr-1 , yi = xi (i ≠ σ ),可得Y < X ,且F ∈UY ,这与X 是(d , B )-MCP矛盾,因此,xi = bir ≥ 「ω [${\sum }_{e}^{}{\sum }_{k}^{}$ ${f}_{k}^{{v}_{e}\left(T\right)}$ ai ∈${P}_{k}^{{v}_{e}\left(T\right)}$ ${\sum }_{g}^{}{\sum }_{k}^{}$ ${f}_{k}^{{t}_{g}\left(T\right)}$ ai ∈${P}_{k}^{{t}_{g}\left(T\right)}$ ir-1 ,∀i 。
根据定理1 由满足市场需求d 和费用约束B 的流向量F 转换而来的容量向量X 称作候选(d , B )-MCP。定义Ω 为候选(d , B )-MCP的集合,Ω min 为集合Ω 中的极小元素组成的集合。定理2将要证明Ω min 是(d , B )-MCP集合。
定理2 Ω min 是所有(d , B )-MCP的集合。
证明 假设X 是一个(d , B )-MCP,但X ∉ Ω min ,从定理1可知X ∈ Ω 。因为X ∉ Ω min ,在集合Ω 中存在Y ∈ Ω 满足Y < X 。因为Y ∈ Ω ,Y ∈Φ 成立,这与X 是(d , B )-MCP相矛盾。假设容量向量X 不是(d , B )-MCP,但X ∈ Ω min ,可得X ∈Ω 。X 不是(d , B )-MCP,则存在(d , B )-MCP Y 满足Y < X ,Y ∈ Ω ,这与X ∈ Ω min 相矛盾。因此Ω min 是所有(d , B )-MCP的集合。
3.3 算法
算法:给定库存的网络可靠性算法。
假设第g 个配送中心的库存分配量为zg (g = 1, 2, …, m )、市场需求为d ,费用约束为B ,则网络可靠性的计算步骤如下。
步骤1 根据下面的步骤求解所有满足市场需求d 的流向量F = (f 1 , f 2 , …, fμ )。
(1)如果$\sum _{g=1}^{m}$ zg < d ,找出所有满足下列约束的非负整数解F = (f 1 , f 2 , …, fμ )。
(10) ${\sum }_{k}^{}$ {${f}_{k}^{{t}_{g}\left(T\right)}$ │${P}_{k}^{{t}_{g}\left(T\right)}$ ∈E (tg , T )}=zg ,g =1,2,…,m
(11) ${\sum }_{e}^{}{\sum }_{k}^{}$ {${f}_{k}^{{v}_{e}\left(T\right)}$ │${P}_{k}^{{v}_{e}\left(T\right)}$ ∈E (ve , T )}=d -$\sum _{g=1}^{m}$ zg
(2)如果$\sum _{g=1}^{m}$ zg ≥ d ,且m 个配送中心到市场的极小路能够承载d 单位的商品需求,则找出所有满足下列约束的非负整数解F = (f 1 , f 2 , …, fμ )。
(12) ${\sum }_{k}^{}$ {${f}_{k}^{{t}_{g}\left(T\right)}$ │${P}_{k}^{{t}_{g}\left(T\right)}$ ∈E (tg , T )} ≤zg ,g =1,2,…,m
(13) ${\sum }_{e}^{}{\sum }_{k}^{}$ {${f}_{k}^{{v}_{e}\left(T\right)}$ │${P}_{k}^{{v}_{e}\left(T\right)}$ ∈E (ve , T )}=d
步骤2 对于步骤1得到的所有流向量F = (f 1 , f 2 , …, fμ ),验证其是否满足最大容量约束和费用约束:
(14) 「ω [${\sum }_{e}^{}{\sum }_{k}^{}$ {${f}_{k}^{{v}_{e}\left(T\right)}$ │ai ∈${P}_{k}^{{v}_{e}\left(T\right)}$ }+${\sum }_{e}^{}{\sum }_{k}^{}$ {${f}_{k}^{{t}_{g}\left(T\right)}$ │ai ∈${P}_{k}^{{t}_{g}\left(T\right)}$ }]⌉≤biπi ,i =1,2,…,n
(15) $\sum _{i=1}^{n}$ ci 「ω [${\sum }_{e}^{}{\sum }_{k}^{}$ {${f}_{k}^{{v}_{e}\left(T\right)}$ │ai ∈${P}_{k}^{{v}_{e}\left(T\right)}$ }+${\sum }_{g}^{}{\sum }_{k}^{}$ {${f}_{k}^{{t}_{g}\left(T\right)}$ │ai ∈${P}_{k}^{{t}_{g}\left(T\right)}$ }]⌉≤B
步骤3 将步骤2得到的流向量F = (f 1 , f 2 , …, fμ )转换成容量向量X = (x 1 , x 2 , …, xn ),转换关系式为
(16) xi = bir ≥「ω [${\sum }_{e}^{}{\sum }_{k}^{}$ {${f}_{k}^{{v}_{e}\left(T\right)}$ │ai ∈${P}_{k}^{{v}_{e}\left(T\right)}$ }+${\sum }_{g}^{}{\sum }_{k}^{}$ {${f}_{k}^{{t}_{g}\left(T\right)}$ │ai ∈${P}_{k}^{{t}_{g}\left(T\right)}$ }]⌉≤bir-1 ,i =1,2,…,n
步骤4 用Ω ={X 1 , X 2 , …, Xu }表示步骤3得到的所有容量向量的集合,利用比较方法从Ω 中得到(d , B )-MCP。
步骤5 利用步骤4得到的(d , B )-MCP和式(9)计算可靠性Rd , B
4 算例分析
通过算例阐明网络可靠性算法的计算过程。
图2 所示的网络共有3个货源地、2个配送中心、1个市场和8条边。网络中每条边上的单位容量运输费用、配送容量和容量概率分布如
表1 所示。
图2 表明,从货源地v
1 到市场T的极小路有
${P}_{1}^{{v}_{1}\left(T\right)}$ = {
a 1 ,
a 7 }和
${P}_{2}^{{v}_{1}\left(T\right)}$ = {a
2 , a
8 };从货源地v
2 到市场T的极小路有
${P}_{3}^{{v}_{2}\left(T\right)}$ = {a
3 , a
7 }和
${P}_{4}^{{v}_{2}\left(T\right)}$ = {a
4 , a
8 };从货源地v
3 到市场T的极小路有
${P}_{5}^{{v}_{3}\left(T\right)}$ = {a
5 , a
7 }和
${P}_{6}^{{v}_{3}\left(T\right)}$ = {a
6 , a
8 };从配送中心t
1 到市场T的极小路有
${P}_{7}^{{t}_{1}\left(T\right)}$ = {a
7 };从配送中心t
2 到市场T的极小路有
${P}_{8}^{{t}_{2}\left(T\right)}$ = {a
8 },从货源地、配送中心到市场T的极小路共有8条。设每单位商品流实际占用容量ω = 0
. 6,市场需求d = 7,费用约束B = 16,配送中心t
1 的库存量
z 1 = 2,配送中心
t 2 的库存量
z 2 = 3。下列步骤将演示如何通过枚举法计算网络可靠性
R 7,15 。
步骤1 因为S = 5 < d = 7, 利用下面的关系式找到所有满足市场需求d 的流向量F = (f 1 , f 2 , …, f 8 ):
(19) ${f}_{7}^{{t}_{1}\left(T\right)}$ = z 1 =2
(20) ${f}_{8}^{{t}_{2}\left(T\right)}$ = z 2 = 3
(21) ${f}_{1}^{{v}_{1}\left(T\right)}$ +${f}_{2}^{{v}_{1}\left(T\right)}$ +${f}_{3}^{{v}_{2}\left(T\right)}$ +${f}_{4}^{{v}_{2}\left(T\right)}$ +${f}_{5}^{{v}_{3}\left(T\right)}$ +${f}_{6}^{{v}_{3}\left(T\right)}$ =2
用枚举法可得21个满足市场需求
d 的流向量,结果见
表2 的第1列。
步骤2 利用下面的关系式验证步骤1产生的21个流向量F 是否满足最大容量向量M 和费用约束B :
(22) 「0.6${f}_{1}^{{v}_{1}\left(T\right)}$ ⌉≤ 4
(23) 「0.6${f}_{2}^{{v}_{1}\left(T\right)}$ ⌉≤ 3
(24) 「0.6${f}_{3}^{{v}_{2}\left(T\right)}$ ⌉≤ 4
(25) 「0.6${f}_{4}^{{v}_{2}\left(T\right)}$ ⌉≤ 3
(26) 「0.6${f}_{5}^{{v}_{3}\left(T\right)}$ ⌉≤ 4
(27) 「0.6${f}_{6}^{{v}_{3}\left(T\right)}$ ⌉≤ 2
(28) 「0.6(${f}_{1}^{{v}_{1}\left(T\right)}$ +${f}_{3}^{{v}_{2}\left(T\right)}$ +${f}_{5}^{{v}_{3}\left(T\right)}$ +${f}_{7}^{{t}_{1}\left(T\right)}$ )⌉≤ 4
(29) 「0.6(${f}_{2}^{{v}_{1}\left(T\right)}$ +${f}_{4}^{{v}_{2}\left(T\right)}$ +${f}_{6}^{{v}_{3}\left(T\right)}$ +${f}_{8}^{{t}_{2}\left(T\right)}$ )⌉≤ 3
(30) 2「0.6${f}_{1}^{{v}_{1}\left(T\right)}$ ⌉+3「0. 6${f}_{2}^{{v}_{1}\left(T\right)}$ ⌉+. 6${f}_{3}^{{v}_{2}\left(T\right)}$ ⌉+2「0. 6${f}_{4}^{{v}_{2}\left(T\right)}$ ⌉+. 6${f}_{5}^{{v}_{3}\left(T\right)}$ ⌉+1「0. 6${f}_{6}^{{v}_{3}\left(T\right)}$ ⌉+. 6${f}_{1}^{{v}_{1}\left(T\right)}$ +${f}_{3}^{{v}_{2}\left(T\right)}$ +${f}_{5}^{{v}_{3}\left(T\right)}$ +${f}_{7}^{{t}_{1}\left(T\right)}$ )⌉+. 6${f}_{2}^{{v}_{1}\left(T\right)}$ +${f}_{4}^{{v}_{2}\left(T\right)}$ +${f}_{6}^{{v}_{3}\left(T\right)}$ +${f}_{8}^{{t}_{2}\left(T\right)}$ )⌉≤ 16
本步骤得到10个满足最大容量向量
M 和费用约束
B 的流向量
F ,结果见
表2 的第2列。
步骤3 将步骤2得到的10个可行流F = (f 1 , f 2 , …, f 8 )转换成容量向量X = (x 1 , x 2 , …, x 8 ),转换公式为
(31) x1 = b1r , b1r ≥ 「0.6${f}_{1}^{{v}_{1}\left(T\right)}$ ⌉> b1r-1
(32) x2 = b2r , b2r ≥ 「0.6${f}_{2}^{{v}_{1}\left(T\right)}$ ⌉> b2r-1
(33) x8 = b8r , b8r ≥ 「0.6(${f}_{2}^{{v}_{1}\left(T\right)}$ +${f}_{4}^{{v}_{2}\left(T\right)}$ +${f}_{6}^{{v}_{3}\left(T\right)}$ +${f}_{8}^{{t}_{2}\left(T\right)}$ )⌉ > b8r-1
本步骤得到10个容量向量
X ,
Ω ={
X 1 ,
X 2 , …,
Xu },结果见
表2 的第3列。
步骤4 利用比较法依次判断Ω 中的容量向量X 是否是(7,16)-MCP,即
I =∅,
i = 1,
j = 2
X 1 = (0, 0, 0, 0, 0, 2, 2, 3)不小于X2 (0, 0, 0, 0, 1, 1, 2, 3)
X2 = (0, 0, 0, 0, 1, 1, 2, 3)不小于或等于X 1 = (0, 0, 0, 0, 0, 2, 2, 3)
j = 3
︙
X 1 = (0, 0, 0, 0, 0, 2, 2, 3)是一个(7,16)-MCP。I = 1,
i = 2,
︙
本步骤得到10个(7,16)-MCPs,结果见
表2 的第4列。
步骤5 根据步骤3得到的10个(7,16)-MCPs,利用式(9)计算网络可靠性,得到R 7,16 = 0.835 9。
假设库存总量
S = 5,可得到6种库存组合:Z
1 ={0, 5},
Z 2 ={1, 4},
Z 3 ={2, 3},
Z 4 ={3, 2},
Z 5 ={4, 1},
Z 6 ={5, 0}。每种库存组合可靠性结果如
表3 所示,可发现当库存组合为
Z 4 ={3, 2}时,可靠性
R 7,16 = 0.889 1,在6种库存组合中可靠性最大。如
表3 所示,当库存组合为{0, 5}和{5, 0}时,对应的可靠性为0.000,因此将库存全部分配至一个配送中心时,并不能改善网络可靠性。当配送中心
t 1 分配到的库存量增加时,网络可靠性随之增加,直至配送中心
t 1 的库存量
z 1 =3时,网络可靠性达到最大。而当继续为配送中心
t 1 增加库存量时,网络可靠性下降,由此可见,增加配送中心库存并不总是能够改善网络可靠性水平。
5 结论
物流配送网络是推动经济发展的重要基础设施,其可靠性问题越来越被人们所关注。配送中心是连接物流配送网络中供应商和市场之间的中间节点,对于网络中的商品存储和流通具有重要作用,而物流配送网络能否提供可靠的运输服务,配送中心库存是一个关键因素。因此,将物流配送网络建模为多状态流网络,在考虑配送中心库存优先供应市场以及运输费用约束的基础上,提出基于极小容量向量的物流配送网络可靠性计算方法。根据货源地、配送中心和市场之间的关系分配商品流,并在此基础上,找到所有满足运输费用约束和市场需求的极小容量向量,采用不交和算法计算网络可靠性。最后,通过数值实验对所提出的可靠性评估方法的有效性进行了验证,并分析了不同库存组合对网络可靠性的影响,结果表明增加配送中心库存并不总是能够改善网络可靠性水平。
PDF
(1652KB)
