近几年，在我国突发性的自然灾害及人为的社会动荡事件时有发生，造成很大的生命及财产损失，严重影响了人们日常生活水平的提高及国民经济的增长，大大阻碍社会的发展。因此我国非常重视应急预案的制订，在全国各地都储备了大量应急物资，希望在发生自然灾害后能最大程度地降低损失，使受灾地区及时得到救援。对于发生自然灾害或人为社会动荡后的应急物资配送问题，国内外许多学者^{[1, 2, 3, 4, 5, 6, 7]}也做了相关研究，给政府及相关决策单位在发生灾害后选择配送路径时提供很大帮助，这在很大程度上减小灾害带给我们的生命和财产损失，及时制止了一些人为的社会动荡。但是这些研究成果大多数假定运输路径的相关权值为确定变量，事实上很多时候对于路径的走行时间、运输风险等相关变量经常在某个范围波动，无法给出一个确定的值，因此必须研究模糊环境下的应急物资配送问题。

本文考虑模糊环境下应急物资配送路径优化问题,建立应急物资配送路径机会约束规划模型^{[8, 9]},利用混合智能算法来求解。 1 模糊环境下应急物资配送模型 1.1 模糊环境下应急物资配送问题描述

本文以配送路径的走行时间与路径风险最小化为目标，那么模糊环境下应急物资配送路径优化问题可以表述为：网络G=(V,E)中，
V为节点集,E为节点间的有向弧的集合。V=n,E=m,V={v₁,v₁,…,v_n},E={e₁,e₂,…,e_m}。对于图G中的每一条弧e=(v_i,v_j)，v_i,v₂∈V。设起点为v₁,终点为vn，任一条弧(v_i,v_j)∈E上赋有二维目标向量r(i,j)=(r^(i,j)₁,r^(i,j)₂)，其中,r^(i,j)₁为弧(v_i,v_j)的走行时间； r^(i,j)₂为弧(v_i,v_j)上的路径风险。

设决策变量 x_ij=1表示边(i,j)在1→n的路径上 0表示边(i,j)不在1→n的路径上，则路径x所需的总时间及总风险可以用式(1)、式(2)表示：

点击浏览公式

点击浏览公式

假定ξ是一个模糊变量，它的隶属函数为μ(x)，r是一个实数。那么模糊事件{ξ≥r}的可能性和必要性可分别用式(3)和式(4)来表示：

点击浏览公式

点击浏览公式

从式(3)和式(4)可以看出，当一个模糊事件的可能性是1时，该事件未必成立。当该事件的必要性是0时，该事件也可能发生。因此引出了可信性测度的概念：模糊事件的可信性(Cr)为该模糊事件可能性和必要性的平均，即：

点击浏览公式

点击浏览公式

对于模糊变量的比较，相关学者做了大量研究，给出了很多不同的比较方法，这里介绍Liu^{[11, 12]}给出的模糊数的比较方法。设ξ和η为两个模糊变量，可采用下面的方法比较它们的大小。

(1)对于某个置信水平r0，若Cr{ξ≤r0}>Cr{η≤r0}，那么有ξ>η，式中，Cr为模糊环境下使得模糊事件成立的可信性。

(2)对于某个置信水平α∈{0,1}，若ξinf(α)>ηinf(α)，那么有ξ>η，式中ξinf(α)和ηinf(α)分别为ξ和η的α－悲观值。 1.3 模糊环境下应急物资配送机会约束规划模型

根据对模糊环境下应急物资配送问题的描述，可以看出走行时间和路径风险均为模糊变量，当模型中含有模糊变量时，传统的优化算法不能用来解决此类问题，在期望值模型被提出之后，Charnes和Cooper^[8]于1959年提出了第二类随机规划，即机会约束规划。

这里所选择路径的走行时间、路径风险能够满足一定的置性水平，那么模糊环境下应急物资配送问题的机会约束规划模型^[4]如式(7)所示：

点击浏览公式

为解决上述模型，我们使用基于优先权的染色体编码方式^[10]。在网络中的每一个节点给定一个不同于其他节点的优先权，因为优先权的不同，便选择不同的节点，进而构建一条完整的路径。针对本文的问题，基于优先权的编码方式可以作如下描述：如果问题中有n个节点，令N={1,2,3,…,n}，令pi表示节点i的优先权，它是N中的一个随机整数，且pi应满足下列条件：pi≠pjpi,pj∈N，i≠j，i,j=1,2,…,n。基于优先权的编码形式可定义为：[p1,p2,…,pn]。

因此可以下面的图 1表示基于优先权的染色体编码：

图1 基于优先权的编码 Fig. 1 Priority-based coding

图选项

图 1给出了本文所讨论问题的基于优先权的编码方式，但是对于选择路径的决策者来说，需要的并不是各个节点的优先权，而是一条完整的路径，因此还需将染色体进行解码。这就需要根据可供选择的各个节点的优先权，从节点1开始，不断将一条条的边添加到路径中，直至找到一条从节点1至终点n的完整路径。

下面给出得到一条完整的路径的具体步骤：

Step 1：定义一个二维数组solution[2] [n]，用于存储各个节点编码及节点的优先权；

Step 2：数组solution[2] [n]的第一行依次赋值1,2,3，…，n；

Step 3：给数组solution[2] [n]的第二行依次赋值，其值为[1,n]中的随机数pi，且pi≠pj，pi,pj∈N，i,j=1,2,3，…,n,且i≠j；

Step 4：定义数组route[i]=k,令route[i]=0,i=1,2,3,…，n；

Step 5：定义变量i,k，令i=1,k=1；

Step 6：令route[i]=k，找出与route[i]相连并具有更高的优先权的节点k，令i=i+1；

Step 7：判断k是否等于总的节点数n，若k≠n,返回step 6，否则，转step 8；

Step 8：route[1],route[2] ,…,route[i－1]的值代表 1→n一条完整的路径。

图 2为一个8节点的网络图，图 3为此网络图中各个节点优先权的编码，那么产生一个初始解的具体步骤如下。首先，寻找和节点相邻的节点，节点2、3、4都满足要求，但从图 3可以看出节点2的优先权最高，所以我们选择节点2纳入路径，用同样的方法找到下一个可行节点集，重复上述操作，直至找到一条完整的路径1→2→5→7→8。

图 2 8个节点网络图 Fig. 2 Network with 8 nodes

图选项

图 3 8个节点网络图基于优先权的编码 Fig. 3 Priority-based coding of network with 8 nodes

图选项

(1)针对上面建立的机会约束规划模型，由于两个目标函数的单位不同，因此需对两个目标函数进行无量纲化处理，从当代种群中选取走行时间和路径风险的最大值和最小值，分别记为：Amax，Amin，Bmax，Bmin。那么对每个染色体所代表路径的走行时间和路径风险进行无量纲化处理的公式如式(8)、式(9)所示。为使分母不为零，式中引入一个很小的正数ε。 走行时间无量纲化处理公式为：

点击浏览公式

点击浏览公式

将两个目标无量纲化处理后，还得将多目标化为单目标。这里引入目标权重，化多目标为单目标后得到新的目标函数如式(10)所示：

点击浏览公式

经过上述处理，就得到了一个新的单目标函数，因此适应度函数可以构造成式(11)的形式：

点击浏览公式

最后，根据各个个体的适应度值大小，使用改进的轮盘赌法确定进入下一代种群的个体。改进的轮盘赌法在选择新个体时，首先在当前种群中随机选择一个最优的个体直接进入下一代，其它个体的选择根据其适应度大小，用轮盘赌方式决定是否进入下一代。例如，设当前种群中有M个个体，各个个体的适应值为F1,F2,…,Fm，则各个个体被选中进入下一代的概率如式(12)所示：

点击浏览公式

定义pc∈(0,1)为交叉概率，整数pop_size为染色体个数，为确定实行交叉操作的父代，从i=1到pop_size重复下列过程：在区间(0,1)中产生一个随机数r，若r≤pc，则选择染色体Xi作为一个父代，并采用部分匹配交叉方法进行交叉操作；否则，Xi不进行交叉操作。

定义pm∈(0,1)为变异概率，为了选择实行变异操作的染色体，从i=1到pop_size重复下列过程：在区间(0,1)中产生一个随机数r，若r≤pm，则选择当前染色体，采用对换变异的方法进行变异操作。对换变异示例如图 4所示。

图 4 变异 Fig. 4 Variation

图选项

根据上面的描述，整个遗传算法实现过程如下。

Step 1：设定参数：种群大小、交叉概率、变异概率、最大迭代次数等；

Step 2：根据基于优先权的编码方式，产生初始种群；

Step 3：使用模拟技术，计算出种群中各个染色体的目标函数值；

Step 4：保留目标值最小的染色体，并计算每个染色体的适应度；

Step 5：根据适应度大小，采用改进的轮盘赌法选择染色体，得到新的种群；

Step 6：对新种群进行交叉和变异操作；

Step 7：判断是否达到最大代数，若已达到最大代数，则转入Step 8，否则重复操作Step 3到Step 6；

Step 8：将最好的染色体作为最优解，输出结果。 3 实例分析

这里给出一个实例来验证本文所建立的模糊环境下应急物资配送问题的机会约束规划模型及算法的有效性和实用性。图 5为应急物资配送网络图，节点10处发生了自然灾害，而节点1处储存大量的救援物资，现需找出一条较优的配送路径，尽快将救援物资从物资储备点运送到受灾地区。

图 5 应急物资配送网络图 Fig. 5 Network of emergency supply dispatch

图选项

配送网络图中各个有向弧的走行时间和路径风险如表 1所示，走行时间的单位为小时，路径风险的单位为万元。网络中部分参数为确定变量，部分为三角模糊数。

用本文设计的混合智能算法来求解所建立的模糊环境下机会约束规划模型。参数设定如下： 种群大小为40； 交叉概率为0.85； 变异概率为0.05； 最大迭代次数为400； 设定模糊环境下的机会约束规划模型中走行时间和路径风险的置信水平均为0.8,且两个目标的权重都为1/2，ε＝0.1，将式(11)作为适应度函数，进行仿真后得到一条最优路径1→3→5→7→10，此路径的运输时间为12.8 h，运输风险为7.8万元。 4 结论

通过上述实例可以看出本文设计的混合智能算法能够很好地解决模糊环境下应急物资配送机会约束规划模型，在相对短的时间内找到一条较优的运输路径。在发生灾害后，可以帮助相关决策部门建立一个高效、快捷、安全的应急救援系统，及时制订救援计划，配送应急物资来救援受灾地区，降低因应急物资配送不及时而造成的人员伤亡和财产损失。