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

邢志偉, 魏志強, 羅 謙, 文 濤, 叢 婉, 夏 歡

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

0 引 言

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

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

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

1 基于CTPN-SSM的保障服務模型描述

1.1 保障服務流程

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

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

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

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

定義1[21]著色時間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是前向關聯(lián)矩陣,Post是后向關聯(lián)矩陣,C是庫所的著色色彩集合,具體地,C(pi)={c1,c2,c3,…,cn},其中,i=1,2,3,…,n;δ={δ1,δ2,δ3,…,δn}是所有變遷的時延集合;W:P×T∪T×P→L(C),M:P→L(C),其中,L(C)=a1c1+a2c2+…+ancn為定義在顏色集上的整數(shù)線性函數(shù);在圖形上,庫所用圓圈表示,變遷用矩形表示,庫所與變遷之間的關系用有向弧表示。

1.3 保障服務的CTPN描述

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

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

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

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

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

定義4保障服務狀態(tài)描述為P={Ps,Puc,Pc}。其中,Ps={ps}={p1,p2,p3,…,pn}表示作業(yè)任務狀態(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)庫所的標識和容量函數(shù)如式(1)所示:

(1)

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

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

(2)

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

(3)

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

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

根據(jù)Petri網(wǎng)定義,保障作業(yè)狀態(tài)Ps、保障作業(yè)資源(Pc,Puc)和保障作業(yè)之間的關系用弧來體現(xiàn)[21]。用式(4)、式(5)、式(6)分別表示表示保障作業(yè)狀態(tài)庫所、非消耗性資源庫所、消耗性資源庫所關聯(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)值,且都為非負整數(shù),(wc1+wc2+…+wch≠0),h代表m和n。其他參數(shù)同上述定義所述。

1.4 CTPN保障服務模型

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

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

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

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

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

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

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

2 蒙特卡羅的保障服務時間估算方法

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

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

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

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

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

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

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

步驟6由每次仿真得到的時間值為樣本,求出其均值,其均值對應保障服務時間。

3 實例建模分析

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

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

表2 機型最少過站時間

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

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

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

表3 部分航班保障服務估計時間與實際時間

圖5 部分航班保障服務估計時間與實際時間對比圖Fig.5 Partial flight support service estimated time versus actual time

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

(7)

(8)

MAE由于離差被絕對值化,不會出現(xiàn)正負相抵消的情況。因而,MAE能更好地反映估計值誤差的實際情況。TIC總是介于0～1,數(shù)值越小則估計值和真實值之間的差異越小,估計精度越高。根據(jù)表2和式(7)和式(8)可以計算出考慮機型類別:類別2航空器的MAE=2.59 min,TIC=0.022 3;類別3航空器的MAE=3.88 min,TIC=0.034 7;不考慮機型類別: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é) 論

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

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

參考文獻：

[1] 郝靜麒, 楊文東, 唐小衛(wèi). 樞紐機場停機坪平臺車資源分配仿真研究[J]. 武漢理工大學學報, 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] 楊文東, 陶婧婧, 賈玉平. 機坪擺渡車實時調(diào)度系統(tǒng)仿真[J]. 南京航空航天大學學報, 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].交通運輸系統(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)的航班機坪保障指揮調(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)原理及其在民航交通運輸工程中的應用[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.