危險(xiǎn)品運(yùn)輸中的可控風(fēng)險(xiǎn)最大流算法

毛華，趙小娜

（河北大學(xué) 數(shù)學(xué)與計(jì)算機(jī)學(xué)院，河北 保定 071002）

據(jù)統(tǒng)計(jì)，中國(guó)每年道路運(yùn)輸危險(xiǎn)物2×108t左右，易燃易爆油品類達(dá)108t.危險(xiǎn)品運(yùn)輸一旦發(fā)生事故，具有傷亡人數(shù)多、環(huán)境污染嚴(yán)重等危害.如果對(duì)危險(xiǎn)處理不妥，將會(huì)造成長(zhǎng)遠(yuǎn)的危害.學(xué)者們一直在從事危險(xiǎn)品運(yùn)輸路線的選擇和優(yōu)化問題［1－10］，目前研究重點(diǎn)從事后處理向事前預(yù)防過渡［11］.通常的算法大多是從線性規(guī)劃和概率出發(fā)，把影響因素逐一進(jìn)行考慮，算法繁瑣，故本文把各種可能造成風(fēng)險(xiǎn)的因素統(tǒng)一為一個(gè)風(fēng)險(xiǎn)值，用尋找最大風(fēng)險(xiǎn)路的算法，實(shí)現(xiàn)可控風(fēng)險(xiǎn)最大流算法.

1 預(yù)備知識(shí)

引進(jìn)有關(guān)風(fēng)險(xiǎn)網(wǎng)絡(luò)的基本知識(shí).

定義1［12－14］1）最短路Dijkstra算法原理：若路P＝νsν1…νk－1νk是從νs到νk的最短路，則P′＝νsν1…νk－1必定是從νs到νk－1的最短路，基于這一原理，算法得出網(wǎng)絡(luò)G 中指定頂點(diǎn)νs到其余各點(diǎn)的最短路.2）求最小費(fèi)用ν0流的負(fù)費(fèi)用圈算法思路：①使用Dinic最大流算法，求出網(wǎng)絡(luò)G 中流量為ν0的可行流；②使用最短路算法，尋找增量網(wǎng)絡(luò)N（f）中的負(fù)費(fèi)用有向圈，并沿該圈進(jìn)行增流，從而使可行流的費(fèi)用降低.

給出如下定義和算法.

定義2 風(fēng)險(xiǎn)矩陣：M（ω）＝（ωij）n×n，其中ωij為有向邊νiνj的風(fēng)險(xiǎn)值.若νi到νj無路，則ωij＝－∞；ωii＝－∞.增量矩陣：M（t）＝（tij）n×n，其中tij為有向邊νiνj的可增流量值.若νi到νj無路，則tij＝∞；tii＝∞.

Dinic算法［12－14］

Begin

while G 中存在增廣路do

begin

利用最短路算法，在G 中尋找一條增廣路P；

δ＝min｛tij｜（i，j）∈P｝；

沿P 增流δ；

更新G；

end；

End

2 算法

2.1 算法

算法1給出求νs到νt最大風(fēng)險(xiǎn)路.算法2在算法1的基礎(chǔ)上，給出危險(xiǎn)品運(yùn)輸中已知可控風(fēng)險(xiǎn)ω0，進(jìn)而得到最大流.

算法1 最大風(fēng)險(xiǎn)路算法

Begin

Pf＝Φ；

if G 中存在νs－νt路P；

在G 中找到P1，滿足：

ω（P1）＝max｛ω（Pi），Pi∈P｝；

Pf＝P1；

End

算法2 求可控風(fēng)險(xiǎn)ω0的最大流算法

Begin

利用算法1，求得G 的一條νs－νt有向路P 及ω（P）；

while ω（P）＞ω0do

begin

for （i，j）∈P；

θ（eij）＝max｛ω（P）｝；

在G 中沿P 去掉eij；

更新G；

end；

在網(wǎng)絡(luò)G 中運(yùn)行Dinic算法；

End

2.2 算法復(fù)雜性分析和比較

文中ν和ε 分別表示網(wǎng)絡(luò)G 頂點(diǎn)的總個(gè)數(shù)和邊的總數(shù)；ωP1表示最大風(fēng)險(xiǎn)路P1的風(fēng)險(xiǎn)值，ω0表示事先給定的風(fēng)險(xiǎn)值，cmax和ωmax表示的是網(wǎng)絡(luò)G 中所有弧上容量的最大值和風(fēng)險(xiǎn)值的最大值.

定理1 1）求可控風(fēng)險(xiǎn)ω0的最大流算法的復(fù)雜度為O（ν2·ε·（ωP1－ω0））；2）著名的求最小費(fèi)用ν0流的負(fù)費(fèi)用圈算法的復(fù)雜度為O（ν3·ε·cmax·ωmax）；3）2個(gè)算法進(jìn)行比較，1）比2）的復(fù)雜度低.

證明 1）第1步用最大風(fēng)險(xiǎn)路算法，有νs到νt最大風(fēng)險(xiǎn)路P1，復(fù)雜度為O（ν2），而該步風(fēng)險(xiǎn)值至多循環(huán)（ωP1－ω0）次，因此該步的復(fù)雜度為O（ν2·（ωP1－ω0））；第2步調(diào)用Dinic算法，求更新后網(wǎng)絡(luò)G 的最大流，該步復(fù)雜度為O（ν2·ε）；從而算法總的復(fù)雜度為O（ν2·（ωP1－ω0）＋ν2·ε）＝O（ν2·ε·（ωP1－ω0））.

2）證明詳見參考文獻(xiàn)［14］.

3）網(wǎng)絡(luò)G 中最大風(fēng)險(xiǎn)路P1的風(fēng)險(xiǎn)值ωP1不會(huì)超過（ν－1）·ωmax，從而

ωP1－ω0≤（ν－1）·ωmax－ω0＜ν·ωmax＜ν·ωmax·cmax，即ν2·ε·（ωP1－ω0）＜ν3·ε·cmax·ωmax.

算法1是改進(jìn)最短路Dijkstra算法得到的.算法2是改進(jìn)求最小費(fèi)用ν0流的負(fù)費(fèi)用圈算法［14］得到的.通過此處算法和著名算法的分析和比較，可以得到如下幾點(diǎn)：

1）最大風(fēng)險(xiǎn)路算法和最短路算法的復(fù)雜性都是O（ν2）；但最大風(fēng)險(xiǎn)路算法不是最短路算法的對(duì)偶，在比較風(fēng)險(xiǎn)值大小時(shí)，最短路需將該頂點(diǎn)的所有發(fā)量進(jìn)行比較，而最大風(fēng)險(xiǎn)路算法不必考慮到收點(diǎn)的風(fēng)險(xiǎn)值.

2）求最小費(fèi)用ν0流的負(fù)費(fèi)用圈算法通過增量網(wǎng)絡(luò)尋找負(fù)費(fèi)用有向圈，運(yùn)用最短路算法時(shí)，復(fù)雜度為O（ν3）；而求可控風(fēng)險(xiǎn)ω0的最大流算法，運(yùn)用最大風(fēng)險(xiǎn)路算法時(shí)，風(fēng)險(xiǎn)值不產(chǎn)生負(fù)值，復(fù)雜度為O（ν2）.

3）求最小費(fèi)用ν0流的負(fù)費(fèi)用圈算法中網(wǎng)絡(luò)G 始終是保持不變的；而求可控風(fēng)險(xiǎn)ω0的最大流算法通過尋找最大風(fēng)險(xiǎn)路，把不滿足條件的弧逐一刪去，從而使網(wǎng)絡(luò)G 簡(jiǎn)化，在增流過程中，帶來了很大的方便.

由上述幾點(diǎn)可知，此處求可控風(fēng)險(xiǎn)ω0的最大流算法復(fù)雜度低，應(yīng)用簡(jiǎn)單、方便.

3 算法實(shí)例

本節(jié)通過實(shí)例說明上一節(jié)算法是如何實(shí)現(xiàn)的.

某核電站要運(yùn)輸一批核廢料，選擇一條從出發(fā)點(diǎn)到存儲(chǔ)點(diǎn)的最優(yōu)路線.把運(yùn)輸路線抽象成網(wǎng)絡(luò)G＝（V，A，C，ω），如圖1所示，νs表示產(chǎn)生核廢料的地點(diǎn)；νt表示核廢料的存儲(chǔ)點(diǎn)；ν1，ν2，ν3，ν4表示2條及2條以上公路的交匯處，弧上第1個(gè)數(shù)字為容量，第2個(gè)數(shù)字為風(fēng)險(xiǎn)值.下面運(yùn)用求可控風(fēng)險(xiǎn)ω0的最大流算法求網(wǎng)絡(luò)G 中風(fēng)險(xiǎn)ω0為10的最大流.

圖1 網(wǎng)絡(luò)G＝（V，A，C，ω）Fig.1 The network G＝（V，A，C，ω）

由算法2作出風(fēng)險(xiǎn)矩陣：

在M（ω）中運(yùn)行算法1，得到G 的一條最大風(fēng)險(xiǎn)νs－νt有向路P1:νsν2ν4νt，及ωP1＝13＞ω0，此時(shí)θ（ν2ν4）＝9，沿P1去掉弧ν2ν4，更新網(wǎng)絡(luò)G，如圖2所示.此時(shí)，作出如下新的風(fēng)險(xiǎn)矩陣：

運(yùn)行算法1，得到G 的一條最大風(fēng)險(xiǎn)νs－νt有向路P1:νsν2ν3ν4νt，及ωP1＝11＞ω0，此時(shí)θ（ν3ν4）＝5，沿P1去掉弧ν3ν4，更新網(wǎng)絡(luò)G，如圖3所示.此時(shí)，作出如下新的風(fēng)險(xiǎn)矩陣：

圖2 沿P 去掉弧ν2ν4 更新后的網(wǎng)絡(luò)GFig.2 Updated network G by remoνing arc ofν2ν4based on P

圖3 沿P 去掉弧ν3ν4 更新后的網(wǎng)絡(luò)GFig.3 Updated network Gby removing arc ofν3ν4based on P

運(yùn)行算法1，得到G 的一條最大風(fēng)險(xiǎn)νs－νt有向路P1:νsν2ν3νt，此時(shí)ωP1＝7＜ω0，結(jié)束.在圖3中，運(yùn)行Dinic算法，此時(shí)增量矩陣為：

在M（t）中運(yùn)行最短路Dijkstra算法［12－14］，得到

即一條νs－νt增廣路P:νsν1ν4νt，沿P 增流δ＝2后，如圖4所示.此時(shí)，得到如下新的增量矩陣M（t），弧上括號(hào)外數(shù)字為流值，括號(hào)內(nèi)數(shù)字為可增流量值.

運(yùn)行最短路Dijkstra算法，得到一條νs－νt增廣路P:νsν2ν3νt，沿P 增流δ＝3后，如圖5所示.此時(shí)，得到新的增量矩陣：

圖4 沿P 增流后的網(wǎng)絡(luò)GFig.4 Incremented flow of network Gbased on P

圖5 沿P 增流后的網(wǎng)絡(luò)GFig.5 Network Gafter incrementing flow based on P

運(yùn)行最短路Dijkstra算法，得到νs－νt已無增廣路，即網(wǎng)絡(luò)G 已達(dá)到最大流5.

關(guān)于本例的算法復(fù)雜性分析如下：

本例頂點(diǎn)數(shù)ν＝6，風(fēng)險(xiǎn)值ω0＝10.

1）風(fēng)險(xiǎn)矩陣M（ω）＝（ωij）n×n，用最大風(fēng)險(xiǎn)路算法，得ωP1＜ω0的2條最大風(fēng)險(xiǎn)路P1，更新2次網(wǎng)絡(luò)G，因此該步的復(fù)雜度為ν2·（ωP1－ω0）＝72.

2）在最新的網(wǎng)絡(luò)G 中，用Dinic算法［14］尋找網(wǎng)絡(luò)G 的最大流，此時(shí)ε＝7，該步的復(fù)雜度為ν2·ε＝252.本例可控風(fēng)險(xiǎn)ω0的最大流算法的復(fù)雜度為ν3·ε·（ωp1－ω0）＝504.而本例最小費(fèi)用ν0流的負(fù)費(fèi)用圈算法的復(fù)雜度為69 984.

由此知，該算法與最小費(fèi)用ν0流的負(fù)費(fèi)用圈算法相比較，不僅復(fù)雜性低，而且可簡(jiǎn)化網(wǎng)絡(luò).從本例可以看出，本文的算法簡(jiǎn)單易行、有效性高.

［1］ MIAOU S P，CHIN S M.Computing k－shortest path for spent nuclear fuel highway transportation［J］.European Journal of Operational Research，1991，53：64－80.

［2］ KARA B Y，ERKUT E，VETER V.Accurate calculation of hazardous materials transport risk［J］.Operations Research Letters，2003，31：285－292.

［3］ BUBBICO R，CAVE S D，MAZZAROTTA B.Risk analysis for road and rail transport of hazardous materials：a simplified approach［J］.Journal of Loss Prevention in the Process Industries，2004，17：477－482.

［4］ 毛華，趙小娜，毛曉亮.危險(xiǎn)品運(yùn)輸中的最小風(fēng)險(xiǎn)最大流算法［J］.計(jì)算機(jī)工程，2012，38（9）：268－270.MAO Hua，ZHAO Xiaona，MAO Xiaoliang.Minimal risk and maximal flow algorithm in hazardous materials transportation［J］.Computer Engineering，2012，38（9）：268－270.

［5］ 毛華，俞珊珊.任意基數(shù)集上的擬陣的約束［J］.河北大學(xué)學(xué)報(bào)：自然科學(xué)版，2009，29（1）：22－24.MAO Hua，YU Shanshan.Restriction of matroids of arbitrary cardinality［J］.Journal of Hebei University：Natural Science Edition，2009，29（1）：22－24.

［6］ 任常興，吳宗之.危險(xiǎn)品道路運(yùn)輸選線問題分析［J］.安全與環(huán)境學(xué)報(bào)，2006，6（2）：84－88.REN Changxing，WU Zongzhi.On route－choice analysis of hazardous materials transportation［J］.Journal of Safety and Environment，2006，6（2）：84－88.

［7］ 謝凡榮，賈仁安.供給總量限定需求區(qū)間約束型運(yùn)輸問題－時(shí)限費(fèi)用優(yōu)化模型與算法［J］.運(yùn)籌與管理，2008，17（1）：42－47.XIE Fanrong，JIA Renan.The transportaion problem with supply amount specified and demand interval constraint－models and algorithms for optimization on time limit and cost［J］.Operations Research and Management Science，2008，17（1）：42－47.

［8］ 毛華，毛曉亮，李斌.網(wǎng)絡(luò)最大流部分割矩陣算法［J］.計(jì)算機(jī)科學(xué)，2011，38（12）：229－231.MAO Hua，MAO Xiaoliang，LI Bin.Partial cut algorithm for maximum－flow of network［J］.Computer Science，2011，38（12）：229－231.

［9］ 易玉枚，廖可兵，張佐釗，等.危險(xiǎn)化學(xué)品物流網(wǎng)絡(luò)選址－運(yùn)輸優(yōu)化研究［J］.中國(guó)安全科學(xué)學(xué)報(bào)，2011，21（6）：135－140.YI Yumei，LIAO Kebing，ZHANG Zuozhao，et al.Study on location－transportation optimization for hazardous material logistics network［J］.China Safety Science Journal，2011，21（6）：135－140.

［10］ 毛華，謝利偉.全弧搜索廣義擬陣的構(gòu)造［J］.河北大學(xué)學(xué)報(bào)：自然科學(xué)版，2010，30（2）：133－136.MAO Hua，XIE Liwei.Construction of searching are greedoids［J］.Journal of Hebei University：Natural Science Edition，2010，30（2）：133－136.

［11］ 嚴(yán)虎.危險(xiǎn)品公路運(yùn)輸安全管理現(xiàn)狀及探究［J］.北華航天工業(yè)學(xué)院學(xué)報(bào)，2011，21（4）：17－19.YAN Hu.Status and investigation on highway transportation safety management of hazardous materials［J］.Journal of North China Institute of Aerospace Engineering，2011，21（4）：17－19.

［12］ BONDY J A，MURTY U S R.Graph theory with applications［M］.New York：Elsevier Science Publishing Corporation，1976.

［13］ BONDY J A，MURTY U S R.Graph theory［M］.Berlin：Springer，2008.

［14］ 高隨祥.圖論與網(wǎng)絡(luò)流理論［M］.北京：高等教育出版社，2009.