考慮中斷風險的裝備維修器材供應選址調度組合優化

張 闖，李延通，曹軍海，張 強，劉 毅

(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%。表明相對于分階段求解，采用組合優化能夠顯著提高解的質量。

表2 SH與LBBD算法結果

6 結論

1) 考慮中斷風險的器材供應選址調度組合優化問題屬于NP難問題，求解難度大；2) 本研究中提出的LBBD算法具有良好的求解性能，相比模型P，LBBD的求解能力和解的質量均有顯著優勢；3) 組合優化方法相比傳統的分階段求解方法，能夠獲得更好的全局解。

本研究還存在一些指標，需要下一步重點研究。一是中斷開始時間和持續時間的不確定性以及保障過程中出現中斷時對器材保障作業的影響。二是多種器材供應方式的影響。