基于Petri網(wǎng)的分區(qū)間購(gòu)票系統(tǒng)建模優(yōu)化分析

陳 榮，方賢文

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

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

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

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

（3）F?(P×T)?(T×P)表示PN的流關(guān)系且(P?T,F)是強(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)識(shí)，Mj是網(wǎng)的終止標(biāo)識(shí)，且Mj是死標(biāo)識(shí)；

（7）s∈T是活動(dòng)開始的變遷，e∈T是活動(dòng)終止的變遷。

定義2[15]（變遷發(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:M(p)≥1，記作M[t＞；

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

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

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

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

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

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

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

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

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

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

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

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

圖2 購(gòu)票App的網(wǎng)絡(luò)購(gòu)票流程圖

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

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

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

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

4 小結(jié)

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