基于時(shí)空網(wǎng)絡(luò)的航班機(jī)型分配問(wèn)題研究

樂美龍,黃文秀

(上海海事大學(xué) 科學(xué)研究院,上海 201306)

基于時(shí)空網(wǎng)絡(luò)的航班機(jī)型分配問(wèn)題研究

樂美龍*,黃文秀

(上海海事大學(xué) 科學(xué)研究院,上海 201306)

機(jī)隊(duì)規(guī)劃是航空公司高效運(yùn)營(yíng)的重要前提.本文通過(guò)構(gòu)建基于時(shí)空網(wǎng)絡(luò)的航班機(jī)型分配模型,以及乘客溢出量函數(shù)和航班機(jī)型分配成本函數(shù),為航空公司設(shè)計(jì)了一種航班機(jī)型分配的方法.基本思想是在已知航空公司航班計(jì)劃、乘客需求分布、機(jī)隊(duì)結(jié)構(gòu)、機(jī)型數(shù)量的基礎(chǔ)上,首先通過(guò)構(gòu)建時(shí)空網(wǎng)絡(luò)圖得出航班機(jī)型分配模型所需的參數(shù).然后通過(guò)求解航班機(jī)型分配模型,得到使航班機(jī)型分配總成本最小的航班機(jī)型配置方案和機(jī)隊(duì)配置方案.最后通過(guò)算例驗(yàn)證了上述方法科學(xué)、有效,能夠?yàn)楹娇展竞桨鄼C(jī)型分配提供決策支持.

航空運(yùn)輸;機(jī)型分配;時(shí)空網(wǎng)絡(luò);機(jī)型;航班

1 引 言

機(jī)型分配是指在給定航班計(jì)劃的條件下,已知機(jī)隊(duì)結(jié)構(gòu)、飛機(jī)數(shù)量及每種機(jī)型飛每條航線的成本,航空公司確定每條航線用什么機(jī)型來(lái)飛,使其總利潤(rùn)最大或總成本最小.近年來(lái),隨著航空運(yùn)輸業(yè)的迅速發(fā)展,航空公司的市場(chǎng)競(jìng)爭(zhēng)逐步加劇,國(guó)內(nèi)各航空公司正在采取多種措施來(lái)提高其管理水平,包括優(yōu)化航線網(wǎng)絡(luò)、優(yōu)化資源分配等方式.目前有關(guān)航空公司機(jī)型分配的研究主要集中在如下方面.

國(guó)外的 Brown[1]通過(guò)構(gòu)建基于面板數(shù)據(jù)的模型分析了航空管制因素對(duì)其機(jī)隊(duì)構(gòu)成的影響,文章主要側(cè)重于對(duì)樞紐輪輻式航空公司機(jī)隊(duì)規(guī)劃的研究,但其考慮的影響因素較少.Hane 等人[2]構(gòu)建了一種基于時(shí)間拓展網(wǎng)絡(luò)的多商品流模型,用于解決機(jī)隊(duì)分配的大規(guī)模整數(shù)規(guī)劃問(wèn)題,在模型求解中用到了內(nèi)點(diǎn)算法,并通過(guò)數(shù)據(jù)驗(yàn)證了該模型和算法在解決大規(guī)模整數(shù)規(guī)劃問(wèn)題上的優(yōu)越性.Bahram 等人[3]在 Brown 模型的基礎(chǔ)上,構(gòu)建了基于市場(chǎng)結(jié)構(gòu)和生產(chǎn)技術(shù)因素的機(jī)隊(duì)規(guī)劃模型,通過(guò)數(shù)據(jù)驗(yàn)證了航空公司機(jī)隊(duì)構(gòu)成受這兩個(gè)因素影響.Barnhart等人[4]提出了一種 IFAM(Itinerary-Based Fleet Assignment Model) 模型, 首先介紹了基本的FAM(Fleet Assignment Model)模型和PMM模型(Passenger Mix Model), 在 PMM 模型的求解中用到了列生成算法,然后,在 FAM 和 PMM 模型的基礎(chǔ)上,構(gòu)建了 IFAM 模型,模型求解用到了分枝定界法.Listes 等人[5]提出了一種基于時(shí)空網(wǎng)絡(luò)的機(jī)隊(duì)分配模型,模型考慮到了乘客的動(dòng)態(tài)需求,在模型求解中用到了情境聚合算法,最后通過(guò)實(shí)際數(shù)據(jù)驗(yàn)證了模型和算法的可行性和優(yōu)越性.Ahuja 等人[6]用大規(guī)模鄰域搜索算法對(duì)機(jī)型分配模型進(jìn)行求解,該方法考慮到了連續(xù)航段上同一機(jī)型的指派,最終不僅生成了機(jī)型的分配方案,而且還生成了連續(xù)的航班段.Sherali 等人[7]提出了一種兩階段的機(jī)隊(duì)分配模型,模型同樣考慮了隨機(jī)乘客需求,模型求解中用了 Benders 分解算法.Barnhart等人[8]在區(qū)別 FAM 和 IFAM 的基礎(chǔ)上,提出了一種GFAM(Generic Fleet Assignment Model) 模型,該模型以最大化航空公司利潤(rùn) 為目標(biāo)函數(shù).Sherali 等人[9]綜合了航班計(jì)劃和機(jī)隊(duì)分配模型,目標(biāo)函數(shù)是最大化航空公司收益,約束包括:航班覆蓋約束,飛機(jī)流約束,飛機(jī)資源約束和乘客需求約束等,求解過(guò)程用了 Benders 分解算法和 Polyhedral 分析.

國(guó)內(nèi)段曉江[10]等人綜合研究了機(jī)隊(duì)和航班計(jì)劃聯(lián)合優(yōu)化問(wèn)題,但是,模型中沒有考慮到乘客需求隨機(jī)性的影響.孫宏[11]等人綜合考慮了乘客不確定性需求,構(gòu)建了機(jī)型分配與飛機(jī)排班一體化的數(shù)學(xué)模型,實(shí)現(xiàn)了機(jī)隊(duì)集中調(diào)度.樂美龍[12]等人提出了一種多機(jī)型不正常航班恢復(fù)的時(shí)空網(wǎng)絡(luò)模型.

本文提出了一種基于時(shí)空網(wǎng)絡(luò)圖的航班機(jī)型分配模型和方法.基本思想是:在已知航空公司航班計(jì)劃、乘客需求分布、機(jī)隊(duì)結(jié)構(gòu)、機(jī)型數(shù)量的基礎(chǔ)上,首先通過(guò)構(gòu)建時(shí)空網(wǎng)絡(luò)圖得出航班機(jī)型分配模型所需的參數(shù),然后通過(guò)航班機(jī)型分配模型,得到使航班機(jī)型分配總成本最小的航班機(jī)型配置方案.

2 航班公司機(jī)型分配問(wèn)題

2.1 時(shí)空網(wǎng)絡(luò)概述

時(shí)空網(wǎng)絡(luò)中縱軸代表時(shí)間,橫軸代表機(jī)場(chǎng).網(wǎng)絡(luò)由若干個(gè)弧和結(jié)點(diǎn)構(gòu)成.網(wǎng)絡(luò)中的結(jié)點(diǎn)包含了機(jī)場(chǎng)在該時(shí)間結(jié)點(diǎn)的所有活動(dòng),包括飛機(jī)的起飛、降落、過(guò)夜等.進(jìn)入結(jié)點(diǎn)的弧表示在該時(shí)間段內(nèi)某架飛機(jī)降落該機(jī)場(chǎng),從結(jié)點(diǎn)出發(fā)的弧表示在該時(shí)間段內(nèi)某架飛機(jī)從該機(jī)場(chǎng)起飛.網(wǎng)絡(luò)中的弧表示航班.

2.2 時(shí)空網(wǎng)絡(luò)結(jié)構(gòu)

如圖1 所示,該時(shí)空網(wǎng)絡(luò)圖包含 4 個(gè)機(jī)場(chǎng),3種機(jī)型,其中,橫軸表示機(jī)場(chǎng),分別是機(jī)場(chǎng) A、機(jī)場(chǎng)B、機(jī)場(chǎng) C、 機(jī)場(chǎng) D. 縱軸表示時(shí)間, 從 10:00-17:00.連線(箭頭) 表示航段,結(jié)點(diǎn)表示某個(gè)機(jī)場(chǎng)在一天中某個(gè)特定時(shí)間航班的進(jìn)出港情況.圖中,折線(帶箭頭)表示地面連接線,用于將機(jī)場(chǎng)的最后一個(gè)結(jié)點(diǎn)與第一個(gè)(或非第一個(gè))結(jié)點(diǎn)連接起來(lái),這種線表示飛機(jī)在該機(jī)場(chǎng)過(guò)夜,它將某一天的最后一個(gè)進(jìn)港航班與第二天的出港航班銜接起來(lái),過(guò)夜期間可以對(duì)飛機(jī)進(jìn)行檢修及保養(yǎng).

圖1 時(shí)空網(wǎng)絡(luò)示例Fig.1 An example of time-space network

2.3 機(jī)型分配模型

集合:

F ——航班集合;

J ——機(jī)型集合;

C ——終止結(jié)點(diǎn)集合,且 C ? M;

M ——時(shí)空網(wǎng)絡(luò)中的所有結(jié)點(diǎn)集合;

下標(biāo):

i——航班下標(biāo),i∈ F;

j——機(jī)型下標(biāo),j∈ J;

k ——終止節(jié)點(diǎn)下標(biāo),k ∈ C;

m ——時(shí)空網(wǎng)絡(luò)中所有結(jié)點(diǎn)下標(biāo),m ∈ M.

參數(shù):

ci,j——用機(jī)型 j飛機(jī)執(zhí)飛航班 i的成本;

ck,j——機(jī)型 j的機(jī)組成員在終止結(jié)點(diǎn) k 所在機(jī)場(chǎng)的過(guò)夜成本;

Nj——機(jī)型 j的可用飛機(jī)數(shù)量;

Si,m=1——結(jié)點(diǎn) m 的航班 i是進(jìn)港航班;

Si,m=-1——結(jié)點(diǎn) m 的航班 i是出港航班;

CAPj——機(jī)型 j的容量;

Demandi——航班 i的平均需求量;

di——航班 i的航程;——結(jié)點(diǎn) k 所 在機(jī) 場(chǎng)在 時(shí)間 段內(nèi)最多降落飛機(jī)數(shù)量;——結(jié)點(diǎn) k 所在機(jī)場(chǎng)在時(shí)間段內(nèi)最多起飛飛機(jī)數(shù)量;

nk——結(jié)點(diǎn) k 所在機(jī)場(chǎng)的最小過(guò)夜飛機(jī)數(shù)量(目的保證航班正常運(yùn)營(yíng));

am,k=1——結(jié)點(diǎn) m 是終止結(jié)點(diǎn),即 m=k;

am,k=0——結(jié)點(diǎn) m 不是終止結(jié)點(diǎn),即 m ≠ k.

決策變量:

xi,j=1——航班 i分配給機(jī)型 j,否則,xi,j=0;

Gm,j——機(jī)型 j在結(jié)點(diǎn) m 的飛機(jī)數(shù)量(Gm-,j表示機(jī)型 j在結(jié)點(diǎn) m 的前一個(gè)結(jié)點(diǎn)的飛機(jī)數(shù)量); Gk,j——機(jī)型 j在終止結(jié)點(diǎn) k 的飛機(jī)數(shù)量.

模型:

目標(biāo)函數(shù)(1)表示最小化航班機(jī)型分配成本;約束(2)為航班覆蓋約束,確保任何一個(gè)航班都由一個(gè)機(jī)型來(lái)執(zhí)行;約束(3)為飛機(jī)平衡約束條件,確保任何一個(gè)結(jié)點(diǎn)的飛機(jī)流平衡;約束(4)為機(jī)型數(shù)量約束,保證每種機(jī)型過(guò)夜結(jié)點(diǎn)的數(shù)量之和不超過(guò)其最大數(shù)量;約束(5)為機(jī)型容量約束,確保各結(jié)點(diǎn)實(shí)際登記乘客人數(shù)小于等于飛機(jī)的最大容量;約束(6)為航程約束,確保各結(jié)點(diǎn)飛機(jī)的最大航程大于等于以該結(jié)點(diǎn)出發(fā)的航班的航程;約束(7)為結(jié)點(diǎn)單位時(shí)間段內(nèi)飛機(jī)到達(dá)約束,確保結(jié)點(diǎn) k所在機(jī)場(chǎng)在時(shí)間 段內(nèi)飛機(jī)到達(dá)數(shù)量不超過(guò)其最大到達(dá)能力限制;約束(8)為結(jié)點(diǎn)單位時(shí)間段內(nèi)飛機(jī)起飛約束,確保結(jié)點(diǎn) k 所在機(jī)場(chǎng)在時(shí)間段內(nèi)飛機(jī)起飛數(shù)量不超過(guò)其最大起飛能力限制;約束(9)為單位時(shí)間段內(nèi)結(jié)點(diǎn)所在機(jī)場(chǎng)的可用飛行跑道數(shù)量限制,確保結(jié)點(diǎn) k 在時(shí)間段內(nèi)占用飛機(jī)跑道的飛機(jī)不超過(guò)機(jī)場(chǎng)該時(shí)間段內(nèi)的可用飛行跑道數(shù)量;約束(10)為終止結(jié)點(diǎn)最小過(guò)夜飛機(jī)數(shù)量約束;約束 (11) 表 示 xi,j為 0-1 決 策變量,am,k為 0-1 協(xié)變量;約束(12)確保 Gm,j、 Gk,j為整數(shù).

3 算 例

該算例涉及 42 個(gè)航班,84 個(gè)結(jié)點(diǎn),3 種機(jī)型,8個(gè)機(jī)場(chǎng),航班計(jì)劃如表1所示.

表1 航班計(jì)劃Table1 The schedule of flights

續(xù)表

圖2 時(shí)空網(wǎng)絡(luò)Fig.2 The time-space network

3.1 構(gòu)建時(shí)空網(wǎng)絡(luò)圖

通過(guò) 2.2 節(jié)所述的時(shí)空網(wǎng)絡(luò)結(jié)構(gòu),運(yùn)用如下方法構(gòu)建圖2的時(shí)空網(wǎng)絡(luò)所示,并通過(guò)時(shí)空網(wǎng)絡(luò)數(shù)據(jù)用 C++語(yǔ)言編程輸出 Si,m、am,k.步驟如下:

Step1確定各機(jī)場(chǎng)所有航班的起飛和到達(dá)時(shí)間.

Step2將所有機(jī)場(chǎng)進(jìn)行編號(hào),L=1,2,3,…,8.

Step3將機(jī)場(chǎng) L=1 的所有航班起飛時(shí)間和降落時(shí)間按照時(shí)間順序進(jìn)行編號(hào),m=1,2,3,…,k;

If m=k 是從機(jī)場(chǎng) L=1 出發(fā)或到達(dá)機(jī)場(chǎng) L=1的最后一個(gè)航班結(jié)點(diǎn),則定義 k結(jié)點(diǎn)為機(jī)場(chǎng) L=1的終止結(jié)點(diǎn),k∈C,

else m 為任意結(jié)點(diǎn),且C? M.

Step4將機(jī)場(chǎng) L=2 的所有航班起飛時(shí)間和降落時(shí)間按照時(shí)間順序進(jìn)行編號(hào),m=k+1,k+2,…,k';

If m=k'是從機(jī)場(chǎng) L=2 出發(fā)或到達(dá)機(jī)場(chǎng) L= 2 的最后一個(gè)航班結(jié)點(diǎn),則定義 k'結(jié)點(diǎn)為機(jī)場(chǎng) L=2的終止結(jié)點(diǎn),k'∈ C,

else m 為任意結(jié)點(diǎn),且C? M;

for all(L=3,4,5,6,7,8)按照順序do(Step4).

Step5for all(m ∈ M)do

If m 為航班 i∈ F 的出港航班,則 Si,m=-1, else Si,m=1.

Step6for all(m ∈ M,k ∈ C)do

If m=k 為航班 i∈ F 的出港航班,則 am,k=1,

else am,k=0.

Step7輸出 C,M,Si,m,am,k.

3.2 乘客溢出量和航班機(jī)型分配成本的計(jì)算

三種機(jī)型 B737-800、B757-200、B767-200 的CASM(可用座公里成本) 分別為 0.042 美元、0.044 美元、0.043 美元,RASM(可用座公里收入)為 0.15 美元;三種機(jī)型的機(jī)組成員在非樞紐機(jī)場(chǎng)過(guò)夜的成本分別為 1200 美元、1400 美元、1 000美元,在樞紐機(jī)場(chǎng)過(guò)夜的成本分別為 500 美元、600美元、400 美元;可提供的飛機(jī)數(shù)量分別為 9 架、5架、2 架;機(jī)型容量分別為 162、200、214.乘客溢出量和航班機(jī)型分配成本的計(jì)算方法如下:

式(13) 為乘客溢出量的計(jì)算,Sspillover表示乘客溢出量,CAPj為機(jī)型 j∈ J 的容量,乘客的需求服從 (μ,ρ2) 的正態(tài)分布[13];式(14) 為航班機(jī)型分配成本的計(jì)算,包括兩部分:運(yùn)營(yíng)成本和溢出成本,rrecapture表示航空公司的再捕獲率 ( 即從某航班上溢出但是又可以轉(zhuǎn)簽到該航空公司其他航班上旅客人數(shù)的百分比),設(shè)定為 15%,各機(jī)場(chǎng)(按照順序)的最小過(guò)夜飛機(jī)數(shù)量為 2、2、0、5、0、0、0、0.

3.3 分配方案

通過(guò) IBM ILOG CPLEX 12.2 軟件對(duì)航班機(jī)型分配模型進(jìn)行求解,運(yùn)行環(huán)境為英特爾 酷睿2雙核 T6570@2.1GHz 筆記本處理器、5120MB 內(nèi)存、64 位 Windows 7 操作系統(tǒng),求解時(shí)間為 4.75 s.最小分配成本為 423 864.820 美元,分配方案如表2和表3所示.

表2 航班機(jī)型分配Table2 Airline fleet assignment

表3 機(jī)場(chǎng)過(guò)夜飛機(jī)數(shù)量_Table3 The number of overnight aircrafts at various airports

通過(guò)計(jì)算得出該航空公司的客座率達(dá)到85.55%,而通常情況下,航空公司的客座率不超過(guò)81.00% 左右.此時(shí),航空公司需求的總的飛機(jī)數(shù)量是 16 架,為了獲得更好的機(jī)隊(duì)配置組合,可以通過(guò)調(diào)整機(jī)隊(duì)的機(jī)型配置,以獲得總成本較小和客座率較高的配置方案.表4為部分配置方案的成本和客座率.從表中可以看出,雖然方案 9 的客座率不高,但是其機(jī)隊(duì)配置的總成本最小.此外,該表可以為航空公司的機(jī)隊(duì)規(guī)劃管理提供決策支持.各方案的航班機(jī)型配置表不再一一列出.

表4 機(jī)隊(duì)配置方案的成本與客座率Table4 The cost and seat kilometer utilization of fleet configuration schemes

4 研究結(jié)論

本文通過(guò)模擬航空公司運(yùn)營(yíng)環(huán)境中的航線網(wǎng)絡(luò)特征、航班計(jì)劃、乘客需求分布、機(jī)隊(duì)結(jié)構(gòu)、機(jī)型數(shù)量,提出了一種基于時(shí)空網(wǎng)絡(luò)的航班機(jī)型分配模型,并且通過(guò)乘客溢出量函數(shù)和航班機(jī)型分配成本函數(shù)準(zhǔn)確計(jì)算機(jī)型分配的成本.此外,目標(biāo)函數(shù)中考慮到了飛機(jī)機(jī)組人員在外過(guò)夜成本,與傳統(tǒng)的機(jī)型分配模型相比更加準(zhǔn)確詳細(xì).通過(guò)算例發(fā)現(xiàn),本文設(shè)計(jì)的機(jī)型分配方法的平均計(jì)算時(shí)間相對(duì)較短,為 4.40 s,且生成的分配方案的平均客座率相對(duì)較高,為 83.15%,能夠?yàn)楹娇展竞桨鄼C(jī)型分配提供決策支持.

[1] Brown J.Airline fleet composition and deregulation [J].Review of Industrial Organization,1992,8 (4):435-449.

[2] Hane C A,Barnhart C,Johnson E L,et al.The fleet assignment problem: Solving a large-scale integerprogram [J]. MathematicalProgramming, 1995,70(2):211-232.

[3] Bahram A,Garland C,Kambiz R.The effects of market structure and technology on airline fleet composition afterderegulation [J]. Review of Industrial Organization,1999,15(1):77-88.

[4] Barnhart C,Kniker T S,Lohatepanont M.Itinerarybased airline fleet assignment[J],Transportation Science,2002,36(2):199-217.

[5] Listes O,Dekker R.A scenario aggregation-based approach for determining a robustairline fleet composition fordynamiccapacityallocation [J]. Transportation Science,2005,39(3):367-382.

[6] Ahuja R K,Goodstein J,Mukherjee A,et al.A very large-scale neighborhood search algorithm forthe combined through-fleet-assignmentmodel[J].Informs Journal on Computing.2007,19(3),416-428.

[7] Sherali H D,Xiaomei Zhu.Two-stage fleet assignment model considering stochastic passengerdemands[J]. Operations Research,2008,56(2):383-399.

[8] Barnhart C,Farahat A,Lohatepanont M.Airline fleet assignment with enhanced revenue modeling[J]. Operations Research,2009,57(1):231-244.

[9] Sherali H D,Bae K H,Haouari M.Integrated airline scheduledesign and fleetassignment: polyhedral analysis and benders'decomposition approach[J]. Informs Journalon Computing. 2010, 22(4): 500-513.

[10] 段曉江,馮允成. 啟發(fā)式民用飛機(jī)機(jī)隊(duì)規(guī)劃[J]. 北京航 空 航 天 大 學(xué) 學(xué) 報(bào),1996,22(4):504-508. [DUAN X J,FENG Y C.Efficient heuristic algorithm to airline fleet planning[J]. Journal of Beijing University of Aeronautics and Astronautics,1996,22 (4):504-508.]

[11] 孫宏,張翔,徐杰. 航空公司機(jī)隊(duì)集中調(diào)度理論研究[J].中國(guó)管理科學(xué),2008,16(1):86-89.[SUN H, ZHANG X,XU J.The theory of integrated airline fleet dispatching[J].Chinese Journal of Management Science,2008,16(1):86-89.]

[12] 樂美龍,王婷婷,吳聰聰.多機(jī)型不正常航班恢復(fù)的時(shí)空網(wǎng)絡(luò)模型[J].四川大學(xué)學(xué)報(bào)(自然科學(xué)版), 2013,50(3):477-483.[LE M L,WANG T T,WU C C.The time-band model for recovery of multi-type aircrafts'disrupted flights[J].Journal of Sichuan University(Nat Sci Ed),2013,50(3):477-483.]

[13] T S Kniker, C Barnhart. Shortcomings ofthe conventional airline fleet assignment model[C].In Proceeding:Tristan Ⅲ,pages 17-23,Puero Rico, June 1988.

Airline Fleet Assignment Model Based on Time-space Network

LE Mei-long,HUANG Wen-xiu
(Academy of Science,Shanghai Maritime University,Shanghai 201306,China)

The fleet planning is an important prerequisite for the airlines'efficient operations.A method is provided for the airline fleet assignment model,which is based on a time-space network,a function of passengers'spillover,and a cost function of airline fleet assignment.Based on the known conditions of airline's flight planning,passengers'demand distribution,fleet structure and the number of aircraft types, the parameters of airline fleet assignment model are obtained from the time-space network.The new schemes of minimizing the cost of airline fleet assignment and fleet configuration are got by solving the airline fleet assignment model.The instance verifies the method to be scientific and effective.It provides the foundations for decision making of airline fleet assignment.

air transportation;airline fleet assignment;time-space network;aircraft types;flights

1009-6744(2014)01-0081-07

N945.15

A

2013-07-15

2013-09-30錄用日期:2013-10-23

上海市自然科學(xué)基金創(chuàng)新行動(dòng)計(jì)劃項(xiàng)目(10190502500);上海市科委工程中心項(xiàng)目(09DZ2250400);上海市教委重點(diǎn)學(xué)科項(xiàng)目(J50604).

樂美龍(1964-),男,浙江寧波人,教授,博士生導(dǎo)師.*通訊作者:meilongle@hotmail.com