航空公司選擇樞紐機(jī)場的魯棒優(yōu)化方法_姜濤

1、文章編號:10014098(2006)06001305航空公司選擇樞紐機(jī)場的魯棒優(yōu)化方法姜濤朱金福(南京航空航天大學(xué)民航學(xué)院江蘇南京210016)摘要:航空公司構(gòu)建自己的中樞輻射航線網(wǎng)絡(luò)可以事先對n個備選機(jī)場作為樞紐機(jī)場能夠帶來的效益值分別作出預(yù)測然后從中選擇p個(p給定)效益值最大的機(jī)場作為自己的樞紐機(jī)場。由于事物未來發(fā)展的不確定性對于效益值的分析預(yù)測往往與實際情景有較大的偏差。為了規(guī)避風(fēng)險一種比較穩(wěn)妥的方法是對該效益值可能的范圍(概

2、率分布未知)做出預(yù)估再從中選擇p個樞紐。利用魯棒優(yōu)化的方法對這樣的問題進(jìn)行解決并將已有的魯棒優(yōu)化算法復(fù)雜性O(shè)((minpnp)2n)加以改進(jìn)在原算法的基礎(chǔ)上將算法復(fù)雜性減弱到O((minpnp)n)給出了解決這個問題的一種多項式算法。關(guān)鍵詞:樞紐機(jī)場選址問題魯棒優(yōu)化情景分析中圖分類號:F560文獻(xiàn)標(biāo)識碼:A1前言1.1問題的提出中國航空運輸業(yè)發(fā)展迅速國航、東航、南航以及海航等較大的航空公司的機(jī)隊規(guī)模均已達(dá)百架以上并且仍在不斷地引進(jìn)新飛機(jī)

3、航線網(wǎng)絡(luò)遍布全國各個省會及主要的旅游城市。隨著規(guī)模的不斷擴(kuò)大航空公司就需要針對自身的特點規(guī)劃自己的航線網(wǎng)絡(luò)。中樞輻射航線網(wǎng)絡(luò)是航線網(wǎng)絡(luò)規(guī)劃中非常重要的一種網(wǎng)絡(luò)構(gòu)形其顯著的特點是非樞紐機(jī)場之間的客源通過樞紐機(jī)場中轉(zhuǎn)來體現(xiàn)規(guī)模經(jīng)濟(jì)效應(yīng)。構(gòu)建中樞輻射航線網(wǎng)絡(luò)時樞紐機(jī)場的選擇意義重大樞紐機(jī)場的選擇是航空公司長期的戰(zhàn)略決策。樞紐機(jī)場是旅客和貨物的吞吐量達(dá)到一定規(guī)模的大型機(jī)場航空公司構(gòu)建中樞輻射航線網(wǎng)絡(luò)時選擇了樞紐機(jī)場之后取消已有的樞紐機(jī)場或者增加

4、新的樞紐機(jī)場都要消耗航空公司大量的時間和費用而對非樞紐機(jī)場與樞紐機(jī)場連接的改變航空公司的花費相對較少更具有可行性。因此航空公司籌建中樞輻射航線網(wǎng)絡(luò)可以先確定樞紐機(jī)場的位置也就是在一些備選機(jī)場中選擇幾個機(jī)場作為自己中樞輻射航線網(wǎng)絡(luò)的樞紐。本文針對航空公司構(gòu)建中樞輻射航線網(wǎng)絡(luò)時的樞紐機(jī)場的選擇問題展開研究在不確定的環(huán)境下對樞紐機(jī)場作出選擇使得選擇的結(jié)果在未來各種可能發(fā)生的情景下航空公司都可以接受。這對于航空公司規(guī)劃自己的中樞輻射航線網(wǎng)絡(luò)具有

5、長期的戰(zhàn)略意義。1.2采取的方法從n個備選機(jī)場中選擇p個機(jī)場(p一般不會很大)作為樞紐對于每個機(jī)場航空公司的收益部門通過一系列的指標(biāo)如市場預(yù)測、自身所占的份額以及建設(shè)樞紐機(jī)場所需的前期投入等得到該機(jī)場作為樞紐能給航空公司帶來的效益值然后選擇p個使總效益最大的機(jī)場作為自己的樞紐。MilanJanic和AuraReggiani[1]利用多屬性決策方法給出了計算效益值的方法。但在分析預(yù)測效益值時由于各種因素的影響以及事物未來發(fā)展的不確定性效益

6、值的預(yù)測往往與實際情景有較大的偏差。為了規(guī)避風(fēng)險一種比較穩(wěn)妥的方法是對該效益值可能范圍做出預(yù)估也就是對效益值給出區(qū)間估計并且由于此類問題沒有歷史數(shù)據(jù)資料因此概率分布也無法得到。在這樣的情況下需要作出在未來任何可能發(fā)生的情景下都能接受的決策決策者可以采用最小最大后悔值法也就是本文所采用的魯棒優(yōu)化方法。對每一種決策計算與各種可能情景下的最優(yōu)決策的偏差其中的最大值作為該決策的最大后悔值具有最小的最大后悔值的決策具有最好的魯棒性稱為是魯棒優(yōu)化的

7、解。魯棒優(yōu)化方法不同于確定性的和隨機(jī)性的方法只針對未來的一種可能情景或者是各種情景的期望而是尋第24卷第6期(總第150期)系統(tǒng)工程Vol.24No.62006年6月SystemsEngineeringJun.2006收稿日期:20060312修訂日期:20060409作者簡介:姜濤(1978)男山東青島人南京航空航天大學(xué)民航軟科學(xué)研究所博士研究生研究方向:管理科學(xué)與工程管理智能化朱金福(1955)男江蘇常州人教授博士生導(dǎo)師研究方向:管

8、理智能化交通規(guī)劃與管理。x和目標(biāo)函數(shù)值這個過程的復(fù)雜性是O(n)。V一定在wii∈I∪wii∈I內(nèi)取值對于V每一個可能的取值r的所有可能取值為012…p.對于V和r取值的所有可能組合一一驗證分別得出可行解其中使得問題2的目標(biāo)函數(shù)值最小的可行解即為最優(yōu)解。由IgAverbakh[12]的結(jié)論V只可能取最大的2p個wi和wi的值從而該算法的復(fù)雜性為O((minpnp)2n)。實際上V的可能取值范圍還可以縮小并且對于V的每一個取值不必對r的所

9、有取值一一求解而直接求出V取值確定時問題2的解和目標(biāo)函數(shù)值。4算法的改進(jìn)記U1=wii∈IU2=wii∈I將U1和U2中的元素按大小順序為:wa1≤wa2≤…≤wanwb1≤wb2≤…≤wbn由IgAverbakh[12]的結(jié)論V∈wbkwakk=n2p1…n。其中a1…an以及b1…bn均為1…n的一個全排列。下面通過給出以下五個定理對Averbakh[12]中的算法加以改進(jìn)。定理1V∈U=wanp1…wan∪wbn2p1…wbnp1

10、。證明因為y(x)B1∪B3B1∩B3=|B1∪B3|≥p.對于i∈y(x)則有i∈B1或i∈B3.對于i∈B1有wi≥wi≥V對于i∈B3有wi≥V所以若V∈U1則V∈wbn2p1…wbnp1。由于|B2∪B4|≥np對于iy(x)有i∈B2或i∈B4對于i∈B2有wi≤V對于i∈B4有wi≤wi≤V所以若V∈U2則V∈wanp1…wan結(jié)論成立。證畢。對于V的每一個可能取值和任意的x∈A在關(guān)于x的最壞情景s(x)下引入記號BV(x)

11、=i∈I|ws(x)i≥VB′y(x)=i∈I|ws(x)iV(V)′x=argminws(x)i|i∈B′V(x)。對于V∈Ux∈A建立關(guān)于V和x的二元函數(shù)ZV(x)為ZV(x)=∑i∈x(Vws(x)i)∑i∈BV(x)(ws(x)iV)=∑i∈x(Vwi)∑i∈BV(x)(ws(x)iV)(7)問題3minx∈AZV(x)。問題3的最優(yōu)目標(biāo)函數(shù)值記作ZV最優(yōu)解記作xV.分析1在問題3中關(guān)于最優(yōu)解xV所包含的p個元素的選擇:對i∈B

12、5如果從ixV變?yōu)閕∈xV將使得ZV(x)增加Vwi對i∈B6如果從ixV變?yōu)閕∈xV將使得ZV(x)增加2V(wiwi)對i∈B7如果從ixV變?yōu)閕∈xV將使得ZV(x)增加Vwi.ZV(x)關(guān)于i的增加值記為iV.問題3的最優(yōu)解xV就是對于所有的i∈I=B5∪B6∪B7根據(jù)各自所屬的集合計算iV將iV按從小到大排序選擇前p個i組成的可行解就是xV但是其最優(yōu)解可能不唯一。注:在這里僅僅考慮了元素i從ixV變?yōu)閕∈xV對ZV(x)的改變

13、并沒有考慮i從xV中替換出的元素對ZV(x)的改變但這對結(jié)論沒有影響。分析2對于問題2IgAverbakh[12]的方法是根據(jù)V的每一個可能取值確定r的可能取值然后尋找可行解x使得V=minws(x)i|i∈y(x)在V與r取值的一對組合下得到目標(biāo)函數(shù)值。討論V與r取值的所有可能組合得到的所有目標(biāo)函數(shù)值中的最小值即為問題2的最優(yōu)目標(biāo)函數(shù)值。從而對于V∈U問題2相當(dāng)于尋找ZV(x)在限制范圍內(nèi)的最優(yōu)解也就是x∈A需要滿足下述兩個條件:①|(zhì)

14、BV(x)|≥p②|B′V(x)|≤p1。對于V∈U將滿足上述條件的x的范圍記作AV.問題4minx∈AVZV(x)。問題4的最優(yōu)目標(biāo)函數(shù)值記作Z0V最優(yōu)解記作x0V.當(dāng)V∈UAV=時Z0V值記為∞.定理2Z=minV∈UZ0V.證明由IgAverbakh[12]的方法。定理3對于固定的x∈AZV(x)作為V的函數(shù)必在滿足:①|(zhì)B′V(x)|=p或者②|B′V(x)|p并且|BV(x)|≥p的取值處達(dá)到最小值。當(dāng)①成立時ZV(x)在區(qū)間

15、[V(V)′x]內(nèi)達(dá)到最小值并在整個區(qū)間內(nèi)取值相同當(dāng)②成立時ZV(x)在滿足條件V的處取得最小值。證明關(guān)于V的函數(shù)ZV(x)是逐段線性函數(shù)對于確定的x∈Awiix和wii∈x是它的不可導(dǎo)點由最值定理和ZV(x)的表達(dá)式知結(jié)論成立。證畢。定理4Z=minV∈UZV證明由定義AVA所以有ZV≤Z0VminV∈UZV≤minV∈UZ0V=Z若ZV=ZV(xV)也就是ZV(x)在xV處取得最小值則對于xVZV(xV)作為V的函數(shù)存在V0∈U|B

16、′V0(xV)|p且|BV0(xV)|≥p由定理3知有ZV(xV)≥ZV0(xV)成立同時也有xV∈AV0成立所以ZV0(xV)≥Z0V0≥ZminV∈UZV≥Z綜上結(jié)論成立。證畢。定理5存在V0∈U使得Z=ZV0和ZV0=ZV0成立。并且可以選取xV0∈AV0Z=ZV0(x0V0)=Z0V0(xV0)。證明由定理4知一定存在V0∈U使得Z=ZV0成立。由定義一定有ZV0≤Z0V0若ZV0=ZV0(xV0)對于xV0如果有|BV0(xV