基于航班純度的魯棒性機型指派問題研究

摘 要：機型指派問題(FAP)是指根據飛機艙位能力、運營成本、潛在收益及飛機可用性，將具有不同艙位容量的飛機指派給各定期航班的問題。它是飛機、機組排班問題的基礎，是整個航班計劃中的最核心環節。然而，單獨的機型指派最優對整個航班計劃而言，可能是次優的，甚或是不可行的。本文針對國內航班計劃特點，從航班的角度，定義了航班純度概念，并建立基于航班純度的機型指派模型。最后，以國內某航空公司干線網絡為實例，表明該研究具有很大的理論意義和實踐價值。

關鍵詞： 航班計劃；機型指派；航班純度

中圖分類號：F560 文獻標識碼：A 文章編號：1003-5192(2011)01-0071-04

The Research on Robust Fleet Assignment Problem Based on Flight Purity

ZHU Xing-hui， ZHU Jin-fu， GAO Qiang

(College of Civil Aviation， Nanjing University of Aeronautics Astronautics， Nanjing 210016， China)

Abstract:The airline fleet assignment deals with assigning aircraft types to the scheduled flight legs based on aircraft capabilities， operational costs， potential revenues and aircraft availabilities. An airline’s fleet assignment decision is essential component of its overall scheduling process. However， an optimal solution for the fleet assignment is not necessarily optimal for the entire flight scheduling system， and can even yield an infeasible input to the subsequent processes， such as aircraft maintenance routing. This paper presents the notion of flight purity and builds fleet assignment model subjected to flight purity according to the characters of domestic airline network and flight scheduling. At last， the instance with 48 aircrafts and 1786 flight legs were testified， and the computational results reveal that theoretical value and practical significance of the research.

Key words:flight scheduling; fleet assignment; flight purity

1 引言

機型指派問題(Fleet Assignment Problem:FAP)是指根據不同機型具有不同的艙位數量，運行成本和潛在收益，指派不同的飛機類型給定期航班［1］。它是航空公司航班計劃的核心內容之一，機型指派的優劣不僅影響到航空公司的成本和收益，也影響到航班之間的銜接、飛機維修路徑、機組排班以及登機口、停機位指派等后續環節。

在國外，航空運輸發達，機型指派研究資料很充分，但主要集中于樞紐航線網絡和日航班計劃。Hanif［1］等對機型指派問題的模型及求解算法進行了綜述研究。機型指派基本模型有鏈接網絡［2］(Connection Network)和時空網絡［3］(Time-space Network)模型。為減少機型指派問題規模，Hane［4］對時空網絡提出了節點縮減(Node Aggregation)和孤島(Island)等預處理方法。Rexing［5］等將航班時刻綜合考慮，建立了基于“時間窗”的機型指派模型。Barnhart［6］和Jonathan［7］分別從旅客行程結構和網絡效應構建了機型指派模型。在國內，定量研究不多，孫宏［8，9］等對飛機排班問題進行了比較詳細的研究，但其問題規模相對較小；朱星輝［10，11］等對競爭環境下航班頻率和針對國內航線網絡和航班計劃特點的周機型指派模型進行了研究。在機型指派魯棒性方面，國內尚未見公開發表的文獻；國外Barry［12］等從機場純度(Station Purity)的角度，建立了魯棒性機型指派模型，即要求每種機型涉及的機場盡量集中。本文借鑒他的思路，從航班的角度，建立基于航班純度的魯棒性機型指派模型。

國內航班計劃均以周為單位周期進行編排，航班純度的概念即要求對一個周期內具有相同航班號不同天的航班(每天航班的離港時間點往往相同)盡可能指派同一種機型。機型指派是飛機、機組排班的基礎，航班純度考慮不僅有利于不正常航班情況下飛機的調整、方便停機位安排，而且有利于維護飛行員飛行任務的穩定性等。因此，機型指派航班純度的提高，能極大地改善機型指派的魯棒性。

2 模型建立

與連接網絡相比，時空網絡更方便航班之間銜接，因此本文選擇建立時空網絡G(Nk，Ak)［10］，節點Nk表示機場與時間軸的二維時空點，弧Ak表示航班段。對于同一航班號上的不同天航班，本文定義一種主機型，例如某航班(航班號N257)一周飛行七班，即每天一班，其中有四班由機型A執行，兩班由機型B執行，一班由機型C執行，則我們定義機型A為航班(號)N257的主機型，其它機型定義為輔助機型，即N257航班純度為4/7(57.14%)，為提高航班純度，為輔助機型設置罰函數。模型參數具體說明如下：

(1)式為收益最大化目標函數；(2)式為覆蓋約束，要求每個航班段指派一種且只有一種機型;(3)、(4)式為機型航班純度約束，其中(3)為每一個航班號定義一種且只有一種主機型，(4)表示變量之間的邏輯關系，即當航班段i指派的機型k不是該航班號l(i)上的主機型，則航班段i上的機型必為輔助機型；(5)式為飛機守恒約束，要求周期結束時各機型在各機場飛機數分布與周期開始時一樣；(6)式表示飛機可用性約束，即如果Xkj=1，則保證在航班段j離港時至少有一架k機型飛機在機場待命；(7)式為機隊規模約束，即飛機架次限制，該約束與(6)式一起保證了各機場飛機守恒約束；(8)式為飛機利用率約束；(9)式為指派飛機的座位容量約束；(10)式表示經停航班約束，即要求一次經停航班的兩個航班段指派相同機型。

3 實例計算

以國內某航空公司干線航班網絡為例，進行驗證分析。該公司有48架飛機干線飛機，根據飛機型號及座位數分為5種機型，執行54個機場，每周250個航班(號)，共1786個航班段，其中包括544個一次經停航班段。機型成本根據各機型實際總運行成本估算得出，見表1。

航班段的航班號，離港、到港時間和離港、到港機場由該公司航班時刻表讀取，各航班段最大旅客溢出量均取i.spill=0.1，航班段旅客量由預測得出，平均票價為電子客票價格，再由德爾菲法考慮一定折扣最終確定。對輔助機型懲罰值γ很難界定，因此本文對不同懲罰值進行測試，結果見表2。

從表2可以看出當γ=0時，即沒有考慮航班的機型純度，最優目標函數值為84422052元，即為文獻［10］的結論；隨著γ增大，輔助機型減少，航班的機型純度提高，而最優目標值在減少。但即使設置很大的懲罰值如γ=10000，目標值比實際收益還多出449963元，相對提高了0.54％(推算每年增加利潤超過2千萬)，輔助機型航班段數降到53個，航班純度達到97.03％，而實際問題航班純度僅為94.74％，提高了2.29％。因此，該模型不僅提高了航班純度，改善了機型指派的魯棒性，同時也提高了收益。進一步對γ=10000時單個航班純度進行了分析，每個航班號最多指派了兩種機型；航班純度最低為50％，主要是存在兩個航班號(占0.8%)每周只有兩班（如某航班號班期為周二、周五），而指派了不同的機型；共有218(占87.20%)個航班號的航班純度達到100％，優化效果十分理想。

4 結論

本文根據國內航線網絡及以周為單位周期編制航班計劃的特點，借鑒機場純度的概念，提出了航班純度的概念；同時，指出航班純度的提高，能極大地改善機型指派的魯棒性，有利于不正常航班情況下飛機的調整、方便停機位安排，而且有利于維護飛行員飛行任務的穩定性，因此本文建立基于航班純度的魯棒性機型指派模型。最后，以國內某航空公司干線航班網絡進行實例分析。結果表明，不僅可以提高航班純度，改善機型指派魯棒性，還可以提升公司的收益水平，因此，該模型不僅可為航空公司機型指派決策提供參考，也為航班計劃系統開發奠定理論基礎，該研究具有很大理論價值和現實指導意義。

參 考 文 獻：

［1］Hanif D S， Ebru K B， Zhu Xiaomei. Airline fleet assignment concepts， models， and algorithms［J］. European Journal of Operational Research， 2006， 172(1): 1-30.

［2］Abara J. Applying integer linear programming to the fleet assignment problem［J］. Interfaces， 1989， 19(4): 20-28.

［3］Berge M E， Hopperstad C A. Demand driven dispatch: a method for dynamic aircraft capacity assignment， models and algorithms［J］. Operational Research， 1993， 41(8): 153-168.

［4］Hane C A， Barnhart C， Johnson E L， et al.. The fleet assignment problems: solving a large-scale integer program［J］. Mathematical Programming， 1995， 70(2): 211-232.

［5］Rexing B， Barnhart C， Kniker T. Airline fleet assignment with time windows［J］. Transportation Science， 2000， 34(1): 1-20.

［6］Barnhart C， Kniker T S， Lohatepanont M. Itinerary-based airline fleet assignment［J］. Transportation Science， 2002， 36(1): 199-217.

［7］Jonathan D， Fati A， Fran S. Improving the objective function of the fleet assignment problem［J］. Transportation Research Part B， 2009， 43(2): 466-475.

［8］孫宏，杜文.應用網絡流模型解決航班銜接問題［J］.西南交通大學學報，2002，37(2):223-226.

［9］孫宏，杜文.航空公司飛機排班問題的分階段指派算法［J］.系統工程學報，2003，18(2):168-172.

［10］朱星輝，朱金福，姜濤.我國航空公司機型指派模型及算法研究［J］.工業技術經濟，2007，26(4):75-77.

［11］朱星輝，朱金福，姜濤.分階段多航空公司競爭下航班頻率研究［J］.預測，2007，26(5):71-74.

［12］Barry C S， Ellis L J. Robust airline fleet assignment: imposing station purity using station decomposition［J］. Transportation Science， 2006， 40(4): 497-516．