曹軍海，張闖，李延通，郭一鳴，郭慶義

(1.陸軍裝甲兵學(xué)院 裝備保障與再制造系，北京 100072；2.大連海事大學(xué) 航運經(jīng)濟與管理學(xué)院，遼寧 大連 116026；3.65316部隊，遼寧 大連 116300)

0 引言

裝備維修器材的預(yù)儲預(yù)置，是保障作戰(zhàn)部隊在戰(zhàn)爭初期快速獲得器材供應(yīng)的重要手段，是提高裝備維修器材保障效率和部隊持續(xù)戰(zhàn)斗力的關(guān)鍵之一。美軍在海灣戰(zhàn)爭、伊拉克戰(zhàn)爭等21世紀(jì)以來的幾次局部戰(zhàn)爭中，通過海上、陸上等預(yù)儲預(yù)置力量，實現(xiàn)了裝備和物資的快速部署，促進了部隊?wèi)?zhàn)斗力的快速生成，對后續(xù)作戰(zhàn)行動起到了促進作用[1]。當(dāng)前，我國陸軍正在進行深刻改革，從區(qū)域防衛(wèi)型向全域機動型轉(zhuǎn)變。面對當(dāng)前我周邊復(fù)雜備戰(zhàn)形勢，有必要在主要戰(zhàn)略方向預(yù)先配置一定規(guī)模的裝備維修器材，避免保障任務(wù)初期出現(xiàn)保障難、保障慢的問題，提高戰(zhàn)時部隊部署效率，快速形成戰(zhàn)斗力和保障力。

針對戰(zhàn)時預(yù)置儲備問題，一些學(xué)者已經(jīng)進行了研究。林勇等[2]對美國陸軍預(yù)置儲備情況進行系統(tǒng)梳理，并結(jié)合我國陸軍實際提出了建設(shè)啟示。李守耕等[3]分別對邊境地區(qū)、島礁、海外基地和海上艦船4種戰(zhàn)備物資預(yù)置方式進行研究，并提出可行方案。王耀等[4]針對島嶼、邊境和海外等3種作戰(zhàn)環(huán)境下后勤戰(zhàn)備物資預(yù)置儲備進行總體設(shè)計。在戰(zhàn)時軍事物流的文獻中，張巍等[5]研究了戰(zhàn)時前沿補給基地的選址問題。王申坪等[6]針對戰(zhàn)時裝備倉庫選址問題，提出了基于兩階段的廣義最大覆蓋模型，并針對某次演習(xí)任務(wù)中裝備倉庫的選址進行了仿真分析。呂游等[7]研究了戰(zhàn)時物流配送路徑規(guī)劃問題，姜大立等[8]對戰(zhàn)時不確定環(huán)境下的軍事運輸動態(tài)路徑規(guī)劃問題進行了研究。

從當(dāng)前已有文獻來看，一方面，對裝備物資預(yù)置儲備的文獻大多集中于總體設(shè)計和方案研究，少有對主要戰(zhàn)略方向預(yù)儲點選擇和戰(zhàn)前裝備物資快速預(yù)置等問題的優(yōu)化方法研究。另一方面，戰(zhàn)時軍事物流的文獻中，大多研究裝備物資倉庫或基地的選址問題，或運輸配送問題，而很少將二者作為一個問題同時考慮。事實上，設(shè)施(倉庫)選址和基于設(shè)施位置的運輸配送二者緊密相關(guān)，設(shè)施選址是運輸配送的前提和基礎(chǔ)，后期運輸配送是設(shè)施選址的目的和后續(xù)。傳統(tǒng)的優(yōu)化方法將二者作為獨立問題分別研究，首先確定設(shè)施選址方案，當(dāng)預(yù)置任務(wù)開始時，基于前期選址確定的設(shè)施位置，進行需求分配和運輸保障。這種模式無法保證其方案的全局最優(yōu)，與信息化戰(zhàn)爭中對裝備器材保障的精確、高效等需求不相適應(yīng)。為了獲得全局最優(yōu)的保障方案，需要將二者進行有效融合，形成一類復(fù)雜的組合優(yōu)化問題——選址調(diào)度問題(ScheLoc)。

ScheLoc問題是近年來廣受關(guān)注的一類組合優(yōu)化問題，最早由Hennes等[9]于2002年提出。ScheLoc問題有效融合了設(shè)施選址和機器調(diào)度兩類經(jīng)典運籌優(yōu)化問題，其決策環(huán)節(jié)主要包括設(shè)施的選址、設(shè)施和需求的分配以及各設(shè)施對所分配需求的服務(wù)次序等。按照設(shè)施數(shù)量，ScheLoc問題分為單機ScheLoc問題(即只有一個設(shè)施)[10-11]和并行機ScheLoc問題[12-13]；按照選址類型可分為平面ScheLoc問題(即在一定范圍內(nèi)任意位置選址)[14]和離散ScheLoc問題(在指定待選位置集內(nèi)選址)[15]。近年來，一些學(xué)者還就不確定環(huán)境下的ScheLoc問題進行了研究，形成了一些有意義的研究成果[16-17]。在現(xiàn)實生產(chǎn)生活中，ScheLoc問題被廣泛應(yīng)用在港口管理[18]、礦石開采[19]、物流配送中心規(guī)劃[20]等問題的優(yōu)化中。目前ScheLoc問題在軍事中的研究較少，Wesolkowski等[21]針對軍事訓(xùn)練設(shè)施的選址和參訓(xùn)部隊的訓(xùn)練規(guī)劃進行了研究，以多種成本目標(biāo)及總訓(xùn)練時間的最小化為目標(biāo)，構(gòu)建了雙目標(biāo)模型，并利用NSGA-Ⅱ算法進行了求解。值得注意的是，本文僅研究訓(xùn)練設(shè)施選址和參訓(xùn)部隊分配兩階段問題，未對各部隊訓(xùn)練次序進行規(guī)劃。而本文所研究的預(yù)儲點選址與預(yù)置運輸配送組合優(yōu)化，將預(yù)置運輸配送次序納入研究范圍，形成更完整的優(yōu)化方案。

因此，本文針對裝備維修器材預(yù)儲預(yù)置問題，將預(yù)儲點選址和戰(zhàn)前裝備維修器材預(yù)置融合為ScheLoc組合優(yōu)化問題，決策環(huán)節(jié)包括裝備維修器材預(yù)儲點的選擇、器材使用部隊(即需求點)與預(yù)儲點的分配關(guān)系，以及各預(yù)儲點進行器材預(yù)置時的保障次序，屬于離散并行機ScheLoc問題。通過考慮預(yù)儲點開設(shè)成本、運輸成本以及保障延誤懲罰成本等目標(biāo)，構(gòu)建混合整數(shù)規(guī)劃模型，并開發(fā)高效的求解算法，獲得全局最優(yōu)的器材預(yù)儲預(yù)置方案，保證在作戰(zhàn)任務(wù)開始前快速完成裝備維修器材的部署，保障部隊作戰(zhàn)任務(wù)的開展。

1 問題描述

本文考慮在某戰(zhàn)略方向上，擬于適宜進行裝備維修器材預(yù)儲的待選位置集合中(通常選用現(xiàn)有裝備維修器材倉庫或其他已有設(shè)施場地)，選擇并設(shè)立若干預(yù)儲點進行裝備維修器材的預(yù)先儲存，并在戰(zhàn)爭開始前，按照部隊部署情況及時將器材預(yù)置至指定位置。具體過程可描述如下：

考慮某次實戰(zhàn)化演練中，保障部門擬在經(jīng)勘查評估確定的l個備選位置中，最多選擇開發(fā)m個預(yù)儲點，記預(yù)儲點備選位置集合K={1,2,…,l}為預(yù)儲點備選位置集合，要在其中選擇開設(shè)m個預(yù)儲點。對位置k(k∈K)，其坐標(biāo)為(Xk,Yk)，開設(shè)固定成本為ck，器材存儲上限為Qk，部署運輸車隊編組集合為Bk={1,2,…,b,…,|Bk|}，負(fù)責(zé)器材的運輸和預(yù)置。車隊編組b以整車隊形式獨立執(zhí)行任務(wù)，不與其他編組進行車輛借調(diào)。假設(shè)本地域即將部署n個作戰(zhàn)部隊，構(gòu)成部隊集合為J={1,2,…,n}，每個部隊j(j∈J)的坐標(biāo)表示為(Xj,Yj)，根據(jù)作戰(zhàn)計劃，其對裝備維修器材的需求量為pj。在預(yù)置任務(wù)開始前，需要解決部隊器材需求和預(yù)儲點的分配，以及預(yù)儲點對各部隊預(yù)置器材的先后次序。當(dāng)部隊j的需求分配至預(yù)儲點k時，由該預(yù)儲點的車隊b將器材從預(yù)儲點k運送至部隊j的部署位置，完成預(yù)置后立刻返回，執(zhí)行下一次運送任務(wù)。假設(shè)每個車隊單次只運送一個部隊的器材，且該部隊的需求量能夠被車隊一次性保障完畢，其單程運送時間rjk和運輸成本ejk與部隊j與預(yù)儲點k之間的距離gjk有關(guān)，表示為rjk=gjk/s，ejk=egjk，其中s和e分別表示行車速度和單位距離運輸成本，本文均假設(shè)為定值。由于不同部隊擔(dān)負(fù)的任務(wù)不同，其對于器材需求的迫切程度也不同，假設(shè)部隊j的期望到達時間為dj。若在該期限內(nèi)未能到達，將產(chǎn)生延誤時間，同時將影響部隊后續(xù)任務(wù)的開展，因此必須承擔(dān)一定的延誤懲罰成本。記Cj為部隊j的器材到達預(yù)定地域的時間，即保障完成時間，Tj為延誤時間，則Tj=max(Cj-dj,0)。定義qj為部隊j的單位時間延誤懲罰成本。本文的決策內(nèi)容包括預(yù)儲點的選擇、部隊與預(yù)儲點的分配關(guān)系建立，以及預(yù)儲點運送器材的先后順序。為兼顧軍事效益與經(jīng)濟效益，本文優(yōu)化目標(biāo)為預(yù)儲點總固定費用、總運輸成本以及總延誤懲罰成本的加權(quán)和最小，三者的權(quán)重分別表示為θ1、θ2、θ3。

2 模型構(gòu)建

根據(jù)第1節(jié)的問題描述，為構(gòu)造混合整數(shù)規(guī)劃模型，首先對問題進行如下假設(shè)：

1)預(yù)儲點固定開設(shè)成本可知；

2)戰(zhàn)時裝備維修器材采用基數(shù)化存儲，器材量單位為基數(shù)，且不區(qū)分器材品種；

3)戰(zhàn)時裝備維修器材采用集裝化運輸和機械化裝卸，其裝載、卸載時間忽略不計。

同時，定義如下決策變量：

wk=1，表示備選點k被選為預(yù)儲點，否則為0；

vjkb=1，表示部隊j由預(yù)儲點k的車隊b保障，否則為0；

xij=1，表示部隊j的保障次序在部隊i之后(無需相鄰)，否則為0。

由以上問題假設(shè)及變量定義，構(gòu)建混合整數(shù)規(guī)劃模型，記為P，其表示方式如下：

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

Cj≥Ci+rik+rjk-L(3-xij-vjkb-vikb)

(7)

Ci≥Cj+rik+rjk-L(2+xij-vjkb-vikb)

(8)

Tj≥Cj-dj

(9)

Tj≥0

(10)

wk∈{0,1}

(11)

vjkb∈{0,1}

(12)

xij∈{0,1}

(13)

3 算法設(shè)計

本文問題是設(shè)施選址和并行機調(diào)度兩類問題的組合優(yōu)化，設(shè)施選址和并行機調(diào)度問題已被證明均屬于NP-難問題[22-23]，因此本文研究的問題也屬于NP-難問題。組合優(yōu)化使得問題能夠獲得全局最優(yōu)解的同時，也極大地增加了模型的復(fù)雜度和求解難度，需要設(shè)計高效算法進行求解。針對該問題，本文首先生成一種基于邏輯的Benders分解(LBBD)算法，該算法是一種精確算法，在求解復(fù)雜的組合優(yōu)化問題時性能較好。同時，為了對比組合優(yōu)化與傳統(tǒng)優(yōu)化方法的表現(xiàn)，還構(gòu)造了一種序貫式優(yōu)化(SH)算法。以下對兩種算法的原理和流程分別進行介紹。

3.1 基于邏輯的Benders分解

LBBD算法是一種基于松弛分解、迭代切割的精確算法。首先，經(jīng)典Benders分解算法由Benders于1962年提出[24]，其基本原理為：將原問題中的復(fù)雜變量固定松弛，分解為一個主問題和一個子問題，主問題為原問題的松弛問題，其計算結(jié)果構(gòu)成原問題的下界(LB)，主問題求解完成后將解傳至子問題，求解形成原問題的上界(UB)，子問題求解后生成Benders切割，并添加至下一迭代的主問題中，以提高問題下界。由此反復(fù)迭代，直至求得最優(yōu)解(LB=UB)，或到達最大計算時限。經(jīng)典Benders分解算法中，子問題形式被限定為線性規(guī)劃問題，限制了該算法的應(yīng)用范圍。21世紀(jì)初，Hooker等[25]將經(jīng)典Benders分解算法擴展，形成基于邏輯的Benders分解(LBBD)算法，其子問題可為任意優(yōu)化問題。LBBD算法自提出以來，在組合優(yōu)化問題的求解中展現(xiàn)出了顯著優(yōu)勢，在機器調(diào)度[26]、路徑規(guī)劃[27]以及醫(yī)院手術(shù)室調(diào)度[28]等問題中得到了成功應(yīng)用。

對模型P，首先將目標(biāo)函數(shù)中保障延誤懲罰成本松弛，形成的主問題主要解決預(yù)儲點選址和部隊器材需求與預(yù)儲點的分配兩個決策問題，當(dāng)以上決策變量求解并固定后，子問題則變?yōu)榍蠼庖幌盗袉螜C調(diào)度問題，以在各車隊上最小化完成所有保障任務(wù)出現(xiàn)的延誤懲罰成本。隨后，子問題生成Benders切割，并添加至下一迭代中的主問題。值得注意的是，Benders切割可分為可行性切割和最優(yōu)性切割，但在本文問題中，子問題求解時總存在可行解，因此本文所生成的Benders切割均為最優(yōu)性切割。下面對主問題、子問題以及Benders切割的表示進行詳細(xì)描述。

3.1.1 主問題

為表示主問題，定義ψ為目標(biāo)函數(shù)中總延誤懲罰成本的下界，將該部分以及對應(yīng)的器材運送次序決策環(huán)節(jié)松弛，使得主問題成為研究預(yù)儲點選址、部隊與預(yù)儲點分配的松弛問題，松弛后的主問題表示為

(14)

s.t.

(2)式～(5)式，(11)式，(12)式，及

CUTS

(15)

此時，目標(biāo)函數(shù)(14)式表示預(yù)儲點固定成本、運輸成本及總延誤懲罰成本下界的加權(quán)和。約束(15)式的CUTS即表示迭代過程中產(chǎn)生并添加至主問題的Benders切割。此時，由于對問題進行了松弛，ψ下界較差，使得主問題質(zhì)量較差，需要根據(jù)問題結(jié)構(gòu)特點提出有效不等式，對主問題進行加強。

3.1.2 有效不等式

(16)

(17)

(18)

(19)

Φkb≥0

(20)

Tj≥0

(21)

(16)式表明總延誤懲罰成本不小于所有預(yù)儲點的車隊的延誤懲罰成本之和；(17)式表示總延誤懲罰成本不小于所有部隊各自延誤懲罰成本之和；(18)式表示各運輸車隊的延誤懲罰成本，不低于最小單位延誤時間懲罰成本與最小延誤時間的乘積，其中，最小延誤時間以車隊保障最后一個部隊的最短用時與最大期望到達時間之間的差；(19)式表示部隊j的延誤時間不小于該部隊與所所分配的預(yù)置點之間的距離與期望到達時間的差，即部隊j為車隊的第一個保障對象。

3.1.3 子問題

當(dāng)主問題求解完畢后，預(yù)儲點選址變量wk、分配變量vjkb等的值得以確定，此時子問題則變?yōu)榍蠼庖幌盗袉螜C調(diào)度問題，即在各預(yù)儲點位置上被分配有器材預(yù)置任務(wù)的車隊，其保障次序的確定，目標(biāo)為最小化該車隊產(chǎn)生的總保障延誤懲罰成本。定義集合Jkb為預(yù)儲點k中車隊b所承擔(dān)的部隊器材預(yù)置任務(wù)，即Jkb={j|vjkb=1,?j∈J}。定義變量zij表示部隊i和j的保障次序相鄰，且i在j之前。則對預(yù)儲點k中車隊b的子問題可表示為

(22)

s.t.

zij+zji≤1

(23)

Cj≥Ci+rik+rjk-L(1-zij)

(24)

Cj≥rjk

(25)

Tj≥Cj-dj

(26)

Tj≥0

(27)

zij∈{0,1}

(28)

目標(biāo)函數(shù)(22)式表示在預(yù)儲點k中車隊b處的總延誤懲罰成本最小化；約束(23)式表示兩部隊i和j的保障次序關(guān)系，即部隊i不可能同時既是部隊j的前一保障對象又是部隊j的后一保障對象；約束(24)式～(27)式與對應(yīng)前述約束(7)式～(10)式；約束(28)式為變量zij的域。

根據(jù)Graham等[29]提出的三段分類法，此處所描述的子問題可表示為1‖∑qjTj。該問題已經(jīng)被證明為強NP難問題。當(dāng)前對1‖∑qjTj問題的求解已有較多文獻，其中精確算法包括分支定界、動態(tài)規(guī)劃、列生成等。經(jīng)過前期試驗，由Tanaka等[30]提出的基于動態(tài)規(guī)劃的精確方法具有良好的性能。該方法基于提出的Ibaraki等[31]提出的SSPD算法，通過多種改進策略，解決了SSPD算法內(nèi)存使用大、計算效率低等問題，經(jīng)過數(shù)值實驗，這種基于動態(tài)規(guī)劃的方法能夠在合理時間內(nèi)求解工件數(shù)量(即本文中的部隊數(shù))達300的無空閑時間的單機調(diào)度加權(quán)延誤時間最小化問題。因此，本文應(yīng)用Tanaka等的動態(tài)規(guī)劃方法對子問題進行求解，并基于子問題的結(jié)果生成Benders切割。

3.1.4 Benders切割

(29)

3.2 傳統(tǒng)序貫式算法

為比較組合優(yōu)化方法與傳統(tǒng)優(yōu)化方法的性能，本節(jié)構(gòu)造一種序貫式優(yōu)化方法(記作SH)，通過兩個階段依次對問題進行求解，即：先以預(yù)儲點開設(shè)固定成本和運輸成本最小化為目標(biāo)，求解預(yù)儲點選址和部隊需求分配問題。第一階段完成后，第二階段轉(zhuǎn)化為針對承擔(dān)預(yù)置任務(wù)的各運輸車隊單機調(diào)度問題，優(yōu)化目標(biāo)為總延誤懲罰成本最小化。為了保證算法的性能，兩階段分別使用精確方法進行求解。下面分別對各階段的求解方法進行詳細(xì)描述。

3.2.1 第一階段

本階段以預(yù)儲點固定成本和運輸成本最小化為目標(biāo)，構(gòu)造MILP模型如下：

(30)

s.t.

(2)式～(5)式，(11)式，(12)式

3.2.2 第二階段

第一階段求解完成后，選址變量wk和分配變量vjkb得以固定，此時第二階段轉(zhuǎn)化為一系列求最小延誤懲罰成本的單機調(diào)度問題。該問題與3.1.3節(jié)類似，為提高后期數(shù)值實驗計算結(jié)果對比的可信度，本階段采用與4.3節(jié)相同的求解方法，即Tanaka等[30]的基于動態(tài)規(guī)劃的精確求解方法。

4 數(shù)值實驗

為評估本文所提出的模型和算法的性能，隨機生成160個算例對模型P及算法LBBD和SH進行測試實驗，首先對算例的生成規(guī)則進行簡要介紹，隨后對實驗結(jié)果進行匯總和分析。

4.1 算例生成

本文所提出的模型P、算法LBBD和SH，均通過C++鏈接求解器Cplex12.10編程實現(xiàn)，其中模型P利用CPLEX求解器直接求解時，其內(nèi)核算法為分支切割算法。每個算例的求解時限設(shè)置為600 s。運行環(huán)境為Intel Xeon CPU E5-2690 v3，2.60 GHz，32 GB RAM。為更好地對計算結(jié)果進行分析，將該部分算例分為3組，分別是常規(guī)算例組(20≤n≤60)、大算例組(80≤n≤120)和超大算例組(140≤n≤200)。下面分別對各組算例的計算結(jié)果進行分析。

4.2 常規(guī)算例組結(jié)果

常規(guī)算例組的計算結(jié)果如表1所示，表格中前4列表示算例相關(guān)參數(shù)，分別為部隊數(shù)n，待選位置數(shù)l，預(yù)儲點數(shù)m，以及各預(yù)置點運輸車隊數(shù)b。中間3列表示各模型和算法的求解質(zhì)量，用上界UB和下界LB的差值百分比Gap(%)度量，其計算方式可表示為

(31)

值得注意的是，SH是一種兩階段序貫式優(yōu)化方法，無法準(zhǔn)確獲得整個問題的有效下界，因此其下界采用模型P和算法LBBD所生成的最好下界，并利用其自身上界求得算法SH的Gap值。由于本節(jié)所生成的算例考慮TF和R值不同，每種規(guī)模的算例共有4個具有不同期望到達時間的算例，因此表1中各算例數(shù)值為4個算例的平均值。最后一行括號內(nèi)數(shù)字代表該組取得最優(yōu)解(Gap=0)的算例的數(shù)量。表格右側(cè)3列為各算例的計算時間。

從表1中可以看出，在常規(guī)算例組的實驗中，本文所提出的模型P和算法LBBD均取得了良好的求解效果，LBBD算法獲得了最多得最優(yōu)解，為28個，模型P得到27個最優(yōu)解，略低于LBBD，而算法SH僅有2個最優(yōu)解。LBBD算法的平均Gap值為3.10%，在三者中表現(xiàn)最好，模型P的Gap值為3.71%，高于LBBD算法，但明顯好于SH算法的25.69%。從求解效率上看，LBBD同樣表現(xiàn)最好，其平均計算時間為262.77 s，模型P的平均計算時間為279.99 s。SH由于采用序貫式優(yōu)化方法，其問題復(fù)雜度低，平均求解時間不到1 s，但同時解的質(zhì)量較差。

從表1中還可以觀察到，對模型P和算法LBBD，總體上看，其運輸車隊數(shù)量越多，解的質(zhì)量越好。從表1中可以統(tǒng)計發(fā)現(xiàn)：在該組算例中，當(dāng)車隊數(shù)量為3時，模型P平均Gap為4.53%，算法LBBD的平均Gap值為3.71%；當(dāng)車隊數(shù)量為5時，二者分別降為2.95%和2.49%，降幅均超過30%。其可能的原因為：在同等算例規(guī)模下，當(dāng)車隊數(shù)量較少時，每個車隊將分配更多需求，由于以加權(quán)延誤時間最小化為目標(biāo)的單機調(diào)度問題為NP難問題，其求解復(fù)雜度高，可能造成求解質(zhì)量相對較低。

表1 常規(guī)算例組計算結(jié)果

4.3 大算例組結(jié)果

大算例組為部隊數(shù)量為80～120的算例，計算結(jié)果如表2所示。從表2中可以看出，大算例組的求解難度相對于常規(guī)算例組有所增大，模型P的表現(xiàn)出現(xiàn)明顯下降。從求解質(zhì)量上看，模型P共取得15個最優(yōu)解，其平均Gap值為19.78%，平均用時為493.27 s。LBBD算法得到27個最優(yōu)解，其平均Gap為5.32%，平均計算時間為263.04 s，明顯優(yōu)于模型P。SH的計算效率仍最高，平均計算時間在 1 s 以內(nèi)，但其求解質(zhì)量相對較差，其平均Gap高達21.11%，共獲得12個最優(yōu)解。

表2 大算例組計算結(jié)果

4.4 超大算例組結(jié)果

為進一步評價和探索模型P及算法LBBD、SH的性能，本文對超大規(guī)模算例進行了實驗，該組64個算例中，部隊數(shù)n={140,160,…,200}。即：決策者要對某戰(zhàn)略方向上最高達200個裝備維修器材預(yù)置任務(wù)進行預(yù)儲點選擇和預(yù)置方案決策，計算結(jié)果如表3所示。

針對表3中的計算結(jié)果，從求解質(zhì)量上看，算法LBBD的表現(xiàn)相比模型P和算法SH具有明顯優(yōu)勢。在64個算例中，LBBD共求得34個最優(yōu)解，其平均Gap值為8.00%。SH獲得18個最優(yōu)解，其平均Gap值為23.11%。模型P隨著算例規(guī)模的增加，表現(xiàn)顯著下降，在超大規(guī)模算例中性能最差，僅在n=140的算例中獲得2個最優(yōu)解，平均Gap值達到80.21%，遠高于算法LBBD和SH。在n=180的算例中，模型P的平均Gap值均在85%以上，而當(dāng)n=200時，平均Gap值均大于98%，此時模型P已基本失去優(yōu)化求解能力。從計算時間上看，模型P平均計算時間為596.39 s，接近計算時限600 s，算法LBBD的平均計算時間為289.83 s，相比表2中的263.04 s較穩(wěn)定，算法SH的平均計算時間只有1.4 s。

表3 超大算例組計算結(jié)果

從3組算例的計算結(jié)果來看，算法LBBD在3種方法中表現(xiàn)最好。在160個算例中，LBBD共求得89個最優(yōu)解，總平均Gap值為5.73%；算法SH獲得32個最優(yōu)解，其平均Gap值為23.29%；模型P獲得44個最優(yōu)解，平均Gap值為39.14%。當(dāng)算例規(guī)模增大時，模型P的性能下降明顯，在48個常規(guī)算例中，模型P求得27個最優(yōu)解，平均Gap值為3.74%，而在64個超大算例中，兩項數(shù)據(jù)分別變?yōu)?個和80.21%，說明在本文所研究的組合優(yōu)化問題具有較高的復(fù)雜性。而算法LBBD保持了良好的求解穩(wěn)定性，3組算例的平均Gap值分別為3.10%，5.32%和8.00%。在組合優(yōu)化LBBD算法與序貫式優(yōu)化方法SH算法的比較中，LBBD的求解質(zhì)量顯著高于SH，證明了組合優(yōu)化方法在獲得更高質(zhì)量解方面的優(yōu)勢。

同時，分析表1～表3的結(jié)果發(fā)現(xiàn)，算法SH求得的最優(yōu)解數(shù)量隨著算例規(guī)模的增大而增加，經(jīng)過分析發(fā)現(xiàn)，其原因主要與期望到達時間有關(guān)。因此，接下來對不同期望達到時間對問題求解的影響進行分析。

4.5 期望到達時間的影響

4.1節(jié)詳細(xì)介紹了期望到達時間的生成方法，其中參數(shù)TF的大小影響整體的松緊程度，即TF值越大，整體期望達到時間越短，表明戰(zhàn)爭的突發(fā)性越強，需要在最短時間內(nèi)完成器材預(yù)置；反之，整體期望達到時間越長，體現(xiàn)戰(zhàn)爭準(zhǔn)備時間較充裕。參數(shù)R的值反映了不同部隊對器材到達時間需求的差異性。R值越小，說明期望到達時間分布越集中，反之則越分散。本節(jié)對不同TF和R值組合下各模型和算法的表現(xiàn)進行分析，其結(jié)果如表4所示。值得注意的是，表4中每個結(jié)果均為40個算例結(jié)果的平均值，括號內(nèi)為取得的最優(yōu)解數(shù)量。

表4 期望到達時間的影響

從表4的結(jié)果來看，不同TF和R值的組合對各模型和算法的求解具有顯著影響。當(dāng)(TF,R)=(0.2,0.6)時，表明整體期望到達時間較長，且分布較散，即：戰(zhàn)爭準(zhǔn)備時間充足，各部隊需求緊迫性差異大，此時問題復(fù)雜度較低，因此各模型和算法表現(xiàn)較好。以算法LBBD為例，在該組的40個算例中，LBBD取得39個最優(yōu)解，平均Gap僅為0.02%，平均計算時間16.11 s，明顯好于在其他(TF,R)組合中的表現(xiàn)。在該組中，算法SH獲得24個最優(yōu)解。由于當(dāng)算例規(guī)模增大時，運輸成本在目標(biāo)函數(shù)中的比重上升，而該組延誤懲罰成本較低，使得SH獲得最優(yōu)解的能力上升。因此，在表1～表3中，算例規(guī)模越大，算法SH獲得的最優(yōu)解數(shù)量越多。當(dāng)(TF,R)=(0.6,0.2)時，表明戰(zhàn)爭準(zhǔn)備時間較短，且各部隊均面臨緊迫的裝備維修器材需求，此時問題求解難度最大。在各模型和算法中，LBBD算法表現(xiàn)最好，其平均Gap值為17.17%，明顯好于模型P的50.28%及算法SH的45.59%。

從動態(tài)角度看，當(dāng)TF值不變，R值由0.2增加至0.6時，表示各部隊期望到達時間由集中變得分散，此時各模型和算法獲得的最優(yōu)解數(shù)量增加，平均Gap值降低，平均計算時間縮短。以算法LBBD為例，TF=0.2情況下，當(dāng)R值由0.2變?yōu)?.6時，平均Gap值由0.17%降為0.02%，最優(yōu)解數(shù)量由34變?yōu)?9，平均計算時間由92.69 s縮短為16.11 s。當(dāng)R值不變、TF值增大時，表示整體期望到達時間縮短，從表4的數(shù)據(jù)來看，問題求解難度大大增加，各模型和算法的表現(xiàn)均有下降。以模型P為例，R=0.2情況下，當(dāng)TF值由0.2變?yōu)?.6時，平均Gap值由33.75%增至50.28%，最優(yōu)解數(shù)量由17變?yōu)?，平均計算時間由417.27 s變?yōu)?56.73 s。同時，從表4中結(jié)果可以總結(jié)發(fā)現(xiàn)，TF值變化所產(chǎn)生的影響遠大于R值變化的影響，即：戰(zhàn)爭準(zhǔn)備時間是否充足，是影響裝備維修器材預(yù)儲預(yù)置決策難度的主要因素。同時，決策者也應(yīng)關(guān)注不同部隊需求緊迫性之間的差異。

5 結(jié)論

本文研究了裝備維修器材預(yù)儲點選址與預(yù)置運輸及配送優(yōu)化方法，將預(yù)儲點選址與戰(zhàn)前器材預(yù)置融合為一類選址調(diào)度組合優(yōu)化問題，構(gòu)建以預(yù)儲點固定成本、運輸成本與保障延誤懲罰成本最小化為目標(biāo)的混合整數(shù)線性規(guī)劃模型，設(shè)計了一種基于邏輯的Benders分解算法(LBBD)和一種序貫式優(yōu)化方法SH，并基于160個隨機算例進行了數(shù)值實驗。得出以下主要結(jié)論：

1)該問題屬于NP難問題，對模型P直接求解時，其表現(xiàn)隨問題規(guī)模增加而顯著下降，需要開發(fā)高效的求解算法。

2)提出的LBBD算法獲得的最優(yōu)解數(shù)量最多，求解質(zhì)量最好。序貫式算法SH采用兩階段分別精確求解的優(yōu)化方法，其求解效率高，但求解質(zhì)量低。LBBD與SH算法的對比實驗證明組合優(yōu)化方法在獲得更高質(zhì)量解方面具有優(yōu)越性。

3)戰(zhàn)爭準(zhǔn)備時間以及不同部隊期望到達時間的差異性對問題的求解具有重要影響，進一步表明了裝備維修器材預(yù)儲預(yù)置的總要性。

下一步可針對考慮戰(zhàn)時不確定性和中斷風(fēng)險的裝備維修器材供應(yīng)保障優(yōu)化方法進行研究。