模糊需求下保障設施選址- 路徑模型及算法*

孫 凌，梁 明，羅長遠

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

0 引言

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

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

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

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

1.1 模糊需求量分析

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

1.2 保障設施備選址評價

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

圖1 選址決策評價指標體系

Step1：確定隸屬度

假設有s 個決策組，以m 個評價指標對n 個備選方案進行評價，指標特征值矩陣為：

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

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

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

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

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

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

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

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

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

2 保障設施選址-路徑模型

2.1 模型建立

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

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

式（7）表示選址方案最優(yōu)；式（8）表示保障成本，主要包括計劃運輸費用、偏離保障時間懲罰成本及考慮服務失敗所產(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ā)式的模型進行求解過程分為4 個階段：

1）第1 階段，作戰(zhà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 的坐標，m 是小組總數(shù)，n 是備選點數(shù)。

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

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

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

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ù)器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)解進行改善；

Step9：利用式（22）和式（23）進行信息素更新；

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

3 算例分析

假設10 個作戰(zhàn)單元分散在其作戰(zhàn)區(qū)域內(nèi)，即形成了10 個保障需求點。根據(jù)該階段任務的既定作戰(zhàn)目標，指揮部門對各作戰(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)單元的重要度及保障物資對該單位完成此次任務的重要性，得出各作戰(zhàn)單元的保障時間滿意度函數(shù)及偏離時間懲罰成本函數(shù)，其參數(shù)如表3、表4 所示。

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

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

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

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

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

4 結(jié)論

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