郝惠晶　王麗麗　劉祥偉

（1.安徽理工大學數學與大數據學院；2安徽理工大學經濟與管理學院　安徽淮南　232001）

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

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

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

一、基本概念梳理

下面僅介紹流程模型Petri網的定義及其可達性，闡述了行為輪廓的相關定義，其他概念。

定義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，F）是強連通圖；

（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}是流程網的結構類型；

（6）M0是網的初始標識，Mf是網的終止標識，且Mf是死標識；

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

則稱該網為流程模型Petri網。

在此定義上，我們定義了網的前集和網的后集。

定義2[1]（前集和后集）設N=（P，T，F）為一個網，我們用X=P∪T表示所有的節(jié)點，用F+表示流關系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網，并具有下面的變遷發(fā)生規(guī)則

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

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

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

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

則稱Mk為從M可達的。從M可達的一切標識的集合記為 R（M）。

定義5[3]（行為輪廓）設（N，M0）是一個網，初始標識為M0。對任給的變遷對（t1,t2）∈（T×T）滿足下面關系;

（1）若 t1＞t2且 t2≯t1，則稱嚴格序關系，記作 t1→t2；

（2）若 t1≯t2且 t2＞t1，則稱嚴格逆序關系，記作 t1→-1t2；

（3）若 t1≯t2且 t2≯t1，則稱排他關系，記作 t1//t2;

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

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

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

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

圖1　網上購火車票流程圖

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

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

圖2　網絡購火車票模型Petri網結構圖

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

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

圖3　網絡購火車票優(yōu)化模型Petri網結構圖

三、結語

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

參考文獻：

[1]吳哲輝.Petri網理論[M].北京：機械工業(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.