基于Petri網(wǎng)的網(wǎng)購(gòu)生鮮品模型優(yōu)化分析

王 娟

(安徽理工大學(xué)數(shù)學(xué)與大數(shù)據(jù)學(xué)院 安徽淮南 232001)

一、引言

業(yè)務(wù)流程建模通過(guò)圖形來(lái)可視化組織執(zhí)行業(yè)務(wù)流程的過(guò)程，是分析解決實(shí)際業(yè)務(wù)流程問(wèn)題的有效方法，因此許多學(xué)者利用Petri網(wǎng)對(duì)業(yè)務(wù)流程建模進(jìn)行了研究。Petri網(wǎng)是分布式系統(tǒng)的建模與分析工具，它不僅直觀，便于溝通和理解，而且可以運(yùn)用數(shù)學(xué)方法來(lái)對(duì)其性質(zhì)進(jìn)行分析；因此，很多學(xué)者利用Petri網(wǎng)對(duì)不同領(lǐng)域的業(yè)務(wù)流程進(jìn)行了建模以及應(yīng)用[1]。

在Petri網(wǎng)的建模研究中，可達(dá)性是研究系統(tǒng)動(dòng)態(tài)特性的最基本的性質(zhì)，也是系統(tǒng)行為分析的基礎(chǔ)。文獻(xiàn)[2]介紹了可達(dá)樹(shù)和可達(dá)圖的概念與構(gòu)造算法；文獻(xiàn)[3]提出了一種新的可達(dá)樹(shù)來(lái)求解無(wú)界網(wǎng)的可達(dá)性問(wèn)題，并且該可達(dá)樹(shù)還可以正確地檢查無(wú)界Petri網(wǎng)的死鎖。但是在實(shí)際流程中，由于受模型的規(guī)模、復(fù)雜程度等因素的影響，Petri網(wǎng)模型的運(yùn)行效率不是很高，所以對(duì)模型進(jìn)行優(yōu)化就顯得尤為重要[4]。文獻(xiàn)[5]提出了一種添加抑制弧對(duì)工作流網(wǎng)進(jìn)行優(yōu)化的算法思想，并利用可達(dá)圖的分析方法說(shuō)明了該算法的有效性；文獻(xiàn)[6]在工作流網(wǎng)的可達(dá)性和合理性的基礎(chǔ)上提出了控制節(jié)點(diǎn)添加優(yōu)化算法、并行優(yōu)化算法和合并優(yōu)化算法，并且對(duì)包含選擇結(jié)構(gòu)和順序結(jié)構(gòu)的輸入模型進(jìn)行了優(yōu)化，可減少平均完成時(shí)間。與普通網(wǎng)購(gòu)相比，在網(wǎng)上購(gòu)買的生鮮品會(huì)因?yàn)闀r(shí)間、溫度等各種因素而變質(zhì)，目前，基于Petri網(wǎng)對(duì)網(wǎng)購(gòu)生鮮品模型進(jìn)行建模和優(yōu)化的研究相對(duì)來(lái)說(shuō)還比較少，利用第三方物流的實(shí)時(shí)定位功能，本文基于Petri網(wǎng)和行為輪廓的思想，建立了網(wǎng)購(gòu)生鮮品的基本業(yè)務(wù)流程模型，并且對(duì)其進(jìn)行可達(dá)性分析；在此基礎(chǔ)上，結(jié)合實(shí)際問(wèn)題對(duì)模型進(jìn)行優(yōu)化分析，使得模型更具有適用性和一致性。

二、基本知識(shí)

定義[1](流程模型Petri網(wǎng))滿足下列條件的六元組PN=稱作一個(gè)流程模型Petri網(wǎng):

（1）S是有限庫(kù)所集，T是有限活動(dòng)變遷集

（2）S≠?,T≠?,且S?T=?

（3）F?(S×T)?(T×S)，F(xiàn)表示網(wǎng)PN的流關(guān)系，并且(S?T，F(xiàn))是一個(gè)強(qiáng)連通圖，即網(wǎng)中沒(méi)有孤立節(jié)點(diǎn)

（4）dom(F)?cod(F)=S?T

其中

（5）C={and,xor,or}是流程網(wǎng)的結(jié)構(gòu)類型

（6）s∈P是唯一的一個(gè)開(kāi)始庫(kù)所，e∈P是唯一的，一個(gè)結(jié)束庫(kù)所。

定義2[1]（變遷發(fā)生規(guī)則）一個(gè)四元組PN=()P,T;F,M0稱為Petri網(wǎng)，并具有下面的變遷發(fā)生規(guī)則：

（1）變遷t∈T具有發(fā)生權(quán)，當(dāng)且僅當(dāng)對(duì)?P∈·t:

（2）在標(biāo)識(shí)M下能使的變遷t經(jīng)發(fā)生后，得到一個(gè)新的標(biāo)識(shí)M'，記作M[t＞M'，則有

定義3[1](可達(dá)性)設(shè)為一個(gè)Petri網(wǎng)。如果存在t∈T，使得M[t＞M'，則稱M'為從M直接可達(dá)的。如果存在變遷序列t1,t2,…,tk和標(biāo)識(shí)序列M1,M2,…,Mk使得M[t1＞M1[t2＞M2…Mk-1[tk＞Mk

則稱Mk為從M可達(dá)的。從M可達(dá)的一切標(biāo)識(shí)的集合記為

定義4[7](行為輪廓)設(shè)是一個(gè)Petri網(wǎng)。對(duì)于任意給定的變遷對(duì)滿足下面的關(guān)系：

(1)若t1?t2且t2?t1，則稱變遷對(duì)(t1,t2)中的t1與t2為嚴(yán)格序關(guān)系，記作t1→t2；

(2)若t1?t2且t2?t1，則稱變遷對(duì)(t1,t2)中的t1與t2為嚴(yán)格逆序關(guān)系，記作t1→-1t2；

(3)若t1?t2且t2?t1，則稱變遷對(duì)(t1,t2)中的t1與t2為排他性關(guān)系，記作t1+t2；

(4)若t1?t2且t2?t1，則稱變遷對(duì)(t1,t2)中的t1與t2為交叉序關(guān)系，記作t1‖t2。

將上述4種關(guān)系的集合稱為網(wǎng)系統(tǒng)的行為輪廓，記作BP={→,→-1,+,‖}。

三、基于Petri網(wǎng)的網(wǎng)購(gòu)生鮮品模型

隨著計(jì)算機(jī)技術(shù)和電商的迅速發(fā)展，人們網(wǎng)購(gòu)生鮮產(chǎn)品呈逐漸增多趨勢(shì)。網(wǎng)購(gòu)生鮮品的基本業(yè)務(wù)流程模型如圖1所示。

圖1 網(wǎng)購(gòu)生鮮品的基本流程模型

上述流程模型可解釋為：顧客在網(wǎng)購(gòu)生鮮品時(shí)，首先要選擇自己想要的生鮮品，然后選好規(guī)格準(zhǔn)備下單。在選擇好收貨地址和支付方式之后便可以支付下單。賣家收到訂單后便接單并且聯(lián)系第三方物流發(fā)貨，發(fā)貨之后會(huì)出現(xiàn)兩種情況：一是由于天氣等意外因素使得配送時(shí)間超時(shí)，另一個(gè)是顧客在約定好的時(shí)間內(nèi)收到商品。當(dāng)配送超時(shí)時(shí)，客戶可以催單，然后繼續(xù)等著商品的到來(lái)。收到商品后，客戶進(jìn)行驗(yàn)貨，如果滿意，可確認(rèn)收貨；如果不滿意，則可以聯(lián)系賣家退貨。

為了解模型（圖1）的狀態(tài)變化和活動(dòng)變遷發(fā)生序列的情況，對(duì)模型進(jìn)行可達(dá)性分析，其對(duì)應(yīng)的可達(dá)標(biāo)識(shí)圖如圖2所示。

圖2 基于Petri網(wǎng)的網(wǎng)購(gòu)生鮮品模型可達(dá)標(biāo)識(shí)圖

四、基于Petri網(wǎng)的網(wǎng)購(gòu)生鮮品模型優(yōu)化

圖1 所建立的模型給出了顧客從購(gòu)買生鮮品到收到生鮮品的一個(gè)流程。然而在現(xiàn)實(shí)生活中，由于時(shí)間、溫度等因素，生鮮品在配送過(guò)程中極易變質(zhì)，所以對(duì)該模型進(jìn)行優(yōu)化。優(yōu)化內(nèi)容如下：顧客在約定時(shí)間內(nèi)，若沒(méi)收到生鮮品，可以主動(dòng)聯(lián)系賣家取消訂單。優(yōu)化后的模型如圖3 所示。

圖3 網(wǎng)購(gòu)生鮮品Petri網(wǎng)結(jié)構(gòu)圖

圖3 中的模型的運(yùn)行過(guò)程如下：變遷T0 發(fā)生（選擇商品），然后T1發(fā)生(下單)，此時(shí)T2和T3處于并發(fā)關(guān)系，即只有在T2（選擇收貨地址）和T3（選擇支付方式）都發(fā)生之后，T4才可以發(fā)生（支付）。顧客支付完成之后，賣家便接單并且安排物流公司發(fā)貨，即T4和T5順序發(fā)生。這時(shí)顧客會(huì)遇到以下兩種情況：一種是顧客在約定時(shí)間內(nèi)收到商品，即T8 發(fā)生，另一種是由于天氣、交通等意外因素導(dǎo)致配送時(shí)間過(guò)長(zhǎng)，顧客長(zhǎng)時(shí)間未收到商品，即T6發(fā)生。T8發(fā)生時(shí)，顧客可根據(jù)商品的新鮮程度判斷是否滿意，如果滿意，則確認(rèn)收貨，該交易流程結(jié)束，即變遷序列T9T10發(fā)生；如果不滿意，則顧客聯(lián)系賣家退貨，即變遷序列T11T12發(fā)生。在超時(shí)情況下，顧客要么催單，然后繼續(xù)等著生鮮品的到來(lái)，即變遷T6發(fā)生；要么直接與賣家協(xié)商退貨，此時(shí)T14和T15是并發(fā)關(guān)系，也就是說(shuō)只有在顧客取消訂單并且拒收該快遞后，T16才可以發(fā)生，這一過(guò)程即變遷序列T13（T14T15+T15T14）T16發(fā)生。

雖然該系統(tǒng)考慮到了生鮮品會(huì)因時(shí)間過(guò)長(zhǎng)而引起變質(zhì)，但是在實(shí)際的網(wǎng)購(gòu)生鮮品系統(tǒng)中，一旦賣家接單并聯(lián)系物流公司發(fā)貨之后，賣家和顧客便不清楚商品在運(yùn)送過(guò)程中的情況了，比如說(shuō)物流的實(shí)時(shí)位置。

為了優(yōu)化上述問(wèn)題，本文給出了如圖4所示的基于Petri網(wǎng)的網(wǎng)購(gòu)生鮮品優(yōu)化模型。該模型引入第三方物流這一主線流程。當(dāng)賣家接單之后便通知物流公司開(kāi)始配送，物流公司收到訂單之后便準(zhǔn)備安排車輛開(kāi)始配送，即T17發(fā)生，并且還要利用定位系統(tǒng)對(duì)快遞進(jìn)行實(shí)時(shí)定位，即T18發(fā)生。顧客可以查看定位判斷配送時(shí)間是否過(guò)長(zhǎng)，如果正常，即T8發(fā)生，則顧客等著收到商品；如果配送超時(shí)，即圖中T6 發(fā)生。此時(shí)T13和T20處于排他關(guān)系，即：顧客要么催單，直接等著生鮮品的到來(lái)；要么直接與賣家協(xié)商拒收退款。這樣便使得顧客能夠了解生鮮品在運(yùn)送過(guò)程中的實(shí)時(shí)位置，提高了用戶的使用滿意度。

圖4 實(shí)時(shí)定位監(jiān)控的優(yōu)化模型Petri網(wǎng)結(jié)構(gòu)圖

五、用PIPE軟件進(jìn)行仿真模擬

為了驗(yàn)證優(yōu)化模型的有效性，本文借助PIPE 軟件對(duì)模型進(jìn)行模擬運(yùn)行，運(yùn)行過(guò)程如下。

首先，打開(kāi)PIPE 安裝目錄中的launch.bat 文件，按一下回車鍵，然后在彈出的界面中畫(huà)出所建立的模型Petri網(wǎng)結(jié)構(gòu)圖，如圖5所示：

圖5 PIPE中構(gòu)建的實(shí)時(shí)定位監(jiān)控的優(yōu)化模型Petri網(wǎng)結(jié)構(gòu)圖

然后雙擊右上角的State Space Analysis 選項(xiàng)，如圖6所示；再點(diǎn)擊所彈出界面的Analysis按鈕，便可得到該模型的仿真結(jié)果，如圖7所示。

圖6 PIPE界面的State Space Analysis選項(xiàng)位置

圖7 仿真結(jié)果圖

圖7表明，本文所建立的Petri 網(wǎng)優(yōu)化模型是有界的、安全的，這表明本文優(yōu)化后的模型是有效的。

六、結(jié)語(yǔ)

本文基于Petri網(wǎng)構(gòu)建了網(wǎng)購(gòu)生鮮品的基本流程模型，并對(duì)其進(jìn)行了可達(dá)性分析。然后對(duì)該模型做了兩步優(yōu)化：一是在配送時(shí)間過(guò)長(zhǎng)的情況下，用戶可以直接聯(lián)系賣家協(xié)商退貨；二是利用第三方物流的實(shí)時(shí)定位情況來(lái)對(duì)網(wǎng)購(gòu)生鮮品過(guò)程進(jìn)行了優(yōu)化，最后利用PIPE 軟件驗(yàn)證了該優(yōu)化模型是有效、合理地?？蛻粼诰W(wǎng)購(gòu)生鮮品時(shí)，除了配送時(shí)間會(huì)引起變質(zhì)，溫度過(guò)高等其他因素也可能會(huì)引起生鮮品變質(zhì)，所以今后本文可以從配送過(guò)程中溫度的控制方面來(lái)進(jìn)行建模分析，另外今后還會(huì)從日志中挖掘出活動(dòng)之間的具體關(guān)系，以找到實(shí)用性更強(qiáng)的模型。