黃國輝

(廈門航空有限公司，福建廈門361000)

近年來，中國民航運(yùn)輸業(yè)呈現(xiàn)快速發(fā)展趨勢(shì)，根據(jù)《2020年民航行業(yè)發(fā)展統(tǒng)計(jì)公報(bào)》[1]，截至2020年底，中國大陸已有64家運(yùn)輸航空公司、3 903架運(yùn)營飛機(jī)、5 581條執(zhí)飛定期航班航線.對(duì)于各家航空公司而言，飛機(jī)是重資產(chǎn)、航權(quán)時(shí)刻是關(guān)鍵資源，企業(yè)核心目標(biāo)是在飛機(jī)投入最小化的情況下，高效利用航權(quán)時(shí)刻資源，編排出最優(yōu)的航線網(wǎng)絡(luò)，最終實(shí)現(xiàn)經(jīng)營利潤最大化.因此，制定合理的航班計(jì)劃對(duì)提升航空公司市場(chǎng)競(jìng)爭力有著重要作用.航季航班計(jì)劃編制是一項(xiàng)非常復(fù)雜而繁重的工作，操作難點(diǎn)在于飛機(jī)機(jī)型指派和飛機(jī)連線銜接[2-4].目前，國內(nèi)大部分航空公司還是借助人工來完成這兩項(xiàng)業(yè)務(wù)，操作效率和編排質(zhì)量都較低.行業(yè)主流的航班編排系統(tǒng)基本都被歐美公司壟斷，國內(nèi)航空公司不得不高額采購引進(jìn)這些系統(tǒng)，不僅維護(hù)成本極高，而且無法根據(jù)國內(nèi)航空公司的實(shí)際業(yè)務(wù)優(yōu)化系統(tǒng)功能，存在較大的應(yīng)用局限性.Zhou[5]整理綜述了機(jī)型指派(FAP)、飛機(jī)路徑(ARP)和機(jī)組排班(CSP)等航空公司計(jì)劃和調(diào)度問題的解決方法，并指出航班調(diào)度仍是當(dāng)前主要難題.都業(yè)富[6]在航班串優(yōu)化的研究中提出航班銜接是評(píng)價(jià)航線調(diào)度優(yōu)化效果的重要因素.肖東喜等[7]認(rèn)為飛機(jī)連線問題是航班環(huán)構(gòu)建的實(shí)際體現(xiàn)，飛機(jī)連線的自動(dòng)銜接有助于降低航空公司構(gòu)建航班環(huán)的難度，進(jìn)而提高航線計(jì)劃的效率.于焯等[8]引入等圖的概念，構(gòu)造航線調(diào)配狀態(tài)圖，將飛機(jī)航線調(diào)配問題等價(jià)為等圖的路徑査找問題.孫宏[9]用二部圖來描述航節(jié)銜接問題，并通過Ford Fulkerson算法進(jìn)行求解.然而，當(dāng)前研究主要用于解決單樞紐(或基地)航線網(wǎng)絡(luò)的航班銜接問題，無法完全滿足多樞紐、固定連線等復(fù)雜的實(shí)際需求.加權(quán)二部圖算法是在二部圖的基礎(chǔ)上，給邊賦予權(quán)重，以實(shí)現(xiàn)不同優(yōu)先級(jí)別的目標(biāo)實(shí)現(xiàn)[10]，張紹陽等[11]利用加權(quán)二部圖最優(yōu)匹配算法研究了中文段落相似度的匹配查重問題，但該算法還比較少應(yīng)用于解決航線優(yōu)化問題.

綜合考慮機(jī)型指派、飛機(jī)路線問題，朱星輝等[12]建立了基于列生成算法的一體化飛機(jī)排班模型.但該模型是基于以天為單位的航班計(jì)劃(即每天的航班計(jì)劃都相同)，飛機(jī)數(shù)量和航班數(shù)量均較少.而在實(shí)際應(yīng)用場(chǎng)景，國內(nèi)中大型航空公司機(jī)隊(duì)數(shù)量達(dá)數(shù)百架，每周航班數(shù)量高達(dá)數(shù)千個(gè)，如果用一體化模型求解，建模和求解的復(fù)雜性將倍增，求解效率根本無法滿足航季航班計(jì)劃編制過程中快速模擬的需求.如Ahmed等[13]基于美國聯(lián)合航空公司的航班網(wǎng)絡(luò)，考慮航班計(jì)劃魯棒性，建立了綜合機(jī)型指派、連線銜接、機(jī)組排班等一體化的模型，該案例解決了超過200架飛機(jī)的航班排班問題，但需要數(shù)小時(shí)的求解時(shí)間；Sanchez等[14]利用啟發(fā)式算法建立了考慮飛機(jī)維修計(jì)劃的一體化飛機(jī)排班模型，該模型求解529架飛機(jī)的排班問題也需要2 h.結(jié)合相關(guān)領(lǐng)域的前沿算法，尋找有效的解決方案仍是目前亟待解決的一個(gè)重要難題.

由于國內(nèi)民航市場(chǎng)規(guī)模大、變化速度快，且政府監(jiān)管頻率較高，意味著航班優(yōu)化調(diào)整的效率對(duì)航空公司而言極為重要.因此，本文以使用飛機(jī)數(shù)量最小化和收益貢獻(xiàn)最大化為目標(biāo)，采取兩階段方式解決機(jī)型指派和連線銜接的問題.首先，利用時(shí)空網(wǎng)絡(luò)圖完成機(jī)型指派，明確最少的使用飛機(jī)數(shù)量，為飛機(jī)連線銜接確定機(jī)型基礎(chǔ).其次，采用加權(quán)二部圖算法來解決航線銜接問題，根據(jù)連線銜接的目的不同，設(shè)計(jì)不同的銜接權(quán)重，求解滿足要求的銜接方案.為了與加權(quán)二部圖算法作對(duì)比，本文在第二階段加入二部圖、先進(jìn)先出、后進(jìn)先出等連線銜接算法，并通過橫向、縱向?qū)Ρ炔煌惴ǖ目尚行耘c適用性.

1 問題描述和數(shù)學(xué)建模

1.1 問題描述

在國內(nèi)民航運(yùn)輸業(yè)，每年分為兩個(gè)航季，即夏航季(每年3月的最后一個(gè)星期日至10月的最后一個(gè)星期日的前一天)和冬航季(每年10月的最后一個(gè)星期日開始到第二年3月的最后一個(gè)星期日的前一天).每次換季都要重新制定航班計(jì)劃，包括航班日期、航線、航班號(hào)、起降時(shí)刻、機(jī)型、連線編號(hào)等要素.其中：1) 航班日期是指每個(gè)航班在第一個(gè)起飛機(jī)場(chǎng)的起飛日期；2) 航線是指航空公司開展經(jīng)營活動(dòng)所運(yùn)營的航班路線，比如，廣州-上海、廈門-舟山-北京；3) 航班號(hào)是一天中區(qū)分不同航班的唯一標(biāo)識(shí)，比如，南航廣州-上海CZ3533；4) 起降時(shí)刻是指航班在起點(diǎn)機(jī)場(chǎng)、終點(diǎn)機(jī)場(chǎng)和經(jīng)停機(jī)場(chǎng)的起飛及降落時(shí)刻；5) 機(jī)型指用于執(zhí)飛該航班的飛機(jī)型號(hào)，比如波音B787、空客A321；6) 連線編號(hào)是指每架飛機(jī)執(zhí)飛任務(wù)的編號(hào)，即同一架飛機(jī)執(zhí)飛不同的航班，這些航班均屬于同一個(gè)連線編號(hào)，比如有3架A321飛機(jī)，那么這3架飛機(jī)連線編號(hào)為A321_01、A321_02、A321_03.

通常情況下，新航季航班計(jì)劃編制是在前一個(gè)同航季航班計(jì)劃的基礎(chǔ)上(比如2021年冬航季是基于2020年冬航季)，根據(jù)航空公司的機(jī)隊(duì)規(guī)劃、航權(quán)、時(shí)刻等資源情況和市場(chǎng)預(yù)期效益進(jìn)行優(yōu)化調(diào)整.因此，新航季會(huì)有部分航班是延續(xù)前一個(gè)同航季的航班計(jì)劃，但多數(shù)航班會(huì)根據(jù)市場(chǎng)和資源爭取情況做調(diào)整.這里的航季航班計(jì)劃是以周為單位制定，即只要編制出一周的航班計(jì)劃，再將其復(fù)制到后續(xù)周期，就可以形成整個(gè)航季的航班計(jì)劃.

在航班計(jì)劃編制過程中，第一步是機(jī)型指派.主要是滿足運(yùn)行約束的前提條件下分配機(jī)型，使航班收益貢獻(xiàn)最大化.即考慮兩個(gè)因素：1) 運(yùn)行限制.不同型號(hào)的飛機(jī)具有不同的飛行性能(如航程、最大起飛重量、發(fā)動(dòng)機(jī)推力等)，不同性能的飛機(jī)決定了該機(jī)型可以執(zhí)飛的航班.比如：B737、A320等短航程機(jī)型就不能執(zhí)飛國內(nèi)到洛杉磯等長航程的洲際航線.2) 預(yù)期效益.不同機(jī)型的運(yùn)營成本存在差異，不同座艙布局的飛機(jī)載客能力也不同，同一架飛機(jī)執(zhí)飛不同航班產(chǎn)生的收益貢獻(xiàn)也不同，故航班計(jì)劃編排也要綜合考慮預(yù)期效益.這里的收益貢獻(xiàn)是指航空公司從事經(jīng)營活動(dòng)所獲得的稅后收入減去使用某種機(jī)型執(zhí)飛的變動(dòng)成本，是衡量航班盈利能力的重要指標(biāo).

第二步是連線銜接.在確定每個(gè)航班的執(zhí)飛機(jī)型后，兩個(gè)航班能實(shí)現(xiàn)銜接的前提是滿足以下兩條規(guī)則：1) 同機(jī)場(chǎng)，即前序航班的落地機(jī)場(chǎng)要與后續(xù)航班的起飛機(jī)場(chǎng)相同.2) 滿足最小過站時(shí)間，即前序航班降落與后續(xù)航班起飛之間在機(jī)場(chǎng)的停留時(shí)間要滿足最小過站時(shí)間標(biāo)準(zhǔn).除了最基本的銜接原則外，航空公司在編制航班計(jì)劃時(shí)，也會(huì)根據(jù)實(shí)際業(yè)務(wù)需求增加航班銜接要求，常見的有3類：1) 保留原始銜接.航季航班計(jì)劃編排并不是完全從零開始，有部分航班計(jì)劃是延續(xù)上一個(gè)同航季的航班計(jì)劃，這些航班保留了部分銜接信息甚至機(jī)組排班信息.2) 保留往返銜接.往返航班銜接是指從出發(fā)地到達(dá)目的地，然后再從目的地返回出發(fā)地的兩個(gè)航班之間的銜接.這不僅利于機(jī)組排班，還可以減少機(jī)組在外站的過夜費(fèi)用，對(duì)航空公司控制成本有重要意義.3) 緊湊銜接.航季航班計(jì)劃會(huì)盡可能用最少的飛機(jī)數(shù)量編排最多的航班，使整個(gè)航班計(jì)劃的飛機(jī)利用率最高.在此過程中，航空公司通常會(huì)將較短過站時(shí)間的兩個(gè)航班優(yōu)先銜接，使得編排的航班計(jì)劃更為緊湊，可以集中利用空檔運(yùn)力，有利于增加航班執(zhí)飛量，提高飛機(jī)利用率.如圖1所示，假設(shè)最小過站時(shí)間為60 min，航班A、C的落地機(jī)場(chǎng)與航班B、D的起飛機(jī)場(chǎng)相同，圖1(a)中航班A與航班B的銜接過站時(shí)間為3 h，航班C與航班D的銜接過站時(shí)間為4 h，這兩個(gè)過站時(shí)間均較短，新增航班比較困難；但是，航班C與航班B的銜接時(shí)間最短且滿足最小過站時(shí)間，如圖1(b)，如果優(yōu)先將航班C與航班B銜接，過站時(shí)間為1 h，剩余的航班A與航班D的銜接過站時(shí)間長達(dá)6 h，在這6 h的空余運(yùn)力中新增航班就相對(duì)容易.

圖1 緊湊銜接航班計(jì)劃示意圖Fig.1Diagram of a tightly connected flight plan

A航空公司之前也是通過引進(jìn)國外某系統(tǒng)來完成航季航班編排，但該系統(tǒng)只能在人工確定機(jī)型的前提下進(jìn)行連線銜接操作，無法自動(dòng)分配機(jī)型，自動(dòng)化程度不高.為進(jìn)一步提高航班計(jì)劃編排效率，確保航班收益最大化，經(jīng)過長期的業(yè)務(wù)總結(jié)和技術(shù)研究，A公司已探索出滿足國內(nèi)航司航季航班編排的解決方案.首先運(yùn)用機(jī)型指派模型，在飛機(jī)數(shù)量最小化前提下確定每個(gè)航班執(zhí)飛機(jī)型，使整體收益貢獻(xiàn)最大化；然后運(yùn)用先進(jìn)先出、后進(jìn)先出、二部圖、加權(quán)二部圖等算法完成連線銜接.基于上述思路，本文列出以下假設(shè)條件：

1) 航季航班計(jì)劃是以周為單位，不同自然周的航班計(jì)劃均相同.因此，只需某個(gè)自然周的航班計(jì)劃進(jìn)行連線自動(dòng)銜接，其余周期的航班計(jì)劃重復(fù)銜接即可.

2) 航季航班計(jì)劃的飛機(jī)連線不涉及具體機(jī)號(hào)，只需根據(jù)具體型號(hào)的飛機(jī)數(shù)量給出對(duì)應(yīng)數(shù)量的飛機(jī)連線即可.

3) 所有運(yùn)行約束都只考慮機(jī)型維度的運(yùn)行約束，不考慮機(jī)號(hào)維度的運(yùn)行約束.

4) 每個(gè)航班用不同機(jī)型執(zhí)飛所產(chǎn)生的收益貢獻(xiàn)為已知，貢獻(xiàn)大小僅與機(jī)型有關(guān)，與航班銜接無關(guān).本文使用的預(yù)計(jì)貢獻(xiàn)是利用神經(jīng)網(wǎng)絡(luò)模型根據(jù)歷史經(jīng)營情況以及未來航班的銷售情況進(jìn)行預(yù)計(jì)，文中不作詳述.

1.2 航班機(jī)型指派模型

機(jī)型指派模型以時(shí)空網(wǎng)絡(luò)為基礎(chǔ).在時(shí)空網(wǎng)絡(luò)中，橫軸代表時(shí)間，縱軸代表機(jī)場(chǎng)，網(wǎng)絡(luò)由若干航班組成，能夠體現(xiàn)航班起飛、降落的時(shí)刻與機(jī)場(chǎng).圖2所示為一周的時(shí)空網(wǎng)絡(luò)圖，xd,f,k等箭頭表示第d天用k機(jī)型執(zhí)飛f航班，yd,a,k等節(jié)點(diǎn)表示第d天凌晨3:00時(shí)在A機(jī)場(chǎng)k機(jī)型的過夜數(shù)量(由于每天的航班計(jì)劃中，最遲降落的航班時(shí)刻可能超過24:00，故本文選取凌晨3:00作為過夜飛機(jī)數(shù)的統(tǒng)計(jì)節(jié)點(diǎn)).機(jī)型指派模型最核心的思想是當(dāng)航班起飛時(shí)必須有一架飛機(jī)可供使用，例如：對(duì)于機(jī)型k，當(dāng)x1,4,k準(zhǔn)備起飛時(shí)，機(jī)場(chǎng)B初始的飛機(jī)有y1,b,k架，進(jìn)港的飛機(jī)有x1,5,k、x1,2,k、x1,3,k，離港的飛機(jī)有x1,1,k、x1,6,k.因此，要使x1,4,k有k機(jī)型可用，就必須滿足y1,b,k+x1,5,k+x1,2,k+x1,3,k-x1,1,k-x1,6,k大于等于1.此外，為了航班計(jì)劃的銜接能夠循環(huán)延續(xù)，每個(gè)機(jī)場(chǎng)最終的機(jī)型數(shù)量分布要與該機(jī)場(chǎng)最初的機(jī)型數(shù)量分布一致，即需要圖中y8,a,1=y1,a,1.

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

1.2.1 參數(shù)設(shè)置

模型參數(shù)和變量設(shè)置如表1和2所示.

表1 模型參數(shù)

表2 模型變量說明

1.2.2 目標(biāo)函數(shù)

對(duì)于航季航班分配機(jī)型通?？紤]兩個(gè)目標(biāo)：一是將現(xiàn)有航班用最少的飛機(jī)數(shù)編排；二是使航線網(wǎng)絡(luò)收益貢獻(xiàn)最大化.根據(jù)以上兩個(gè)目標(biāo)可以得出目標(biāo)函數(shù)(1)和(2)：

(1)

(2)

對(duì)于多目標(biāo)決策，主要思路是將多目標(biāo)降維成一系列單一目標(biāo)進(jìn)行優(yōu)化，常見的有搶占式優(yōu)化和加權(quán)優(yōu)化.搶占式優(yōu)化需要根據(jù)目標(biāo)的重要性多次建立模型，而加權(quán)優(yōu)化只需建立一次模型，通過設(shè)置加權(quán)系數(shù)的正負(fù)性保證加權(quán)目標(biāo)函數(shù)最大化或最小化一致，其中系數(shù)絕對(duì)值大小體現(xiàn)目標(biāo)的重要性，這樣就能減少建模次數(shù)，提高優(yōu)化效率.在實(shí)際業(yè)務(wù)中，要優(yōu)先保證以最小的飛機(jī)數(shù)排下所有航班，然后再調(diào)整機(jī)型增加貢獻(xiàn).因此，本文采取加權(quán)優(yōu)化，可以列出目標(biāo)函數(shù)(3)，加權(quán)目標(biāo)是求最大化的問題，所以β的系數(shù)為負(fù).經(jīng)過測(cè)試，當(dāng)設(shè)α=1，β=-10 000時(shí)，求解的最小飛機(jī)數(shù)、最大貢獻(xiàn)與搶占式優(yōu)化的結(jié)果一致.

(3)

1.2.3 約束條件

飛機(jī)連線的銜接要求覆蓋每個(gè)航班且每個(gè)航班只能被指派1種機(jī)型執(zhí)飛，如式(4)：

(4)

每個(gè)航班在起飛前必須有1架飛機(jī)可供使用，即如果xd,f,k=1，則對(duì)于d天在fj航班的起飛機(jī)場(chǎng)的初始飛機(jī)數(shù)加上在fj航班起飛前進(jìn)港的飛機(jī)數(shù)再減去在fj航班起飛前離港的飛機(jī)數(shù)后，在fj航班離港時(shí)至少有一架k機(jī)型的飛機(jī)可供其使用，如式(5)：

(5)

在每個(gè)機(jī)場(chǎng)，每天的初始飛機(jī)數(shù)加上該機(jī)場(chǎng)的所有進(jìn)港飛機(jī)數(shù)再減去該機(jī)場(chǎng)的所有出港飛機(jī)數(shù)要等于該機(jī)場(chǎng)的最終的飛機(jī)數(shù)，如式(6)：

(6)

這里：?k∈K,?a∈A,?d∈D且d≠8.

機(jī)隊(duì)平衡約束，在優(yōu)化周期內(nèi)，每個(gè)機(jī)場(chǎng)的初始機(jī)隊(duì)分布要與最終的機(jī)隊(duì)分布一致，如式(7)：

y1,a,k-y8,a,k=0,?k∈K,?a∈A.

(7)

機(jī)隊(duì)規(guī)模約束，即每種機(jī)型在優(yōu)化周期的初始機(jī)隊(duì)數(shù)量應(yīng)在用戶設(shè)定的上下限之間，如式(8)和(9)：

(8)

(9)

每個(gè)機(jī)場(chǎng)對(duì)不同機(jī)型的保障能力不同，因此還需對(duì)每個(gè)機(jī)場(chǎng)每種機(jī)型允許過夜的飛機(jī)數(shù)量進(jìn)行約束，如式(10)：

(10)

這里：?d∈D,?k∈K,?a∈A.

1.3 連線自動(dòng)銜接優(yōu)化

通過航班機(jī)型指派模型，只能確定在使用最少飛機(jī)數(shù)的前提下每個(gè)航班的執(zhí)飛機(jī)型，并且能使總體貢獻(xiàn)最大化，但是機(jī)型指派模型并不能確定航班與航班間是如何銜接的.飛機(jī)連線的銜接本質(zhì)是在每個(gè)機(jī)場(chǎng)為進(jìn)港航班找到后續(xù)的出港航班，如圖3所示兩條飛機(jī)連線，實(shí)際上可以拆分成在杭州、廣州、?？凇⑸蜿柡吞m州機(jī)場(chǎng)的進(jìn)港航班和出港航班的銜接.基于機(jī)場(chǎng)銜接思路，飛機(jī)連線的銜接算法主要有以下3種方法：先進(jìn)先出、后進(jìn)先出、加權(quán)二部圖最佳完美匹配算法.

圖3 飛機(jī)連線銜接本質(zhì)示意圖Fig.3Aircraft routing schematic diagram

1.3.1 先進(jìn)先出和后進(jìn)先出算法

圖4 先進(jìn)先出和后進(jìn)先出算法Fig.4FIFO & LIFO algorithms

先進(jìn)先出和后進(jìn)先出算法如圖4所示.假設(shè)最小過站時(shí)間為60 min，先進(jìn)先出算法(圖4(a))主要是在每個(gè)機(jī)場(chǎng)內(nèi)，先進(jìn)港的航班優(yōu)先與滿足最小過站時(shí)間標(biāo)準(zhǔn)的先出港航班銜接；后進(jìn)先出(圖4(b))算法主要是在每個(gè)機(jī)場(chǎng)內(nèi)，將后進(jìn)港的航班優(yōu)先與滿足最小過站時(shí)間標(biāo)準(zhǔn)的先出港航班銜接.圖4中，08:10為第一個(gè)出港航班，無前序航班；12:00為最后一個(gè)進(jìn)港航班，則無后續(xù)航班.先進(jìn)先出的優(yōu)點(diǎn)在于求解速度最快，飛機(jī)的過站時(shí)間分布較為均衡，過站時(shí)間相對(duì)較充足；后進(jìn)先出的優(yōu)點(diǎn)在于飛機(jī)的過站時(shí)間分布較為極端，可以集中體現(xiàn)飛機(jī)的空余運(yùn)力.尤其在市場(chǎng)旺季區(qū)間，使用后進(jìn)先出法可以快速發(fā)現(xiàn)空余運(yùn)力，有利于旺季增加航班量，提高飛機(jī)利用率.

1.3.2 加權(quán)二部圖最佳完美匹配算法

每個(gè)機(jī)場(chǎng)的航班銜接實(shí)際上可以看作是一張二部圖的指派問題，即將機(jī)場(chǎng)的每個(gè)進(jìn)港航班指派給該機(jī)場(chǎng)的每個(gè)出港航班，根據(jù)銜接目的不同可以對(duì)二部圖的邊(銜接)進(jìn)行賦權(quán)，得到一張加權(quán)二部圖，再通過KM(Kuhn-Munkres)算法求得二部圖的最佳完美匹配，即可得到滿足要求的銜接方案.

連線銜接通常考慮保留原始銜接、往返銜接、緊湊型銜接3個(gè)因素.本文分別對(duì)原始銜接、往返銜接、緊湊銜接按0～100的不同得分賦值，其中：如果銜接為往返銜接(原始銜接)，往返銜接(原始銜接)得分即為100分，反之0分；對(duì)于緊湊銜接得分，采用指數(shù)函數(shù)y=100·ax(0

1.3.3 指派飛機(jī)連線編號(hào)

在每個(gè)機(jī)場(chǎng)都建立好銜接之后，需要將每個(gè)航班賦值機(jī)型連線編號(hào).首先建立3個(gè)集合：初始航班集合P、前序-后續(xù)航班集合PF、終止航班集合F.對(duì)于先進(jìn)先出、后進(jìn)先出算法，如果未匹配航班屬于降落航班集合，說明該航班無后續(xù)航班銜接，屬于終止航班集合F；相反，如果未匹配航班屬于起飛航班集合，說明該航班無前序航班銜接，屬于初始航班集合P.對(duì)于加權(quán)二部圖求解的結(jié)果，邊權(quán)為-104的匹配在業(yè)務(wù)上是不合法的，在這些不合法的匹配中，將起飛的航班歸入初始航班集合，將落地的航班歸入終止航班集合.其次，遍歷初始航班集合P中的每個(gè)航班，通過該初始航班在前序-后續(xù)航班集合PF中不斷尋找后續(xù)航班，直到后續(xù)航班為終止航班，說明這些航班屬于同一條飛機(jī)連線，為其編號(hào)，以形成完整的連線銜接方案.具體的連線銜接流程如圖5所示.

2 實(shí)驗(yàn)及分析

2.1 評(píng)價(jià)指標(biāo)

使用不同算法和同一算法不同參數(shù)求得的連線銜接方案會(huì)有差異.本文結(jié)合航空公司實(shí)際業(yè)務(wù)，從飛機(jī)日利用率、往返航班銜接占比、原始銜接占比、空檔運(yùn)力情況、過站時(shí)間裕度等指標(biāo)，對(duì)比不同連線銜接方案的差異.

1) 飛機(jī)日利用率

飛機(jī)日利用率是從時(shí)間維度衡量飛機(jī)使用情況的重要指標(biāo)，計(jì)算如式(11)所示.日利用率高說明在同等規(guī)模的機(jī)隊(duì)下，能夠充分利用主要固定資產(chǎn)，執(zhí)飛更多的航班，為航空公司帶來更高收益.

(11)

2) 往返航班銜接占比

衡量往返航班銜接占比高低的指標(biāo)，如式(12)所示.

往返航班銜接占比=

(12)

3) 原始銜接航班占比

衡量原始銜接占比高低的指標(biāo)，如式(13)所示.

100%.

(13)

4) 空檔運(yùn)力數(shù)量和時(shí)長

如前所述，空檔運(yùn)力是指每天6:00—24:00時(shí)期間，連續(xù)6 h及以上沒有任何航班執(zhí)行計(jì)劃的飛機(jī)數(shù)和時(shí)長.例如，圖1(a)中的空檔數(shù)量和時(shí)長均為0，圖1(b)中的空檔數(shù)量為1，空檔時(shí)長為6 h.

圖5 飛機(jī)連線銜接及編號(hào)流程圖Fig.5Aircraft routing flow chart

5) 過站時(shí)間裕度分布

過站時(shí)間裕度是指飛機(jī)實(shí)際過站時(shí)間與局方要求最小過站時(shí)間之差.過站時(shí)間裕度越小，說明航班銜接得越緊湊，有利于騰出空檔運(yùn)力，但應(yīng)對(duì)前序航班延誤情況的能力有限.過站時(shí)間裕度越大，說明航班銜接越寬松，不利于發(fā)現(xiàn)空檔運(yùn)力，但能夠較好地應(yīng)對(duì)前序航班延誤的情況，整個(gè)航班計(jì)劃的穩(wěn)定性更好.本文中過站時(shí)間裕度不計(jì)過夜銜接的時(shí)間裕度.

2.2 實(shí)驗(yàn)結(jié)果

本文選取A航空公司每周共3 876個(gè)航班進(jìn)行實(shí)證分析.在這些航班中，1 317個(gè)航班延續(xù)了上個(gè)同航季的航班計(jì)劃，占總航班的34.0%；1 028個(gè)航班的銜接屬于往返航班銜接，占總航班的26.5%；其余航班均未指派機(jī)型且均未確定銜接情況.航班計(jì)劃共涉及4個(gè)主要基地、79個(gè)機(jī)場(chǎng).

機(jī)型配置方面，本文應(yīng)用cplex對(duì)機(jī)型配置模型進(jìn)行求解，計(jì)算時(shí)間為16.3 s(cpu：i5-4570，主頻：3.0 GHz，內(nèi)存：8 GB)；連線銜接方面，本文用Python程序求解，其中先進(jìn)先出、后進(jìn)先出算法求解時(shí)間不到1 s，加權(quán)二部圖的求解約3 s，實(shí)現(xiàn)了大規(guī)模航班飛機(jī)連線的快速模擬(表3).對(duì)比從國外引進(jìn)的現(xiàn)有系統(tǒng)，雖在機(jī)型確定的前提下連線銜接僅需5 s，但還要考慮機(jī)型調(diào)整的時(shí)間，采用人工，則需要1～4 h，若采用本文機(jī)型配置結(jié)果，還要增加人工錄入時(shí)間.對(duì)比引言中提到的一體化模型需要數(shù)小時(shí)的求解時(shí)間，分階段的模式在求解效率上具有明顯的優(yōu)勢(shì)，均在20 s以內(nèi).

通過第一階段機(jī)型指派模型結(jié)果(表4)可以得出，使用最少的飛機(jī)數(shù)為160架，飛機(jī)日利用率為8.40 h，貢獻(xiàn)22 602.8萬元，比現(xiàn)有系統(tǒng)編排結(jié)果增加收益貢獻(xiàn)232.8萬元/周，相當(dāng)于1個(gè)航季可以增加收益貢獻(xiàn)7 200萬元.

為對(duì)比加權(quán)二部圖不同參數(shù)的效果，本文制定了3個(gè)方案，如表5所示.方案一側(cè)重往返銜接(簡稱“往返”)，方案二側(cè)重保留原始銜接(簡稱“原始”)，方案三側(cè)重緊湊銜接(簡稱“緊湊”).

在第一階段機(jī)型指派的結(jié)果上，分別運(yùn)用先進(jìn)先出、后進(jìn)先出、二部圖、加權(quán)二部圖等算法進(jìn)行連線銜接.從往返航班銜接占比(圖6)可以看出加權(quán)二部圖往返方案的占比最高，達(dá)82.0%，較初始航班計(jì)劃提高55.5個(gè)百分點(diǎn)，符合最初側(cè)重往返銜接的得分設(shè)置.從原始銜接航班占比(圖7)可以看出現(xiàn)有系統(tǒng)的占比最高，為33.7%，基本上保留了初始航班銜接的信息，其次為加權(quán)二部圖原始方案，占比31.7%，僅比現(xiàn)有系統(tǒng)少2個(gè)百分點(diǎn).從空檔運(yùn)力和時(shí)間(圖8、表6)可以看出后進(jìn)先出和加權(quán)二部圖緊湊方案騰出的空檔運(yùn)力最多，空檔運(yùn)力數(shù)量達(dá)115個(gè)，比現(xiàn)有系統(tǒng)多4個(gè)，最高空檔時(shí)間達(dá)883 h，比現(xiàn)有系統(tǒng)多10%.從過站時(shí)間裕度分布(圖10)可以看出，后進(jìn)先出和加權(quán)二部圖緊湊方案在0～5 min銜接裕度上數(shù)量最多，其余時(shí)間段均為最少，也可以說明這兩種算法傾向于緊湊型的銜接，而先進(jìn)先出算法在20 min以上銜接裕度數(shù)量上均為第一，說明該算法傾向于較為寬松的銜接.對(duì)于二部圖算法，在各個(gè)指標(biāo)上均不突出，實(shí)際上二部圖的結(jié)果只是求得一個(gè)可行解，并不能像加權(quán)二部圖一樣可以滿足不同的需求傾向.

表3 機(jī)型指派模型和連線銜接算法運(yùn)行時(shí)間

表4 機(jī)型指派模型運(yùn)行結(jié)果

表5 銜接算法中加權(quán)二部圖算法得分權(quán)重設(shè)置

圖6 各銜接算法對(duì)往返航班銜接占比的影響Fig.6The impacts on proportion of round-trip flights among different aircraft routing algorithms

圖7 各銜接算法對(duì)原始銜接航班占比的影響Fig.7The impacts on proportion of initial flights among different aircraft routing algorithms

圖8 各銜接算法對(duì)空檔運(yùn)力數(shù)量的影響Fig.8The impacts on unused aircraft numbers among different aircraft routing algorithms

圖9 各銜接算法空檔運(yùn)力時(shí)間的影響Fig.9The impacts on unused aircraft flight times among different aircraft routing algorithms

圖10 各銜接算法對(duì)過站時(shí)間裕度分布的影響Fig.10The impact of transit time distribution among different aircraft routing algorithms

3 結(jié)論和展望

航季航班編排關(guān)系到航空公司飛機(jī)利用率和整體經(jīng)營效益.本文以使用飛機(jī)數(shù)量最小化和收益貢獻(xiàn)最大化為目標(biāo)，通過運(yùn)用機(jī)型指派模型，確定了新航季中每個(gè)航班的執(zhí)飛機(jī)型，再運(yùn)用先進(jìn)先出、后進(jìn)先出、二部圖、加權(quán)二部圖等算法，根據(jù)不同業(yè)務(wù)需求，求解滿足條件的連線銜接方案，實(shí)現(xiàn)航季航班編排的完整規(guī)劃.研究結(jié)果表明：

1) 先進(jìn)先出算法傾向于寬松的銜接條件，在運(yùn)力充足的情況下，采用此方法可以增加過站時(shí)間裕度，在發(fā)生航班延誤時(shí)，能提高整個(gè)航班計(jì)劃的穩(wěn)定性.

2) 后進(jìn)先出和加權(quán)二部圖緊湊方案算法在騰挪空檔運(yùn)力方面效果顯著，在運(yùn)力較為緊張時(shí)，可以通過緊湊型的銜接，發(fā)現(xiàn)空檔運(yùn)力，有利于增加航班，提高飛機(jī)利用率.

3) 加權(quán)二部圖可以通過對(duì)不同需求設(shè)置差異化權(quán)重，實(shí)現(xiàn)往返航班銜接、保留原始航班銜接、騰挪空檔運(yùn)力等方面的特定需求.特別是盡量做到往返航班銜接，并保留原始航班的銜接，更有利于機(jī)組排班等業(yè)務(wù)工作.

總結(jié)本文的研究創(chuàng)新點(diǎn)，主要有兩個(gè)方面：

1) 本文提出的模型更側(cè)重于航空公司的實(shí)際運(yùn)營需要.采用現(xiàn)有系統(tǒng)編排航季航班，編排效率低、效果不理想；使用一體化模型求解，運(yùn)行時(shí)間較長，較適用于航班計(jì)劃相對(duì)固定的國際航線編排，但國內(nèi)民航市場(chǎng)的航班計(jì)劃每天都可能發(fā)生變動(dòng)，對(duì)連線銜接的求解效率要求很高，如果采取一體化模型，求解效率將無法滿足實(shí)際需要.本文采用兩階段模型，可以快速求解滿足需求的連線銜接方案，20 s以內(nèi)就能完成每周3 800班左右的航班編排.

2) 本文創(chuàng)造性將機(jī)型配置模型和加權(quán)二部圖算法結(jié)合應(yīng)用.目前，二部圖在連線銜接上主要用于解決單樞紐(或基地)航線網(wǎng)絡(luò)的航班銜接問題，無法完全滿足多樞紐航線網(wǎng)絡(luò)的銜接，以及尋找運(yùn)力空檔、往返銜接等不同銜接目標(biāo)的復(fù)雜實(shí)際業(yè)務(wù)需求.本文運(yùn)用加權(quán)二部圖，針對(duì)銜接目標(biāo)不同進(jìn)行差異賦權(quán)，在每個(gè)機(jī)場(chǎng)建立一張加權(quán)二部圖，再通過KM算法求得二部圖的最佳完美匹配，生成針對(duì)多樞紐航線網(wǎng)絡(luò)不同銜接需求的銜接方案，對(duì)比現(xiàn)有系統(tǒng)，航班編排收益貢獻(xiàn)可以提高232.7萬元/周，改善效果明顯.

本文以一個(gè)自然周的航班計(jì)劃作為研究樣本，通過重復(fù)單周的航班銜接方案，擴(kuò)展至整個(gè)航季的航班計(jì)劃，可以適用于航季航班計(jì)劃的連線銜接優(yōu)化.但到了航季中段，不同周期的航班計(jì)劃可能存在差異，需要編排的航班周期就會(huì)大于1周(比如暑運(yùn)).面對(duì)這種情況，算法上計(jì)算量和計(jì)算時(shí)間就會(huì)有所增加，后續(xù)可以考慮啟發(fā)式算法等更加高效的優(yōu)化算法，應(yīng)用于優(yōu)化長周期的航班計(jì)劃.