不确定条件下后装协同保障链优化调度

曾 斌, 张泉先, 李厚朴

(1. 海军工程大学管理工程与装备经济系, 湖北 武汉 430033;2. 海军工程大学导航工程系, 湖北 武汉 430033)

0 引 言

后装保障链对于军队后勤和装备保障具有十分重要的作用,它可以看作是从后方保障基地到前线作战部队的一条需求供应链或网络,主要功能是存储、运输、中转和分配作战物资,协调保障行动。它与商业供应链存在相似之处,但由于目的要求不同导致二者又有很多不同[1-2],保障链相比商业供应链的特点体现在:① 敏捷性要求更高;② 供应链更复杂;③ 资源类型更加多样;④ 环境动态变化;⑤ 对可靠性和维修性要求更高。其中④和⑤与不确定性直接相关。

近年来后装保障供应链已成为军事理论研究的热点问题,也取得了不少成果。文献[3-4]分别利用时空网络和复杂网络技术描述了保障网络,但以保障中断恢复为研究背景,不确定影响考虑较小。文献[5]研究了军事供应链中武器装备备件的保障生产问题。文献[6]研究了军事供应链的风险管理问题。文献[7]通过价值流图减小多级军事供应链的备件提前期。它们都指出了后装保障属于多保障点、多需求点以及多梯队的复杂供应链,具有较大的失效风险。

文献[8]利用粒子群算法解决两层军事供应链问题,文献[9]为一个3层军事供应链提供决策支持,文献[10-11]分别提出了战时陆地和海上的集中式后勤保障规划模型并用遗传算法进行求解。它们都指出了军事供应链的优化计算复杂度较高,但都采取了战时统一指挥下的集中式规划模型。

在研究供应链的不确定性方面,文献[12]用区间数度量装备供应网的不确定性,采用基于禁忌搜索的两阶段进行求解,给本文以较大启发,但优化模型中没有考虑库存水平和运输方式,求解算法性能不够,另外区间分析在进行复杂运算时易产生区间扩张,产生较大误差。文献[13-15]采用鲁棒规划解决不同类型供应链的不确定性问题。文献[16-17]采用模糊控制解决备件多级供应的不确定性问题,虽然与本文采用的模糊规划在模型建立和应用目的上有较大不同,但表明了模糊优化在处理保障供应不确定性问题方面的优势。文献[18-19]主要研究了灾害救援供应链的设计,利用历史统计数据来支持不确定性规划问题。

本文主要贡献如下:① 无论是应急保障还是作战保障,现有研究大多假设有一个集中管理部门,由其统一协调与控制,这对于持续时间较短的小规模行动是有效的,但是对于大规模且需要长期对抗的军事活动,例如争夺海上资源的分布式海战场以及海上预置基地的设置[20],需要多部门协调和征用民用设施和资源,为此本文提出了一个基于信息共享的协同保障算法,解决后方保障基地和前进基地之间的资源协调问题。② 尽管近年来关于不确定情况下的供应链研究越来越受到重视,但是它们主要采用统计或鲁棒规划方法来处理不确定性,这需要有大量的客观历史数据来做支撑,从中预估出数据的离散或连续概率分布情况,而且只有在系统行为能够多次重复时,统计规划的结果才具有实践意义。但是对于作战保障而言,一方面缺乏足够多的实际战场数据来估计模型中不确定性参数,另一方面由于敌方武器性能和兵力参数的可信度难以验证,导致兵棋演练或作战仿真得到的数据也缺乏权威性。因此,本文采用模糊规划来处理后装保障的不确定性参数,综合保障指挥员的经验及小样本来建立不确定参数的模糊数。③ 供应链优化往往包括多个相互冲突的目标,现有研究一般以线性加权法来处理,但是在战时后装保障场景下,优化项较多而且缺乏先验知识来估算各个目标权重值,为此利用加权增强约束法来估算多目标Pareto解,辅助决策后装指挥人员选择合适的解决方案。④ 与传统的应急保障和后勤保障研究相比,本文研究对象更为复杂,属于多规划周期、多物质类型、多需求点、多保障梯队的供应链优化问题,而且在决策变量中增加了后装指挥需要的重要指标-库存水平,这些问题在提高模型实用性的同时也使得解算过程更为复杂,为了提高计算精度和效率,提出了一个嵌入自适应大规模邻域搜索的Memetic算法。

1 规划模型

本文模型属于无限时域规划,为了书写简便,在参数和决策变量的定义中省略了系统时间描述,模型分为以下两个部分。

1.1 前进基地模型

1.1.1 对象/集合的定义

B:保障基地集合,保障基地b∈B;

Q:候补前进基地集合,前进基地q∈Q;

R:保障需求点集合,r∈R;

K:保障物质类型集合,k∈K;

V:运输方式(工具类型)集合,v∈V。

1.1.2 参数的定义

hkq:在前进基地q每存储单位数量的k物质所需要花费的维护开销;

Mv:基地拥有运输工具v的最大可用数量;

Cv:运输工具v的最大运输容量;

av:运输工具v的护航开销;

ck:每单位物质k占用的存储空间;

Oq:前进基地q的最大库存容量;

1.1.3 决策变量的定义

xbqkv:以工具v作为运输方式,从保障基地b运送到前进基地q的物质k的数量(决策者是前进基地);

yqrkv:以工具v作为运输方式,从前进基地q运送到保障需求点r的物质k的数量;

zl:布尔变量,为1表示在l点部署前进基地,否则为0;

dkq:前进基地q存储的物质k的库存水平;

ukr:需求点r申请物质k,但没有得到满足的数量;

Tbqv:从保障基地b到前进基地q之间的运输工具v的数量;

1.1.4 前进基地规划模型的设计

目标函数如下:

(1)

目标函数包含5项,第1项为从保障基地到前进基地的运输开销(与距离有关),第2项为从前进基地到保障需求点的运输开销,第3项为前进基地的库存维护开销,第4项为缺货开销,第5项为护航开销(与物质量或运输工具数量有关),这里开销并非金额,而是惩罚单位。约束条件如下:

(2)

(3)

(4)

(5)

(6)

(7)

(8)

Tbqv≤Mv

(9)

(10)

式(2)表示前进基地收到的物质不大于保障基地发送的物质量;式(3)表示前进基地的库存约束,即对某一种物质,本供货周期中前进基地进货数量加上上一周期的库存量减去发货量,等于现在的库存量。式(4)表示保障需求点申请的物质量减去没有满足的物质量等于它实际接收到的物质量;式(5)表示前进基地库存总量约束;式(6)表示从保障基地到前进基地的运输总量约束;式(7)表示从前进基地到保障需求点的运输总量约束;式(8)表示流量约束,M为一个极大数,表示只有该候选地址部署了前进基地才能接收物质;式(9)和式(10)表示运输工具数量的限制。

1.2 保障基地模型

模型参数定义如下:

pkb：保障基地b采办单位物质k的开销;

ck：每单位物质k占用的存储空间;

Skb：保障基地b被申请发送的物质k数量(该信息从前进基地q获取)；

决策变量定义如下:

目标函数如下:

(11)

式中，目标函数包括3项,第1项为总采办开销(战时可省略),第2项为库存开销,第3项为保障基地的缺货惩罚。约束条件如下:

(12)

(13)

(14)

(15)

式(12)表示保障基地的库存约束,即对某一种物质,本供货周期中保障基地采办数量加上上一周期的库存量减去发货量,等于现在的库存量。式(13)表示保障基地发往前进基地的物质量等于前进基地申请量减去保障基地的缺货量。式(14)表示保障基地的库存总量限制。

2 分布式协同算法

如果战场局势需要采取处于长期遏制态势,前进基地作为预置储备节点为分布式杀伤作战节点服务[21],后方保障基地可能会租用民用物流公司,这时要更多的从经济利益和市场活动出发,后方保障基地关心的是采办开销,前进基地关心的是库存和运输开销,二者之间需要建立一个基于信息共享的采办—分发协同机制来提高后装保障效率。前进基地和后方保障基地的协同算法设计如下。

步骤 2前进基地计算前进基地规划模型,见目标函数式(1)和约束条件式(2)～式(10),得到后装物质的分发方案,其中xbqkv表示后方保障基地至前进基地的物质种类及数量,汇总后作为Skb共享至保障基地模型。

(16)

3 模糊规划的转化

根据作战区域激烈程度和任务的不同,保障需求的类型和数量具有较大的不确定性,因此前进基地模型中的物质申请量是一个不确定参数。从保障基地到前进基地以及从前进基地到需求点的运输开销会随着作战区域和路线的变化而变化,也属于不确定参数,由于物质短缺导致的惩罚系数也与作战任务和优先级相关,属于不确定参数。

本文利用了模糊规划方法处理优化问题中的不确定性。由于本文中参数不确定性较大,所以采用了梯形分布作为隶属度函数。另外模糊规划中使用两种测度来测量置信水平度[22],一种是基于乐观的可能性测度,还有一种是基于悲观的必然性测度,在战场环境下物质供应比较紧张,本文采用谨慎态度来处理物质保障问题,所以通过必然性测度来保证机会约束的满意度。下面为本文紧凑形式规划模型对应的模糊规划模型,目标函数如下所示:

(17)

约束条件如下:

(18)

Gx≤Hy

(19)

(20)

x,y为正整数向量

(21)

图1 梯形隶属度函数

区间EI和期望值Ev可按下式计算:

(22)

(23)

(24)

从式(24)可推导得:

(25)

从式(25)可以把紧凑形式模糊规划模型转换成对应的清晰式,其目标函数描述如下:

(26)

约束条件为

Cx≤(Iβ-β)D(2)+βD(1)

(27)

Gx≤Hy

(28)

(29)

(30)

x,y为正整数向量

(31)

式中，Iβ为全1矢量，维数与β相同;Iv为全1矢量，维数与v相同。因此,基于上述紧凑形式的清晰式规划模型,将含有不确定参数的保障基地模型和前进基地模型分别等价变换为清晰式,下面只描述清晰化改造后的目标函数和原来包括不确定参数的约束关系,原来只有确定参数的约束条件保持不变,带下标(1)～(4)的参数为对应的可调节梯形隶属度函数参数,前进基地清晰等价模型的目标函数如下:

minZ1=

(32)

原包含不确定参数的约束条件式(4)改造为以下两个不等式,其他约束条件不变。

(33)

(34)

保障基地清晰等价模型的目标函数如下:

(35)

原包含不确定参数的约束条件(15)改造为以下不等式,其他约束条件不变。

(36)

4 求解算法

保障基地和前进基地的优化可以看作是一个多目标规划问题。

4.1 多目标转换单目标

根据决策者的参与阶段,多目标转换方法可以归纳为以下3种:① 先验方法，最常用的加权和[23]就属于这种方法,它要求决策者在问题求解之前事先确定目标的权重;② 交互法，在求解过程中需要决策者参与问题的搜索过程[24],要求决策者对计算过程较为了解;③ 后验方法，生成一批有效解,由用户从中选出最适合的Pareto解[25]。后验方法虽然增加了时间复杂度,但能够在减少用户事先干预的情况下提高Pareto解的质量,鉴于后装保障问题的两个规划问题涉及优化项较多,且难以事先给定权重的具体值,所以本文采用了后验方法中ε-约束法的改进版本“加权增强ε-约束法”[26],目标函数转换为如下形式:

(37)

式中,θ1和θ2为可调节优先级参数，θ1+θ2=1;range1和range1分别表示前进基地和保障基地目标函数的取值范围;sl2为保障基地目标的松弛度,根据ε-约束法建议,δ值任取10-3和10-4之间的一个极小数。由于前进基地的保障效果直接关系到战场态势,所以取前进基地目标为主目标,保障基地目标移入约束条件。

原有保障基地目标函数改造为如下所示的惩罚约束,将其加入原有约束条件中:

Z2+sl2=ε2

(38)

式中,ε2不是一个数,而是一批数,可以看作一个矢量,所以规划模型也根据ε2的数量将转换为多个。本文单目标转化算法步骤具体如下。

步骤 2按下式分别计算前进基地和保障基地目标函数的取值范围:

(39)

步骤 3设置中间网格点数量g2,计算ε2矢量值为

(40)

这样原模型转换为g2+1个规划模型,每一个ε2对应的模型得到一个折中解。

4.2 基于Memetic算法的求解过程

尽管经过模糊规划和加权增强ε-约束法对原模型进行了清晰化和单目标转换,但转换后模型还是属于NP难的混合整数线性规划模型,现有数学方法难以计算其精确解,所以本文借鉴了Memetic算法框架[28],在利用遗传算法的全局搜索能力的同时,还嵌入了自适应大邻域搜索算法的局部搜索优势,在确保求解精度的前提下提高了计算速度。图2为本文算法流程图。

图2 Memetic算法流程图

4.2.1 染色体的编码和译码

对于整数规划,遗传算法存在Michalewicz矩阵、Prufer数字以及基于优先级等多种染色体编码方法,本文采用了基于优先级的分层分段改进编码方法[29],如图3所示,编码矩阵中,纵向分3层,首先按时间周期分组,在一个时间周期内又按物质种类分组,如果考虑运输工具,则需要再加一层,示例中为了简洁起见没有考虑运输工具。最后按优先级PR和库存水平IL分组,横向分两段,第一段为保障基地模型涉及的物质传输节点(保障基地和前进基地),第二段为前进基地模型涉及的传输节点(前进基地和保障需求点)。例子中保障基地数量|B|=3,前进基地数量|Q|=4,保障需求点数量|R|=5。在算法初始化阶段(见图2中步骤1),随机生成不相同的随机数(1～|B|+|Q|)作为保障基地段染色体,同样生成|R|+|Q|个各不相同的随机数(1～|R|+|Q|)作为前进基地段染色体。

图3 染色体编码示例

设T为决策周期数,K为保障物质类型数,下面为单段(保障基地段或前进基地段)染色体译码算法(见图2中步骤3)的伪代码。

输入参数:

S-发货节点集合(B或Q);

D-收货节点集合(Q或R);

Isdk-收发货节点之间的运输开销;

V(|S|+|D|)-物质k的优先级PR层染色体编码。

输出:

Xsdk-收发货节点之间运输的物质数量;

Zs-布尔量,决策是否在s节点建立基地。

Fort=1 toT∥遍历保障决策周期

Fork=1 toK∥遍历保障物质类型

输入该次循环所需参数;

While ∑sCks≤0 && ∑dRkd≤0

Xsd=0 ∀s∈S,d∈D

n=argmax{V}∥V中找出优先级最高的节点

ifn∈Sthen∥如果n为发货节点

s*=n

d*=argmin{Isdk|V(d)≠0,d∈D}

∥选择最小运输开销的节点为收货方

else如果n为收货节点

d*=n

s*=argmin{Isdk|V(d)≠0,s∈S}

∥选择最小运输开销的节点为发货方

Xs*d*=min(Cks*,Rkd*)∥选择运输物质数量

Cks*=Cks*-Xs*d*∥更新发货方库存

Rkd*=Rkd*-Xs*d*∥更新收货方需求量

ifCks*=0 thenV(s*)=0

ifRkd*=0 thenV(d*)=0

end loop

fors=1 to |S|

if ∑dXsd≤0 thenZs=1∥s点设置基地

endfor

endfor

4.2.2 染色体的交叉和变异

交叉算法通过交换父代染色体的部分基因段来扩展新的解集空间,整数互换编码可以采取的交叉算子较多,包括部分映射交叉、排序交叉以及基于位置的交叉等,但本文采取的是优先级分段编码,常规的染色体交叉算子容易引起交叉后基因出现互异性和不合理性[21]。

为了避免冲突检测和修补步骤影响执行效率,本文采取了二阶段子段互换算子,如图4所示。首先,生成一个随机二进制数组,把它分配至各个染色体段。本文只是针对现有2层供应链的2段编码进行说明,所以图4只需要2位二进制,但本文算法可以扩展到3层以上。第2阶段,如果被分配的数字为1,按图4说明交换算子。这样可以避免交叉后染色体出现重复基因,违反优先级编码原则。

图4 染色体交叉算子示例

与交叉类似,变异算子也用以扩展新解集空间并防止过早收敛,只不过它只作用于一个染色体上,本文采取了“新增”变异算子,即在选中染色体上随机选择一个位置的基因并把它插入到一个也是随机选择的新位置处,如图5所示。

图5 染色体变异算子示例

4.2.3 邻域搜索算法

为了弥补遗传算法局部搜索能力的不足,本文在Memetic算法中增加了自适应大邻域搜索算法[30](见图2中步骤4),它通过一系列破坏算子和修复算子对当前解进行变化,产生相应的新邻居解集合,其中破坏算子会破坏当前解的一部分,而后修复算子会对被破坏的解进行重建。自适应大邻域搜索算法会为每个破坏算子和修复算子分配权重,通过该权重控制对应算子在搜索期间使用的频率,为了得到更好的邻居解集,算法还会根据搜索过程中各个算子的表现动态调整其权重,该算法能在减少计算时间的同时提高解集质量。

本文定义了如下两类破坏算子:

(1) DN1，在当前解染色体编码中随机选择不相邻位置的基因实施破坏,基因数量随机;

(2) DN2,在当前解染色体编码中随机选择相邻位置的基因实施破坏,基因数量随机。

如果DN1和DN2中的基因数量不随机,而是选择1到多个,可以改变为多个破坏算子。

定义了如下3类修复算子:

(1) RN1,对选择破坏的基因集合随机重新排序,再放回原位置;

(2) DN2,对选择破坏的基因集合倒序排列,再放回原位置;

(3) DN3,选择破坏的基因集合与染色体内其他位置的基因交换位置。

邻域搜索算法伪代码如下所示。

输入:

1 遗传算法传来的当前迭代的最佳解;

2 破坏算子集Ω-和修复算子集Ω+;

3 破坏算子权重集ω-和修复算子权重集ω+;

4 禁忌表TL。

输出:改善的解集。

1ω-=(1,…,1);ω+=(1,…,1);∥ω-中每一个数字对应Ω-对应位置算子的权重,ω+也类似

2s=遗传算法当前迭代的最优解

3 repeat

4 根据ω-和ω+的权重,选择r∈Ω-,d∈Ω+

5s’=r(d(s));∥先破坏后修复s得到新解s’

6 ifs’ ∈TL then continue;∥新解曾经出现过

7 按式(37)计算新解s’的适应度F(s’);

8 ifF(s’)>F(s) thens=s’

9 按下式更新ω-和ω+:

(41)

(42)

10 对s’再次应用爬山法进行搜索

11 更新TL、θd和θr

12t=t+1

13 untilt>maxt

14 返回s’

步骤10中爬山法每次迭代都使用DN1和RN1来更新邻域。

5 仿真验证

为了评估本文算法的有效性,首先建立了一个包含3层保障链(保障基地、前进基地、保障需求点)的实验案例,实验数据包含保障需求点不同时间段的物质申请的种类和数量以及起始时保障基地的库存物质等信息,来源于分布式杀伤兵棋演练的存储数据,从中选取了5个不同规模想定的参数设置和仿真演练数据验证本文模型,模型中不确定参数取想定中对应参数的三角分布。

第1个实验把协同算法、集中求解算法与分立求解算法的结果进行了对比。保障基地数量为5,保障需求点数量为32,前进基地数量为5,在分立求解算法中,前进基地和保障基地模型分别求解,案例中供应链的每一个节点输出提取计算求和。集中求解算法中,取消第2节的分布式优化算法,前进基地和保障基地模型的约束条件和目标函数合并后优化。表1为置信水平分别为0.7、0.8和0.9时的目标函数值(开销),从中可以看出协同算法的总开销小于分立算法但高于集中算法。例如当β=0.7时,分立算法为957 632,但协同算法的缺货开销为0。分立算法转化为协同算法时,由于存在信息共享机制,所以前进基地开销没有增加,与分立算法相同,另外由于协同算法中没有缺货开销,所以保障基地开销和总开销小于分立算法。这里开销并非金额,代表惩罚单位。从表1可以看出,集中算法的实施需要后方前方统一指挥,虽然开销最小,但如第2节所述,这种方式难以持续。而当前,特别是某些争议海域局势紧张的局面可能长期存在,这就需要协同算法来优化处理。

表1 算法开销比较

第2个实验分别对前进基地模型(Z1及约束)、保障基地模型(Z2及约束)和协同保障模型进行敏感性分析。

图6和图7显示随着前进基地数量的变化,3个模型目标函数值(开销)的变化情况。如图6所示,对于所有3个模型,当前进基地数量增加时,Z1的开销减小,当前进基地数量为7时,Z1开销最小。在图7中,当前进基地数量为6～9之间时,Z2开销最小。尽管随着前进基地数量增加,协同模型和保障基地模型求解得到的Z2开销相应减少,但前进基地模型的Z2开销却并不总是减少,其运输开销和护航开销会随着数量增加而增加,转折点大概在前进基地数量为7的位置。另外,从图6和图7中可以看出协同算法求解得到的是Z1和Z2之间的较优值。

图6 前进基地数量对Z1开销的变化

图7 前进基地数量对Z2开销的变化

图8 运输工具可用数量对Z1开销的影响

在后装保障供应链中的一个关键问题是如何管理不确定性。如果直接把包含所有不确定参数的模型与确定性模型进行比较,会导致参数均值化问题,从而影响比较结果,为此在第3个实验中设计了4个不确定程度不同的比对模型进行性能比较。

比对模型4:所有不确定参数为随机数。

图9为5类想定下不同比对模型求解得到的总开销。可以看出由于比对模型1不考虑不确定性,所以在保障供应链中引起的开销最大,而且在不同想定下的开销变化量也比较大。比对模型2考虑了物质保障不确定性,尽管模型复杂度有部分增加,但应对不确定环境的能力也相应提高。模型的不确定性程度越高,它转换为概率约束规划后包含的参数种类和数量也会相应增加,即复杂度增加,但是与低不确定性模型相比,总开销会降低。如图9所示,不确定性程度越高的模型,总开销降低的同时稳定性也相应增强。比对模型4相较于模型1、2和3,总开销的平均降低率为8.9%、6.7%和3.7%。

图9 不确定程度不同模型的总开销

第4个实验检验协同算法计算Pareto解的有效性。根据保障基地数量、前进基地数量、保障申请点数量以及运输工具数量等参数,从仿真演练想定案例中分别选取小、中、中大、较大和大型5种保障规模的数据进行优化计算,并以只实现第4.2.2节染色体编码译码的常规多目标遗传算法NSGA-II作为比对算法,为了公平起见,遗传算法的最大迭代数量为本文Memetic算法的3倍。

以下为用于比对的两种性能指标:① Pareto优化解的平均数量;② Pareto优化解的平均比例APR[31]。设S1和S2分别为Memetic算法和NSGA 算法计算得到的Pareto解集,U为S1和S2的并集,S1集合的Pareto解比例定义为U中任何一个元素非支配的S1解所占比例,表达式如下:

(43)

如果APR增加,表示U中成员非支配的S1中的Pareto解数量也增加。

表2为每一个想定数据运行15次后计算结果的平均值,Met为改进Memetic算法,GA为NSGA-II算法。从中可以看出,针对每一个规模的案例,改进Memetic算法性能都要好于NSGA-II算法。改进Memetic算法平均能够找到7.86个Pareto优化解,而NSGA-II算法只能平均找到4.53个解。另外改进Memetic算法的解质量也要明显高于NSGA-II算法,平均0.99大于0.07。而且改进Memetic算法计算时间也要优于NSGA-II算法,平均花费620.81 s,而NSGA-II平均花费1 344.55 s。图10为两种算法某次运行的Pareto前沿示例图。从性能指标比较结果看,对于后装保障供应链优化问题,综合了加权增强ε-约束法以及邻域搜索法的改进Memetic算法具有良好的求解性能。

表2 两种算法求解多目标规划的结果比较

图10 两种算法的Pareto前沿示例

6 结束语

本文首次提出了不确定条件下基于信息共享的保障基地-前进基地的协同模型,该模型中保障基地作为后装物质的提供者,前进基地负责物质的存储及配送,二者与作战部队构成3层保障链模式,并对它们的保障行为进行了数学描述。然后在仿真案例中从分立、集中和协同3种决策结构的角度进行了模型求解,在分立结构中,由于保障链成员各自独立决策,造成供货方经常性缺货,保障链总体开销增大。与之相比,集中结构下的保障链总体开销得到大幅度降低。而协同结构由于采用了信息共享机制,开销同样得到较大降低,特别是前进基地在保持分立结构的同时还能减少开销。

本文还采用了模糊规划方法来解决保障链中的不确定性参数影响,为了克服转换后规划模型的计算复杂性过大的问题,提出了改进的Memetic算法进行模型求解,并通过仿真实验验证了算法的鲁棒性和有效性。下一步工作将继续研究存在运输中断风险的保障链规划模型。