裝備維修器材預(yù)儲(chǔ)點(diǎn)選址與預(yù)置運(yùn)輸配送組合優(yōu)化方法

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

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

0 引言

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

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

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

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

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

1 問題描述

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

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

2 模型構(gòu)建

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

1)預(yù)儲(chǔ)點(diǎn)固定開設(shè)成本可知；

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

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

同時(shí)，定義如下決策變量：

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

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

xij=1，表示部隊(duì)j的保障次序在部隊(duì)i之后(無(wú)需相鄰)，否則為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è)計(jì)

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

3.1 基于邏輯的Benders分解

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

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

3.1.1 主問題

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

(14)

s.t.

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

CUTS

(15)

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

3.1.2 有效不等式

(16)

(17)

(18)

(19)

Φkb≥0

(20)

Tj≥0

(21)

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

3.1.3 子問題

當(dāng)主問題求解完畢后，預(yù)儲(chǔ)點(diǎn)選址變量wk、分配變量vjkb等的值得以確定，此時(shí)子問題則變?yōu)榍蠼庖幌盗袉螜C(jī)調(diào)度問題，即在各預(yù)儲(chǔ)點(diǎn)位置上被分配有器材預(yù)置任務(wù)的車隊(duì)，其保障次序的確定，目標(biāo)為最小化該車隊(duì)產(chǎn)生的總保障延誤懲罰成本。定義集合Jkb為預(yù)儲(chǔ)點(diǎn)k中車隊(duì)b所承擔(dān)的部隊(duì)器材預(yù)置任務(wù)，即Jkb={j|vjkb=1,?j∈J}。定義變量zij表示部隊(duì)i和j的保障次序相鄰，且i在j之前。則對(duì)預(yù)儲(chǔ)點(diǎn)k中車隊(duì)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ù)儲(chǔ)點(diǎn)k中車隊(duì)b處的總延誤懲罰成本最小化；約束(23)式表示兩部隊(duì)i和j的保障次序關(guān)系，即部隊(duì)i不可能同時(shí)既是部隊(duì)j的前一保障對(duì)象又是部隊(duì)j的后一保障對(duì)象；約束(24)式～(27)式與對(duì)應(yīng)前述約束(7)式～(10)式；約束(28)式為變量zij的域。

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

3.1.4 Benders切割

(29)

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

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

3.2.1 第一階段

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

(30)

s.t.

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

3.2.2 第二階段

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

4 數(shù)值實(shí)驗(yàn)

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

4.1 算例生成

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

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

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

(31)

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

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

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

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

4.3 大算例組結(jié)果

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

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

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

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

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

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

從3組算例的計(jì)算結(jié)果來(lái)看，算法LBBD在3種方法中表現(xiàn)最好。在160個(gè)算例中，LBBD共求得89個(gè)最優(yōu)解，總平均Gap值為5.73%；算法SH獲得32個(gè)最優(yōu)解，其平均Gap值為23.29%；模型P獲得44個(gè)最優(yōu)解，平均Gap值為39.14%。當(dāng)算例規(guī)模增大時(shí)，模型P的性能下降明顯，在48個(gè)常規(guī)算例中，模型P求得27個(gè)最優(yōu)解，平均Gap值為3.74%，而在64個(gè)超大算例中，兩項(xiàng)數(shù)據(jù)分別變?yōu)?個(gè)和80.21%，說(shuō)明在本文所研究的組合優(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)勢(shì)。

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

4.5 期望到達(dá)時(shí)間的影響

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

表4 期望到達(dá)時(shí)間的影響

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

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

5 結(jié)論

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

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

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

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

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