基于HTCPN的牽引車動態優化調度

蘇志剛，趙松澤，郝敬堂

(中國民航大學 中歐航空工程師學院，天津 300300)

0 引 言

快速增長的航空運輸量極大增加了機場場面的運行壓力[1]。目前我國大部分機場的工作人員是通過目視、語音對講等方式對符合條件的車輛進行調度[2]，落后的信息獲取方式及決策過程導致航班高峰時段調度效率低下，進而影響航班的準點率。地勤保障車輛調度問題持續受到國內外學者的廣泛關注，研究方法主要集中在運籌學方法[3-7]和系統仿真方法[8-12]兩個方面。

運籌學方法是將車輛調度問題簡化為多目標優化模型，再利用啟發式算法進行求解。啟發式算法主要是對靜態調度問題進行優化。即假設在航班計劃、航班需求時間窗以及作業時間等信息已知并始終不變的前提下，根據航班的需求規劃車輛的行駛路徑。實際情況下影響航班運行的隨機因素較多。當隨機因素對原有航班計劃產生影響時，車輛資源需要重新分配。雖然啟發式算法可以得到可行解，但其不能很好地對調度過程中的隨機因素實時響應。

系統仿真方法利用離散仿真模型模擬調度流程，十分適用于機場車輛調度這種存在諸多不確定因素的離散動態隨機過程的分析。采用仿真方法可以很好地模擬調度過程中的突發事件，設計出針對不同隨機問題的解決方案。芝加哥機場和日本民航局采用TAAM[11](total airspace & airport modeler)對空域和飛行區進行仿真研究，分析機場的運行方式和空域構型。丹佛機場利用SIMMOD[12]分析現有飛行區的運行狀況以及新的改造措施對延誤的影響。上述仿真軟件雖然功能強大，但價格昂貴，且仿真的主要對象是航空器，僅有少部分功能涉及到車輛調度過程。

本文運用層次賦時著色Petri網(hierarchical timed colored Petri net，HTCPN)對牽引車調度過程進行仿真。利用層次Petri網(hierarchical Petri net，HPN)對系統進行模塊劃分，增加模型的可視性；利用著色Petri網(colored Petri net，CPN)對不同資源進行標記區分；利用賦時Petri網(timed Petri net，TPN)模擬牽引車資源占用和釋放的實時情況。搭建動態調度仿真系統，根據航空器發送的推出申請完成航空器與牽引車的動態匹配。提出調度優化方案，實現不同車輛間工作負荷均衡度最高和車輛行駛總距離最短的優化目標，通過仿真實驗驗證了優化的有效性。最后完成對目標機場牽引車保障能力的評估，預測在不同航班密度下的牽引車配置數量。

1 牽引車調度數學模型

1.1 調度流程分析

針對牽引車調度特點，將調度流程簡化為如下步驟：首先按照假設的規則隨機生成離港航班信息，系統根據每架航空器的預計離港時刻非降序排列所有航班信息形成航空器等待隊列，每架航空器在其預計離港時刻前TRequest分鐘發出推出申請；系統按照設定的動態優化調度目標逐一為待服務航空器分配滿足條件的牽引車前往服務；牽引車在開始推出任務前判斷與鄰近機位是否存在推出沖突，如存在沖突則在原地等待；待沖突解脫后牽引車將航空器推出到指定位置，并完成信息的記錄與更新。

1.2 基本假設

機場場面運行過程中包含諸多隨機因素，在不影響牽引車和航空器正常運行的前提下對模型做如下假設：

(1)單位時間內離港航空器數目服從參數為λ的泊松分布[13，14]；

(2)正常情況下，每架航空器在其預計離港時刻前TRequest=15min發出推出申請；

(3)牽引車推出航空器時與鄰近機位發生推出沖突的概率為PConflict， 若存在推出沖突，牽引車和航空器在原地等待的時間滿足均值為TConflict的指數分布；

(4)牽引車推出航空器的作業時間服從高斯分布N(μ,σ2)。 作業時間的均值μ由被服務航空器的機型決定。標準差σ的取值與航空器機型無關，與推出時地服人員和飛行員配合的熟練度有關。

1.3 優化目標

在現有運行模式下，調度部門收到推出申請后，會按照車輛序號順序分配可用車輛。如果存在可用車輛，立刻分配該牽引車從當前位置駛向指定機位進行服務。若所有牽引車當前時刻均處于工作狀態，調度人員會根據反饋信息指派最先完成當前任務的牽引車執行該任務。現行調度規則存在以下問題。

(1)每輛牽引車航班任務分配不均衡；

(2)為航空器分配牽引車時沒有考慮候選車輛與服務需求點間的距離。

為解決當前調度模式下存在的問題，需要依次從車輛到達時間、車輛工作負荷均衡度和車輛行駛距離3個方面進行優化。

車輛到達時間：在實際運行中時間因素最為重要，要求車輛延誤到達的時間最少

(1)

式中：ti表示第i架航空器因牽引車晚點造成的延誤時間，式(2)是表示延誤與否的符號函數

(2)

車輛工作負荷均衡度：為保證牽引車的安全使用和駕駛人員的合理分配，調度車輛時應盡量提高不同車輛間工作負荷的均衡度，本文采用車輛間工作負荷差的累積和作為表征均衡度的目標函數

C2=min∑i,j∈V|Ni-Nj|

(3)

式中：V表示牽引車的集合，Ni和Nj表示編號為i和j的牽引車服務過的航班數量。

車輛行駛距離：牽引車在不同機位間往返的距離不可忽略，減少行駛距離可進一步保證牽引車的準時到達，同時降低機場或航空公司的燃油成本

C3=min∑i∈VDi

(4)

式中：Di表示編號為i的牽引車行駛過的總距離。

2 HTCPN動態調度仿真系統

2.1 模型描述

建模采用自頂向下的分解原則。首先確定調度流程的整體功能模型圖，然后再對頂層模型進一步細化，在子頁中實現子流程功能，形成分層模型。牽引車動態調度仿真系統的層次賦時著色Petri網模型可簡化為以下多元組

HTCPN=(S,SN,SA,PN,PT)

(5)

HTCPN中各參數的含義分別為：

(1)S代表子頁的有限集合，每個子頁對應于調度過程中一個關鍵的子流程，依次為航空器推出申請、航空器牽引車實時匹配、航空器推出沖突、航空器推出過程。S中的任意子頁s均是一個非層次的賦時著色Petri網

s=(CPN,R,r0)

(6)

式中：R是時間值的集合，稱為時間戳；r0是R中的元素，對應于調度過程的起始時刻。

(2)SN是替代變遷，SN?T，T表示變遷集合，采用變遷代表Petri網結構中的某一模塊，使得網絡在邏輯上得到簡化，之后在對應的子頁再進行更深層次的精細化建模。

(3)SA是頁分配函數，SA∶SN→S， 表示子頁和替代變遷間的對應關系。

(4)PN代表端口節點的集合，PN?P，P表示庫所集合。

(5)PT是端口類型函數，是從PN定義到{In,Out,In/Out,General} 的函數。

式(6)中的參數CPN表示一個非層次的著色Petri網，可用如下9元組表示

CPN=(P,T,A,Σ,V,C,G,E,I)

(7)

式中：P表示庫所集合，以橢圓形表示，可以表示動態調度仿真系統各資源的實時狀態；T表示變遷集合，以矩形表示，代表調度中每個具體事件的發生，實現不同庫所間的信息傳遞；A為有向弧集合，是聯系庫所和變遷之間的流關系；Σ為顏色集的非空有限集合；V為變量集合；C為顏色集函數，定義庫所的數據類型；G為變遷上的守衛表達式，E為有向弧表達式，守衛表達式和弧表達式共同定義了變遷的使能條件；I為初始化函數，定義庫所的初始標記。

托肯(token)表示分配給庫所的資源，在Petri網模型的執行過程中會發生個數和位置的變化。牽引車和航空器是模型中兩種不同類型的資源，分別對其著以不同的顏色進行分類。變遷觸發后會從其輸入庫所移出托肯，同時向輸出庫所增加托肯, 從而引起模型狀態的改變。航空器與牽引車的顏色集見表1。

表1 航空器與牽引車顏色集

航班號、停機位、牽引車編號等初始屬性的作用是對托肯的活動進行約束，牽引車到達時刻、牽引車已服務航班序列、牽引車當前位置等屬性則會隨系統的運行實時更新，更新后的結果將成為后續運行中新的約束條件。

2.2 頂層模型

動態調度仿真系統的頂層模型如圖1所示。替代變遷用雙框矩形表示，各替代變遷的含義見表2。

表2 頂層模型中替代變遷及其對應子過程

圖1 牽引車調度頂層模型

庫所右下方的標識代表顏色集，根據容納的資源類型分為4類：航空器狀態庫所(PInfor)、航空器隊列狀態庫所(LPInfor)、牽引車集合狀態庫所(LCInfor)和約束類庫所(LDistance,Cap)。

庫所Plane存儲系統隨機生成的航班信息，庫所Tug存儲機場內初始時刻所有牽引車的信息，庫所Airport對應于機坪不同位置點距離的錄入，以上3個庫所是模型中初始信息的輸入窗口。所有航空器會依次通過4個替代變遷，最終回到Finish PlaneList庫所中，該庫所的作用是記錄每架航空器被推出后的最終狀態。此外，庫所Capacity對航空器等待隊列起到容量約束的作用。在庫所和替代變遷的共同作用下，調度過程的HTCPN模型形成一個閉環反饋結構。

2.3 航空器推出申請

頂層模型中表示航空器推出申請的替代變遷(Request)展開后可得到如圖2所示的子頁模型。

圖2 航空器推出申請模型

系統首先通過Timetable變遷在一定規則下隨機生成航班數據。該變遷守衛表達式中的density用于模擬服從泊松分布的航班流。庫所Apron中存儲系統自動生成的離港航空器所在停機位編號，分配時采取隨機原則，同時確保同一機位在2小時內不會被再次分配。生成的航班信息在List中以列表的形式存儲。List中的航班列表再通過Sort變遷完成按預計離港時刻的非降序排列，在Queue中形成航班的等待隊列。最后通過Request變遷逐一發出推出申請。通過Capacity庫所可以使系統逐一地接收航空器隊列發出的推出申請，從而實現對航空器等待隊列的容量約束。端點為空心圓的弧為抑制弧，作用是設置變遷發生的優先權。當庫所Plane中存在托肯時，變遷Sort無法發生，通過抑制弧使排隊過程在航班信息生成后進行，從而可以自主控制仿真實驗中的航空器數目。Request變遷輸出弧上的applytime是航空器發出推出申請的時刻，作為每架航空器初始狀態下攜帶的時間戳。

2.4 航空器牽引車實時匹配

基于貪婪算法設計了航空器牽引車實時匹配算法。貪婪算法是以當前情況為基礎追求局部最優解，可以針對航空器隊列發出的推出申請逐一完成牽引車的分配，對動態調度問題有一定的解決能力，航空器牽引車實時匹配算法如圖3所示。

圖3 航空器牽引車實時匹配算法

系統在讀取待服務航空器發出的推出申請后，依次以車輛到達時間、車輛工作負荷均衡度以及車輛行駛距離為判據篩選出滿足條件的牽引車集合。

首先實現車輛到達時間的匹配，篩選出當前時刻處于空閑狀態的牽引車集合，如若沒有空閑車輛，則選定完成當前任務時刻最早的牽引車。車輛工作負荷均衡度匹配是對每輛牽引車服務過的航班數進行非降序排列并篩選出服務航班數最少的牽引車集合。最后再對每輛牽引車行駛總距離完成非降序排列，篩選出行駛總距離最少的牽引車，從而實現車輛行駛距離的匹配。若此時滿足條件的牽引車仍多于一輛，則按照車輛序號順序隨機指派一輛牽引車前往服務。

基于上述算法建立了如圖4所示的航空器牽引車實時匹配模型。

圖4 航空器牽引車實時匹配模型

模型中從上至下的3個替代變遷分別對應于流程圖中的車輛到達時間匹配、車輛工作負荷均衡度匹配和車輛行駛距離匹配。每個替代變遷后的節點庫所分別表示航空器的最新狀態和經過篩選后的牽引車集合狀態。

發出推出申請后的航空器首先與牽引車集合Tug同時綁定于Arrival Time替代變遷，目的是篩選出滿足時間要求的牽引車集合。經過第一步篩選后的牽引車集合和航空器同時綁定于Load Balance替代變遷，篩選出服務航班數輛最少的牽引車集合。Airport以鄰接矩陣的格式存儲目標機場內不同位置點間的距離，通過Distance替代變遷搜索出每輛牽引車當前位置與待服務航空器間距離并計算出行駛到目的點的時間。經過3個替代變遷篩選后產生唯一滿足條件的牽引車，系統安排該牽引車前往相應的停機位進行服務。

2.5 航空器推出沖突

在機場運行高峰時段，鄰近停機位航班常會因離港時間過近而引發沖突。當航空器側向推出時與同側鄰近停機位上另一正要推出的航空器由于安全間隔而產生沖突[15]，發生推出沖突后的解決方案是后機在原地等待，只有當前機推出并滑行通過推出安全點后，后機才能開始推出，推出沖突會導致牽引車使用時間的增加以及實際推出時間的延遲，推出沖突的模型如圖5所示。

圖5 航空器推出沖突模型

待服務航空器與上一步篩選出的牽引車同時綁定于變遷Ran，通過Ran在庫所Conflict中產生隨機數ran，再根據Normal和Wait上的守衛函數判斷航空器推出沖突事件是否發生。當ran>P時，變遷Normal使能，航空器正常推出；當ran≤P時，沖突產生，變遷Wait使能。P表示發生推出沖突的概率。時間延遲delay表示產生推出沖突后航空器和牽引車需要在原地等待的時間。

2.6 航空器推出過程

航空器推出后伴隨著牽引車和航空器信息的更新，航空器推出過程模型如圖6所示。

圖6 航空器推出過程模型

首先通過替代變遷UpdateTug，代表牽引車的托肯重新回到牽引車資源庫所(Tug)，此時牽引車服務過航班序列、當前時刻位置、可為下一航班開始服務時刻、行駛總距離等屬性隨之更新。下一步再通過替代變遷UpdatePlane完成航空器信息的更新，代表航空器的托肯進入已被推出航空器隊列庫所(Finish PlaneList)，記錄航空器被服務后的最終狀態，包括匹配的牽引車編號、牽引車到達時刻、開始推出時刻、完成推出時刻等屬性。推出任務完成后容量庫所中的托肯也完成更新，服務對象轉變為下一架發出推出申請的航空器。

3 系統仿真分析

選定天津濱海國際機場作為研究對象，驗證HTCPN動態調度仿真系統解決實際問題的有效性。機場停機位布局如圖7所示，特種車輛需嚴格按指定路線行駛，即圖中各停機位之間的連接線，牽引車的停車場位于118號和201號停機位之間。

圖7 天津機場停機位布局

根據地理位置可以得出不同地面點間的鄰接關系，并計算出任意兩個地面點之間的最短距離。根據文獻[16]中的通用配置方法可估算出天津機場牽引車理論配置數量為12輛。表3為仿真實驗中假設的推出作業時間均值與機型的關系。

表3 作業時間均值

基于蒙特卡洛方法[17]對高峰時段的牽引車動態調度進行仿真分析，仿真系統中初始設定航班密度λ=25架次/小時，牽引車行駛速度v=20km/h，作業時間的標準差σ=0.5min，推出沖突發生概率PConflict=20%， 原地等待時間均值TConflict=5min。 在不同的服務航班數量下分別進行100次獨立實驗，圖8和圖9顯示了牽引車工作負荷均衡度和牽引車平均行駛總距離優化前后結果的對比。

圖8 車輛間工作負荷差累積和

圖9 牽引車平均行駛總距離

圖8的縱軸是表征不同車輛工作負荷均衡度的負荷差累積和∑i,j∈V|Ni-Nj|， 優化前車輛負荷差累計和與服務航班數量呈現正相關的趨勢。優化后的結果大幅降低，負荷差累計和隨航班數量的增加近似周期性變化，在服務航班數量為60時達到最低點，由于實驗中12輛牽引車被分配的任務數幾乎相等，所以車輛間工作負荷差累積和趨近于0。

由圖9可見，場面內所有牽引車平均行駛總距離與服務航班數量的關系。隨著服務航班數量的累加，行駛總距離的優化結果會更為顯著。

為體現仿真系統對隨機變化的動態反應，在保證離港航班信息相同的前提下，可以將系統中一些隨機化處理的數據轉化為固定的常量再次實驗后進行對比分析。在對照組實驗中，將發生航空器推出沖突的概率設置為0，牽引車推出航空器的作業時間不再服從高斯分布，所有航空器的推出時間均為5 min。

表4中分別羅列了引入常量數據和隨機數據每輛牽引車依次服務過的航班序列。

表4 牽引車服務過航班序列

結合每個航空器托肯最終狀態下攜帶的牽引車到達時刻、開始推出時刻和完成推出時刻分別繪制了兩次實驗結果對應的甘特圖，如圖10和圖11所示。

圖10 采用常量數據時牽引車調度結果

圖11 采用隨機數據時牽引車調度結果

綜合表4、圖10和圖11可以發現，當考慮到航空器發生推出沖突的可能性以及推出時間分布的隨機性后，牽引車的等待時間和服務時間會相應地受到影響，此時系統會以當前情況為基礎追求局部最優解，因此航空器與牽引車的匹配方案較采用常量數據時產生了較大的變化。

民航局相關文件規定，牽引車應在待服務航空器預計離港時刻前5 min到位，否則將被視作晚點到達。由圖10和圖11可見，每個航班任務的牽引車等待時間均大于5 min，表明沒有延誤發生，且優化后每輛牽引車的任務量得到了合理的分配。

調整航班密度λ和牽引車數量N進一步評估天津機場牽引車的保障能力。在每組參數下進行200次蒙特卡洛實驗，牽引車晚點率隨λ和N的變化關系如圖12所示。

圖12 牽引車晚點率變化曲線

選擇以晚點率10%作為評估保障能力合格與否的臨界值。從圖中可以發現，當λ≤29架次/小時，11輛牽引車就可以將晚點率控制在10%之下，表明機場當前配置的12輛牽引車是冗余的，此時可適當減少場面內牽引車的使用數量；當30架次/小時≤λ≤33架次/小時，當前機場配置剛好滿足準點要求，牽引車數量應當維持現狀；當34架次/小時≤λ≤37架次/小時，現有配置已無法滿足需要，配置13輛牽引車才可使得晚點率降低到10%以下；當λ繼續增大時，在現有配置下增加兩輛牽引車才可有效改善牽引車的延誤問題。

4 結束語

基于層次賦時著色Petri網理論搭建了機場牽引車動態調度仿真系統。根據航空器實時發送的推出申請完成牽引車的動態分配。同時考慮了運行過程中各個環節的隨機性以及高峰時段可能發生的推出沖突問題。在還原機場現有調度模式的基礎上，對調度過程進行了多目標優化，首先實現航班延誤最少這一基礎目標，之后依次實現不同車輛間工作負荷均衡度最高和車輛行駛總距離最短的優化目標。以天津濱海國際機場為例，通過蒙特卡洛實驗驗證了優化的有效性，同時驗證了本方法可以對目標機場的牽引車保障能力進行評估，最后通過本方法預測出在不同航班密度下必要的牽引車配置數量。