考虑蓄意攻击的第四方物流弹性网络设计模型

李　锐,黄　敏,张瑞友,王兴伟

(东北大学信息科学与工程学院;流程工业综合自动化国家重点实验室(东北大学),辽宁沈阳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.