王 湛，吳 術(shù)

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

1 引言

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

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

2 DCCEA模型構(gòu)建

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

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

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

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

續(xù)表

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

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

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

初次分配按照“先到先分配”原則，沒有考慮最大延誤約束，當(dāng)機(jī)場(chǎng)進(jìn)場(chǎng)容量下降過多時(shí)，優(yōu)化可能會(huì)無解.

(2)外部?jī)?yōu)化效用分析.

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

(1)目標(biāo)函數(shù).

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

(2)有效性約束條件.

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

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

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

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

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

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

3 仿真實(shí)驗(yàn)

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

表2 CDM GDP時(shí)隙分配Table 2 CDM GDP slot assignment

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

4 研究結(jié)論

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

［1］馬正平，崔德光.機(jī)場(chǎng)航班延誤優(yōu)化模型［J］.清華大學(xué)學(xué)報(bào)(自然科學(xué)版)，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］胡明華，錢愛東，蘇蘭根.基于地面等待策略的航班時(shí)刻規(guī)劃方法［J］.航空學(xué)報(bào)，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án)新平.多目標(biāo)智能優(yōu)化算法及其應(yīng)用［M］.北京:科學(xué)出版社，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)工程學(xué)報(bào)，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é)同地面機(jī)場(chǎng)延誤時(shí)隙MAS動(dòng)態(tài)協(xié)調(diào)交易［J］. 系統(tǒng)工程學(xué)報(bào)，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］張洪海.機(jī)場(chǎng)終端區(qū)協(xié)同流量管理關(guān)鍵技術(shù)研究［D］.南京航空航天大學(xué)，2009.［ZHANG H H.The key technologies of collaborative flow management in airportterminalarea［J］. Nanjing University of Aeronautics and Astronautics，2009.］