考虑位置信息的物流配送网络节点重要性评估

张 俊，李义华，罗大庸

1.中南林业科技大学 物流与交通学院，长沙410086

2.中南大学 信息科学与工程学院，长沙410075

1 引言

物流配送都是物流过程重要的作业环节。空间分布不同的各个物流配送中心通过网络实现信息共享。物流企业就能根据货物实际运输线路和装载情况对运输车辆安排合适的配送中心就近进行中途货物补载或调配，提高配送和运输的合理化。基于这种考虑，不仅物流配送中心的选址十分重要，而且建立的配送中心的规模设计更加重要。以零售业物流为例，仅在同一个城市就会设置多个配送中心。这些配送中心通过网络通信进行数据资源的共享，形成一个专门的物流配送中心的网络系统。

目前研究物流配送网络的研究方法有如下两种。一种是基于运筹学为理论基础，研究配送网络系统的节点选址、路径优化等问题[1-3]；第二种是基于复杂网络系统为理论基础，研究配送网络的网络特性、鲁棒性等问题[4-6]。综合前面所述，本文将采用第二种方法来分析和研究物流配送网络的节点评估问题。借助图论和复杂网络理论，每个配送中心视为一个网络节点，根据实际货流量大小，评价出整个配送网络中关键节点，有助于帮助企业合理设置物流配送中心的等级，能对物流配送中心的容量及时调整，特别是一些有零担运输业务的商家需要在各个物流配送中心进行货物中转、调运，提高配送有效性。在实现物流配送的过程中，货运量和运输距离是影响其配送网络节点的关键因素。

应用复杂网络进行节点重要性分析，在化工、生产制造等领域都得到较多应用，关于物流领域的研究成果较少，涉及有向加权网络节点评估的研究就更少。如文献[2]分别通过不同算法计算出快递网络的配送时间、货运中转量、运输费用等，构建具有配送时间约束和节点最大流量约束的网络模型，逐层得到成本最小的结果。文献[5]针对快递的订单数据，构建企业配送网络的拓扑结构，运用重要度评价矩阵确定重要节点，提出优化对策;文献[6]定义了节点重要度贡献矩阵，验证节点之间重要性依赖关系，且依赖关系与节点邻近的位置相关，并根据构建的贡献矩阵确定网络中的重要节点。鉴于配送网络具有复杂网络的特性，可借鉴复杂网络的一些研究成果[7-15]。如文献[7]综合考虑节点效率、节点度值和相邻节点的重要度贡献，利用重要度评价矩阵来确定复杂网络关键节点；文献[8]将卫星时变拓扑网络分解成一系列稳定状态的拓扑图结构，综合考虑节点介数、节点紧密度和节点距离的重要度贡献，设计网络节点的重要度评估算法，评估出网络拓扑图中各节点的重要度；文献[9]借鉴通信系统中“信息量”的定义方法，分析特殊条件下网络的特征属性，提出一种有向加权网络的节点重要性评估方法，挖掘出网络中的核心节点等；文献[10]基于网络模型构建三个影响力矩阵，依据交叉强度指标分析节点;文献[15]针对pert网络，优化网络得路径积关键性的指标。

在以往的物流配送过程中，节点分析都建立在货运信息的基础上，但很多没有考虑方向性问题，更未考虑其权重关系。同时，物流配送还受其他因素的影响，例如距离的远近、节点就近性等。很多文献资料中并未将相关因素纳入考虑范围。

综合上面的描述，本文将在复杂网络的理论分析方法的基础上，从物流配送网络自身的特点考虑，提出节点交叉信息的概念，同时还考虑运输成本，加入节点间的位置信息等因素，更具实用价值。综合考虑更多关键因素，构造节点重要性评估因素的相关矩阵来共同分析和评估一个物流配送网络中关键节点的重要度问题。

2 有向加权的物流配送网络关键因素分析

对于一个物流配送网络，配送节点的重要性与其货运信息、地理位置等因素息息相关，可以用相关影响因素的矩阵来表述。基于相似权原则，下面将逐一对这些因素进行分析，讨论其对节点重要性的影响。

首先，对一个物流配送网络的模型进行描述。具体的模型和相关符号说明如下：首先一个物流配送网络模型用G=(V,E)表示。其中，V={v1,v2,…,vn}是网络模型各个节点集合，E={e1,e2,…,em}是网络模型的边集合，见图1所示。

图1 配送网络示意图

图1 中，节点1 至节点n 分别表示若干个物流配送点。每个节点之间通过有向的边进行连接起来。假设以节点i 为研究节点，节点j 为邻接节点，考虑网络的有向加权问题，即在节点i 和j 之间，w(i,j)表示有向边(i,j)的权值，w(j,i)表示有向边(j,i)的权值。一般来说，w(i,j)≠w(j,i)。每个节点的位置坐标为（Px,Py）。

2.1 配送节点间货运量信息分析

货运量直观地视为货物信息从该节点流入流出的情况。即，货物从一个供应点运输到目的节点，涉及到其运输路径的选择，还可能会途经其他节点。另外，配送过程中会出现配货点缺货问题，需要从调配节点向缺货节点完成货物调配。同时，考虑到物流配送网络中节点间货运信息存在方向的差异性，信息大小不对等，将配送网络中的双向链路转化为两条方向相反的单向链路进行分析，实现一个复杂网络模型从传统的无向无权的网络结构转化为一个有向加权的网络结构。

在物流配送网络中，边的权重视为货运信息流即数据流，每个节点所包含的信息量来代表节点的重要程度，不同方向上传递不同的信息量，分析网络的加权互信息。从相似权原则出发，即认为连边的权重越大，表示物流配送网络中两个配送节点之间的货运信息越大，关系越亲密。以节点i 为例，节点强度视为其连接边的有向权值之和，包含该节点的S(i)=Sin(i)+Sout(i)。其中，是节点i 的出强度，Sout(i)=

进行节点重要性评估之前，根据货运信息的方向将图1的网络结构划分出两层网络，以节点i 为研究节点，配送网络划为以节点i 为出点的一层网络和以节点i 为入点的另一层网络。先定义节点的出边概率和入边概率以及有向信息，具体如下。

定义1 对从节点i 指向节点j 的有向边(i,j)，则定义节点i 的出边概率为：；该节点j 关于来自节点i 的入边概率为。令节点i 与节点j 之间的互信息为I(i,j)。 I(i,j)包括了节点i 指向节点j 的互信息，定义其为如下形式：

定义2 对于从节点k 指向节点i 的有向边(k,i)，则定义节点i 的入边概率为：；该节点k 关于来自节点i 的出边概率为。令节点i 与节点k 之间的互信息为I(w,i)。 I(w,i)包括了节点w指向节点i 的互信息，则定义其为如下形式：

定义3 令节点i 的信息量为I(i)，该信息量既包括节点i 指向其他连接节点的互信息（输出信息），也包括其他连接节点指向节点i 的互信息（输入信息）。

仅标识该节点的输出信息和输入信息无法区别两者的差别，也无法突出显示该物流配送网点的主要功能。针对这一问题，本文结合有向的互信息提出节点交叉信息的概念，即：

其中，Vout(i)代表节点i 指向的所有节点集合，Vin(i)代表指向节点i 的所有节点集合，λ ∈(0,1)是一常数，它的不同取值会影响不同节点的信息量，导致配送节点的重要性评价结果不同。

从定义1～3 可知，通过计算后，所有节点的信息量可按照从小到大进行排列，信息量越大，代表该节点的重要性越大。节点的信息量大小不仅与其自身出强度有关，还与其入强度有关。只要总强度越大，代表与该节点相关连的信息传递越多，表示该节点越重要。在一个物流配送点，货物的输出信息量更能反映该节点的重要性。就好比一篇学术论文的他引次数比起该篇论文引用他人的论文次数更加反映出这篇文章的重要性等。采用交叉信息是在节点互信息的基础上进行扩展，作为衡量节点重要性的一个局部指标。λ 的引入可以用来衡量一个出度很大而入度为0 或入度很大而出度为0的节点重要性，也更加可以用于评价有向加权网络中各节点重要性。

2.2 配送节点的位置信息分析

配送网络中各节点的位置影响了节点之间的传输路径。令节点i 的位置坐标为(Pxi,Pyj)，节点j 的位置坐标为(Pxj,Pyj)，则根据位置坐标可确定两节点的距离Dij，决定配送系统的最短传输路径。配送网络中各个节点通过有效途径传播各自的影响。需从两个方面去考虑，一方面是如果一个配送节点与其他配送节点的位置距离越接近，则该配送节点可提供的货运和调配的可能性就越大，表明该配送点的紧密度越高，其在网络中的地位也更重要；另一方面从网络拓扑图看，从发出节点到目标节点的最短路径中会经过其他节点。如果一个节点的最短路径条数越多，意味着路径过程中关联节点可能更多。

（1）配送节点的紧密度分析

定义4 假设一个物流配送网络具有n 个节点，其中第i 个配送节点的紧密度Ci到达其他配送节点的平均距离倒数，即为该配送点的紧密度，表示为：

其中，dij表示节点i 和节点j 之间最短路径。若节点i和节点j 之间没有可通路径，则dij→∞。节点通过其与网络中其他节点的紧密关系来反映其在整个网络中的地位重要程度。

（2）配送节点的介数分析

在物流配送过程中，如果节点A 和节点B 之间有k条不同的最短运输路径，其中如果有b 条经过节点i，则说明节点i 在节点A 和节点B 的最短路径中的重要性为比值。这个比值越大，说明节点i 越重要，反映节点的“桥梁”作用。从实际意义的角度出发，这也符合现实物流配送流程，在一定程度上有利于节约运输资源，降低运输成本。

从前面所述，本文考虑配送网络中各节点介数。假设从节点i 到节点j 进行配送，则节点介数具体表示为。其中，Nij表示节点i 和节点j 之间的最短路径条数，Nij(l)表示节点i 和节点j 之间的最短路径经过节点l 的条数。为了区别以往对节点介数的定义，下面重新定义一个节点在整个网络中的介数特性。

定义5 假设一个物流配送网络具有n 个节点，会形成n×n 条有向配送路径。令该配送网络中第l 个节点的介数为：

其中，i=1,2,…,n，j=1,2,…,n，l=1,2,…,n。

3 物流配送网络节点关键性排序算法

根据第2章的描述，一个物流配送网络的节点关键性结合信息论和图论，选择节点的互信息描述节点的物流量，节点的紧密度来描述节点的位置信息以及节点介数来描述节点间的关联性。

综合上述的三种影响因素，可以得到节点关键性评估矩阵见式（6）。式中，矩阵H 专门针对物流配送网络进行关键节点分析，对计算公式进行新的诠释。该算法在网络连接边有向加权的基础上既考虑节点自身的位置信息，还考虑节点间互相的影响，更加引入配送网络中各配送节点之间的货物量情况。

综合节点的全局重要性和局部重要性，使算法更适用于分析物流配送网络的真实情况。通过对矩阵H 分解，则该物流配送网络中各节点的关键性评估值为：

据此算法得到的配送节点的重要性排序结果能提供更有效的指导作用。下面给出一个物流配送网络节点关键性的算法步骤。

步骤1 划分一个物流配送网络范围，提取一定运作时期内的网络拓扑图，确定n 个配送节点。

步骤2 计算物流配送网络在稳态下的节点重要度排序。

For i=1 to n：计算网络中所有节点对之间的最短距离dij，根据式（4）计算每个节点的紧密度Ci。计算节点的互信息I(i)和介数Bi。

步骤3 将步骤2 中计算得到各节点的影响因素带入式（7），计算节点关键性评估矩阵H 。

步骤4 根据步骤3，计算其中每个节点的关键值HI(i)（i=1,2,…,n）。

4 验证

例1 首先以文献[12]中图1的有向加权网络为例进行进一步讨论。在文献[12]中，网络考虑节点之间方向和互信息，但是节点间的边的长度没有考虑其中。

在本例中，加入边信息，即图2和图3中括号里参数所示，用来表示节点间的距离。根据本文方法对网络中的网络节点的重要性进行计算，并进行对比分析。

图2 等边距离的对称结构型有向加权网络拓扑

图3 不等边距离的对称结构型有向加权网络拓扑

以图2 为例子，对网络参数进行说明。单以节点3为例，计算节点3的I(3)、C3和B3。（1）计算I(3)。需要根据2.1 节先计算节点3 的出强度Sout(3)=3 和入强度Sin(3)=5，得到总强度S(3)。然后根据式（1）和式（2）计算节点3 与其他节点间的互信息I(3,j ，I(k,3 ，其中j ∈Vout(3)，k ∈Vin(3)，再根据式（3）将节点入信息和出信息进行加权处理，此处λ 取值0.8，得到节点3 的信息值I(3)=7.64。（2）计算C3。事先确定网络总节点数量n=10，再计算节点3 到各节点的最短距离d3j，根据式（4）得到C3。（3）计算B3。首先确定网络总节点数量n=10，再逐一列出各节点之间的路径条数，从其中计算出通过节点3 的路径数量为18 条，根据式（5）得到B3=0.18。（4）依据（1）、（2）和（3）的计算方法，依次计算出其他网络节点的相关参数。（5）根据前面已得的各参数，进行归一化处理，计算出式（6），得到节点重要性评估值。

图2 基于等位置距离的前提下得到的网络节点的重要性排序经过计算与文献[12]中图1 的计算结果（两者的网络拓扑结构完全相同）进行对比可知，本文中提出的新的网络节点关键性评估方法是有效的。而在实际的物流配送网络中，配送节点的实际位置距离是不相同的（见图3 中括号所示），就会影响相关节点的关键性。换句话而言，位置距离较短的配送节点具有更大的优先被选择的优势，其在整个配送网络中的地位就更加重要。因此，本文中提出的方法考虑节点的位置信息，将配送节点的关键性排序更加具体化和细化，在表1的最右一竖列已一一列出。对比表1 中前两个竖列的排序结果，处于网络拓扑具有对称位置结构的节点也进行关键性排序，如节点1和节点9，节点2和节点10，节点5和节点6都分别进行前后排序，更加验证本文中提出的排序方法比文献[12]的方法更加合理。

表1 各方法对对称结构网络节点进行重要性评估排序

例2 本例以文献[9]中的图1 为基础网络模型。该模型是一个包含10节点的混合加权网络。在此将其转换为有向加权网络，见图4。

图4 混合加权型非对称网络模型

图4 中考虑各节点间等距离和不等距离这两种情况，在图中用括号表示，形式如（1/*）。等边距离的情况下图4的网络模型与文献[13]的图1模型相同。根据图4提供的两种情况，采用本文中提出的方法分别计算图4中各节点的关键性，并进行排序比较，见表2所示。

文献[13]利用总强度法对网络各节点进行关键性排序。该方法容易出现关键性评价值相同的情况而无法区分相应的节点，例如节3 和节点4 的总强度都是5.5。且对于潜在节点的关键性无法准确评估。文献[9]基于互信息理论，结合节点自身强度、节点之间的强度使得节点的差异性更为细化，但是不能保证在任何条件下都能做到完全区分。本文不仅结合节点自身强度、节点之间的强度，而且还赋予两种强度的权重比例关系。同时，还充分考虑节点间的位置信息，分析节点间距相同和不等的两种情况下网络节点关键性的评估值并进行相应排序。从网络拓扑图上来看，节点3、4和8 处于网络节点链接位置，应该比较重要，排序相对靠前。文献[13]中这几个节点排名较靠后，文献[9]中节点3的排序也较靠后，其与靠前一个排序的节点评估值相差较大。采用本文方法，在等距条件下节点2、3、4、6和8 排序靠前。这几个节点都处于网络拓扑图的节点链接位置，一旦出现其中任何一个节点处断了，会造成整个或较大局部的网络不能连通。特别是节点3、4 和8，会造成整个网络不能连通。本文方法结合了节点的互信息量以及节点的位置信息，通过计算验证本文的算法简单有效，而且更加符合物流配送网络结构的实际情况。

5 小结

本文针对配送网络，构建其网络拓扑图，综合考虑节点间的位置信息以及物流信息量，借助复杂网络的理论分析手段，对其互信息、紧密度、介数等特征进行分析。相比以往的物流配送网络结构研究中，大多数的文献只考虑货运信息量或者是运输距离，在很大程度上没有考虑两者均共同影响物流配送网络中各节点的影响力以及有向性问题。基于上述考虑，借鉴总强度法，一方面考虑配送节点间货运的互信息量并进行加权处理各自节点的出强度和入强度的权重比，另一方面考虑配送节点间距，以及节点的介数特性，满足物流配送过程路径最短原则以及货物组装联合运输的需要，提出一种新的节点关键性评估方法。并对该方法进行对比验证和优势分析。结果表明该方法能够有效地排列出节点关键性，有利于进行中心性评估。对于实际的物流配送中心的网络结构，有利于分析其网络的复杂性，帮助每个配送中心合理有效地进行货物储备和调配，提高配送中心的效率，具有有效可行的应用指导意义。

表2 各方法对不对称结构网络节点进行重要性评估排序