基于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.