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

李 東 晏湘濤 匡興華

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

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

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

1 問題描述

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

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

2 選址模型

定義以下符號(hào).

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

式中：

M1是一個(gè)雙層規(guī)劃.上層規(guī)劃目標(biāo)是要找到一個(gè)地址組合，使得由該地址組合構(gòu)成的戰(zhàn)場保障網(wǎng)絡(luò)在無路段失效和出現(xiàn)路段失效時(shí)系統(tǒng)覆蓋盡可能多的需求量，即目標(biāo)函數(shù)（1）.目標(biāo)函數(shù)（1）的第一部分表示無路段失效時(shí)戰(zhàn)場保障網(wǎng)絡(luò)覆蓋的需求量，第二部分表示由某種地址組合x組成的戰(zhàn)場保障網(wǎng)絡(luò)在某一路段失效時(shí)覆蓋的需求量H（x），H（x）由下層規(guī)劃的目標(biāo)函數(shù)（5）來決定.下層規(guī)劃是目標(biāo)是找到一個(gè)路段，使得該路段失效時(shí)系統(tǒng)覆蓋的需求量最小.約束條件（2）是限定部隊(duì)用戶只能被開設(shè)的MLDC覆蓋；約束條件（3）限定了待建MLDC的數(shù)量；約束條件（6）計(jì)算路段失效時(shí)系統(tǒng)覆蓋的需求量.約束條件（7）和（8）把上下2層規(guī)劃連接起來，約束條件（7）限定當(dāng)路段k失效時(shí)，部隊(duì)用戶只能被開設(shè)的MLDC覆蓋，在xj和yik之間建立聯(lián)系，約束條件（8）限定在路徑k失效的情況下，當(dāng)且僅當(dāng)覆蓋部隊(duì)用戶i的MLDC數(shù)量大于0時(shí)，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)點(diǎn)與需求點(diǎn)之間滿足覆蓋半徑約束的可用覆蓋路徑；其次，任選一條路段使其失效，并對可用覆蓋路徑進(jìn)行剪裁，得到此路段失效時(shí)網(wǎng)絡(luò)節(jié)點(diǎn)之間的可達(dá)矩陣；然后，利用可達(dá)矩陣和部隊(duì)用戶的需求量計(jì)算網(wǎng)絡(luò)的覆蓋程度；最后，比較不同路段失效時(shí)網(wǎng)絡(luò)覆蓋程度的大小，找出使網(wǎng)絡(luò)覆蓋程度最小的路段.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 應(yīng)用算例

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

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

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

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

圖2 算法進(jìn)化過程

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

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

5 結(jié)束語

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

［1］晏湘濤，李 東，匡興華.基于共識(shí)度決策的軍事物流配送中心選址研究［J］.武漢理工大學(xué)學(xué)報(bào)：交通科學(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)化計(jì)算方法［M］.北京：清華大學(xué)出版社，2007.