1、1基于复杂网络的人道救援物流路径优化研究【摘要】 传统的人道救援车辆路径优化方法主要是用最短路径策略进行选择,容易造成重要交通节点的连接度过大、负荷超重引起堵塞的问题,本文从复杂网络的角度提出新的路径优化策略,在绕道时间和等待时间之间进行选择,通过调节变量 a 值来控制他们之间的关系,并运用 MATLAB 程序进行仿真分析,统计结果表明:当 a=1 时,整个系统存在帕累托最优解。新的路径优化策略为进一步提高人道救援物流效率提供了新的思路。 【关键词】 复杂网络 路径优化 人道救援物流 一、引言 人道救援物流复杂网络的研究是一门新的交叉学科,主要结合复杂科学、管理科学和计算机仿真技术。对于人道救
2、援物流路径问题的研究,目前已有学者将复杂网络理论引入到物流领域进行研究,如文献(俞峰,2009)系统研究了动态随机复杂网络的最短路径问题;文献(李靖、张永安,2011)在分析物流网络特征的基础上,探讨了引入复杂网络的合理性;文献(唐晋韬、王挺、王戟,2011)基于现实网络的拓扑特征,提出了一种适合于复杂网络的最短路径近似算法;文献(后锐、杨建梅、姚灿中,2010)利用复杂网络分析我国物流企业竞争关系网络,发现其具有小世界特征与无标度特征。但总体来看,公开发表的基于复杂网络理论来研究人道救援物流的成果仍然较少,而且这些研究通常是在考虑道路2边权的情况下,用最短路的方法来进行路径优化,忽略了各节点
3、的连接度和最大通行能力,很容易导致高连接度的节点负荷过重,从而造成交通堵塞。因此,本文主要从复杂网络的角度研究人道救援物流网络,通过分析节点度与交通负荷之间的关系,提出新的路径优化策略,旨在让人道救援车辆能够及时绕开连接度较高的节点,缓解因交通堵塞而引起的救灾延迟,提高救援效率。 二、人道救援物流网络的复杂性分析 复杂网络是指具有自相似性、自组织性、小世界属性、吸引子属性、无标度属性中部分或全部性质的网络。当前的主要研究方法是把各种复杂系统简化为节点以及连接节点的边的集合,其中系统的基本组成单位是各个节点,边则用来表示各个节点之间的相互联系,并通过计算机技术来分析网络上的相关指标,用这些作为代
4、表来描述整个网络的性质。 1、节点度和度分布 节点的度就是指与这个节点直接相连的其他节点的数目,用 ki 来表示。该指标的作用是来衡量节点在网络中的地位的,如果网络中有许多节点都直接与其中的一个节点相连,那么该节点就拥有较高的度,对整个网络的重要性也较高。 节点度是节点最基本的特性之一,通常更具广泛性的特征就是节点的度分布,通常是用来表示网络中度为 K 的节点在整个网络中所占的比例。如果一个网络中有 Nk 个度值为 k 的节点,网络中所有的节点数为N,那么度值为 k 的节点的度分布可表示为: 32、介数 介数主要是用来反映节点在网络中重要程度的指标,如果一个节点在其他许多点对的最短路径上,那么
5、该点的介数就较大,它起到网络中控制信息流的桥梁纽带作用。若假设节点 i 和 j 之间有 n 条最短路径,此时存在第三个节点 k,该节点在它们的最短路之间,且 n 条最短路径中有 n(k)条经过此节点,用 bij(k)来表示节点 k 对节点 i、j 之间来往的控制力,也就是 k 位于 i、j 最短路上的概率,则那么 bij(k)=。节点 k 的介数就是把节点 k 相应于网络中所有点对的中间度相加,可表示为:Ck=bij(k) ,ijk。 3、平均距离 网络中连接这两个节点的最短路径上的边权就是两节点之间的距离d,网络中任意两个节点之间的距离的最大值就是该网络的直径,通常记为 D,表达式为:D=m
6、axd。 平均最短距离是在进行复杂网络结构分析时最常考察的,可以理解为网络中任意两节点之间距离的平均值,可用公式表示为: 网络的大小在一定程度上是由网络的平均距离决定的。许多物理学家通过对现实的网络的研究,发现了大多数网络的平均距离较小的特性,这种现象被描述为小世界属性。通过研究发现,世界上绝大部分的复杂网络基本具有小世界属性和无标度网络结构特征,道路网络也不例外,这就为从复杂网络的角度来研究人道救援物流提供了可能。 4三、改进的最短路径策略 无标度网络存在显著的二八现象,体现的是一种非均匀的网络,就拿道路网络系统来说,80%的节点度值较小,只有 20%的节点度值较大,Yang 等通过研究认为
7、多数网络中节点的度值与介数正相关,即网络中度值较大的节点其介数通常也比较大,因此节点往往处在网络的中心位置,承载的负荷较大,容易形成交通堵塞。为了能够及时规避这些负荷较大的节点,提出新的路径优化策略:假设人道救援车辆需要从节点 s 运送救灾物资到节点 t,以其起始节点 s 为中心,搜索其邻近节点的度值和道路边权,接着以该邻接节点的度值与其所有邻接节点度值之和的比为权重调整起始点 s 与其邻接节点的距离,并以该距离为基准选择邻接节点,按照传统最短路算法(Dijkstra 算法)逐层向外扩展,直到扩展到终点为止。可用公式表示为: 其中,L 表示起点 s 到终点 t 之间的总距离;dij 表示节点
8、i 到节点j 的道路边权;kj 表示节点 j 的连接度值;k 表示与节点 i 相连的所有节点的度值总和。a 为调节系数,当 a=0 时,则车辆按最短路径行驶。 四、最短路径策略仿真设计 人道救援物流复杂网络是由一系列低连接度和高连接度的节点构成的,当自然灾害发生时,高连接度节点的交通流量较大,当负荷超过一定值就会形成交通堵塞,为了规避这些高连接度的节点,可以设置较高的 a 值。较高的 a 值虽然可以绕开连接度高的节点,缓解因交通堵塞而引起的救灾延迟,但是人道救援车辆的行车路程会因为绕道而增加,所5以应该综合考虑等待时间和绕道增加时间之间的关系,这样能够找到一个合适的 a 值,为人道救援物流车辆
9、路径选择提供决策支持。 为了找到合适的 a 值,本研究设计了一个仿真,在进行仿真之前,我们需要进行相关假设: 第一,道路网络符合 BA 模型,且可以由 BA 模型生成; 第二,计算机随机产生每辆车的起始点; 第三,网络中所有救援车辆的行车速度相等; 第四,Ci 为节点 i 的设计通行量,当车流量超过该值就会发生堵塞; 第五,如果节点发生堵塞,按先到先服务的原则处理车流量; 第六,相邻两个路口之间的距离为 L。 仿真流程描述如下:自然灾害发生之后,如何将救灾物资及时迅速的运往灾区,让受灾民众得到最快的救治是最重要的。在人道救援车辆出发之前,救援指挥中心需要根据已经掌握的信息来构建人道救援物流网络
10、,并通过数据分析与统计来了解该网络的各种属性;然后运用计算机技术模拟灾害发生时人道救援物流网络中产生的初始车流量,用 R 表示。其中,车辆的起始点是由计算机随机产生的,并以最短路原则来选择行使路径。接着,通过控制时钟,模拟车辆在该网络中的行驶,记录每个时刻每个节点的车流量,当节点 i 的瞬时流量超高其设计通行量 Ci 时,该节点发生堵塞,即满足: 其中 Li(t)表示节点 i 在时刻 t 的流量,V 表示时刻 t0 的瞬时速度。最后,用计算机随机生成一系列救援设施点和受灾点,通过设置不6同的 a 值模拟人道救援车辆在该网络中的行车路径,统计分析不同 a 值情况下人道救援车辆的平均行车时间,找出
11、最合适的 a 值,为人道救援车辆路径选择提供决策依据。 五、人道救援网络中最短路径策略仿真分析 假设各个节点的设计通行量如表 1 所示。灾害发生后,网络中的初始车流量为 R=10000 辆;路口之间的距离 L=50 米;网络中救援车辆行车速度 v=5 米/秒;网络的最长距离为 5,那么在没有发生交通堵塞的情况,整个仿真的时间为 50?5/5=50 秒。初始网络规模为 m=4,当网络的规模N=500 时,仿真结束。 运用计算机在 500 个节点中随机产生 1000 对救援设施点和受灾点,通过设置不同的 a 值,模拟人道救援车辆在网络中的救援路径,通过统计得到不同 a 值下的平均行车时间,具体数据
12、如表 2 所示。 由表 2 可知,随着 a 值的逐渐增大,人道救援车辆的平均行驶时间先逐渐降低后逐渐增加。人道救援车辆平均行驶时间的先降低是由于车辆在行驶过程中为了绕过高连接度的节点,避免交通堵塞造成的等待时间;但是随着 a 值的逐渐增大,人道救援车辆需要绕道的节点在逐渐增多,救援路程在一定程度上变大,所以平均行驶时间又开始增加。 为了验证 a=1 在其它初始交通流的情况下依然存在帕累托最优解,调节 R 的取值,重复做以上实验,得到的数据如表 3 所示。 7表 3 可以说明,无论 R 值如何变化,当 a=1 时,车辆根据新的路径优化策略在网络中行驶,所花费的平均行驶时间是最短的。 六、结论与展
13、望 本文将复杂网络理论引入到人道救援物流研究中,通过分析人道救援物流复杂网络的含义及特点,从而选择最贴近其特点的道路网络系统作为主要研究对象,并分析其属性。从规避连接度高的节点的角度出发,提出了一种新的路径优化策略,新的路径优化策略主要是在在绕道时间和等待时间之间进行选择,通过调节变量 a 值来控制他们之间的关系。运用计算机仿真技术,找出了存在帕累托最优解时 a 值是 1。 本文是在假设信息通畅和单目标的前提下做的相关研究,因此,在考虑信息局限性以及自然灾害对道路造成不确定性影响的前提下,从多目标决策和占线问题的角度对人道救援物资运输的路径进行动态选择将是下一步研究的重点。 【参考文献】 1
14、俞峰:复杂动态随机网络最短路径问题研究D.浙江大学,2009. 2 李靖、张永安:复杂网络理论在物流网络研究中的应用J.中国流通经济,2011(5). 3 唐晋韬、王挺、王戟:适合复杂网络分析的最短路径近似算法J.软件学报,2011(10). 4 后锐、杨建梅、姚灿中:物流产业竞争关系复杂网络模型研究J.管理学报,2010(3). 85 JianmeiYang,LvpingLu,WangdanXie,GuanrongChen,Dong Zhuang:On competitive relationship networks:A new method for industria competition analysis J.PHYSICAA,2007(382). 6 李建春:构建生命权利高于一切的灾害应急物流体系研究J.学术论坛,2014(5). (责任编辑:陈丹)