基于Petri網(wǎng)的航班機(jī)坪保障指揮調(diào)度建模*

朱新平，唐志星，夏正洪

（中國(guó)民用航空飛行學(xué)院空中交通管理學(xué)院，四川廣漢618307）

基于Petri網(wǎng)的航班機(jī)坪保障指揮調(diào)度建模*

朱新平，唐志星，夏正洪

（中國(guó)民用航空飛行學(xué)院空中交通管理學(xué)院，四川廣漢618307）

為支持航班機(jī)坪保障指揮調(diào)度優(yōu)化，提出基于Petri網(wǎng)的機(jī)坪保障指揮調(diào)度建模方法。構(gòu)建包含服務(wù)線、模塊和任務(wù)的機(jī)坪保障作業(yè)協(xié)調(diào)關(guān)聯(lián)模型，實(shí)現(xiàn)保障過(guò)程的層次化分解；將保障作業(yè)任務(wù)分為單設(shè)備作業(yè)任務(wù)和多設(shè)備作業(yè)任務(wù)，給出其模塊化賦時(shí)Petri網(wǎng)模型構(gòu)造方法，并針對(duì)設(shè)備調(diào)派過(guò)程建模需要進(jìn)行擴(kuò)展；考慮作業(yè)任務(wù)之間的前置開(kāi)始關(guān)聯(lián)和前置結(jié)束關(guān)聯(lián)兩類關(guān)系，給出其對(duì)應(yīng)Petri網(wǎng)模型之間的合成方法，并提出基于協(xié)調(diào)關(guān)聯(lián)模型的保障作業(yè)指揮調(diào)度過(guò)程Petri網(wǎng)模型構(gòu)造算法。以某航班機(jī)坪保障指揮調(diào)度建模為例，驗(yàn)證所給建模方法的有效性和適用性。

機(jī)場(chǎng)，機(jī)坪保障，建模，Petri網(wǎng)

0 引言

機(jī)坪保障效率低下已成為大型機(jī)場(chǎng)航班延誤的重要原因之一［1］。為實(shí)現(xiàn)機(jī)坪保障指揮調(diào)度自動(dòng)化，需構(gòu)建對(duì)應(yīng)的信息關(guān)聯(lián)模型。航班機(jī)坪保障指揮調(diào)度過(guò)程由若干離散事件推動(dòng)（如航空器入位、客艙門(mén)開(kāi)啟等），屬于一類離散事件動(dòng)態(tài)系統(tǒng)，因而可采取Petri網(wǎng)建模［2］。以往有研究采用賦時(shí)Petri網(wǎng)建模機(jī)坪保障中加油作業(yè)［3］或采用著色Petri網(wǎng)建模整個(gè)機(jī)坪保障作業(yè)［4-5］。也有學(xué)者采用AOE（Activity On Edge）網(wǎng)絡(luò)［6-7］或簡(jiǎn)單時(shí)間網(wǎng)絡(luò)（Simple Temporal Network）［8］建模機(jī)位保障過(guò)程。但上述研究對(duì)機(jī)坪保障資源調(diào)度缺乏直觀描述。其他學(xué)者建立了機(jī)坪保障作業(yè)仿真模型［9-10］。此外，也有學(xué)者將機(jī)坪保障指揮調(diào)度視為多設(shè)備并行作業(yè)調(diào)度問(wèn)題建立相應(yīng)地優(yōu)化調(diào)度模型［11］?？偨Y(jié)起來(lái)，以往機(jī)坪保障指揮調(diào)度模型不足主要有：①對(duì)機(jī)坪保障指揮調(diào)度過(guò)程描述不直觀，不利于建模人員和指揮調(diào)度人員交互理解；②采用運(yùn)籌學(xué)方法建立的模型參數(shù)較多，求解計(jì)算較為復(fù)雜。

1 航班機(jī)坪保障過(guò)程

航班機(jī)坪保障涉及始發(fā)、過(guò)站和航后三類航班。以圖1所示過(guò)站航班機(jī)坪保障為例，飛機(jī)進(jìn)機(jī)位上輪擋后，調(diào)派保障設(shè)備至機(jī)位開(kāi)展進(jìn)港保障作業(yè)和離港保障作業(yè)，最后撤輪擋推出完成過(guò)站保障。始發(fā)航班僅涉及離港保障過(guò)程，且可能包括始發(fā)拖曳作業(yè)；航后航班僅涉及進(jìn)港保障過(guò)程，且可能包括航后拖曳作業(yè)。在機(jī)坪保障過(guò)程中，各作業(yè)任務(wù)均在離散時(shí)刻開(kāi)始或結(jié)束，且作業(yè)任務(wù)之間存在一定的作業(yè)時(shí)序約束。大型機(jī)場(chǎng)機(jī)坪空間大、保障持續(xù)時(shí)間長(zhǎng)，且保障設(shè)備分屬不同部門(mén)，通常采取“責(zé)任分區(qū)”方式進(jìn)行。機(jī)坪保障指揮調(diào)度需要跨部門(mén)協(xié)作，各部門(mén)調(diào)度人員多基于現(xiàn)場(chǎng)作業(yè)通報(bào)或手冊(cè)開(kāi)展調(diào)度，效率較低。

圖1 過(guò)站航班機(jī)坪保障指揮調(diào)度過(guò)程概觀

2 機(jī)坪保障協(xié)調(diào)關(guān)聯(lián)模型

將機(jī)坪保障作業(yè)分解成旅客服務(wù)線、貨郵服務(wù)線、飛機(jī)服務(wù)線，各服務(wù)線又分解成設(shè)備調(diào)派模塊和機(jī)位保障模塊，分別負(fù)責(zé)保障設(shè)備的機(jī)坪行駛路線規(guī)劃和作業(yè)調(diào)度。進(jìn)一步地，設(shè)備調(diào)派模塊和機(jī)位保障模塊分解成多個(gè)子任務(wù)。建立機(jī)坪保障協(xié)調(diào)關(guān)聯(lián)模型（Coordination Correlation Model for Apron Service，CCMAS），如圖2所示。

圖2 航班機(jī)坪保障協(xié)調(diào)關(guān)聯(lián)模型

定義1機(jī)坪保障協(xié)調(diào)關(guān)聯(lián)模型CCMAS={V，R，φ，E}，其中，V=Vr∪Vs∪Vm∪Vt，Vr為根結(jié)點(diǎn)集合，Vs為服務(wù)線結(jié)點(diǎn)集合，Vm為模塊結(jié)點(diǎn)集合，Vt=Vd∪Vo為任務(wù)結(jié)點(diǎn)集合（Vd為調(diào)派任務(wù)結(jié)點(diǎn)集合，Vo為作業(yè)任務(wù)結(jié)點(diǎn)集合）；關(guān)系集R=R1∪R2，其中R1={m，o}為不同層次結(jié)點(diǎn)間關(guān)系的抽象語(yǔ)義集合，m、o分別對(duì)應(yīng)必選、可選關(guān)系；R2={pp，pa}為作業(yè)任務(wù)結(jié)點(diǎn)間關(guān)系的抽象語(yǔ)義集合，分別對(duì)應(yīng)前置結(jié)束關(guān)聯(lián)、前置開(kāi)始關(guān)聯(lián)。m，o，pp，paV→φ（V），φ（V）為定義在V上的謂詞函數(shù)，對(duì)?x?V，φ（x）表示與結(jié)點(diǎn)x存在φ關(guān)系的所有結(jié)點(diǎn)集合；E={（Vi，Vj）|Vi，Vj?V}為結(jié)點(diǎn)間連接關(guān)系集合，即邊的集合。

CCMAS需滿足：①對(duì)（V1，V2）?E，V2?m（V1）∪o（V1）∪pp（V1）∪pa（V1），即邊集合中的元素必對(duì)應(yīng)某一協(xié)調(diào)關(guān)系；②對(duì)?V1?V，|{x?V|V1?m（x）}|+| {x?V|V1?o（x）}|+|{x?V|V1?pp（x）}|+|{x?V|V1?pa（x）}|≤1，即同一對(duì)結(jié)點(diǎn)間僅允許同時(shí)存在一種關(guān)系；③對(duì)V1，V2?m（x）∪o（x）且V1，V2?Vo，x?V，則V2?pp（V1）∪pa（V1），即與同一模塊結(jié)點(diǎn)存在關(guān)聯(lián)的作業(yè)任務(wù)結(jié)點(diǎn)之間一定對(duì)應(yīng)著前置作業(yè)關(guān)聯(lián)或后置作業(yè)關(guān)聯(lián)。

3 典型作業(yè)任務(wù)Petri網(wǎng)模型

3.1 單一設(shè)備作業(yè)任務(wù)Petri網(wǎng)模型

定義2單一設(shè)備作業(yè)任務(wù)Petri網(wǎng)模型UPN= {P，T，I，O，M0，Ω}，其中，P={Ps}∪{Pr}∪{Ps0，Ps1}，過(guò)程庫(kù)所Ps表示某任務(wù)狀態(tài)（s對(duì)應(yīng)于任務(wù)編號(hào)），設(shè)備庫(kù)所Pr表示完成此次作業(yè)的設(shè)備（r對(duì)應(yīng)于設(shè)備編號(hào)），Ps0，Ps1分別表示作業(yè)任務(wù)準(zhǔn)備就緒和完成狀態(tài)庫(kù)所；變遷ts0，ts1?T分別表示開(kāi)始和結(jié)束作業(yè)任務(wù)；I（O）為模型的輸入（輸出）函數(shù)；M0為模型的初始標(biāo)識(shí)；Ω：{Ps}→（Q+∪0）×（Q+∪∞）為作業(yè)過(guò)程庫(kù)所對(duì)應(yīng)的任務(wù)耗時(shí)約束，ps→Ωps=［ai，bi］，其中0≤ai≤bi，Q+為正有理數(shù)集。

單一設(shè)備作業(yè)任務(wù)Petri網(wǎng)模型UPN及其簡(jiǎn)化模型如圖3所示。對(duì)某一作業(yè)任務(wù)，用ij表示作業(yè)任務(wù)耗時(shí)，取值在時(shí)間區(qū)間［ai，bi］且實(shí)際指揮調(diào)度過(guò)程中可視情優(yōu)化。

圖3 單一設(shè)備作業(yè)任務(wù)Petri網(wǎng)模型及其簡(jiǎn)化模型

3.2多設(shè)備作業(yè)任務(wù)Petri網(wǎng)模型

多設(shè)備作業(yè)任務(wù)包括串聯(lián)型作業(yè)和并聯(lián)型作業(yè)。串聯(lián)型作業(yè)在同一時(shí)間僅允許一臺(tái)設(shè)備進(jìn)入機(jī)位開(kāi)展作業(yè)，并可分解為若干子任務(wù)，其Petri網(wǎng)模型如圖4（a）所示。

圖4 多設(shè)備保障作業(yè)及其對(duì)應(yīng)的Petri網(wǎng)模型

并聯(lián)型作業(yè)任務(wù)在同一時(shí)間可允許多臺(tái)設(shè)備進(jìn)入機(jī)位作業(yè)，其對(duì)應(yīng)Petri網(wǎng)模型如圖4（b）所示。對(duì)上述模型采用以下方法擴(kuò)展，以描述保障設(shè)備的場(chǎng)面調(diào)派行駛過(guò)程，如圖5所示。具體步驟：對(duì)每一作業(yè)任務(wù)PN模型增加資源庫(kù)所Rr描述保障設(shè)備無(wú)任務(wù)狀態(tài)；增加變遷分別描述設(shè)備被調(diào)用或結(jié)束調(diào)用，使得，同時(shí)對(duì)變遷賦時(shí)以描述設(shè)備由駐地進(jìn)入機(jī)位所需行駛時(shí)間；最后，在庫(kù)所和變遷之間增加使能弧，表明作業(yè)任務(wù)結(jié)束后，相應(yīng)地設(shè)備資源必須釋放。

4 機(jī)坪保障Petri網(wǎng)模型構(gòu)造算法

機(jī)坪保障作業(yè)任務(wù)之間存在以下關(guān)系：①前置結(jié)束關(guān)聯(lián)，即前一作業(yè)任務(wù)完全結(jié)束之后方可開(kāi)展后一作業(yè)任務(wù)；②前置開(kāi)始關(guān)聯(lián)，即一旦前一任務(wù)的機(jī)位作業(yè)開(kāi)始便可開(kāi)展后一任務(wù)機(jī)位作業(yè)。對(duì)典型任務(wù)Petri網(wǎng)模型合成方式如圖6所示。若兩任務(wù)之間滿足“前置結(jié)束關(guān)聯(lián)”關(guān)系，則對(duì)其模型可采取第1種合成方式；若兩任務(wù)之間滿足“前置開(kāi)始關(guān)聯(lián)”關(guān)系，則對(duì)其模型可采取第2種合成方式。

圖5 作業(yè)任務(wù)對(duì)應(yīng)Petri網(wǎng)模型的設(shè)備調(diào)派過(guò)程擴(kuò)展

圖6 典型作業(yè)任務(wù)Petri網(wǎng)模型的合成方式

機(jī)坪保障指揮調(diào)度Petri網(wǎng)模型構(gòu)造算法思路：首先，對(duì)CCMAS模型搜索，找出從根結(jié)點(diǎn)到作業(yè)任務(wù)結(jié)點(diǎn)路徑上的元素；其次，明確最底層各作業(yè)任務(wù)結(jié)點(diǎn)之間的協(xié)調(diào)關(guān)系；再次，基于典型作業(yè)任務(wù)Petri網(wǎng)模型構(gòu)造方法得到各任務(wù)結(jié)點(diǎn)對(duì)應(yīng)Petri網(wǎng)模型，并依據(jù)協(xié)調(diào)關(guān)系進(jìn)行合成；最后，對(duì)所有服務(wù)線任務(wù)結(jié)點(diǎn)對(duì)應(yīng)的Petri網(wǎng)模型進(jìn)行合成。

算法1：機(jī)坪保障指揮調(diào)度Petri網(wǎng)模型構(gòu)造算法。

Step1：確定CCMAS模型各服務(wù)線、模塊、任務(wù)構(gòu)成，并明確各結(jié)點(diǎn)間的協(xié)調(diào)關(guān)系；

Step2：確定CCMAS模型中從根結(jié)點(diǎn)到各作業(yè)任務(wù)結(jié)點(diǎn)的路徑集合A={r1，r2，…，rn}；

Step3：對(duì)路徑ri，rj?A，若存在服務(wù)線結(jié)點(diǎn)s1?ri∩rj，進(jìn)入Step4；

Step4：依據(jù)ri，rj中作業(yè)任務(wù)結(jié)點(diǎn)之間的協(xié)調(diào)關(guān)系，利用典型作業(yè)任務(wù)Petri網(wǎng)模型及其合成方法，得到作業(yè)任務(wù)Petri網(wǎng)模型；

Step5：對(duì)其他路徑ri，rj?A，重復(fù)Step3至Step4。

5 實(shí)例

以?？窟h(yuǎn)機(jī)位的過(guò)站航班機(jī)坪保障為例，構(gòu)建對(duì)應(yīng)的機(jī)坪保障指揮調(diào)度Petri網(wǎng)模型。該航班機(jī)坪保障服務(wù)線及作業(yè)任務(wù)信息如下頁(yè)表1所示（注：2輛擺渡車同時(shí)到機(jī)位開(kāi)始作業(yè)）。

表1 航班機(jī)坪保障作業(yè)服務(wù)線及作業(yè)任務(wù)信息

圖7 某航班保障作業(yè)對(duì)應(yīng)的CCMAS模型

依據(jù)定義1可得到該航班保障作業(yè)對(duì)應(yīng)的CCMAS模型如圖7所示。

利用所給模型生成算法，首先，從建立的CCMAS模型中獲取由根結(jié)點(diǎn)到各作業(yè)任務(wù)結(jié)點(diǎn)的路徑集合A={r1，r2，…，rn}；其次，明確作業(yè)任務(wù)結(jié)點(diǎn)之間的協(xié)調(diào)關(guān)系；再次，對(duì)各作業(yè)任務(wù)結(jié)點(diǎn)建立相應(yīng)的Petri網(wǎng)模型。以r1={v0，v1，v5，v14}，r2={v0，v1，v5，v15}為例，r1和r2具有相同的服務(wù)線結(jié)點(diǎn)v1，且作業(yè)任務(wù)結(jié)點(diǎn)v14是v15的“前置開(kāi)始關(guān)聯(lián)”結(jié)點(diǎn)。利用第3節(jié)所給典型作業(yè)任務(wù)Petri網(wǎng)模型構(gòu)建方法，其對(duì)應(yīng)地作業(yè)Petri網(wǎng)模型可記為P-NV14、P-NV15，如圖8所示；最后，對(duì)該服務(wù)線中其他任務(wù)結(jié)點(diǎn)進(jìn)行建模，并依據(jù)作業(yè)任務(wù)協(xié)調(diào)關(guān)系及對(duì)應(yīng)地模型合成方法，得到該服務(wù)線對(duì)應(yīng)地Petri網(wǎng)模型，如圖9所示。

進(jìn)一步，對(duì)其他服務(wù)線所含的任務(wù)結(jié)點(diǎn)建立對(duì)應(yīng)的Petri網(wǎng)模型，并合成得到該航班機(jī)坪保障指揮調(diào)度Petri網(wǎng)模型，如下頁(yè)圖10所示。

圖8 任務(wù)結(jié)點(diǎn)V12、V13對(duì)應(yīng)的Petri網(wǎng)模型

圖9 旅客服務(wù)線對(duì)應(yīng)的Petri網(wǎng)模型

6 結(jié)束語(yǔ)

提出一種基于Petri網(wǎng)的機(jī)坪保障指揮調(diào)度過(guò)程建模方法。其優(yōu)點(diǎn)在于：①CCMAS模型能從全局視角直觀、清晰地體現(xiàn)機(jī)坪保障作業(yè)任務(wù)協(xié)調(diào)關(guān)系；②以CCMAS模型和典型作業(yè)任務(wù)Petri網(wǎng)模型為基礎(chǔ)，可動(dòng)態(tài)生成機(jī)坪保障指揮調(diào)度Petri網(wǎng)模型，保證了建模靈活可擴(kuò)展。進(jìn)一步研究包括模型特性分析及基于所建模型的機(jī)坪保障指揮調(diào)度優(yōu)化算法設(shè)計(jì)。

圖10 航班機(jī)坪保障指揮調(diào)度Petri網(wǎng)模型

［1］Wu C L，Robert E.Modeling and Optimization of Aircraft Turnaround Time at An Airport［J］.Transportation Planning and Technology，2004，27（1）：47-66.

［2］袁崇義.Petri網(wǎng)原理［M］.北京：北京大學(xué)出版社，1999.

［3］宋麗娟，劉長(zhǎng)有.基于賦時(shí)庫(kù)所Petri網(wǎng)的飛機(jī)地面車輛資源配置［J］.中國(guó)民航大學(xué)學(xué)報(bào)，2008，26（增刊）：194-196.

［4］Vidosavljevic A，Tosic V.Modeling of Turnaround Process Using Petri Nets［C］//Proceedings of the 14th ATRS World Conference.Porto，Portugal.2010.

［5］Miquel A，Alexey N，Cesar T.A Simulation Model to Improve Air Cargo Operations in Passenger Aircraft［C］//Proceedings of the 2010 Summer Computer Simulation Conference，San Diego，2010.

［6］趙桂紅，劉利.延誤航班停機(jī)坪作業(yè)運(yùn)行控制研究［J］.中國(guó)民航學(xué)院學(xué)報(bào)，2006，24（4）：58-61.

［7］孫瑞山，張子仝.基于CPM的停機(jī)坪航班保障工作方法研究［J］.中國(guó)民航學(xué)院學(xué)報(bào)，2011，29（5）：23-26.

［8］Leeuwen P，Witteveen C.Temporal Decoupling and Determining Resource Needs of Autonomous Agents in the Airport Turnaround Proces［R］.NLR-TP-2009-336.

［9］Wu C L，Robert E.Modelling of aricraft roatation in a multiple airport environment［J］.Transportation Research，2002，38（2）：265-277.

［10］陶婧婧.機(jī)坪保障服務(wù)設(shè)備調(diào)度仿真與優(yōu)化［D］.南京：南京航空航天大學(xué)，2011.

［11］Du Y Q，Zhang Q，Chen Q S.ACO-IH：An Improved Ant Colony Optimization Algorithm for Airport Ground Service Scheduling［C］//Proceedingsofthe2008IEEE International Conference on Industrial Technology.2008.

Petri Net-based Modeling of Command and Dispatch for Flight Apron Service

ZHU Xin-ping，TANG Zhi-xing，XIA Zheng-hong
（School of Air Traffic Management，Civil Aviation Flight University of China，Guanghan 618307，China）

To support the optimization of apron service tasks scheduling，a Petri net-based modeling method for apron service process is proposed.The Coordination Correlation Model for Apron service（CCMAS）is established，including service lines，modules，and tasks，which demonstrates the hierarchal structure of apron service.The service task is categorized into single-equipment service and multi-equipments service process，and the corresponding time Petri net-based modeling approach is provide，including the extension for equipment dispatch process modeling.The composition method for different models is proposed for the front-start and front-end correlation among the corresponding tasks，and also the modeling algorithm of apron service based on the CCMAS was provided.Finally，the effectiveness and applicability of the proposed approach is demonstrated by one flight apron service process modeling.

airport，apron service，modeling，Petri net

V355.1

A

1002-0640（2015）12-0048-05

2014-12-05

2015-02-19

國(guó)家自然科學(xué)基金委員會(huì)與民用航空局聯(lián)合資助（U1433126）；中國(guó)民航飛行學(xué)院科研基金面上項(xiàng)目（J2013-60）

朱新平（1983-），男，湖南常德人，博士。研究方向：新一代空中交通管理系統(tǒng)。