李 東 晏湘濤 匡興華

（國防科技大學(xué)信息系統(tǒng)與管理學(xué)院1） 長沙 410073） （國防科技大學(xué)人文與社會科學(xué)學(xué)院2） 長沙 410074）

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

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

1 問題描述

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

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

2 選址模型

定義以下符號.

I為部隊用戶集合，用i遍歷；J為備選地址點集合，用j遍歷；N為全部節(jié)點集合，N＝I＋J，且｜I｜＋｜J｜＝n；r為待建 MLDC數(shù)目；wi為部隊用戶i的需求；L為網(wǎng)絡(luò)內(nèi)全部路段集合；m為路段的數(shù)目；θ為權(quán)重系數(shù).

式中：

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

3 模型求解

3.1 下層規(guī)劃的求解

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

對于網(wǎng)絡(luò)G，有n個頂點，建立可達(dá)矩陣

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

根據(jù)最大覆蓋設(shè)施選址問題中關(guān)于覆蓋的定義，有如下命題成立.

命題1當(dāng)網(wǎng)絡(luò)中路段ek的長度大于覆蓋半徑時，對于網(wǎng)絡(luò)內(nèi)任意2個節(jié)點p和q，刪除路段ek不會影響p與q之間的覆蓋狀態(tài).

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

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

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

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

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

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

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

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

步驟7選擇其他路段，重復(fù)步驟4～6.當(dāng)每條路徑都失效過一次之后，停止循環(huán).

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

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

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

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

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

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

步驟2按照目標(biāo)函數(shù)（1）計算初始種群中各條染色體的適應(yīng)度.

步驟3根據(jù)染色體適應(yīng)度的大小，在種群中選擇部分染色體.

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

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

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

步驟7重復(fù)步驟2～6，直到進化次數(shù)達(dá)到進化代數(shù)G停止.

步驟8確定進化代數(shù)G內(nèi)具有最大適應(yīng)度的染色體，該染色體所對應(yīng)選址方案，即為模型的最優(yōu)解.

4 應(yīng)用算例

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

圖1 算例網(wǎng)絡(luò)圖

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

表1 模型結(jié)果比較

圖2 算法進化過程

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

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

5 結(jié)束語

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

［1］晏湘濤，李 東，匡興華.基于共識度決策的軍事物流配送中心選址研究［J］.武漢理工大學(xué)學(xué)報：交通科學(xué)與工程版，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］刑文訓(xùn)，謝金星.現(xiàn)代優(yōu)化計算方法［M］.北京：清華大學(xué)出版社，2007.