考虑中断风险的装备维修器材供应选址调度组合优化

2022-06-04李延通曹军海

兵器装备工程学报 2022年5期

张闯，李延通，曹军海，张强，刘毅

(1.陆军装甲兵学院装备保障与再制造系，北京 100072；2.大连海事大学航运经济与管理学院，辽宁大连 116026；3.北京跟踪与通信技术研究，北京 100094； 4.军事科学院战略评估咨询中心，北京 100091)

1 引言

装备维修器材(以下简称器材)的快速、足量供应是作战部队保持作战能力、完成作战任务的重要物质保证。信息化条件下的现代战争节奏快、消耗大，需要战前根据作战计划制定器材保障方案，为战时作战部队提供足量、快速的器材供应。完整的器材保障方案通常包括野战仓库选址、部队需求分配及野战仓库任务调度等决策过程。事实上，各决策过程之间并不独立，如野战仓库的选址将对需求分配和各野战仓库任务调度产生重要影响。因此，传统的将上述决策过程分阶段逐个求解的方法，难以保证其保障方案的全局最优性，无法满足现代战争对器材供应提出的高效、精确的要求。同时，由于战场环境的高度不确定性，野战仓库面临遭敌火力打击等多种风险，可能导致供应能力中断，对部队的持续作战能力产生重大影响。

因此，需要对上述问题进行有效融合，形成一类考虑中断风险的装备维修器材供应组合优化问题。该问题求解难度相对较高，需要构建合理的数学模型并开发求解算法，以形成完整、科学、高效的器材保障方案。

与该问题密切相关的研究主要包括两类，一是考虑中断风险的供应链管理，二是选址调度组合优化问题。

中断风险是供应链管理中的重要问题之一，近年来，许多学者进行了深入研究，形成了许多成果。本文中针对其中的组合优化问题进行综述。Esmaeili-Najafabadi等针对中断风险下的集中式供应链中供应商选择和订单分配组合优化问题进行研究，采用供应商保护和预储备2种预防性保护策略以应对中断风险。Sawik等研究多层级供应链中，考虑中断风险的供应、生产、配送等的组合优化问题，构建了考虑均摊成本和服务水平的双目标随机混合整数规划模型。Rayat等针对多产品、多阶段选址-库存-路径组合优化问题，建立了最小化系统成本和中断故障的双目标混合整数非线性规划模型。国内方面，孔繁辉等从供应链弹性角度出发，研究了中断风险下OEM供应链弹性交互影响机制，并设计了一种针对性的深度学习机制以提升供应链弹性。张莹深入研究了考虑中断风险的供应链组合优化问题的模型和算法，具有很强的参考价值。还有其他研究人员从另外的角度对考虑中断风险下的供应链管理进行了深入研究。

选址调度组合优化(ScheLoc)将经典的设施选址和资源调度问题整合为一类组合优化问题，能够提高解的全局最优性，近年来得到国内外学者的广泛关注和研究。ScheLoc问题根据选址数量可分为单机和并行机ScheLoc问题，也可根据选址范围分为平面(连续)和离散ScheLoc问题。针对离散并行机ScheLoc问题，Wang等提出了一种基于网络流的数学模型并提出多种启发式算法进行求解。Kramer等设计了一种新的弧-流模型(arc-flow)并提出一种高效的列生成算法以及3种启发式算法。Filcek等研究设施数量不固定的双目标ScheLoc问题，以总完成时间和选址成本的最小化为目标构建数学模型，并提出一种基于NSGA-Ⅱ算法机制的启发式算法。受篇幅限制，ScheLoc问题更多研究可见文献。

从目前来看，考虑中断风险的装备维修器材选址调度组合优化问题还未得到深入研究。与该问题相近的文献中，王亚东等针对战时备件选址-分配优化问题，设计了一种考虑中断风险的鲁棒优化模型以最小化总保障成本。于冬梅等研究中断情境下的可靠性选址-分配组合优化问题，建立包含成本、服务质量以及最小覆盖水平的多目标数学模型，并应用NSGA-Ⅱ算法进行了求解。当前文献很少将仓库选址、需求分配及任务调度等决策进行组合优化，以获得全局最优解。

基于以上分析，并立足战时装备维修器材供应实际，将野战仓库选址、需求分配及任务调度等决策过程融合为ScheLoc问题。考虑野战仓库中断风险，构建基于情境的混合整数线性规划(MILP)模型。考虑问题模型的高度复杂性，设计一种基于逻辑的Benders分解算法(LBBD)对模型进行求解，并通过算例实验对模型和算法的性能进行验证分析。下面对本文中所研究的问题进行具体描述。

2 问题描述

考虑某次装备维修器材供应任务，需要在战场适当位置设立野战仓库，并完成对部队的器材供应。假设={1,2,…,}为经预先勘察研判，可作为野战仓库的待选位置集合(通常选择现有设施或场地)，其中最多选择个位置作为野战仓库。待选位置(∈)的坐标表示为(,)。在作战地域内，共有集合={1,2,…,}的部队需要进行器材补充。若部队的需求分配至仓库，则该部队派出运输车辆到达仓库开始装载，部队所需装载时间为，可综合器材需求量与仓库装载能力提前估算。定义部队至仓库的距离为，行车时间为。装载过程采用非抢占模式，各部队按照一定次序逐次装载。部队在仓库完成装载的时间记为。待所有部队器材装载均完成，则本次保障任务完成，定义保障任务完成时间为，即：=max,∀∈。

战时野战仓库受敌火力威胁，可能因遭敌打击等原因导致供应能力中断。若保障任务开始时，野战仓库处于中断状态，则无法进行器材供应，需待中断排除后恢复正常，定义野战仓库的中断风险为，中断排除时间为。

根据以上描述，构建考虑中断风险的器材供应组合优化模型，目标函数为期望保障完成时间的最小化。

3 模型构建

(1)

为构建基于中断情境的MILP模型，首先对模型进行如下假设：

1) 中断概率可通过战场位置、历史数据和仿真推演等方式估算；

2) 待选仓库和部队配属位置已知；

3) 不考虑野战仓库器材短缺问题;

4) 不考虑仓库中断对人员、器材的损伤，抢修完毕后完全恢复供应能力；

5) 不考虑中断情境下器材需求的重分配。

同时，定义以下变量：

：=1表示在待选位置处开设野战仓库，否则为0；

：=1表示部队分配在仓库装载，否则为0；

：一个足够大的正整数。

基于以上假设和定义，构建MILP模型(记为P)如下：

(2)

(3)

(4)

(5)

≤∀∈,∈

(6)

(7)

(8)

(9)

(10)

(11)

∈{0,1} ∀∈

(12)

∈{0,1} ∀∈,∈

(13)

(14)

其中：式(2)表示目标函数为期望保障完成时间的最小化；约束式(3)表示最多开设个野战仓库；约束式(4)表示任一部队器材仅由一个野战仓库供应；约束式(5)和式(6)表示部队需求仅能分配至开设野战仓库的位置；约束式(7)表示情境下，部队的保障完成时间，至少为部队至野战仓库的行车时间，与器材装载时间之和，且若野战仓库发生中断，需待中断排除后，才能派出运输车辆；约束式(8)～式(9)为部队装载次序约束，即：在情境下，若部队、均分配至仓库，且部队在部队之前，则部队的装载完成时间，至少是部队的完成时间，加上部队装载时间；约束式(10)为保障完成时间的计算方式；约束式(11)～式(14)为相关变量的域。

4 算法设计

本文中所研究的选址调度组合优化问题，融合了选址问题和并行机调度问题两类经典优化问题，属于NP难问题。同时，考虑中断情境后，问题求解更加困难，需要开发高效的算法进行求解。因此，设计一种基于逻辑的Benders分解(LBBD)算法，采用“分解、迭代、切割”的求解模式，降低问题复杂度，实现精确、高效求解。

LBBD算法由Hooker等提出，近年来广泛应用于求解复杂组合优化问题。LBBD的基本原理是将原问题分解为一个主问题和一个或多个子问题。主问题将原问题中复杂变量固定，作为松弛问题，求解后形成原问题的下界，并将解传递至子问题。基于主问题的解，子问题对原问题进行进一步求解，获得原问题的整体解，作为上界。子问题求解过程中生成Benders切割，添加至主问题，该过程反复迭代，直至获得最优解或满足其他停止条件，并输出最终解。Benders切割分为可行性切割和最优性切割。若传到子问题的解无法求得可行解，则生成可行性切割，使该解在后续迭代中不再出现；若有可行解，则在子问题求解后形成最优性切割，并添加至主问题。LBBD算法求解流程如图1所示。

图1 LBBD算法求解流程框图

本文中研究的考虑中断风险的装备维修器材供应组合优化问题，其决策内容包括野战仓库选址、部队需求分配以及各仓库的保障次序确定，以实现中断情境下期望保障完成时间的最小化。主问题中，将各仓库的保障次序变量松弛，仅求解仓库选址和部队需求分配。主问题求解完成后，将相关变量的解传至子问题，转化成中断情境下各个仓库处的供应次序确定问题，以最小化各仓库保障完成时间。下面分别对主问题、子问题及Benders切割进行叙述。

4.1 主问题

根据以上描述，主问题包括野战仓库选址和需求分配2个决策环节，在目标函数中将期望保障完成时间松弛，以ψ为期望保障完成时间的下界。由此构建主问题模型如下：

min

(15)

s.t. (3)～(6),(12),(13),and

≥0 ∀∈,∈

(16)

∀∈,∈,∈

(17)

其中，目标函数式(15)为期望保障完成时间下界的最小化。约束表达式(16)表示为非负数。式(17)即为子问题求解后生成的Benders切割。以上为主问题的基本形式，解的下界较弱，因此，需要对提出有效不等式进行强化。

4.2 有效不等式

根据问题结构，提出以下有效不等式：

(18)

(19)

(20)

不等式(18)表示期望保障完成时间不小于所有仓库在各情境下的保障完成时间与情境概率的加权和。不等式(19)相当于约束表达式(7)与约束表达式(10)的综合。不等式(20)表示情境下的保障完成时间，不小于此情境下任一仓库处的保障完成时间，不等式右侧为情境下仓库处保障完成时间的下界。

4.3 子问题

(21)

(22)

(23)

(24)

约束表达式(22)表示在装载次序上，部队不可能既是部队的紧前对象，又是部队的紧后对象。约束表达式(23)为部队的装载次序约束，相当于约束表达式(8)和表达式(9)。约束表达式(24)等价与约束表达式(7)。

从运筹学角度，该问题为典型的以makespan最小化为目标的单机调度问题，复杂度较低，能够在多项式时间内获得最优解，因此采用基于ERD原则的求解方法，即：按照行车时间降序的方式对所分配部队进行排序，以确定保障完成时间。

4.4 Benders切割

(25)

5 数值实验

为验证所提出的模型和算法的可行性和求解性能，本节生成40个不同规模的算例进行计算实验。本文中所提出的模型P和LBBD算法，均通过 C++链接求解器Cplex12.10编程实现，每个算例的求解时限设置为600 s。运行环境为Intel Xeon CPU E5-2690 v3，2.60 GHz，32 GB RAM。下面首先简要介绍算例生成方式，随后进行结果分析。

5.1 算例生成

假设保障部门拟为某方向200×200(单位：公里)范围的地域内的作战部队提供器材供应保障。该地域内部署的部队数={10,20,…,100}，待选位置数={4,6,8,10}，野战仓库数=2。每组和值的组合共构成40个算例。

每个算例中，部队坐标在[1,200]内随机分布，器材装载时间在{0.5,1,…,3}内随机取值(单位：小时)。仓库待选位置在横坐标[1,200]，纵坐标[1,100]范围内随机分布。所有距离均采用欧式距离计算，并向上取整。部队运输车辆行车速度设为60()，仓库中断概率在[10,30]内随机分布。考虑中断事件的严重性不同，将导致中断恢复时间不同，设中断恢复时间为{2,4,8}内的随机值(单位：小时)。

5.2 算法性能分析

针对以上算例，分别对模型P利用求解器直接求解(以下简称模型P)和利用LBBD求解2种方式进行计算和分析。其中，模型P利用C++链接求解器CPLEX进行计算，其内核算法为分支切割算法(Branch and Cut,B&C)。2种方法计算结果见表1所示，其中No.、、分别表示算例编号、部队数、待选位置数，P、LBBD、(P-L)%分别表示模型P和算法LBBD求得的目标函数值，以及P对LBBD的差值百分数。符号“—”表示该方法未能求得可行解。

表1 算例计算结果

从表1可以看出，在40个算例中，模型P共求得33个可行解，LBBD对40个算例均能求解。当算例规模较小时，P和LBBD表现相当，如算例1、2、5中2种方法解的差值均在5%以内。但当算例规模变大时，模型P的性能相较于LBBD迅速下降。当≥40时，二者差值均大于45%，部分算例超过70%。这一结果表明本文中所研究的问题具有较高的复杂度，同时也表明LBBD算法具有良好的求解性能，在规定时间内能够获得更好的解。同时，可以观察到，在部队数相同的情况下，模型P的解的质量随待选数量增大而迅速下降。如=30的算例中，LBBD的目标值随值增加而降低，其原因在于随着值增加，仓库数量随之增加(=2)，分配至同一仓库的部队数减少，因此，保障完成时间缩短。但模型P的目标函数值随值增大而增大，当从4增加至6时，模型P目标值从33.22增加至57.69。说明解的质量显著降低。其原因在于，值的增大使得情境数||呈指数增加，大大提高了模型的复杂度，导致求解难度增大。而当算例规模继续增大时，模型P无法在规定时间内给出部分算例的可行解。

同时，为了证明组合优化方法的优越性，本节设计一种传统分阶段求解方法(记为SH)与LBBD算法进行计算对比。SH算法的原理为：第一阶段选取距所有部队总距离最近的个待选位置为野战仓库，第二阶段将部队需求分配至各仓库，使得所有部队与所分配仓库的总距离最短。第三阶段在各情境下，依据ERD原则进行保障次序确定。SH是一种分阶段的启发式算法，其计算结果与LBBD的对比见表2，其中(S-L)%为二者差值百分比。值得注意的是，该表中每个目标函数值为同一部队数的4个算例解的平均值。

从表2可以看出，LBBD算法在所有规模的算例中，解的质量均明显好于SH，其差值百分比的平均值为27.95%。表明相对于分阶段求解，采用组合优化能够显著提高解的质量。