孫 凌，梁 明，羅長遠(yuǎn)

（1.河南牧業(yè)經(jīng)濟(jì)學(xué)院信息工程學(xué)院，鄭州 450044；2.解放軍31674 部隊，拉薩 851400，3.信息工程大學(xué)，鄭州 450001）

0 引言

為實現(xiàn)有效的裝備保障，保障系統(tǒng)的快速反應(yīng)能力就尤為突出。在保障系統(tǒng)中，倉庫、補給站等保障設(shè)施是為被保障單位提供保障服務(wù)的基地，其位置及配送路線的合理與否，直接關(guān)系著保障系統(tǒng)能否在有效的時間范圍內(nèi)提供保障服務(wù)、所提供保障服務(wù)的效率高低以及保障成本高低，直接影響著保障系統(tǒng)對保障需求的反應(yīng)能力。因此，保障設(shè)施的選址-路徑?jīng)Q策成為戰(zhàn)時保障的重要研究內(nèi)容。

選址-路徑問題是物流管理中開展最早、研究最多的一類集成優(yōu)化問題。文獻(xiàn)［1］研究了多期離散設(shè)施選址-路徑問題；文獻(xiàn)［2］對平面內(nèi)單設(shè)施選址-路徑問題進(jìn)行了研究，并用分層算法進(jìn)行求解；文獻(xiàn)［3］對模糊需求下的選址-路徑問題進(jìn)行了研究，并用混合模擬退火算法進(jìn)行求解；文獻(xiàn)［4］研究了工業(yè)有害廢物處理中心的選址-路徑問題，涉及到廢物的收集、運輸、處理、回收等多個環(huán)節(jié)；以上文獻(xiàn)在對選址-路徑的研究中，沒有考慮倉庫及運輸車輛容量的限制。文獻(xiàn)［5-11］分別用不同的方法對有容量限制的選址-路徑問題進(jìn)行了研究，但其客戶的需求量都是確定的。由于戰(zhàn)斗的突發(fā)性及高消耗性，導(dǎo)致前方作戰(zhàn)單元只能對自己的需求量提供一個大概的數(shù)值，而運輸車輛在到達(dá)作戰(zhàn)單元之前并不知道確切的需求量，因此，在預(yù)先計劃的運輸線路上，可能使得累積需求量超出車輛的容量限制，保障無法繼續(xù)進(jìn)行。

本文針對被保障單位需求量不確定現(xiàn)象，建立了模糊需求下帶有時間窗及容量限制的選址-路徑模型，并設(shè)計了基于聚類分析與蟻群算法的混合啟發(fā)式模型求解算法。

1 保障設(shè)施選址-路徑相關(guān)因素分析

1.1 模糊需求量分析

第k+1 個作戰(zhàn)單元的需求量不超過保障基地庫存剩余量的可信度為：

1.2 保障設(shè)施備選址評價

初步構(gòu)建保障設(shè)施選址方案評價指標(biāo)體系如圖1 所示。這種層次結(jié)構(gòu)的組成元素和構(gòu)架不是固定不變，保障部門在具體應(yīng)用時可根據(jù)不同的評價對象對圖1 進(jìn)行適當(dāng)調(diào)整。結(jié)合模糊綜合評價與群決策思想，用于確定保障部門對各備選方案的綜合評價值，步驟如下：

圖1 選址決策評價指標(biāo)體系

Step1：確定隸屬度

假設(shè)有s 個決策組，以m 個評價指標(biāo)對n 個備選方案進(jìn)行評價，指標(biāo)特征值矩陣為：

3）按vi*的大小對方案集進(jìn)行排序，vi*越大，則相應(yīng)的備選址方案越優(yōu)。

通過以上模糊群決策過程，保障部門可以綜合考慮各保障設(shè)施備選址點的眾多特性，對可行備選地址點進(jìn)行科學(xué)合理的評價，得到相應(yīng)的權(quán)重值。

1.3 時間滿意度及懲罰成本分析

1.3.1 保障時間滿意度函數(shù)

對于各作戰(zhàn)單元來說，除了有最佳保障時段外，為了做好應(yīng)急準(zhǔn)備，其都還有一段對提前到達(dá)及超時到達(dá)的容忍時限。為了準(zhǔn)確刻畫各作戰(zhàn)單元對保障時間的要求，構(gòu)建衡量作戰(zhàn)單元對保障反應(yīng)時間滿意度的評價函數(shù)：

其中，tj表示運輸車輛實際到達(dá)作戰(zhàn)單元j 的時間，mj表示作戰(zhàn)單元j 的最大提前到達(dá)容忍時限，aj表示作戰(zhàn)單元j 的最佳保障時段的開始時間，bj表示作戰(zhàn)單元j 的最佳保障時段的結(jié)束時間，nj表示作戰(zhàn)單元j 的最大超時到達(dá)容忍時限。式（5）表示若運輸車輛到達(dá)時間tj在mj之前，保障時間低于作戰(zhàn)單元j 的最大提前到達(dá)容忍時限mj，即作戰(zhàn)單元j 的滿意度為0；當(dāng)mj≤tj＜aj時，保障時間在作戰(zhàn)單元j的提前到達(dá)容忍時段內(nèi)，作戰(zhàn)單元的滿意度會隨著時間的推移而增大；當(dāng)aj≤tj≤bj時，保障時間在作戰(zhàn)單元j 的最佳保障時段內(nèi)，其滿意度為1；當(dāng)bj＜tj≤nj時，保障時間在作戰(zhàn)單元j 的超時到達(dá)容忍時段內(nèi)，作戰(zhàn)單元的滿意度會隨著時間的推移而減少；當(dāng)tj＞nj時，保障時間大于作戰(zhàn)單元j 的最大超時到達(dá)容忍時限nj，即作戰(zhàn)單元j 的滿意度為0。

1.3.2 偏離時間懲罰成本函數(shù)

由于每個保障任務(wù)中都有時間窗約束（作戰(zhàn)單元的最佳保障時間段），當(dāng)運輸車輛未能在時間窗內(nèi)完成保障任務(wù)時，將會產(chǎn)出懲罰成本，且到達(dá)時間偏離約束時間窗越多，懲罰成本則越高。構(gòu)建偏離時間懲罰成本函數(shù)：

式（6）表示若運輸車輛到達(dá)時間tj在作戰(zhàn)單元j的最大提前到達(dá)容忍時限mj之前，則所造成的懲罰成本為Mj1；當(dāng)mj≤tj＜aj時，保障時間在作戰(zhàn)單元j的提前到達(dá)容忍時段內(nèi)，所造成的懲罰成本將隨著時間的推移而減少；當(dāng)aj≤tj≤bj時，保障時間在作戰(zhàn)單元j 的最佳保障時段內(nèi)，能夠圓滿完成保障任務(wù)，即懲罰成本為0；當(dāng)bj＜tj≤nj時，保障時間在作戰(zhàn)單元j 的超時到達(dá)容忍時段內(nèi)，所造成的懲罰成本將隨著時間的推移而增大；當(dāng)tj＞nj時，保障時間大于作戰(zhàn)單元j 的最大超時到達(dá)容忍時限nj，則所造成的懲罰成本為Mj2。

2 保障設(shè)施選址-路徑模型

2.1 模型建立

假設(shè)J 為作戰(zhàn)單元集合；I 為保障基地候選點集合；V 表示所有點集合，即J∪I；E 表示所有連接兩節(jié)點（i，j）的集合，i，j∈V；K 表示運輸車輛集合。ωj表示作戰(zhàn)單元j 處作戰(zhàn)任務(wù)的成功完成對該次戰(zhàn)役任務(wù)的重要度；dj表示作戰(zhàn)單元j 的需求量；Pi表示保障基地i 的最大庫存容量；gij表示節(jié)點i 到節(jié)點j距離；cij表示兩節(jié)點（i，j）的單位運輸費用，其中（i，j）∈E。f 表示因各路徑上的服務(wù)失敗而產(chǎn)生的額外運輸總費用；v 表示運輸車輛平均速度。tjk表示運輸車輛k 在其路徑上到達(dá)作戰(zhàn)單元j 的時刻；stjk表示運輸車輛k 在作戰(zhàn)單元j 的保障時間；ltjk表示運輸車輛k 在其路徑上從作戰(zhàn)單元j 離開的時刻；fj（tjk）表示作戰(zhàn)單元j 對運輸車輛k 保障反應(yīng)時間的滿意度函數(shù)；hj（tjk）表示運輸車輛k 在對作戰(zhàn)單元j 保障時偏離時間的懲罰成本函數(shù)。決策變量Zi和Yij表示在創(chuàng)庫候選點i 被選中以及為作戰(zhàn)單元j 服務(wù)時取值1，Wjk和Xijk表示車輛k 為作戰(zhàn)單元j 服務(wù)以及在其路徑上有從i 到j(luò) 的路段時取值1；否則取值為0。

在上述分析的基礎(chǔ)上，建立了使總選址方案最優(yōu)，保障成本最小的選址-路徑雙目標(biāo)模型：

式（7）表示選址方案最優(yōu)；式（8）表示保障成本，主要包括計劃運輸費用、偏離保障時間懲罰成本及考慮服務(wù)失敗所產(chǎn)生的額外費用；約束（9）表示在車輛容量及可信水平范圍內(nèi)保障所有作戰(zhàn)單元；約束（10）表示在保障基地庫存容量及可信水平范圍內(nèi)保障所有作戰(zhàn)單元；約束（11）保證每個作戰(zhàn)單元有且只有一輛車為其保障；約束（12）保證線路中沒有子回路；約束（13）與約束（14）保證線路的連續(xù)性及車輛返回到起點保障基地；約束（15）表示每個作戰(zhàn)單元有且僅有一個候選點為其保障；約束（16）表示兩決策變量之間的關(guān)系；約束（17）表示前后兩連續(xù)作戰(zhàn)單元上車輛離開時間約束；約束（18）表示運輸車輛只有在時間窗口開啟保障作戰(zhàn)單元之后離開。

2.2 模型求解

基于聚類分析與蟻群算法的混合啟發(fā)式的模型進(jìn)行求解過程分為4 個階段：

1）第1 階段，作戰(zhàn)單元分組

利用聚類分析思想進(jìn)行分組，作戰(zhàn)單元分組要考慮各作戰(zhàn)單元的時間窗、作戰(zhàn)單元之間的距離、模糊需求量及運輸車輛的容量等相關(guān)因素。其步驟如下：

Step1：從未分組的作戰(zhàn)單元中選擇最佳保障時間段開始時間aj最小的作為聚類中心，記為j；

Step4：若還有未檢測過的作戰(zhàn)單元，則在其集合中執(zhí)行Step2；否則，執(zhí)行Step5；

Step5：若還有未分組的作戰(zhàn)單元，則新創(chuàng)建一個小組，執(zhí)行Step1；否則，執(zhí)行Step6；

Step6：作戰(zhàn)單元分組完成，算法停止。

2）第2 階段，備選址點排序

Step2：利用式（20）計算每個組的重心與每個備選點之間的距離之和。

其中，Bi表示備選點i 與所有分組重心點之間的歐氏距離，（xi，yi）表示備選點i 的坐標(biāo)，m 是小組總數(shù)，n 是備選點數(shù)。

Step3：根據(jù)Bi/vi*的比值大小按升序把備選點從1 到n 排序，并按照此序列選擇倉庫建設(shè)點。

3）第3 階段，作戰(zhàn)單元分組匹配

Step1：計算每個未匹配的作戰(zhàn)單元分組重心與未匹配備選點中排名第一者之間的歐氏距離，根據(jù)歐氏距離的大小按升序把小組進(jìn)行排序，并按照此序列對該備選點進(jìn)行分配；

Step3：對后序作戰(zhàn)單元分組執(zhí)行Step2，直到該備選點剩余庫存不能容納任何一個小組；

Step4：若還有未匹配的作戰(zhàn)單元分組，則執(zhí)行Step1；否則，執(zhí)行Step5；

Step5：作戰(zhàn)單元分組匹配完成，算法停止。

4）第4 階段，確定線路

①狀態(tài)轉(zhuǎn)移規(guī)則

第k 個路徑上的螞蟻由作戰(zhàn)單元i 轉(zhuǎn)向作戰(zhàn)單元j 的概率為：

②信息素更新規(guī)則

其中，δ 為螞蟻釋放的信息素量的單位長度。

利用上述算法規(guī)則，配送路徑的求解算法步驟如下：

Step1：初始化各參數(shù)；

Step2：設(shè)置迭代計數(shù)器Nc=0，將m 只螞蟻放于保障基地，分別為各螞蟻建立禁忌表；

Step3：對每只螞蟻i，在已確定匹配關(guān)系的作戰(zhàn)單元分組列表中找出所有未訪問過的節(jié)點，根據(jù)式（21）計算的概率來選擇下一個訪問的客戶節(jié)點j；

Step4：判斷作戰(zhàn)單元j 的需求量是否超過運輸車輛的剩余量，若不超過，則執(zhí)行Step5；否則，將作戰(zhàn)單元j 重新放入集合A 中，并執(zhí)行Step6；

Step5：判斷tjk是否滿足時間窗要求，若滿足，則把點j 放入禁忌表中，并執(zhí)行Step3；否則將點j 重新放入集合A 中，執(zhí)行Step6；

Step6：判斷集合A 是否為空，若為空，則執(zhí)行Step7；否則從集合A 中選擇開始時間最早的點作為起點，并執(zhí)行Step3；

Step7：計算每只螞蟻走過的每條回路的路徑長度，按照各螞蟻所得到的可行解，得出局部最優(yōu)解；

Step8：運用2-opt 法對局部最優(yōu)解進(jìn)行改善；

Step9：利用式（22）和式（23）進(jìn)行信息素更新；

Step10：判斷Nc＞Ncmax是否成立，若成立，則算法結(jié)束，輸出計算結(jié)果；否則清空禁忌表，執(zhí)行Step2。

3 算例分析

假設(shè)10 個作戰(zhàn)單元分散在其作戰(zhàn)區(qū)域內(nèi)，即形成了10 個保障需求點。根據(jù)該階段任務(wù)的既定作戰(zhàn)目標(biāo)，指揮部門對各作戰(zhàn)單元的保障重要度做出了評價，并與作戰(zhàn)單元的位置、需求量（單位t）、作業(yè)時間（單位h）、約束時間窗及容忍時限等信息繪制成表，如表1 所示。

表1 各作戰(zhàn)單元的信息

為了實現(xiàn)及時有效地保障，裝備保障部門擬在該保障區(qū)域內(nèi)建立2 個保障基地。保障基地配備運輸車輛若干，每輛車載重量均為8 t，車輛平均行駛速度為50 km/h，單位運輸費用為50 元/km。根據(jù)戰(zhàn)場環(huán)境保障相關(guān)技術(shù)部門對作戰(zhàn)區(qū)域的地形地貌、水電能源條件及道路交通狀況等各方面的考察，已確定5 處可行的保障基地備選點，各備選點的權(quán)重、地理位置及容量限制（t）等信息繪制成表，如表2 所示。

表2 各備選點的信息

另外，根據(jù)作戰(zhàn)單元的重要度及保障物資對該單位完成此次任務(wù)的重要性，得出各作戰(zhàn)單元的保障時間滿意度函數(shù)及偏離時間懲罰成本函數(shù)，其參數(shù)如表3、表4 所示。

表3 各作戰(zhàn)單元的保障時間滿意度函數(shù)相關(guān)參數(shù)

表4 各作戰(zhàn)單元的偏離時間懲罰成本函數(shù)相關(guān)參數(shù)

圖2 保障物資配送線路規(guī)劃示意圖

依據(jù)配送方案，進(jìn)而得到各配送線路的費用及總方案評價值如表5 所示。從表中可以看出，本文給出的優(yōu)化方案無論在總費用和評價值方面都具備比較好的優(yōu)勢。這是因為備選點權(quán)重優(yōu)先方案雖然選擇的保障基地的權(quán)重最高，但缺少考慮路徑問題所以帶來巨大的費用成本，從而也影響了方案的總評價值；短路徑距離優(yōu)先方案雖然也選擇了②、③備選點作為保障基地，并確保了計劃費用最小，但是其缺少考慮時間限制因素，導(dǎo)致了較高的懲罰成本。

表5 選址-路徑方案及相應(yīng)數(shù)據(jù)

4 結(jié)論

針對裝備保障過程中被保障單位需求量不確定的問題，對模糊需求下帶有時間窗及容量限制的選址-路徑問題進(jìn)行了研究，建立了相應(yīng)的模型，結(jié)合對模型的分析，設(shè)計了基于聚類分析與蟻群算法的混合啟發(fā)式算法，通過算例分析，驗證了模型的正確性及算法的有效性。研究成果對模糊需求下物資供應(yīng)類裝備保障點的選址-路徑確定具有一定的參考價值。由于維修類裝備保障通常采用分級多基地保障，備件庫存狀態(tài)轉(zhuǎn)移相對穩(wěn)定，多考慮基于馬爾可夫過程的橫向轉(zhuǎn)運或延遲轉(zhuǎn)運及備件庫存模型。但文中的保障設(shè)施備選址評價方法對維修類保障設(shè)施的選址也具備一定的借鑒意義。