一种基于演化模型的应急服务网络优化方法

邓菊丽 王艳 陈国荣

(1. 重庆科技学院化学化工学院， 重庆 401331； 2. 重庆科技学院智能技术与工程学院， 重庆 401331)

0 前言

应急管理是指政府及其他公共机构在突发事件的事前预防、事发应对、事中处置和事后善后恢复过程中，通过建立必要的应对机制，采取一系列必要措施，应用科学的技术规划与管理等手段，保障公众生命、健康和财产安全，促进社会和谐健康发展的有关活动。由于应急网络规划布局不够合理，我国现有的应急服务中心和应急物流基地，服务效率并不高。同时，盲目投资兴建各种功能大而全的应急服务基地的情况还时有发生，造成社会资源的浪费。我们应该从全局的角度规划应急服务网络的布局，避免社会资源的浪费，提高应急救援效率和事故应对效率。关于应急服务网络规划和建设，学者们主要从应急服务网络建模和服务基地的选择等方面作了研究。

(1) 应急服务网络建模方面的研究。赵林度等人构建了基于弹性的城际重大危险源应急网络协同机制，并分别从风险弹性、信息弹性、资源弹性的角度对城际应急网络的协同弹性水平进行了研究[1]。宋琪通过对地震应急协同物流网络进行复杂系统分析，建立了多Agent模型结构及Agent交互规则[2]。陈涛等人以北京为例，开展了城市运行与应急管理技术架构与应用模式研究，提出城市运行和应急管理融合的技术框架[3]。李阳研究了面向城市应急管理的情报能力建设问题[4]。

(2) 应急服务基地的选择方面的研究。陈国荣等人基于对应急物流的研究，提出了一种基于成长的物流网络建模方法[5]。郑斌等人以汶川大地震应急物资配送为背景，设计了一种震后应急物流动态选址-联运问题的双层规划模型[6]。王沛等人结合商品车运输“库前移”模式的运作特点，开展了基于“库前移”模式的铁路商品车物流基地分层动态选址优化研究[7]。刘洁研究了铁路乘用车物流基地作业区布局优化研究[8]。

上述方法的不足之处是，对于网络的规划和研究基本上停留在应急服务基地结点数量和应急网络连接保持固定不变的状态，不能适应网络规模不断成长和网络结构变化的趋势。文献[5]中提出了一种基于成长的物流网络建模方法NGM(Nodes Growing Model)，解决了应急物流网络成长过程的建模问题。

本次研究是在文献[5]的基础上，通过施加一定的扰动，使网络产生形变，从而得到一种新的演化效果。通过比较演化情形，从中获取一种较优的应急服务网络效果，以实现网络的最优控制。

1 应急服务网络的演化模型

考虑应急服务网络的实际情况，假定所研究的网络不存在结点自身到自身的连接，也不存在2个结点之间的重复连接。另外，本次研究中对边的删除只是基于网络图的正常演化过程，不考虑网络图的突变。

1.1 基于优先连接和赋权边的结点增长模型

结点的增长参考了文献[5]中提出的成长模型，算法如下：

(1) 产生第1个结点。根据产业需求建设第一个应急服务基地，并将其作为网络第一个结点和起点。

(2) 产生第2个结点。由于更多应急服务需求的增加，决定在该地建立新的应急服务结点，两个结点之间用一条边连接起来。

(3) 随机化增加结点。异地应急服务需求的进一步增加，产生更多的结点。

(4) 基于优先序和赋权边的网络连接，新结点与已知结点i通过带权的路径相连接的概率Pi、结点i的度ki、权重ri之间满足式(1)：

(1)

其中

新结点与原有网络中结点，按照Pi从大到小的顺序连接；t为结点度和边的权重调节参数，0≤t≤1，其值取决于实际网络的具体需求。权重越大，该路径在网络中的重要度、两结点的相关度、被选择连接的可能性就越大。

上述算法构造的网络成长过程如图1所示，其成长网络度分布服从式(2)规律：

P(k，r，t) ∝2n2(ktr1-t)-3

(2)

式中：n为网络结点的总数；k为结点的度；r为边的权重。

图1所示为向有19个结点的网络中增加1个结点的情况。其中，应急服务网络具有幂率特性，按照指数规律进行成长。需要讨论的是，这种成长方式是否是我们需要的，以及应该从哪些方面进行优化。

1.2 增长型演化过程的加边效应

定义1：当图G中的任意两结点i和j之间需要增加新的连接边时，必须考虑择优原则，即新增加的连接边必须使得网络图中任何两结点之间的距离更短。

图1 向有19个结点的网络中增加1个结点

网络中各结点的度分布如式(3)所示：

K=[k1，k2，…，kn]

(3)

网络中结点之间的距离dui如式(4)所示：

(4)

且

(5)

忽略结点本身对边权重的影响，并假定边的成本为权重的倒数。在定义1的基础上，如果网络图G中的结点u需要增加一条边，并给定了新增连接边的边权重r，则由式(1)得式(6)和式(7)：

(6)

Pa=max{Pui}，(0

(7)

因此，边的增长过程如下：

(1) 确定需要增加边的结点u。

(2)计算网络中各结点到结点u的距离dui。

(3)按照式(6)计算并确定与结点u相连的max{Pui}，(0

(4) 比较rui和r的关系，考查有无增加连接边eui的必要。如果rui>r，则结点u和结点i之间的连线eui即为网络图中新增加的边，且增加新边后的网络图的度分布为：K=[k1，k2，(ki+1) ，…，(ku+1)，kn]。如果rui≤r，即新增边的重要度不够，则增加新边不能对网络产生优化效果，因而没有必要增加这一条重要度为r的边。

(5)如果结点u和结点i之间出现重边，则删除边eui。

基于上述步骤，对结点C17增加边，如图2所示。

1.3 蜕化型演化过程

定义2：当图G中的任意两结点i和j之间需要删除连接边时，必须考虑择劣原则，即每次被删除的边的重要度对于给定结点rij为最低。

本次研究中，对于边的删除不考虑网络图的突变，而是仅基于网络图的正常演化过程。从定义2可看出，删除边与增加边的计算过程相同，只是边eui所对应的结点u和结点i的连接概率Pd由概率矩阵集合中的最小值min{Pui} 确定，即

Pd=min{Pui}，(0

(8)

综上所述，边的删除过程如下：

(1)确定需要删除边的结点u。

(2)计算网络中各结点到结点u的距离dui。

(3)按照式(6)计算并确定与结点u相连的Pd。

(4)删除连接概率Pd对应的边eui，更新结点度的集合K=[k1，k2，(ki-1) ，…，(ku-1) ，kn]。

(5)如果删除eui后出现孤点，则将相应的结点一并删除，并更新结点的集合和结点总数n。

基于上述步骤，删除结点C19与C2之间的连接边，如图3所示。

图3 对结点C19删除边的过程

1.4 平衡演化过程

前面着重强调了结点增长型演化过程和结点蜕化型演化过程。但在实际情况下，不断有新的结点加入现有的应急服务网络，也不断有旧结点蜕化和消失，因而整个网络在不断发生动态变化。很明显，应急服务网络满足耗散结构体的基本特性，因而具有耗散结构的相关特性。即，网络的平衡属于动态平衡，需要外界的输入和输出予以供养。

为了判断网络是否达到平衡，下面定义结点的熵变dA。

定义3：对于给定的结点，如果市场需求变化为dD，结点所能供给的需求变化为dS，则该结点的熵变dA可通过式(9)来计算：

dA=dS-dD

(9)

定义3表明，熵变dA是网络与外界之间进行物质和能量交换的结果。其中，dD为市场的需求变化，可正可负。如果dD为正，表示应急服务需求呈增长态势；反之，如果dD为负，表示应急服务需求可能萎缩。dS为结点的供给能力，对于一个给定的结点来说，其能力有一个最大限值dSmax，超出此限值时给定结点将无法满足市场的需要；然而，如果市场需求远不能满足该结点的能力，由于成本等因素的影响，可能会运行不下去。

上述结果最终表现在熵变dA上。一方面，如果dA>0，意味着网络具有较好的增长动力；且当dA≫0时，结点很有可能发生突变，产生新结点和新边。另一方面，如果熵变dA<0，说明该结点无法达到预定的运行效果；且当dA≪0时，结点及其相应的边入不敷出，进入蜕化程序在所难免。

2 仿真实验分析

为了验证本应急服务网络建模方法的正确性，我们建立了一个实验网络模型。考虑结点增长效应，向结点数为19的网络中增加1个新结点，即第20个结点，其有关数据如表1所示。表1中，R为新增结点边权重；K19为结点C19的度；Kr为基于边权重的演化网络；Kk为基于结点的度的演化网络数；Kr，k为基于边权重和结点度的演化网络数；Pr为基于边权重的演化网络加边概率；Pk为基于结点度的演化网络加边概率；Pr，k为基于边权重和结点度的加边概率；Cr为基于边的聚类系数；Ck为基于结点的聚类系数；Cr，k为综合聚类系数。

由表1中的数据以及式(2)可知：赋权化的网络度分布为幂指数方程，因而该模型建立的网络属于幂律分布网络。

由式(1)和(2)可知，尽管新结点的连接倾向于选择“富”结点，但由于边权重因素的影响，优先连接的现象也非常普遍。当t= 0时，结点的度无关紧要，起决定作用的是边的权重；当t=1时，网络中结点的重要性完全取决于结点的度；当 0

表1 第20个结点后参数值的变化情况

注：加背景底纹的数值表示该列极大值，即具有优先连接特性的结点；带“*”数字为该列极小值，即优先退化边

根据定义2所述的择优加边原则，与结点u相连接的结点i的概率Pa，由概率矩阵集合中的最大值max{Pui}，(0r，结点u和结点i之间的连线eui即为网络图中新增加的边，且增加新边后的网络图的度分布为：K=[k1，k2，(ki+1) ，…，(ku+1) ，kn]；如果rui≤r，则新增加的边的重要度不够，表明增加新边不能对网络产生优化效果，因而没有必要增加这一条重要度为r的边。由于式(6)与式(1)一样，都考虑了边的权重和结点的度，因此，增加新边后网络的结构仍然保持为层次结构。考虑加边效应，在选择结点时，选择结点C5的可能性最大(见图2)。

根据定义2所述的择劣删边原则，与结点u相连接的结点i的概率Pa，由概率矩阵集合中的最小值min{Pui}，(0

定义3考虑了市场的需求和网络结点的供给能力，给出了网络增长和蜕化的动力，因而对网络的结构不会产生破坏作用。

3 结 语

针对应急服务网络的发展规律，提出了应急服务网络的演化模型：

(1) 对于结点的增长过程，提出了应急服务网络的成长模型，给出了定量和定性的计算方法和结点增长步骤。

(2) 对于边的增加，推导了基于择优原则的边增长定量计算方法。

(3) 考虑到边和结点的删除情况，给出了基于择劣原则的边和结点的删除过程。

(4) 考虑网络的平衡演化过程，建立了网络的耗散结构模型。

对上述方法进行仿真，结果表明该建模方法符合应急服务网络的实际情况，边和结点的变动不会影响应急服务网络结构的稳定发展。