姬莉霞，張 晗

（鄭州大學(xué)軟件技術(shù)學(xué)院，河南鄭州 450002）

0 引言

如何對到港飛機進(jìn)行高效合理的排序是管制員的主要職責(zé)，管制員根據(jù)飛行數(shù)據(jù)、經(jīng)驗和直觀判斷，確定飛機著陸次序和時間?，F(xiàn)有調(diào)度策略一般在滿足相鄰飛機尾流間隔和其他空管規(guī)則的限制下，根據(jù)先到先服務(wù)（first come first serve，F(xiàn)CFS）原則制定每架飛機的著陸時間。此方法存在很大局限性:首先，管制員在短時間內(nèi)做出決定，很難詳細(xì)考慮各種方案的利弊，可能會造成不必要的沖突和延誤;其次，從經(jīng)濟(jì)效益考慮，調(diào)度方案的不科學(xué)性將導(dǎo)致著陸總成本的無謂增加。

飛機著陸調(diào)度問題在近20年來得到各國研究機構(gòu)和空管部門的廣泛研究［1～4］，主要內(nèi)容為確定著陸飛機隊列的順序、時間和跑道指派，以達(dá)到減小延誤、提高系統(tǒng)容量和增強飛行安全的目的。本文在研究相關(guān)文獻(xiàn)的基礎(chǔ)上，主要從三方面著手研究:1）在每架飛機著陸時間窗范圍內(nèi)安排著陸時間;2）滿足相鄰飛機最小尾流間隔;3）根據(jù)機型、環(huán)境因素、到達(dá)時間等參數(shù)安排跑道和著陸時間。采用時間自動［5］（timed automata，TA）機及其擴展分支價格時間自動［6］（priced timed automata，PTA）機作為形式化方法。

1 問題描述與概念模型的建立

假設(shè)某機場具有m條不同方向的跑道，交通流量為Δt時間內(nèi)有n架飛機著陸，集合E={i|1≤i≤n}代表飛機以最佳巡航速度預(yù)計到達(dá)序列，即飛機最佳著陸時間序列，集合W={［i，j］|1≤i≤2，1≤j≤n}為飛機著陸時間窗，集合S={j|1≤j≤n}為調(diào)度后飛機的實際降落時間序列。本文采用的調(diào)度結(jié)果是得到與E（i）一一對應(yīng)的S（j），并滿足以下約束:

1）飛機在其時間窗內(nèi)降落

2）同一跑道上連續(xù)降落的飛機滿足安全尾流間隔。以i?j為飛機j尾隨i降落在相同跑道;常量C表示基準(zhǔn)尾流間隔;集合T={［i］|1≤i≤n}為飛機相應(yīng)的尾流間隔系數(shù);e為綜合環(huán)境影響參數(shù)，主要包括風(fēng)力風(fēng)向、跑道方向、雨雪霧等，這些因素皆能對安全尾流間隔造成影響，從而直接影響后續(xù)飛機著陸時間和額外成本

3）著陸時飛機如果能夠逆風(fēng)飛行，不僅可以使?fàn)顟B(tài)更穩(wěn)定，而且著陸后可以更快地在跑道上停止，從而減少所需跑道的長度和安全尾流間隔，因此，盡可能為到港飛機安排逆風(fēng)的跑道。用R={i|1≤i≤m}為跑道的角度，變量d為風(fēng)向，兩者采用相反的原始坐標(biāo)和相同的增加方向

飛機著陸調(diào)度的目標(biāo)通常為容量最大或總延誤最小，本文兼顧兩者，采用額外總成本最優(yōu)作為目標(biāo)。假設(shè)第i架飛機單位時間內(nèi)因為提前降落而加速飛行產(chǎn)生的額外費用為F（i），單位時間內(nèi)延遲降落盤旋產(chǎn)生的費用為Y（i），則額外消耗最優(yōu)成本問題的概念性數(shù)學(xué)模型為

2 形式化模型的建立

2．1 時間自動機和價格時間自動機

時間自動機被廣泛應(yīng)用于各類擁有觸發(fā)事件和時間約束的復(fù)雜實時系統(tǒng)，在模型驗證方面得到了非常廣泛的應(yīng)用［7］。

定義1:一個時間自動機是一個八元組TA=（L，l0，C，A，E，I，V，T）:L為有限位置集合;l0∈L為開始位置集合;C為有限時鐘集合;A為有限動作集合;E?L×Ф（C）×A×2C×L為邊的集合，邊一般伴隨有動作、衛(wèi)士條件和復(fù)位時鐘集合;I:L→Ф（C）為位置的不變式;V為有窮變量集合;T:L×A→L為轉(zhuǎn)換函數(shù)。

價格時間自動機是在時間自動機的基礎(chǔ)上擴展價格元素的模型，它是建模和解決成本最優(yōu)問題的形式化方法。

定義2:一個價格時間自動機是一個九元組PTA=（L，l0，C，A，E，I，V，P，T），其中，L，l0，C，A，E，I，V，T與TA中意義相同，P:L∪E→N0表示給位置和邊分配價格元素。

多個并發(fā)的PTA可以構(gòu)成價格時間自動機網(wǎng)絡(luò)，每個PTA都有自身的狀態(tài)，它們之間共享時鐘變量和全局?jǐn)?shù)據(jù)變量，并通過邊上的動作同步協(xié)作，通過共享全局變量進(jìn)行傳值通信。格局用于描述價格時間自動機網(wǎng)絡(luò)中所有PTA的運行狀態(tài)。

定義3:假設(shè)有n個價格時間自動機PTA1，…，PTAn，由這n個價格時間自動機構(gòu)成的網(wǎng)絡(luò)為價格時間自動機的積，記為PTAN≡PTA1‖PTA2…‖PTAn，它的一個格局表示為一個三元組c=〈l，r，v〉，其中

2．2 調(diào)度主體的PTA模型

飛機著陸問題牽涉的最重要對象是飛機，取樣n架飛機，抽象得到如圖1所示的價格時間自動機模型Aircraft。在模型中，位置Approach表示飛機進(jìn)入管制臺雷達(dá)視線范圍，位置 Early，Ontime，Delay分別為飛機提前［W（1，i），E（i）］、準(zhǔn)時E（i）和延后［E（i），W（2，i）］，在轉(zhuǎn)換約束下，這3個位置僅有1個可能處于活動狀態(tài)。位置Early產(chǎn)生的額外成本為引擎加速飛行造成，計算方法為該位置的價格與其處于活動狀態(tài)的時間的積。位置Ontime為緊迫位置，也就是當(dāng)其轉(zhuǎn)換條件滿足時毫無延遲的發(fā)生，在此位置不產(chǎn)生額外成本。位置Delay產(chǎn)生的額外成本為盤旋等待著陸產(chǎn)生的消耗，計算方法為該位置的價格與該位置處于活動狀態(tài)的時間的積。緊迫位置Urg保證在臨近時間窗結(jié)束時，暫時不考慮成本因素，優(yōu)先降落。位置Special表示在綜合環(huán)境影響參數(shù)高于安全著陸閾值時，收到廣播信號poor，此時飛機等待著陸或備降信號。

圖1 飛機的價格時間自動機模型示意圖Fig 1 Diagram of PTA model of aircraft

2．3 交互實體的PTA模型

在著陸過程中，與飛機交互作用的實體應(yīng)具備以下特征:擁有唯一的身份標(biāo)識以區(qū)別于其他實體;擁有一定的物理或者虛擬屬性，狀態(tài)可以被改變或者可以被感知;具有通信能力。如果將各個交互實體看作對象，那么相同屬性的實體可以被抽象為類，從飛機著陸過程中，可以抽象出控制臺、管制員、雷達(dá)、跑道、環(huán)境等類，為弱化系統(tǒng)內(nèi)部交互，將雷達(dá)和管制員并入控制臺類，則各實體的PTA模型示意如圖2所示。

圖2 交互實體的價格時間自動機模型示意圖Fig 2 Diagram of PTA models of interacting entities

跑道（runway）模型的位置Idle和Use分別表示跑道空閑和使用，跑道的選擇通過邊ready的價格參數(shù)來確定，優(yōu)先為飛機安排空閑逆風(fēng)跑道，跑道選定后判斷風(fēng)力是否為積極影響，并據(jù)此影響尾流間隔。環(huán)境屬性只能被感知而不能被改變，其模型 Enviorment的固有屬性es，ew，er，es，ef和wdir分別表示當(dāng)前風(fēng)力參數(shù)、降雨參數(shù)、冰雪參數(shù)、霧靄參數(shù)、其他環(huán)境系數(shù)以及當(dāng)前風(fēng)向，當(dāng)綜合環(huán)境影響參數(shù)超出安全著陸閾值時，通過控制器發(fā)出廣播信號poor。控制器模型 Control主要通過信道 approach，ready，land，done以及廣播信道poor與飛機、環(huán)境和跑道協(xié)同交互。

3 最優(yōu)成本可達(dá)性問題

最優(yōu)成本可達(dá)性問題就是找到一個到達(dá)給定目標(biāo)位置的最小花費［2，8］。由于時鐘被定義為非負(fù)整數(shù)，價格轉(zhuǎn)換系統(tǒng)可以是無限的，與價格符號狀態(tài)［9］相關(guān)的成本也可能是無限的。在探索過程中，如果沿不同的路徑到達(dá)相同的狀態(tài)的成本不同，則丟棄更昂貴的狀態(tài)。類似于時間自動機，PTA的價格符號狀態(tài)通過時鐘域的簡單約束來表示，成本通過價格時鐘域［9］上的仿射平面給出。

在PTA驗證工具UPPAAL CORA中，最優(yōu)成本的可達(dá)性分析使用如下所示標(biāo)準(zhǔn)分支界定算法，算法可以使用不同的搜索策略，目前有廣度優(yōu)先、（隨機）深度優(yōu)先、最佳深度優(yōu)先、最佳優(yōu)先和用戶啟發(fā)式等。

Cost記錄當(dāng)前已知最優(yōu)成本，列表Passed和Waiting分別記錄已搜索過的和待搜索的符號狀態(tài)，算法迭代搜索直至沒有狀態(tài)需要搜索。在While循環(huán)中，根據(jù)分支策略選擇未搜索狀態(tài)S，如果S被已搜索狀態(tài)主導(dǎo)或者其成本不可能更低，則跳過此狀態(tài);否則，如果S是目標(biāo)狀態(tài)，則得到最優(yōu)成本;如果S不是目標(biāo)狀態(tài)，則將其所有后繼加入Waiting序列并進(jìn)行下一次迭代。

4 仿真分析

某機場由3條跑道組成，交通需求平均88架/h，表1給出某時間段的一組數(shù)據(jù)。以該機場為例，在 UPPAAL CORA中，將系統(tǒng)模型實體化，追蹤模擬系統(tǒng)運行狀況，得到多種運行軌跡。

表1 部分到港飛機數(shù)據(jù)Tab 1 Datas of partial inbound aircraft

圖3給出單條跑道極限容量下1 h內(nèi)對40架飛機仿真調(diào)度示意。不同長度的黑色線段代表不同類型的飛機;E0表示最優(yōu)著陸時間序列，存在嚴(yán)重沖突;S1表示忽略環(huán)境影響時現(xiàn)有FCFS調(diào)度結(jié)果，各飛機的著陸時間被勻化，一旦延遲發(fā)生，將不可避免的造成后續(xù)延遲累加，平均延時約191 s;S2表示與S1對應(yīng)的基于PTA的調(diào)度結(jié)果，平均延時約156 s;S1＇表示風(fēng)向隨機波動、環(huán)境影響參數(shù)在安全著陸范圍內(nèi)隨機波動情況下現(xiàn)有FCFS調(diào)度結(jié)果，平均延時約221 s;S2＇表示與S1＇對應(yīng)的基于PTA的調(diào)度結(jié)果，平均延時約169 s。

表2給出該機場24 h對2113架飛機仿真優(yōu)化調(diào)度成本、延誤和容量等分析結(jié)果。在不考慮和考慮環(huán)境影響2種情況下，平均延誤減小幅度分別為30．22%和32．70%;跑道容量增幅分別為5．28%和6．71%;因加速、盤旋、環(huán)境等造成額外成本減幅分別為32．92%和34．28%。從該結(jié)果可以看出:在以最優(yōu)成本為目標(biāo)的PTA方法中，平均延時和額外成本有較大幅度下降，跑道容量也有一定的提升空間，在考慮環(huán)境影響因素情況下效果尤為顯著。

圖3 單跑道調(diào)度結(jié)果示意圖Fig 3 Scheduling result diagram of a single runway

表2 24 h仿真調(diào)度結(jié)果分析Tab 2 Simulation scheduling results analysis in 24 h

5 結(jié)束語

針對目前飛機著陸調(diào)度方法的不足，以著陸消耗成本為目標(biāo)，考慮環(huán)境因素的影響，給出了飛機著陸調(diào)度需要滿足的限制條件和最優(yōu)成本問題的數(shù)學(xué)描述。使用價格時間自動機作為形式化建模方法，對飛機、跑道、控制器、環(huán)境等交互實體進(jìn)行建模，使用UPPAAL CORA對模型實體進(jìn)行模擬分析和求解最優(yōu)成本的可達(dá)性，并對某機場飛機著陸調(diào)度數(shù)據(jù)進(jìn)行仿真實驗和分析。為復(fù)雜環(huán)境下安全高效地進(jìn)行飛機著陸調(diào)度提供了科學(xué)的建議。

［1］ Alur R，Trivedi A．Relating average and discounted costs for quantitative analysis of timed systems［C］∥The 11th ACM International Conference on Embedded Software，New York，2011．

［2］ Behrmann G，Larsen G K G，Rasmussen J I．Priced timed automata:Algorithms and applications［C］∥International Symposium Formal Methods for Components and Objects（FMCO），Berlin，Heidelberg:Springer-Vedag，2004．

［3］ Chen Shuang，Xia Xuezhi．Researches on optimal scheduling model for aircraft landing problem［C］∥2009 WASE International Conference on Information Engineering:IEEE Computer Society，2009:418-421．

［4］ 余 江，劉曉明，蒲 云．飛機著陸調(diào)度問題的MPS優(yōu)化算法研究［J］．系統(tǒng)工程理論與實踐，2004（3）:119-133．

［5］ Alur R，Dill D L．A theory of timed automata［J］．Theoretical Computer Science，1994，126:183-235．

［6］ Behrmann G，F(xiàn)elmker A，Hune T，et al．Minimum-cost reachability for priced timed automata［C］∥Lecture Notes in Computer Science，Berlin，Heidelberg:Springer-Verlag，2001．

［7］ 周清雷，姬莉霞，王艷梅．基于UPPAAL的實時系統(tǒng)模型驗證［J］．計算機應(yīng)用，2004，24（9）:129-131．

［8］ Behrmann G，Larsen K，Rasmussen J．Optimal scheduling using priced timed automata［C］∥ACM SIGMETRICS Perfoin’lance E-valuation Review，New York:ACM，2005．

［9］ Larsen K，Behrmann G，Brinksma E，et al．As cheap as possible:Efficient cost-optimal reachability for priced timed automata［C］∥Proc of Computer Aided Verification，2011:493-508．