飛機排隊問題

1、數(shù)學建模與計算問題飛機排隊問題（1）問題機場通常都有用“先來后到”的原則分配飛機跑道.即當飛機準備離開登機口 時，駕駛員電告地面控制中心，加入等候跑道的行列.假設控制塔可以從快速反應 數(shù)據(jù)庫中得到每架飛機的如下信息：1）預定離開登機口的時間；2）實際離開登機口的時間；3）機上乘客人數(shù)；4）預定在下一站轉(zhuǎn)機的人數(shù)和轉(zhuǎn)機時間；5）到達下一站的預定時間.又設共有7種飛機，載客量從100人起以50人遞增，最大的飛機載客量為400人 這7種飛機可能分屬不同的航空公司.試開發(fā)和建立一種能使乘客和航空公司雙方都滿意的數(shù)學模型，以安排飛機 起飛的先后次序.（2）假設1）機場控制塔上有一個快速反應的數(shù)據(jù)庫，該庫

2、中存貯著每一架飛機的正點起飛 時間，正點抵達目的地的時間，乘客數(shù)量，飛行距離等信息,其他一些有用的參數(shù)，可 以根據(jù)數(shù)據(jù)庫中已有數(shù)據(jù)估計出來.2）所有飛機都在同一專用跑道上起飛，任何一種飛機在跑道上起飛所需要的時間 相同，這樣可以把時間劃分成間隔為的起飛時段.3）標號為i的飛機在第j個時段起飛所需費用與先前起飛的飛機無關(guān)，僅與其安排 的次序有關(guān).這一假設使我們可以把總費用作為飛機調(diào)度排序的線性函數(shù).4）所有飛機從登機口到跑道起點的時間相同.5）記t為使飛機尚能正點到達目的地所推遲起飛的最長時間.同時假定，當飛機的 誤點時間超過t時,則飛機將以最大的安全速度飛行.6）如果飛機推遲起飛的時間超過t

3、,則機上所有下站轉(zhuǎn)機的乘客都將耽誤轉(zhuǎn)機.7）因誤點而要求改航的賠償費對每一個乘客都是相同的.(3)記號及意義:飛機起飛的時間間隔；0最早起飛的飛機離港時間；d :正點起飛的時間;七:正點到達目的地的時間；t:晚點時間；T :最大允許晚點起飛的時間；k:各種類型的飛機因晚點起飛而引起耗油的費用常數(shù)；陌:平均飛行速度；y max :最大的安全飛行速度;r:要求改航的乘客的賠償費；n :下站轉(zhuǎn)機的乘客數(shù)；P:乘客總數(shù)；:由于晚點起飛所引起的乘客不滿意程度的增長率；a:全體乘客由于飛機晚點起飛所引起的不滿意度折合成美元的折合率;b:耽誤轉(zhuǎn)機的乘客不滿意度折合成美元的折合率.分析與建模若有n架飛機都要求

4、在時刻正點起飛，并且認為所有飛機都有直通跑道.我 們以總費用最小作為目標來安排飛機起飛的次序.總費用由兩部分組成，即航空公 司的費用和乘客不滿意程度所折合的費用.設%為標號，的飛機在第，個起飛時段起飛的費用，引入狀態(tài)變量氣廠其定義 為=J1,當標號為i的飛機第/個起飛七=10,其它則總費用為一 n nZ 二在 c xi=1 J=1為了保證每一架飛機只安排在一個時段內(nèi)起飛及每一個時段內(nèi)只有一架飛機 起飛，因此對狀態(tài)變量xtj增加約束條件: x = 1, i = 1,2,., n 寸 x = 1, j = 1,2,.,nij=1由假設條件可知，Cj與Xjj無關(guān)，因而總費用C是一個線性函數(shù).這是一個

5、指派問題.假定每隔時間只有一架飛機離開登機口加入到請求起 飛的行列中，這樣就保證總有飛機請求起飛.每隔時間，執(zhí)行一次程序，以安排在 當前狀態(tài)下最優(yōu)的起飛次序.這里需要說明一點，該程序運行時間極短,不到一分 鐘便可完成，因此，如果數(shù)據(jù)發(fā)生變化時,如飛機晚點進港等，幾乎可以立即決策.下面來分析費用系數(shù)的確定問題.總費用應包括航空公司的費用和乘客的不滿意度所折合的費用.首先把基本 費用視為0,即設飛機在正點起飛時的費用為0,僅考慮由于飛機晚點起飛所導致 的額外費用.航空公司的費用主要由兩部分組成.一部分為額外的汽油費，這個費用主要是 由于飛機晚點起飛時，要在空中快速飛行所額外消耗的汽油費;另一部分為

6、耽誤了 轉(zhuǎn)機的乘客需要改航時的賠償費.若飛機晚點起飛，為了正點抵達目的地,它必須 在空中以更快的速度飛行，這樣由于風阻力的增大和其它因素，就要增加汽油的消 耗.我們不太清楚速度的增加如何引起耗油費和增加，但當飛機加速過程結(jié)束,在空中 以最大安全速度飛行時,額外的耗油費將是一個常數(shù).為簡單起見，選用線性函數(shù)來表示額外的油耗費，其公式為:F (t)=kt,t T其中J為飛機晚點起飛的時間，顯然當飛機正點起飛時J=0,若to為首架起飛的時 刻，？為正點起飛的時刻,為起飛的時間間隔，則第j個起飛的飛機晚點起飛的 時間為:t = t + (j - 1)A-10d由于T為最長的晚點起飛時間，即當晚點起飛的

7、時間超過T以后，即使在空中以最 大速度飛行，也不能正點抵達目的地，因此T = T 廠max其中TA為正點抵達目的地的時刻,d為飛行距離，max為最大的安全飛行速度.d可用公式來表示d=吧其中，為正點起飛時刻，Vav為正點起飛時平均飛行速度.常數(shù)k與油價、單位晚點時間油耗的增加率及最大安全飛行速度有關(guān)，同時 還應與飛行距離有關(guān)，當然飛行距離越長，額外的油耗就越大.由于飛行距離為Ta -七，乘以最大安全飛行速度,則有:F(t)=k(T t t)t, t tAd下面再計算改航旅客的賠償費.為簡單起見，由假設條件，記每一個改航旅客 的賠償費用為一個常數(shù)r(若賠償不同，則令r為賠償?shù)钠谕?.由于當飛機

8、晚點起 飛時，所有下站轉(zhuǎn)機的乘客都將改航,則改航的賠償費為：R (t) = r nu (t-t )n為轉(zhuǎn)機旅客總數(shù),u(t)為單位階梯函數(shù)，即0, S 0費用系數(shù)中還應考慮乘客的不滿意程度.一般地,飛機晚點起飛的時間越長， 旅客就越抱怨，其不滿意程度就越大.如果晚點時間只有12分鐘，旅客就不會太 不滿意.但是，隨著晚點時間的增加，旅客會非常生氣，而不滿意度會急驟增加，因此 我們選用指數(shù)函數(shù)描述旅客的不滿意程度.這個不滿意程度對機上每一旅客都是 如此，但對下站要轉(zhuǎn)機的乘客，還需要追加另外的不滿意度，用D(t)表示總的不滿 意程度所折合的費用，則D(t) = ap(et -1) + bnu(t -

9、t )p為機上乘客總數(shù),n為下站轉(zhuǎn)機的乘客總數(shù)，為了保證在正點起飛時乘客的不滿 意度為0,因而采用了 3 T)的形式，顯然t=0時,D(0)=0. a為乘客不滿意度的 增長率,a,b為折合率，ap(ea D代表全體乘客不滿意度折合的費用，b兀()為下站轉(zhuǎn)機乘客追加的不滿意度所折合的費用,這一項只有當t t才起作用.綜上所述，費用系數(shù)c .應為額外油耗費、賠償費、及不滿意度所折合的費用之和c = F(t) + R(t) + D(t)j時 tcij，/一、 / d=k(T 一t t)t + ap(eat 1),t t t A dt和T由下式給出t = t t + (j1)A0 dt = T t T

10、a - td 匕AVmax2)計算實例為了執(zhí)行簡單，再作一些假設。1)全多有三架飛機等候飛行(即n3)如果不足三架，在模型中增加一架或2)3)跑道上沒有飛機降落;4)每一個改航旅客的賠償費用為350美元;兩架虛擬的飛機，虛擬的飛機的費用系數(shù)視為0。任何飛機起飛時間至多1分鐘，即=1，其間，其它飛機不能占用跑道。5)一個要改航乘客的不滿意度是誤點15分鐘的乘客的2倍 乘客多的飛機先起飛例有A,B,C三架飛機都已離開了登機口，要求在上午6點鐘正點起飛，這三架 飛機將飛往三個不同城市，但空中飛行距離都相同，正點抵達目的地的時間均為上午7點20分.另外，其乘客數(shù)量分別為350,100,400,且每架飛

11、機上都有100名乘客將在下一站轉(zhuǎn)機.執(zhí)行結(jié)果為：標號乘客數(shù)/轉(zhuǎn)機乘客數(shù)費用系數(shù)解A350/10000.480.97010B100/10000.410.83001C400/10000.51100其最小費用為1.31,起飛的次序為C,A,B.這一結(jié)果與我們的直覺完全一致，即在 其它條件相同的情況下，乘客數(shù)量多的飛機優(yōu)先起飛.誤點時間最長的飛機優(yōu)先起飛接著上面問題，飛機C正在起飛的同時，飛機D已經(jīng)離開了登機口請求起飛.已知 飛機D載有200名乘客，其中150名將在下站轉(zhuǎn)機，這架飛機已經(jīng)晚點18分鐘， 要使飛機D正點抵達目的地,必須在2分鐘內(nèi)起飛（即必須在6點02分或6點03 分兩個起飛時段內(nèi)起飛）.

12、執(zhí)行結(jié)果如下表.標號乘客數(shù)/轉(zhuǎn)機乘客數(shù)已晚點時間（min）費用系數(shù)解D200/150180.280.911100B100/10010.070.150.22001A350/10010.090.170.26010這個例子中的總費用為1.22，最優(yōu)的起飛次序為D,A,B.這一結(jié)果與直覺相符，即 晚點時間最長的飛機優(yōu)先起飛.優(yōu)先權(quán)相差不明顯的情形當系統(tǒng)時鐘指向6點03分，此時C,D,A三架飛機已先后起飛，飛機B已晚點 3分鐘，而又有一架飛機E離開登機口，請求起飛.對飛機E,我們知道如下信息:總 乘客數(shù)不122名，其中89名乘客在下站轉(zhuǎn)機，晚點1分鐘的費用為450美元;最長 的晚點時間為45分鐘.在求解時,須增加一架虛擬飛機X,對應于飛機X的所有參數(shù)為0.結(jié)果如下：標乘客數(shù)/轉(zhuǎn)機乘客已晚點時間費用