基于Petri網(wǎng)的停車場預(yù)約停車流程優(yōu)化

李 冉

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

科技的發(fā)展給人們帶來了生活的便利，人們的出行變得更加方便和舒適.與此同時，也產(chǎn)生了新的問題——停車難.中國地大物博，人口眾多，發(fā)展日新月異，但基建設(shè)施的完善需要時間，而購買汽車的人數(shù)有增無減，越來越多的人選擇開車出行，造成了市區(qū)交通擁堵，高峰時期，熱門商圈停車位“一位難求”.于是有的停車場引入了智慧車位，無需保安，自動抬桿停車場，在停車位上安裝智能感應(yīng)器，監(jiān)控車位余量.但對于停車難的問題還是沒有得到很好地解決.在擁擠的市區(qū)中，路邊停車位本就不寬裕，遇到一些司機隨意停放時，交通擁堵更加嚴重，有時不得不出動交警的力量，對于亂停車的車輛進行貼條處罰.但因為交警力量有限，還有別的任務(wù)，這種監(jiān)管方式不能有大范圍的效果.Petri網(wǎng)是具有批處理功能的系統(tǒng)建模工具，能應(yīng)用于各種實際系統(tǒng)中進行系統(tǒng)分析.文獻[1]主要介紹了工作流管理作為Petri 網(wǎng)的應(yīng)用領(lǐng)域，介紹了有關(guān)工作流驗證的最新結(jié)果，將其用于實際場景.文獻[2]從行為輪廓的角度出發(fā)，對Petri網(wǎng)的多方面性能進行了分析，為優(yōu)化業(yè)務(wù)流程模型的性能提供了有效的方法.文獻[3]提出了基于隊列邏輯的 Petri 網(wǎng)業(yè)務(wù)流程，利用Petri網(wǎng)對車輛進出車庫的流程進行了建模與分析.文獻[4]引入了邏輯時延Petri網(wǎng)，來描述協(xié)同系統(tǒng)中的批處理和不確定性問題.對停車預(yù)訂系統(tǒng)進行了建模和分析.文獻[5]利用Petri網(wǎng)對超市車庫出入口同時出庫的問題進行了建模，通過增加控制結(jié)構(gòu)，進行優(yōu)化.文獻[6]提出了一種通過添加抑制弧對工作流網(wǎng)進行優(yōu)化的算法思想.在對于較為復(fù)雜的模型中，可以利用此算法對可達狀態(tài)的數(shù)目進行壓縮，從而簡化模型.

1 基本概念

定義1[1](流程模型)設(shè)一個六元組PM=(A，G，F(xiàn)，s,e,t)是一個流程模型：

1)A為一組有限非空活動集；

2)G為一組有限網(wǎng)關(guān)集；

3)A∩G=?并且N=A∪G為結(jié)點集；

4)s∈A為開始活動；

5)e∈A為終止活動；

6)F?(N{e}×N{e}為流關(guān)系，從而(N,F∪{(e,s)}為一個強連通圖；

7)t:G→{and,xor,or}連接每一個網(wǎng)關(guān)類型；

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

1)變遷t∈T具有發(fā)生權(quán)，當且僅當?P∈t:M(p)≥1,對，記作M[t>;

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

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

神經(jīng)系統(tǒng) 人體的神經(jīng)系統(tǒng)包括大腦、脊髓和遍布全身的神經(jīng)。要是沒有了神經(jīng)系統(tǒng)，我們就看不見、聽不到、聞不到、食而無味，也自然感覺不到疼。神經(jīng)系統(tǒng)由不計其數(shù)的細胞構(gòu)成，這些細胞被稱為“神經(jīng)元”。每個神經(jīng)元都含有樹突和軸突—— 樹突相當于一個傳感器，而軸突則連通著脊髓。

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

2)若t1?t2且t1?/t2，則稱t1和t2為嚴格逆序關(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；

以上幾種關(guān)系構(gòu)成網(wǎng)的行為輪廓，記為BP={→,→-1,+,‖}

定義4[1](可達性)已知Petri網(wǎng)PN=(P,T;F,M)，如果存在t∈T，使M[t>M′，則稱M′為從直接可達的.如果存在變遷序列t1,t2,…,tk和標識序列M1,M2,…,Mk使得M[t1>M1[t2>M2…Mk-1[tk>Mk則稱Mk為從M可達的.從M可達的一切標識集合記為R(M).

2 預(yù)約停車流程建模

現(xiàn)階段，國內(nèi)停車場在高峰時段停車困難的問題十分突出，部分地區(qū)引入了停車預(yù)約系統(tǒng).依據(jù)某預(yù)約停車軟件，利用Petri網(wǎng)建立了模型如圖1、表1所示(以下簡稱原模型).

表1 圖1中變遷符號的含義Table 1 The meaning of the change symbol in Figure 1

圖1 原始模型圖Figure 1 The original model diagram

預(yù)約停車系統(tǒng)原始模型流程主要分為四大模塊：第一部分賬戶登錄；第二部分預(yù)約停車；第三部分入場停車；第四部分出場.第一部分賬戶登錄流程如下：用戶登錄停車預(yù)約系統(tǒng)t1發(fā)生，進入停車預(yù)約系統(tǒng)，t2和t3是排他關(guān)系，記做t2+t3，根據(jù)用戶是否有賬號進入不同的流程.用戶有賬號發(fā)生t2，輸入密碼發(fā)生t6，t2和t6是嚴格序關(guān)系，記作t2→t6；用戶無賬號發(fā)生t3，此過程t3，t4和t5是嚴格序關(guān)系，記作t3→t4→t5，用戶注冊賬號t4發(fā)生，用戶設(shè)置密碼，t5發(fā)生.賬戶登錄成功，t7發(fā)生.第二部分預(yù)約停車流程：t7和t8為嚴格序關(guān)系，用戶賬號登錄成功后可以選擇停車預(yù)約，t8發(fā)生.預(yù)約停車首先需要選擇目的地，t9發(fā)生，t9發(fā)生后會出現(xiàn)一個排他序關(guān)系t10和t11，根據(jù)用戶所選地址查看是否有同名的地區(qū)，進行篩選.篩選后，用戶查看停車場信息，發(fā)生t13，t13和t14為嚴格序關(guān)系，用戶查看多選地區(qū)的停車位信息，發(fā)生t14，t14發(fā)生后產(chǎn)生一個排他序關(guān)系，根據(jù)用戶是否滿意該停車車場選擇發(fā)生t15或t16，如果不滿意該停車場，發(fā)生t15，用戶可以重新進行停車場選擇發(fā)生t12，滿意該停車場，發(fā)生t16；t16，t17和t18為排他序，用戶選擇預(yù)約時段，發(fā)生t17，預(yù)約成功發(fā)生t18.第三部分入場停車，用戶超時未入場，發(fā)生t19，如果用戶按時入場，t20發(fā)生，在t21車牌識別后，進行t22查詢流程，根據(jù)是否預(yù)約，選擇發(fā)生t23或t27，如果未預(yù)約，t23發(fā)生，t24和t28為排他序，記作t24+t28，若該停車場無空余車位發(fā)生t24，t24,t25和t26為嚴格序；若該停車場有空余車位發(fā)生t28；若查詢后已預(yù)約，則發(fā)生t27；t29，t30和t31為嚴格序，車輛入場發(fā)生t29后，尋找空閑車位，發(fā)生t30，停車成功發(fā)生t31.第四部分出場：用戶停車結(jié)束，準備離開停車場，發(fā)生t32；t33，t34和t35為嚴格序，經(jīng)過識別車牌，計算停車時長，繳費幾個流程，t33，t34和t35依次發(fā)生，車輛離場成功，發(fā)生t36，流程結(jié)束.

3 模型優(yōu)化

根據(jù)以上預(yù)約停車流程，發(fā)現(xiàn)現(xiàn)有停車場的預(yù)約停車流程主要包括用戶提前預(yù)約個人目的地的某停車場，并在規(guī)定時間內(nèi)到達，入場停車成功.這種預(yù)約停車的方式給用戶出行停車帶來了便捷，但是以此來緩解停車困難的問題，效果不大.本文針對以上預(yù)約停車模式，發(fā)現(xiàn)了如下問題：

1)預(yù)約時，用戶只能查詢到實時的空余車位.

2)只能選擇預(yù)約某停車場，不能預(yù)約該停車場的某個具體車位.例如對于商場來說，停車場有多個入口可以進入商場，不同的入口進入商場的位置不同，如果某顧客想進入商場某1號門，最后車停在靠近5號門的位置，會給用戶出行帶來不便.

3)對于現(xiàn)有停車場來說，如果停車場車位已滿，該車輛就不能進入，只能離場.

4)現(xiàn)有預(yù)約停車場，在出場時，還需要手動掃碼或者現(xiàn)金繳費.浪費出場時間.容易在車庫出口造成排隊擁堵.

5)對于現(xiàn)有停車場入場識別系統(tǒng)，只是簡單識別車牌號，對于套牌車輛，容易出現(xiàn)不必要的麻煩.

針對以上問題基于Petri網(wǎng)提出了以下模型優(yōu)化：

針對問題1)，提出在車主預(yù)約車位時，不只是查詢該停車場的實時空余車位，車主可以設(shè)定自己的停車時間段，查詢未來時間段內(nèi)停車場的空余車位.在模型中預(yù)約停車部分，增加了選擇時間的流程，在t11預(yù)約發(fā)生后，會產(chǎn)生一個交叉序關(guān)系，t12和t13，記作t12∥t13，用戶需要選擇目的地和時間后再進行預(yù)約.而在用戶預(yù)約時，發(fā)現(xiàn)某時段該停車場沒有空余車位，用戶可以通過查詢目的地周邊其他停車場的空余車位，而更改停車目的地，這樣可以大大緩解一些熱門商圈在高峰時期的停車壓力.用戶預(yù)約發(fā)現(xiàn)無車位發(fā)生t15，此時顯示預(yù)約失敗，用戶可以選擇查看周邊停車場的空余車位，取消預(yù)約或繼續(xù)等待，其中查看地圖t19，取消預(yù)約t18和繼續(xù)等待t17三個變遷為排他序.通過多車輛多用戶，設(shè)定預(yù)約停車時長的這種預(yù)約模式，可以有效提高停車場中多個停車位的利用率，同時用戶和停車場系統(tǒng)可以實時調(diào)控自己的出行需求和停車位的安排.見圖2、表2.

圖2 優(yōu)化模型圖Figure 2 Optimization model diagram

表2 圖2中變遷符號的含義Table 2 Meaning of the change symbols in Figure 2

針對問題2)在用戶選擇停車地址時，已經(jīng)明確知道自己需要選擇該停車場哪個位置進出時，可以通過預(yù)約具體的車位，進而簡化自己的停車流程.在圖2中，用戶在預(yù)約車位，輸入車牌發(fā)生t27后，可以選擇是否提前預(yù)選車位，其中t28預(yù)選車位和t31不預(yù)選車位為排他序，記作t28+t31.同時通過接入地圖導航，直接導航至預(yù)約的停車位，減少在停車場這種較為復(fù)雜的路段尋找車位的時間，同時也可以減少停車場車禍等事故的發(fā)生.因為較多的停車場事故主要是由于駕駛員在開車時需要分心尋找車位時造成.在圖2中，用戶進入停車場后，查詢到達停車位的最短路徑，變遷t54發(fā)生，用戶通過車位引導，發(fā)生變遷t55，最后到達車位，發(fā)生t56，停車成功，發(fā)生t57，其中t54，t55，t56和t57為嚴格序關(guān)系.

針對問題3)通過新增停車場排隊等候區(qū)，可以提高車主停車的便利性.同時通過嵌入地圖，車主在目的地停車場沒有找到空閑車位時，可以通過導航選擇該目的地內(nèi)1 km以內(nèi)其他有空余車位的停車場，可以提高一些熱門商圈不同停車場的停車效率和利用率.在圖2中，對于沒有預(yù)約的車輛在入場后，發(fā)現(xiàn)沒有空余車位，發(fā)生變遷t42，車輛進入臨時等待區(qū)，發(fā)生t46；t50和t52為排他序，記作t50+t52，根據(jù)等待人數(shù)的多少，可以選擇繼續(xù)等待或離場.

針對問題4)用戶在預(yù)約時就可以選擇綁定支付寶或者微信等，開通免密支付，在出場時，可以減少在停車場出口的擁堵和等待時間.圖2中，用戶在注冊賬戶時，發(fā)生變遷t4，設(shè)置密碼發(fā)生t5，用戶綁定支付寶，發(fā)生t6，圖中t8和t9為排他序，記作t8+t9，用戶可以選擇開通免密支付，發(fā)生變遷t8或不開通，則發(fā)生t9.

針對問題5)，在車輛進行入場時，增加圖像采集變遷t36，車輛檢測變遷t37，車牌識別變遷t38，其中t36，t37和t38為交叉序.通過增加以上流程可以有效減少套牌車輛的出行，以及停車場入口識別的準確度，提高車輛入場和出場效率.

4 仿真實驗

為了檢驗優(yōu)化模型的正確性和可行性，本文采用了Petri網(wǎng)分析軟件PIPE進行模擬運行，優(yōu)化后的流程在PIPE中通過 State Space Analysis操作對模型進行狀態(tài)空間分析，以此驗證優(yōu)化后該模型是否滿足有界性、安全性以及有無死鎖的特征.

經(jīng)過PIPE仿真后，驗證優(yōu)化后的結(jié)構(gòu)能夠滿足有界性、安全性、無死鎖.運行結(jié)果如圖3、4所示.

圖3 PIPE模擬圖Figure 3 The PIPE simulation diagram

圖4 PIPE模擬結(jié)果Figure 4 PIPE simulation results

5 結(jié) 語

本文主要在Petri網(wǎng)理論的基礎(chǔ)上對商場停車系統(tǒng)進行了針對單用戶的過程優(yōu)化，通過完善用戶預(yù)約流程，增強用戶停車后對其行為的監(jiān)控，豐富流程結(jié)構(gòu)，提高了預(yù)約停車系統(tǒng)的實用性和用戶體驗.本文僅針對單對象的流程模型進行優(yōu)化，缺乏對多對象流程的應(yīng)用性.在接下來的研究中，會將單對象的流程模型進階發(fā)展成為多對象的模型優(yōu)化研究，引入更多的流程知識和過程管理.通過利用候補過程模型以及搜索最大項集的算法對尋找車位以及停車場管理車位進行進一步的流程優(yōu)化.