動態(tài)時隙再分配的分布式協(xié)同進化模型研究

王 湛，吳 術(shù)

(1.南京航空航天大學民航學院，南京210016;2.南京大學工程管理學院，南京210093)

1 引言

隨著CDM(流量管理協(xié)同決策機制)在空中交通中的深入研究和廣泛應用，協(xié)同時隙再分配管理將從集中式?jīng)Q策逐步過渡到分布式協(xié)同決策模式，可分為簡單交易和復雜交易問題.簡單交易，即“一對一”交易，指一次只允許交易一個時隙資源;復雜交易，即“多對多”的交易，可以同時交易多個時隙資源.協(xié)同時隙再次分配問題實質(zhì)上就是一種資源協(xié)調(diào)交易問題，其主要個體為流管部門和航空公司，流管部門分配目標為最大化資源利用率，航空公司分配目標為最大化自身效益，相應的群體目標為在最大化資源利用的基礎上，最小化總延誤損失［1-3］.

DCCEA使用一種新的小生境機制、保留非劣解的檔案和一種擴展操作.算法可根據(jù)決策變量的個數(shù)將問題分解，產(chǎn)生多個子種群，然后通過子種群的協(xié)同進化來逼近問題的全局Pareto最前端［4］.分析該算法在處理分布式動態(tài)協(xié)同優(yōu)化問題上的優(yōu)勢及特點，將該算法應用于協(xié)同時隙再次分配中，構(gòu)建基于動態(tài)時隙再分配的分布式協(xié)同多目標進化算法模型，可有效解決分布式動態(tài)環(huán)境下的CDM GDP時隙再次分配問題.

2 DCCEA模型構(gòu)建

DCCEA可通過將復雜系統(tǒng)分解為獨立進化的模塊，利用一組獨立進化的種群來解決問題，在模塊進化過程中，存在模塊的集成以還原成完整系統(tǒng).在時隙再分配過程中，分配結(jié)果由內(nèi)外部效用共同決定，同時內(nèi)外部效用又由各自不同的效用函數(shù)決定，由此，結(jié)合上述DCCEA的特點可知構(gòu)建基于時隙再次分配的DCCEA模型的可行性.

2.1 協(xié)同時隙再分配復雜交易效用分析

在時隙再分配中，AOC(航空公司運控中心)為時隙提供者和需求者，可同時取消或延誤多個航班、放棄它們占用的較早時隙，其請求交易的必要條件為:能在其指定時隙區(qū)間集內(nèi)獲得多個可以為后面某些航班所用的較晚時隙，以消除或降低延誤;同時為了獲得多個較早時隙，以降低某些航班的延誤［5-9］.為便于描述，定義交易相關(guān)參量如表1所示.在表1中，為配置給中m個航班的n個接受時隙;當m=n=1，為簡單交易;當m，n≥2，為復雜交易;若m=n≥2，為平衡復雜交易問題;若m≠n≥2，為非平衡復雜交易問題.

表1 協(xié)同時隙再分配參量Table 1 CDM GDP slot assignment parameters

續(xù)表

啟動協(xié)同復雜交易過程時，首先AOC放棄時隙時便在中介市場上注冊發(fā)布交易信息表示預拍賣時隙，在內(nèi)擁有時隙AOC可請求交易;然后滿足條件的AOC檢測自身航班集中是否存在交易鏈，若有，則單獨出價請求，否則與其它需求者聯(lián)合出價.請求交易信息為:，表示用某時隙組成的時隙集交換中的所有時隙，追加補償金pr，由此在提供者和請求者的交易對象之間搭建“航班橋”，通過上移或下移橋梁航班實現(xiàn)交換;然后AOC根據(jù)設定目標，選取最佳請求者，進行效用分析，選出即時最佳者，駁回失敗請求;最后交易達成，AOC間評估需求及分析系統(tǒng)，交換時隙和追加補償金，更新信息、清理市場.

(1)內(nèi)部優(yōu)化效用分析.

內(nèi)部優(yōu)化決策定義為，航空公司在初次分配后，為達最佳配置，其會根據(jù)目標置換或取消航班以調(diào)整航班與時隙配置關(guān)系的行為.該行為產(chǎn)生的效益為內(nèi)部優(yōu)化效用，包括有形和無形效用，本文內(nèi)部優(yōu)化目標定為最小化航空公司的總延誤成本損失Da，約束條件為:任一航班須配置一個晚于其預計進場時間，且引起的延誤小于等于最大延誤時隙;任一時隙至多分配給一個航班;為確保延誤不會傳播到續(xù)航航班的后續(xù)飛機，制定續(xù)航航班最大延誤約束:tj-otai≤ΔTi，?fi∈F'a;決策變量為xij，yi，內(nèi)部優(yōu)化效用Ua為優(yōu)化前的總延誤成本損失D'a減去優(yōu)化后的總延誤成本損失Da.

初次分配按照“先到先分配”原則，沒有考慮最大延誤約束，當機場進場容量下降過多時，優(yōu)化可能會無解.

(2)外部優(yōu)化效用分析.

2.2 模型目標函數(shù)及約束條件

(1)目標函數(shù).

時隙再分配模型的目標函數(shù)由內(nèi)外部優(yōu)化效用兩部分組成，構(gòu)建時要求效用最優(yōu)，制定目標函數(shù)如下:

(2)有效性約束條件.

時隙再分配需滿足以下條件:續(xù)航航班配置最大延誤約束，延誤不會影響后續(xù)飛機;航班與所配置時隙一一對應，時隙晚于其預計進場時間，所引起的延誤小于等于最大延誤;由此有效性約束條件如下所示:

2.3 模型結(jié)構(gòu)

DCCEA模型中，每個子種群優(yōu)化一個參數(shù)，根據(jù)各點計算機的數(shù)量，將子種群分組至各同位機.各子種群間無直接通信，所有通信在子種群和中心服務器間進行，在每個同位機中，利用通過合作產(chǎn)生的候選解對檔案升級，同時各子種群不斷調(diào)整其代表［4］.

DCCEA在分布計算框架Paladin-DEC實現(xiàn).Paladin-DEC軟件由兩塊組成——服務區(qū)和工作區(qū)，二者通過RMI-IIOP相連.服務區(qū)作為信息中心和支持站，各個點的機器通過服務區(qū)識別身份或恢復其工作狀態(tài);工作區(qū)是各個點的機器以組為單位共同工作的地方，服務區(qū)內(nèi)具有三種不同的服務器——logon服務器、調(diào)度服務器和數(shù)據(jù)庫服務器，其中l(wèi)ogon服務器為每個注冊的同位機安排一個身份，當一個同位機退出并將其信息與調(diào)度服務器保持同步時，logon服務器將注銷該同位機的信息和身份.調(diào)度服務器選擇要執(zhí)行的任務并將同位機進行分組以執(zhí)行該任務.

每個同位機的具體工作過程如下:同位機首先通過發(fā)送合法E-mail地址給服務器以完成登錄，然后同位機組合在一起，等待服務器分派的任務.一旦同位機監(jiān)測到一個已分派任務，在從服務器中遠程下載類之前，它將從服務器提取相關(guān)信息，若已下載的類與Paladin-DEC系統(tǒng)一致，則計算開始，工作過程如圖1所示.

圖1 同位機的工作過程Fig.1 The working process of apposition machine

3 仿真實驗

設定某機場四家航空公司(A1、A2、A3、A4)在10:00～14:00執(zhí)行CDM-GDP，航班信息及機場時隙如表1中所示.航班分為重、中、輕型三類，其單位時間延誤運營成本分別為4 250元/小時、2 873元/小時和199元/小時;航班等級分為國內(nèi)、國際和要客三種等級，其每名旅客的平均延誤成本分別為50元/小時、100元/小時、100元/小時;補償金支付比率ra=0.53，ΔTi=90 min，航班均價、均凈利潤率及飛行小時分別設定為739元、2.35%、2小時.采用RBS算法進行初次時隙分配;A1和A2分別取消A14、A16和 A24、A25，進行再分配，全局優(yōu)化時令:yi=1;?fi∈ C;yi=0，?fi∈F/C.模型采用matlab2009編程構(gòu)建，采用cell工具把整個模型程序分步.記憶庫數(shù)據(jù)量為300，種群規(guī)模為300，迭代次數(shù) 300.DCCEA和Compression基于內(nèi)部優(yōu)化，DCCEA采用分步式仿真:(1)A2發(fā)布交易信息:［1 140］→A28［1 150，1 250］;(降低 A28的延誤，交易時隙1 140，在［1 150，1 250］內(nèi)擁有時隙的航空公司具有交易請求提出資格);(2)A1發(fā)布交易信息:［1 130］→A17［1 150，1 250］;(3)A1 發(fā)布交易信息:［1 120］→A18［1 200，1 300］.DCCEA 交易結(jié)果見表 2，黑體代表橋梁航班.效用分析對比如表3所示，DCCEA較Compression得到更多補償，總交換效用有所提高，有助于提高資源利用率;同時運行顯示，采用DCCEA、Comression及全局優(yōu)化三種方法模型運算時間分別為 t1= 0.313 86 s，t2=0.367 85 s，t3=0.473 24 s，由此采用 DCCEA 模型運行的效率相較Compression和全局優(yōu)化有了一定的提高.

表2 CDM GDP時隙分配Table 2 CDM GDP slot assignment

表3 再分配效用分析Table 3 Utility analysis generated by reassignment

4 研究結(jié)論

本文針對時隙再分配問題，提出了以效用來表示航空公司對交易的自主決策.利用DCCEA在處理分布式動態(tài)協(xié)同優(yōu)化問題上的優(yōu)勢，將其應用于協(xié)同時隙再次分配中，構(gòu)建基于動態(tài)時隙再次分配的分布式協(xié)同多目標進化算法模型.算例仿真表明，該模型能夠提高航空公司的交易效用，適用于動態(tài)的分布式空管協(xié)同決策環(huán)境中.在下一步研究中，可進一步納入實際空管因素，增強其應用價值.

［1］馬正平，崔德光.機場航班延誤優(yōu)化模型［J］.清華大學學報(自然科學版)，2004，44(4):474-477.［MA Z P，CUI D G.Optimizing airport flight delays［J］.Journal of Tsinghua University (Science And Technology)，2004，44(4):474-477.］

［2］胡明華，錢愛東，蘇蘭根.基于地面等待策略的航班時刻規(guī)劃方法［J］.航空學報，2001，23(3):262-264.［HU M H，QIAN A D，SU L G.Airlines time table programming method on ground holding strategy［J］.Acta Aeronautica et Astronautica Sinica，2001，23(3):262-264.］

［3］Vossen T，Ball M.Optimization and mediated bartering models for ground delay programs［J］.Naval Research Logistics，2006，53(1):75-90.

［4］雷德明，嚴新平.多目標智能優(yōu)化算法及其應用［M］.北京:科學出版社，2009:133-139.［LEI D M，YAN X P.Multiobjective intelligent optimization algorithm and its application［M］.Beijing Science Press，2009:133-139.］

［5］Capri S，Ignaccolo M，Genetic algorithms for solving the aircraft-sequencing problem: the introduction of departures into the dynamic model［J］.Journal of Air Transport Management，2004，10(5):345-351.

［6］Vossen T，Ball M.Optimization and mediated bartering models for ground delay programs ［J］.Naval Research Logistics，2006，53(1):75-90.

［7］余江，王大海，浦云.終端區(qū)起飛著陸的協(xié)同優(yōu)化［J］. 系統(tǒng)工程學報，2003，18(5):462-465.［YU J，WANG D H，PU Y.Coordinated optimization of terminal area landingand takeoff［J］.JournalofSystems Engineering，2003，18(5):462-465.］

［8］張洪海，胡明華.協(xié)同地面機場延誤時隙MAS動態(tài)協(xié)調(diào)交易［J］. 系統(tǒng)工程學報，2010，25(3):394-400.［ZHANG H H，HU M H.Dynamic coordination trading slot MAS-based in collaborative ground delay airport［J］.Journal of Systems Engineering，2010，25(3):394-400.］

［9］張洪海.機場終端區(qū)協(xié)同流量管理關(guān)鍵技術(shù)研究［D］.南京航空航天大學，2009.［ZHANG H H.The key technologies of collaborative flow management in airportterminalarea［J］. Nanjing University of Aeronautics and Astronautics，2009.］