朱新平，唐志星，夏正洪

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

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

朱新平，唐志星，夏正洪

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

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

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

0 引言

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

1 航班機坪保障過程

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

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

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

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

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

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

CCMAS需滿足：①對（V1，V2）?E，V2?m（V1）∪o（V1）∪pp（V1）∪pa（V1），即邊集合中的元素必對應(yīng)某一協(xié)調(diào)關(guān)系；②對?V1?V，|{x?V|V1?m（x）}|+| {x?V|V1?o（x）}|+|{x?V|V1?pp（x）}|+|{x?V|V1?pa（x）}|≤1，即同一對結(jié)點間僅允許同時存在一種關(guān)系；③對V1，V2?m（x）∪o（x）且V1，V2?Vo，x?V，則V2?pp（V1）∪pa（V1），即與同一模塊結(jié)點存在關(guān)聯(lián)的作業(yè)任務(wù)結(jié)點之間一定對應(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}，過程庫所Ps表示某任務(wù)狀態(tài)（s對應(yīng)于任務(wù)編號），設(shè)備庫所Pr表示完成此次作業(yè)的設(shè)備（r對應(yīng)于設(shè)備編號），Ps0，Ps1分別表示作業(yè)任務(wù)準(zhǔn)備就緒和完成狀態(tài)庫所；變遷ts0，ts1?T分別表示開始和結(jié)束作業(yè)任務(wù)；I（O）為模型的輸入（輸出）函數(shù)；M0為模型的初始標(biāo)識；Ω：{Ps}→（Q+∪0）×（Q+∪∞）為作業(yè)過程庫所對應(yīng)的任務(wù)耗時約束，ps→Ωps=［ai，bi］，其中0≤ai≤bi，Q+為正有理數(shù)集。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 實例

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

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

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

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

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

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

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

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

6 結(jié)束語

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

圖10 航班機坪保障指揮調(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］宋麗娟，劉長有.基于賦時庫所Petri網(wǎng)的飛機地面車輛資源配置［J］.中國民航大學(xué)學(xué)報，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］趙桂紅，劉利.延誤航班停機坪作業(yè)運行控制研究［J］.中國民航學(xué)院學(xué)報，2006，24（4）：58-61.

［7］孫瑞山，張子仝.基于CPM的停機坪航班保障工作方法研究［J］.中國民航學(xué)院學(xué)報，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］陶婧婧.機坪保障服務(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

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

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