基于Petri網(wǎng)的多狀態(tài)運輸網(wǎng)絡(luò)端端可靠度計算方法*

蘇 瑩，張 濤

（國防科技大學(xué)信息系統(tǒng)與管理學(xué)院，長沙 410073）

基于Petri網(wǎng)的多狀態(tài)運輸網(wǎng)絡(luò)端端可靠度計算方法*

蘇 瑩，張 濤

（國防科技大學(xué)信息系統(tǒng)與管理學(xué)院，長沙 410073）

經(jīng)典的網(wǎng)絡(luò)可靠性問題認為網(wǎng)絡(luò)和部件只存在完全工作或完全故障兩種狀態(tài)。但在運輸網(wǎng)絡(luò)中，節(jié)點和弧可能處于某種中間狀態(tài)，即存在多狀態(tài)特性。描述了一種基于Petri網(wǎng)計算多狀態(tài)運輸網(wǎng)絡(luò)端端可靠度的方法，節(jié)點和弧的能力可以服從任何分布，傳輸時間是與其當(dāng)前能力和運輸需求有關(guān)的的隨機值。能力隨機有色Petri網(wǎng)被用于模擬系統(tǒng)行為，通過仿真估算多狀態(tài)運輸網(wǎng)絡(luò)的端端可靠度，同時可以確定可靠度最高的最優(yōu)路徑，最后給出了一些計算實驗。

端端可靠度，多狀態(tài)網(wǎng)絡(luò)，運輸網(wǎng)絡(luò)，Petri網(wǎng)，仿真

引 言

在運輸網(wǎng)絡(luò)中，降低通過網(wǎng)絡(luò)的總運輸時間是一個很重要的問題。經(jīng)典的最短路徑問題是在從源點送至終點的路徑中找到一條總運輸時間最短的路徑，每條弧一般有兩個屬性：能力和持續(xù)時間［1］。在真實的運輸網(wǎng)絡(luò)中，由于氣候、故障、交通事故、維修、臨時交通管制等原因，每條路（?。┑哪芰κ窃诓粩嘧兓?，每條路的狀態(tài)不僅僅只有完全工作或完全故障兩種，還存在很多中間狀態(tài)，這屬于典型的多狀態(tài)網(wǎng)絡(luò)。在這樣一個多狀態(tài)運輸網(wǎng)絡(luò)中，最短的或最快的路徑不一定是最可靠的路徑。因此，如何正確有效地評估一個多狀態(tài)運輸網(wǎng)絡(luò)的端端可靠性（2TR）成為了一個很重要的問題。然而，經(jīng)典的網(wǎng)絡(luò)端端可靠性問題認為網(wǎng)絡(luò)和部件都只有兩種狀態(tài)，完全工作或者完全故障狀態(tài)，因此，傳統(tǒng)的兩狀態(tài)可靠性理論和模型不能很好地描述多狀態(tài)網(wǎng)絡(luò)的行為［2］。

近年來，一些多狀態(tài)可靠性分析方法和模型被提出來用于解決這些問題。首先，經(jīng)典的端端可靠性問題（2TR）已經(jīng)被擴展為多狀態(tài)端端可靠性問題（M2TR）。多狀態(tài)端端可靠性（M2TR）的定義在不同應(yīng)用背景下會有所不同。在運輸需求為d時的多狀態(tài)端端可靠度（M2TRd）是最早出現(xiàn)的一種，它被定義為在多狀態(tài)網(wǎng)絡(luò)中從源點（s）傳輸?shù)浇K點（t）成功運輸d個單位需求的概率［3-4］。進而，它還被擴展到一些更加復(fù)雜的問題，例如，多貨物運輸可靠度［5-9］，帶時限的M2TRd（M2TR（d，T））［10-11］和有成本限制的M2TRd（M2TR（d，c））［12-13］。在計算M2TRd的模型中，大多數(shù)都基于最小割集（MC）或者最小路徑（MP）方法。在這些類型的方法中，關(guān)鍵問題是獲得滿足需求的所有可能的d-MCs或者d-MPs。如果d-MCs或者d-MPs已知，系統(tǒng)可靠度就很容易計算出來。例如 M2TR（d，T）和 M2TR（d，c）這樣的擴展問題同樣也可以基于MC或者MP的方法來解決，不同之處在于獲得MCs或者MPs的算法略有不同。然而，這些基于MC或者MP的模型存在NP-難問題，當(dāng)網(wǎng)絡(luò)的大小或者部件的數(shù)量增加時，計算效率也是不可忽視的。因此，需要研究更多實用的算法來解決這個問題。仿真是一種非常有效的途徑，它犧牲計算結(jié)果的精準性來交換運行的時間。Ramirez-Marquez等人［2］提出了一個蒙特卡洛仿真方法來模擬M2TRd。

圖1 一個多狀態(tài)運輸網(wǎng)絡(luò)

另外，在上述提到的工作中，所有的節(jié)點被假設(shè)為不失效的。然而，在運輸網(wǎng)絡(luò)中被視為節(jié)點的路口不僅僅存在失效情況，而且也是多狀態(tài)的。通過節(jié)點的可行路徑會因為故障、時間、維修或交通事故進行調(diào)整。

1 問題描述

圖2 路口5處于第1種狀態(tài)時的所有可行路徑

圖3 路口5處于第2種狀態(tài)時的所有可行路徑

在一個多狀態(tài)網(wǎng)絡(luò)G=（N，A）中，在時限T內(nèi)，需要將d個單位的運輸需求從源點s運送到終點t，運輸工具對每條路的最小能力要求為c。N={n1，n2，…，nm}代表節(jié)點集，m是節(jié)點的數(shù)量，nj代表第j個節(jié)點，j=1，2，…，m。A=（a1，a2，…，am）代表弧集，n 是弧的數(shù)量，ai代表第 i條弧，i=1，2，…，n?；?ai當(dāng)前的狀態(tài)（能力）由ci表示，ci是隨機的并且服從給定的概率分布。令 δ（ai，ci，d）為通過能力為 ci的弧 ai傳輸 d 個單位需求的傳輸時間，它同樣是隨機的并且服從于一個給定的概率分布。節(jié)點存在的狀態(tài)及其概率已知。目標就是在假設(shè)不同弧和節(jié)點是統(tǒng)計獨立的情況下，計算運輸任務(wù)成功的概率，即多狀態(tài)運輸網(wǎng)絡(luò)的 M2TR（d，T，c）。在這里，多狀態(tài)運輸網(wǎng)絡(luò)的 M2TR（d，T，c）被定義為在給定時限T和每條路徑必須的最小能力c時，d個單位需求能從源點運送到終點的概率。

2 能力隨機有色Petri網(wǎng)

Petri網(wǎng)是一種適應(yīng)性強的、多用途的、簡單的繪畫建模工具，可以用來描述動態(tài)系統(tǒng)。由于多狀態(tài)運輸網(wǎng)絡(luò)中節(jié)點和弧的狀態(tài)和能力存在很強的不確定性，一種高級的Petri網(wǎng)形式——能力隨機有色Petri網(wǎng)（CSCPN）被用來分析多狀態(tài)運輸網(wǎng)絡(luò)的動態(tài)行為［14］。

2.1 隨機有色Petri網(wǎng)

基本的Petri網(wǎng)（PN）是一種有向圖，含有4種元素：庫所、變遷、弧、令牌。令牌可以用來代表狀態(tài)、數(shù)據(jù)、項目或者資源。在某個變遷的激活條件被滿足后，一些令牌會移出或移入相應(yīng)的庫所。移出或移入的令牌數(shù)目與相應(yīng)的弧的權(quán)重有關(guān)［15］。為了描述系統(tǒng)行為的延遲時間，時間Petri網(wǎng)（TPN）考慮將Petri網(wǎng)中的變遷點火和時間聯(lián)系起來。隨機Petri網(wǎng)（SPN）是時間Petri網(wǎng)的一個特例，它的時延是隨機變量。在許多系統(tǒng)中，它們存在很多相似的行為和過程，區(qū)別僅僅在于它們的輸入和輸出［16］。為了減少Petri網(wǎng)中的庫所、變遷和弧的數(shù)量，提出了一種更加緊湊的Petri網(wǎng)形式——有色Petri網(wǎng)（CPN）［17］。在有色Petri網(wǎng)中，庫所和變遷之間移動的每一個令牌都被指定一種顏色。

隨機有色Petri網(wǎng)（SCPN）是同時具備SPN和CPN兩種特征的高級Petri網(wǎng)形式，它被定義為一個由八元組表示的有向圖 SCPN=（P，T，Co，H，Pre，Post，F(xiàn)T，M0）［14］。

P={P1，P2，…，PL}是庫所的有限非空集，L>0。

T={T1，T2，…，TJ}是變遷的有限非空集，J>0。

C0∶P∪T→C是一個顏色函數(shù)，與P∪T中每一個元素存在聯(lián)系。C是所有令牌顏色的集合。令牌的顏色可以用自定義的多值結(jié)構(gòu)來描述。Co（Pi）是庫所Pi中所有可能的令牌顏色集，Pi∈P。Co（Ti）是變遷Ti中所有可能的令牌顏色集，Ti∈T。

H∶P×T→CMS是抑制弧，將庫所連接到變遷。Pi∈P和Ti∈T之間存在一條抑制弧（例如H（Pi，Tj）={c}，c∈C）說明Pi中一旦存在顏色為c的令牌，這條弧就會抑制Tj的點火。這里，CMS是非空集C上的多重集。

Pre是前關(guān)聯(lián)矩陣。Pre（Pi，Tj）∶Co（Ti）→Co（Pi）MS是從Tj∈T的顏色集到Co（Pi）上的多重集的輸入關(guān)聯(lián)映射函數(shù)。例如，Pre（P1，T1）=c1→{c1，c3}表明如果庫所P1中有顏色為c1，c3的令牌，庫所P1上變遷T1的點火條件滿足，令牌顏色c1將添入變遷T1中。

Post是后關(guān)聯(lián)矩陣。Post（Pi，Tj）∶Co（Ti）→Co（Pi）MS是從Tj和Pi并集到顏色集Co（Pi）上的多重集的輸出關(guān)聯(lián)映射函數(shù)。

FT∶T×C→R+是點火時間函數(shù)，F(xiàn)T（Tj，ci）是當(dāng)激活的令牌顏色是Ci∈Co（Tj）時變遷Tj的持續(xù)時間。R+為非負實數(shù)集。FT由給定的分布和令牌顏色確定。

M0∶P→CMS是初始令牌顏色集函數(shù)，將令牌顏色和數(shù)量關(guān)聯(lián)到每一個庫所。M0（Pi）={c1，c2，…，cn}，ci∈C，i=1，2，…，n 表示庫所 Pi的初始令牌顏色集為{c1，c2，…，cn}。

2.2 能力隨機有色Petri網(wǎng)

為了描述多狀態(tài)運輸網(wǎng)絡(luò)的動態(tài)行為，在SCPN原始定義的基礎(chǔ)上，變遷被擴展為帶有隨機能力的變遷，并對通過對顏色的擴展定義，提出能力隨機有色Petri網(wǎng)（CSCPN）。CSCPN被定義為一個九元組CSCPN=（P，T，Co，H，Pre，Post，F(xiàn)T，M0）［14］，即在SCPN的基礎(chǔ)上增加了CP，并對FT進行了擴展。

Pre（Pi，Tj）和Post（Pi，Tj）不是靜態(tài)矩陣，而是節(jié)點、弧的狀態(tài)以及庫所、變遷中令牌顏色的動態(tài)函數(shù)。

CP∶T→R+是能力函數(shù)，CP（Tj，ci）是當(dāng)激活的令牌顏色為ci∈C0（Tj）時變遷Tj的能力。CP服從給定的離散或連續(xù)分布。

FT∶T×C→R+是延遲時間函數(shù)，F(xiàn)T（Tj，cpj，ci）是當(dāng)變遷Tj當(dāng)前的能力是cpj并且被激活的令牌顏色為ci∈C0（Yj）時，它的延遲時間。

對于一個運輸網(wǎng)絡(luò)，網(wǎng)絡(luò)中的節(jié)點和弧在能力隨機有色Petri網(wǎng)中分別被表示為庫所和變遷。在圖1的例子中，有10個路口和19條路。當(dāng)源點為節(jié)點1、2、3，終點為節(jié)點10時，基于能力隨機有色Petri網(wǎng)的描述規(guī)則，可以非常容易的將網(wǎng)絡(luò)圖轉(zhuǎn)換成能力隨機有色Petri網(wǎng)，如圖4所示。雙向通行的道路用兩個變遷描述，單向通行的道路用一個變遷描述。

圖4 多狀態(tài)運輸網(wǎng)絡(luò)的能力隨機有色Petri網(wǎng)

同時為了描述多狀態(tài)運輸網(wǎng)絡(luò)的動態(tài)行為，令牌顏色被定義為如下的結(jié)構(gòu)：

令牌的顏色也可以記為一個七元組c=（RoutInf o，SourceNo，SinkNo，Demand，Capacity，Timestamp，Reservation）［14］。定義較為復(fù)雜的令牌顏色，目的是為了記錄路徑和時間信息并且指引這個令牌移動到終點庫所。對于令牌c來說，c.［paramrter_name］用來得到或者給定相應(yīng)性質(zhì)的值。

3 端端可靠度仿真

在運輸網(wǎng)絡(luò)中，盡管從源點到終點可能存在多條可選路徑，但在實際情況中只有一條路徑會被選擇。因此，M2TR（d，T，c）是根據(jù)實際被選擇的那條路徑得出的。在本次研究中，端端可靠度最高的路徑將會被在實際中被選擇，因此，這條路徑的可靠度被看作整個網(wǎng)絡(luò)的端端可靠度 M2TR（d，T，c）。

通過一定次數(shù)的CSCPN仿真，可以找出所有滿足運輸網(wǎng)絡(luò)需求的可行路徑，在此基礎(chǔ)上可計算出M2TR（d，T，c），同時找出端端可靠度最高的路徑。

所以，當(dāng)仿真的次數(shù)足夠多時，所有可能路徑的集合可以這樣表示：

這里，M是所有可行路徑的總數(shù)。

AllRoutes中的每一條路徑的路徑可靠度可以這樣計算：

4 計算實驗

計算實驗基于圖1中的運輸網(wǎng)絡(luò)，源點可以為節(jié)點1、節(jié)點2或節(jié)點3，終點為節(jié)點10，可靠度最高的路徑在實際中會被采用。各條弧的能力和傳輸時間的分布參數(shù)如表1所示。各個節(jié)點的狀態(tài)和概率如表2所示。

表1 圖4中弧的能力概率分布和變遷的時間分布

表2 圖4中節(jié)點狀態(tài)概率分布

5 結(jié)論

傳統(tǒng)的針對M2TR問題的研究假設(shè)每條弧有若干個具有確定發(fā)生概率的離散狀態(tài)，并且假設(shè)所有節(jié)點都是完全可靠的，但是這些基于最小割集和最小路徑方法的模型都是NP-難問題。本文描述了一個基于能力隨機有色Petri網(wǎng)計算多狀態(tài)運輸網(wǎng)絡(luò)端端可靠度的仿真方法，該方法允許弧和節(jié)點都存在多狀態(tài)特性，模型更為接近實際，可以有效支持路徑設(shè)計和優(yōu)化工作。

［1］Park CK，Lee S，Park S.A Label-Setting Algorithm for Finding a QuickestPath［J］.Computers&Operations Research，2004（31）：2405-2418.

［2］Ramirez-Marquez JE，CoitD.AMonte-Carlo Simulation Approach for Approximating Multi-State Two-Terminal Reliability［J］.Reliability Engineering and System Safety，2005（87）：253-264.

［3］Lin JS，Jane CC，Yuan J.On Reliability Evaluation ofa Capacitated-Flow Network in Terms of Minimal Pathsets［J］.Networks，1995（3）：131-138.

［4］Yeh W C.A Simple Approach to Search for all d-MCs of a Limited-Flow Network［J］.Reliability Engineering and System Safety，2001，71（1）：15-19.

［5］Lin Y K.Study on theMulticommodity Reliability ofa Capacitated-Flow Network［J］.Comput Math，2001，42（1-2）：255-264.

［6］ Lin Y K.Two-Commodity Reliability Evaluation for a Stochastic-Flow Network with Node Failure［J］.Computers and Operations Research，2002（29）：1927-1939.

［7］ Lin Y K.Two-Commodity Reliability Evaluation of a Stochastic-Flow Network with Varying Capacity Weight in TermsofMinimal Paths［J］.Computersand Operations Research，2009（36）：1050-1063.

［8］Lin Y K.Performance Evaluation for the Logistics System in Case that Capacity Weight Varies From Arcs and Types of Commodity［J］.Applied Mathematics and Computation，2007（190）：1540-1550.

［9］Yeh W C.A Simple Minimal Path Method for Estimating the Weighted Multi-Commodity Multistate Unreliable Networks Reliability［J］.Reliability Engineering and System Safety，2008（93）：125-136.

［10］Lin Y K.Routing Policy of Stochastic-Flow Networks Under time Threshold and Budget Constraint［J］.Expert Systems with Applications，2009（36）：6076-6081.

［11］Lin Y K.System Reliability of a Stochastic-Flow Network Through Two Minimal Paths Under Time Threshold［J］.Int.J.Production Economics，2010（124）：382-387.

［12］Lin Y K.An Algorithm to Evaluate the System Reliability for Multicommodity Case Under Cost Constraint［J］.Computers and Mathematicswith Applications，2004（48）：805-812.

［13］Zhou Y，Meng Q.Improving Efficiency of Solving d-MC Problem in Stochastic-Now Network［J］.Reliability Engineering and System Safety，2007（92）：30-39.

［14］Zhang T，Guo B，Tan Y J.Reliability-Based Route Optimization ofa Transportation Network with Random Arc Capacities and Time Threshold ［C］//IUKM 2011，Springer-Verlag Berlin Heidelberg，LNAI2011.

［15］Molloy M H.Performance Analysis Using Stochastic Petri nets［J］.IEEETrans，Comp 1982，C-31：913-917.

［16］Bruno A P，Ernesto F，Nobre J.Giovanni Cordeiro Barroso.A Stochastic Coloured Petri Net Model to Allocate Equipments for earth moving operations［J］.ITcon，2008（13）：476-490.

［17］ Jensen K.Coloured Petri nets：Basic Concepts，Analysis Methodsand Practicaluse［M］.New York：Springer，1992.

A PetriNet-Based Approach for Computing Two-Term inalReliability of M ulti-State Transportation Network

SUYing，ZHANGTao
（School of Information Systems and Management，National University of Defense Technology，Changsha 410073，China）

Classical network reliability problem assumes both network and components have only binary states，fully working or fully failed states.But in the transportation network，the nodes and arcs may be in intermediate stateswhich are not fully working either fully failed.This paper describes a Petri net-based approach for computing the two-terminal reliability of amulti-state transportation network.In this study，the capacities of roads （arcs）and the abilities of crossings （nodes）may be in a stochastic state following a kind of probability distribution.And the transmission time of each arc is also not a fixed number but stochastic according to its current capacity and demand.The stochastic coloured Petri net is used for modelling the system behaviour.Capacitated transition and self-modified token colour with route information are defined to describe themulti-state transportation network.By the simulation，the two-terminal reliability can be estimated and the optimal route with highest reliability also can be given.Finally，some experiments are given.

two-terminal reliability，multi-statenetwork，transportation network，petrinet，simulation

TN306；U462.3+5

A

1002-0640（2014）02-0011-05

2013-02-18

2013-03-29

國家自然科學(xué)基金資助項目（70971132）

蘇 瑩（1988- ），女，陜西寶雞人，碩士研究生。研究方向：系統(tǒng)可靠性，項目管理。