不確定信息下模糊網(wǎng)絡(luò)最短路徑關(guān)鍵邊問(wèn)題

李秀美，陳華友

(1.安徽交通職業(yè)技術(shù)學(xué)院土木工程系，安徽 合肥 230051;2.安徽大學(xué)數(shù)學(xué)科學(xué)學(xué)院，安徽 合肥 230601)

由于交通事故等因素的影響，道路中斷的現(xiàn)象經(jīng)常發(fā)生。車輛在行駛的過(guò)程中并不知道道路中斷的及時(shí)信息，往往行駛到中斷處時(shí)才知道。同時(shí)在實(shí)際的交通網(wǎng)絡(luò)中，邊權(quán)可能是由距離、時(shí)間、路況等多因素構(gòu)成的一個(gè)模糊數(shù)。因此，有必要研究在不確定環(huán)境下的模糊交通網(wǎng)絡(luò)最短路徑關(guān)鍵邊問(wèn)題，這將對(duì)減少道路中斷帶來(lái)的經(jīng)濟(jì)損失，優(yōu)化交通運(yùn)輸管理，提高運(yùn)輸效率有著十分重要的現(xiàn)實(shí)意義。

目前，已有相關(guān)文獻(xiàn)研究了最短路徑關(guān)鍵邊問(wèn)題[1－3]、最長(zhǎng)繞行路關(guān)鍵邊問(wèn)題[4]、交通網(wǎng)絡(luò)最大流關(guān)鍵邊問(wèn)題[5]、不完全信息下交通網(wǎng)絡(luò)最短路徑的關(guān)鍵邊問(wèn)題[6]，以及不完全信息下交通網(wǎng)絡(luò)的關(guān)鍵路徑問(wèn)題[7]。然而上述文獻(xiàn)是建立在確定網(wǎng)絡(luò)圖的基礎(chǔ)上的，對(duì)于不確定環(huán)境下的模糊交通網(wǎng)絡(luò)最短路徑關(guān)鍵邊問(wèn)題尚未見(jiàn)到相關(guān)文獻(xiàn)的報(bào)道。筆者在現(xiàn)有文獻(xiàn)的基礎(chǔ)上，同時(shí)考慮不確定環(huán)境下的道路中斷信息和含模糊數(shù)的交通網(wǎng)絡(luò)權(quán)的交通網(wǎng)絡(luò)最短路徑的關(guān)鍵邊問(wèn)題。在OERI積分值概念的基礎(chǔ)上，定義了模糊網(wǎng)絡(luò)的最短路徑，給出了模糊網(wǎng)絡(luò)最短路徑的標(biāo)號(hào)算法，同時(shí)給出了不確定環(huán)境下的模糊最短路徑關(guān)鍵邊的有效算法，最后進(jìn)行了實(shí)例分析，表明了算法的有效性。

1 模糊數(shù)基本概念

記 FN={(a，b，c)|?a ＜ b ＜ c，a，b，c∈R}為三角模糊數(shù)集。

定義1[8]設(shè) A=(a，b，c) ∈ FN，B=(p，q，r)∈FN，則三角模糊數(shù)的加法定義為A+B=(a+p，b+q，c+r)。令:

則稱μA(x)為三角模糊數(shù)A的隸屬函數(shù)。

定義2設(shè)A=(a，b，c)∈FN為三角模糊數(shù)，令 A(α)=[AL(α)，AR(α)]，0≤α≤1，其中AL(α)=a+(b－a) α，AR(α)=c－(c－b) α，則稱區(qū)間數(shù)A(α)是模糊集A的α截集。AL(α)為α截集的左端點(diǎn)，AR(α)為α截集的右端點(diǎn)。

定義 3[9]設(shè)，則稱F(A)為A的OERI積分值，其中λ(α)∈(0，1)為決策者對(duì)水平α的權(quán)重，L(α)和R(α)分別為決策者對(duì)A的左右部的權(quán)重。

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

實(shí)際應(yīng)用時(shí)，決策者可根據(jù)自己的偏好來(lái)決定權(quán)重λ、L和R的取值。

根據(jù)定義3，可以對(duì)三角模糊數(shù)進(jìn)行排序，設(shè)A=(a，b，c)∈FN，B=(p，q，r)∈FN，排序準(zhǔn)則為:若A＞B，則 F(A)＞F(B);若 A=B，則 F(A)=F(B)。

2 模糊交通網(wǎng)絡(luò)模型及最短路徑標(biāo)號(hào)算法

將現(xiàn)實(shí)中的道路交通抽象成以道路交叉口為節(jié)點(diǎn)、兩節(jié)點(diǎn)間的道路為邊的交通網(wǎng)絡(luò)，且邊權(quán)為模糊數(shù)，這樣的道路交通網(wǎng)絡(luò)稱為模糊交通網(wǎng)絡(luò)，記為 G=(V，E，W)。其中 V={1，2，…，n}為節(jié)點(diǎn)集，1 表示起始點(diǎn)，n 表示終止點(diǎn);E={ei，j|i，j∈V}為邊的集合;W={wi，j|ei，j∈E} 為模糊邊長(zhǎng)集合，wi，j∈FN為三角模糊數(shù)。

筆者研究的假設(shè)條件與文獻(xiàn)[6]相同，即假設(shè):①車輛總是沿著最短路徑行進(jìn);②道路中斷僅發(fā)生在起點(diǎn)至終點(diǎn)的最短路徑上;③在車輛行進(jìn)過(guò)程中只發(fā)生一條道路中斷，但不知道哪條路段中斷;④車輛行進(jìn)到中斷路的節(jié)點(diǎn)(靠近起點(diǎn)的節(jié)點(diǎn))處時(shí)，獲得道路是否中斷的信息。

設(shè)P1n為模糊交通網(wǎng)絡(luò)G中從起始點(diǎn)1至終止點(diǎn)n的所有模糊路徑集合，p∈P1n，即p為起始點(diǎn) 1 至終止點(diǎn) n 的某一條路徑，記 p={v1，e1，i，vi，…，vj，ej，n，vn}。

定義4在模糊交通網(wǎng)絡(luò)G中，?p∈P1n，令則稱d(p) 為模糊路徑p對(duì)應(yīng)的距離，其中 wi，j為邊 ei，j對(duì)應(yīng)的模糊邊長(zhǎng)，F(xiàn)(w) 為 w的 OERI積分值。若存在 p*∈ P，

i，ji，j1n?p∈P1n使得d(p*)≤d(p)成立，則稱p*為G中從起始點(diǎn)至終止點(diǎn)的模糊最短路徑。

為了敘述方便，定義如下變量和符號(hào):

S為已得到永久標(biāo)號(hào)點(diǎn)的集合;ˉS為與S中頂點(diǎn)有關(guān)聯(lián)的邊，且沒(méi)有得到永久標(biāo)號(hào)的臨時(shí)標(biāo)號(hào)點(diǎn)的集合;b(i)為點(diǎn)1至點(diǎn)i模糊最短路徑中點(diǎn)i的前序點(diǎn)，從而可反向找到最短路徑;為 邊 ei，j的 模 糊 權(quán);F(wi，j) 為 邊 ei，j的OERI積分值;V(i)=(VL(i)，Vm(i)，VR(i))為從頂點(diǎn)1至頂點(diǎn)i的模糊最短路徑的模糊標(biāo)號(hào)值;VL(i)，VR(i)，Vm(i)分別為 V(i)的左、右、中部值，Vm(i)可由 F(wi，j)累加得到。

類似求最短路徑的 Dijkstra 算法[10－11]，可得起始點(diǎn)1至終止點(diǎn)n的模糊最短路徑的算法，步驟如下:

(2)若n∈S，則找到了1至n的模糊最短路徑，路長(zhǎng)為模糊數(shù)V(n)，路徑可從 b(n)反推出來(lái)，計(jì)算結(jié)束;否則轉(zhuǎn)入步驟(3);

(3)計(jì)算新的永久標(biāo)號(hào)點(diǎn)。若j*=arg(min{Vm(j)|j∈ˉS})，則把j*加入到永久標(biāo)號(hào)點(diǎn)的集合S中，同時(shí)在臨時(shí)標(biāo)號(hào)點(diǎn)的集合ˉS中去掉j*;

3 模糊交通網(wǎng)絡(luò)最短路徑關(guān)鍵邊確定方法

文獻(xiàn)[6]討論了道路中斷不完全信息的最短路徑關(guān)鍵邊問(wèn)題的研究，其特點(diǎn)是交通網(wǎng)絡(luò)邊權(quán)為確定數(shù)值。筆者將其結(jié)果推廣到道路邊權(quán)為模糊數(shù)的情形，為此定義具有完全信息和不確定信息環(huán)境下模糊最短路徑關(guān)鍵邊的概念。

定義5在一個(gè)至少兩個(gè)邊的連通模糊網(wǎng)絡(luò)G=(V，E，W)中，模糊最短路徑 pG(1，n)上至少存在一條邊eu，v，其中u點(diǎn)更靠近起始點(diǎn)1，當(dāng)從G=(V，E，W)中刪除 eu，v時(shí)，使得起始點(diǎn) 1 至終止點(diǎn)n的模糊最短路徑對(duì)應(yīng)的距離(見(jiàn)定義4)增至最大，則稱邊eu，v為該模糊最短路徑的關(guān)鍵邊。

定義6在一個(gè)至少兩個(gè)邊的連通模糊網(wǎng)絡(luò)G=(V，E，W)中，設(shè)模糊最短路徑 pG(1，n)上的任意一條邊為eu，v，其中u點(diǎn)更靠近起始點(diǎn)，當(dāng)從G中刪除邊時(shí)，從u*點(diǎn)繞路到達(dá)終止點(diǎn)，使得模糊最短路徑對(duì)應(yīng)的距離 dG－e*(1，n)≥dG－e(1，n)，則稱邊為不確定信息環(huán)境下模糊最短路徑的關(guā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)上起始點(diǎn)1到u點(diǎn)的模糊路徑對(duì)應(yīng)的距離，dG－e(u，n)為G=(V，E－e，W)中從u點(diǎn)到終止點(diǎn)n的最短繞行路徑的對(duì)應(yīng)距離。

下面討論不確定信息環(huán)境下的模糊最短路徑關(guān)鍵邊的計(jì)算。

首先計(jì)算得到以終止點(diǎn)n為根的最短路徑樹(shù)TG(n)，同時(shí)得到最短路徑 pG(1，n)。設(shè) eu，v是pG(1，n)上的一條邊，其中節(jié)點(diǎn)u更靠近起始點(diǎn)1，把邊 eu，v刪除后，TG(n)就被分割成兩棵子樹(shù)。令Mn(u)為TG(n)中刪除邊eu，v后形成的以n為根的子樹(shù)，Nn(u)為TG(n)中刪除邊 eu，v后形成的以u(píng)為根的子樹(shù)。設(shè)x∈Nn(u)，y∈Mn(u)，則有:

根據(jù)子樹(shù)連通的思想，則有:

其中，ex，y∈E － {eu，v}，加上道路中斷前已經(jīng)走過(guò)的路長(zhǎng)，可得到 dG－e(1，n)=dG(1，u)+dG－e(u，n)。

根據(jù)上述算法思想，可給出不確定信息環(huán)境下的模糊交通網(wǎng)絡(luò)最短路徑關(guān)鍵邊的確定方法:

(1)利用上述模糊最短路的算法，計(jì)算G=(V，E，W)中終止點(diǎn)n至所有其他頂點(diǎn)的最短路徑，此時(shí)便可得到pG(1，n)和TG(n)，并記錄pG(1，n)上邊的條數(shù)k;

(2)令i=1;

(3)從 pG(1，n)中刪除邊 ei，得到 Mn(u)，Nn(u);

(5)如果i≤k，則轉(zhuǎn)入步驟(3)，否則轉(zhuǎn)入步驟(6);

(6)對(duì)dG－ei(1，n)求最大值，最大值所對(duì)應(yīng)中斷邊為不確定信息環(huán)境下的最短路徑關(guān)鍵邊。

4 實(shí)例分析

圖1為某市部分路網(wǎng)起點(diǎn)①至終點(diǎn)⑥間的道路。在正常的情況下，車輛沿著①至⑥的最短路徑行駛，然而由于交通事故等突發(fā)事件的發(fā)生，經(jīng)常造成道路中斷，使得車輛不得不繞行，假設(shè)發(fā)生一次道路堵塞，但不知道哪條路段中斷，要使車輛盡快到達(dá)終點(diǎn)，就得尋求模糊最短路徑。

當(dāng)模糊最短路徑上的一條邊中斷時(shí)，可能會(huì)對(duì)起點(diǎn)①至終點(diǎn)⑥之間的模糊交通網(wǎng)絡(luò)最短路徑造成最大損失，即所走的實(shí)際路程最長(zhǎng)，該問(wèn)題的實(shí)質(zhì)是要求在不確定信息環(huán)境下，在實(shí)際的運(yùn)輸管理中避免這種最壞情形的發(fā)生。

若決策者根據(jù)自己的偏好采用無(wú)差異觀點(diǎn)來(lái)決定權(quán)重λ、L和R的取值，即則起點(diǎn)①至終點(diǎn)⑥之間的最短路徑為①－③－⑤－⑥，對(duì)應(yīng)的模糊最短路徑長(zhǎng)為V(⑥)=(11，26，37)，可解釋為最可能的長(zhǎng)度為26，且含有減少15和增加11的不確定性。為了比較分析模糊最短路徑關(guān)鍵邊和不確定信息環(huán)境下的模糊最短路徑關(guān)鍵邊問(wèn)題，分別計(jì)算這兩個(gè)問(wèn)題的關(guān)鍵邊。計(jì)算結(jié)果如表1所示。

比較上述結(jié)果可以得到以下結(jié)論:

(1)當(dāng)①－③邊中斷，確定環(huán)境下的模糊總路長(zhǎng)等于不確定環(huán)境下的模糊總路長(zhǎng)，都為(17.00，29.00，39.00)，行走的路線同為①－②－③－⑤－⑥。這是因?yàn)棰伲壑袛鄷r(shí)，i=1，dG(1，u)=0。

(2)不確定信息環(huán)境下模糊最短路徑關(guān)鍵邊問(wèn)題的總行程的模糊積分和比確定環(huán)境下模糊最短路徑關(guān)鍵邊情形時(shí)多走3個(gè)單位。這是由于確定環(huán)境下模糊最短路徑關(guān)鍵邊問(wèn)題在出發(fā)前就已具有路段中斷的完全信息，而不確定信息環(huán)境下模糊最短路徑關(guān)鍵邊問(wèn)題并不具有這些完全信息，兩者所走的線路分別為①－②－④－⑤－⑥和①－③－④－⑤－⑥。

表1 兩種環(huán)境下模糊最短路徑關(guān)鍵邊的計(jì)算結(jié)果

(3)上述兩個(gè)問(wèn)題的最終結(jié)果是不一樣的，不確定信息環(huán)境下模糊最短路徑關(guān)鍵邊是③－⑤邊，而確定環(huán)境下模糊最短路徑關(guān)鍵邊為⑤－⑥邊，即如果網(wǎng)絡(luò)結(jié)構(gòu)發(fā)生改變，兩種環(huán)境下的關(guān)鍵邊就有可能不相同。

5 結(jié)論

在現(xiàn)實(shí)交通運(yùn)輸中，經(jīng)常由于各種突發(fā)事件，如交通事故、自然災(zāi)害等，導(dǎo)致道路中斷，又由于突發(fā)事件的不可預(yù)見(jiàn)性，使得行駛的車輛無(wú)法得到行進(jìn)線路上道路中斷的完全信息，且在實(shí)際的交通網(wǎng)絡(luò)中，邊權(quán)可能是一個(gè)模糊數(shù)。從交通運(yùn)輸管理角度來(lái)看，不確定信息環(huán)境下的模糊最短路徑關(guān)鍵邊問(wèn)題更貼近實(shí)際中的不確定情形，因此這項(xiàng)研究具有十分重要的現(xiàn)實(shí)意義。

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

[2] 李引珍，郭耀煌.交通運(yùn)輸網(wǎng)絡(luò)最短路徑關(guān)鍵邊問(wèn)題研究[J].中國(guó)管理科學(xué)，2004，12(4):69－73.

[3] 魏寶紅.救災(zāi)物流系統(tǒng)中的交通網(wǎng)絡(luò)最短路徑問(wèn)題的研究[J].鐵道運(yùn)輸與經(jīng)濟(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] 石超峰，徐寅峰.交通網(wǎng)絡(luò)最大流關(guān)鍵邊[J].系統(tǒng)工程，2009，27(9):55 －59.

[6] 閆化海，徐寅峰.不完全信息下交通網(wǎng)絡(luò)最短路徑的關(guān)鍵邊問(wèn)題[J].系統(tǒng)工程，2006，24(2):37 －40.

[7] 劉明，徐寅峰，杜源江，等.不完全信息下交通網(wǎng)絡(luò)的關(guān)鍵路徑問(wèn)題[J].系統(tǒng)工程，2006，24(12):16 －20.

[8] 李榮鈞.模糊多準(zhǔn)則決策理論及應(yīng)用[M].北京:科學(xué)出版社，2002:45－109.

[9] 李引珍.模糊最短路的一種算法[J].運(yùn)籌與管理，2004，13(5):7 －11.

[10] 胡運(yùn)權(quán)，郭耀煌.運(yùn)籌學(xué)教程[M].北京:清華大學(xué)出版社，1998:34－78.

[11] 嚴(yán)曉鳳，陸濟(jì)湘，唐雙平.基于Floyd算法的校園最短路徑問(wèn)題分析與實(shí)現(xiàn)[J].武漢理工大學(xué)學(xué)報(bào):信息與管理工程版，2012，34(6):695－698.