基于著色時間Petri網的航班保障服務建模方法

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

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

0 引 言

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

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

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

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

1.1 保障服務流程

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

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

1.2 著色時間Petri網

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

定義1[21]著色時間Petri網可表示為:CTPN=(P,T,Pre,Post,C,W,δ,M),其中,P={p1,p2,p3,…,pn}為有限庫所集合,T={t1,t2,t3,…,tn}為有限變遷集合,且P∩T≠?,P∪T≠?,Pre是前向關聯矩陣,Post是后向關聯矩陣,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為定義在顏色集上的整數線性函數;在圖形上,庫所用圓圈表示,變遷用矩形表示,庫所與變遷之間的關系用有向弧表示。

1.3 保障服務的CTPN描述

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

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

定義3保障作業的邏輯關系描述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是垃圾車作業,t4是行李貨郵作業,三者關系如圖2所示,即并行關系。

圖2 并聯作業關系Fig.2 Parallel operating relationship

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

(1)

式中,ms為保障作業狀態庫所的數量;cs為保障作業狀態標記(保障作業狀態只能出現一種狀態,所以只用cs表示)。

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

(2)

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

(3)

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

定義5保障服務狀態與保障作業關系描述。

根據Petri網定義,保障作業狀態Ps、保障作業資源(Pc,Puc)和保障作業之間的關系用弧來體現[21]。用式(4)、式(5)、式(6)分別表示表示保障作業狀態庫所、非消耗性資源庫所、消耗性資源庫所關聯弧的權函數:

?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)資源的權值,且都為非負整數,(wc1+wc2+…+wch≠0),h代表m和n。其他參數同上述定義所述。

1.4 CTPN保障服務模型

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

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

為航班保障服務Petri網模型,具備下列條件:

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

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

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

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

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

CTPN-SSM中,保障作業過程描述對應著蒙特卡羅方法中針對單個元件時間的求取及進而求取其分布,保障作業邏輯關系對應蒙特卡羅方法串并聯方法求取對應關系的保障作業時間,通過對保障服務狀態的描述及保障服務和作業狀態的描述,把保障作業形成整體Petri網,這對應蒙特卡羅方法中如何求取整體保障服務時間。本節將保障服務Petri網系統中的各個作業變遷看作獨立元件,求出每個作業變遷產生的分布,再根據其分布產生相應的隨機數,最終依據保障服務Petri網系統的邏輯關系模擬出整體服務時間。根據上述,本節基于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設置仿真初始時刻,并確定仿真循環次數。

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

步驟3根據保障服務時間分布產生相應隨機數,作為變遷的關聯時間。

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

步驟5若仿真循環號小于設置的循環號循環次數加1,轉回步驟3,否則轉入步驟6。

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

3 實例建模分析

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

表1 作業對應變遷

表2 機型最少過站時間

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

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

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

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

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

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

(7)

(8)

MAE由于離差被絕對值化,不會出現正負相抵消的情況。因而,MAE能更好地反映估計值誤差的實際情況。TIC總是介于0～1,數值越小則估計值和真實值之間的差異越小,估計精度越高。根據表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 結 論

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

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

參考文獻：

[1] 郝靜麒, 楊文東, 唐小衛. 樞紐機場停機坪平臺車資源分配仿真研究[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] 楊文東, 陶婧婧, 賈玉平. 機坪擺渡車實時調度系統仿真[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] 馮霞,任子云.基于遺傳算法的加油車和擺渡車協同調度研究[J].交通運輸系統工程與信息, 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網的航班機坪保障指揮調度建模[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網原理及其在民航交通運輸工程中的應用[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.