關(guān)于機場停機位分配方案模型的設(shè)計研究[20111129]

1、<p>　　關(guān)于機場停機位分配方案模型的研究</p><p>　　中南財經(jīng)政法大學(xué)信息管理與信息系統(tǒng)2009級0903班 易盈盈 0909030336</p><p>　　摘要：隨著信息化社會的高速發(fā)展，人們的生活越來越依托于網(wǎng)絡(luò)技術(shù)，本文主要討論機場停機位分配問題即考慮如何在滿足一定約束條件下，借助于網(wǎng)絡(luò)信息系統(tǒng)為到達和離開機場的航班分配合適的停機位，保證航班正常且高效運行

2、。本文關(guān)于機場停機位分配方案構(gòu)建了3種模型，一是飛機最適應(yīng)模型；二是乘客最短路徑模型；三是二者均衡考慮，構(gòu)建模型。該模型實施將為我國大部分機場運營管理中的手工機位分配所導(dǎo)致的效率低下問題帶來可能的解決方案。實現(xiàn)計算機化機位分配，適應(yīng)信息化的飛速發(fā)展，從而提高機場運營企業(yè)資源利用效率，降低運營成本，同時節(jié)省人力資源，因此具有重要的研究價值和應(yīng)用價值。</p><p>　　關(guān)鍵詞： 機場；停機位分配；模型構(gòu)建<

3、/p><p>　　a study on the airport gate allocation model </p><p>　　Abstract: With the rapid development of information society, people's lives are increasingly relying on Internet technology, th

4、is article focuses on airport gate allocation problem is to consider how to satisfy certain constraints, by means of network information systems for the airport's flight arrival and departure appropriate allocation o

5、f parking bays to ensure the normal and efficient flight operation. This article about the airport gate allocation plan to build three different models, on</p><p>　　Key words: airport; gate allocation; mod

6、el building</p><p><b>　　1 引言</b></p><p><b>　　背景</b></p><p>　　隨著社會經(jīng)濟的快速發(fā)展，人們對于乘坐航班出行的需求日益增加，在促進民航規(guī)模迅速發(fā)展的同時，也使得機場停機位不足與航班數(shù)量不斷增長的矛盾日益凸顯。</p><p><

7、;b>　　現(xiàn)狀</b></p><p>　　目前我國民航數(shù)量不斷增長，人們出行對于飛機等交通工具的依賴也越來越大，這勢必會導(dǎo)致空間資源的緊張，雖然可以通過擴大機場，增加設(shè)施緩解停機位分配不足的矛盾，但是從長遠來看這一方案并不可行。因為一方面擴建機場需要大量的人力物力，對機場周圍環(huán)境產(chǎn)生影響；另一方面這一方案有時間上的滯后性，由于機場擴建需要一定的工期，這會對現(xiàn)存的營業(yè)產(chǎn)生影響。傳統(tǒng)的機位分配方案

8、是由人工計算控制沒有納入計算機控制中，這與現(xiàn)代化的速度明顯存在矛盾。而根據(jù)計算機化的控制合理優(yōu)化飛機停機位方案，卻可以做到高效控制機場資源的配置，節(jié)省資源空間。并且由于計算機化的操作，使得人力配備減少，能夠大大提高效率。</p><p><b>　　2 問題分析</b></p><p>　　停機位分配問題的約束條件</p><p>　　不同航班

9、分配模型在滿足的約束條件上不完全相同，有的模型考慮的約束多一些，有的相對少一些。但分配停機位時通常的約束條件有：</p><p>　　（1）同一個停機位在同一時間段最多只能?？恳粋€航班。</p><p>　?。?）需為每個航班分配停機位，且至多只能分配一個停機位。</p><p>　　（3）航班從開始?？康诫x港的時間應(yīng)大于等于飛機的最短地面服務(wù)的時間。</p&

10、gt;<p>　?。?）連續(xù)占用同一停機位的前后航班之間要保持一定的安全時間間隔，以保證航班順利進出停機位并防止意外發(fā)生。</p><p>　?。?）應(yīng)滿足機型與機位相互匹配的約束。即大型航班只能使用大型停機位，中型航班可以使用大型或中型停機位，小型航班可以使用所有停機位。</p><p><b>　　需要解決的問題</b></p><

11、;p>　　（1）如何使占用的停機位數(shù)最少，使資源的利用率達到最高；</p><p>　?。?）如何使乘客行走距離最短，使乘客感受到最便捷的服務(wù)；</p><p>　　（3）如何采取加權(quán)數(shù)，綜合分析，得到最優(yōu)化解決方案。</p><p><b>　　3 目標優(yōu)化</b></p><p>　　停機位分配問題的優(yōu)化目標&

12、lt;/p><p>　　典型的停機位分配優(yōu)化目標如下幾種：</p><p>　?。?）空間資源率利用最高。</p><p>　?。?）最小化旅客總的行走距離。</p><p>　?。?）最小化未分配停機位的航班數(shù)目。</p><p>　?。?）航班等待延誤時間最小。</p><p><b>

13、;　　思路過程與框架</b></p><p>　　本論文對機場機位分配優(yōu)化問題進行系統(tǒng)地研究，并結(jié)合我國機場實際運行的情況，針對目前我國機場機位緊張且利用率不高、旅客平均行走距離較長以及航班等待延誤現(xiàn)象嚴重這三個方面的問題，分別以占用停機位數(shù)目最少、旅客平均行走距離最短和綜合考慮加權(quán)最優(yōu)化目標，建立機位分配模型，采用基于背包問題算法、進程調(diào)度算法和改進的方案算法對模型求解。</p>&l

14、t;p>　　整個過程思路如圖1所示：先系統(tǒng)闡述停機位分配問題的背景和現(xiàn)狀，結(jié)合實際應(yīng)用指出現(xiàn)存的缺陷和不足，分析問題，提出優(yōu)化目標，然后針對提出的目標根據(jù)已學(xué)的知識建立相關(guān)模型，構(gòu)建模型，比較各自的優(yōu)缺點。提出展望總結(jié)。</p><p>　　圖1 停機位分配方案思路流程圖</p><p><b>　　4 模塊構(gòu)建</b></p><p>

15、;　　機場場地資源利用率最大模塊</p><p>　　對于這一模塊，本文選取以背包算法為原型。背包問題其實就是一個優(yōu)化問題，即在所有裝包方案中選擇一種最為有效精確的裝包方案，使背包的體積最少，背包內(nèi)所裝物體價值最大。在這一模型中，機場空間資源就相當(dāng)于一個背包，要在背包中裝下盡可能多的資源，使空間的利用率達到最大，就是使未分配停機位的飛機數(shù)達到最少。</p><p>　　首先假設(shè)機場停機位空

16、間為C，根據(jù)飛機達到停機場的先后順序組成一個有序數(shù)組，a{n1，n2，n3…}按照飛機機型的不同，將其分為大中小三類型。分別占用空間資源為c1，c2，c3。取一個假設(shè)的某段時間t，要在這一段時間使機場空間資源的利用率達到最大。計算在這個時段內(nèi)航班的到達時間和停靠時間。即要同時考慮時間和空間問題。</p><p><b>　　計算：</b></p><p>　　n1在t

17、1時間到達，停靠時間k1，離開時間t1+k1，占用資源c1，剩余資源空間cn=C-c1；</p><p>　　n2在t2時間到達，?？繒r間k2（k2<(t1+k2)），占用資源c2，離開時間（t2+k2），則剩余資源空間為cn=C-c1-c2；</p><p>　　n3在t3時間到達，停靠時間k3，占用資源c3，離開時間t3+k3；</p><p>　　if（

18、k3<(t1+k1)）</p><p><b>　　cn=C-c1;</b></p><p>　　if（k3<(t2+k2)）</p><p><b>　　cn=C-c2;</b></p><p><b>　　else </b></p><p&g

19、t;　　cn=C-c1-c2;</p><p><b>　　有兩航班同時到達：</b></p><p>　?。?）兩航班占用同樣多的資源，算法同上；</p><p>　?。?）兩航班占用資源不同ni占用資源ci，nj占用資源cj（ci<cj），?？繒r間同：</p><p>　　if（ci<cn&&am

20、p;cj<cn）</p><p>　　if((ci+cj)>cn)</p><p>　　cn=cn-cj;//使資源利用率達到最高</p><p>　　if（ci<cn&&cj>cn）</p><p><b>　　cn=cn-ci;</b></p><p>

21、<b>　　else</b></p><p>　　cn=cn-ci-cj;</p><p>　?。?）兩航班占用資源不同，?？繒r間不同，ni?？繒r間ti，離開時間ki+ti，nj停靠時間tj離開時間為kj+tj(ti<tj)：</p><p>　　if((ti+ki)<(t0+t)&&(tj+kj)<(t0+t

22、))</p><p><b>　　方法同2；</b></p><p>　　if（（ti+ki）<(t0+t)&&(tj+kj)>(t0+t)）</p><p><b>　　方法同2—；</b></p><p>　　if（（ti+ki）>(t0+t)）</p&g

23、t;<p>　　都不滿足條件存入緩存中等待。</p><p>　　此種方案考慮在某一時間段內(nèi)使可用資源的利用達到最大，但是由于t的選取可大可小，也存在著時間上的銜接問題。這是需待改進的。</p><p><b>　　乘客路徑最短模型</b></p><p>　　對于這一模塊本文選取無向圖為模型。無向圖的端點表示候機廳或者停機場的位

24、置，機場停機位到機場候機廳的距離就是由無向圖中的某些連通的線段構(gòu)成，每條線段的權(quán)數(shù)代表了每一段路徑的長度。</p><p>　　本文要解決的就是根據(jù)各個候機廳的乘客人數(shù)分配比，再根據(jù)到機場停機位的距離比，計算出使所有乘客的總路徑最短的那條路徑，即路徑最短優(yōu)先。</p><p>　　乘客路徑最短模型可以簡化為如圖2所示：假設(shè)有1,2,3,4號候機廳，矩形框代表可選停機位分別為1號、2號、3號

25、……，1、2、3、4號候機廳到1號停機位的距離分別為s11，s12，s13，s14，2號候機廳到2號停機位的距離分別為s21，s22，s23，s24……依次類推。 </p><p>　　圖2 乘客路徑最短模型無向圖</p><p>　　此時不考慮空間資源分配問題，并且假設(shè)各個候機廳的乘客人數(shù)差異性很小可以忽略不計，完全關(guān)注求距離最短的算法。如果選擇1號停機位，則總距離為s1=s11+s1

26、2+s13+s14；若選擇2號停機位，則總距離為s2=s21+s22+s23+s24，若選擇3號停機位，則總距離為s3=s31+s32+s33+s34。比較選擇s1，s2，s3中最小的作為最佳停機位停靠。</p><p>　　取bool類型的數(shù)組state[]表示停機位是否被占用，false表示當(dāng)前狀態(tài)不可用，true表示當(dāng)前狀態(tài)可用。用一個整型值choice表示選擇的停機位。</p><p&

27、gt;<b>　　計算：</b></p><p>　　if(（s1<s2&&s1<s3&&s1<s4)&&state[1]=true）</p><p><b>　　{</b></p><p>　　state[1]=false;</p><

28、p><b>　　choice=1;</b></p><p><b>　　}</b></p><p>　　if（（s1<s2&&s1<s3&&s1<s4）&&state[1]=false）</p><p><b>　　{</b>&l

29、t;/p><p>　　if((s2<s3&&s2&&s4)&&state[2]=true)</p><p>　　{ state[2]=false;</p><p><b>　　choice=2;</b></p><p><b>　　}</b&

30、gt;</p><p><b>　　}</b></p><p>　　如果某航班離開停機位了，則：</p><p>　　state[i]=true;</p><p><b>　　折中優(yōu)化模塊</b></p><p>　　在本模塊中，選擇的方案是先進行資源利用率最大的算法，確定符

31、合條件的停機位，再在符合條件的停機位中選擇乘客路徑最短的停機位。</p><p><b>　　計算：</b></p><p>　　在時間t內(nèi)，有航班將要?？?，此時機場資源C=ci；根據(jù)背包算法原理找到了符合條件的停機位1號，2號，3號。</p><p>　　假設(shè)候機廳有4個分別為1，2，3，4位，4個候機廳到1號停機位的距離分別為s11,s12

32、,s13,s14，總距離s1=s11+s12+s13+s14；到2號停機位的距離分別為s21,s22,s23,s24，總距離為s2=s21+s22+s23+s24；到3號停機位的距離分別為s31,s32,s33,s34，總距離為s3=s31+s32+s33+s34；到4號停機位的距離分別為s41,s42,s43,s44，總距離為s4=s41+s42+s43+s44。</p><p>　　同樣取bool類型的數(shù)組s

33、tate[]表示停機位是否被占用，false表示當(dāng)前狀態(tài)不可用，true表示當(dāng)前狀態(tài)可用。用一個整型值choice表示選擇的停機位。</p><p><b>　　計算：</b></p><p>　　if(（s1<s2&&s1<s3&&s1<s4)&&state[1]=true）</p>&

34、lt;p><b>　　{</b></p><p>　　state[1]=false;</p><p><b>　　choice=1;</b></p><p><b>　　}</b></p><p>　　if（（s1<s2&&s1<s3&

35、&s1<s4）&&state[1]=false）</p><p><b>　　{</b></p><p>　　if((s2<s3&&s2&&s4)&&state[2]=true)</p><p>　　{ state[2]=false;</p

36、><p><b>　　choice=2;</b></p><p><b>　　}</b></p><p><b>　　} </b></p><p><b>　　5 結(jié)論 </b></p><p><b>　　比較分析<

37、/b></p><p>　　第一種算法僅考慮了空間利用率，在僅著眼于空間利用水平上確實不失為一種良好的方案。但是沒有考慮到乘客的便利性問題，在實際實施的過程中可能帶來乘客的不便利麻煩。而第二種方案則是完全站在乘客的角度，考慮路徑資源最少，而忽視了場地資源的浪費。第三種方案，結(jié)合了前兩種的優(yōu)點，選取一個折中方案，權(quán)衡兩者之間的重要性，在適當(dāng)?shù)膱龊细鶕?jù)兩者的加權(quán)選取優(yōu)化方案。</p><p&

38、gt;<b>　　展望</b></p><p>　　通過對幾種算法模型的構(gòu)建，并且結(jié)合實際需要選擇實用的方案，使機場停機問題能夠得到改善和有效率地解決。但可以看到本文的研究還不夠深入，還可以進一步完善的地方主要表現(xiàn)在以下幾方面：</p><p>　?。?）文中的數(shù)學(xué)模型還不夠全面，有一些約束條件沒有考慮到，進一步的工作可以考慮增加更多的約束規(guī)則，使停機位分配模型更加完

39、善、更加切合實際情況。</p><p>　?。?）文中幾種算法采用的都是單目標函數(shù)優(yōu)化，雖然單獨考慮某一個目標時結(jié)果較好，但無法同時優(yōu)化多個目標。</p><p>　?。?）本文研究工作都是針對航班停機位分配的預(yù)分配問題，即在預(yù)先知道機場預(yù)計到港和離港航班時刻表、停機位使用狀態(tài)的情況下給出的預(yù)分配況中，有很多不可預(yù)知的因素（如天氣、飛機故障等）會導(dǎo)致航班提前或延遲，有時不得不需要調(diào)整停機位

40、的預(yù)分配方案，這就屬于停機的點后再求解，這是一個值得進一步研究的方向。</p><p>　　雖然現(xiàn)有的模型還存在不足，但是可以展望，隨著研究的深入和社會科技的發(fā)展，人們對于資源節(jié)約型社會的重視，停機位分配模型的構(gòu)建發(fā)展會越來越完善。</p><p><b>　　參考文獻：</b></p><p>　　戴順南.機場機位分配模型構(gòu)建及算法實現(xiàn)[M]

41、.北京:北京交通大學(xué)出版社2008,105-110</p><p>　　Erico Piazza.Increasing Airport Efficiency:Injecting New Technology[J].IEEE Intelligent System,2002,17(3):10-13</p><p>　　朱世群.大型機場機位實時調(diào)配問題的研究[M].南京:南京航空航天大學(xué).200