考慮路段失效的軍事物流配送中心選址模型＊

李 東 晏湘濤 匡興華

（國防科技大學信息系統與管理學院1） 長沙 410073） （國防科技大學人文與社會科學學院2） 長沙 410074）

軍事物流配送中心（military logistics distribution center，MLDC）是戰場保障網絡的支撐點，對戰場物流的流量、時間、成本有重大影響.由于戰場保障網絡是后勤保障的重心，因此物流通道在戰時常常遭到敵人的打擊.從戰爭實際來發，MLDC位置的選擇需要考慮物流通道失效的情況［1］.

考慮失效的設施選址，稱為可靠（的）設施選址（reliable facility location）.可靠設施選址，就是前攝地選擇設施位置，使配送系統不但在正常情況下能夠實現最優化，而且在發生失效時仍能運行“良好”［2］.Daskin研究團隊以無容量限制選址問題（uncapacitated facilities location problem）為基礎，采用不同的選址目標系統地研究了設施無容量限制情況下的可靠選址問題［3－4］；Dinakar擴展了Daskin團隊的研究，研究了設施存在能力限制的可靠選址問題，要求設施能力同時滿足無失效時的基本指派和發生失效后再指派的需要［5］；O＇Hanley和 Church［6－7］在研究覆蓋型網絡的可靠設施選址問題時，考慮了覆蓋路徑對選址決策的影響.以上學者的研究都是假設物流網絡中的設施存在失效可能.然而，對于戰場保障網絡而言，物流通道比保障設施更容量出現失效.因此，本文在研究戰場保障網絡的軍事物流配送中心可靠選址問題時，把失效的焦點集中在配送路段上，突出路段失效對選址決策的影響，采用最大覆蓋模型進行研究.

1 問題描述

對于一個由部隊用戶、備選地址點、配送路段構成的戰場保障網絡，基本假設如下：（1）不考慮軍事物流配送中心的供應能力；（2）每個路段都存在失效的可能，但只有一條路段失效；（3）能夠建立的軍事物流配送中心數目已知.軍事物流配送中心的供應能力主要由戰役級保障設施的保障效果決定.由于本文研究的重點是軍事物流配送中心到部隊用戶之間的后勤保障，因此軍事物流配送中心的供應能力不是本文考慮的內容，假設（1）成立.假設（2）是對未來戰場環境的描述.假設（2）既能考慮到己方決策部門設計配送方案時的謹慎態度，又可以兼顧敵人企圖通過打擊補給線干擾對方戰爭行動的可能性.假設（3）是簡化問題的必要假設.

考慮路段失效的軍事物流配送中心選址問題，就是從給定的備選地址中選擇出一個地址組合，使得由處于這些地址的軍事物流配送中心構成的保障系統，無論是在無路段失效還是在出現路段失效的情況下，都能在滿足覆蓋半徑的約束內覆蓋盡可能多的需求量.

2 選址模型

定義以下符號.

I為部隊用戶集合，用i遍歷；J為備選地址點集合，用j遍歷；N為全部節點集合，N＝I＋J，且｜I｜＋｜J｜＝n；r為待建 MLDC數目；wi為部隊用戶i的需求；L為網絡內全部路段集合；m為路段的數目；θ為權重系數.

式中：

M1是一個雙層規劃.上層規劃目標是要找到一個地址組合，使得由該地址組合構成的戰場保障網絡在無路段失效和出現路段失效時系統覆蓋盡可能多的需求量，即目標函數（1）.目標函數（1）的第一部分表示無路段失效時戰場保障網絡覆蓋的需求量，第二部分表示由某種地址組合x組成的戰場保障網絡在某一路段失效時覆蓋的需求量H（x），H（x）由下層規劃的目標函數（5）來決定.下層規劃是目標是找到一個路段，使得該路段失效時系統覆蓋的需求量最小.約束條件（2）是限定部隊用戶只能被開設的MLDC覆蓋；約束條件（3）限定了待建MLDC的數量；約束條件（6）計算路段失效時系統覆蓋的需求量.約束條件（7）和（8）把上下2層規劃連接起來，約束條件（7）限定當路段k失效時，部隊用戶只能被開設的MLDC覆蓋，在xj和yik之間建立聯系，約束條件（8）限定在路徑k失效的情況下，當且僅當覆蓋部隊用戶i的MLDC數量大于0時，yik才能取值為1，在zk和xj之間建立聯系.約束條件（4）和（9）是對決策變量xj，yi，yik，zk的0或1整數約束.

3 模型求解

3.1 下層規劃的求解

為了下文表述方便，稱下層規劃為“最佳路段失效問題”.求解最佳路段失效問題的基本思想：首先，找出網絡內供應點與需求點之間滿足覆蓋半徑約束的可用覆蓋路徑；其次，任選一條路段使其失效，并對可用覆蓋路徑進行剪裁，得到此路段失效時網絡節點之間的可達矩陣；然后，利用可達矩陣和部隊用戶的需求量計算網絡的覆蓋程度；最后，比較不同路段失效時網絡覆蓋程度的大小，找出使網絡覆蓋程度最小的路段.

對于網絡G，有n個頂點，建立可達矩陣

元素apq的取值為0或1.當取值為1時，表示節點p到節點q的路徑距離滿足覆蓋半徑約束；當取值為0時，節點p到節點q的路徑距離不滿足覆蓋半徑約束.

根據最大覆蓋設施選址問題中關于覆蓋的定義，有如下命題成立.

命題1當網絡中路段ek的長度大于覆蓋半徑時，對于網絡內任意2個節點p和q，刪除路段ek不會影響p與q之間的覆蓋狀態.

證明如果p與q之間的最短路徑包括了路段ek，p與q之間的距離肯定大于覆蓋半徑，因此若欲p覆蓋q，那么p與q之間的最短路徑一定不能包括路段ek.由此可知，刪掉路段ek不會影響整個網絡的覆蓋程度.

對于由部隊用戶集合I和備選地址點集合J以及I與J之間的路段構成的網絡G，最佳路段失效問題的具體求解步驟.

步驟1刪除無影響路段.根據設施覆蓋半徑的長度，移除G中長度大于覆蓋半徑的路段.

步驟2搜索某個給定選址方案的可用覆蓋路徑.若在節點p建立MLDC，那么根據點p的覆蓋半徑約束，找出從點p出發符合要求的路段，然后根據這些路段的尾節點繼續搜索，直到找出所有符合覆蓋半徑約束的路徑，得到全部設施的可用覆蓋路徑集P.

步驟3根據P建立初始可達矩陣An×n（A內元素的初始值為0）.只要點q處的部隊用戶包含于點p處的MLDC發出的某條可用覆蓋路徑之內，那么apq，apq＝1；否則，apq，apq＝0.

步驟4從全部路段集中任選一個路段ek，令路段ek失效（即路段ek的長度為∞），并使路徑集P中包含路段ek的可用覆蓋路徑，去掉自路段ek以后的部分，得到新的可用覆蓋路徑集Pk.

步驟5根據Pk建立路段ek失效情況下的可達矩陣（Ak內元素的初值為0）.路段ek失效時，Ak中的元素由Pk中的可行覆蓋路徑決定.只要點q處的部隊用戶包含于點p處的MLDC發出的某條可用覆蓋路徑之內，那么＝1；否則＝0.

步驟6計算路段ek失效時網絡覆蓋程度的變化量Ck.記G的需求矩陣為D＝｛d1，d2，…，dn｝，若點q處為部隊用戶，那么dq＝wq，若點q處為備選地址點，那么dq＝0，Ck的值由下式求得.

步驟7選擇其他路段，重復步驟4～6.當每條路徑都失效過一次之后，停止循環.

步驟8確定最優解.使Ck最大的路段ek即為最佳路段失效問題的最優解.

其中，在步驟2求解可用覆蓋路徑中，由于每條可用覆蓋路徑最多遍歷每個節點一次，所以路徑的邊數不會超過（n－1）.將每條路徑每次推進一步，使得搜索可以在（n－2）內完成.

3.2 基于遺傳算法的模型求解

遺傳算法（genetic algorithm，GA）是一種全局優化搜索算法，具有簡單通用、魯棒性強、適于并行處理以及應用范圍廣等顯著特點［8］.本文采用遺傳算法對模型進行求解，通過選擇、交叉、變異操作識別出好的染色體，求得最佳選址地點.

基于遺傳算法的模型求解具體步驟如下.

步驟1初始化算法的相關參數，產生初始種群.相關參數主要包括：種群規模K、進化代數G、選擇規模系數pselect、交叉概率pcross等，并令進化次數a＝0.

步驟2按照目標函數（1）計算初始種群中各條染色體的適應度.

步驟3根據染色體適應度的大小，在種群中選擇部分染色體.

步驟4對選擇的染色體進行交叉操作，得到子代染色體.

步驟5對子代染色體進行變異操作，計算變異后子代染色體的適應度.

步驟6根據子代后染色體的適應度的大小，把變異的子代染色體插入父代種群中，得到新的種群.

步驟7重復步驟2～6，直到進化次數達到進化代數G停止.

步驟8確定進化代數G內具有最大適應度的染色體，該染色體所對應選址方案，即為模型的最優解.

4 應用算例

在某次戰區演習的進攻戰斗中，后勤部門決定在某機械化師的作戰地域內建立3個軍事物流配送中心，為該師的10個營級戰斗分隊提供物資保障.經初步考察已有5個地點被列為備選地址，備選地址與戰斗分隊構成的物流網絡如圖1所示.后勤部門確定軍事物流配送中心的覆蓋半徑為2，各戰斗分隊的需求量、網絡中各節點之間的距離已知并在圖中表示出來.圖中點1～10為需求點，即戰斗分隊的位置，點A～E為備選地址點.

圖1 算例網絡圖

令式（1）中θ的取值為0.7，種群規模K＝40，進化代數G＝400，選擇規模系數pselect＝0.9，交叉概率pcross＝0.7.采用 Matlab7.0編程求解，求解結果如表1所列，算法進化過程如圖2所示.

表1 模型結果比較

圖2 算法進化過程

由表1可知，本文模型的選址結果與不考慮路段失效情況的最大覆蓋選址結果存在差異.在無路段失效時，M0的選址方案能夠覆蓋最多的需求量，選址結果優于M1.然而，在最佳路段失效情況下，M0的選址方案不再是最優的，M1的選址方案能夠在最佳路徑失效時損失較低的需求覆蓋量.特別地，M1的選址方案在無路段失效時覆蓋的需求量方面與M0的選址方案相差不多，還能夠有效控制最佳路段失效時的系統損失.

對于后勤部門來說，可以根據戰斗分隊作戰地域的資源狀況情況結合模型的特點，選擇適當的模型進行軍事物流配送中心選址決策.當作戰地域內交通便利，保障資源豐富時，可以采用M0進行選址決策.豐富的保障資源可以使后勤部門在最佳路段失效做出快速反應，迅速地就地籌措物資，并通過便利的交通通道把用戶急需的軍事物資及時送達指定地點，彌補M0的選址方案在最佳路段失效時的不足.當作戰地域遠離戰役后方、交通不便、保障資源稀少、自然資源匱乏、軍事物資難以就地籌措時，戰場物資保障完全依靠前出保障時，可以采用M1進行選址決策.M1選址方案可以獲得較高的需求覆蓋量，又能控制路段失效時的系統損失，能夠降低緊急情況下應急保障對就地籌措保障方式的依賴程度.

5 結束語

本文研究了戰場保障網絡設計中的軍事物流配送中心選址問題，考慮了配送路段失效的情況，以最大化系統在無路段失效時和最佳路段失效時所覆蓋的總需求量作為優化目標，建立了雙層規劃形式的選址模型.未來對于保障設施選址問題的研究可以考慮從以下幾個方面著手：（1）多路段失效情況下的設施選址.從戰爭實際來看，路段失效的個數取決于戰爭雙方的實力，呈現出一定的不確定性.因此為了更接近實際，需要對本文模型進行路段隨機失效情況下的擴展；（2）結合用戶敏捷性要求的選址.戰時物資保障是供需雙方共同作用的結果，供方具有配送能力約束，需方會有保障的時效性要求.因此，建立滿足用戶敏捷性要求選址模型，是一個值得深入研究的問題；（3）針對大型問題的模型求解算法.

［1］晏湘濤，李 東，匡興華.基于共識度決策的軍事物流配送中心選址研究［J］.武漢理工大學學報：交通科學與工程版，2010，34（1）：27－30.

［2］Snyder L V，Daskin M S.Models for reliable supply chain network design［R］.Evanston：Northwestern University，2006.

［3］Snyder L V.Planning for disruptions in supply chain networks［M］.New Orleans：INFORMS，2005.

［4］Snyder L V，Daskin M S.Reliability models for facility location：the expected failure cost case［J］.Transportation Science，2005，39（3）：400－416.

［5］Dinakar G.Capacitated facilities location problems with unreliable facilities［D］.Fayetteville：University of Arkansas，2005.

［6］O＇Hanley J R，Church R L.Designing robust cover－age networks to hedge against worst－case facility losses［J］.European Journal of Operational Research，2010，In Press.

［7］Church R L，ReVelle C S.The maximal covering location problem［J］.Papers of the Regional Science Association，1974，32：101－118.

［8］刑文訓，謝金星.現代優化計算方法［M］.北京：清華大學出版社，2007.