基于Petri 網的駕校預約系統優化分析

張昊宇

（安徽理工大學 數學與大數據學院，安徽 淮南 232001）

1 引言

隨著科技的發展，人們的出行服務對于汽車的需求量不斷增加，駕校的用戶數量也在不斷上漲，據公安部統計，2019 年全國新注冊登記機動車3214 萬輛，2020 年全國新注冊登記機動車3328 萬輛。駕校預約系統作為自動化處理平臺，可以幫助駕校管理人員規范學員數據，按照預約順序排列練車名單，提高業務處理效率，也可以幫助學員更簡易化地進行線上預約流程。但隨著駕校學員數量的快速增長，傳統的駕校預約業務流程已無法同時滿足大量用戶對練車的需求，因此對于業務流程的優化變得愈加重要。

Petri 網是1962 年由德國科學家Carl Adam Petri 在他的博士論文 “Kommunikation mit Automaten”中首先提出來的。它是分布式系統、業務流程的建模和分析工具，被廣泛應用到各大領域。特別便于描述系統中進程或部件的順序、并發、沖突以及同步等關系。同其他系統網模型相比較，對真并發的恰切描述是Petri 網的獨特優勢。作為一種系統模型，Petri 網不僅可以刻畫系統的結構，而且可以描述系統的動態行為（如系統的狀態變化等）。Petri 網作為一種最常見的流程建模工具，廣泛應用于各種業務流程建模、分析和優化，面對復雜而交互的模型，Petri 網作為一種專業的圖形化數學工具，體現了優秀的分析性和擴充性，Petri 網可以很好地處理模型間的行為關系以及正確性驗證，以此分析模型間的交互行為[1]。

通過分析Petri 網中活動間的行為輪廓關系，并采用不同的配置信息可以實現對基于Petri 網的業務流程進行優化。Smirnov 等人使用行為輪廓對業務流程模型的描述和優化，使用了閾值對行為進行分析判別抽象模型間行為關系的方法，通過結合模型間的弱序關系，改變和增添模型間的行為輪廓關系，對原始模型進行優化，使優化模型的結構更加完善[2]。Aalst 等人使用配置信息對于業務模型進行正確性驗證[3]，Sobociński 等人使用了分布函數對于配置信息的概念介紹[4]。Weidlich 等人提出了一種基于行為輪廓增加變遷的手段對模型進行搜索優化的方法[5]。向小陽等人使用了基于Petri 網的配置信息對智能快遞柜系統中的投放和取件流程進行優化，用戶通過選擇收件方式來改變快遞員的投遞方式，提高購物體驗[6]。

本文采用Petri 對駕校預約系統的業務流程進行建模，通過分析活動間的行為輪廓關系來檢驗該模型的合理性。該模型包括了從用戶注冊預約、駕校收到學員名單后開始安排練車、學員收到通知后考慮是否有時間練車、駕照考試等基本流程。通過分析該模型的動態行為，以發現該模型建模的業務流程中存在的不足，如用戶等待時間長，用戶和約車時間沖突等問題，并通過添加配置信息對原模型進行了優化，實現了駕校預約系統的業務效率的有效提高，很好地解決了當前駕校中普遍存在的問題。

2 基本概念

Petri 網是用于描述分布式系統的一種模型。它既能描述系統的結構，又能模擬系統的運行，描述系統結構的部分稱為網，它可以通過對業務模型的優化和配置約束的添加來滿足用戶的使用需求[1]。

定義1（流程模型） 設∑(A,ai,a0,C,F,T)為一個六元組的流程模型[2]，其中：

（1）T 為一個非空的活動變遷節點集，C 為控制流的節點集，A 和C 互不相交；

（2）ai∈A 為一個最初的活動變遷，a0∈A 為一個最終的活動變遷；

（3）F?(A{a0})∪C×(A{a}∪C 為流關系；

（4）T：C→{ang,or,xor}為流程模型控制流的類型。

定義2（行為輪廓） 設一個網系統(N,M0)。其中N=(P,T,F)初始標識是M0；對于任意給定的變遷(t1,t2)∈(T×T)。滿足如下關系:

若t1?t2，且t2?/t1，則稱為嚴格序關系，記作t1→t2；

若t1?/t2，且t2?/t1，則稱為排他序關系，記作t1+t2；

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

若t1?/t2，且t2?t1，則稱為嚴格逆序關系，記作t1→－1t2。

將以上幾種關系構成網N 的行為輪廓，記為BP={→，→－1，+，‖}[2]。

定義3（可達性） 已知Petri 網PN=(P,T;F,M),如果存在t∈T,使M[t＞M'，則稱M' 為從M 直接可達的。如果存在變遷序列t1,t2,…，tk和標識序列M1,M2,…，Mk使得:則稱Mk為從M 可達的，從M 可達的一切標識的集合記為R(N)[1]。

定義4（變遷發生規則） 一個四元組PN=(P,T;F,M0)稱為Petri 網，并具有下面的變遷發生規則[1]：

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

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

定義5（配置） 設N=（P，T，F）是一個工作流網，CN∈T→{allow,hide,block} 是網N 的一個配置。則定義:

定義6一個工作流網是合理的當且僅當[1]：

（1）對于任意的標識，都存在一個發生序列M，使得初始庫所可以通過M 到達終止庫所。

（2） 通過一個初始標識發生而發生的中間標識，如果此時的終止庫所里至少有一個token，該狀態就是終止狀態。終止時，該工作流網終止庫所中有且僅有一個標識，并且整個工作流程只有唯一的一個標識。

（3）無死鎖，即該Petri 網是活的。

3 基于Petri 網的駕校預約系統初始模型

在目前的駕校練車系統中，雖然對于用戶的練車需求由教練根據情況安排，但仍需要人工的審核和電話咨詢，在預約過程中，為保證學員練車預約的公平性是非常必要的。但在實際生活中，常常有預約不上練車或預約剛開始名額就已滿額，導致部分學員多次預約不上練車的情況。依據某駕校A的預約系統流程，建立Petri 網模型如圖1 所示，各變遷對應的活動名稱如表1 所示。

圖1 駕校練車預約系統Petri 網圖

表1 駕校練車預約系統Petri 網中所示變遷含義

駕校練車預約系統業務流程模型如圖1 所示，用戶在進入系統時選擇登陸方式，未注冊用戶進行賬號注冊，已注冊賬號用戶直接登錄并進行信息驗證，驗證通過后進入系統，用戶進入系統后進行繳費，預約后等待駕校安排練車，駕校在獲取已預約的學員名單后，進行練車時間安排，由教練通知學員相應的練車時間，學員在收到練車安排的通知后，根據個人是否有時間進行練車來選擇進入此輪練車或等待下一輪練車安排，在教練對學員進行練車評測后，練車合格的用戶進入考試階段，未合格用戶進行下一輪練車預約，通過考試的用戶成功畢業，未通過考試的用戶進行下一次考試預約。

模型中的變遷相互影響，例如用戶在登錄界面選擇登陸方式后，未注冊用戶t2和已注冊用戶t3互為排他序關系（記為：t2+t3）；若用戶已經注冊賬號，則用戶進行賬號輸入t5與系統進行信息驗證t8按順序依次發生，互為嚴格序關系（記為：t5→t8）；未注冊用戶進行注冊后，系統驗證注冊信息合法性t6與系統內驗證注冊信息重復性t7互為交叉序關系（記為：t6‖t7）。

通過分析圖1 所示的業務流程圖，可以發現該系統中存在兩個問題：（1）學員缺失自主選擇機會，在系統流程中只能通過被動的接收駕校通知的時間來進行個人練車時間的安排，缺乏自主性。（2）在學員收到駕校練車通知后，學員將根據有無時間進行后續流程變遷的選擇。若學員此次無時間練車，將重新排隊預約下次練車時間。當系統中等待練車的用戶數量較多時，將可能會導致部分無時間練車的用戶在放棄此次練車機會后，出現下一次預約等待周期較長，或者再次收到不適合自己的練車時間通知等現象，從而使得平臺預約效率低，學員產生較多的抱怨甚至長期預約不上合適的練車時間。所以目前的駕校預約系統不能動態根據用戶和駕校時間自動安排雙方都合適的練車時間。存在不足的業務流程子模塊如圖1 中的虛線所示。本文對此問題開展了研究，并對當前的駕校預約流程提出了較好的解決方案。

4 基于Petri 網的駕校預約系統優化過程模型

在圖1 模型中，當用戶高峰期時，排隊預約的模型機制很容易使得部分用戶始終處于等待階段，為解決用戶高峰期時約車難問題，使預約系統效率得到提高，本文通過增添變遷配置信息的概念，對部分變遷增加配置信息，通過對原有的變遷加入{hide，block，allow}其中的一個值，來對模型進行約束，改變原有的路徑。其中配置信息hide（隱藏）變遷表示路徑中觸發此變遷時會默認進行跳過，且后續路徑的變遷正常發生；block（阻塞）變遷表示默認處于阻塞封閉狀態，如果沒有其他路徑可以選擇，則該路徑后續變遷也不發生；allow（允許）變遷指此變遷既不隱藏也不阻塞，不受約束條件影響。

針對圖1 中虛線框部分所出現的第一個問題，在優化模型時，增加了用戶自主選擇預約時間的途徑，不選擇預約時間t13設定為hide 變遷，默認用戶并不選擇預約時間，變遷用戶進行自選時間t14對于這些用戶也是阻塞的，若用戶選擇了特定時間段進行預約練車，則進入變遷t14的后續路徑，若用戶預約的時間段，駕校練車名單有空余，則用戶直接進行練車，若駕校該時段練車名單已滿，則和默認不選擇的用戶一并進入等待階段，通過此種途徑對高峰練車時期的用戶進行分流，降低練車預約難度。

針對預約練車名額時部分學員始終預約失敗所導致的公平性問題，為部分變遷增添配置信息并在系統中為當次流程循環中沒有預約上練車名額的用戶增加預約優先級。設定t24變遷為block 變遷，此時默認駕校通知的學員有時間進行練車，對于有時間進行練車的用戶而言，模型不會執行t24變遷以及后面的流程，若用戶無練車時間，則會觸發t24變遷，進行后續的流程。對于進入t24變遷后續路徑的學員，駕校進行人數統計，安排教練對于此類學員進行預約等級的提升，在下一輪的預約練車名單流程中，這些學員具有更高的預約優先權。例如同一批練車學員進行練車預約，駕校在統計的此批次練車名單中，篩選其中上一輪練車中未有時間練車已提高預約優先級的學員，將此批次學員在此輪練車安排中優先對學員預約的時間進行考慮，若此時間段無空閑名額，則在駕校安排的順序名單中，將此批次學員提前，以此來解決部分時間段內無空閑時間用戶始終無法預約到練車機會的問題。優化后的模型如圖2 所示，優化部分使用虛線框標識。新增變遷對應的活動如表2 所示。

圖2 基于配置信息的優化模型

表2 基于配置信息的優化模型中新增變遷含義

5 仿真實驗與分析

為了驗證優化后模型的合理性，本文利用Petri 網分析軟件——PIPE 對優化后的模型進行結構分析。PIPE 是一個支持Petri 網模型設計和分析的開源軟件，在通過PIPE 軟件對優化后的模型進行仿真運行后，測試結果如圖3 所示，結果表明優化后的模型能夠正確的按照預期的變遷路線進行運行，直到流程結束，具有良好的正確性，在圖3 的結果分析中也表明優化后的模型具有良好的有界性和安全性，無死鎖問題。

圖3 PIPE 模擬運行結果

6 總結

本文基于Petri 網對實際駕校練車預約流程進行建模，通過對模型的動態分析，發現目前的駕校預約流程缺少用戶自主選擇性與預約公平性方向，通過增加配置變遷信息和子流程模塊兩種方案，對原有Petri 模型的行為關系進行了優化，有效地提高了預約系統的業務效率，增強了系統對于練車高峰時期的處理能力，能夠有效解決用戶約車困難的問題并增加了用戶自主預約的方式。通過仿真模型表明了優化模型的可行性，是有界、安全并且無死鎖的，但實際的實施階段可能會與流程模型產生差異，今后將通過結合過程挖掘等方面的知識進行進一步的分析。