考虑多级设施中断的供应链选址—库存决策模型及优化算法

狄卫民，王 然

(郑州大学 管理工程学院，河南 郑州 450001)

0 引言

供应链设施选址具有战略重要性，选址结果是否合理直接影响供应链运营绩效。以往设计供应链网络时，通常认为设施建成后总能按照既定计划正常运行，忽略了设施中断对供应链运作的影响。在此情形下，一旦因自然灾害、疫情防控、设备故障或生产组织不力等导致部分设施停工停产，即出现设施中断，将难以完成与这些设施相关联的下游客户的产品供应任务；若将这些任务临时指派给其他设施，则可能因其他设施距离较远而导致系统费用大幅度增加。可见，为了提高供应链运营绩效，亟需研究考虑设施中断的选址决策方法。

针对随机中断、确定性需求下无能力限制的供应链设施选址问题，Snyder等[1]引入虚拟设施临时服务部分客户，建立了混合整数非线性规划模型，设计了求解模型的拉格朗日松弛算法;Li等[2]建立了该问题的两阶段随机规划模型，并提出了求解模型的样本均值近似算法;Zhang等[3]研究了随机中断、确定性需求下有能力限制的设施选址—路径问题，并基于设施中断情景建立了混合整数规划模型，设计了一种融入最大似然抽样法、路径—任务调整、两阶段邻域搜索和模拟退火思想的元启发式算法;马卫民等[4]考虑到决策者在设施中断和需求波动方面的风险偏好，建立了不确定需求下有能力限制的供应链网络设计模型，给出了嵌入最短增广链法的混合智能遗传算法;于冬梅等[5]应用不确定集合描述不确定需求，建立了不确定需求下有能力限制的可靠性设施选址鲁棒优化模型，设计了求解模型的蝙蝠算法。这些研究有利于降低设施中断风险，提高供应链运营绩效，但因研究的侧重点不同，建模时均未考虑库存费用对选址决策的影响。

李志等[6]研究了存在中断风险和能力限制的分销网络选址—库存优化问题，建立了0-1整数非线性规划模型，给出了求解模型的遗传算法，研究表明，在网络设计阶段考虑中断风险能够大幅度降低网络运营时的应急成本；马祖军等[7]同时考虑风险防御策略进一步研究了该问题，亦得出同样结论;原丕业等[8]同时考虑中断风险和转运策略，研究了不确定需求下无能力限制的分销网络选址—库存优化问题，并分别利用遗传算法、模拟退火算法和粒子群算法求解模型，发现遗传算法具有更好的运算效率和计算精度。不过，文献[6-8]均未在设施中断后重新制定下游关联成员的产品分配方案，不利于下游产业安全和供应链弹性的提升。Rayat等[9]同时考虑中断风险和路径再分配策略，研究了不确定需求下有能力限制的供应链选址—库存—路径优化问题，建立了混合整数非线性双目标规划模型，并利用改进的归档式多目标模拟退火算法求解模型，取得良好效果。

以上研究有利于合理设计供应链网络，但文献[1-9]仅考虑了单一层级的设施中断问题，文献[6-9]仅适用于含有单一初端供应源的设施中断问题。实际上，一条供应链通常由多个层级构成，而在每个层级上通常又存在多个可能发生中断的设施，且多级中断风险不可能是单级中断风险的简单叠加，因此还需要加强含有多级设施中断的供应链选址—库存优化研究。

目前，考虑多级设施中断的供应链网络优化设计文献较少。Rohaninejad等[10]针对一种单个下游企业可由多个上游企业同时供货(部分量分配)的三级网状供应链系统，研究了确定性需求下有能力限制且各层设施均可能发生中断的供应链选址问题，建立了混合整数非线性规划模型，设计了基于样本均值近似算法和加速Benders分解算法的模型求解方法，该研究中设施中断概率由设施投资水平决定，若最终客户的需求不能得到满足，则根据缺货量施以相应金额的惩罚。该文献虽然考虑到多级设施中断问题，但尚未涉及需求的不确定性和供应链的库存费用。在实际应用中，除上述网状系统外，单个下游企业一次仅允许一个上游企业供货(全量分配)的树状供应链系统也是一种常见系统[11]。在含有多个初端工厂的树状系统中，设施中断后，为保障下游成员的产品供应，有可能在更大范围内进行服务指派方案的临时调整，这符合现实运作要求，也使选址—库存优化问题更具一般性，当然也相应增加了方案调整的维度和难度。鉴于此，为拓展该领域的研究内容，弥补已有研究的不足，本文在分析产品获取成本的基础上，同时考虑设施中断后指派任务的临时调整和设施容量的确定问题，探讨了不确定需求下有能力限制且存在多级中断风险的树状供应链选址—库存优化决策方法，建立了以系统期望总成本最小化为目标的混合整数非线性规划模型，设计了在遗传算法框架下嵌入特定成本分析法的混合遗传算法。

1 问题描述

考虑一种由多个工厂、多个配送中心和若干零售商构成的三级树状供应链系统。在该系统中，零售商不设库存，配送中心设有库存并采用(r,Q)库存控制策略补货，工厂在正常情况下供应能力充足。为便于管理，规定每个零售商在每天营业前仅由一个配送中心为其运送当日待售产品，每个配送中心需要补货时仅由一个工厂为其补货。当工厂/配送中心中断时，其下游的关联配送中心/零售商将面临缺货风险，为应对这种风险，允许其他未中断的工厂/配送中心为这些配送中心/零售商提供临时服务。这样，由于可能出现设施中断，在一段时期内，对于一个给定的配送中心/零售商而言，未必始终由同一个工厂/配送中心为其补货/送货。

为避免由其他工厂/配送中心为下游配送中心/零售商提供临时服务时可能导致的系统费用的大幅度增加，分析时需要比较配送中心/零售商通过本系统获取产品的成本(即生产成本加物流过程成本)和就地购买同种产品的成本(即购买价格加必要的搬运成本，此处的购买价格多为当地批发价格)。如果通过本系统获取产品的成本不大于就地购买成本，则通过本系统获取产品；否则，可通过就地购买方式获取产品。为便于分析，假设存在一个永不中断的虚拟工厂/虚拟配送中心，且该虚拟工厂/虚拟配送中心为所有需要就地购买产品的配送中心/零售商提供服务。这样，通过增加虚拟设施，便将外部购买方式添加到了先前的三级供应链系统中(如图1)。此时可以认为，在一段时期内，零售商的全部需求完全由实际配送中心和虚拟配送中心共同完成，实际配送中心的全部补货完全由实际工厂和虚拟工厂共同完成。

假设已经明确了每个工厂、零售商和候选配送中心的具体位置，且各零售商的每日产品需求量完全独立并服从正态分布，则在工厂和配送中心均可能发生中断的情况下，为使供应链系统的期望总费用最低，如何确定配送中心的建设位置、建设数量、仓储容量以及各工厂/配送中心对于各配送中心/零售商的补货/送货指派等级是待解决的问题。

2 模型建立

2.1 建模假设

为便于研究，作如下假设：

(1)研究单一产品在一个较长规划期的配送中心选址决策及仓储容量配置问题。

(2)类似于文献[1]，假设各工厂和各配送中心的中断事件完全独立，同类设施的中断概率基本相同，而且设施在中断期间完全不可用。

(3)供应链成员间具有较高的信息共享度，未中断的设施可以即时提供临时服务。

(4)配送区域范围合适，配送中心接到送货指令后，可以当晚装车并于零售商次日营业前将所需产品送达零售商处。

(5)配送中心的订货提前期主要取决于从工厂到该中心的产品运输时间。

(6)各工厂技术水平相当，产品生产成本基本相同。

2.2 符号说明

为便于建模，定义如下符号：

m、n、g分别表示零售商、候选配送中心和实际工厂的数量。

I={1,2,…,m}、J={1,2,…,n,n+1}、K={1,2,…,g,g+1}分别表示零售商、配送中心和工厂的编号集合，其中：(n+1)即|J|为虚拟配送中心编号，(g+1)即|K|为虚拟工厂编号。

i、j、k分别表示零售商、配送中心和工厂的编号，有i∈I，j∈J，k∈K。

b表示某配送中心对于某零售商的服务指派等级，若b=0，说明正常情况下应由该中心为该零售商送货，即该中心为该零售商的首级服务设施；若b=1，说明当该零售商的首级配送中心中断而该中心正常时，应指派该中心为该零售商送货，即该中心为该零售商的第1级备用服务设施；若b=2，说明当该零售商的首级和第1级备用配送中心同时中断而该中心正常时，应指派该中心为该零售商送货，即该中心为该零售商的第2级备用服务设施；依次类推，若b=n0，说明当该零售商的首级和第1～(n0-1)级备用配送中心同时中断而该中心正常时，应指派该中心为该零售商送货，即该中心为该零售商的第n0级备用服务设施。由于虚拟配送中心永不中断，对于每个零售商而言，虚拟配送中心为该零售商送货的服务指派等级即为集合J相对于该零售商的最大服务指派等级；若记此时的等级值为b0，显然b0≤n。

s表示某工厂对于某实际配送中心的服务指派等级，类似于b的赋值，有s=0,1,…,s0，其中s0是虚拟工厂为该中心补货时的服务指派等级值，s0≤g。

μi、σi和μj、σj分别为零售商i和配送中心j的产品日需求量的均值与标准差。fj为配送中心j的日均固定建设成本，Bj为配送中心j一次订货的固定成本，hj为配送中心j的单位产品日均持有成本，ej为配送中心j的单位容量日均建设成本，rj为配送中心j的再订货点，Qj为配送中心j的订货量，Lj和σLj分别为配送中心j的订货提前期的均值和标准差，Tj为配送中心j两次订货的间隔天数，zαj为配送中心j在服务水平αj下应对需求量变化的安全系数。

Aj1、Aj2、Aj3分别为配送中心j的周转库存、安全库存和最大库存水平。

cij为配送中心j到零售商i的单位运输成本，其中虚拟中心到零售商i的单位运输成本ci|J|用产品在零售商i附近的就地购买成本与供应链系统中产品生产成本的差值代替；cjk为工厂k到配送中心j的单位运输成本，其中虚拟工厂到配送中心j的单位运输成本cj|K|用产品在配送中心j附近的就地购买成本与供应链系统中产品生产成本的差值代替。

djk为工厂k到配送中心j的距离；vjk为工厂k到配送中心j的车辆行驶速度。

q为配送中心中断概率，p为工厂中断概率。

xj表示是否建设配送中心j，是取1，否取0。

yijb表示配送中心j是否以等级b为零售商i送货，是取1，否取0。

wjks表示工厂k是否以等级s为配送中心j补货，是取1，否取0。

2.3 选址—库存决策模型

2.3.1 供应链系统成本分析

在一个较长的规划期内，要想获得最小的供应链系统总费用，只需让该系统的日均总成本最小即可。此处，主要估算配送中心到零售商的日均运送成本、配送中心的日均库存成本和日均建设成本以及工厂到配送中心的日均运输成本。

(1)配送中心到零售商的日均运送成本

对于给定的某实际配送中心j和任一零售商i，若该中心是为零售商i服务的首级配送中心(即yij0=1)且尚未中断，则该中心一定会向零售商i运送产品，由于这一事件的发生概率为(1-q)，故此种情形下该中心到零售商i的期望运送量为(1-q)μiyij0=q0(1-q)μiyij0；若该中心为零售商i服务的第b(1≤b≤n)级配送中心(即yijb=1)，并且为零售商i服务的第0～(b-1)级配送中心已同时中断但该中心没有中断，这种情形下该中心也一定会向零售商i运送产品，由于这一事件的发生概率为qb(1-q)，故此时该中心到零售商i的期望运送量为qb(1-q)μiyijb。另外，若该中心不是零售商i的第b(0≤b≤n)级配送中心(即yijb=0)，即便该中心没有中断，它也不会以等级b向零售商i运送产品，但此种情形下该中心到零售商i的运送量仍可记为qb(1-q)μiyijb。综上所述，在等级b(0≤b≤n)上配送中心j到零售商i的期望运送量可记为qb(1-q)μiyijb。

类似地，因虚拟配送中心永不中断，在等级b(0≤b≤n)上虚拟配送中心|J|到零售商i的期望运送量可记为qbμiyi|J|b。

因此，配送中心到零售商的日均运送成本为：

(1)

(2)配送中心的日均库存成本

对于给定的某实际配送中心j，其日运送量的均值和标准差分别为：

(2)

(3)

(4)

标准差为

(5)

因此，配送中心j的日均库存费用为

(6)

由式(6)可以看出，若μj=0，则Cj=0，这与现实情况相符。

因此，配送中心的日均库存成本为

(7)

(3)配送中心的日均建设成本

配送中心的建设成本与其容量大小密切相关，如果假设配送中心的容量不受限制，则难以准确反映建设成本，与现实情况不符。此处，将配送中心建设成本分为固定成本和可变成本两个部分，其中固定成本主要包括建设时的管理成本、行政办公和其他辅助设施的基本建设成本等;可变成本主要包括仓储设施的建设成本及其可能引起的其他设施的增加成本，可变成本与仓储最大库存水平(即仓储容量)直接相关。最大库存水平Aj3=Qj+Aj2。因此，实际配送中心j的日均建设成本为：

(8)

配送中心的日均建设成本为

(9)

(4)工厂到配送中心的日均运输成本

类似于配送中心到零售商的日均运送成本分析方法，可以得到工厂到配送中心的日均运输成本：

(10)

可见，工厂到配送中心的日均运输成本同时受到工厂和配送中心两级设施的中断影响，且该影响并非单级设施中断影响的简单叠加。

2.3.2 数学规划模型

为使供应链系统的日均总成本最小，建立混合整数非线性规划模型(Model1)：

minTC=CIJ+CJ+FJ+CJK。

(11)

s.t.

式(4)，式(5)。

i=1,2,…,m;b=0,1,…,n。

(12)

j=1,2,…,n;s=0,1,…,g。

(13)

yijb≤xj，i=1,2,…,m;

j=1,2,…,n;b=0,1,…,n。

(14)

wjks≤xj，j=1,2,…,n;k=1,2,…,

g+1;s=0,1,…,g。

(15)

(16)

(17)

xj∈{0,1}，j=1,2,…,n。

(18)

yijb∈{0,1}，i=1,2,…,m;j=1,2,…,

n+1;b=0,1,…,n。

(19)

wjks∈{0,1}，j=1,2,…,n;k=1,2,…,

g+1;s=0,1,…,g。

(20)

其中：目标函数式(11)的第1部分为配送中心到零售商的日均运送成本，第2部分为配送中心的日均库存成本，第3部分为配送中心的日均建设成本(包括固定建设成本和可变建设成本)，第4部分为工厂到配送中心的日均运输成本。约束条件式(4)和式(5)服务于目标函数值的计算；式(12)确保在指派虚拟配送中心为某个零售商送货前，在每一个指派等级上有唯一的配送中心为该零售商送货；式(13)确保在指派虚拟工厂为某个配送中心补货前，在每一个指派等级上有唯一的工厂为该中心补货；式(14)保证只有确定建设的配送中心才能考虑其送货任务；式(15)保证只有确定建设的配送中心才能考虑其补货需求；式(16)确保每个配送中心最多在一个指派等级上为某个零售商送货；式(17)确保每个工厂最多在一个指派等级上为某个配送中心补货；式(18)～式(20)为决策变量的取值约束。

3 优化算法

选址—库存决策模型(即Model1)具有高维性和非线性特征，是一类NP-hard问题，不宜直接求解。但是，如果能够事先给定配送中心选址方案，即给定xj的值，Model1便通过一定程度的降维简化成了单一的指派决策模型(Model2)。为便于表述，此处对已确定建设的配送中心的编号和虚拟配送中心的编号进行连续化处理，并用j′表示处理后的编号，J′表示处理后的编号集合，b′表示新编号下的配送中心指派等级。假设已确定建设n′个配送中心，则有j′=1,2,…,n′,n′+1，|J′|=n′+1。Model2如下：

minTC=CIJ′+CJ′+FJ′+CJ′K。

(21)

(22)

(23)

b′=0,1,…,n′。

(24)

j′=1,2,…,n′;s=0,1,…,g。

(25)

j′=1,2,…,n′+1。

(26)

k=1,2,…,g+1。

(27)

yij′b′∈{0,1}，i=1,2,…,m;j′=1,2,…,

n′+1;b′=0,1,…,n′。

(28)

wj′ks∈{0,1}，j′=1,2,…,n′;k=1,2,…,

g+1;s=0,1,…,g。

(29)

虽然Model2仍是混合整数非线性规划模型，但可以通过特定成本分析法(见3.1节)确定工厂/配送中心相对于配送中心/零售商的服务指派方案，从而得到决策变量wj′ks和yij′b′的值，以及既定选址方案下的供应链系统日均总成本(不再以传统算法求解模型)。可见，如果能够产生不同的选址方案，有望在短时间内得到Model1的优化结果。遗传算法(Genetic Algorithm, GA)是解决高维决策问题的一种有效算法[12-14]，下面将根据GA原理产生、比较并优化配送中心选址方案(算法中的染色体代表选址方案)，同时基于特定成本分析法获得每个选址方案(或者说Model2)的设施服务指派方案和对应的系统日均总成本。这样，便形成了GA框架下嵌入特定成本分析法的混合遗传算法(Hybrid Genetic Algorithm, HGA)，可用于Model1的求解。

3.1 特定成本分析法

此处的特定成本包括产品渠道成本和供应链系统总成本两种。为了获得既定选址方案下工厂和配送中心两类设施的服务指派方案，首先根据产品渠道成本构造一个初始设施服务指派方案，即找到Model2的一个初始可行解，然后再根据供应链总成本获得调整后的满意设施服务指派方案，即找到Model2的满意解。

3.1.1 基于产品渠道成本构造初始设施服务指派方案

设施中断后，为了以较少的投入保障下游成员的产品供应，文献[1,3]注意到运输费用与运输量和运输距离的线性关系，在假设运输路况无差异的情况下，按照设施与下游客户的距离远近确定了设施服务指派等级，即距离越近，指派等级值越低;距离越远，指派等级值越高。此处，若将某节点的产品渠道成本定义为将单位产品从工厂或虚拟设施沿着给定渠道转移至该节点的物流过程成本，则可以根据产品渠道成本的高低类似地确定设施服务指派等级，即在未得到虚拟设施的服务指派等级前，设施的产品渠道成本越低，其指派等级值越低;渠道成本越高，指派等级值越高。显然，这种确定方法满足Model2的约束条件，得到的设施服务指派方案一定是可行方案。

根据产品流向，首先确定工厂的服务指派等级，然后再确定配送中心的服务指派等级。对于一个已确定建设的配送中心j′(j′=1,2,…,n′)，其产品必然直接来源于工厂k(k=1,2,…,g)或虚拟工厂|K|，因此配送中心j′的可能产品渠道成本只能为cj′k(k=1,2,…,g)或cj′|K|。为尽量以较低的渠道成本获取产品，此处将产品渠道成本从小到大以0为序号起点依次排序，然后确定工厂相对于配送中心j′的服务指派等级。确定原则为：①在虚拟工厂的指派等级未得到认定前，根据产品渠道成本序号由前向后依次认定相应工厂的服务指派等级，并令指派等级值等于产品渠道成本序号；②一旦认定了虚拟工厂的指派等级，结束为配送中心j′补货的工厂指派等级认定任务。根据上述原则，如果系统中有4个实际工厂和1个虚拟工厂，且产品渠道成本cj′1≤cj′3≤cj′5≤cj′2≤cj′4，则对于配送中心j′，除了wj′10=wj′31=wj′52=1外，其他的wj′ks均等于0。

利用上述方法确定各工厂/配送中心对于各配送中心/零售商的服务指派等级后，便形成了既定选址方案下的初始设施服务指派方案。由于各工厂在正常情况下供应能力充足，并且根据产品转移过程可知，对于给定的选址方案，确定上游设施的服务指派等级时不会受到下游设施中断的影响，因此按照上述方法确定的工厂服务指派等级即为使工厂层至配送中心层的期望运输费用最小(参见式(10))的最优指派等级[1]。从本质上讲，式(21)的供应链总成本即为各零售商按照其产品渠道成本获得所需产品所花费的全部费用，故如果能够获得各零售商的准确的产品渠道成本，则可以就此确定最小的供应链总成本。在此情形下，理论上可以根据零售商的产品渠道成本确定配送中心的最优服务指派等级。但是，在计算过程中，考虑到非线性关系项的影响(参见式(6)和式(8))，对零售商的产品渠道成本进行了近似处理，因此本节算法仅能称为确定配送中心服务指派等级的构造启发式算法。但应用该算法时能够确定工厂的最优服务指派等级。

3.1.2 基于供应链总成本改进配送中心服务指派方案

在制定初始设施服务指派方案时，对间接渠道中的零售商产品渠道成本进行了近似计算，这可能导致某些配送中心对于某个零售商的服务指派等级的微小变动。通过比较初始方案和某些配送中心服务指派等级已产生微小变动的其他众多方案的供应链总成本(即式(21)中的TC值)，能够确定其中的最佳方案并判断有无必要进行方案调整。若有必要进行方案调整，则将调整后的方案再次与某些配送中心服务指派等级产生微小变动的其他方案进行比较，可以进一步优化指派方案。根据该思路，能够找到较为理想的指派方案，但寻优过程中的计算量大，计算效率低。为此，提出利用原方案与其临近方案的供应链总成本差值表改进配送中心指派方案的计算方法。该算法可以称为确定配送中心服务指派等级的改进启发式算法。由于计算过程中根据目标函数式(21)改进配送中心指派等级，故改进后的结果必然是Model2的满意解。

此处，将一个已有设施服务指派方案的临近方案定义为：在已有方案的基础上，交换为某个零售商送货的具有相邻指派等级的两个实际配送中心所形成的方案、将为某个零售商服务的虚拟配送中心的指派等级提前一个级别(该级别的原配送中心变为无服务指派等级的配送中心)所形成的方案，或者将为某个零售商服务的虚拟配送中心的指派等级退后一个级别(将虚拟配送中心的原服务指派等级赋给无服务指派等级中编号最靠前的配送中心，即赋给在该指派等级上最具有送货可能性的那个配送中心)所形成的方案。根据定义可知，临近方案的决策变量取值仍然满足Model2的约束条件，故临近方案仍是可行方案。计算时，可以将临近方案视为原方案的可比较方案。为便于计算，给出命题1。

命题1可以根据以下3种情形计算原方案与其临近方案的供应链总成本差值ΔTC。

(30)

(31)

(32)

式中：

(33)

证明对于情形(1)，由于已经确知wj′ks的值，根据式(22)和式(23)可以确定Lj′和σLj′的值。于是，由式(1)和式(10)可知，日均运输成本CIJ′和CJ′K均为决策变量yij′b′的线性函数。对于线性函数而言，只有那些在临近方案中取值已发生变化的yij′k的线性关系项才会导致原方案与临近方案之间的目标函数值差异。此处，原方案与其临近方案的日均运输成本的差值为：

(34)

由式(6)和式(8)可知，配送中心j′的日均库存成本和日均建设成本均为决策变量yij′b′的非线性函数，且两成本之和为：

(35)

(36)

由于原方案与其临近方案的目标函数差值为ΔTC=Δ(CIJ′+CJ′K)+Δ(CJ′+FJ′)，代入Δ(CIJ′+CJ′K)和Δ(CJ′+FJ′)的计算式，整理后可知式(30)成立。情形(1)得证。

类似地，可以证明对于情形(2)有式(31)成立，对于情形(3)有式(32)成立(证明过程略)。证毕。

根据命题1计算原方案与其某临近方案的ΔTC，如果ΔTC>0，说明该临近方案优于原方案，可以将其作为新方案中的备选方案。若存在多个优于原方案的临近方案，可以选择使ΔTC最大的那个临近方案作为调整后的新方案。由于新方案与原方案相比，已经将为某个零售商送货的或最具有送货可能性的一个实际配送中心与跟该中心具有相邻指派等级的某个配送中心(实际的或虚拟的)进行了交换，因此新方案的临近方案与原方案的临近方案会有不同。为便于计算新方案与其临近方案的供应链总成本差值，给出推论1。

推论1若通过交换原方案中相对于零售商i′的一个实际配送中心j′与跟该中心具有相邻指派等级的某个配送中心(实际的或虚拟的)形成了新方案，则在计算新方案与其临近方案的目标函数差值时，如果在新方案中配送中心j′以某个指派等级为零售商i0送货，则需重新计算新方案与那些相对于零售商i0通过交换配送中心j′与跟该中心具有相邻指派等级的某配送中心而形成的新临近方案的目标函数差值；其他情况下，新方案与新临近方案的目标函数差值和原方案与对应的原临近方案的目标函数差值相同。

证明由式(33)可知，Ej′(j′=1,2,…,n′)的计算值主要取决于yij′b′=1(i=1,2,…,m;b′=0,1,…,n′)的各项，即有哪些零售商在某个指派等级上由配送中心j′为其送货。显然，在相对于零售商i′交换配送中心j′与跟该中心具有相邻指派等级的某配送中心时，一定会改变某个yi′j′b′(b′=0,1,…,n′)的取值，即若配送中心j′不再以某个指定等级为零售商i′送货，则该yi′j′b′由1变为0，否则，若改由配送中心j′以某一指定等级为零售商i′送货，则该yi′j′b′由0变为1，这势必会导致Ej′的数值变化。由式(31)～式(32)可知，无论在哪种情形下，若通过交换相对于零售商i0的配送中心j′与跟该中心具有相邻指派等级的某配送中心形成新方案的临近方案，则新方案与该临近方案的目标函数差值ΔTC均会发生改变。在其他情况下，虽然新方案/新临近方案与原方案/对应的原临近方案相比，目标函数值不同，但新、旧ΔTC不变。故推论1成立。证毕。

此处，基于命题1和推论1，给出利用原方案与其临近方案的供应链总成本差值表改进配送中心服务指派方案的计算步骤。

(1)将初始设施服务指派方案看作原方案。

表1 原方案与其临近方案的ΔTC值

(3)原方案的最优性检验与方案调整。若表1中的ΔTC值均不大于0，原方案即为最佳方案，结束调整过程；否则，将对应于表中最大ΔTC值的那个临近方案作为调整后的新方案，同时根据推论1计算新方案与其临近方案的ΔTC值。例如，对应情形(1)，若表1中的ΔTC5-2-3为最大差值(正数)，则新方案为通过交换原方案中为零售商5送货的第2级和第3级配送中心1和2所形成的临近方案。根据推论1，需重新计算相对于各零售商的与实际配送中心1或2相关的ΔTC值，为便于区分，将该值记为Δ′TCi-b′-(b′+1)(仍按照命题1计算该值)，计算结果如表2所示。类似地，对应情形(2)，若表1中的ΔTC1-1-2为最大差值(正数)，计算结果如表3所示；对应情形(3)，若表1中的ΔTC4-1-2为最大差值(正数)，并且在原方案中相应于零售商4的第2个无指派等级的配送中心编号为1，计算结果如表4所示。

表2 新方案与其临近方案的ΔTC值—情形(1)

表3 新方案与其临近方案的ΔTC值—情形(2)

表4 新方案与其临近方案的ΔTC值—情形(3)

(4)将新方案看作原方案，重复步骤(3)，直至表1中的ΔTC值均不大于0为止。

通过以上运算，可以确定配送中心相对于零售商的理想服务指派等级;联合先前得到的工厂相对于配送中心的最优服务指派等级，可以得到Model2的满意解。

3.2 混合遗传算法

将Model1分解为配送中心选址和设施服务指派两个相互关联的子问题，然后利用GA优化选址方案和特定成本分析法确定每个选址方案的设施服务指派方案。下面给出HGA的主要运算步骤。

(1)生成初始种群 每条染色体代表一个配送中心选址方案。对应于n个候选配送中心的建设情况，用一个由1和0组成的长度为n的二进制串表达染色体，其中1表示建设，0表示不建设。为便于进化计算，随机产生一定数量的染色体作为GA的初始种群。

(2)计算染色体适应度 针对每条染色体，利用特定成本分析法确定工厂和配送中心的服务指派方案，进而得到Model2的目标函数值。由于供应链总成本越小越好，计算时首先将目标函数值的倒数作为染色体适应度的映射值。然后利用线性尺度变换方法，将种群中的各映射值规格化在区间[0,1]内，并将规格化后的数值作为染色体的适应度。

(3)遗传算子操作 ①根据轮盘赌法选择父代个体；②根据交叉概率和双点交叉策略形成子代个体；③根据变异概率和单点0-1翻转变异策略变异子代个体；④根据最优保存策略保留父代精英。

(4)循环或终止GA运算 重复步骤(2)和步骤(3)，直至迭代到了最大允许进化代数或在规定进化代数内最优染色体无变动时，终止GA运算，此时的最优染色体就是Model1的满意解。

(5)结果整理 根据Model1的满意解确定配送中心的建设位置、仓储容量，以及各工厂/配送中心对于各配送中心/零售商的补货/送货指派等级。

4 算例分析

M公司在河南省拥有4个工厂和97个零售商。目前，该公司直接从工厂向零售商运送产品，响应速度慢，运送费用高，当某些工厂中断时不便协调运送方案。为改进供应链网络，降低运送费用，M公司拟在19个候选地点建设若干配送中心，将来运营时，工厂向配送中心批量补货，配送中心每日向零售商运送产品。河南省东西向距离约580 km，南北向距离约550 km，因此可以将所有设施映射在580×550的平面上。考虑M公司的目前运作状况和将来运作要求，参考文献[1,5,6]的参数设置方法，将各设施的中断概率赋值为0.1，即p=q=0.1。其他主要参数的取值为，cj|K|=8，ci|J|=15，hj=2，ej=1，αj=95%，zαj=1.96，vjk=80，fj和Bj的值如表5所示。对于本算例，由于4个以上工厂/配送中心同时中断的概率小于0.000 1，属于小概率事件[5]，计算时仅考虑了各配送中心/零售商3级以内的可用工厂/配送中心(包括虚拟的)，即仅取0≤s≤3和0≤b′≤3范围内的服务指派等级。

表5 配送中心j的fj和Bj

利用MATLAB语言编程，在处理器为Intel(R) Core(TM) i5-3230 M CPU@2.60 GHz、内存为4.00 GB、操作系统为Windows 7的计算机上运行程序。正式运算前，综合考虑计算允许时间、算法收敛性、解空间扩展和避免算法“早熟”的需要，在多次试验测试和计算过程跟踪分析的基础上，确定了相对合适的遗传算法参数，即交叉概率为0.7，变异概率为0.1，种群规模为50，最大进化代数为100。正式运算后，连续运行15次程序，运算时间均在443 s内，平均值283 s。算法表现出良好收敛性，运算结果均为：建设配送中心4、8、12、13、15，仓储容量依次为1 285、1 413、1 513、1 167、1 367，供应链总成本94 609(服务指派关系略)。其中，第1次运算时间276 s，运算过程如图2所示。图2中，“种群平均成本”和“种群最小成本”分别表示某代种群的平均供应链总成本和最小供应链总成本，种群平均成本呈现出逐渐下降趋势，体现了适者生存、优胜劣汰的进化特征。若将各配送中心/各零售商与其首级服务设施连接起来，可得到如图3所示的供应链基础网络(即各设施均未中断时的供应链网络)。由图3可以看出，部分零售商的首级服务设施并不是距其最近的配送中心，这说明当考虑配送中心的可变建设成本和库存成本时，不能像传统方法那样仅凭距离远近确定服务指派关系。

为便于比较，称上述p=0.1、q=0.1时的运算结果为结果1；分别称p=0、q=0.1，p=0.1、q=0和p=0、q=0时的运算结果为结果2、3、4。因此，结果2为：建设配送中心4、6、12、13、15、16，仓储容量依次为1 287、916、1 531、1 204、1 343、1 012，总成本为91 019；结果3为：建设配送中心编号4、6、12、13、15，仓储容量依次为1 332、943、1 800、1 204、1 330，总成本为91 228；结果4为：建设配送中心4、6、12、13、18，仓储容量依次为1 332、943、1 981、1 145、1 012，总成本为88 021。可以看出，不同结果的选址决策存在明显差异。结果2比结果1多出1个配送中心，结果3、4与结果1的配送中心数量虽然相同，但配送中心建设位置不尽相同，且仓储容量存在较大差异。若在考虑两级设施中断(p=0.1、q=0.1)的情况下，应用结果2、3、4的选址方案(含选址决策和仓储容量)计算各项成本，对比分析如表6所示。计算时，规定超出配送中心仓储能力的补货量由虚拟工厂提供；表6中某结果的“总成本增长率”指该结果与结果1总成本的差值同结果1总成本的比率。从表6可以看出，若将结果2、3、4所对应的选址方案应用于含有两级设施中断风险的运作情景中，与结果1相比，它们的总成本均有所增加。可见，在一并考虑两级设施中断情形进行选址—库存联合决策时，不宜以单级设施中断或不考虑设施中断时的决策结果代替其满意方案。

表6 运算结果对比分析

另外，以往考虑设施中断的供应链选址文献大多忽略了库存费用，并且通常假设配送中心的仓储能力无限制。为作比较，将不考虑仓储能力和库存费用的运算结果记为结果5，该结果为：建设配送中心1、4、6、9、10、12、13、15、16，总成本为70 448。若考虑库存费用，结果5对应的选址决策会产生18 796的库存成本和18 641-9 510=9 131的可变建设成本，与结果1相比，总成本增长率达3.98%(如表6)。可见，若忽略库存费用，虽然通过增设4个配送中心降低了运输成本，但是由于仓储地分散反而会增加更多的库存成本，进而导致了更高的系统总成本。这在一定程度上说明了进行选址决策时同时考虑库存费用的重要性。

5 结束语

综合考虑需求不确定性、多级设施中断风险、供应链库存费用和可变建设成本对供应链网络优化设计的影响，建立了以系统期望总成本最小化为目标的供应链选址—库存联合决策模型。该模型是一个复杂的混合整数非线性规划模型，不宜应用常规算法求解。为此，设计了一种在GA框架下嵌入特定成本分析法的混合遗传算法。算法中，利用GA产生若干配送中心选址方案，并对选址方案寻优；利用特定成本分析法确定既定选址方案下的设施服务指派方案。特定成本分析法又由两部分构成，其中：第一部分基于产品渠道成本构造既定选址方案下的初始设施服务指派方案;第二部分基于供应链总成本并利用原方案与其临近方案的总成本差值表改进既定选址方案下的设施服务指派方案。通过算例验证了模型和算法的有效性，为求解类似问题提供了新思路。研究成果有利于在供应链网络设计阶段从根本上降低多级设施中断风险的不利影响，有助于根据设施服务指派等级科学制订配送中心的应急补货方案和零售商的应急送货方案，具有现实指导意义。未来，将进一步研究设施中断时同级设施间的产品横向调配问题以增强供应链弹性。