基于Petri网在网络购物系统的建模优化分析

夏 磊 王丽丽 刘祥伟

（安徽理工大学数学与大数据学院 安徽淮南 232001）

业务流程分问题常借助计算机技术，通过网络建模的方法加以分析，寻求解决。但是，由于实际流程问题往往复杂而交互，建模时常常遇到一些不一致或者不适用的情况，此时，借助Petri网及行为轮廓的相关理论知识加以优化模型，是非常重要的一步。行为轮廓理论的基础是通过合理的自由选择Petri网，对过程行为建立模型，细化并数字化Petri网模型间的行为弱序关系，以此更有利于验证分析模型的交互行为和组合[1]。

越来越多的国内外学者关注于对流程模型的优化分析。文献[2]提出一种诊断过程模型之间行为差异的方法，阐述了行为轮廓的相关性质，给出了行为轮廓的一些性质和分析方法。文献[3]说明了行为轮廓是基于UML来捕捉和阐述服务软件中的重要行为规则，主要分析在应用发展中特定软件构件之间的交互准则。在文献[4]中提出了Petri网的可达性检查技术，并阐述了行为轮廓主要用于模型动态行为的监控。文献[5]阐述了将多个子模型合并成一个综合模型，利用模块分解对模型进行优化,并借助合并模型的可追溯性进行综合分析。文献[6]将流程模型用规范化术语表示，并使用术语重写系统进行标准化，使得能够对不同的流程模型进行语义比较。文献[7]对Petri网的行为特征提出了分析方法，首先构建行为顺序关系，分析行为顺序关系建立初始过程模型;然后提出一致性分析的测量方法和其他评估标准，对初始过程模型进行优化，最后根据算法得出优化模型。文献[8]中将现有的严格的行为等值概念的不恰当性作为出发点，提出了行为概况的概念，用于捕捉流程模型的基本行为约束。文献[9]提出了一种等同性的概念，它适用于各种行为之间的对应关系，而不是单一行为。将等价概念与行为继承的工作结合起来，以应对一个过程中存在但不存在于另一个过程中的行为，从而引出行为兼容性的概念，兼容性概念验证了两个模型对于它们共同的操作具有相同的行为。

本文基于Petri网和行为轮廓的思想，以合理的自由选择网为基础，从过程行为角度建模，提出了网络购物系统模型的优化分析。为了使得买家能够在网络购物时能够更加方便地调换商品，结合Petri网中库所变迁的行为关系分析优化流程模型，使其达到适用性和一致性。

本文结构的第二部分内容介绍了Petri网及行为轮廓的相关概念，第三部分通过分析网络购物系统模型间的弱序关系对换货系统进行优化，第四部分是通过PIPE软件对优化后的模型进行检验，验证正确性与合理性，第五部分是总结论文并对未来工作的一个展望，最后是本文涉及的参考文献。

一、基本概念

定义1[10]（流程模型Petri网）一个流程模型Petri网PM=（P,T,F,C,s,e）是一个六元组，满足以下条件：

（1）P是有限库所集，T是有限活动变迁集；

（2）P≠Ø，T≠Ø 且 P∩T=Ø；

（3）F⊆（P×T）∪（T×P）表示 PN的的流关系且（P∪T，F）是强连通图；

（4）dom（F）=P∪T，其中 dom（F）={x∈P∪T｜∃y∈P∪T，(x,y∈F)}；cod(F∈P∪T|∃y∈P∪T,(y,x)∈F};

（5）C={and,xor,or}是流程网的结构类型；

（6）M0是网的初始标识，Mf是网的终止标识，且Mf是死标识；

（7）s∈T是开始活动变迁，s∈T是终止活动变迁。则称该网为流程模型Petri网,在此定义上，我们定义了网的前集和网的后集。

定义2[1]（前集和后集）设N=（P，T，F）为一个网，我们用X=P∪T表示所有的节点，F+用表示流关系F的不自反传递闭包。x∈X,·x={y|y∈P∪T∧（y,x）∈F}表示 x的前集，x·={y|y∈P∪T∧（y,x）∈F}表示 x的后集。

定义3[1]（变迁发生规则）一个四元组PN（P，T；F，M0）称为Petri网，并具有下面的变迁发生规则：

⑴变迁 t∈T具有发生权，当且仅当对∀P∈·t：M（P）≥1，记作 M[t＞；

⑵在标识M下能使的变迁t经发生后，得到一个新的标识 M'，记作 M[t＞M'，则有

定义4[1]（可达性）已知Petri网PN=（P，T；F，M），如果存在t∈T，使M[t＞M'，则称M'为从M直接可达的。如果存在变迁序列t1,t2,…，tk和标识序列M,M2,…，Mk使得M[t1＞M1[t2＞M2…＞MK-1[tk＞MK则称 MK为从 M可达的。从M可达的一切标识的集合记为R（M）。

定义5[11]（行为轮廓）设（N，M0）是一个网，初始标识为M0。对任给的变迁对（t1,t2）∈（T×t）满足下面关系;

(1)若 t1≻t2且 t2≯t1，则称严格序关系，记作 t1→t2；

(2)若 t1≯t2且 t1≻t2，则称严格逆序关系，记作 t1→-1t2；

(3)若 t1≯t2且 t2≯t1，则称排他关系，记作 t1//t2;

(4)若 t1≻t2且 t2≻t1，则称交叉序关系，记作 t1×t2；

(5)将所有关系的集合叫做网系统的行为轮廓，记作BP={→,←-1,//,×}。

二、基于Petri网的网络购物系统的建模优化分析

随着电子商务的不断发展，越来越多的人喜欢在网上购物，但是网络购物常会遇到退换商品的问题，本文重点分析在未收货前决定调换商品的情况，暂不考虑退货的情形。下面利用petri网对网络购物流程建模分析，如下图1。

图1 网络购物模型Petri网结构图

图1中买家登录购物系统后，变迁t1发生，然后t2、t3、t4依次发生，t4（支付）发生后出现一个交叉序关系t5和t23，买家系统继续进行，t5发生，若订单无问题，买家等待收货，t6发生，再看卖家系统，t23（确认订单）发生后，t24发生，产生一个交叉序关系t25和t29，接着t25发生产生另一个交叉序关系t26和t30，然后t31、t32发生，导致买家系统t7发生，产生一个排他关系t8和t10，若对商品满意则t10发生，接着t11、t12发生，t11发生后导致卖家系统t27（收款）发生，接着t28发生；若对商品不满意，则t8（寄回）发生，如果卖家同意换货则t13发生，接着t7再发生，t10、t11、t12依次发生，如果卖家不同意换货，则t14发生，t22（申请退款）发生。重点看换货系统，若t5发生后，在未收货前买家已经决定换货，则t15发生，产生一个排他序关系t16和t17，若商家未发货，则t16发生，如果同意换货，则t18发生，接着买家等待收货，后面过程如上述；若商家已经发货，则t17发生，如果同意换货，则t20发生，接着t7发生，买家将商品寄回，则t8（寄回）发生，接着 t13、t7、t10、t11、t12 依次发生，若不同意换货，则 t21发生，接着 t7、t8、t14、t22 依次发生。

但是，发现在未收货前决定换货时，若卖家已经发货，买家只能先等待收货，收到商品后再寄回给卖家，重新调换后再等待收货。本文对此过程进行优化处理，使卖家接到买家的换货要求后，立即联系物流公司，传达指令使商品在下一个转运点转回，如此达到节省换货时间和成本的目的，优化后的petri网模型如下图2。

图2中优化部分用红框标出，t13发生后产生一个排他序关系t16和t17，若卖家同意换货，则t17发生，接着t24、t25发生，卖家联系物流公司发出商品转回指令，则t28（发出指令）发生，接着物流公司系统t32发生，商品在下一转运点转回，t34发生，然后卖家重新发货，则t21发生，接着t30、t31、t35 发生，买家系统 t7、t8、t9、t10 发生；若商家不同意换货，则t16发生，买家申请退款并且商品同样也需要转回，则t18 发生，且 t24、t25、t28、t32、t33、t35 依次发生，卖家发出指令到物流公司，商品在下一转运点转回，流程结束。

图2 网络购物优化模型Petri网结构图

三、利用PIPE软件对优化后Petri网模型模拟运行

为了检验优化后的Petri网模型的正确性和可行性，本文利用了PIPE软件对模型模拟运行。将模型在PIPE软件上画出，并点击运行，模型运行结果如下图3。

对优化后的Petri网模型进行状态空间分析，分析结果如下图4。

图3 PIPE软件模拟运行优化后的Petri网模型

图4 优化后Petri网模型的状态空间分析

经过PIPE软件的状态空间分析，可以看出优化后的Petr网模型是有界的、安全的、无死锁的，因此，优化后的Petri网模型对于网络购物换货环节的改善是有效的。

四、结语

本文基于Petri网给出了网络购物模型换货环节的一种优化方法。根据Petri网的变迁发生规则及其可达性和行为轮廓的排他性等基本性质，通过增加相应的结构变迁对其进行优化。构建的模型包括顺序关系的流程图及具有交叉序关系、排他关系的变迁发生序列，使模型应用更加全面，也体现了该模型在实际生活中的适用性。未来关于建模优化还有许多问题去研究，需要对优化后的模型基于Petri网及其行为轮廓的相关性质分析其模型的一致性和合理性。