基于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網及其行為輪廓的相關性質分析其模型的一致性和合理性。