數(shù)學(xué)建模飛機的登機順序安排問題

1、飛機的登機順序安排問題摘要美國航空機場服務(wù)規(guī)劃副總裁馬克.都彭的話來說:“登機就好比是跟在一輛慢吞吞的卡車后行駛,又不能超車?！遍L期以來,航空公司為了使飛機按時出發(fā)費盡了心思。有的公司安排從后排開始登機,有的公司從靠窗座位開始,還有些公司設(shè)計出兩者的組合方案。但實際情況卻沒有如航空公司所愿。近年來隨著民用航空業(yè)飛速發(fā)展,無論是航空公司還是旅客都希望縮短登機時間,這樣航空公司可以贏得更多時間用于飛行獲得豐厚利潤,旅客也可以縮短旅途時間。然而隨著乘坐飛機的旅客越來越多以及飛機的容量不斷增加,使得登機時間卻在不斷加長。如何縮短登機時間這一問題亟待解決。針對客機登機順序問題,文章將登機過程類比于總線型

2、局域網(wǎng)的數(shù)據(jù)傳輸過程,建立了總線狀態(tài)模型,在此基礎(chǔ)上建立了蒙特卡洛隨機模擬模型?？偩€狀態(tài)模型的主要思想是:利用總線型局域網(wǎng)拓撲結(jié)構(gòu)的原理,將客機登機所需時間轉(zhuǎn)化為拓撲結(jié)構(gòu)中總線從空載狀態(tài)到負載狀態(tài)再到空載狀態(tài)所經(jīng)過的時間。通過查閱相關(guān)資料文獻,我們篩選出六種比較具有代表性的登機方案-Back to Front、Rotating Zone、Random、Reverse Pyramid、Outside in、block。對選擇的不同機型進行模型求解,對模擬結(jié)果進行分析,得出不同飛機設(shè)計登機方案的原則。在此原則的基礎(chǔ)上,提出新的方案,并對新方案進行模擬求解,最后從已有方案的六種方案和新提出的方案中提

3、出適合各型飛機最優(yōu)的登機方案。關(guān)鍵詞:客機、登機、總線狀態(tài)模型、蒙特卡洛隨機模擬模型一.問題重述航空公司可以自由的安排等待登機的旅客的登機順序,首先安排有特殊需要的乘客登機就座已經(jīng)成為慣例. 按照常規(guī)有特殊需要的輪椅旅客首先登機,緊跟著是頭等艙的乘客(他們坐在飛機的前部. 然后是安排經(jīng)濟艙和商務(wù)艙的乘客按行排隊登機,從飛機后排的乘客依次往前安排登機。從航空公司的角度來看,除了考慮到乘客的等待時間外,時間就是金錢,所以登機時間最好應(yīng)該減小到最少. 只有飛機載客飛行,航空公司才能賺錢,而過長的登機時間將會限制飛機在一天內(nèi)的飛行次數(shù).發(fā)展大型飛機,諸如空客A380-800客機(載客800人 這樣的最

4、小化登機(離機時間的問題就更顯得重要了。(1針對不同的小型(85-210座、中型(210-330座和大型(450-800座客機,設(shè)計制訂并比較不同乘客人數(shù)的登機或離機程序.(2編寫一份不超過兩頁紙的實施概要,你要闡明你們的研究結(jié)論。閱讀對象包括航空公司的業(yè)務(wù)主管、登機口的執(zhí)法人員、空(地勤有關(guān)人員.二.問題分析本文要求設(shè)計合理優(yōu)化的登機、下機步驟,使乘客登機、下機的時間最小,以此來增加飛機在每個周期的飛行次數(shù),縮短周轉(zhuǎn)時間從而為航空公司增加收益。要研究不同登機方案的登機時間,首要的問題是要明確登機時間是由哪些部分構(gòu)成,通過對文獻的研讀以及對登機過程的研究,我們發(fā)現(xiàn)周轉(zhuǎn)時間的影響因素關(guān)鍵在于登機

5、乘客造成的干擾時間,問題的重點在于盡可能的縮短干擾時間,在假設(shè)條件下轉(zhuǎn)換成盡量減少干擾次數(shù)的問題上,包括減少座位干擾次數(shù)和過道干擾次數(shù)。登機時間主要由乘客步行時間、放行李的時間、不同排座位乘客之間的干擾時間以及同一排的乘客之間的干擾時間構(gòu)成,在此基礎(chǔ)上就是建立相應(yīng)的模型計算總的登機時間。通過對飛機座位布局和乘客登機過程的研究,我們發(fā)現(xiàn)飛機座位布局跟局域網(wǎng)的總線型拓撲結(jié)構(gòu)極為相似,而乘客的登機過程跟局域網(wǎng)上的信息傳遞過程極為相似,于是可以通過將飛機登機問題轉(zhuǎn)化為總線型局域網(wǎng)上的信息傳遞問題來進行研究。飛機的走道就相當于總線型局域網(wǎng)的總線,乘客相當于總線中傳遞的信息包,在局域網(wǎng)中總線狀態(tài)可以描述局

6、域網(wǎng)的狀態(tài),同樣,飛機走道的狀態(tài)(走道上各位置乘客的狀態(tài)也可以反映飛機的登機狀態(tài)。于是,可以通過飛機走道狀態(tài)的研究來找到總登機時間的算法。找到計算登機時間的算法后,可以進一步結(jié)合計算機模擬的算法對現(xiàn)有的登機策略進行模擬研究,通過對結(jié)果的對比分析并結(jié)合實際情況,可以判斷不同登機方案的優(yōu)劣并提出相對最優(yōu)的方案。三.模型假設(shè)(1所有乘客所帶上機的行李的大小重量相同;(2乘客的身體情況和行動能力相同;(3乘客一個緊接一個以相同間距進入飛機,且進入飛機過道上的乘客之間的間距也保持相同;(4過道上一次只能通行1人;(5 乘客為同一排的乘客讓出空間使其到達自己位置時,必須先讓到過道上,此時在過道上的讓與被讓

7、者占有的過道空間還是一個人所占有的空間;(6乘客不會走錯到不屬于自己的位置上;(7乘客首先在走道上放好自己的行李,各乘客放行李的時間相同,且一次放好不會再進行調(diào)整;(8所有乘客按登機牌上的座位號對好入座,不會調(diào)換座位;(9飛機所有位置坐滿;(10乘客不會出現(xiàn)遲到等其他一些突發(fā)情況。(11某乘客登機行為只可能影響到在他之后登機的一個人,對其他人沒有后續(xù)影響.(12登機門為飛機的前艙門。(13乘客均按登機牌號碼入座。如果乘客不對號入座,那么就有可能造成配載的計算重心與飛機的實際重心發(fā)生偏差,非滿客時此規(guī)定尤為重要。四.符號說明錯誤!未找到引用源。b t 乘客從一排座位到相鄰座位間的步行時間f t

8、乘客放行李的時間1t 需要一個乘客讓位的時間2t 需要兩個乘客讓位的時間t 基本時間間隔,b t t =i t 表示i t 時刻i Z i t 時刻的總線狀態(tài)ik z i t 時刻的總線上k 節(jié)點的狀態(tài)五.模型準備5.1登機時間登機時間是指發(fā)登機牌到旅客安檢、托運行李、候機樓候機、排隊登機等時間;從旅客進入飛機到在座位上坐好的時間為入座時間。乘客登機時間是這兩部分時間之和。經(jīng)波音公司調(diào)查,乘客登機時間主要來自于乘客入座時間(特別是大飛機,如 A380。乘客入座時間來自于乘客入座的干擾,主要是座位干擾和通道干擾。登機方式及步驟(1從后往前:把乘客分為適當?shù)膸捉M,按一定的次序從機艙的尾部就做一直到

9、機艙前面結(jié)束就做。(2從外向內(nèi):首先靠著窗戶的就座,然后中間的就座,最后靠走道的就座。(3反向金字塔系統(tǒng):首先是后窗與中間就坐,然后是前窗與中間,再接著是后面的的走廊過道,最后是前面的走廊過道。5.2總線型局域網(wǎng)的拓撲結(jié)構(gòu)總線型局域網(wǎng)的拓撲結(jié)構(gòu)是指用一根稱為總線的同軸電纜將服務(wù)器和工作站以線性方式連接在一起?？偩€的兩端都有一個終端器,它可給連接在總線之間的電路加載。所有網(wǎng)絡(luò)上的計算機通過合適的接口連接在總線上,即網(wǎng)絡(luò)上的所有節(jié)點共享這條總線,總線上的節(jié)點通過廣播信息的地址與各節(jié)點通信。支線上的每個節(jié)點都有唯一的一個地址。當節(jié)點的地址與信息的地址相同時,就把總線上的信息復(fù)制下來。網(wǎng)絡(luò)結(jié)構(gòu)示意圖如

10、下(圖1。圖1總線型局域網(wǎng)拓撲結(jié)構(gòu)在總線型局域網(wǎng)中,可以只有一臺服務(wù)器,只有這臺服務(wù)器能向網(wǎng)絡(luò)中其他各節(jié)點發(fā)送數(shù)據(jù)包,其他網(wǎng)絡(luò)節(jié)點通過共同的總線接受服務(wù)器發(fā)送給自己的數(shù)據(jù)包。5.3乘客登機就座過程與總線型拓撲結(jié)構(gòu)信息傳輸?shù)念惐韧ㄟ^研究飛機的登機過程,我們發(fā)現(xiàn)飛機的登機過程與上面介紹的總線型局域網(wǎng)信息傳輸過程非常相似。從結(jié)構(gòu)上來說,客機的艙門好比總線型局域網(wǎng)拓撲結(jié)構(gòu)的服務(wù)器,過道好比總線,客機的各個座位好比拓撲結(jié)構(gòu)中支線上的各個節(jié)點,乘客好比要傳輸?shù)臄?shù)據(jù)包。從過程上來說,乘客經(jīng)過艙門,通過過道,到達自己座位的過程就好比網(wǎng)絡(luò)結(jié)構(gòu)中的服務(wù)器發(fā)出一個個的數(shù)據(jù)包到總線再到各個節(jié)點的過程;而當乘客到達總線

11、上的目的地址進入支線時,由于要放行李或有其他乘客干擾使其占用過道時間較長,這相當于總線的傳輸速度要比支線的傳輸速度快得多,因此支線在接受數(shù)據(jù)時會占用較多的總線時間。從上面的分析不難看出,飛機的登機過程在一定程度上可以近似看作一總線型局域網(wǎng)傳輸數(shù)據(jù)的過程,因此我們完全可以借鑒研究局域網(wǎng)的一些思想和方法來研究飛機登機的過程。在局域網(wǎng)中,可以用總線狀態(tài)即總線上各節(jié)點的狀態(tài)來描述和研究某時刻局域網(wǎng)的運行狀態(tài),因此我們可以通過研究登機過程中某時刻飛機走道的狀態(tài)來描述登機的過程。只要找到走道相鄰各狀態(tài)之間的聯(lián)系,就可以求得登機的時間。從這個角度出發(fā)可以建立求解飛機登機時間的模型。5.4基本問題的確定要研究

12、登機過程的總時間,首要的問題是確定登機時間由那些部分構(gòu)成。在登記過程中,乘客從飛機入口走到相應(yīng)位置要花費步行時間;一般乘客都帶有一些隨身行李,到達座位旁的走道時要先將行李放在座位上方的行李架上,這就是放行李的時間;當乘客需要已入座好的同排乘客讓出空間使自己入座時,需要一定的讓座時間。于是,整個登機過程所需時間主要就與乘客的步行時間、放行李時間、讓座時間三部分有關(guān),下面分別對這三種時間進行研究。(1步行時間根據(jù)資料,在登記過程中,乘客從某一排行走到相鄰排的平均時間是0.95秒,根總線節(jié)點支線節(jié)點終端器終端器 支線 總線服務(wù)器據(jù)假設(shè)(3和假設(shè)(4,為研究問題方便,可以將整個走道沿行進方向分成若干段

13、,每一段的長度就是相鄰兩排座位之間的距離,如下圖所示(圖2: 圖2 客機座位平面簡化圖圖中標注為0的格子表示過道的一段,標注為負的格子表示左邊的座位,標注為正的格子表示右邊的座位,1(-1、2(-2、3(-3分別代表靠走道的座位、中間的座位、靠窗的座位。因此可以認為,在走道不堵塞的情況下,一個乘客經(jīng)過0.95b t =秒從走道的一個格子行走到相鄰的下一個格子。(2放行李的時間根據(jù)資料,乘客平均放行李的時間是7.1f t s =,根據(jù)假設(shè)(1和假設(shè)(7,每個乘客到達自己座位旁的走道時,都要先站在走道上放好行李,且放行李的時間都是7.1秒。(3讓座位的時間座位干擾:靠在窗戶的乘客入座時,外面的座位

14、上已經(jīng)有乘客就坐,這時外邊的這位的乘客需要起身給剛來的這位乘客讓開位置使他能夠順利入座。根據(jù)資料,平均讓座的時間是9.7秒,設(shè)A 、B 、C 分別代表同排的三個位置的入座順序(A 代表最先入座、C 代表最后入座,如C-B-A 代表靠窗的座位最先入座、靠過道的座位最后入座,其考慮的情況為以下幾種:1B-C-A 這種情況需要的時間為3個單位,如設(shè)一個單位的時間為0t ,則這種情況需要03t 的讓位時間;2 C-A-B 這種情況需要03t 的讓位時間;3 A-C-B 這種情況需要05t 的讓位時間;4 B-A-C 這種情況需要06t 的讓位時間; 5 A-B-C 這種情況需要08t 的讓位時間;于是

15、由平均讓位時間9.7秒可以計算出0 1.94t s =。據(jù)此,對于某一個乘客來說,如果需要別的乘客讓位,其可能的情況為: 1 只需要靠走道的一個乘客讓位,所需時間為03 5.82t s =; 1 只需要坐中間的一個乘客讓位,所需時間為03 5.82t s =;3需要靠走道和坐中間的兩個乘客讓位,所需時間0611.64t s =。 綜上,某個乘客若需要讓位,其可能的情況是: 1 只需一個乘客讓位,所需時間為1 5.82t s =;1 需要兩個乘客讓位,所需時間為211.64t s =。 需要說明的是,以上放行李的時間和讓位的時間都是指從動作發(fā)生開始至讓出走道為止之間的時間。同時,為了研究問題的方

16、便,以乘客步行時間0.95b t =為基準,將放行李時間7.1f t s =調(diào)整為7.6f t s =,將讓位時間1 5.82t s =調(diào)整為1 5.7t s =,將211.64t s =調(diào)整為211.4t s =。這樣調(diào)整后8f b t t =,16b t t =,212b t t =,這樣就可以0.95b t =為一個時間間隔研究總線狀態(tài)的改變,可以方便問題的研究。同時,做出這樣調(diào)整還有另外一個意義。由于還有很多突發(fā)因素沒有考慮,有可能計算出的登機時間比實際的小,這樣就會導(dǎo)致出現(xiàn)航班延誤的情況,對時間做出上述調(diào)整后,必然會增加計算所得的登機時間,從而可以在一定程度上減少航班延誤的情況發(fā)生。

17、六.模型的建立與求解6.1總線狀態(tài)模型的建立由前面的分析,將登機過程看成總線型局域網(wǎng)的信息傳輸過程以后,總的登機時間就相當于總線開始由空載狀態(tài)進入負載狀態(tài)起,最后回復(fù)到空載狀態(tài)瞬間所經(jīng)歷的時間,而這段時間的確定依賴于中間任一時刻總線狀態(tài)的確定?？偩€狀態(tài)的描述若總線上有n 個節(jié)點,那么i t 時刻的總線狀態(tài)i Z 可以描述為:(01i ik Z z = i1i2ik in i(k-1i(k+1(z ,z ,z ,z ,z ,z 或其中0ik z =表示i t 時刻k 節(jié)點上沒有到達信息包,1ik z =表示i t 時刻k 節(jié)點上有到達信息包。這樣,總線狀態(tài)通過其上各個節(jié)點的狀態(tài)來描述,總線狀態(tài)的

18、改變?nèi)Q于各節(jié)點狀態(tài)的改變。設(shè)(1i t -時刻k 節(jié)點的狀態(tài)為(1i k z -,i t 時刻k 節(jié)點狀態(tài)的為ik z ,那么從(1i t -時刻到i t 時刻k 節(jié)點狀態(tài)的改變可以分為以下四種情況: (1 (100i k ik z z -=出現(xiàn)這種情況的可能條件是:1 (1(10i k z -=,即(1i t -時刻1k -節(jié)點上沒有數(shù)據(jù)包到達;2 (1(11i k z -=,即(1i t -時刻1k -節(jié)點上有數(shù)據(jù)包到達,且其目的地址就是1k -節(jié)點,但還在等待進入下一級目的地址;(2 (101i k ik z z -=出現(xiàn)這種情況的條件是:(1(11i k z -=,即(1i t -時

19、刻1k -節(jié)點上有數(shù)據(jù)包到達; (3 (110i k ik z z -=出現(xiàn)這種情況的條件可能是:1 (11i k z -=且(1(10i k z -=同時(1(10i k z -+=,即(1i t -時刻k 節(jié)點上有信息包到達,且其目的地址是比k 節(jié)點大的節(jié)點,而(1k -節(jié)點上沒有數(shù)據(jù)包到達,同時(1k +節(jié)點上沒有到達數(shù)據(jù)包;2 (11i k z -=且(1(11i k z -=同時(1(10i k z -+=,即(1i t -時刻k 節(jié)點上有信息包到達,且其目的地址是比k 節(jié)點大的節(jié)點,而(1k -節(jié)點上有數(shù)據(jù)包到達其目的地址就是(1k -節(jié)點,同時(1k +節(jié)點上沒有到達數(shù)據(jù)包;3

20、(11i k z -=且(1(11i k z -=,即(1i t -時刻k 節(jié)點上有信息包到達,且其目的地址是k 節(jié)點,從(1i t -時刻到i t 時刻的基本時間間隔t 內(nèi)剛好完成放行李或放行李和被讓位的過程后離開過道(即讓出總線;(4 (111i k ik z z -=出現(xiàn)這種情況的條件可能是:1 (11i k z -=,即(1i t -時刻k 節(jié)點上有數(shù)據(jù)包到達,且其目的地址是k 節(jié)點,但從(1i t -時刻到i t 時刻的基本時間間隔t 內(nèi)還沒結(jié)束放行李或放行李和被讓位的過程而離開過道(即讓出總線;2 (11i k z -=且(1(11i k z -+=,即(1i t -時刻k 節(jié)點上

21、有數(shù)據(jù)包到達,1k +節(jié)點上也有數(shù)據(jù)包到達,k 節(jié)點上有數(shù)據(jù)包的目的地址是比k 節(jié)點大的節(jié)點,從(1i t -時刻到i t 時刻的基本時間間隔t 內(nèi)1k +節(jié)點上的數(shù)據(jù)包還沒有讓出總線;3 (11i k z -=且(1(11i k z -+=同時(1(11i k z -=,即(1i t -時刻k 節(jié)點上有數(shù)據(jù)包到達,1k +節(jié)點上也有數(shù)據(jù)包到達,k 節(jié)點上有數(shù)據(jù)包的目的地址是比k 節(jié)點大的節(jié)點,從(1i t -時刻到i t 時刻的基本時間間隔t 內(nèi)1k +節(jié)點上的數(shù)據(jù)包剛好讓出總線,k 節(jié)點上的數(shù)據(jù)包傳送到1k +節(jié)點的同時1k -節(jié)點的數(shù)據(jù)包傳送到k 節(jié)點。根據(jù)上述的節(jié)點狀態(tài)改變情況,就可以

22、由上一時刻的所有節(jié)點狀態(tài)確定下一時刻的所有節(jié)點狀態(tài),即某一時刻的總線狀態(tài)可以由初始狀態(tài)和各節(jié)點狀態(tài)的時間遞歸確定,當總線狀態(tài)又回復(fù)到空載狀態(tài)時,就是登機完成的時刻。需要說明的是,總線回復(fù)到空載狀態(tài)是以最后一個信息包離開總線,即走道上的最后一個乘客離開走道瞬間為標志,事實上登記結(jié)束應(yīng)該以最后一個乘客入座為標志,但從走道到入座的時間相比總的登機時間來講可以忽略,因此以總線回復(fù)到空載瞬間為登機結(jié)束的標志是合理的。6.2隨機模擬模型的建立由于在實際情況中,不可能嚴格要求乘客按照某一順序排隊登機,所以無論以怎樣的登機策略登機,登機的過程總存在著一定的隨機性,這種隨機性一方面來自于乘客進入飛機艙的順序具有

23、一定的隨機性,另一方面人的行動也總是具有一定的隨機性和不確定性。根據(jù)前面的假設(shè),不考慮這種人的行為不確定性對登機過程的影響,即每個人以既定的相同的行為、時間和節(jié)奏進行登機,這樣在模擬登機過程的時候所要模擬的隨機事件就只剩下乘客進入飛機的順序。設(shè)一定數(shù)量的乘客進入飛機的順序是任意的一個隨機順序,利用蒙特卡洛隨機模擬的方法,在計算機上可以先產(chǎn)生一個隨機的乘客進入飛機的順序,然后通過前面的總線狀態(tài)模型,從總線狀態(tài)的角度模擬飛機登機的全過程,進而求出登機時間。對同一種登機策略在同一種飛機上進行多次模擬,可以得到該種登機方案運用到該種飛機上的登機時間的期望。下圖所示為蒙特卡洛隨機模擬的流程圖(圖3:座位

24、編號產(chǎn)生隨機登機順序初始化總線狀態(tài)下一間隔時間總線狀態(tài)否是否空載是退出圖3 蒙特卡洛流程圖6.3模型的求解根據(jù)題目要求,我們選擇了大、中、小三種機型的座位布置情況來進行模擬計算,三種機型分別是“B737-300”、“B757-200”和“B777-300”。中、小型飛機都是單走道的,大型飛機是雙走道的,其作為布置圖見附件1(附圖1至附圖3。根據(jù)前面模型準備的討論,可以將飛機的座位布置圖作如下簡化,以小型飛機“B737-300”為例,其簡化后的座位布置圖如下(圖4: 圖4 小型機B737-300座位布置圖其他兩種飛機的座位布置簡化圖見附件2(附圖4和附圖5。圖3中沒有畫出頭等艙的座位情況,因為頭等艙座位較少空間較大,對于總登機時間的影響較小,因此在模擬計算時可以不予考慮,只模擬商務(wù)艙和經(jīng)濟艙的登機情況。根據(jù)資料,現(xiàn)有的并且較常用的登機方案有六種:Back to Front、Rotating Zone、Random、Reverse Pyramid、Outside In、Block。其登機方法如下圖(圖5所示: 圖5 六種登機方案示意圖其中顏色淺的表示先登記,顏色越深表