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

郝惠晶　王丽丽　刘祥伟

（1.安徽理工大学数学与大数据学院；2安徽理工大学经济与管理学院　安徽淮南　232001）

随着计算机技术的快速发展及其广阔的应用前景，网络建模已经成为分析解决业务流程问题的常用方法。在建模过程中可能会因实际问题情况复杂交互而出现不适用或者不一致的情形，那么依据行为轮廓及Petri网的相关性质进行建模优化就显得尤为重要。而Petri网的行为轮廓理论是以合理的自由选择petri网为基础，从过程行为角度建模，使得Petri网模型间的行为关系具体化、数字化，直观的刻画了行为间的内部关系[1]。

对流程模型进行优化最终获得最优的模型成为了国内外学者关注的课题。因此确定模型变化部分且进行优化分析显得越来越重要。

本文基于Petri网和行为轮廓的思想，以合理的自由选择网为基础，从过程行为角度建模，提出了网络购票系统模型的优化分析。为了使得购票人在网络购票系统中更方便快捷的购买到合适的车票，并且针对改签退票过程可能出现的情况，结合Petri网中库所变迁的行为关系分析优化流程模型，使其达到适用性和一致性。

一、基本概念梳理

下面仅介绍流程模型Petri网的定义及其可达性，阐述了行为轮廓的相关定义，其他概念。

定义1[2]（流程模型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）∪cod（F）=P∪T，其中，

dom（F）={x∈P∪T|∃y∈P∪T，（x,y∈F）}；

cod（F）={x∈P∪T|∃y∈P∪T，（x,y∈F）}。

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

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

（7）s∈T是开始活动变迁，e∈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∧（x,y）∈F}表示 x的后集。

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

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

（2）在标识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[t1＞M1[t2＞M2…Mk-1[tk＞MK

则称Mk为从M可达的。从M可达的一切标识的集合记为 R（M）。

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

（1）若 t1＞t2且 t2≯t1，则称严格序关系，记作 t1→t2；

（2）若 t1≯t2且 t2＞t1，则称严格逆序关系，记作 t1→-1t2；

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

（4）若 t1＞t2且 t2＞t1，则称交叉序关系，记作 t1×t2；

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

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

随着网络技术的普及，人们出行购买火车票不再局限于去窗口排队购票，更多的是采取网络购票，基本的网络购票流程如下图1所示。

图1　网上购火车票流程图

通常在网上购买火车票，需要先进入官网，登录个人账户，登录成功后进入车票预订的界面，依次选择好出发地，目的地，以及出行的日期等，点击查询，就会出现符合要求的所有车次。添加常用联系人，并选定购票人，确认无误后提交订单，然后进行支付，现行支付的方式有支付宝，微信或者银行卡等不同方式。支付成功后就会跳出购票成功的页面，之后就可以取票上车了。但是，在网络购票过程中，我们可能会遇到选择的出发地和目的地没有可供选择的车次，或者购票成功后因突发情况需要改签或者退票，那么此时我们应该如何对网络购票进行控制与优化呢？下面我们就通过Petri网来对这些情况进行建模分析。

上述模型给出了简单的从用户登录到购票成功的一个流程。但是如果用户在查询火车票的车次时没有从出发地到目的地的直达火车票，那么就需要通过中转来乘车，这里就需要在模型中构建一个最优的乘车方案，使得购票人能选择合适的车程出行。还有就是购票人在购票成功以后因意外情况需要改签时间地点或者需要退票重新购票，在改签过程中，购票人需考虑改签票是否与所购火车票时间冲突，如果冲突的话就需要退票重新购票，不冲突就只需要直接改签。图2我们用流程Petri网来建模。

图2　网络购火车票模型Petri网结构图

图2中变迁t1（登录）发生，然后t2发生，t3和t4是排他关系，如果有直达票直接选择高铁或者普快直达，否则需要购买中转票，t4发生，同样会出现一个排他结构t5和t6，分别考虑高铁和普快，选择最优的乘车方案，进而选择合适的车次，接着t9、t10、t11、t12发生，购票完成。如果购票人确认取票则t13发生，如果因其他原因要选择改签或者退票，则t14和t17排他发生，假设改签就需要考虑是否是所购票时间冲突，不冲突直接选择改签的时间和地点，冲突就需要先退票后选择购票信息，这个就是t15和t16的排他发生。而如果是选择退票的话，有两种情况，一种是退票后不购票了，另一种就是退票后重新选择购票信息。此系统虽整体反映了网络购票的所有情况，但是对于改签情况下不需要重新选择购票人和改签到其他时间段不需要考虑时间冲突的问题没有给出合理的控制。

所以，为了优化上述结构，我们通过图3给出了优化后的网络购票模型Petri网结构图，通过用红色框标示出来，增加了几个新的变迁。如果是改签状态下，我们不再需要选择购票人，即t10发生。如果选择改签，还需要考虑过有没有改签过，没有改签过，那么t16发生，若t17发生则说明改签过一次，就不能再次改签只能选择退票。而且改签状态下，看改签的时间点，如果改签到当天（t19发生），就需要考虑改签时间冲突与否，即与图2所示一样。如果改签到其他时间段的话，即图3中t18发生，就不用再考虑时间冲突问题，直接选择时间地点进行改签即可，这样就比较全面的考虑到网络购票的整体流程，实现了建模系统的优化。

图3　网络购火车票优化模型Petri网结构图

三、结语

本文基于Petri网给出了网络购票模型一种优化方法。根据Petri网的变迁发生规则及其可达性和行为轮廓的排他性等基本性质，通过增加相应的结构变迁对其进行优化。构建的模型包括顺序关系的流程图及具有排他关系的变迁发生序列，利用改签和退票间的交互关系优化购票系统。使模型应用更加全面，也体现了该模型在实际生活中的适用性。

参考文献：

[1]吴哲辉.Petri网理论[M].北京：机械工业出版社，2006:6-22，1-28.

[2]Smirnov S,Weidlich M,Mendling J.Business Process Model Abstraction based on Behavioral Profiles[C].In 8th International Conference,San Francisco,December 7-10,2010.Heidelberg:Springer Berlin Heidelberg,2010,6470:1-16.

[3]Jensen M T.Improving robustness and flexibility of tardiness and total flow-time job shops using robustness measures[J].Applied Soft Computing,2001,1(1):35-52.