陳 榮，方賢文

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

隨著計算機技術的發(fā)展，網(wǎng)絡建模已經(jīng)得到廣泛的應用。在建模過程中會因為實際問題的復雜而出現(xiàn)不合適的現(xiàn)象，如何改進這些模型，這就突顯了Petri網(wǎng)相關性質及行為輪廓的重要性。Petri網(wǎng)是一種模型構建方式，它可以描述系統(tǒng)中各結構和行為之間的關系還可以描述系統(tǒng)的動態(tài)性質如：活性、有界性，使得系統(tǒng)直觀化[1-2]。

目前，有很多學者都在Petri網(wǎng)的行為輪廓、過程挖掘和結構方面做了建模優(yōu)化分析，例如：文獻[3]以行為輪廓為基礎,提出了基于配置約束的業(yè)務流程模型優(yōu)化方法，并信用證交易系統(tǒng)的實例驗證了優(yōu)化模型結構。文獻[4]從行為輪廓的理論和應用方面對模型進行優(yōu)化。文獻[5]給出了一些有關行為輪廓的性質和分析方法，闡述了有關序關系的對稱性及相關性質。文獻[6]從行為輪廓角度對Petri網(wǎng)的性能加以分析，為優(yōu)化模型性能提供了有效的方法。文獻[7]提出了一種基于過程挖掘的結構優(yōu)化方法，利用過程挖掘獲取實時模型，通過對關聯(lián)結構的改造降低流程耗時。文獻[8]使用S不變量和T不變量對修正時間賦時變遷Petri網(wǎng)（Modified timed transition Petri net，MTTPN）分析的方法對裝配線進行了建模和節(jié)拍優(yōu)化。文獻[9-10]利用隨機理論建立和優(yōu)化模型，通過計算比較驗證優(yōu)化模型的有效性。也有學者在網(wǎng)絡購票及選座優(yōu)化方面進行了研究，如文獻[11]提出了網(wǎng)絡選座過程中出現(xiàn)的一些問題，在結合實際經(jīng)驗基礎上提出網(wǎng)絡選座的對策，并通過實例分析驗證了優(yōu)化方法的有效性。文獻[12]提出了網(wǎng)絡購票系統(tǒng)建模優(yōu)化分析方法，通過增加相關的活動變遷和庫所對業(yè)務流程模型進行了優(yōu)化。文獻[13]利用PIPE軟件分析了優(yōu)化模型是有界安全的。目前，利用Petri網(wǎng)對分區(qū)間購票的研究尚未見相關報道。考慮到為了使分區(qū)間購票最大便利化，本文利用Petri網(wǎng)并以自由選擇網(wǎng)為基礎，提出一種基于Petri網(wǎng)的分區(qū)間購票系統(tǒng)的優(yōu)化模型，并用Hips軟件分析優(yōu)化模型的合理性和有效性。

1 基本概念

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

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

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

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

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

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

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

定義3[16]（行為輪廓）設N,M0是一個Petri網(wǎng)，初始標識為M0，對任意給定的變遷(t1,t2)∈(T×T)。滿足下列關系：

（1）若t1?t2且t2?t1，則稱t1和t2為嚴格序關系，記作t1→t2；

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

（3）若t1?t2且t2?t1，則稱t1和t2為排他序關系，記作t1+t2；

（4）若t1?t2且t2?t1，則稱t1和t2為交叉序關系，記作t1‖t2；

（5）將所有的關系集合稱為網(wǎng)系統(tǒng)的行為輪廓，記作BP={→,←-1,+,‖}。

2 基于Petri網(wǎng)的建模優(yōu)化分析

在分區(qū)間購票的情況下，網(wǎng)絡購票的優(yōu)勢更加明顯，網(wǎng)絡購票包含網(wǎng)上選票和支付兩個環(huán)節(jié)?；镜木W(wǎng)絡購票流程如圖1。

圖1 淘寶以及其他購物App的網(wǎng)絡購票流程圖

網(wǎng)絡購票通常由登錄、選擇和支付3個流程構成。乘客首先打開購物App，登錄成功后在搜索欄輸入關鍵詞，搜索后會出現(xiàn)一系列車票，選擇合適的車票加入購物車或者是立即購買，同時要選擇相應的車票類型如座位位置、座位等級，然后選擇付款，付款成功后代表購票成功，如圖1。另外，還有其他的購票方式如圖2。在乘客登錄后，依次設置區(qū)間，選擇日期，查詢余票，若變遷序列t4t6、t4t7、t5t9發(fā)生，這時就有排他關系t6、t7、t8和t9、t10，如果直達分區(qū)間無票則t8、t11發(fā)生。如果分區(qū)間無票則t10發(fā)生，即購票失敗。若t12、t13、t14、t16、t17、t18順序發(fā)生,則購票成功，同樣會有排他關系t15、t16，若乘車人信息不正確則購票失敗[17-19]。

從上述描述中可以看出，圖1的購票流程雖然簡單，但是圖1對乘客信息驗證不夠嚴格，只是憑票入座，如果乘客的票據(jù)丟失就會影響到出行。相比之下，圖2檢驗了乘客的乘車信息，實名認證在一定程度上解決了乘客票據(jù)丟失問題。但是上述兩種出行方式都存在一些問題如先選擇座位后付款，這樣先購買車票的乘客就會先擁有座位，后面的乘客在購票時就只能被動選座。在購票過程中，有時出發(fā)地和目的地沒有直達車票，這種情況乘客就必須分區(qū)間購票，被動選座的乘客就要在車上來回換座，尤其在站點停靠時，車內(nèi)的人流量就會增多，造成車內(nèi)擁堵，除此之外分區(qū)間購票的費用會比直達車票的費用高，這又在一定程度上給乘客出行帶來不便?；谶@些問題，本文建立一種優(yōu)化購票模型，見圖3。

圖2 購票App的網(wǎng)絡購票流程圖

圖3 網(wǎng)絡購票優(yōu)化模型petri網(wǎng)結構圖

為了優(yōu)化圖1和圖2流程，增加t21～t3010個變遷建立了優(yōu)化模型圖3。從各變遷的關系可知，通過交換變遷t17和t18的發(fā)生順序，付款成功后，在發(fā)車前一天顯示座位，可以在一定程度上減少乘客來回換座的情況，緩解了車內(nèi)擁堵現(xiàn)象。如果乘車人信息正確才能選擇車票有嚴格序關系t16、t22發(fā)生。如果乘客選擇一張車票，可以直接進入付款環(huán)節(jié)，即t23t18t31t17t19變遷序列發(fā)生。如果乘客選擇的車票多于一張，在核驗信息時是同一乘車人且發(fā)車間隔小于等于24小時，這時系統(tǒng)會自動生成長途票價進入付款環(huán)節(jié)，即t24t25t27t28t30t18變遷序列發(fā)生，如果是同一乘車人但是發(fā)車間隔大于24小時和不是同一乘車人的情況，都不能生成長途票價，直接進入付款環(huán)節(jié)，即(t24t25(t26+t27t29))t18變遷序列發(fā)生。經(jīng)過上述分析，可以看出優(yōu)化的流程給乘客帶來了更多便利，也比較全面考慮到乘客從購票到乘車的整體流程，實現(xiàn)了建模系統(tǒng)的優(yōu)化。下面將從模型分析的角度，驗證優(yōu)化模型的合理性和有效性[20-21]。

3 優(yōu)化模型的仿真模擬

為了驗證圖3的合理性，本文利用Hips對優(yōu)化后的模型進行結構分析，首先，在Hips軟件中畫出優(yōu)化模型的結構圖，然后在初始庫所里放入一個token分析模型的狀態(tài)。結果表示，該優(yōu)化模型是無死鎖、有界、安全的模型。

4 小結

本文基于Petri網(wǎng)的理論知識，構建了關于網(wǎng)絡購票的兩種基本模型，通過增加相關活動變遷對兩種網(wǎng)絡購票模型結合優(yōu)化，得到一種新的網(wǎng)絡購票模型。最終的優(yōu)化模型不僅解決了分區(qū)間購票票價高的問題，而且在一定程度上緩解了車內(nèi)擁擠現(xiàn)象，給乘客出行帶來便利。最后通過Hips軟件進一步驗證了優(yōu)化模型的合理性。