基于著色時(shí)間Petri網(wǎng)的航班保障服務(wù)建模方法

邢志偉, 魏志強(qiáng), 羅 謙, 文 濤, 叢 婉, 夏 歡

(1. 中國民航大學(xué)電子信息與自動(dòng)化學(xué)院, 天津 300300;2. 中國民用航空局第二研究所, 四川 成都 610041)

0 引 言

隨著民航運(yùn)輸業(yè)的高速發(fā)展,截止2016年旅客吞吐量達(dá)千萬級的大型機(jī)場已有28個(gè)。這類機(jī)場的快速擴(kuò)張因保障服務(wù)粗放式管理導(dǎo)致其運(yùn)行效率日趨低下。而機(jī)場運(yùn)行尤以地面服務(wù)保障流程為核心展開,因此開展機(jī)坪保障服務(wù)流程建模、評估和優(yōu)化研究有望求解上述難題。

文獻(xiàn)[1]利用Service model工具實(shí)現(xiàn)平臺(tái)車的業(yè)務(wù)流程仿真,文獻(xiàn)[2]對機(jī)坪擺渡車調(diào)度過程進(jìn)行了簡化仿真,二者僅就單類保障服務(wù)展開研究。因此,文獻(xiàn)[3-12]分別基于數(shù)學(xué)模型和快速連續(xù)啟發(fā)式方法、基于遺傳算法、多目標(biāo)遺傳算法、粒子群算法、啟發(fā)式遺傳算法、快速啟發(fā)式算法、帶有混合編碼的遺傳算法、線性整數(shù)規(guī)劃方法以及簡單時(shí)間網(wǎng)絡(luò)與Agent結(jié)合方法探討了機(jī)坪多類保障服務(wù)資源調(diào)度優(yōu)化機(jī)制,但仍缺乏對地面服務(wù)保障的整體刻畫。據(jù)此,文獻(xiàn)[13]圍繞航班貨郵行李和旅客服務(wù)等核心流程建立了航線運(yùn)行模式的仿真模型;文獻(xiàn)[14]利用線性規(guī)劃數(shù)學(xué)模型研究了航班過站的部分服務(wù)過程,如上下旅客、加油、上下輪擋等；文獻(xiàn)[15]利用改進(jìn)多Agent研究了航班地面保障服務(wù)資源調(diào)度；文獻(xiàn)[16]利用面向Agent方法研究過站航班保障服務(wù)；文獻(xiàn)[17]利用Petri網(wǎng)簡要刻畫了過站航班的保障服務(wù)過程；文獻(xiàn)[18]利用項(xiàng)目評估和評審技術(shù)以及關(guān)鍵路徑方法提升了航班過站過程的效率；文獻(xiàn)[19]利用離散系統(tǒng)仿真方法研究了航班保障服務(wù),但上述研究并未提出一個(gè)描述整體保障服務(wù)的精準(zhǔn)模型；文獻(xiàn)[20]建立了基于Petri網(wǎng)的機(jī)坪保障指揮調(diào)度模型,但未引入保障資源和時(shí)間要素,導(dǎo)致保障服務(wù)流程的定量分析缺少基礎(chǔ)支撐。

本文根據(jù)大型樞紐機(jī)場實(shí)際航班地面保障流程,基于著色時(shí)間Petri網(wǎng)(colored time Petri net, CTPN)理論,研究航班地面保障服務(wù)全過程定量描述模型以及基于蒙特卡羅方法的保障時(shí)間預(yù)測估計(jì)算法,并利用實(shí)際數(shù)據(jù)對模型有效性進(jìn)行驗(yàn)證。

1 基于CTPN-SSM的保障服務(wù)模型描述

1.1 保障服務(wù)流程

過站航班保障流程主要是指從上輪擋到撤輪擋時(shí)間段內(nèi)的一系列保障作業(yè)活動(dòng)集合。本文主要以B737系列和A320系列等型號的航空器為研究對象,其保障流程大致可抽象為圖1所示。航空器機(jī)坪保障作業(yè)活動(dòng)主要包括以下部分:上輪檔、廊橋或客梯車靠接等19個(gè)標(biāo)準(zhǔn)作業(yè)節(jié)點(diǎn)。上述作業(yè)具有一定的先后次序和邏輯次序,共同構(gòu)成了航班保障服務(wù)作業(yè)流程。

圖1 航班保障服務(wù)流程Fig.1 Flight support service flow

1.2 著色時(shí)間Petri網(wǎng)

PETRI博士提出了一種離散建模工具Petri網(wǎng)[21],但由于缺乏對時(shí)間和資源種類刻畫元素(時(shí)間和顏色標(biāo)記),不能滿足建模要求。針對此，本文利用以著色Petri網(wǎng)和時(shí)間Petri網(wǎng)為基礎(chǔ)的改進(jìn)Petri網(wǎng)模型描述保障服務(wù)過程。

定義1[21]著色時(shí)間Petri網(wǎng)可表示為:CTPN=(P,T,Pre,Post,C,W,δ,M),其中,P={p1,p2,p3,…,pn}為有限庫所集合,T={t1,t2,t3,…,tn}為有限變遷集合,且P∩T≠?,P∪T≠?,Pre是前向關(guān)聯(lián)矩陣,Post是后向關(guān)聯(lián)矩陣,C是庫所的著色色彩集合,具體地,C(pi)={c1,c2,c3,…,cn},其中,i=1,2,3,…,n;δ={δ1,δ2,δ3,…,δn}是所有變遷的時(shí)延集合;W:P×T∪T×P→L(C),M:P→L(C),其中,L(C)=a1c1+a2c2+…+ancn為定義在顏色集上的整數(shù)線性函數(shù);在圖形上,庫所用圓圈表示,變遷用矩形表示,庫所與變遷之間的關(guān)系用有向弧表示。

1.3 保障服務(wù)的CTPN描述

保障服務(wù)過程通常包括保障作業(yè)、保障作業(yè)狀態(tài)、保障資源(非消耗性資源、消耗性資源)等類型;本文把保障服務(wù)過程看作Petri網(wǎng)系統(tǒng),并用相關(guān)基本元素對該過程進(jìn)行描述。

定義2保障作業(yè)過程描述。T={t1,t2,t3,…,tn},其中，tn表示為各個(gè)保障作業(yè)過程；n為保障作業(yè)的數(shù)量。δ:T→R+,表示保障作業(yè)所用時(shí)間的時(shí)延變遷。保障作業(yè)變遷時(shí)間用δ表示,δ={δ1,δ2,δ3,…,δn},其中,δn表示保障作業(yè)的時(shí)延,δn=[tnstart,tnend],Tδ n=tnend-tnstart,Tδ n為作業(yè)時(shí)間;tnend為tn保障作業(yè)結(jié)束時(shí)間;tnstart為tn保障作業(yè)開始時(shí)間。

定義3保障作業(yè)的邏輯關(guān)系描述R?T×T。?t∈T,若ti∈*ps且tj∈ps*,則ti和tj為串行關(guān)系。?t∈T且pi,pj∈ps,若pi∈*ti(ti*)、pj∈*tj(tj*)且pi∈t*(*t)、pj∈t*(*t),ti和tj為并行關(guān)系。

例如，t2是加航油,t3是垃圾車作業(yè),t4是行李貨郵作業(yè),三者關(guān)系如圖2所示,即并行關(guān)系。

圖2 并聯(lián)作業(yè)關(guān)系Fig.2 Parallel operating relationship

定義4保障服務(wù)狀態(tài)描述為P={Ps,Puc,Pc}。其中,Ps={ps}={p1,p2,p3,…,pn}表示作業(yè)任務(wù)狀態(tài)庫所集合,其中,{p1,p2,p3,…,pn}表示不同作業(yè)的狀態(tài)庫所;?ps∈Ps:*ps∩ps*=?表示前集與后集作業(yè)狀態(tài)庫所無交集,其中,*ps為前集保障作業(yè)狀態(tài)庫所,ps*為后集保障作業(yè)狀態(tài)庫所;作業(yè)狀態(tài)庫所的標(biāo)識(shí)和容量函數(shù)如式(1)所示:

(1)

式中,ms為保障作業(yè)狀態(tài)庫所的數(shù)量;cs為保障作業(yè)狀態(tài)標(biāo)記(保障作業(yè)狀態(tài)只能出現(xiàn)一種狀態(tài),所以只用cs表示)。

Puc={puc}表示非消耗性資源庫所集合,其中,puc表示為保障服務(wù)人員庫所和特種車輛庫所等,因而用式(2)表示非消耗性資源庫所的標(biāo)識(shí)、容量函數(shù):

(2)

Pc={pc}表示消耗性資源庫所集合,其中,pc表示航空器加航油等,因而用式(3)表示消耗性資源庫所的標(biāo)識(shí)和容量函數(shù):

(3)

式(2)和式(3)中,mci和kci,muci和kuci分別表示第i種資源在某一狀態(tài)下的資源數(shù)量和第i種資源容許的最大資源數(shù)量,并且都為非負(fù)整數(shù);cuci和cci分別表示第i種資源的標(biāo)記顏色;kc1+kc2+…+kch≠0,i=1,2,…,h,h=m時(shí)表示非消耗性資源庫所標(biāo)記的數(shù)量,h=n時(shí)表示消耗性資源庫所標(biāo)記的數(shù)量。

定義5保障服務(wù)狀態(tài)與保障作業(yè)關(guān)系描述。

根據(jù)Petri網(wǎng)定義,保障作業(yè)狀態(tài)Ps、保障作業(yè)資源(Pc,Puc)和保障作業(yè)之間的關(guān)系用弧來體現(xiàn)[21]。用式(4)、式(5)、式(6)分別表示表示保障作業(yè)狀態(tài)庫所、非消耗性資源庫所、消耗性資源庫所關(guān)聯(lián)弧的權(quán)函數(shù):

?f1∈Ps×T∪T×Ps:W(f1)=cs

(4)

?f2∈Puc×T∪T×Puc:W(f2)=

wuc1cuc1+wuc2cuc2+wuc3cuc3+…+wucncucn

(5)

?f3∈Pc×T∪T×Pc:W(f3)=

wc1cc1+wc2cc2+wc3cc3+…+wcmccm

(6)

式(4)～式(6)中,wuci(i=1,2,…,n)和wci(i=1,2,…,m)資源的權(quán)值,且都為非負(fù)整數(shù),(wc1+wc2+…+wch≠0),h代表m和n。其他參數(shù)同上述定義所述。

1.4 CTPN保障服務(wù)模型

綜上給出保障服務(wù)過程CTPN保障服務(wù)模型(CTPN-support service model,CTPN-SSM)。

CTPN-SSM=(P,T,Pre,Post,F,K,W,C,δ,R,M)

為航班保障服務(wù)Petri網(wǎng)模型,具備下列條件:

(1)T=Ts∪Tv,其中,Ts∩Tv=φ,Ts為作業(yè)變遷,Tv為虛擬作業(yè)變遷。

(2)Pre和Post分別為保障服務(wù)前向關(guān)聯(lián)矩陣和后向關(guān)聯(lián)矩陣。

(3)C={cs,cuc1,cuc2,…,cucn;cc1,cc2,…,ccm}為標(biāo)記顏色集合。cuci(i=1,2,…,n)表示為非消耗性資源保障作業(yè)的顏色標(biāo)記(n為標(biāo)記數(shù)量),如cuc1為保障人員的顏色標(biāo)記;cci(i=1,2,…,m)為消耗性資源保障作業(yè)資源的顏色標(biāo)記(m為標(biāo)記數(shù)量),cs為保障作業(yè)狀態(tài)標(biāo)記。

模型中其他參數(shù)如定義2～定義5所述。

2 蒙特卡羅的保障服務(wù)時(shí)間估算方法

CTPN-SSM中,保障作業(yè)過程描述對應(yīng)著蒙特卡羅方法中針對單個(gè)元件時(shí)間的求取及進(jìn)而求取其分布,保障作業(yè)邏輯關(guān)系對應(yīng)蒙特卡羅方法串并聯(lián)方法求取對應(yīng)關(guān)系的保障作業(yè)時(shí)間,通過對保障服務(wù)狀態(tài)的描述及保障服務(wù)和作業(yè)狀態(tài)的描述,把保障作業(yè)形成整體Petri網(wǎng),這對應(yīng)蒙特卡羅方法中如何求取整體保障服務(wù)時(shí)間。本節(jié)將保障服務(wù)Petri網(wǎng)系統(tǒng)中的各個(gè)作業(yè)變遷看作獨(dú)立元件,求出每個(gè)作業(yè)變遷產(chǎn)生的分布,再根據(jù)其分布產(chǎn)生相應(yīng)的隨機(jī)數(shù),最終依據(jù)保障服務(wù)Petri網(wǎng)系統(tǒng)的邏輯關(guān)系模擬出整體服務(wù)時(shí)間。根據(jù)上述,本節(jié)基于CTPN-SSM提出蒙特卡羅方法來估計(jì)保障服務(wù)時(shí)間(Monte Carlo-method support service time,MC-SST),用于支撐航班保障服務(wù)的定量分析和評價(jià)。MC-SST算法如圖3所示。

圖3 MC-SST估算方法流程Fig.3 Flow of estimating working time of MC-SST

步驟1設(shè)置仿真初始時(shí)刻,并確定仿真循環(huán)次數(shù)。

步驟2根據(jù)CTPN-SSM中各變遷表示的保障作業(yè)時(shí)間,求出各保障作業(yè)的時(shí)間分布。

步驟3根據(jù)保障服務(wù)時(shí)間分布產(chǎn)生相應(yīng)隨機(jī)數(shù),作為變遷的關(guān)聯(lián)時(shí)間。

步驟4根據(jù)CTPN-SSM中保障作業(yè)的邏輯關(guān)系,以變遷的關(guān)聯(lián)時(shí)間為步長進(jìn)行仿真,求得此次的保障服務(wù)時(shí)間。若ti(i=1,2,…,n)為n個(gè)串聯(lián)關(guān)系的保障作業(yè)變遷關(guān)聯(lián)時(shí)間,則仿真時(shí)間t=t1+t2+t3+…+tn;若ti(i=1,2,…,n)為n個(gè)并聯(lián)關(guān)系的保障作業(yè)變遷關(guān)聯(lián)時(shí)間,則仿真時(shí)間t=max(t1,t2,t3,…,tn)。

步驟5若仿真循環(huán)號小于設(shè)置的循環(huán)號循環(huán)次數(shù)加1,轉(zhuǎn)回步驟3,否則轉(zhuǎn)入步驟6。

步驟6由每次仿真得到的時(shí)間值為樣本,求出其均值,其均值對應(yīng)保障服務(wù)時(shí)間。

3 實(shí)例建模分析

本文對國內(nèi)某大型樞紐機(jī)場的航班保障服務(wù)流程建立CTPN-SSM模型。針對不同機(jī)型的航空器,其最小過站時(shí)間不同,但其由機(jī)場代理的國內(nèi)保障作業(yè)流程基本一致,如下:①上輪擋作業(yè);②廊橋或客梯車對接;③開艙門旅客下機(jī);④客艙清潔,配餐作業(yè);⑤航空器加航油作業(yè);⑥旅客登機(jī)作業(yè);⑦垃圾車作業(yè);⑧開貨艙門,卸行李貨郵,裝行李貨郵,關(guān)貨艙門;⑨關(guān)客艙門,廊橋或客梯車作業(yè);⑩撤輪擋,牽引車推出作業(yè);虛擬作業(yè)。相關(guān)作業(yè)數(shù)據(jù)如表1所示。根據(jù)民航局發(fā)布的民航航班正常性統(tǒng)計(jì)辦法 (2016),本文把航空器分為以下5類,如表2所示(為了簡便,表2所示的1、2、3、4、5航空器類別代替座位數(shù)不同的航空器)。建模過程主要考慮B737系列和A320系列等機(jī)型的保障服務(wù)過程。

表1 作業(yè)對應(yīng)變遷

表2 機(jī)型最少過站時(shí)間

根據(jù)上述可建立CTPN-SSM模型,如圖4所示。

圖4 CTPN-SSM模型Fig.4 Model of CTPN-SSM

實(shí)驗(yàn)數(shù)據(jù)來源于該機(jī)場地面服務(wù)保障生產(chǎn)系統(tǒng)并且該數(shù)據(jù)包含了與資源的關(guān)系。首先對數(shù)據(jù)進(jìn)行了預(yù)處理,然后針對表2所給的航空器機(jī)型分類,根據(jù)第3節(jié)保障服務(wù)時(shí)間估計(jì)方法,設(shè)置仿真次數(shù)為10 000,求出類別2和類別3的代表機(jī)型的保障服務(wù)時(shí)間如表3所示,代表機(jī)型主要有B737系列和A320系列等。圖5給出部分航班保障服務(wù)時(shí)間估計(jì)值與實(shí)際值對比和最小過站時(shí)間圖。根據(jù)表3和圖5可知,在最小過站時(shí)間的約束下,該估計(jì)方法為評估保障服務(wù)效率和提出資源改進(jìn)的相關(guān)意見提供了可能。

表3 部分航班保障服務(wù)估計(jì)時(shí)間與實(shí)際時(shí)間

圖5 部分航班保障服務(wù)估計(jì)時(shí)間與實(shí)際時(shí)間對比圖Fig.5 Partial flight support service estimated time versus actual time

根據(jù)上述實(shí)驗(yàn)結(jié)果運(yùn)用誤差分析法來對該模型進(jìn)行分析驗(yàn)證。

(7)

(8)

MAE由于離差被絕對值化,不會(huì)出現(xiàn)正負(fù)相抵消的情況。因而,MAE能更好地反映估計(jì)值誤差的實(shí)際情況。TIC總是介于0～1,數(shù)值越小則估計(jì)值和真實(shí)值之間的差異越小,估計(jì)精度越高。根據(jù)表2和式(7)和式(8)可以計(jì)算出考慮機(jī)型類別:類別2航空器的MAE=2.59 min,TIC=0.022 3;類別3航空器的MAE=3.88 min,TIC=0.034 7;不考慮機(jī)型類別:MAE=3.49 min,TIC=0.032 4;由表2和MAE、TIC可知,類別2航空器的相對誤差最大值為4.40 min,最小值為1.26 min；絕對誤差的最大值為0.074,最小值為0.022,1.26

4 結(jié) 論

為了提升機(jī)場保障服務(wù)效率,本文建立CTPN-SSM模型,并據(jù)此提出了一種MC-SST仿真方法。利用MC-SST算法估算某大型機(jī)場的保障服務(wù)時(shí)間,實(shí)測MC-SST估算時(shí)間與真實(shí)時(shí)間相比MAE<8.35 min,TIC<0.14,表明了CTPN-SSM模型的有效性，為機(jī)場地面保障服務(wù)流程的精細(xì)刻畫找到了一種可行的研究方法。

本文僅僅以單航班為研究對象。因此在后續(xù)研究中,將引入時(shí)間窗口內(nèi)多航班保障協(xié)同以及資源競爭等因素,建立動(dòng)態(tài)的多航班保障服務(wù)模型,進(jìn)一步提升保障服務(wù)模型的有效性和普適性。

參考文獻(xiàn)：

[1] 郝靜麒, 楊文東, 唐小衛(wèi). 樞紐機(jī)場停機(jī)坪平臺(tái)車資源分配仿真研究[J]. 武漢理工大學(xué)學(xué)報(bào), 2013, 35(12): 85-91.

HAO J Q, YANG W D, TANG X W. Simulation for platform truck resource allocation in hub airport apron[J]. Journal of Wuhan University of Technology, 2013, 35(12): 85-91.

[2] 楊文東, 陶婧婧, 賈玉平. 機(jī)坪擺渡車實(shí)時(shí)調(diào)度系統(tǒng)仿真[J]. 南京航空航天大學(xué)學(xué)報(bào), 2013, 45(6): 854-858.

YANG W D, TAO J J, JIA Y P. Simulation of real-time sche-duling of airport ferry bus[J]. Journal of Nanjing University of Aeronautics & Astronautics, 2013, 45(6): 854-858.

[3] GIOVANNI A, LORENZO C, LUIGI DE G, et al. Efficiency and robustness in a support platform for intelligent airport ground handling[J]. Journal of Intelligent Transportation Systems, 2014, 18(1): 121-130.

[4] 馮霞,任子云.基于遺傳算法的加油車和擺渡車協(xié)同調(diào)度研究[J].交通運(yùn)輸系統(tǒng)工程與信息, 2016, 16(2): 155-163.

FENG X, REN Z Y. Collaborative scheduling of fueling vehicle and ferry vehicle based on genetic algorithm[J]. Journal of Transportation Systems Engineering & Information Technology, 2016, 16(2): 155-163.

[5] KELLENBRINK C, HELBER S. Scheduling resource-constrained projects with a flexible project structure[J]. European Journal of Operational Research, 2015, 246(2): 379-391.

[6] CHEUNG A, IP W H, LU D, et al. An aircraft service scheduling model using genetic algorithms[J]. Journal of Manufacturing Technology Management(S1741-038X),2004,16(1):109-119.

[7] ZHAO G H, DU Y P. Research on airport apron service based on particle swarm optimization[J]. Management Science and Engineering, 2013, 20(4): 484-488.

[8] KUHN K, LOTH S. Airport service vehicle scheduling[J]. Air Traffic Control Quarterly, 2010, 18(1): 63-83.

[9] ANDREATTA G, GIOVANNI L D, MONACI M. A fast heuristic for airport ground-service equipment-and-staff allocation[J]. Procedia- Social and Behavioral Sciences, 2014, 108: 26-36.

[10] IP W H, WANG D, CHO V. Aircraft ground service scheduling problems and their genetic algorithm with hybrid assignment and sequence encoding scheme[J]. IEEE Systems Journal, 2013, 7(4): 649-657.

[11] TANG F, LIU S. Research of aircraft ground service scheduling problems[C]∥Proc.of the Chinese Control and Decision Conference, 2016: 689-694.

[12] LEEUWEN P V, WITTEVEEN C. Temporal decoupling and determining resource needs of autonomous agents in the airport turnaround process[C]∥Proc.of the IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology, 2009: 185-192.

[13] WU C L, CAVES R E. Modeling of aircraft rotation in a multiple airport environment[J]. Transportation Research Part E Logistics & Transportation Review(S1366-5545),2002,38(3):265-277.

[14] AL-BAZI A, GOK S, OZTURK C, et al. Developing a mathematical model for scheduling of turnaround operations (low cost airline as a case study)[C]∥Proc.of the International Aviation Management Conference, 2016：1-9.

[15] ANSOLA P G, HIGUERA A G, OTAMENDI F J, et al. Agent-based distributed control for improving complex resource scheduling: application to airport ground handling operations[J]. IEEE Systems Journal, 2014, 8(4): 1145-1157.

[16] MILLER T, LU B, STERLING L, et al. Requirements elicitation and specification using the agent paradigm: the case study of an aircraft turnaround simulator[J]. IEEE Trans.on Software Engineering, 2014, 40(10): 1007-1024.

[17] VIDOSAVLJEVIC A,TOSIC V. Modeling of turnaround process using Petri nets[C]∥Proc.of the World Conference of Air Transport Research Society, 2010：1-13.

[18] MAKHLOOF M A A, WAHEED M E, BADAWI E R, et al. Real-time aircraft turnaround operations manager[J]. Production Planning & Control, 2014, 25(1): 21-25.

[19] MUJICA M, BOCK N D, BOOSTEN G, et al. Simulation-based turnaround evaluation for Lelystad airport[C]∥Proc.of the Air Transport Research Society World Conference,2015：1-15.

[20] 朱新平, 唐志星, 夏正洪. 基于Petri網(wǎng)的航班機(jī)坪保障指揮調(diào)度建模[J]. 火力與指揮控制, 2015，40(12): 48-52.

ZHU X P, TANG Z X, XIA Z H. Petri net- based modeling of command and dispatch for flight apron service[J]. Fire Control & Command Control, 2015，40(12): 48-52.

[21] 湯新民, 朱新平. Petri網(wǎng)原理及其在民航交通運(yùn)輸工程中的應(yīng)用[M]. 北京: 中國民航出版社, 2014.

TANG X M, ZHU X P. Petri Net theory and its application civil aviation transportation engineering[M]. Beijing: China Civil Aviation Press, 2014.