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

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

2、。本文關(guān)于機(jī)場(chǎng)停機(jī)位分配方案構(gòu)建了3種模型，一是飛機(jī)最適應(yīng)模型；二是乘客最短路徑模型；三是二者均衡考慮，構(gòu)建模型。該模型實(shí)施將為我國(guó)大部分機(jī)場(chǎng)運(yùn)營(yíng)管理中的手工機(jī)位分配所導(dǎo)致的效率低下問(wèn)題帶來(lái)可能的解決方案。實(shí)現(xiàn)計(jì)算機(jī)化機(jī)位分配，適應(yīng)信息化的飛速發(fā)展，從而提高機(jī)場(chǎng)運(yùn)營(yíng)企業(yè)資源利用效率，降低運(yùn)營(yíng)成本，同時(shí)節(jié)省人力資源，因此具有重要的研究?jī)r(jià)值和應(yīng)用價(jià)值。</p><p>　　關(guān)鍵詞： 機(jī)場(chǎng)；停機(jī)位分配；模型構(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>　　隨著社會(huì)經(jīng)濟(jì)的快速發(fā)展，人們對(duì)于乘坐航班出行的需求日益增加，在促進(jìn)民航規(guī)模迅速發(fā)展的同時(shí)，也使得機(jī)場(chǎng)停機(jī)位不足與航班數(shù)量不斷增長(zhǎng)的矛盾日益凸顯。</p><p><

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

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

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

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

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

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

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

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

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

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

17、1時(shí)間到達(dá)，停靠時(shí)間k1，離開時(shí)間t1+k1，占用資源c1，剩余資源空間cn=C-c1；</p><p>　　n2在t2時(shí)間到達(dá)，停靠時(shí)間k2（k2<(t1+k2)），占用資源c2，離開時(shí)間（t2+k2），則剩余資源空間為cn=C-c1-c2；</p><p>　　n3在t3時(shí)間到達(dá)，?？繒r(shí)間k3，占用資源c3，離開時(shí)間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>　　有兩航班同時(shí)到達(dá)：</b></p><p>　?。?）兩航班占用同樣多的資源，算法同上；</p><p>　　（2）兩航班占用資源不同ni占用資源ci，nj占用資源cj（ci<cj），?？繒r(shí)間同：</p><p>　　if（ci<cn&&am

20、p;cj<cn）</p><p>　　if((ci+cj)>cn)</p><p>　　cn=cn-cj;//使資源利用率達(dá)到最高</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>　　（3）兩航班占用資源不同，停靠時(shí)間不同，ni?？繒r(shí)間ti，離開時(shí)間ki+ti，nj?？繒r(shí)間tj離開時(shí)間為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>　　此種方案考慮在某一時(shí)間段內(nèi)使可用資源的利用達(dá)到最大，但是由于t的選取可大可小，也存在著時(shí)間上的銜接問(wèn)題。這是需待改進(jìn)的。</p><p><b>　　乘客路徑最短模型</b></p><p>　　對(duì)于這一模塊本文選取無(wú)向圖為模型。無(wú)向圖的端點(diǎn)表示候機(jī)廳或者停機(jī)場(chǎng)的位

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

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

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

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

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

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

33、tate[]表示停機(jī)位是否被占用，false表示當(dāng)前狀態(tài)不可用，true表示當(dāng)前狀態(tài)可用。用一個(gè)整型值choice表示選擇的停機(jī)位。</p><p><b>　　計(jì)算：</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>　　第一種算法僅考慮了空間利用率，在僅著眼于空間利用水平上確實(shí)不失為一種良好的方案。但是沒有考慮到乘客的便利性問(wèn)題，在實(shí)際實(shí)施的過(guò)程中可能帶來(lái)乘客的不便利麻煩。而第二種方案則是完全站在乘客的角度，考慮路徑資源最少，而忽視了場(chǎng)地資源的浪費(fèi)。第三種方案，結(jié)合了前兩種的優(yōu)點(diǎn)，選取一個(gè)折中方案，權(quán)衡兩者之間的重要性，在適當(dāng)?shù)膱?chǎng)合根據(jù)兩者的加權(quán)選取優(yōu)化方案。</p><p&

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

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

40、的預(yù)分配方案，這就屬于停機(jī)的點(diǎn)后再求解，這是一個(gè)值得進(jìn)一步研究的方向。</p><p>　　雖然現(xiàn)有的模型還存在不足，但是可以展望，隨著研究的深入和社會(huì)科技的發(fā)展，人們對(duì)于資源節(jié)約型社會(huì)的重視，停機(jī)位分配模型的構(gòu)建發(fā)展會(huì)越來(lái)越完善。</p><p><b>　　參考文獻(xiàn)：</b></p><p>　　戴順南.機(jī)場(chǎng)機(jī)位分配模型構(gòu)建及算法實(shí)現(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>　　朱世群.大型機(jī)場(chǎng)機(jī)位實(shí)時(shí)調(diào)配問(wèn)題的研究[M].南京:南京航空航天大學(xué).200