樂美龍,黃文秀

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

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

樂美龍*,黃文秀

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

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

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

1 引 言

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

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

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

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

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

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

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

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

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

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

2.3 機(jī)型分配模型

集合:

F ——航班集合;

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

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

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

下標(biāo):

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

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

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

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

參數(shù):

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

ck,j——機(jī)型 j的機(jī)組成員在終止結(jié)點 k 所在機(jī)場的過夜成本;

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

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

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

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

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

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

nk——結(jié)點 k 所在機(jī)場的最小過夜飛機(jī)數(shù)量(目的保證航班正常運營);

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

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

決策變量:

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

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

模型:

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

3 算 例

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

表1 航班計劃Table1 The schedule of flights

續(xù)表

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

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

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

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

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

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

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

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

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

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

else m 為任意結(jié)點,且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ī)型 B737-800、B757-200、B767-200 的CASM(可用座公里成本) 分別為 0.042 美元、0.044 美元、0.043 美元,RASM(可用座公里收入)為 0.15 美元;三種機(jī)型的機(jī)組成員在非樞紐機(jī)場過夜的成本分別為 1200 美元、1400 美元、1 000美元,在樞紐機(jī)場過夜的成本分別為 500 美元、600美元、400 美元;可提供的飛機(jī)數(shù)量分別為 9 架、5架、2 架;機(jī)型容量分別為 162、200、214.乘客溢出量和航班機(jī)型分配成本的計算方法如下:

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

3.3 分配方案

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

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

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

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

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

4 研究結(jié)論

本文通過模擬航空公司運營環(huán)境中的航線網(wǎng)絡(luò)特征、航班計劃、乘客需求分布、機(jī)隊結(jié)構(gòu)、機(jī)型數(shù)量,提出了一種基于時空網(wǎng)絡(luò)的航班機(jī)型分配模型,并且通過乘客溢出量函數(shù)和航班機(jī)型分配成本函數(shù)準(zhǔn)確計算機(jī)型分配的成本.此外,目標(biāo)函數(shù)中考慮到了飛機(jī)機(jī)組人員在外過夜成本,與傳統(tǒng)的機(jī)型分配模型相比更加準(zhǔn)確詳細(xì).通過算例發(fā)現(xiàn),本文設(shè)計的機(jī)型分配方法的平均計算時間相對較短,為 4.40 s,且生成的分配方案的平均客座率相對較高,為 83.15%,能夠為航空公司航班機(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ī)隊規(guī)劃[J]. 北京航 空 航 天 大 學(xué) 學(xué) 報,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ī)隊集中調(diào)度理論研究[J].中國管理科學(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ù)的時空網(wǎng)絡(luò)模型[J].四川大學(xué)學(xué)報(自然科學(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)新行動計劃項目(10190502500);上海市科委工程中心項目(09DZ2250400);上海市教委重點學(xué)科項目(J50604).

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