基于Petri网行为轮廓的超市自助结账系统优化分析

魏瑶

摘 要：本研究对超市自助结账系统进行建模并对模型进行优化，以达到使模型更具有实用性的目的，首先对自助结账系统进行建模，在保证行为合理的基础上，通过增加相应的结构变迁，再利用行为轮廓的相关理论和性质，对原自助结账系统模型进行优化，以提高其实用性，缩短结账时间，并通过HIPS仿真软件进行模拟运行证明了优化模型的可行性。

关键词：Petri网;行为轮廓;自助结账;优化;HIPS

中图分类号：TP391.9  文献标识码：A  文章编号：1673-260X（2021）02-0010-03

0 引言

新型冠状病毒的爆发已经给人们的日常生活方式带来了很大的影响，随着疫情下人们对无接触支付模式的深入了解，无接触的超市自助结账模式也得到了广大消费者的接受，自助收银机成为人们在超市购物付款时的新选择。为了提高系统的工作效率，现对自助结账系统进行建模优化，利用Petri网的相关性质[1]和行为轮廓的相关知识[2]可以解决很多问题。

如何实现业务流程的优化是当今热门研究课题，目前国内外许多学者在该方面做了大量研究。邵叱风提出了一种利用Java编程实现算数计算Petri网动态模型的模拟，验证了Petri网的模拟能力[3]，同时提出一种日志挖掘方法，利用日志除标签外的属性辅助发现过程模型[4]，另外提出了一种基于过程挖掘的结构优化方法，通过过程挖掘得到模型，再改造关联结构提高流程运行效率[5];应丽等人利用行为轮廓增加相关的控制结构对模型进行优化，并通过分析说明了流程模型优化的有效性[6]。KHAN G等人为了解决服务组成和调度活动面临的性能和复杂性问题，在Petri网的基础上，利用模型和可达图的概念，对安全性、有界性和公平性等进行了形式化分析[7]。

本文以基于Petri网行为轮廓的超市自助结账系统优化为例，帮助顾客在超市购物时可以用更短的时间完成支付。本文结构如下，第一部分介绍Petri网的基本概念，第二部分对基于Petri网的自助结账系统模型进行分析，并给出了优化后的模型，第三部分将优化后的模型通过HIPS[6]仿真软件进行模拟运行，对优化后的模型的结构和行为进行分析。第四部分总结了本篇文章。

1 相关定义

定义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）是强连通图;

（4）dom（F）∪cod（F）=P∪T，其中

dom（F）{x∈P∪T|？埚y∈P∪T，（x，y∈）}

cod（F）{x∈P∪T|？埚y∈P∪T，（y，x∈）};

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

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

（7）s∈T是活动开始的变迁，e∈T是活动终止的变迁.

则称该网为流程模型Petri网。在此定义上，我们定义了网的前集和网的后集。

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

變迁t∈T具有发生权，当且仅当对？坌p∈t：M（p）≥1，记作M[t>;

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

M′（P）=M（P）+1，若p∈t-′tM（P）-1，若p∈′t-tM（P），其他

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

定义4[2]（行为轮廓） 设有网PN=（P，T，F，C），初始标识为M0，对任意给定的变迁满足下列关系：

（1）若t1？酆t2且t2，则称t1和t2为严格序关系，记作t1→t2;

（2）若且t2？酆t1，则称t1和t2为严格逆序关系，记作t1→-1t2;

（3）若且，则称t1和t2为排他序关系，记作t1+t2;

（4）若t1？酆t2且t2？酆t1，则称t1和t2为交叉序关系，记作t1‖t2.

2 超市自助结账系统的建模优化分析

2.1 问题描述

随着疫情下无接触支付模式的发展，以及缓解传统人工结账方式存在的在高峰期排队时间久的问题，越来越多的超市等大型零售场所开始推行消费者自助结账系统，由顾客自行扫描所购商品条码，由超市系统核对信息并计算总金额，顾客扫码支付。如果按照单次商品分别查找，审核和计算金额，会浪费很多时间。现通过Petri网对自助结账系统进行建模优化，可以解决这一问题，提高系统的工作效率。

2.2 模型提出

图1为单件商品的超市自助结账系统，由图可知：从顾客挑选商品开始，t1，t2发生，然后由顾客扫描商品条码，在超市系统提供的商品信息库中识别商品，引发t3发生，t1和t3，t2和t3满足严格序关系，然后t4，t5，t6，t7发生，由超市系统审核商品的重量与商品信息库中重量是否一致，避免发生顾客扫描低价商品后更换高价商品的情况，并产生一个排他关系，记作t8+t9，若t9发生，则系统结束运行，结账失败;若t8发生，则t10，t11，t12，t13继续发生，系统核算金额，进入付款界面，产生两种付款模式t14， t15，它们是一个排他关系，记作t14+t15;接下来t16发生，也产生两种情况，若超时未付款，则t18，t19发生，交易失败;若系统收到付款，则t17，t21，t22发生，交易成功。该模型表示单件商品的结账流程，若购买商品数量较多，则会消耗较多时间。因此，考虑在系统中加入相应的结构变迁，以实现循环，提高效率。

2.3 模型优化

针对图1的模型进行优化时，考虑加入合适的结构变迁，以形成循环，所建优化模型如图2所示，在原模型基础上，增加了变迁t24，使得系统可以在审核完第一件商品后，继续循环审核第二件，最后将金额累计，可以节约时间，提高系统工作效率。

3 仿真软件模拟运行

我们通过HIPS[6]仿真软件进行模拟运行，对优化后的模型的结构和行为进行分析，如图3和图4所示。

使用CPNtools对优化前后后的模型执行时间进行分析，默认每个变迁执行耗时为1，商品数量为1-10。仿真实验结果表明，优化后的自助结账系统的Petri网模型是可行的（如图5所示），相较于优化前结账耗时明显降低（如图6所示）。

仿真实验表明，优化后的自助结账系统的Petri网模型是可行的，相较于优化前结账耗时明显降低。

4 结语

本文构建了基于Petri网构建的超市自助结账系统流程模型，运用Petri网的可达性并分析其行为轮廓，根据Petri网流程模型运行规则，通过添加相关的控制结构，得到优化的目标模型。优化后的模型从一定程度上縮短了时间，提高了系统的工作效率。但是不同超市的系统会有所不同，所以本文在一定程度上具有局限性，今后可以结合更多的超市付款流程，对流程进行进一步的优化和改进，提高模型的适用性。

——————————

参考文献：

〔1〕吴哲辉.Petri网导论[M].北京：机械工业出版社，2006.6-22.

〔2〕方贤文.Petri网行为轮廓理论及其应用[M].上海：上海交通大学出版社，2017.39-40.

〔3〕邵叱风.基于流程挖掘的并行优化算法[J].赤峰学院学报（自然科学版），2019，35（10）：66-70.

〔4〕应丽，王丽丽，刘祥伟.基于Petri网的门诊就医流程模型优化分析[J].延边大学学报（自然科学版），2018，44（01）：79-82.

〔5〕KHAN G， SARKAR A， SENGUPTA S. Behavioral Analysis of Service Composition Patterns in ECBS Using Petri-Net-Based Approach[M]//Advanced Computing and Systems for Security. Springer， Singapore， 2020： 53-66.

〔6〕HARIE Y， MITSUI Y， FUJIMORI K， et al. HiPS： Hierarchical Petri Net design， simulation， verification and model checking tool[C]//2017 IEEE 6th Global Conference on Consumer Electronics （GCCE）. IEEE， 2017： 1-5.