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

張亞平 賈國洋 程紹武

（哈爾濱工業(yè)大學(xué)交通科學(xué)與工程學(xué)院 哈爾濱 150090）

0 引 言

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

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

綜上，國內(nèi)外學(xué)者的研究均未涉及將Petri網(wǎng)理論應(yīng)用于航站樓旅客安檢流程模型及性能分析，針對此類問題，本文以某機場航站樓旅客安檢流程為研究對象，構(gòu)建基于Petri網(wǎng)的航站樓旅客安檢流程模型，并進行性能分析.

1 航站樓安檢流程分析

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

圖1 航站樓安檢流程

2 基于Petri網(wǎng)的航站樓安檢流程模型

2.1 基于Petri網(wǎng)的模型構(gòu)建前提條件

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

2.2 基于Petri網(wǎng)的航站樓安檢流程模型

根據(jù)安檢流程各個步驟以及上述前提條件，構(gòu)建基于Petri網(wǎng)的航站樓安檢流程模型，如圖2所示.

圖2 基于Petri網(wǎng)的航站樓安檢流程模型

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

2.3 模型正確性驗證

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

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

2.4 原始模型轉(zhuǎn)化為隨機Petri模型（SPN）

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

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

3 性能分析

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

性能分析過程及結(jié)果如下.

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

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

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

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

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

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

表1 安檢過程GSPN’模型可達標(biāo)識列表

利用安檢流程GSPN’模型的可達標(biāo)識列表數(shù)據(jù)建立可達標(biāo)識圖，見圖4.

圖4 安檢過程GSPN’模型的可達標(biāo)識圖

4）構(gòu)造與安檢流程GSPN’模型同構(gòu)的馬爾可夫鏈MC，建立轉(zhuǎn)移速率矩陣.

消失狀態(tài) 無.

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

圖5 與安檢過程GSPN’模型同構(gòu)的MC

5）對λ＝｛λ1，λTA，λTB，λTC，λ9，λ′｝賦值，建立狀態(tài)方程，求出每個可達標(biāo)識的穩(wěn)定概率，方程式如下.

解上述方程組，其結(jié)果見表2.

表2 安檢流程穩(wěn)定狀態(tài)時的概率分布

6）性能指標(biāo) 有穩(wěn)定狀態(tài)下的概率分布確定安檢過程中各個庫所的平均托肯數(shù)，見表3.

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

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

4 結(jié)束語

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

［1］朱新平，韓松臣，湯新民.A－SMGCS機場場面運行控制的Petri網(wǎng)建模［J］.武漢理工大學(xué)學(xué)報：交通科學(xué)與工程版，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］李耐毅.航站樓離港航班動態(tài)性仿真研究［J］.科技前沿，2012，6（2）：40－41.

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

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

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

［9］程紹武，張亞平，別一鳴.民用機場航站樓資源動態(tài)配置及調(diào)度智能化理論［M］.北京：電子工業(yè)出版社，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］文 軍.基于灰色馬爾可夫鏈模型的航空貨運量預(yù)測研究［J］.武漢理工大學(xué)學(xué)報：交通科學(xué)與工程版，2010，34（4）：695－698.