航線團隊旅客收益管理雙層規劃模型

徐 琪，徐月芳

（南京航空航天大學 民航學院，江蘇 南京 210016）

團隊旅客是航空公司客源的主要組成部分之一，是影響收益的一個重要因素[1]。關于團隊旅客的管理問題在國外已經發展的很成熟，相關產品已經為企業的收益管理問題提供了高效的解決方案。比如美國的PROS軟件可以解決在不替代高價票需求的情況下接受團隊，制定最低可售價，定價時考慮風險因子，跟蹤團隊的取消或增加情況，通過在線工具進行團隊旅客銷售的談判及管理，生成與旅行代理商的合同及條款等問題。專門針對航空公司的收益管理軟件SABRE，通過將團隊旅客調整到散客需求較低的航班上能夠平均增加1%～2%的收益；改進客戶服務，通過直接在線預訂團隊票降低成本；通過自動控制縮短團隊請求的周期。國內關于團隊旅客收益管理的文獻較少，楊思梁，徐公達等做過一些定性研究但并未深入，高強提出了一個如何接受團隊的靜態優化模型[1]。高榮環發現在實際中單一航班上可用座位數可滿足團隊旅客需求，這一前提條件不是常常滿足[2]。

當單一航班的可用座位數不能滿足團隊旅客需求時，如果將團隊拆分在同一航線的不同航班上是一個非常值得研究的問題。將團隊拆分在不同的航班上可提高航空公司的收益但從旅行代理商的角度來說增大了管理難度，團隊拆分越散，旅行代理商的對拆團方案的接受度越低。從提高航線上整體收益和代理商可接受度兩個效益背反的因素出發，利用雙層規劃的博弈特點建立模型對如何進行團隊拆分進行定量分析，上層在EMSR－a對散客需求進行預測的基礎上以航線上所有航班的總收益最大為目標，用下層規劃以旅行代理商對拆團接受度最大為目標，運用熵權法計算出在影響因素下旅行代理商可接受度的綜合得分，作為拆分團隊的依據。最后，設計了分層迭代的算法，并結合實例驗證了模型和算法的有效性。

1 問題描述

當單一航班上的可用座位數不能滿足團隊旅客需求的時候，將團隊拆分在同一航線的不同航班上可有效提高航班的客座率增加收益。但團隊拆分的同時對于旅行代理商來說不僅意味著增加了管理難度，也可能引起旅客滿意度的下降。因此，航空公司在以收益最大化為目標進行團隊拆分時也要兼顧到旅行代理商的可接受程度。基于這種關系，可以用雙層規劃模型（Bi－level programming）來描述，上層規劃（U）描述為航空公司拆分團隊時以航線總收益最大化為目標。下層規劃（L）描述為航空公司將團隊在分配在不同的航班上，其目標是盡量提高旅行代理商的可接受度。上層規劃在散客預測的基礎上從收益最大化角度給出航空公司一個拆分方案，Belobaba在1987年提出了著名的EMSR理論，此后多年雖然有多種變化，但基于EMSR的艙位控制策略幾乎成了一種工業標準[3]。下層規劃即根據旅行代理商的可接受度來決定拆分到哪些航班上多少人。某些航班可能因為航空公司收益高被選擇，但在下層規劃中可能因為旅行代理商出于某些因素的考慮而安排團隊旅客較少，甚至為零。上層規劃和下層規劃反復的相互影響，既可增加航空公司的收益，且同時兼顧旅行代理商，有益于航空公司的良性發展。

2 建立團隊旅客收益模型

2.1 模型假設

為了便于建立模型，文中建立如下假設：

1）航線上單一航班在散客預測的基礎上剩余座位不能滿足同一團隊旅客的需求；

2）團隊旅客不占用頭等艙、商務艙座位；

3）不同艙位的散客需求呈正態分布且獨立；

4）團隊整體最多拆分在3個航班上。

2.2 模型建立

符號意義：

pgi：不同航班團隊旅客的價格

ni：分配在不同航班上團隊旅客的人數

ci：每個航班上散客人數

W：航班可用座位數

N：團隊旅客總人數

pil：航班i上 l艙的的散客價格

D ：散客預測數量，Di=（di1，di2，…，dil），dil是散客在票價 l的需求，為獨立正態分布，dil服從 N（μil，）分布上層規劃的目標為航空公司的收益最大，目標函數如下：

其中，

下層規劃目標從考慮旅行代理接受拆團方案的程度方面來分配團隊旅客：

Bi為各影響因素的模糊評價值。

3 旅行社接受拆團方案的評估

熵（Entropy）是一個熱力學概念，由Shannon引入信息論對系統的無需程度進行度量以及數據提供的有效信息量，在此模型中表示旅行社受各種因素影響程度的不確定性。人們可以根據熵值以及熵權的大小來進行決策，熵值越小熵權越大則該因素對決策起到了很重要的作用，對決策結果有較大影響。模糊綜合評價是對受多種因素影響的事物做出全面評價的一種十分有效的多因素決策方法，對于具有多種屬性的事物需要進行綜合評價，而對每種屬性的評價又無法給出定量的評價值，使用模糊綜合評價法可以有效解決這一問題[4]。

3.1 建立評價矩陣

構建n個樣本m個影響因素的判斷矩陣R′=（r′ij）nm（i=1，2，…n；j=1，2，…m。拆團對于旅行代理來講管理成本的變化不大。導游的薪酬組合大致為：基本工資＋帶團津貼＋“回扣”＋少量小費，由于每個導游帶的人數比例固定，所以拆團不會導致導游人數的增加。總的團隊旅客人數不變，所以即使拆團，只要合理的安排接送旅客，則車輛數量也無變化。不同的航班可能有的航班直達，有的航班轉機，因此航空公司給出的折扣航班之間有差別，這是一個很重要的影響因素。航班準點率也是很重要的影響因素之一，這是旅客對服務滿意度的重要評價指標之一[4]。拆團之后，旅行代理的旅游行程安排也會受到一定的影響，由于到達人員時間不一樣，與最佳的行程開始時間有個偏差，旅行代理根據這個偏差對行程做進一步調整。所以影響旅行代理拆團的因素主要有折扣率、航班準點率和預期到達時間偏差這3個因素。

3.2 評價矩陣歸一化

歸一化是一種簡化計算的方式，即將有量綱的表達式，經過變換，化為無量綱的表達式，成為純量[6]。 因評價矩陣中各影響因素的單位不一致，因而必須對數據進行歸一化處理。

對于成本型指標：

3.3 評價矩陣熵權的計算

各影響旅行商接受拆團方案的因素在指標上的值完全相同，熵值達到最大值1，熵權為0表示該指標未向決策提供任何有用信息；若某一因素在指標上的值相差較大，熵值較小，熵權較大時說明該因素提供了一定的信息量，對決策具有一定的影響，應重點分析[5]。

各因素對全部樣本的比重為：

由評價特征矩陣R和綜合權重向量W，利用模糊數學理論可以得到模糊綜合評判模型：

可以根據計算結果Bi的值來對旅行商對航班i的可接受度做出有效估計，Bi的值越大則旅行商對航班i的可接受度就越高。

4 模型求解

雙層規劃模型是由Bracken和McGill在1973年提出的，它是一個雙層決策系統優化的數學模型，具有二層遞階結構的特點，避免了由于單一層次決策方法帶來的弊端[7]。由于雙層規劃方法與傳統的單層規劃方法相比具有不可比擬的優勢，具體表現在:1）可以同時分析決策過程中兩個不同的、相互矛盾的目標；2）雙層規劃多價值準則的決策方法更接近實際情況；上層決策者和下層決策者都有各自的目標函數和約束條件，上層先給出一個決策變量，下層各子系統以這個決策變量為參量，根據自己的目標函數和約束在可能的范圍內求得一個最優值，并將此最優值反饋給上層，上層再在下層的最佳反應的基礎上，在可能的范圍內求得整體上的最優解。一般說來，求解雙層規劃問題比較困難，Hansen（1992）對雙層線性規劃是強NP-hard問題給出了嚴格的證明，其后，Vicente（1994）年指出尋找局部最優解也是NP-hard問題，不存在多項式求解算法，其原因在于即使上下層中目標函數和約束函數都是線性的，它依然可能是一個并且非處處可微的非凸問題。目前雙層線性規劃算法主要有：極點算法，分枝定界法，K-T法，模糊數學算法[6]。這些算法都是針對特定的雙層規劃模型設計的，不具廣泛性 ，針對某一實際問題還需設計適合的算法。針對本文模型特設計如下求解思路：給出上層規劃決策變量一個取值，然后將其帶入下層規劃模型，求出下層規劃模型的最優決策變量；將此最優決策變量代入上層規劃模型，求出上層規劃的最優值，重新帶入到下層規劃模型中，如此上下兩層模型反復迭代一直到收斂于一個精度得出最優解。

本文中模型，上層規劃的決策變量與下層規劃的決策變量存在著內在聯系，但很難直接求出兩者關系的具體表達式，因此之前提及的分層迭代方法求解。其具體思路為：首先進行初始化，給出一個拆團的初始方案；設定一個航班選擇的初始方案U將其代入下層規劃L中，利用單純形法算法求解下層規劃問題，得團隊旅客最優分配方案為N代入到上層規劃中進行求解，獲得新的航班選擇方案U然后將其代入下層規劃，再一次求解團隊旅客配的最優方案N如此重復計算，最后收斂于雙層規劃模型的最優解。

具體步驟如下：

1）設定一個航班選擇方案的初始解I0，令迭代次數k=1；

2）將初始解I0帶入下層求最優解，得旅客分配方案N0及下層規劃的目標函數值fn+1；

3）基于N0求解上層規劃問題得到新的航班選擇方案In+1及上層規劃目標函數值Fn+1；

5）得雙層規劃模型的最優解和最優值。

該算法的關鍵是對每層問題分別進行求解，而單層規劃模型的求解已經有較成熟的方法和計算機軟件可用利用，利用Maple軟件對模型進行求解取得了較好的實驗結果。

5 算例分析

現有一45人的團隊，在城市A到城市B有4個航班，航線上所用機型一致，經濟艙可用座位數120。表1所示為各航班不同艙位價格、散客需求以及航班到達時刻。表2所示為影響旅行商接受拆團方案的因素，管理成本，旅客滿意度以及票價。行程開始的預期時刻為15:00。

表1 航線上航班各艙位情況Tab.1 Status of different cabin

表2 影響旅行代理分配方案的因素Tab.2 Factors influencing the travel agency’s acceptance to group passenger distribution

標準化后的特征矩陣為：

熵 H=[0.846 0.864 0.883]，各影響因素熵權 W=[0.326 0.333 0.341]，進而得綜合評分B=[0.635 0.63 0.381 0.335]。通過用maple軟件編程得計算結果：

上層規劃：最優解U=[1 1 0 0]，最優值F=89.7

下層規劃：最優解N=[18 27 0 0]，最優值 f=145.34

由結果可以看出綜合得分較低的航班3沒有分配到團體旅客，雖然其折扣比較低，與預期達到時間差也較小，4航班也沒有分配到團體旅客，這是其準點率較低的緣故。

6 結 論

提出利用雙層規劃模型對團隊旅客進行拆團，上層規劃以航線上航班總收益最大為目標，下層以旅行代理接受拆團方案為目標，使得航空公司在增加收益的同時又不會失去旅行代理商。其中下層規劃中影響旅行代理接受拆團方案的因素用綜合評分得以體現，采用基于熵權法對影響旅行代理決策的因素進行評價，先計算出各影響因素的權重，乘以標準判斷矩陣得出各旅行代理對拆團方案的接受度。最后，設計了雙層迭代算法求解模型，并結合實例驗證了模型和算法的有效性。

[1]高強.航空收益管理中艙位控制問題的研究 [D].南京：南京航空航天大學，2006.

[2]高榮環，許莉.團隊旅客收益管理研究[D].南京：南京航空航天大學碩士學位論文，2010.

[3]梅虎，朱金福，汪俠.基于旅客艙位選擇的航空收益管理[J].系統工程，2006（9）:25-30.MEI Hu，ZHU Jin-fu，WANG Xia.Revenue management based on passenger seat choice behavior[J].Systems Engineering，2006（9）:25-30.

[4]姚韻，朱金福.基于可拓權重的航班延誤服務旅客滿意度多級模糊評價模型[J].商業研究，2007（7）:90-125.YAO Yun，ZHU Jin-fu.Based on extension weight flight service passenger satisfaction multi-step fuzzy assessment model[J].Commerce Study，2007（7）:90-125.

[5]王旭，葛顯龍，林云.供應商選擇的雙層規劃模型及求解分析[J].計算機工程與應用，2009，45（23）：11-14.WANG Xu，GE Xian-long，LIN Yun.Bi-level programming mode l and solutions analysis for supplier selection[J].Computer Engineering and Applications，2009，45（23）：11-14.

[6]Weber C A，Currint J R.A multi objective approach to vendor selec-tion[J].European Journal of Operational Research，2003，68（2）：73-84.