考慮蓄意攻擊的第四方物流彈性網絡設計模型

李　銳,黃　敏,張瑞友,王興偉

(東北大學信息科學與工程學院;流程工業綜合自動化國家重點實驗室(東北大學),遼寧沈陽110819)

考慮蓄意攻擊的第四方物流彈性網絡設計模型

李銳,黃敏,張瑞友,王興偉

(東北大學信息科學與工程學院;流程工業綜合自動化國家重點實驗室(東北大學),遼寧沈陽110819)

研究考慮蓄意攻擊的第四方物流彈性網絡設計問題.建立一個雙層的第四方物流網絡設計優化模型,上層模型確定網絡結構,并在一定彈性水平下最小化網絡成本,下層模型則通過選擇攻擊策略來最大化網絡的攻擊效果.設計了雙層優化算法,上層概率解發掘算法求解網絡設計問題,下層迭代局部搜索算法求解最優的攻擊策略.最后,仿真實驗結果表明模型的合理性和算法的有效性.

第四方物流;網絡設計;彈性;蓄意攻擊;概率解發掘算法;迭代局部搜索

1　引　言

為了專注于自己的核心業務,許多企業將其物流業務外包給專業的物流公司.對于一些規模較大的企業來說,由于它們的商品生產地分散,需求遍布世界各地,所以客觀上要求物流公司能夠有機地整合各種物流活動,并對供應鏈進行系統化的管理.因為第三方物流(third party logistics,3PL)的服務能力薄弱,節約成本的潛力有限,并且不能整合社會所有物流資源,所以難以實現對整個供應鏈的優化.因此,作為供應鏈集成商的第四方物流[1](fourth party logistics,4PL)得到人們的廣泛關注.它對公司內部和具有互補性的服務提供商所具有的不同資源、能力和技術進行整合和管理,能為客戶企業提供一整套供應鏈解決方案.近年來,4PL的相關問題已經得到國內外學者的研究.陳建清等[2]提出了第四方物流運作中決策支持系統的框架和多維權的有向圖模型.王勇等[3]對4PL中的作業整合優化問題進行了研究.崔妍等[4]研究了考慮中轉發車時間和帶模糊處理時間的4PL路徑優化問題.Chen等[5]對4PL中的活動指派問題進行了研究.這些都為4PL的進一步研究奠定了基礎.

實際運作中,4PL管理者往往需要根據客戶的物流需求來設計有效的服務網絡.另外,4PL網絡還可能面臨各種中斷風險.其中人為的蓄意攻擊所產生的中斷會給4PL網絡帶來更大的破壞.特別是恐怖襲擊對于這種遍布全球的網絡化基礎設施的破壞會給人們帶來很大損失.因此,研究考慮蓄意攻擊的4PL網絡設計問題變得十分重要.目前,有關物流網絡安全性問題的研究大部分都考慮隨機中斷[6-8],而考慮蓄意攻擊中斷的研究都是針對已有網絡的保護問題[9,10].此外,彈性[11,12]也提供了一種描述系統安全性的新方法.

綜上所述,本文研究考慮蓄意攻擊的4PL彈性網絡設計問題.建立了考慮蓄意攻擊中斷的雙層優化模型.根據問題模型特點,設計雙層優化算法(IPSDA/ILS),上層采用改進的概率解發掘算法(improved probability solution discovery algorithm,IPSDA),下層采用迭代局部搜索算法(iterated local search,ILS),并通過數值例子與仿真實驗驗證模型的合理性和算法的有效性.

2　考慮蓄意攻擊的4　PL網絡設計模型

4PL可能承擔某一區域內的物流配送任務,通過3PL服務節點(倉庫、配送中心與港口等)和3PL運輸供應商將商品從供應點運輸到需求點.4PL網絡如圖1所示,圖中節點分別表示供應節點、3PL服務節點和需求節點;其中每條弧代表一個3PL運輸供應商.因為兩個節點之間可能存在多個3PL運輸供應商,所以在兩個節點之間可能有多條弧.此外,考慮4PL網絡中的3PL服務節點或運輸供應商受到蓄意攻擊而發生中斷.蓄意攻擊是指攻擊者通過攻擊3PL服務節點或運輸供應商來最大程度的降低網絡的服務質量.這里通過選擇冗余的3PL服務節點和運輸供應商作為備用來保證網絡在中斷狀態下的服務質量,增強網絡的彈性.

圖1　4PL網絡結構Fig.1　4PL Network Structure

考慮蓄意攻擊的4PL彈性網絡設計問題是指4PL管理者通過選擇3PL服務節點和運輸供應商來構建服務網絡,最小化網絡總成本,同時使其在蓄意攻擊下的彈性水平滿足一定的要求.

模型假設條件如下:

1)供應節點的數量、位置及最大供應量已知,用S表示供應節點集合,Fi表示供應節點i∈S的最大供應量;

2)需求節點的數量、位置和需求量已知,用L表示需求節點集合,Dj表示需求點j∈L的需求量;

3)3PL服務節點的處理費用、處理能力和構建成本已知,并分別表示為Ci,Qi和Hi,i∈U,其中U表示3PL服務節點集合;

4)3PL運輸供應商的單位貨物運輸成本、運輸能力和構建成本已知,分別表示為cijk,qijk和hijk,i∈V,j∈V,k∈Kij,其中V=S∪U∪L表示節點集合,Kij表示節點i和j之間3PL運輸供應商集合;

5)攻擊者的能力有限,即只能攻擊一定數量的3PL服務節點或者運輸供應商.

基于以上模型假設建立考慮蓄意攻擊中斷的4PL網絡設計雙層優化模型.上層模型在滿足一定的彈性水平下,最小化網絡總成本.下層模型通過優化攻擊策略使攻擊破壞效果最大,即最小化網絡對所有節點的最大滿足量.

2.1上層4PL網絡優化模型

引入如下決策變量:xijk∈{0,1},如果點i和j之間3PL運輸供應商k被選擇xijk為1,否則為0;yi∈{0,1},如果3PL服務節點i被選擇yi為1,否則為0;fijk為無攻擊狀態下節點i和j之間3PL運輸供應商k的運輸量;并令X={xijk|?i∈V,?j∈V,?k∈Kij},Y={yi|?i∈U}.

建立4PL網絡優化模型為

模型(1)的目標函數C(X,Y)為網絡總成本,包括固定的構建成本和可變的運作成本;約束(2)要求系統的彈性滿足要求的水平β,其中G(X,Y)為網絡受攻擊下的需求最大滿足量的最小值(可由蓄意攻擊優化模型(15)求得);約束(3)和(4)確保當3PL服務節點沒有被選擇時,與之相連的3PL運輸供應商也不能被選擇;約束(5)和(6)表示如果3PL服務節點被選擇,那么必須保證至少分別有一個3PL運輸供應商運入商品和運出商品;式(7)～式(9)分別是3PL運輸供應商,3PL服務點和供應點的能力的約束;約束(10)確保每個需求點的需求必須得到滿足;約束(11)保證3PL服務節點兩端的流平衡;式(12)是流量非負約束;式(13)和式(14)表示二值的決策變量.

2.2下層蓄意攻擊優化模型

決策變量wijk∈{0,1},如果點i和j之間3PL供應商k被攻擊則取值為1,否則為0;zi∈{0,1},如果3PL服務節點i被攻擊則取值為1,否則為0.令W={wijk|?i∈V,?j∈V,?k∈Kij},Z={zi|?i∈U}.

建立蓄意攻擊優化模型為

模型(15)最小化網絡在蓄意攻擊下對需求的最大滿足量,具體來說,Φ(X,Y,W,Z)表示網絡(X,Y)在攻擊策略(W,Z)下對所有需求點的最大滿足量(即去除被攻擊節點和弧后的剩余網絡的最大流);約束(16)和(17)表示被攻擊的3PL運輸供應商和服務節點必須是已選擇的;約束(18)和(19)表示攻擊3PL運輸供應商和服務節點的數量限制分別為p1和p2;式(20)和式(21)表示二值的決策變量.

3　雙層IPSDA/ILS算法

考慮蓄意攻擊的4PL彈性網絡設計問題的模型復雜,對于規模較大的問題求解十分困難.上層帶有彈性約束的4PL網絡設計問題是經典可靠性網絡設計問題的擴展,因此是NP-hard的.下層網絡蓄意攻擊問題可歸結為經典的背包問題,也是NP-hard問題.針對問題的特點,設計雙層IPSDA/ILS優化算法,通過對上層IPSDA的解進行解碼得到X和Y,然后調用下層ILS算法求解網絡的蓄意攻擊優化問題.

3.1上層IPSDA算法

PSDA算法是由美國Ramirez-Marquez和Rocco提出的一種進化算法,并已經成功求解網絡可靠性問題[13],網絡阻斷問題[14].由于PSDA算法容易出現早熟現象.為了改善PSDA算法的這個缺陷,設計一種改進的IPSDA算法,在產生解的樣本點步驟中引入擾動.

3.1.1IPSDA算法的步驟

IPSDA算法的主要步驟如下:

步驟1初始化概率向量γ0,解集規模 SAMPLE,最優子集規模m,最大循環代數 NG;

步驟2根據概率向量γu(u=1,2,...,NG),利用Monte Carlo仿真產生數量為SAMPLE的解集合.解的第j位按下式產生,即

其中γuj表示第u次循環第j位取值為1的概率,rand(0,1)表示隨機產生的[0,1]之間的隨機數.

由于PSDA算法經過一些代的循環之后,概率向量會收斂于1或者為0,所以很容易使搜索陷入局部最優.為了避免這種情況發生,對概率向量為0或1的位,以一定的概率Pr執行擾動,即如果rand(0,1)＜Pr,則執行下面操作,即

具體操作如下:以供應節點為初始點進行廣度優先搜索,按照上述方法依次確定解中對應位的值,同時對不滿足網絡連通性約束的解進行修復(詳見3.1.3節);

步驟3對于h=1,2,...,SAMPLE,調用下層ILS算法得到,計算每個樣本點Xhu的適應值,并按照降序排列適應值;

步驟4從已排序的數量為SAMPLE的解集中,選擇數量為m的最好子集更新概率向量γu,同時,數量為TOP的最好解被選擇,存儲于集合Ω.具體如下

根據下面式子更新概率向量的分量

步驟5當算法達到最大循環代數NG,或者γu再不能更新,則算法終止.否則,轉到步驟2;步驟6對集合Ω中解調用下層ILS算法精確計算彈性,選擇目標值最小的解輸出.

3.1.2解的表示

上層IPSDA的一個解可以表示為一維的向量.向量的維數為3PL服務節點和運輸供應商的總數.向量的每一位有0和1兩個狀態,表示對應的3PL服務節點或運輸供應商的選擇情況,“0”表示未被選擇,“1”表示被選擇.

3.1.3解的修復策略

為了滿足網絡連通性約束(3)～(6),在生成新解的過程中需要對不滿足這些約束的解進行修復,策略如下:如果一個3PL服務節點i∈U有入弧無出弧,此時隨機選擇一個以節點i為起點的弧,并將解中該弧的對應位設為1,即至少選擇一個出弧.類似地,如果一個解中沒有弧指向某需求節點,則可以用類似地方法進行修復.

3.1.4解的適應值

其中C(X,Y)為目標函數(1),如果給定(X,Y),通過增加虛的起始節點和目的節點,可以將問題轉換為網絡的最小費用流問題,然后用Bellman-Ford和Ford-Fulkerson結合的方法求解.按照上述方法計算的過程中,一個解還可能不滿足彈性約束(2)和需求滿足約束(10),所以將這些約束作為懲罰項加入到解的評價函數.α1和α2為懲罰系數,G(X,Y)通過調用下層ILS算法來計算求得,Φ(X,Y,W,Z)則通過網絡的最大流算法求得,x+=max(x,0).

3.2下層ILS算法

迭代局部搜索算法[15]是一種元啟發式算法.它通過局部搜索和擾動兩個基本操作產生新解.

3.2.1ILS算法的步驟

ILS算法的主要步驟如下：

步驟1產生初始解x0(詳見3.2.3節),并初始化最好解,x?←x0;

步驟2以x0為初始解執行局部搜索獲得一個改進解x′;

步驟3重復下面的步驟直到達到最大擾動次數NK,則算法終止.

步驟3.1隨機選擇一種擾動策略對x′進行擾動,得到x′′,

步驟3.2以x′′作為初始解進行局部搜索,得到局部最優解x′′′,

步驟3.3如果x′′′適應值滿足g(x′′′)＜g(x′),則轉移,x′←x′′′,

步驟3.4如果g(x?)＞g(x′′′),則更新最好解,x?←x′′′;

步驟4輸出最好解x?.

3.2.2解的表示

下層算法的解采用一維二進制數組來表示.數組的維數為上層模型中選擇的3PL服務節點和運輸供應商的數量.二進制碼表示對應的3PL服務節點和運輸供應商是否被攻擊,“1”表示被攻擊,而“0”表示未被攻擊.

3.2.3初始解的產生

3.2.4局部搜索策略

1)單點—單點交換:隨機選擇一個已攻擊的和一個未攻擊的3PL服務節點,交換兩個節點對應位的值,即“1”變為“0”,而“0”變為“1”.

2)單邊—單邊交換:隨機選擇一個已攻擊的和一個未攻擊的3PL運輸供應商,交換兩個節點對應位的值,即“1”變為“0”,而“0”變為“1”.

3.2.5擾動策略

1)多點—多點交換:隨機選擇多個已攻擊的3PL服務節點和相同數量的未攻擊的3PL服務節點,交換各個節點對應位的值,即“1”變為“0”,而“0”變為“1”.

2)多邊—多邊交換:隨機選擇多個已攻擊的3PL運輸供應商和相同數量的未攻擊的3PL運輸供應商,交換各個3PL運輸供應商對應位的值,即“1”變為“0”,而“0”變為“1”.

4　實驗結果及分析

為了測試IPSDA/ILS算法的有效性,本文對數據隨機生成的問題進行測試.算法采用MATLAB語言編碼,實驗環境為Intel Core 2 Quad 2.66 GHz臺式機,內存2.00 GB.

問題的規模如表1所示.問題的數據都按照下面均勻分布隨機產生,供應點的最大供應量Fi～U[240,260];需求點的需求量Dj～U[40,70];3PL服務節點的構建費用Hi～U[500,1 000],單位處理費用Ci～U[10,50],最大處理能力Qi～U[80,100];3PL運輸供應商的構建費用hijk～U[500,1 000],單位運輸費用cijk～U[10,50],最大運輸能力qijk～U[80,100].

為了測試雙層優化算法的性能,對不同規模的問題進行求解(所有問題的彈性約束水平都設置為0.6),并與PSDA/ILS算法的計算結果進行比較.其中IPSDA/ILS算法的參數設置如下:上層IPSDA的初始概率向量γ0各分量取0.5,最大循環代數NG為50,最優子集規模m取10,每代解集規模SAMPLE為40,擾動概率Pr為0.01;下層ILS的擾動次數NK為30,局部搜索次數為20.

對于每個問題每種算法分別運行20次,表2給出兩種算法的對比結果.由表2可知,雙層優化算法IPSDA/ILS的性能優于PSDA/ILS.表3給出不同問題的詳細計算結果.為了分析彈性對問題結果的影響,以問題P4為例進行測試(其中被攻擊3PL服務節點數取1,3PL運輸供應商數量取10).

表1　問題的規模Table 1　Size of the problems

表2　IPSDA/ILS算法與PSDA/ILS的性能對比Table 2　Comparison of IPSDA/ILS and PSDA/ILS algorithms

表3　問題的詳細結果Table 3　The detailed results of the problems

表4給出問題P4在不同彈性水平下的詳細結果.可見,隨著彈性的增加,目標值變大,構建成本增加,而運輸和處理成本變化不大.因為要增加網絡的彈性,需要構建冗余的3PL服務節點和運輸供應商,這樣在某些3PL服務節點和運輸供應商受到攻擊而發生中斷的情況下,網絡中剩余的3PL服務節點和運輸供應商仍然可以繼續提供服務,使需求點的需求盡量得到滿足,保證了網絡的服務質量.但是,冗余的網絡結構對網絡的最優費用的影響可能不大.

為了分析被攻擊的3PL服務節點數和3PL運輸供應商數對問題結果的影響,同樣以問題P4為例進行實驗(其中彈性取值為0.5).圖2給出被攻擊3PL服務節點數p2和被攻擊的3PL供應商的數量p1對目標值值構建成本和運輸處理成本的影響.可見,在p2不變的情況下,隨著p1的增加,目標值和構建成本都增加,而運輸和處理成本基本保持不變.對于不同的被攻擊3PL服務節點數p2,相同的p1對應的結果也不相同.如果p2較大,則目標值和構建成本也較大.

表4　問題的詳細結果Table 4　The detailed results of the problems

圖2　被攻擊的3PL供應商的數量對各成本的影響Fig.2　The effect of the number of attacked 3PL to the costs

5　結束語

本文研究考慮蓄意攻擊的4PL彈性網絡設計問題.構建了考慮蓄意攻擊的4PL網絡設計雙層優化模型.根據模型特點,設計了雙層優化算法(IPSDA/ILS)進行求解.最后,通過隨機產生的算例驗證了模型的合理性和算法的有效性.實驗結果表明改進的IPSDA/ILS算法優于PSDA/ILS算法,同時給出彈性和被攻擊3PL服務節點和運輸供應商對問題結果的影響,并進行了分析.

[1]Gattorna J.Strategic Supply Chain Alignment:Best Practice in Supply Chain Management.Hampshire,England:Gower Publishing Company,1998.

[2]陳建清,劉文煌,李秀.第四方物流中決策支持及物流方案的優化.計算機工程,2004,30(5):150–153. Chen J Q,Liu W H,Li X.Decision supporting system of the fourth party logistics and its optimization method of logistics solution. Computer Engineering,2004,30(5):150–153.(in Chinese)

[3]王勇,吳志勇,陳修素,等.面向第4方物流的多代理人作業整合優化算法.管理科學學報,2009,12(2):105–116. Wang Y,Wu Z Y,Chen X S,et al.Optimization algorithm for multi-agent job integration for fourth party oriented logistics.Journal of Management Sciences in China,2009,12(2):105–116.(in Chinese)

[4]崔妍,黃敏,王興偉.考慮中轉發車時間4PL RP的模糊規劃模型與算法.系統工程學報,2012,27(4):535–542. Cui y,Huang M,Wang X W.Fuzzy programming model and algorithm of 4PL RP considering travel schedule.Journal of Systems Engineering,2012,27(4):535–542.(in Chinese)

[5]Chen K H,Su C T.Activity assigning of fourth party logistics by particle swarm optimization-based preemptive fuzzy integer goal programming.Expert System with Application,2010,37(5):3630–3637.

[6]Peng P,Snyder L V,Lim A,et al.Reliable logistics networks design with facility disruptions.Transportation Research:Part B,2011, 45(8):1190–1211.

[7]Meepetchdee Y,Shah N.Logistical network design with robustness and complexity considerations.International Journal of Physical Distribution&Logistics Management,2007,37(3):201–222.

[8]Klibi W,Martel A,Guitouni A.The design of robust value-creating supply chain networks:A critical review.European Journal of Operational Research,2010,203(2):283–29.

[9]Liberatore F,Scaparra M P,Daskin M S.Analysis of facility protection strategies against an uncertain number of attacks:The stochastic R-interdiction median problem with fortification.Computers&Operations Research,2011,38(1):357–366.

[10]Scaparra M P,Church R L.A bilevel mixed-integer program for critical infrastructure protection planning.Computers&Operations Research,2008,35(6):1905–1923.

[11]Hollnagel E,Woods D D,Leveson N.Resilience Engineering:Concepts and Precepts.Aldershot:Ashgate Publishing Company, 2006.

[12]Wang D W,Ip W H.Evaluation and analysis of logistics network resilience with application to aircraft servicing.IEEE System Journal,2008,3(2):166–173.

[13]Ramirez-Marquez J E,Rocco C M.All-terminal network reliability optimization via probabilistic solution discovery.Reliability Engineering and System Safety,2008,93(11):1689–1697.

[14]Ramirez-Marquez J E,Rocco C M.Stochastic network interdiction optimization via capacitated network reliability modeling and probabilistic solution discovery.Reliability Engineering and System Safety,2009,94(5):913–921.

[15]Lourenco H R,Martin O,Stützle T.A beginner’s introduction to iterated local search//Proceedings of Meta-heuristics International Conference.Porto,Portugal:Springer-Verlag,2001:1–6.

Model for resilient network design of fourth-party logistics with proactive attacks considered

Li Rui,Huang Min,Zhang Ruiyou,Wang Xingwei
(College of Information Science and Engineering,Northeastern University;State Key Laboratory of Synthetical Automation for Process Industries(Northeastern University),Shenyang 110819,China)

Resilient network design of fourth party logistics with proactive attack is studied.A two-level optimization model for network design of fourth-party logistics is proposed,with the top-level model minimizing the total costs subject to the resilience constraint by determining the network topology and the down-level model maximizing the attack effect by selecting the attack strategy.A two-level optimization algorithm is developed to solve it,a probability solution discovery algorithm is used to solve the top-level model,and iterated local search is used to solve the down-level model.Finally,numerical experiments are presented and the results indicate the significance of the model as well as the effectiveness of the proposed algorithm.

fourth party logistics;network design;resilience;deliberate attacks;probability solution discovery algorithm;iterated local search

TP273

A

1 000-5781(2016)05-0657-09

10.13383/j.cnki.jse.2016.05.010

2013-09-22;

2013-12-16.

國家杰出青年科學基金資助項目(71325002;61225012);國家自然科學基金重點國際合作研究資助項目(7162010-7003);流程工業綜合自動化國家重點實驗室基礎科研業務費資助項目(2013ZCX11).

李銳(1985—),男,遼寧海城人,博士,講師,研究方向:物流優化,智能算法等,Email:rui850109@163.com;

黃敏(1968—),女,福建長樂人,博士,教授,博士生導師,研究方向:物流與供應鏈管理,生產計劃,調度與存儲控制,風險管理和軟計算,Email:mhuang@mail.neu.edu.cn;

張瑞友(1979—),男,遼寧遼陽人,博士,副教授,研究方向:建模與優化,物流系統等,Email:zhangruiyou@ise.neu.edu.cn;

王興偉(1968—),男,遼寧蓋州人,博士,教授,博士生導師,研究方向:計算機網絡等,Email:wangxw@mail.neu.edu.cn.