基于Petri网的多状态运输网络端端可靠度计算方法*

苏 莹，张 涛

（国防科技大学信息系统与管理学院，长沙 410073）

基于Petri网的多状态运输网络端端可靠度计算方法*

苏 莹，张 涛

（国防科技大学信息系统与管理学院，长沙 410073）

经典的网络可靠性问题认为网络和部件只存在完全工作或完全故障两种状态。但在运输网络中，节点和弧可能处于某种中间状态，即存在多状态特性。描述了一种基于Petri网计算多状态运输网络端端可靠度的方法，节点和弧的能力可以服从任何分布，传输时间是与其当前能力和运输需求有关的的随机值。能力随机有色Petri网被用于模拟系统行为，通过仿真估算多状态运输网络的端端可靠度，同时可以确定可靠度最高的最优路径，最后给出了一些计算实验。

端端可靠度，多状态网络，运输网络，Petri网，仿真

引 言

在运输网络中，降低通过网络的总运输时间是一个很重要的问题。经典的最短路径问题是在从源点送至终点的路径中找到一条总运输时间最短的路径，每条弧一般有两个属性：能力和持续时间［1］。在真实的运输网络中，由于气候、故障、交通事故、维修、临时交通管制等原因，每条路（弧）的能力是在不断变化的，每条路的状态不仅仅只有完全工作或完全故障两种，还存在很多中间状态，这属于典型的多状态网络。在这样一个多状态运输网络中，最短的或最快的路径不一定是最可靠的路径。因此，如何正确有效地评估一个多状态运输网络的端端可靠性（2TR）成为了一个很重要的问题。然而，经典的网络端端可靠性问题认为网络和部件都只有两种状态，完全工作或者完全故障状态，因此，传统的两状态可靠性理论和模型不能很好地描述多状态网络的行为［2］。

近年来，一些多状态可靠性分析方法和模型被提出来用于解决这些问题。首先，经典的端端可靠性问题（2TR）已经被扩展为多状态端端可靠性问题（M2TR）。多状态端端可靠性（M2TR）的定义在不同应用背景下会有所不同。在运输需求为d时的多状态端端可靠度（M2TRd）是最早出现的一种，它被定义为在多状态网络中从源点（s）传输到终点（t）成功运输d个单位需求的概率［3-4］。进而，它还被扩展到一些更加复杂的问题，例如，多货物运输可靠度［5-9］，带时限的M2TRd（M2TR（d，T））［10-11］和有成本限制的M2TRd（M2TR（d，c））［12-13］。在计算M2TRd的模型中，大多数都基于最小割集（MC）或者最小路径（MP）方法。在这些类型的方法中，关键问题是获得满足需求的所有可能的d-MCs或者d-MPs。如果d-MCs或者d-MPs已知，系统可靠度就很容易计算出来。例如 M2TR（d，T）和 M2TR（d，c）这样的扩展问题同样也可以基于MC或者MP的方法来解决，不同之处在于获得MCs或者MPs的算法略有不同。然而，这些基于MC或者MP的模型存在NP-难问题，当网络的大小或者部件的数量增加时，计算效率也是不可忽视的。因此，需要研究更多实用的算法来解决这个问题。仿真是一种非常有效的途径，它牺牲计算结果的精准性来交换运行的时间。Ramirez-Marquez等人［2］提出了一个蒙特卡洛仿真方法来模拟M2TRd。

图1 一个多状态运输网络

另外，在上述提到的工作中，所有的节点被假设为不失效的。然而，在运输网络中被视为节点的路口不仅仅存在失效情况，而且也是多状态的。通过节点的可行路径会因为故障、时间、维修或交通事故进行调整。

1 问题描述

图2 路口5处于第1种状态时的所有可行路径

图3 路口5处于第2种状态时的所有可行路径

在一个多状态网络G=（N，A）中，在时限T内，需要将d个单位的运输需求从源点s运送到终点t，运输工具对每条路的最小能力要求为c。N={n1，n2，…，nm}代表节点集，m是节点的数量，nj代表第j个节点，j=1，2，…，m。A=（a1，a2，…，am）代表弧集，n 是弧的数量，ai代表第 i条弧，i=1，2，…，n。弧 ai当前的状态（能力）由ci表示，ci是随机的并且服从给定的概率分布。令 δ（ai，ci，d）为通过能力为 ci的弧 ai传输 d 个单位需求的传输时间，它同样是随机的并且服从于一个给定的概率分布。节点存在的状态及其概率已知。目标就是在假设不同弧和节点是统计独立的情况下，计算运输任务成功的概率，即多状态运输网络的 M2TR（d，T，c）。在这里，多状态运输网络的 M2TR（d，T，c）被定义为在给定时限T和每条路径必须的最小能力c时，d个单位需求能从源点运送到终点的概率。

2 能力随机有色Petri网

Petri网是一种适应性强的、多用途的、简单的绘画建模工具，可以用来描述动态系统。由于多状态运输网络中节点和弧的状态和能力存在很强的不确定性，一种高级的Petri网形式——能力随机有色Petri网（CSCPN）被用来分析多状态运输网络的动态行为［14］。

2.1 随机有色Petri网

基本的Petri网（PN）是一种有向图，含有4种元素：库所、变迁、弧、令牌。令牌可以用来代表状态、数据、项目或者资源。在某个变迁的激活条件被满足后，一些令牌会移出或移入相应的库所。移出或移入的令牌数目与相应的弧的权重有关［15］。为了描述系统行为的延迟时间，时间Petri网（TPN）考虑将Petri网中的变迁点火和时间联系起来。随机Petri网（SPN）是时间Petri网的一个特例，它的时延是随机变量。在许多系统中，它们存在很多相似的行为和过程，区别仅仅在于它们的输入和输出［16］。为了减少Petri网中的库所、变迁和弧的数量，提出了一种更加紧凑的Petri网形式——有色Petri网（CPN）［17］。在有色Petri网中，库所和变迁之间移动的每一个令牌都被指定一种颜色。

随机有色Petri网（SCPN）是同时具备SPN和CPN两种特征的高级Petri网形式，它被定义为一个由八元组表示的有向图 SCPN=（P，T，Co，H，Pre，Post，FT，M0）［14］。

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

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

C0∶P∪T→C是一个颜色函数，与P∪T中每一个元素存在联系。C是所有令牌颜色的集合。令牌的颜色可以用自定义的多值结构来描述。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是前关联矩阵。Pre（Pi，Tj）∶Co（Ti）→Co（Pi）MS是从Tj∈T的颜色集到Co（Pi）上的多重集的输入关联映射函数。例如，Pre（P1，T1）=c1→{c1，c3}表明如果库所P1中有颜色为c1，c3的令牌，库所P1上变迁T1的点火条件满足，令牌颜色c1将添入变迁T1中。

Post是后关联矩阵。Post（Pi，Tj）∶Co（Ti）→Co（Pi）MS是从Tj和Pi并集到颜色集Co（Pi）上的多重集的输出关联映射函数。

FT∶T×C→R+是点火时间函数，FT（Tj，ci）是当激活的令牌颜色是Ci∈Co（Tj）时变迁Tj的持续时间。R+为非负实数集。FT由给定的分布和令牌颜色确定。

M0∶P→CMS是初始令牌颜色集函数，将令牌颜色和数量关联到每一个库所。M0（Pi）={c1，c2，…，cn}，ci∈C，i=1，2，…，n 表示库所 Pi的初始令牌颜色集为{c1，c2，…，cn}。

2.2 能力随机有色Petri网

为了描述多状态运输网络的动态行为，在SCPN原始定义的基础上，变迁被扩展为带有随机能力的变迁，并对通过对颜色的扩展定义，提出能力随机有色Petri网（CSCPN）。CSCPN被定义为一个九元组CSCPN=（P，T，Co，H，Pre，Post，FT，M0）［14］，即在SCPN的基础上增加了CP，并对FT进行了扩展。

Pre（Pi，Tj）和Post（Pi，Tj）不是静态矩阵，而是节点、弧的状态以及库所、变迁中令牌颜色的动态函数。

CP∶T→R+是能力函数，CP（Tj，ci）是当激活的令牌颜色为ci∈C0（Tj）时变迁Tj的能力。CP服从给定的离散或连续分布。

FT∶T×C→R+是延迟时间函数，FT（Tj，cpj，ci）是当变迁Tj当前的能力是cpj并且被激活的令牌颜色为ci∈C0（Yj）时，它的延迟时间。

对于一个运输网络，网络中的节点和弧在能力随机有色Petri网中分别被表示为库所和变迁。在图1的例子中，有10个路口和19条路。当源点为节点1、2、3，终点为节点10时，基于能力随机有色Petri网的描述规则，可以非常容易的将网络图转换成能力随机有色Petri网，如图4所示。双向通行的道路用两个变迁描述，单向通行的道路用一个变迁描述。

图4 多状态运输网络的能力随机有色Petri网

同时为了描述多状态运输网络的动态行为，令牌颜色被定义为如下的结构：

令牌的颜色也可以记为一个七元组c=（RoutInf o，SourceNo，SinkNo，Demand，Capacity，Timestamp，Reservation）［14］。定义较为复杂的令牌颜色，目的是为了记录路径和时间信息并且指引这个令牌移动到终点库所。对于令牌c来说，c.［paramrter_name］用来得到或者给定相应性质的值。

3 端端可靠度仿真

在运输网络中，尽管从源点到终点可能存在多条可选路径，但在实际情况中只有一条路径会被选择。因此，M2TR（d，T，c）是根据实际被选择的那条路径得出的。在本次研究中，端端可靠度最高的路径将会被在实际中被选择，因此，这条路径的可靠度被看作整个网络的端端可靠度 M2TR（d，T，c）。

通过一定次数的CSCPN仿真，可以找出所有满足运输网络需求的可行路径，在此基础上可计算出M2TR（d，T，c），同时找出端端可靠度最高的路径。

所以，当仿真的次数足够多时，所有可能路径的集合可以这样表示：

这里，M是所有可行路径的总数。

AllRoutes中的每一条路径的路径可靠度可以这样计算：

4 计算实验

计算实验基于图1中的运输网络，源点可以为节点1、节点2或节点3，终点为节点10，可靠度最高的路径在实际中会被采用。各条弧的能力和传输时间的分布参数如表1所示。各个节点的状态和概率如表2所示。

表1 图4中弧的能力概率分布和变迁的时间分布

表2 图4中节点状态概率分布

5 结论

传统的针对M2TR问题的研究假设每条弧有若干个具有确定发生概率的离散状态，并且假设所有节点都是完全可靠的，但是这些基于最小割集和最小路径方法的模型都是NP-难问题。本文描述了一个基于能力随机有色Petri网计算多状态运输网络端端可靠度的仿真方法，该方法允许弧和节点都存在多状态特性，模型更为接近实际，可以有效支持路径设计和优化工作。

［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

国家自然科学基金资助项目（70971132）

苏 莹（1988- ），女，陕西宝鸡人，硕士研究生。研究方向：系统可靠性，项目管理。