航線聯營下基于轉運的飛機航線路徑優化

閆妍，馬嘯來

(1. 西安財經大學 管理學院，西安 710100； 2. 西南交通大學 交通運輸與物流學院，成都610031；3. 西南交通大學 綜合交通運輸智能化國家地方聯合工程實驗室，成都610031)

中國航空運輸貨運量逐年增加，航空基礎設施建設加快，樞紐機場的作用日益顯現，整體上我國航空物流發展速度很快，但仍存在如航空貨運的資源閑置導致的高成本等問題。因此，本文以降低航空運輸企業的運營總成本為目標，對飛機航線路徑進行優化研究。

目前國內外對研究航空聯盟環境下飛機航線路徑優化的研究較少，對航線網絡優化的研究集中在線路優化[1-2]、航線調配[3-4]、飛機排班優化[5]方面。多采用定性與定量分析方法優化航線，通過建立的指標評估體系、數學模型，采用決策樹法[6]、聚類法、迭代法[7]、松弛法[8]等精確算法，設計遺傳算法[9]、列生成算法等啟發式算法，也有部分采用數學求解器，如MATLAB 優化工具箱[1]、CPLEX[10]等軟件解決模型，確定最優航線。聯盟環境下的飛機航線路徑優化研究主要有王苗苗[11]基于航空節點聯盟，不考慮樞紐點的建設成本，以網絡總成本最小化為目標，構建航線網絡優化模型，并求解分析航空網絡布局。不考慮航空聯盟的飛機航線路徑優化研究中的選址-路徑問題（location-routing problems, LRP），楊忠振等[12]構建總運輸成本最小化的雙層規劃模型，確定航空樞紐點選址及航段上的指派路徑。不考慮航空聯盟的飛機航線路徑優化（fleet route optimization，FRP），裴一麟[5]構建航線網絡航班時刻雙層優化模型，利用二分法精確求解航班時刻、各航線的成本和總成本。Armacost 等[13]同時確定聯合包裹服務（united parcel service，UPS）飛機航線、機隊分配和包裹路線，確保以最低成本實現隔夜交付，并應用復合變量法解決模型。

基于現有研究，本文將研究點點式、軸輻式組成的混合式航空貨運網絡的轉運點選址與飛機航線路徑優化問題。本文的創新性在于引入航空聯盟運營選擇概率函數，構建聯盟環境多起訖點的航空貨物中轉及飛機航線路徑優化模型，并設計自適應遺傳算法求解模型。

因此，本文將以航空聯盟為基礎，解決航空貨運中轉點選址及飛機航線路徑優化問題，以轉運點數量及轉運次數為限制條件，不考慮飛行過程中的時間成本及等待時間成本，以總成本最小化為目標，建立了航線聯營下基于轉運的航線路徑優化模型（aircraft fleet route problem based on transshipment and airline alliance, T-AAAFRP）。采用改進的遺傳算法求解模型，并通過案例分析航空線路聯盟下的航空中轉點選址、飛機飛行路徑及在不同轉運點限制條件下的選址及路徑問題。

1 問題描述

本文研究的問題可描述為在已知貨運需求起終點i、j的位置及需求量Dij的基礎上，考慮航空網絡中單、雙機場城市飛機容量限制，實際運行中全貨機飛行時段及空域容量的限制，聯盟其他航司的飛行時段及空域容量的限制。任意一架飛機必須從航空基地集合O∈[1,2,...,N]出發，完成一天運輸任務后，返回到出發航空基地。并考慮聯盟對運營的影響，引入航空聯盟選擇概率，確定非轉運、轉運前后各航段運輸的承運及托運問題，若存在運輸無法完成的情況，則需要承擔相應的懲罰成本。因此，本文是研究航線聯營下基于轉運的航線路徑優化問題，即T-AAAFRP 問題。航線聯營下基于轉運的飛機航線路徑優化問題示意圖如圖1 所示。

圖1 基于轉運的飛機航線路徑優化問題示意圖Fig. 1 Aircraft route optimization based on transshipment

2 模型假設及建立

2.1 模型假設

飛機飛行過程中的運量反應示意圖如圖2 所示。T-AAAFRP 問題建模思路如圖3 所示。

圖2 飛機飛行過程中的運量反應示意圖Fig. 2 Traffic response of aircraft in flight

圖3 T-AAAFRP 問題建模思路Fig. 3 Modeling ideas of T-AAAFRP problem

1) 貨物轉運最多1 次。根據大多數航空貨運轉運的研究，轉運次數限制在1～2 次最好，本文根據文獻[14]中的轉運最優結果，因此假設轉運最多1 次。

2) 不考慮飛機降落的排隊問題。假設飛機降落所需時間一樣，且錯開時間降落，因此不存在排隊問題。

3) 轉運貨物計算2 次裝卸費用。根據物流轉運業務費用核算的一般規律，對轉運貨物計算2 次裝卸費用。

4) 轉運過程中不考慮時間等待成本。若飛機在樞紐點不等待，直接飛往下一航段，只需將轉運的貨物在樞紐點卸下，并等待下一飛機到達樞紐點后飛往目的地，其中貨物的時間等待成本不計，但是樞紐點暫存貨物，需要支付樞紐點固定成本；若飛機在樞紐點等待，則還需要承擔停機費用。

5) 運輸過程中各航段的單位運輸成本相同。飛機的單位運輸成本與飛機的類型相關，假設所用的飛機類型一致。

6) 航空公司所有的需求點及轉運點都是航空公司承運。

7) 航線承運時，任意2 個航空節點間的貨物只能沿著一條運輸成本最小的航線完成運輸。航空公司在運營中，以成本最小為目標，則必選擇成本最小的航線完成運輸。

8) 樞紐點的容量限制與機場數相關。假設雙機場城市選擇樞紐點的容量限制是單機場城市選擇樞紐點的容量限制的2 倍。

9) 若航段運營托運時，則該航段航空公司的承運貨運量為0。

2.2 航空聯盟運營選擇概率函數

當航空公司選擇加入聯盟時，不同航段上的運營選擇與其貨運量、其他合作航空公司貨運量及其他合作航空公司運營選擇有關。

當航空公司選擇聯盟承運時，效益為

采用改進的風險價值函數，評估風險損失大小，風險價值函數為

2.3 基于轉運的飛機航線路徑優化模型

對于轉運中心選址，一般采用樞紐選址模型[15]，解決需求點間的樞紐轉運問題。針對飛機航線路徑優化，一般采用FRP 模型[16]，解決飛機路線設計、航空運輸問題。因此，本文將以總成本最小化為目標函數，建立基于轉運的飛機航線路徑優化模型：

式 中：yij為 航 段i到j選 擇 承 運，服 從0～1 分 布；CTik j為 點i經 點k到點j的單位運輸成本，CTik j=θ1CTik+θ3CTk j≈θ(CTik+CTk j)，總 運 輸 成 本 與 重量、距離相關， θ1、θ3為直達成本與轉運成本之間系數，且與運輸航段有關， θ為標準的直達成本與轉運成本之間系數，可簡化表示為 CTik j=θ(CTik+CTk j)，dik j為 點i經 點k到 點j的 距 離，dik j=dik+dk j；POk j為 轉運前的出發點是基地的概率。

裝卸降落成本，包括航段直達與轉運兩部分：

無人運輸的懲罰成本：

3 算法設計

3.1 算法選擇及流程

本文研究的航空公司轉運點選址和飛機路徑聯合優化問題，需要解決的問題有：①確定貨物的轉運點；②每架飛機的飛行路線。

對該類聯合優化問題的求解大多采用遺傳算法，考慮本文研究屬于LRP，也將采用遺傳算法求解，本文研究的創新性是基于有向需求的優化問題，因此，將基因工程中的剪切技術運用在遺傳算法的交叉與變異過程中，設計自適應遺傳算法求解轉運點選址及飛機路徑優化問題，優化過程如圖4 所示，其中，終止條件1 為：需要將所有的需求點全部計算完，終止條件2 為：根據計算結果，與上一輪的結果比較留質最優的結果，且迭代次數達到了規定。

圖4 算法流程Fig. 4 Algorithm flow

3.2 算法改進及設計

步驟 1 改進編碼形式及參數初始化，改進的編碼形式如圖5 所示。

圖5 改進的編碼形式Fig. 5 Improved coding form

采用分段編碼的形式，分為2 段。第1 段采用整數染色體編碼形式，共有K個個體，表示K個中轉點，每一個染色體基因代表第幾個機場被選為中轉點。第2 段采用向量編碼的形式，在可行域內隨機產生M×M個個體，且將第2 段編碼分為3 個部分，第1 部分代表基地機場出發的需求，第2 部分為需求點的需求，第3 部分代表返回基地機場的需求，構成初始種群。若有2 個航空基地，10 個需求點，則將產生一條10×10 的群體，編號為[(1,3),(3,4),(4,5),(5,1),(1,2),(2,6), (6,7),(7,8),(8,2),(2,1),(1,9),(9,10),(10,1)]，代表相應的路徑，需要3 架飛機進行運輸，路線1 為1-2-3-5-1，路線2 為2-6-7-8-2，路線3 為1-9-10-1。

步驟 2 基于備選點確定轉運中心初始解。在給定的K1個 備選點中，隨機選擇確定K個個體，作為轉運點初始解。

步驟 3 染色體解碼。染色體解碼的目的是為了獲取每一架飛機所運輸的起終點需求，即OD 對解碼的具體過程如下：①初始化一條路徑；②將染色體中的基因值順序插入到當前路徑中，其中經中轉運輸的航段必須符合轉運點的約束條件，若1 個基因值的插入導致該路徑的負荷超過了飛機、航段的最大容量或飛機飛行時長的約束，則開始構建新的路徑；③重復1、2 操作，通過掃描方式直至所有OD 對均被插入到路徑中分割成多個染色體，最終形成一個可行解。若有2 個航空基地，10 個需求點，則將產生1 個可行解。為避免出現不可行解等問題，在該步驟按照假設條件及約束條件，進行解碼，確保解的可行性。假設染色體的編碼為[(1,3),(3,4),(4,5),(5,1),(1,2),(2,6),(6,7),(7,8),(8,2)]，初始化一條路徑（即一個空的數組），將染色體的基因依次插入路徑中，假設當插入“(1,2)”時，該路徑的負荷超過了飛機的最大容量或飛機到達航段(1,2)時的時長超過了規定時間，則將1-2-3-5-1 分配給飛機1。因為染色體的基因還沒有完全分配完，所以構建一個新的路徑，將未分配的基因依次插入路徑，假設插入到(8,2)時，該路徑的負荷滿足要求同時飛機飛行時長也符合規定，由于需求OD 對已經全部分配完畢，因此將2-6-7-8-2 分配給飛機2。至此解碼結束。

步驟 4 生成禁忌表。根據各需求OD 對，可隨機生成一條染色體，應用式（23）計算轉運選擇，如圖6 所示。

圖6 初始禁忌表示意Fig. 6 Diagram of initial taboo list

步驟 5 生成路徑初始解：①根據航段上總的OD 需求，應用航司隨機選擇均衡函數，初步確定不同航段上的運輸選擇行為；②總OD 需求合并后若大于1 架飛機總載重時，多余的航段需求OD 全部托運，該位置記為空；③根據步驟3、4 的信息，依次連續選擇飛機運輸航線，且出發點為1，2 開頭的航空基地，返回點也需為1,2 結尾，當1 架飛機新增1 個航段任務導致飛行時間超過24 h，則返回上一航段結束，并將已完成運輸航段記為-1；④當2 架飛機完成1 個經轉運的OD 需求時，若后一段運輸發生時間早于前一段，則需要將后一段需求托運，將轉運后聯盟承運記為0，更新選擇行為；⑤根據最新選擇行為，將轉運前后聯盟承運記為1 的航段，按照第3 步重新生成路徑，如圖7 所示，[]表示自營飛機不承擔運輸，由聯盟的其他公司承擔運輸。

圖7 修正后禁忌表示意Fig. 7 Diagram of revised taboo list

步驟 6 適應度值評價。根據式（10）～式（18），計算適應度值。

步驟 7 選擇。根據步驟3、4、5 計算結果，采用錦標賽法進行選擇操作，選擇N/2染色體。具體選擇方法為，當錦標賽法排序選擇時，染色體z1錦標賽的大小大于染色體z2錦標賽的大小，染色體z2優 于染色體z1； 或當錦標賽值相等且染色體z2適應度值大于染色體z1， 染色體z2優 于染色體z1。

步驟 8 基于基因工程的交叉、變異。根據交叉概率pc，借鑒染色體重組技術，利用剪切酶思想，選擇其中任意一段剪切，且將切割位點表示為剪切基因位，并在該條染色體的其他位置選擇相同剪切基因位的任意長度進行剪切，并交換2 段的位置。此時2 段基因交叉可近似視為一般遺傳算法的單點交叉，基于基因工程的染色體交叉過程如圖8 所示。根據變異概率pm，和改進交叉方法相同，基于染色體中的某段基因，選擇將其中一小段基因進行變異，同時在變異位置后，選擇與前段基因連接相同的基因，并將該段基因中的一小段基因與前段基因變異，此時的2 段基因變異可近似視為一般遺傳算法的單點變異，基于基因工程的染色體變異過程如圖9 所示。

圖8 基于基因工程的染色體交叉過程Fig. 8 Chromosome crossover process based on genetic engineering

圖9 基于基因工程的染色體變異過程Fig. 9 Chromosome mutation process based on genetic engineering

步驟 9 精英數目。合并父代及子代的種群染色體，形成新種群P(h)，經過序值、擁擠度、交叉等操作得到下一代群體P(t+1)，并按照適應度值升序排列選擇染色體，最終選擇H個染色體。

步驟 10 終止判斷1。即需要將所有的需求點全部計算完后達到終止條件1，則終止程序，并通過結果驗證，選擇的染色體不能重復輸出結果，否則返回步驟3。

步驟 11 終止判斷2。即根據計算的結果，與上一輪的結果比較留取最優的結果，且迭代次數達到了規定，則終止程序，并通過結果驗證，選擇的染色體不能重復輸出結果，否則返回步驟2。

4 算例分析

4.1 參數設置及基本情況

S 貨運航空公司實際運營時，單位運輸成本CT=0 .003 3 元/(kg·km)，假設飛機的最大載重量Q=30 000 kg，每段航程所需的固定費用（包括飛機折舊）為CP=25 000 元/(架·次)，裝卸作業成本為CW=0.5 元/kg，飛 機 的 起 降 費 CPTL=20 000元/(架·次)，無承運時的單位損失成本為CW= -0.001 元/(kg·km)，航空基地分攤至每天的建設成本 CFo服從均勻分布U（300 000，400 000），每個基地的飛機容量限制QN服從均勻分布U[10 000，20 000]，且雙機場城市{上海、北京、成都}的容量限制Qi服從其他單機場容量限制的2 倍，即服從U[20 000，40 000]。樞紐點建設成本 CFk服從均勻分布U（20 000，40 000），樞紐轉運運輸成本系數為 θ=0.8，備選航空樞紐點數量為N=6，假設不同航段的容量限制服從均勻分布U[30 000，60 000]，各航段的時間窗滿足[U(0，18 000)，U(0，18 000)+U(2 000，6 000)]，超過飛行時間約束的懲罰成本e為500 000 元。已知航空公司基地為{4 深圳、5 杭州}，航空樞紐點備選集合為{1 北京、2 廣州、6 沈陽、7 鄭州、8 武漢、9 成都}，其他參數如表1所示。

表1 修正后禁忌表主要參數設置Table 1 Revised taboo list Main parameter setting

4.2 計算結果

改進的自適應遺傳算法利用MATLAB R2016b軟件，在Inter Core i7-8550U CPU @ 1.80 GHZ 1.99 GHz，8.00 GB 內存電腦上運行計算，通過數值實驗分析改進算法的參數對計算結果的影響如圖10 所示，求解算法的具體參數設置如下：種群大小 NP=100，交叉概率pc=0.8， 變異概率pm=0.8，最大迭代數G=100。當轉運點數量為2 時，在第27 代算法收斂，說明設計的改進算法具有較高的收斂性，算法的迭代收斂曲線如圖11 所示。

圖10 種群大小對計算結果的影響Fig. 10 Effect of population size on calculation results

圖11 收斂曲線Fig. 11 Convergence curve

不同轉運點數量的優化選擇結果如表2 所示，不同優化方案的最優飛機機隊路線如表3 所示。從表2 可以看出，基地機場數量越多，總成本越小，且任意轉運點數量時轉運點都包含成都，即雙機場所在城市，符合航空公司、機場各方業務發展需要。但是總成本越小的方案，不一定是最優的決策方案。企業的決策者需根據不同時期的需求確定不同的計劃。當企業資本較小時，應選擇表2 中的最優選擇4 或5；當企業在市場擴充時，為贏得更多客戶，應該選擇表2 中的最優選擇1 或2。

表2 不同轉運點數量的優化選擇結果Table 2 Optimal selection results of different number of transfer points

表3 5 種方案的最優飛機機隊路線Table 3 Optimal aircraft fleet route of five schemes

4.3 敏感性分析

1） 不同需求量下的結果分析。不同轉運點的數量及位置，在需求量倍數增長下，單位數量的總成本與飛機數量會有所增長，且增長率不斷增大。總成本的平均增長率為-19.3%，飛機數量的平均增長率為106.8%。在同一種轉運點類型下，單位數量的總成本與飛機數量的增長率相差不大，其中2 個轉運點的總成本的平均增長率為-12.5%，飛機數量的平均增長率為41%；其中3 個轉運點的總成本的平均增長率為-11.5%，飛機數量的平均增長率為60.1%；其中4 個轉運點的總成本的平均增長率為-14.2%，飛機數量的平均增長率為91.7%；其中2 個轉運點的總成本的平均增長率為-18.7%，飛機數量的平均增長率為111.6%；其中2 個轉運點的總成本的平均增長率為-20.1%，飛機數量的平均增長率為122%。對比總體可知，當轉運點數量越多，所節省的成本不斷擴大，所使用的飛機數量也越多，如圖12 所示。因此建議在企業運營決策中，多考慮多轉運點的情況，降低成本。

圖12 不同需求量下的計算結果Fig. 12 Calculation results under different demands

2） 不同飛機載重量下的結果分析。不同轉運點的數量及位置，在飛機載重量增長下，總成本與飛機數量有所下降，但趨勢較緩。不同數量的轉運點對比中，同一載重量的總成本隨著轉運點數量的增多而降低的幅度較大。隨著載重量從30 000 kg，35 000 kg，40 000 kg，45 000 kg，50 000 kg 的變化過程，總成本平均增長率分別為-23%、-26.1%、-23%、-24.5%、-25%，飛機數量平均增長率分別為-45.7%、-48.9%、-50%、-53.3%、-54.5%，下降的趨勢明顯，如圖13 所示。總之，轉運點數量較少時，飛機的載重量對優化結果的影響較小，當飛機載重量較大時，決策者需考慮轉運點數量多的方案。

圖13 不同飛機載重量下的計算結果Fig. 13 Calculation results under different aircraft load

3） 不同飛機固定成本下的結果分析。不同轉運點的數量及位置，在飛機固定成本增長下，總成本與飛機數量會呈負增長趨勢，且增長率逐漸趨于平緩。若飛機固定成本較小時，較多的轉運點數量可以減少總成本、降低飛機使用數量。若當飛機固定成本較高時，轉運點越多，則航空公司越多的無法進行承運運輸，此時選擇托運的概率越大。隨著飛機固定成本從25 000 元，30 000 元，35 000 元，40 000 元，45 000 元的變化過程，總成本平均增長率分別為-24.5%、-23.7%、-10.3%、-7.2%、-9.7%，飛機數量平均增長率分別為-48.9%、-62.5%、-27.3%、-22.2%、-28.6%，下降的趨勢明顯，如圖14 所示。總而言之，飛機的固定成本較少時，越多的轉運點則總成本、飛機使用數量越小。當飛機的固定成本較大時，企業選擇托運的概率越大。

圖14 不同飛機固定成本下的計算結果Fig. 14 Calculation results under different aircraft fixed costs

4） 不同成本與收益的系數結果分析。不同的收益系數，較大程度影響決策。當收益系數保持不變時，轉運點數量越多，總成本與飛機的數量越小，平均增長率分別為-25.5%和-48.6%。但當轉運點數量保持不變時，收益系數越多，總成本與飛機的數量越多，平均增長率為56.3%和234%，如圖15所示。因此，航空公司成本與收益的系數的大小對決策的影響很大，系數越大時，可選擇轉運點數量越少的決策方案。

圖15 不同成本與收益的系數下的計算結果Fig. 15 Calculation results under different coefficients of cost and benefit

5） 不同航空聯盟成本分攤系數結果分析。當航空聯盟承運成本分攤系數 α一定時，隨著托運成本分攤系數 β的增多，總成本平均增長率為5%，飛機數量平均增長率為17.3%。當航空聯盟托運成本分攤系數 β一定時，隨著承運成本分攤系數 α的增多，總成本平均增長率為-9.3%，飛機數量平均增長率為-22.4%，如圖16 所示。總之，托運分攤系數越大，選擇承運運輸的概率越大，使用的飛機數越多，但同時總成本越大。反之承運分攤系數越大，航空托運的概率越大，使用的飛機數越少，但同時總成本越小。

圖16 不同航空聯盟成本分攤系數下的計算結果Fig. 16 Calculation results under different cost sharing coefficients of aviation alliance

6） 決策者風險損失偏好不同參數的結果分析。①決策者對損失的敏感度。當轉運點數量保持不變時，不同的決策者對損失的敏感度對優化結果的影響較小，總成本的平均增長率為3%，飛機數量的平均增長率為9.5%。但當決策者對損失的敏感度保持一定時，隨著轉運點數量的增多，總成本的平均增長率為24.4%，飛機數量的平均增長率為51.3%，如圖17 所示。因此，決策者對風險損失敏感度越高，則選擇承運的概率越大，此時所需的總成本、飛機數量越多。②風險損失時權重的大小。當轉運點數量保持不變時，不同的決策者對風險損失時權重大小對優化結果的影響較小，總成本的平均增長率為0.4%，飛機數量的平均增長率為2.1%。但當決策者對風險損失時權重大小保持一定時，隨著轉運點數量的增多，總成本的平均增長率為25.6%，飛機數量的平均增長率為50.8%，如圖18 所示。因此，決策者對風險損失時權重大小，對企業決策影響較小。若為取得更低的成本，應多采取轉運點數量多的方案。

圖17 不同決策者對損失的敏感度下的計算結果Fig. 17 Calculation results under different sensitivity of decision maker to loss

圖18 不同風險損失時權重的大小下的計算結果Fig. 18 Calculation results under the weight of different risk losses

5 結 論

本文主要解決航線聯營下基于轉運的飛機航線路徑優化問題。引入損失價值的前景理論，確定航空聯盟選擇概率函數，建立基于轉運的飛機航線路徑優化模型，將基因工程引入到交叉變異過程中，設計改進的遺傳算法求解模型，最后通過案例分析，可得到以下結論：

1） 在轉運點的確定過程中，當轉運點數量超過3 個時，雙機場城市被貨運航空公司選為轉運點的概率為1。當轉運點數量較少時，轉運點的位置一般集中在與基地位置較遠的區域中心城市。在航空運輸過程中，企業的決策與機場的建設之間相互影響。

2） 當貨運航空公司航段上的貨運需求量大于1/6 飛機載重量時，公司93.4%會選擇直達運輸，此時公司會選擇自己承運航段上的業務。若當貨運需求量小于1/80 飛機載重量時，公司90%會選擇中轉運輸，但有56%會選擇自己承運航段上的業務。

3） 需求量、飛機固定成本、收益系數的大小、承運成本與托運成本的大小對飛機航線路徑優化決策的影響較大。飛機載重量的大小對飛機航線路徑優化決策的影響較小，代表機型對優化結果的影響較小，在軸輻式網絡及航線聯營下，貨運航空公司可自主選擇任意飛機機型。