基于時(shí)變小世界模型的航空網(wǎng)優(yōu)化評(píng)估?

韓定定 姚清清 陳趣 錢(qián)江海

1)(華東師范大學(xué)信息科學(xué)技術(shù)學(xué)院,上海市多維度信息處理重點(diǎn)實(shí)驗(yàn)室,上海 200241)

2)(上海電力學(xué)院數(shù)理學(xué)院,上海 200090)

(2017年5月12日收到;2017年7月4日收到修改稿)

1 引 言

航空網(wǎng)絡(luò)的設(shè)計(jì)是一個(gè)在成本和旅客滿意度之間進(jìn)行平衡的復(fù)雜優(yōu)化問(wèn)題,決定了航空運(yùn)輸?shù)男?航空公司追求低成本、高收益,總是希望通過(guò)合理的網(wǎng)絡(luò)優(yōu)化,用更少的航班來(lái)滿足市場(chǎng)需求;另一方面,要提高旅客的出行滿意度搶占市場(chǎng),必須盡可能地縮短旅客的飛行時(shí)間和轉(zhuǎn)機(jī)次數(shù),但會(huì)增加航空公司的建設(shè)、運(yùn)營(yíng)成本.兩者的利益沖突導(dǎo)致了航線網(wǎng)絡(luò)規(guī)劃和航班計(jì)劃編制的復(fù)雜性.航線網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計(jì)是航空公司航班運(yùn)營(yíng)的基礎(chǔ).傳統(tǒng)的航空網(wǎng)絡(luò)優(yōu)化,通常以整個(gè)航空公司的利潤(rùn)最大化或成本最小化作為優(yōu)化目標(biāo)函數(shù).根據(jù)實(shí)際的座位數(shù)、飛機(jī)利用率、旅客流量、市場(chǎng)份額以及航班頻率整數(shù)性等約束關(guān)系建立混合整數(shù)規(guī)劃模型,求解最優(yōu)航線結(jié)構(gòu)及航班頻率[1?5].由于實(shí)際的航線還要考慮例如機(jī)型指派、機(jī)組調(diào)配、燃油費(fèi)用等現(xiàn)實(shí)問(wèn)題,盡管上述優(yōu)化模型能夠較為準(zhǔn)確地描述網(wǎng)絡(luò)優(yōu)化的本質(zhì),但在實(shí)際應(yīng)用中仍存在極大的局限.特別地,此類問(wèn)題的求解往往是NP-hard問(wèn)題,對(duì)于大規(guī)模網(wǎng)絡(luò)的優(yōu)化問(wèn)題難以給出精確的最優(yōu)解.

近年來(lái)網(wǎng)絡(luò)科學(xué)的興起為研究航空網(wǎng)這一類開(kāi)放的復(fù)雜系統(tǒng)提供了一個(gè)嶄新的視角.將機(jī)場(chǎng)視為一個(gè)節(jié)點(diǎn),兩個(gè)機(jī)場(chǎng)之間的航線視為連邊,每個(gè)航線上的運(yùn)量或者航班頻次視為邊權(quán),可以將航空運(yùn)輸系統(tǒng)抽象成靜態(tài)的復(fù)雜加權(quán)網(wǎng)絡(luò).對(duì)世界、北美、歐洲以及中國(guó)等眾多航空網(wǎng)絡(luò)的實(shí)證研究已經(jīng)證實(shí):航空網(wǎng)是典型的具有無(wú)標(biāo)度特征的空間小世界網(wǎng)絡(luò)[6?13].網(wǎng)絡(luò)功能和效率取決于它的拓?fù)?因此根據(jù)航空網(wǎng)的統(tǒng)計(jì)特征構(gòu)建的簡(jiǎn)化模型是討論空間網(wǎng)絡(luò)優(yōu)化問(wèn)題的有力工具.通過(guò)在節(jié)點(diǎn)間合理地添加長(zhǎng)邊可以有效改善網(wǎng)絡(luò)的全局傳輸效率[14?16].以Kleinberg為代表的學(xué)者詳細(xì)討論了空間小世界網(wǎng)絡(luò)的最優(yōu)導(dǎo)航問(wèn)題,揭示了空間結(jié)構(gòu)的變化對(duì)網(wǎng)絡(luò)平均最短路徑的影響[17?19].由于在航空網(wǎng)等現(xiàn)實(shí)交通系統(tǒng)的建設(shè)中,開(kāi)辟一條新的線路所耗費(fèi)的成本往往正比于其地理距離.文獻(xiàn)[20—23]研究了在有限的成本預(yù)算下,如何通過(guò)合理地配置捷徑來(lái)實(shí)現(xiàn)成本和導(dǎo)航效率的平衡.而Gastner和Newman[24]則將構(gòu)網(wǎng)成本T與旅行成本Z作為構(gòu)建空間網(wǎng)絡(luò)的兩個(gè)主要考慮因素,以成本函數(shù)E=T+γZ最小化作為優(yōu)化目標(biāo),來(lái)求解網(wǎng)絡(luò)的最優(yōu)拓?fù)?上述研究基于對(duì)網(wǎng)絡(luò)空間結(jié)構(gòu)的考慮,為現(xiàn)實(shí)航空網(wǎng)絡(luò)的優(yōu)化設(shè)計(jì)提供了重要的理論支持.

時(shí)變性是航空網(wǎng)絡(luò)的另一個(gè)重要特征.長(zhǎng)期以來(lái),對(duì)航空網(wǎng)絡(luò)的研究通常假設(shè)網(wǎng)絡(luò)本身具有相對(duì)的時(shí)空穩(wěn)定性,而忽視了航班飛行計(jì)劃的時(shí)序?qū)?shí)際旅行時(shí)間的影響.事實(shí)上,每條航線上的航班根據(jù)事先擬定的時(shí)刻表運(yùn)行,由同一時(shí)刻所有處于飛行狀態(tài)的航班構(gòu)成的瞬時(shí)航班網(wǎng)絡(luò)是動(dòng)態(tài)變化的.作為航空運(yùn)輸?shù)妮d體,航班網(wǎng)絡(luò)才是決定實(shí)際運(yùn)輸效率的關(guān)鍵,而航線拓?fù)渥鳛楹桨嗑W(wǎng)絡(luò)的聚合,并不能真實(shí)反映航空網(wǎng)絡(luò)的運(yùn)輸功能.經(jīng)過(guò)高度優(yōu)化設(shè)計(jì)的航線結(jié)構(gòu)必須輔以高效的航班計(jì)劃,才能充分發(fā)揮網(wǎng)絡(luò)空間結(jié)構(gòu)的便利性.近來(lái)針對(duì)時(shí)變網(wǎng)絡(luò)的研究證實(shí),在時(shí)變條件下,無(wú)論是網(wǎng)絡(luò)連接度、故障魯棒性等基本屬性,還是傳播閾值、最優(yōu)導(dǎo)航結(jié)構(gòu)等動(dòng)力學(xué)行為都明顯不同于基于靜態(tài)網(wǎng)絡(luò)的傳統(tǒng)認(rèn)知[25?30].另一方面,出于成本的考慮,航班計(jì)劃的編制充分考慮了航距這一空間因素的影響,因此航空網(wǎng)的空間結(jié)構(gòu)和連邊動(dòng)力學(xué)之間具有潛在的時(shí)空關(guān)聯(lián)特征.準(zhǔn)確把握航空網(wǎng)絡(luò)的時(shí)變行為,考慮航線結(jié)構(gòu)和航班計(jì)劃的綜合作用,并據(jù)此實(shí)現(xiàn)網(wǎng)絡(luò)的整體優(yōu)化設(shè)計(jì),將有助于航空公司構(gòu)建具有競(jìng)爭(zhēng)力的運(yùn)營(yíng)結(jié)構(gòu),并實(shí)現(xiàn)運(yùn)輸資源的優(yōu)化配置.

本文首先實(shí)證航空網(wǎng)的時(shí)空關(guān)聯(lián)行為,從連邊活躍度驅(qū)動(dòng)的角度構(gòu)建一類契合航空網(wǎng)特征的時(shí)變空間小世界網(wǎng)絡(luò),討論時(shí)空耦合強(qiáng)度對(duì)網(wǎng)絡(luò)最優(yōu)結(jié)構(gòu)指數(shù)的影響;繼而以成本最小化作為主要的優(yōu)化目標(biāo),提出一種可以快速評(píng)估航線結(jié)構(gòu)優(yōu)化情況的方法;據(jù)此,可以根據(jù)航線客流的分布情況,快速推算出航線網(wǎng)絡(luò)的最優(yōu)拓?fù)浼捌湎鄳?yīng)的航班頻率分布.

2 航空網(wǎng)的時(shí)空關(guān)聯(lián)特征

作為一個(gè)典型的二維空間網(wǎng)絡(luò),航空網(wǎng)絡(luò)中的節(jié)點(diǎn),即機(jī)場(chǎng),都具有明確的地理坐標(biāo).每條航線的航距也是網(wǎng)絡(luò)設(shè)計(jì)時(shí)一個(gè)重要的考慮因素.本文首先從Open-Flights項(xiàng)目(http://open fl ights.org/data.html)中獲取了所有機(jī)場(chǎng)的經(jīng)緯度信息,并由下式計(jì)算每條航線的理論航距rij:

其中R為地球半徑;(xi,yi),(xj,yj)分別為航線兩端的機(jī)場(chǎng)i,j的經(jīng)緯度.本節(jié)以英國(guó)航空公司和奧地利航空公司這兩個(gè)特定航空網(wǎng)絡(luò)為例,討論航班密度與航線結(jié)構(gòu)之間的關(guān)系.具體的航班信息可從官方網(wǎng)站(http://www.britishairways.com,http://www.austrian.com)公布的航班時(shí)刻表中提取.在同一條航線上,一天內(nèi)可能有多個(gè)起降航班,因此在特定的時(shí)間尺度下,如每天,所有直飛的航班和通航機(jī)場(chǎng)構(gòu)成了實(shí)際的航空網(wǎng)絡(luò),且該網(wǎng)絡(luò)具有時(shí)變特征.再者,一條航線上累積飛行的航班數(shù)量能夠有效反映本航線的繁忙程度.大量實(shí)證研究已經(jīng)證實(shí),航空網(wǎng)絡(luò)具有異質(zhì)特征,各個(gè)機(jī)場(chǎng)的吞吐能力和重要性存在極大的差異[6,9].每條航線的航距作為運(yùn)輸成本的重要考量因素之一,也會(huì)對(duì)航班密度產(chǎn)生影響.以英國(guó)航空網(wǎng)為例,選定網(wǎng)絡(luò)中的樞紐節(jié)點(diǎn)LHR(London Heathrow)機(jī)場(chǎng)以及與其有航班聯(lián)系且度值k=3的其他機(jī)場(chǎng)(Dublin(DUB)機(jī)場(chǎng)、Frankfurt(FRA)機(jī)場(chǎng)、Zürich(ZRH)機(jī)場(chǎng)、Prague(PRG)機(jī)場(chǎng)、Ras Al Khaimah(RAK)機(jī)場(chǎng)),從表1中不難看出,空間距離與航班密度之間確實(shí)存在某種約束,航距越大,航線上的航班密度相應(yīng)較小,這也符合人們的直觀感受.短程航線的設(shè)計(jì)往往以通勤為目標(biāo),因此這類航班通常采用一些支線小型飛機(jī),幾乎每日都有,非常穩(wěn)定.而長(zhǎng)程航線的設(shè)計(jì)主要是為了維系重要城市之間的經(jīng)濟(jì)、社會(huì)往來(lái),但運(yùn)行成本較高,因此通常采用一些大型干線飛機(jī),但班次相對(duì)較少,每日航班差異較大,也更容易受到節(jié)假日等外在因素的影響.

表1 英國(guó)航空公司航距與一周累積航次的關(guān)系Table 1.Dependence of the weekly cumulated fl ights on route distances in British Airways.

為了進(jìn)一步確定航班密度(時(shí)間維度)和航線距離(空間維度)的關(guān)聯(lián)特征,剔除網(wǎng)絡(luò)的異質(zhì)性對(duì)航班頻率的影響,定義歸一化航班密度為nl=Nl/(kikj),其中l(wèi)是機(jī)場(chǎng)i和j之間的航線,而Nl為一周內(nèi)該航線上的累積航班數(shù);ki,kj分別為機(jī)場(chǎng)i和j的度值.如圖1所示,以歸一化航班密度nl作為縱軸,航線距離為橫軸,藍(lán)點(diǎn)即為各個(gè)航班信息在雙對(duì)數(shù)坐標(biāo)圖中的顯示.選取合適的航距范圍內(nèi)的點(diǎn)取其平均值,用紅點(diǎn)表示,并用直線擬合紅色的平均值點(diǎn).從圖1不難看出,無(wú)論是英國(guó)航空還是奧地利航空,歸一化航班密度均隨航距近似冪律衰減,可得出nl～(rl)?0.5,表明現(xiàn)實(shí)航空網(wǎng)絡(luò)的確存在時(shí)空上的關(guān)聯(lián).由于航班密度正是該航線活躍性的體現(xiàn),因此可將航空網(wǎng)絡(luò)視為一個(gè)經(jīng)過(guò)高度優(yōu)化設(shè)計(jì)、由預(yù)設(shè)的活躍度驅(qū)動(dòng)的時(shí)變空間網(wǎng)絡(luò).這一時(shí)空耦合關(guān)系的發(fā)現(xiàn)也為網(wǎng)絡(luò)的優(yōu)化設(shè)計(jì)提供了新的方向.

圖1 航空網(wǎng)的時(shí)空耦合特征 (a)英國(guó)航空;(b)奧地利航空Fig.1.The coupling property between temporal and spatial factors in airline networks:(a)British airlines;(b)Austrian airlines.

3 時(shí)變空間小世界網(wǎng)絡(luò)的優(yōu)化結(jié)構(gòu)

最優(yōu)導(dǎo)航結(jié)構(gòu)是空間小世界網(wǎng)絡(luò)研究的一個(gè)重要分支,以Kleinberg為代表的學(xué)者對(duì)此進(jìn)行過(guò)深入的探討[17?23].本節(jié)運(yùn)用一種活躍度驅(qū)動(dòng)的時(shí)變空間小世界模型[29],討論航空網(wǎng)在時(shí)變條件下的優(yōu)化空間結(jié)構(gòu).N個(gè)節(jié)點(diǎn)分布在d維規(guī)則網(wǎng)格上,每個(gè)節(jié)點(diǎn)與其最近的2d個(gè)鄰居節(jié)點(diǎn)相連.此外,每個(gè)節(jié)點(diǎn)額外擁有一條長(zhǎng)程連邊,節(jié)點(diǎn)i與節(jié)點(diǎn)j通過(guò)長(zhǎng)邊相連的概率為

其中rij=|ri?rj|為節(jié)點(diǎn)間的Manhattan距離,而α為結(jié)構(gòu)指數(shù),其值越大,則長(zhǎng)程連邊的平均距離越小.此時(shí)網(wǎng)絡(luò)中的長(zhǎng)邊分布p(r)～r?δ,δ=α?d+1.另一方面,由上節(jié)對(duì)于航空網(wǎng)絡(luò)時(shí)空分布特征的討論,假設(shè)動(dòng)態(tài)的連邊行為是由其內(nèi)在的活躍度驅(qū)動(dòng)的,且每條長(zhǎng)邊lij的活躍度τij與其地理距離rij相關(guān),滿足其中參數(shù)C為連邊活躍度和地理距離之間的時(shí)空耦合強(qiáng)度.

具體的建模及網(wǎng)絡(luò)演化過(guò)程如下.

1)將N個(gè)節(jié)點(diǎn)均勻分布在一個(gè)L×L的二維周期性網(wǎng)格上.網(wǎng)絡(luò)中最近鄰節(jié)點(diǎn)間兩兩相連,從而保證每個(gè)節(jié)點(diǎn)都是可達(dá)的.

3)為每條長(zhǎng)邊賦予活躍度τij～r?Cij.在任意時(shí)刻t,網(wǎng)絡(luò)中的短邊始終活躍,而長(zhǎng)邊以概率τ活躍,所有短邊和活躍的長(zhǎng)程連邊共同構(gòu)成當(dāng)前時(shí)刻的瞬時(shí)網(wǎng)絡(luò)Gt.

圖2給出了上述模型的時(shí)變過(guò)程.不難看出,距離越長(zhǎng)的連邊狀態(tài)轉(zhuǎn)換越頻繁,而距離較短的連邊相對(duì)穩(wěn)定,符合航空網(wǎng)的時(shí)變特征.在此類時(shí)變空間網(wǎng)絡(luò)中,空間結(jié)構(gòu)和連邊動(dòng)力學(xué)的共同作用是決定時(shí)變網(wǎng)絡(luò)運(yùn)輸效率的關(guān)鍵.在靜態(tài)網(wǎng)絡(luò)中,大量長(zhǎng)程連邊的存在能夠有效提高網(wǎng)絡(luò)的傳輸效率.但在時(shí)變條件下,空間約束使得距離越長(zhǎng)的連邊其活躍的概率往往越低,從而影響網(wǎng)絡(luò)中的傳輸過(guò)程.這種矛盾意味著在網(wǎng)絡(luò)結(jié)構(gòu)的設(shè)計(jì)優(yōu)化中需要有效平衡時(shí)變和空間效應(yīng)的影響.而網(wǎng)絡(luò)本身也必然存在一個(gè)最優(yōu)的空間結(jié)構(gòu)來(lái)平衡捷徑的幾何長(zhǎng)度和活躍度之間的矛盾.

圖2 時(shí)變空間小世界模型示意圖(圖中長(zhǎng)程連邊的粗細(xì)表示活躍度的大小)Fig.2.An illustration of the time-varying spatial small-world networks.The activity of each long-range connection is denoted by its width.

一般來(lái)說(shuō),網(wǎng)絡(luò)的全局傳輸效率可以通過(guò)網(wǎng)絡(luò)的平均最短路徑長(zhǎng)度〈l〉來(lái)衡量.而在拓?fù)鋾r(shí)變的情況下,航空網(wǎng)絡(luò)中的時(shí)變最短路徑長(zhǎng)度可以用從起點(diǎn)出發(fā)經(jīng)過(guò)相關(guān)路徑后到達(dá)目標(biāo)節(jié)點(diǎn)所需的最短的時(shí)間來(lái)衡量.因此,當(dāng)網(wǎng)絡(luò)整體的平均時(shí)變最短路徑長(zhǎng)度〈T〉最小時(shí)所對(duì)應(yīng)的空間結(jié)構(gòu)就是時(shí)變條件下的優(yōu)化結(jié)果.這一過(guò)程可以通過(guò)Monte Carlo方法進(jìn)行模擬,由于變量α,C取值不同,平均時(shí)變最短路徑〈T〉也會(huì)隨之變化.對(duì)于每一個(gè)確定的耦合強(qiáng)度C,希望能找到使〈T〉最小的α,該α即為對(duì)應(yīng)耦合強(qiáng)度C下的αopt.易知當(dāng)C=0時(shí),每條邊的活躍度τ=1,網(wǎng)絡(luò)即轉(zhuǎn)化為Kleinberg靜態(tài)網(wǎng)絡(luò),此時(shí)α越小,遠(yuǎn)距離的長(zhǎng)程連邊越多,所以αopt=0;當(dāng)時(shí)空耦合強(qiáng)度0＜C＜2時(shí),αopt約為2;當(dāng)C?2時(shí),長(zhǎng)程連邊的活躍度非常小,相當(dāng)于一直處于斷開(kāi)狀態(tài),因而αopt趨于無(wú)窮.選定C為0.5,觀察隨著網(wǎng)絡(luò)規(guī)模變化αopt的變化情況,結(jié)果顯示αopt穩(wěn)定于2左右,因而具有很好的魯棒性.結(jié)構(gòu)指數(shù)δ與α是簡(jiǎn)單的線性關(guān)系,且通過(guò)Monte Carlo模擬發(fā)現(xiàn)只有當(dāng)0＜C＜2時(shí),該網(wǎng)絡(luò)結(jié)構(gòu)才符合小世界模型.所以結(jié)合航空網(wǎng)絡(luò)屬于小世界網(wǎng)絡(luò)的特點(diǎn),主要對(duì)處于該范圍內(nèi)的C和對(duì)應(yīng)δopt進(jìn)行分析.結(jié)果如圖3所示,最優(yōu)結(jié)構(gòu)指數(shù)δopt隨不斷加深的空間約束以對(duì)數(shù)形式δopt～log(C)緩慢增長(zhǎng).時(shí)空耦合強(qiáng)度和全局最優(yōu)結(jié)構(gòu)指數(shù)之間這種惟一的約束關(guān)系為時(shí)變航空網(wǎng)絡(luò)的優(yōu)化設(shè)計(jì)提供了一個(gè)嶄新的方向.若確定了耦合強(qiáng)度C,便能快速知道最優(yōu)結(jié)構(gòu)指數(shù)δopt,為航空網(wǎng)絡(luò)的航線的添加調(diào)整提供建議.

圖3 全局最優(yōu)結(jié)構(gòu)指數(shù)δopt與時(shí)空耦合強(qiáng)度C的關(guān)系Fig.3.The relationship between the global optimal structural exponent δoptand temporal-spatial coupling strength C.

4 基于時(shí)變網(wǎng)絡(luò)的航空網(wǎng)優(yōu)化評(píng)估方法

從工程優(yōu)化的角度來(lái)看,航空網(wǎng)絡(luò)的設(shè)計(jì)是航空公司的利潤(rùn)和旅客的需求之間矛盾的平衡.對(duì)于航空公司而言,過(guò)高的航班頻率意味著高運(yùn)行成本、低客座率.而對(duì)旅客而言,航班間隔過(guò)大使得等待時(shí)間增加.因此旅客的等待成本Cp和航班的運(yùn)行成本Cr是航空計(jì)劃編制中需要考慮的兩個(gè)主要因素[2].本節(jié)從成本最小化的角度出發(fā),應(yīng)用時(shí)變條件下最優(yōu)導(dǎo)航結(jié)構(gòu)的相關(guān)結(jié)論,提出一種航線結(jié)構(gòu)的優(yōu)化評(píng)估方法.

首先,假設(shè)航距為r的航線在一個(gè)周期T內(nèi)航班的班次頻率為f,航班的時(shí)間間隔τ=T/f.兩個(gè)城市i和j之間若存在航線,則它們之間必然存在某種經(jīng)濟(jì)或生活上的聯(lián)系,從而驅(qū)動(dòng)了人們?cè)趦蓚€(gè)城市之間的流動(dòng).一般來(lái)說(shuō),城市越發(fā)達(dá)、人口越多,則城市的吸引力越強(qiáng),城市之間的人流量越大.相反,若兩個(gè)城市距離非常遠(yuǎn),考慮到出行的成本、時(shí)間等因素,人流量會(huì)相對(duì)減少.因此,兩個(gè)機(jī)場(chǎng)之間的客流Iij通?？捎靡降男问奖碚鱗31?36],即

其中Pi,Pj分別為兩個(gè)機(jī)場(chǎng)所在城市的人口數(shù);k和λ為一個(gè)常數(shù).因此假設(shè)距離為r的航線,其客流正比于r?λ,而該航線上旅客的總等待成本取決于航班的時(shí)間間隔和客流量,即

另一方面,單個(gè)航班的運(yùn)輸成本一般正比于該航線的航距r,因此總的運(yùn)輸成本等于航班的數(shù)量與單位運(yùn)輸成本之積,即

因此對(duì)于航距為r的航班而言,其總體運(yùn)行成本為

其中a,b為相關(guān)的成本系數(shù).通過(guò)求解總成本的最小值,可以得出最佳的航班時(shí)間間隔.令dCOST/dτ=0,可以解得所以最佳航班頻率滿足:

考慮到實(shí)際的航空網(wǎng)絡(luò)中航班頻率與航線距離之間服從冪律耦合關(guān)系:

聯(lián)立(6)和(7)式可得,時(shí)空耦合參數(shù)C與客流分布指數(shù)λ之間滿足約束關(guān)系:

由(8)式和圖3中給出的δopt與C的約束關(guān)系,可以確定最優(yōu)的δ值,從而推得實(shí)際航線的距離分布,進(jìn)而對(duì)各航空公司的航線安排是否合理做出評(píng)估.由于客流分布指數(shù)λ的值可以通過(guò)歷史數(shù)據(jù)進(jìn)行估計(jì),并根據(jù)當(dāng)前客流量實(shí)時(shí)調(diào)整,可以不斷計(jì)算相應(yīng)的C并確定最優(yōu)的結(jié)構(gòu)指數(shù)δ.因此評(píng)估是動(dòng)態(tài)的,能反映出航空網(wǎng)絡(luò)的發(fā)展是否在不斷優(yōu)化,為航空網(wǎng)絡(luò)的結(jié)構(gòu)調(diào)整提供參考.盡管這一框架經(jīng)過(guò)高度簡(jiǎn)化,將所有航距為r的航班做了同質(zhì)化處理,忽略了很多細(xì)節(jié)上的考慮,但是作為工程優(yōu)化的前導(dǎo)步驟,可以為航線規(guī)劃提供一些理論上的指導(dǎo),而且這一方法同樣適用于其他交通輸運(yùn)系統(tǒng)的整體規(guī)劃.

使用中國(guó)航空網(wǎng)絡(luò)的相關(guān)數(shù)據(jù)來(lái)對(duì)上述模型進(jìn)行實(shí)證研究.首先從歷年的《中國(guó)交通年鑒》中獲取2001—2010十年的民航國(guó)內(nèi)主要航線運(yùn)輸完成情況,選用其中的航班次數(shù)和客流量數(shù)據(jù).從《中國(guó)城市年鑒》中獲取了全國(guó)各大機(jī)場(chǎng)所在城市市轄區(qū)2001—2010年的人口數(shù)量.最后查詢得到161個(gè)機(jī)場(chǎng)的經(jīng)緯度,根據(jù)(1)式可以計(jì)算得到兩兩機(jī)場(chǎng)間的距離.

以2010年為例,將2010年國(guó)內(nèi)主要航線兩兩城市間的客流量、各機(jī)場(chǎng)城市的人口數(shù)量和航線距離代入(2)式,以Iij/(pipj)為縱坐標(biāo),航距為橫坐標(biāo),在雙對(duì)數(shù)坐標(biāo)中顯示各點(diǎn),計(jì)算一定航距范圍內(nèi)客流量平均值,擬合數(shù)據(jù)得到λ=0.4225.由C=(1+λ)/2,即可得到C=0.71125,再通過(guò)圖3中C和δopt的一一對(duì)應(yīng)關(guān)系就可以快速推得δopt=1.08左右.

圖4 2010年客流量分布與航距關(guān)系Fig.4.The relationship between the passenger fl ow and distance.

根據(jù)2010年主要航線航班頻次與相應(yīng)機(jī)場(chǎng)間的距離,按上節(jié)方法做歸一化處理后,在雙對(duì)數(shù)坐標(biāo)中畫(huà)圖,同樣取平均值進(jìn)行擬合得到圖5.由圖5可以看出航班頻率與航線距離呈冪律衰減,且時(shí)空耦合系數(shù)C=0.6928.

圖5 2010年航班頻次與航距關(guān)系Fig.5.The relationship between fl ight frequency and distance.

圖6 2001–2010年實(shí)證數(shù)據(jù)結(jié)果分析Fig.6.The empirical results based on real data during 2001–2010.

由圖4和圖5可以發(fā)現(xiàn)由2010年客流量預(yù)測(cè)得到的時(shí)空耦合參數(shù)C與實(shí)際得到的C分別為0.71125和0.6928,相差0.01845.用同樣的方法擬合2001—2009年的數(shù)據(jù),并計(jì)算預(yù)測(cè)與實(shí)際的差值得到圖6.

由于該模型主要目的是快速評(píng)估動(dòng)態(tài)變化的航空網(wǎng)絡(luò),驗(yàn)證航空網(wǎng)絡(luò)的發(fā)展是否不斷優(yōu)化,作為工程優(yōu)化的前導(dǎo)步驟,因而簡(jiǎn)化了復(fù)雜的細(xì)節(jié)問(wèn)題,只考慮了一些主要影響因素,比如模型推導(dǎo)過(guò)程中,客流量表示為基礎(chǔ)的引力模型,影響因素只有兩個(gè)城市的人口數(shù)和距離,不考慮城市經(jīng)濟(jì)發(fā)展情況、居民收入水平等;在航班成本最優(yōu)化問(wèn)題中,航班成本只由等待成本和運(yùn)輸成本兩部分構(gòu)成,其中等待成本的影響因素是客流量和航班間隔,運(yùn)輸成本的影響因素為航距和航班頻率,忽略了機(jī)型、上座率等實(shí)際因素.所以實(shí)際數(shù)據(jù)和根據(jù)優(yōu)化模型快速推算的數(shù)值存在一定的差距.但從圖6可以非常直觀地看到兩者之間基本一致,2001年、2002年的誤差相對(duì)而言較大,但隨著機(jī)場(chǎng)建設(shè)完善,航空網(wǎng)絡(luò)的優(yōu)化,差距呈逐年遞減并趨于穩(wěn)定的良好趨勢(shì),從而說(shuō)明該優(yōu)化模型和評(píng)估方法是合理可行的.航空公司可根據(jù)客流量的變化情況來(lái)計(jì)算出C以及對(duì)應(yīng)的最優(yōu)結(jié)構(gòu)指數(shù),據(jù)此對(duì)現(xiàn)有的航線做出相應(yīng)的調(diào)整,適當(dāng)?shù)脑鰷p相關(guān)航線,以實(shí)現(xiàn)成本降低、利潤(rùn)提高以及旅客滿意度的提升.

5 結(jié) 論

基于空間優(yōu)化網(wǎng)絡(luò)模型和航班工程優(yōu)化的思想,本文應(yīng)用時(shí)變條件下最優(yōu)導(dǎo)航結(jié)構(gòu)的相關(guān)結(jié)論,提出了快速評(píng)估航線結(jié)構(gòu)優(yōu)化情況的方法.考慮到運(yùn)輸成本與航距(拓?fù)涞目臻g性)密切相關(guān),而等待成本主要取決于客座率和航班頻率(拓?fù)涞臅r(shí)變性)的設(shè)置,通過(guò)將最小化運(yùn)行總成本作為主要的優(yōu)化目標(biāo),可以推得時(shí)空耦合強(qiáng)度C與客流分布指數(shù)λ之間的關(guān)聯(lián).由于時(shí)變航空系統(tǒng)的C值還與網(wǎng)絡(luò)的最優(yōu)導(dǎo)航結(jié)構(gòu)δopt存在惟一的約束關(guān)系,因此可以根據(jù)網(wǎng)絡(luò)客流分布情況快速推算出航線網(wǎng)絡(luò)的最優(yōu)拓?fù)浼跋鄳?yīng)的航班頻率分布.這一思想可以避免傳統(tǒng)優(yōu)化方法求解問(wèn)題的計(jì)算復(fù)雜性,能夠幫助航空公司動(dòng)態(tài)評(píng)估所開(kāi)設(shè)航線的合理性,分析航線網(wǎng)絡(luò)的是否在不斷優(yōu)化,為之后的航線增減與調(diào)整提供建議.

[1]Brueckner J K 2004J.Ind.Econ.52 291

[2]Li F J,Wang L P,Liu Z Y 2007Comput.Eng.33 279(in Chinese)[李福娟,王魯平,劉仲英2007計(jì)算機(jī)工程33 279]

[3]Zheng X,Yu T 2014IEEE Workshop on Advanced ResearchandTechnologyinIndustryApplications(WARTIA)Ottawa,Canada,September 29–30,2014 pp1135–1137

[4]Dobson G,Lederer P J 1993Transp.Sci.27 281

[5]Wang W,Wang C J 2013Acta Geogr.Sin.68 762(in Chinese)[王偉,王成金 2013地理學(xué)報(bào)68 762]

[6]Gautreau A,Barrat A,Barthelemy M 2009Proc.Natl.Acad.Sci.USA106 8847

[7]Qian J H,Han D D,Ma Y G 2011Acta Phys.Sin.60 098901(in Chinese)[錢(qián)江海,韓定定,馬余剛2011物理學(xué)報(bào)60 098901]

[8]Han D D,Qian J H,Liu J G 2009Physica A388 71

[9]Barrat A,Barthelemy M,Pastor-Satorras R,Vespignani A 2004Proc.Natl.Acad.Sci.USA101 3747

[10]Guimera R,Mossa S,Turtschi A,Amaral L A N 2005Proc.Natl.Acad.Sci.USA102 7794

[11]Liu H K,Zhou T 2007Acta Phys.Sin.56 106(in Chinese)[劉宏鯤,周濤 2007物理學(xué)報(bào) 56 106]

[12]Luo Y Q,Tang J H,Zhao Z L,Zhu Y W,Dong X J 2014Complex Systems and Complexity Science11 4(in Chinese)[羅赟騫,湯錦輝,趙鐘磊,朱永文,董相均2014復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)11 4]

[13]Lordan O,Sallan J M,Simo P 2014J.Transp.Geogr.37 112

[14]Moukarzel C F,de Menezes M A 2002Phys.Rev.E65 056709

[15]Kosmidis K,Havlin S,Bunde A 2008Europhys.Lett.82 48005

[16]Yang H,Nie Y C,Zeng A,Fan Y,Hu Y Q,Di Z R 2010Europhys.Lett.89 58002

[17]Kleinberg J M 2000Nature406 845

[18]Kleinberg J M 2000Proceedings of the Thirty-Second Annual ACM Symposium on Theory of ComputingPortland,USA,May 21–23,2000 pp163–170

[19]Boguna M,Krioukov D,Claffy K C 2009Nat.Phys.5 74

[20]Pajevic S,Plenz D 2011Nat.Phys.8 1

[21]Milo R,Shenorr S,Itzkovitz S,Kashtan N,Chklovskii D,Alon U 2002Science298 824

[22]Li G,Reis S,Moreira A,Havlin S,Stanley H E,Andrade Jr J 2013Phys.Rev.E87 042810

[23]Li Y,Dou F L,Fan Y,Di Z R 2012Acta Phys.Sin.61 228902(in Chinese)[黎勇,鈄斐玲,樊瑛,狄增如 2012物理學(xué)報(bào)61 228902]

[24]Gastner M T,Newman M 2006Phys.Rev.E74 016117

[25]Holme P,Saram?ki J 2012Phys.Rep.519 97

[26]Kim H,Anderson R 2012Phys.Rev.E85 026107

[27]Starnini M,Baronchelli A,Barrat A,Pastor-Satorras R 2012Phys.Rev.E85 056115

[28]Trajanovski S,Scellato S,Leontiadis I 2012Phys.Rev.E85 066105

[29]Chen Q,Qian J H,Zhu L,Han D D 2016Phys.Rev.E93 032219

[30]Chen Q,Qian J H,Zhu L,Han D D 2016J.Appl.Anal.Comput.6 30

[31]Wojahn O W 2001Transport Res.E37 267

[32]Grosche T,Rothlauf F,Heinzl A 2007J.Air Transp.Manag.13 175

[33]Qian J H,Han D D 2009Physica A388 4248

[34]Jung W S,Wang F,Stanley H E 2008Europhys.Lett.81 48005

[35]Qian J H,Han D D 2009Acta Phys.Sin.58 3028(in Chinese)[錢(qián)江海,韓定定 2009物理學(xué)報(bào) 58 3028]

[36]N?mmik A,Kukemelk S 2016Aviation20 32