郝惠晶　王麗麗　劉祥偉

（1.安徽理工大學(xué)數(shù)學(xué)與大數(shù)據(jù)學(xué)院；2安徽理工大學(xué)經(jīng)濟(jì)與管理學(xué)院　安徽淮南　232001）

隨著計算機(jī)技術(shù)的快速發(fā)展及其廣闊的應(yīng)用前景，網(wǎng)絡(luò)建模已經(jīng)成為分析解決業(yè)務(wù)流程問題的常用方法。在建模過程中可能會因?qū)嶋H問題情況復(fù)雜交互而出現(xiàn)不適用或者不一致的情形，那么依據(jù)行為輪廓及Petri網(wǎng)的相關(guān)性質(zhì)進(jìn)行建模優(yōu)化就顯得尤為重要。而Petri網(wǎng)的行為輪廓理論是以合理的自由選擇petri網(wǎng)為基礎(chǔ)，從過程行為角度建模，使得Petri網(wǎng)模型間的行為關(guān)系具體化、數(shù)字化，直觀的刻畫了行為間的內(nèi)部關(guān)系[1]。

對流程模型進(jìn)行優(yōu)化最終獲得最優(yōu)的模型成為了國內(nèi)外學(xué)者關(guān)注的課題。因此確定模型變化部分且進(jìn)行優(yōu)化分析顯得越來越重要。

本文基于Petri網(wǎng)和行為輪廓的思想，以合理的自由選擇網(wǎng)為基礎(chǔ)，從過程行為角度建模，提出了網(wǎng)絡(luò)購票系統(tǒng)模型的優(yōu)化分析。為了使得購票人在網(wǎng)絡(luò)購票系統(tǒng)中更方便快捷的購買到合適的車票，并且針對改簽退票過程可能出現(xiàn)的情況，結(jié)合Petri網(wǎng)中庫所變遷的行為關(guān)系分析優(yōu)化流程模型，使其達(dá)到適用性和一致性。

一、基本概念梳理

下面僅介紹流程模型Petri網(wǎng)的定義及其可達(dá)性，闡述了行為輪廓的相關(guān)定義，其他概念。

定義1[2]（流程模型Petri網(wǎng)）一個流程模型Petri網(wǎng)PM=(P,T,F,C,s,e)是一個六元組，滿足以下條件：

（1）P是有限庫所集，T是有限活動變遷集；

（2）P≠?，T≠?且 P∩T≠?；

（3）F?（P×T）∪（T×P）表示 PN 的的流關(guān)系且（P∪T，F(xiàn)）是強(qiáng)連通圖；

（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}是流程網(wǎng)的結(jié)構(gòu)類型；

（6）M0是網(wǎng)的初始標(biāo)識，Mf是網(wǎng)的終止標(biāo)識，且Mf是死標(biāo)識；

（7）s∈T是開始活動變遷，e∈T是終止活動變遷。

則稱該網(wǎng)為流程模型Petri網(wǎng)。

在此定義上，我們定義了網(wǎng)的前集和網(wǎng)的后集。

定義2[1]（前集和后集）設(shè)N=（P，T，F(xiàn)）為一個網(wǎng)，我們用X=P∪T表示所有的節(jié)點(diǎn)，用F+表示流關(guān)系F的不自反傳遞閉包。對 x∈X，·x={y|y∈P∪T∧（y,x）∈F}表示 x的前集，x·={y|y∈P∪T∧（x,y）∈F}表示 x的后集。

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

（1）變遷 t∈T具有發(fā)生權(quán)，當(dāng)且僅當(dāng)對?P∈·t：M（P）≥1，記作 M[t＞；

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

定義4[1]（可達(dá)性）已知Petri網(wǎng)PN=（P，T；F，M），如果存在t∈T，，使M[t＞M'，則稱M'為從M直接可達(dá)的。如果存在變遷序列t1,t2…，tk和標(biāo)識序列使得

M[t1＞M1[t2＞M2…Mk-1[tk＞MK

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

定義5[3]（行為輪廓）設(shè)（N，M0）是一個網(wǎng)，初始標(biāo)識為M0。對任給的變遷對（t1,t2）∈（T×T）滿足下面關(guān)系;

（1）若 t1＞t2且 t2≯t1，則稱嚴(yán)格序關(guān)系，記作 t1→t2；

（2）若 t1≯t2且 t2＞t1，則稱嚴(yán)格逆序關(guān)系，記作 t1→-1t2；

（3）若 t1≯t2且 t2≯t1，則稱排他關(guān)系，記作 t1//t2;

（4）若 t1＞t2且 t2＞t1，則稱交叉序關(guān)系，記作 t1×t2；

（5）將所有關(guān)系的集合叫做網(wǎng)系統(tǒng)的行為輪廓，記作BP={→,←-1，//，x}

二、基于Petri網(wǎng)的網(wǎng)絡(luò)購票系統(tǒng)的建模優(yōu)化分析

隨著網(wǎng)絡(luò)技術(shù)的普及，人們出行購買火車票不再局限于去窗口排隊購票，更多的是采取網(wǎng)絡(luò)購票，基本的網(wǎng)絡(luò)購票流程如下圖1所示。

圖1　網(wǎng)上購火車票流程圖

通常在網(wǎng)上購買火車票，需要先進(jìn)入官網(wǎng)，登錄個人賬戶，登錄成功后進(jìn)入車票預(yù)訂的界面，依次選擇好出發(fā)地，目的地，以及出行的日期等，點(diǎn)擊查詢，就會出現(xiàn)符合要求的所有車次。添加常用聯(lián)系人，并選定購票人，確認(rèn)無誤后提交訂單，然后進(jìn)行支付，現(xiàn)行支付的方式有支付寶，微信或者銀行卡等不同方式。支付成功后就會跳出購票成功的頁面，之后就可以取票上車了。但是，在網(wǎng)絡(luò)購票過程中，我們可能會遇到選擇的出發(fā)地和目的地沒有可供選擇的車次，或者購票成功后因突發(fā)情況需要改簽或者退票，那么此時我們應(yīng)該如何對網(wǎng)絡(luò)購票進(jìn)行控制與優(yōu)化呢？下面我們就通過Petri網(wǎng)來對這些情況進(jìn)行建模分析。

上述模型給出了簡單的從用戶登錄到購票成功的一個流程。但是如果用戶在查詢火車票的車次時沒有從出發(fā)地到目的地的直達(dá)火車票，那么就需要通過中轉(zhuǎn)來乘車，這里就需要在模型中構(gòu)建一個最優(yōu)的乘車方案，使得購票人能選擇合適的車程出行。還有就是購票人在購票成功以后因意外情況需要改簽時間地點(diǎn)或者需要退票重新購票，在改簽過程中，購票人需考慮改簽票是否與所購火車票時間沖突，如果沖突的話就需要退票重新購票，不沖突就只需要直接改簽。圖2我們用流程Petri網(wǎng)來建模。

圖2　網(wǎng)絡(luò)購火車票模型Petri網(wǎng)結(jié)構(gòu)圖

圖2中變遷t1（登錄）發(fā)生，然后t2發(fā)生，t3和t4是排他關(guān)系，如果有直達(dá)票直接選擇高鐵或者普快直達(dá)，否則需要購買中轉(zhuǎn)票，t4發(fā)生，同樣會出現(xiàn)一個排他結(jié)構(gòu)t5和t6，分別考慮高鐵和普快，選擇最優(yōu)的乘車方案，進(jìn)而選擇合適的車次，接著t9、t10、t11、t12發(fā)生，購票完成。如果購票人確認(rèn)取票則t13發(fā)生，如果因其他原因要選擇改簽或者退票，則t14和t17排他發(fā)生，假設(shè)改簽就需要考慮是否是所購票時間沖突，不沖突直接選擇改簽的時間和地點(diǎn)，沖突就需要先退票后選擇購票信息，這個就是t15和t16的排他發(fā)生。而如果是選擇退票的話，有兩種情況，一種是退票后不購票了，另一種就是退票后重新選擇購票信息。此系統(tǒng)雖整體反映了網(wǎng)絡(luò)購票的所有情況，但是對于改簽情況下不需要重新選擇購票人和改簽到其他時間段不需要考慮時間沖突的問題沒有給出合理的控制。

所以，為了優(yōu)化上述結(jié)構(gòu)，我們通過圖3給出了優(yōu)化后的網(wǎng)絡(luò)購票模型Petri網(wǎng)結(jié)構(gòu)圖，通過用紅色框標(biāo)示出來，增加了幾個新的變遷。如果是改簽狀態(tài)下，我們不再需要選擇購票人，即t10發(fā)生。如果選擇改簽，還需要考慮過有沒有改簽過，沒有改簽過，那么t16發(fā)生，若t17發(fā)生則說明改簽過一次，就不能再次改簽只能選擇退票。而且改簽狀態(tài)下，看改簽的時間點(diǎn)，如果改簽到當(dāng)天（t19發(fā)生），就需要考慮改簽時間沖突與否，即與圖2所示一樣。如果改簽到其他時間段的話，即圖3中t18發(fā)生，就不用再考慮時間沖突問題，直接選擇時間地點(diǎn)進(jìn)行改簽即可，這樣就比較全面的考慮到網(wǎng)絡(luò)購票的整體流程，實(shí)現(xiàn)了建模系統(tǒng)的優(yōu)化。

圖3　網(wǎng)絡(luò)購火車票優(yōu)化模型Petri網(wǎng)結(jié)構(gòu)圖

三、結(jié)語

本文基于Petri網(wǎng)給出了網(wǎng)絡(luò)購票模型一種優(yōu)化方法。根據(jù)Petri網(wǎng)的變遷發(fā)生規(guī)則及其可達(dá)性和行為輪廓的排他性等基本性質(zhì)，通過增加相應(yīng)的結(jié)構(gòu)變遷對其進(jìn)行優(yōu)化。構(gòu)建的模型包括順序關(guān)系的流程圖及具有排他關(guān)系的變遷發(fā)生序列，利用改簽和退票間的交互關(guān)系優(yōu)化購票系統(tǒng)。使模型應(yīng)用更加全面，也體現(xiàn)了該模型在實(shí)際生活中的適用性。

參考文獻(xiàn)：

[1]吳哲輝.Petri網(wǎng)理論[M].北京：機(jī)械工業(yè)出版社，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.