基于Petri網的航站樓安檢流程建模及性能分析＊

張亞平 賈國洋 程紹武

（哈爾濱工業大學交通科學與工程學院 哈爾濱 150090）

0 引 言

我國民航2013年的旅客運輸量已經突破3.5億人次，成為世界第二大航空運輸大國.航空運輸也時常受到突發性事件的影響，航班正點率也連年下降，航班安全正點［1］運營已成為社會關注的焦點.由于各方面原因，導致旅客在安檢等區域［2］的長時間滯留現象時有發生，這種現象極易引發群體性事件，也可能給民航運輸業帶來很大的負面影響.因此分析航站樓安檢流程及其性能對于減少安檢排隊長度、提高安檢系統服務效率具有建設性的意義.

目前，針對航站樓旅客服務流程研究較少，相關的基于Petri網的建模和性能分析的研究較多，但是應用到航站樓安檢流程的較少.在機場航站樓旅客服務流程方面，Takakuwa Soemon等［3］開發了一套用于國際旅客離港流程的模擬系統，并應用于對航站樓的旅客流的研究.顧廣輝和李耐毅等［4－5］應用Service Model仿真對國內機場通用的離港流程進行仿真模擬，并用于不同機場的評估并給出了相關流程的優化建議.在Petri網建模和性能分析方面，肖軍等［6］提出了擴展時延Petri網，給出了利用排隊論和隨機Petri網理論計算工作流模型時間性能指標的新方法.秦江濤［7］應用層次化著色Petri網方法和參數調用技術構建了制造系統的Petri網模型，并應用仿真技術進行了性能分析.王晶等［8］結合跨組織工作流建模與對象網之間的相似性，提出了一種基于公共視圖和對象Petri網的跨組織工作流建模方法.

綜上，國內外學者的研究均未涉及將Petri網理論應用于航站樓旅客安檢流程模型及性能分析，針對此類問題，本文以某機場航站樓旅客安檢流程為研究對象，構建基于Petri網的航站樓旅客安檢流程模型，并進行性能分析.

1 航站樓安檢流程分析

安檢即為安全檢查，是為了防止旅客攜帶可能危及飛機安全的物品登機而進行的一項檢查活動.以國內某4E級民用機場航站樓安檢流程為例，其安全檢查包括旅客安檢和隨身物品及行李安檢兩部分.旅客到達安檢區域時，首先將證件交給檢驗人員查驗，然后旅客通過安檢通道的同時隨身行李和物品通過安檢傳送帶，伺候旅客必須再次接受手持掃描儀的仔細檢查［9］.如果行李掃描時發出警報，將對行李進行開箱檢查.此過程中極易產生瓶頸，導致旅客接受安檢服務排隊過長，等待時間過久，安檢系統效率降低等惡性狀況.安檢流程如圖1所示.

圖1 航站樓安檢流程

2 基于Petri網的航站樓安檢流程模型

2.1 基于Petri網的模型構建前提條件

給出安檢流程模型前提條件以便對安檢流程的分析更加精確：（1）旅客已辦理完畢值機手續，等待安全檢查；（2）旅客隨身攜帶無需托運的小件行李；（3）小件行李中裝有機場規定違禁物品；（4）旅客身上有可疑物品；（5）安全監察人員的工作效率是一樣的；（6）安全檢查儀器正常工作，無任何故障；（7）旅客按時到達航站樓，安檢后直接登機［10］.

2.2 基于Petri網的航站樓安檢流程模型

根據安檢流程各個步驟以及上述前提條件，構建基于Petri網的航站樓安檢流程模型，如圖2所示.

圖2 基于Petri網的航站樓安檢流程模型

圖中：t1為查驗旅客身份證等證件；t2為隨身行李和物品；t3為安檢系統報警；t4為工作人員檢驗有問題的物品；t5為工作人員取出有問題的物品，留下其他物品；t6為旅客進入安檢門；t7為對旅客進行人工安檢；t8為工作人員取出可疑物品；t9為旅客收拾好隨身物品和行李.

2.3 模型正確性驗證

根據可靠性定義可對基于Petri網的航站樓安檢流程模型進行正確性驗證.可靠性定義如下.

可靠性定義［11］一個Petri網模型PN＝（P，T，F）是結構正確的，當且僅當：（1）對于每個從狀態i可達的狀態M，存在一個實施的順序，可以從狀態M到狀態o；（2）狀態o是從狀態i可達的唯一最終狀態，且結束時庫所o中至少有一個標記；（3）在（PN，i）沒有死變遷.有上述定義可知：（1）表示為從初始標識i開始，總能到達終止標識o；（2）表示當庫所o中存在一個托肯時，其他庫所應為空；（3）表示在初始標識下，工作流網中不存在死變遷.由以上定義可得出該工作流網是可靠的，即模型是正確的.

2.4 原始模型轉化為隨機Petri模型（SPN）

為便于后續的模型采用馬爾可夫理論進行性能分析，通常需保證模型中隨機時間服從一定的分布規律.在安檢流程模型中每個變遷的可實施狀態與實施狀態之間添加一個服從Molloy設定的指數分布函數，即?t∈T：Ft（x）＝1－e－λtx，其中實數λt＞0代表變遷t單位時間內的平均引發頻率.由此建立的安檢流程SPN模型同構于相應的連續時間馬爾科夫鏈（Markov chain，MC）進而保證得到的安檢流程SPN模型的可達狀態標識圖與一個MC的狀態空間［12］也同構.因此對安檢流程SPN定義如下.

安檢流程SPN定義 SPN＝（P，T；F，M0，λ）表示一個連續時間的隨機Petri網，其中N＝（P，T；F，M0）表示一個Petri網系統，而向量λ＝（λ1，λ2，...，λm）表示相應角標的變遷單位時間內平均引發頻率的一個集合.其中平均實施速率的倒數ζi＝1／λi為變遷ti的平均實施延遲時間或者稱為平均服務時間.

3 性能分析

模型的性能分析指采用合理的分析方法和分析技術對建立的系統模型的動態行為進行定性的評價和定量的計算，以便找出流程由于資源利用效率低，資源擁擠而出現的瓶頸.此處設定為資源數量受限制.資源數量受到限制時可能會出現旅客等待情況，這是因為對旅客安檢需要消耗時間.若消耗時間較長，安檢柜臺數量又較少，而安檢流程有多個環節且每個環節接受安檢服務的旅客比較多，此時到達旅客就需要排隊，直到前一位旅客接受服務完畢，安檢服務的資源變為可用狀態后才能對排隊中的旅客進行安全檢查.

性能分析過程及結果如下.

1）分析建立的安檢流程SPN模型，并進行簡化 安檢流程SPN模型如圖2所示，為簡化研究，用復合變遷tTA代替t4，t5，tTB代替t2，t3，tTC代替t6，t7，t8，替代后的安檢過程模型如圖3所示.

圖3 替代后的安檢流程SPN模型

2）將SPN模型的變遷分為瞬時變遷和時間變遷，瞬時變遷不需要延遲時間，時間變遷給定一個延遲時間，得出廣義隨機Petri網（GSPN）模型.

考慮到安檢流程SPN模型中不含有只表示邏輯意義的變遷，即不含瞬時變遷，因此只需對時間變遷給定延遲時間：時間變遷集Tt＝｛t1，tTA，tTB，tTB，t9｝，每個時間變遷定義一個引發速率λ＝｛λ1，λTA，λTB，λTC，λ9｝，由此轉化為安檢流程廣義隨機Petri網（簡稱GSPN）模型，如圖3所示.

在輸入庫所i和輸出庫所o之間添加一個時間變遷t′，假設t′的引發速率為λ′，得到具有連續過程的安檢流程GSPN’模型.

3）建立由上述過程得到的安檢流程GSPN’模型的可達標識圖，首先求出模型的可達標識，結果見表1.

表1 安檢過程GSPN’模型可達標識列表

利用安檢流程GSPN’模型的可達標識列表數據建立可達標識圖，見圖4.

圖4 安檢過程GSPN’模型的可達標識圖

4）構造與安檢流程GSPN’模型同構的馬爾可夫鏈MC，建立轉移速率矩陣.

消失狀態 無.

由于沒有消失狀態，因此無需對安檢流程GSPN’模型的狀態空間進行化簡.由此建立出與安檢流程GSPN’同構的馬爾可夫鏈MC，結果見圖5.

圖5 與安檢過程GSPN’模型同構的MC

5）對λ＝｛λ1，λTA，λTB，λTC，λ9，λ′｝賦值，建立狀態方程，求出每個可達標識的穩定概率，方程式如下.

解上述方程組，其結果見表2.

表2 安檢流程穩定狀態時的概率分布

6）性能指標 有穩定狀態下的概率分布確定安檢過程中各個庫所的平均托肯數，見表3.

表3 安檢流程各庫所的平均托肯數和利用率

由表3可見，輸入庫所i中存在的托肯數目比較大，此處易形成瓶頸，是由于旅客取出身上和行李物件并等待進入案件傳送帶的時間過長；輸出庫所o中存在的托肯數目也很大，易形成瓶頸，這是由于安檢的總服務流程耗時過久造成.根據穩定狀態下的概率分布，可確定各個變遷的利用率，結果見表3.從表中看出變遷t1的利用率為25.000%，是所有變遷中利用率最高的，分析認為是由旅客等待接受服務時間太久造成.因此，調整安檢口的數量和每個安檢口的功能分配，有助于消除安檢流程瓶頸，提高安檢流程性能和效率.

4 結束語

本文通過對基于Petri網的航站樓安檢流程模型和性能的研究，對導致安檢流程效率低原因進行了分析，分析表明安檢流程中相對其他環節，旅客在進入安檢門之前的效率較低，此環節占用安檢系統人力和物力資源時間較長.針對分析結果提出相應的優化方案，優化安檢系統的人力和物力，提高安檢流程的性能和效率.但是針對優化方案的效果和優劣，是下一步研究中需要重點解決的問題.

［1］朱新平，韓松臣，湯新民.A－SMGCS機場場面運行控制的Petri網建模［J］.武漢理工大學學報：交通科學與工程版，2011，35（5）：950－954.

［2］DIJK V N M，ERIK V D S.Check－in computation and optimization by simulation and IP incombination［J］.European Journal of Operational Research，2006，171：1152－1168.

［3］SOEMON T，TOMOKI O.Simulation analysis of international departure passenger flow in an airport terminal［C］∥ Proceedings of the 2003Winter Simulation Conference，2003：1627－163.

［4］顧廣輝，許 俐，夏薔薇.航站樓離港流程仿真研究［J］.科技信息，2011，33（2）：91－93.

［5］李耐毅.航站樓離港航班動態性仿真研究［J］.科技前沿，2012，6（2）：40－41.

［6］肖 軍，鄧海鴻，高允鋒，等.基于Petri網的工作流建模及時間性能分析［J］.吉林大學學報：信息科學版，2009，27（1）：104－112.

［7］秦江濤.基于Petri網仿真的制造系統性能分析研究［J］.工業工程與管理，2014，19（1）：8－15.

［8］王 晶，胡 昊，余 萍，等.結合公共視圖和對象Petri網的跨組織流程建模［J］.計算機科學與探索，2014，8（1）：18－27.

［9］程紹武，張亞平，別一鳴.民用機場航站樓資源動態配置及調度智能化理論［M］.北京：電子工業出版社，2015.

［10］JIANG Hong，DING Xiangqian，HOU Ruichun，et al.Modeling of hierarchical petri net－based workflow［C］∥Proc of the 2nd International Conference on Computing，Control and Industrial Engineering，2011：113－116.

［11］WVETHEEK H M，BASTEN T，AALST W M P V.Diagnosing work flow processing work flow［J］.The Computer Joumal，2001，44（4）：246－279.

［12］文 軍.基于灰色馬爾可夫鏈模型的航空貨運量預測研究［J］.武漢理工大學學報：交通科學與工程版，2010，34（4）：695－698.