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

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

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

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

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

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

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

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

2 问题描述

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

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

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

3 模型构建

由于中断事件的发生具有高度不确定性，因此模型采用基于情境集的模型构建方法，基于保障任务开始时仓库k的状态，形成所有的中断情境集S。定义参数

表示在情境s下，仓库k发生中断，且中断排除时间为

否则

记每个中断情境s∈S的概率为Ps。由以上描述，可知：

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

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

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

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

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

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

同时，定义以下变量：

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

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

表示情境s下部队i的保障次序在j之前，否则为0；

情境s下部队j的装载完成时间；

情境s下的保障完成时间；

M：一个足够大的正整数。

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

vjk≤wk ∀j∈J,k∈K

vjk∈{0,1} ∀j∈J,k∈K

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

4 算法设计

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

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

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

4.1 主问题

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

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

ψ≥0 ∀j∈J, s∈Ω

CUTs ∀j∈J, k∈K, s∈Ω

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

4.2 有效不等式

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

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

4.3 子问题

对添加有效不等式的主问题进行求解后，野战仓库选址和部队需求分配相关变量得以确定，则子问题变为各情境下，各仓库处的保障次序确定问题最小化其保障完成时间。定义集合Jk表示分配至仓库k处的部队集合，即：Jk={j|vjk=1,∀j∈J}。定义

表示情境s下，仓库k处的保障完成时间。定义辅助变量

表示情境s下，部队i与部队j相邻，且部队i的保障次序在部队j之前。则情境s下，在仓库k处的子问题(记为

可表示为：

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

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

4.4 Benders切割

根据以上分解过程，LBBD算法利用主问题求解仓库选址及部队分配问题，基于主问题的解，子问题决定所分配至各仓库的部队排序问题。因此，子问题总有可行解，不生成可行性切割，仅生成最优性切割。定义

表示子问题

求得的保障完成时间，则生成如下切割：

切割表达式(25)的原理为：在后续迭代过程中，若出现与集合Jk相同的分配方案时，则仓库k在情境s下的保障完成时间至少为

进而情境s下的总保障完成时间

成立，使得后期不再或难以再次获得该解。而当集合Jk中的任一部队被移除，即：∃j∈Jk,vjk=0，则切割表达式(25)右侧括号内结果为非正数，由于

因此切割表达式(25)失效，不会移除后续新的可行解。Benders切割生成后，将被添加至主问题，通过迭代的方式不断求解，直至获得全局最优解，或达到其他停止条件。

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(单位：公里)范围的地域内的作战部队提供器材供应保障。该地域内部署的部队数n={10,20,…,100}，待选位置数l={4,6,8,10}，野战仓库数m=l/2。每组n和l值的组合共构成40个算例。

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

5.2 算法性能分析

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

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

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

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

6 结论

1) 考虑中断风险的器材供应选址调度组合优化问题属于NP难问题，求解难度大；2) 本研究中提出的LBBD算法具有良好的求解性能，相比模型P，LBBD的求解能力和解的质量均有显著优势；3) 组合优化方法相比传统的分阶段求解方法，能够获得更好的全局解。

本研究还存在一些指标，需要下一步重点研究。一是中断开始时间和持续时间的不确定性以及保障过程中出现中断时对器材保障作业的影响。二是多种器材供应方式的影响。

[1] Esmaeili-Najafabadi E,Nezhad M,Pourmohammadi H,et al.A joint supplier selection and order allocation model with disruption risks in centralized supply chain[J].Computers & Industrial Engineering,2019,127:734-748.

[2] Sawik T.Integrated supply,production and distribution scheduling under disruption risks[J].Omega,2016,62:131-144.

[3] Rayat F,Musavi M M,Bozorgi-Amiri A.Bi-objective reliable location-inventory-routing problem with partial backordering under disruption risks:A modified AMOSA approach[J].Applied Soft Computing,2017,59:622-643.

[4] 孔繁辉,李健.供应中断风险下OEM供应链弹性运作与提升策略[J].中国管理科学,2018,26(2):152-159.

Kong F H,Li J.Resiliant operation and promotion strategy of OEM supply chain under supply disruption risk[J].Chinese Journal of Management Science,2018,26(02):152-159.

[5] 张莹.考虑中断风险的供应链优化模型和算法研究[D].北京:清华大学,2016.

Zhang Y.Optimization models and algorithms for supply chain under disruptions[D].Beijing:Tsinghua University,2016.

[6] Xu S,Zhang X,Feng L,et al.Disruption risks in supply chain management:A literature review based on bibliometric analysis[J].International Journal of Production Research,2020,58(11):3508-3526.

[7] Ivanov D,Dolgui A,Sokolov B,et al.Literature review on disruption recovery in the supply chain[J].International Journal of Production Research,2017,55(20):6158-6174.

[8] Snyder V L,Atan Z,Peng P,et al.OR/MS Models for Supply Chain Disruptions:A Review[J].IIE Transactions,2016,48(02):89-109.

[9] Krumke S O,Le H M.Robust absolute single machine makespan scheduling-location problem on trees[J].Operations Research Letters,2020,48(01):29-32.

[10] Elvikis D,Hamacher H W,Kalsch M T.Simultaneous scheduling and location(ScheLoc):The planar ScheLocmakespan problem[J].Journal of Scheduling,2009,12(04):361-374.

[11] Wang S,Wu R,Chu F,et al.An improved formulation and efficient heuristics for the discrete parallel-machine makespan ScheLoc problem[J].Computers & Industrial Engineering,2020,140:106238.

[12] Kramer R,Kramer A.An exact framework for the discrete parallel machine scheduling location problem[J].Computers & Operations Research,2021,132:105318.

[13] Filcek G,Józefczyk J, width=8,height=11,dpi=110

Awrynowicz M.An evolutionary algorithm for joint bi-criteria location-scheduling problem[J].International Journal of Industrial Engineering Computations,2021,12:159-176.

[14] Musavi M M,Bozorgi-Amiri A.A multi-objective sustainable hub location-scheduling problem for perishable food supply chain[J].Computers & Industrial Engineering,2017,113:766-778.

[15] Heßler C,Deghdak K.Discrete parallel machine makespanScheLoc problem[J].Journal of Combinatorial Optimization,2017,34:1159-1186.

[16] 王亚东,石全,陈材,等.考虑中断风险的备件供应选址-分配优化模型[J].兵工学报,2019,40(08):1708-1715.

Wang Y D,Shi Q,Chen C,et al.Location-allocation joint optimization model of spare parts supply under supply disruption risk[J].ActaArmamentarii,2019,40(08):1708-1715.

[17] 于冬梅,高雷阜,赵世杰.中断情境下可靠性应急设施选址-分配多目标优化模型[J].控制与决策,2020,35(06):1415-1420.

Yu D M,Gao L F,Zhao S J.A multi-objective optimization model for reliable emergency facility location-allocation under disruptions[J].Control and Decision,2020,35(06):1415-1420.

[18] Hooker J.N,Ottosson G.Logic-based Benders decomposition[J].Mathematical Programming,2003,96(01):33-60.

[19] Naderi B,Roshanaei V,Begen M A,et al.Increased surgical capacity without additional resources:Generalized operating room planning and scheduling[J].Production and Operations Management,2021,30(08):2608-2635.

[20] Roshanaei V,Booth K,Aleman D M,et al.Branch-and-check methods for multi-level operating room planning and scheduling[J].International Journal of Production Economics,2020,220:107433.

[21] Fachini R F,Armentano V A.Logic-based Benders decomposition for the heterogeneous fixed fleet vehicle routing problem with time windows[J].Computers & Industrial Engineering,2020,48:106641.