從航線頻率到航班排班的大規(guī)模規(guī)劃問題初步研究

蔣韻爾　張偉

摘 要：為了構建更合理的航班排班規(guī)劃，實現(xiàn)更精確的航線網(wǎng)絡運力優(yōu)化分配，獲得更大的航線收益，該文建立以航線收益最大化為目標，以航班頻率為決策變量，并考慮航空公司的資源和限制的線性規(guī)劃模型。為提高計算效率，將模型分解為航線級和飛機級，分步進行優(yōu)化，簡化大規(guī)模運算，并保證優(yōu)化結果的延續(xù)性。以上海浦東為運營基地的5架飛機10條航線為例，說明分步實現(xiàn)規(guī)劃的依據(jù)和意義，得到細化到飛機級的周航班頻率，并據(jù)此進行航班排班。

關鍵詞：航空運輸 航線頻率 航班排班 線性規(guī)劃

中圖分類號：F560 文獻標識碼：A 文章編號：1674-098X（2015）11（c）-0032-03

隨著航空運輸業(yè)的日趨成熟，航空公司運營面臨著更多的競爭，對于航線網(wǎng)絡規(guī)劃與航班排班的要求不斷提升。航班計劃是對航空公司的有限資源（飛機、航線、人員及資金等）進行配置，確定正班飛行的航線、機型、飛行班次和班期時刻[1]可以說航班計劃是航空公司的服務產品，又是航空公司組織運輸?shù)幕A，是其他一切與生產相關計劃的依據(jù)。充分利用航空公司的資源，確定最優(yōu)化的航班計劃，對于航空公司的運營至關重要。且布局合理、管理科學、運轉高效的航線網(wǎng)絡對民航運輸業(yè)的生產和發(fā)展具有重要的戰(zhàn)略意義。

現(xiàn)有國內關于航空優(yōu)化的理論研究和實踐都還處于起步和探索階段，大多還停留在定性分析和比較上，基于市場結構分析、旅客需求、航線決策等影響因素，或通過統(tǒng)計主要航空公司數(shù)據(jù)，對航線規(guī)劃進行宏觀層面的分析[2-5]。較缺乏基于定量模型的分析，特別是完整、全面地研究航班計劃編制和優(yōu)化過程的研究還很缺乏。且傳統(tǒng)的航線網(wǎng)絡規(guī)劃通常以成本最小為目標，這種做法可能會限制機隊的規(guī)劃，無法實現(xiàn)利潤的最大化[6-7]。

綜上所述，現(xiàn)有研究缺乏以實現(xiàn)資源利用最大化為目標的航班計劃定量分析。該文針對以上不足，通過建立線性規(guī)劃模型，以收益最大化為目標，對已有資源進行充分利用，分步進行求解，得到最優(yōu)化的航班頻率，進行收益優(yōu)化的航班排班，從而實現(xiàn)更精確的航線網(wǎng)絡運力優(yōu)化分配。

1 研究方法

線性規(guī)劃方法是輔助人們進行科學管理的一種數(shù)學方法，研究線性約束條件下線性目標函數(shù)的極值問題的數(shù)學理論和方法，能為合理地利用有限的人力、物力、財力等資源作出的最優(yōu)決策，提供科學的依據(jù)。線性規(guī)劃問題可描述為求線性目標函數(shù)在線性約束條件下的最大值或最小值的問題，決策變量、約束條件、目標函數(shù)是線性規(guī)劃的三要素，圖1是線性規(guī)劃問題的求解步驟示意。

航班計劃于航空公司而言即對其已有的有限資源進行充分利用，使利益最大化，因此可以通過以航班周頻率作為決策變量，考慮航空公司運營時的條件與限制作為約束條件，建立線性規(guī)劃模型，并進行最優(yōu)化求解，得到利潤優(yōu)化的航班排班結果。

2 航班頻率模型

對于航空公司而言，實現(xiàn)利潤最大化是其最基本的經(jīng)營目標，因此建立航班頻率優(yōu)化模型時，以“機隊在所運營的航線網(wǎng)絡上的運營利潤最大化”為目標，航班周頻率為決策變量，考慮航線客座率、票價、運營成本，得到最優(yōu)的航班頻率規(guī)劃。

機隊的運力條件應能覆蓋各條航線的執(zhí)飛時間，因此機隊在各航線的運營時間應小于可用的有效飛行時間；為保證良好的運營環(huán)境，局方對于航線的執(zhí)飛頻率有一定的限制，因此每一條航線上的航班數(shù)量不得溢于局方審批的數(shù)量；維修計劃是航班計劃制定需考慮的內容，根據(jù)有關規(guī)定，A檢的間隔時間是800小時，遠大于一周的時間，而該模型以航線周頻率為決策變量，因此考慮通過運力備份來實現(xiàn)。運力備份還包含對突發(fā)事件的冗度，因此對總可用飛行時間保留10%的裕度；為使每一架機得到充分利用，避免個別飛機的過度使用，因此對每架飛機的周飛行時間設定上下限。綜上，在進行航線規(guī)劃優(yōu)化時需要綜合考慮以下約束條件：

3 模型分解

以上模型需進行大規(guī)模運算，需要耗費大量的時間得到最優(yōu)解。因此在實際工作中需對其進行分解。正如同勢能做功，只和初始、最終狀態(tài)相關，而無關乎過程，在進行航班排班時，若將工作分為航線級和飛機級兩層，同樣能實現(xiàn)航班頻率的優(yōu)化。

首先建立航線級頻率優(yōu)化模型，對每一條航線上的航班頻率進行求解，以利潤最大化為目標函數(shù)。得到每一條航線的機隊執(zhí)飛周頻率后，再分配至機隊的每一架機，實現(xiàn)飛機級的航班頻率規(guī)劃。通過將任務分解，分步進行優(yōu)化，能對大規(guī)模運算進行簡化，同時保證優(yōu)化結果的延續(xù)性。

4 案例分析

以上海浦東為運營基地，對10條航線，5架158座飛機的運營計劃進行飛機級規(guī)劃。具體備選航線和飛機的運營情況如表1所示，航線的選擇依據(jù)現(xiàn)有的航線頻率并滿足運營假設條件。

根據(jù)運營的實際情況和飛機的經(jīng)濟技術性能，分步建立目標函數(shù)，首先進行航線級航班頻率規(guī)劃，得到航線周頻率后，再將每條航線上的飛行頻率分配至不同飛機。由于前一步已實現(xiàn)利潤目標的優(yōu)化，在進行飛機級航班頻率規(guī)劃時無需建立目標函數(shù)，而是滿足下列條件：

在此結果基礎上，采用航班排班工具（見圖2）對航班時間進行安排，得到符合民航局過站時間（見表2，其中北京、浦東、廣州、深圳、重慶、西安屬于特殊機場）和航段標航時間規(guī)定的航班計劃。

5 結語

該文從航空公司運營角度出發(fā)，以航線利潤為目標，航班周頻率為決策變量，建立航班頻率優(yōu)化模型。為更方便使其適用于航空公司實際航線運營，將模型分解為兩部分，先根據(jù)航空公司運力限制以及局方航線頻率規(guī)定、求得航線級周頻率，再根據(jù)充分利用每一架飛機的原則將其分配至飛機級。通過以浦東機場為主運營基地的東航5架飛機10條航線網(wǎng)絡排班規(guī)劃案例，系統(tǒng)地描述了模型的整個實現(xiàn)過程。該文可作為航空公司航線網(wǎng)絡規(guī)劃工作的一部分，為決策者提供理論支持。

但該文的研究還存在一些不足。在航空公司的實際運營中，會面臨著復雜得多的情況，存在更多的運營或政策限制條件，此模型是不適于直接用于實際航班排版工作，需根據(jù)實際運營情況作相應調整。此外，與直接規(guī)劃至飛機級相比，將模型進行分解雖能節(jié)省運算時間，但需要一定的轉換步驟，則可能存在一定的誤差。后續(xù)研究可針對該研究的不足之處，進行更深入的計算和分析，并逐步發(fā)展為完整的航班計劃和優(yōu)化成熟理論流程和軟件產品，使國內的航空運輸市場成為真正成熟、合理、完善的市場。

參考文獻

[1] 都業(yè)富.實用航班計劃優(yōu)化方法[J].系統(tǒng)工程理論與實踐，1995，12（2）：23-27.

[2] 李福娟.基于航線決策的航班計劃優(yōu)化研究[D].上海：同濟大學經(jīng)濟與管理學院，2007.

[3] Adrang LB，Chow G，Raffiee K.The effects of market structure and technology on airline fleet composition after deregulation[J].Review of Industrial Organization，1999，15（1）：77-88.

[4] Seristo H， Vepsalainen A P J.Airline cost drivers cost implications of fleet，routes，and personnel policies[J].Journal of Air Transport Management，1997，3（1）：11-22.

[5] Hsu CI，Wen Y H.Application of grey theory and multi-objective programming towards airline network design[J].European Journal of Operational Research，2000，127（1）：44-68.

[6] 彭語冰，張永莉，張曉全.機隊規(guī)劃模型的建立及其應用[J].系統(tǒng)工程理論與實踐，2001（6）：100-103.

[7] 李福娟，王魯平，劉仲英.優(yōu)化理論與技術在航空領域的應用[J].計算機應用與軟件，2004，21（4）：45-47.