李秀美，陈华友

(1.安徽交通职业技术学院土木工程系，安徽 合肥 230051;2.安徽大学数学科学学院，安徽 合肥 230601)

由于交通事故等因素的影响，道路中断的现象经常发生。车辆在行驶的过程中并不知道道路中断的及时信息，往往行驶到中断处时才知道。同时在实际的交通网络中，边权可能是由距离、时间、路况等多因素构成的一个模糊数。因此，有必要研究在不确定环境下的模糊交通网络最短路径关键边问题，这将对减少道路中断带来的经济损失，优化交通运输管理，提高运输效率有着十分重要的现实意义。

目前，已有相关文献研究了最短路径关键边问题[1－3]、最长绕行路关键边问题[4]、交通网络最大流关键边问题[5]、不完全信息下交通网络最短路径的关键边问题[6]，以及不完全信息下交通网络的关键路径问题[7]。然而上述文献是建立在确定网络图的基础上的，对于不确定环境下的模糊交通网络最短路径关键边问题尚未见到相关文献的报道。笔者在现有文献的基础上，同时考虑不确定环境下的道路中断信息和含模糊数的交通网络权的交通网络最短路径的关键边问题。在OERI积分值概念的基础上，定义了模糊网络的最短路径，给出了模糊网络最短路径的标号算法，同时给出了不确定环境下的模糊最短路径关键边的有效算法，最后进行了实例分析，表明了算法的有效性。

1 模糊数基本概念

记 FN={(a，b，c)|∀a ＜ b ＜ c，a，b，c∈R}为三角模糊数集。

定义1[8]设 A=(a，b，c) ∈ FN，B=(p，q，r)∈FN，则三角模糊数的加法定义为A+B=(a+p，b+q，c+r)。令:

则称μA(x)为三角模糊数A的隶属函数。

定义2设A=(a，b，c)∈FN为三角模糊数，令 A(α)=[AL(α)，AR(α)]，0≤α≤1，其中AL(α)=a+(b－a) α，AR(α)=c－(c－b) α，则称区间数A(α)是模糊集A的α截集。AL(α)为α截集的左端点，AR(α)为α截集的右端点。

定义 3[9]设，则称F(A)为A的OERI积分值，其中λ(α)∈(0，1)为决策者对水平α的权重，L(α)和R(α)分别为决策者对A的左右部的权重。

将AL(α)=a+(b－a) α，AR(α)=c－(c－b) α代入F(A)的积分式，可得:

实际应用时，决策者可根据自己的偏好来决定权重λ、L和R的取值。

根据定义3，可以对三角模糊数进行排序，设A=(a，b，c)∈FN，B=(p，q，r)∈FN，排序准则为:若A＞B，则 F(A)＞F(B);若 A=B，则 F(A)=F(B)。

2 模糊交通网络模型及最短路径标号算法

将现实中的道路交通抽象成以道路交叉口为节点、两节点间的道路为边的交通网络，且边权为模糊数，这样的道路交通网络称为模糊交通网络，记为 G=(V，E，W)。其中 V={1，2，…，n}为节点集，1 表示起始点，n 表示终止点;E={ei，j|i，j∈V}为边的集合;W={wi，j|ei，j∈E} 为模糊边长集合，wi，j∈FN为三角模糊数。

笔者研究的假设条件与文献[6]相同，即假设:①车辆总是沿着最短路径行进;②道路中断仅发生在起点至终点的最短路径上;③在车辆行进过程中只发生一条道路中断，但不知道哪条路段中断;④车辆行进到中断路的节点(靠近起点的节点)处时，获得道路是否中断的信息。

设P1n为模糊交通网络G中从起始点1至终止点n的所有模糊路径集合，p∈P1n，即p为起始点 1 至终止点 n 的某一条路径，记 p={v1，e1，i，vi，…，vj，ej，n，vn}。

定义4在模糊交通网络G中，∀p∈P1n，令则称d(p) 为模糊路径p对应的距离，其中 wi，j为边 ei，j对应的模糊边长，F(w) 为 w的 OERI积分值。若存在 p*∈ P，

i，ji，j1n∀p∈P1n使得d(p*)≤d(p)成立，则称p*为G中从起始点至终止点的模糊最短路径。

为了叙述方便，定义如下变量和符号:

S为已得到永久标号点的集合;¯S为与S中顶点有关联的边，且没有得到永久标号的临时标号点的集合;b(i)为点1至点i模糊最短路径中点i的前序点，从而可反向找到最短路径;为 边 ei，j的 模 糊 权;F(wi，j) 为 边 ei，j的OERI积分值;V(i)=(VL(i)，Vm(i)，VR(i))为从顶点1至顶点i的模糊最短路径的模糊标号值;VL(i)，VR(i)，Vm(i)分别为 V(i)的左、右、中部值，Vm(i)可由 F(wi，j)累加得到。

类似求最短路径的 Dijkstra 算法[10－11]，可得起始点1至终止点n的模糊最短路径的算法，步骤如下:

(2)若n∈S，则找到了1至n的模糊最短路径，路长为模糊数V(n)，路径可从 b(n)反推出来，计算结束;否则转入步骤(3);

(3)计算新的永久标号点。若j*=arg(min{Vm(j)|j∈¯S})，则把j*加入到永久标号点的集合S中，同时在临时标号点的集合¯S中去掉j*;

3 模糊交通网络最短路径关键边确定方法

文献[6]讨论了道路中断不完全信息的最短路径关键边问题的研究，其特点是交通网络边权为确定数值。笔者将其结果推广到道路边权为模糊数的情形，为此定义具有完全信息和不确定信息环境下模糊最短路径关键边的概念。

定义5在一个至少两个边的连通模糊网络G=(V，E，W)中，模糊最短路径 pG(1，n)上至少存在一条边eu，v，其中u点更靠近起始点1，当从G=(V，E，W)中删除 eu，v时，使得起始点 1 至终止点n的模糊最短路径对应的距离(见定义4)增至最大，则称边eu，v为该模糊最短路径的关键边。

定义6在一个至少两个边的连通模糊网络G=(V，E，W)中，设模糊最短路径 pG(1，n)上的任意一条边为eu，v，其中u点更靠近起始点，当从G中删除边时，从u*点绕路到达终止点，使得模糊最短路径对应的距离 dG－e*(1，n)≥dG－e(1，n)，则称边为不确定信息环境下模糊最短路径的关键边。其中 dG－e*(1，n)=dG(1，u*)+dG－e*(u*，n)，dG－e(1，n) = dG(1，u) +dG－e(u，n)，dG(1，u)为模糊最短路径 pG(1，n)上起始点1到u点的模糊路径对应的距离，dG－e(u，n)为G=(V，E－e，W)中从u点到终止点n的最短绕行路径的对应距离。

下面讨论不确定信息环境下的模糊最短路径关键边的计算。

首先计算得到以终止点n为根的最短路径树TG(n)，同时得到最短路径 pG(1，n)。设 eu，v是pG(1，n)上的一条边，其中节点u更靠近起始点1，把边 eu，v删除后，TG(n)就被分割成两棵子树。令Mn(u)为TG(n)中删除边eu，v后形成的以n为根的子树，Nn(u)为TG(n)中删除边 eu，v后形成的以u为根的子树。设x∈Nn(u)，y∈Mn(u)，则有:

根据子树连通的思想，则有:

其中，ex，y∈E － {eu，v}，加上道路中断前已经走过的路长，可得到 dG－e(1，n)=dG(1，u)+dG－e(u，n)。

根据上述算法思想，可给出不确定信息环境下的模糊交通网络最短路径关键边的确定方法:

(1)利用上述模糊最短路的算法，计算G=(V，E，W)中终止点n至所有其他顶点的最短路径，此时便可得到pG(1，n)和TG(n)，并记录pG(1，n)上边的条数k;

(2)令i=1;

(3)从 pG(1，n)中删除边 ei，得到 Mn(u)，Nn(u);

(5)如果i≤k，则转入步骤(3)，否则转入步骤(6);

(6)对dG－ei(1，n)求最大值，最大值所对应中断边为不确定信息环境下的最短路径关键边。

4 实例分析

图1为某市部分路网起点①至终点⑥间的道路。在正常的情况下，车辆沿着①至⑥的最短路径行驶，然而由于交通事故等突发事件的发生，经常造成道路中断，使得车辆不得不绕行，假设发生一次道路堵塞，但不知道哪条路段中断，要使车辆尽快到达终点，就得寻求模糊最短路径。

当模糊最短路径上的一条边中断时，可能会对起点①至终点⑥之间的模糊交通网络最短路径造成最大损失，即所走的实际路程最长，该问题的实质是要求在不确定信息环境下，在实际的运输管理中避免这种最坏情形的发生。

若决策者根据自己的偏好采用无差异观点来决定权重λ、L和R的取值，即则起点①至终点⑥之间的最短路径为①－③－⑤－⑥，对应的模糊最短路径长为V(⑥)=(11，26，37)，可解释为最可能的长度为26，且含有减少15和增加11的不确定性。为了比较分析模糊最短路径关键边和不确定信息环境下的模糊最短路径关键边问题，分别计算这两个问题的关键边。计算结果如表1所示。

比较上述结果可以得到以下结论:

(1)当①－③边中断，确定环境下的模糊总路长等于不确定环境下的模糊总路长，都为(17.00，29.00，39.00)，行走的路线同为①－②－③－⑤－⑥。这是因为①－③中断时，i=1，dG(1，u)=0。

(2)不确定信息环境下模糊最短路径关键边问题的总行程的模糊积分和比确定环境下模糊最短路径关键边情形时多走3个单位。这是由于确定环境下模糊最短路径关键边问题在出发前就已具有路段中断的完全信息，而不确定信息环境下模糊最短路径关键边问题并不具有这些完全信息，两者所走的线路分别为①－②－④－⑤－⑥和①－③－④－⑤－⑥。

表1 两种环境下模糊最短路径关键边的计算结果

(3)上述两个问题的最终结果是不一样的，不确定信息环境下模糊最短路径关键边是③－⑤边，而确定环境下模糊最短路径关键边为⑤－⑥边，即如果网络结构发生改变，两种环境下的关键边就有可能不相同。

5 结论

在现实交通运输中，经常由于各种突发事件，如交通事故、自然灾害等，导致道路中断，又由于突发事件的不可预见性，使得行驶的车辆无法得到行进线路上道路中断的完全信息，且在实际的交通网络中，边权可能是一个模糊数。从交通运输管理角度来看，不确定信息环境下的模糊最短路径关键边问题更贴近实际中的不确定情形，因此这项研究具有十分重要的现实意义。

[1] CORLEY H W，SHA D Y.Most vital links and nodes in weighted networks[J].Operation Research Letters，1982(1):157－16l.

[2] 李引珍，郭耀煌.交通运输网络最短路径关键边问题研究[J].中国管理科学，2004，12(4):69－73.

[3] 魏宝红.救灾物流系统中的交通网络最短路径问题的研究[J].铁道运输与经济，2008，30(5):62 －64.

[4] NARDELLI E，PROIETTL G，WIDMYER P.Finding the detour critical edge of a shortest path between nodes[J].Information Processing Letters，1998，67(1):51－54.

[5] 石超峰，徐寅峰.交通网络最大流关键边[J].系统工程，2009，27(9):55 －59.

[6] 闫化海，徐寅峰.不完全信息下交通网络最短路径的关键边问题[J].系统工程，2006，24(2):37 －40.

[7] 刘明，徐寅峰，杜源江，等.不完全信息下交通网络的关键路径问题[J].系统工程，2006，24(12):16 －20.

[8] 李荣钧.模糊多准则决策理论及应用[M].北京:科学出版社，2002:45－109.

[9] 李引珍.模糊最短路的一种算法[J].运筹与管理，2004，13(5):7 －11.

[10] 胡运权，郭耀煌.运筹学教程[M].北京:清华大学出版社，1998:34－78.

[11] 严晓凤，陆济湘，唐双平.基于Floyd算法的校园最短路径问题分析与实现[J].武汉理工大学学报:信息与管理工程版，2012，34(6):695－698.