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

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

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

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

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

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

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

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

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

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

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

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

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

17、1時間到達(dá)，?？繒r間k1，離開時間t1+k1，占用資源c1，剩余資源空間cn=C-c1；</p><p>　　n2在t2時間到達(dá)，停靠時間k2（k2<(t1+k2)），占用資源c2，離開時間（t2+k2），則剩余資源空間為cn=C-c1-c2；</p><p>　　n3在t3時間到達(dá)，?？繒r間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>　　有兩航班同時到達(dá)：</b></p><p>　?。?）兩航班占用同樣多的資源，算法同上；</p><p>　?。?）兩航班占用資源不同ni占用資源ci，nj占用資源cj（ci<cj），停靠時間同：</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>　?。?）兩航班占用資源不同，?？繒r間不同，ni?？繒r間ti，離開時間ki+ti，nj?？繒r間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)使可用資源的利用達(dá)到最大，但是由于t的選取可大可小，也存在著時間上的銜接問題。這是需待改進(jìn)的。</p><p><b>　　乘客路徑最短模型</b></p><p>　　對于這一模塊本文選取無向圖為模型。無向圖的端點(diǎn)表示候機(jī)廳或者停機(jī)場的位

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

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

26、2+s13+s14；若選擇2號停機(jī)位，則總距離為s2=s21+s22+s23+s24，若選擇3號停機(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)可用。用一個整型值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>　　在時間t內(nèi)，有航班將要停靠，此時機(jī)場資源C=ci；根據(jù)背包算法原理找到了符合條件的停機(jī)位1號，2號，3號。</p><p>　　假設(shè)候機(jī)廳有4個分別為1，2，3，4位，4個候機(jī)廳到1號停機(jī)位的距離分別為s11,s12

32、,s13,s14，總距離s1=s11+s12+s13+s14；到2號停機(jī)位的距離分別為s21,s22,s23,s24，總距離為s2=s21+s22+s23+s24；到3號停機(jī)位的距離分別為s31,s32,s33,s34，總距離為s3=s31+s32+s33+s34；到4號停機(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)可用。用一個整型值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í)不失為一種良好的方案。但是沒有考慮到乘客的便利性問題，在實(shí)際實(shí)施的過程中可能帶來乘客的不便利麻煩。而第二種方案則是完全站在乘客的角度，考慮路徑資源最少，而忽視了場地資源的浪費(fèi)。第三種方案，結(jié)合了前兩種的優(yōu)點(diǎn)，選取一個折中方案，權(quán)衡兩者之間的重要性，在適當(dāng)?shù)膱龊细鶕?jù)兩者的加權(quán)選取優(yōu)化方案。</p><p&

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

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

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