航線團(tuán)隊(duì)旅客收益管理雙層規(guī)劃模型

徐 琪，徐月芳

（南京航空航天大學(xué) 民航學(xué)院，江蘇 南京 210016）

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

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

1 問題描述

當(dāng)單一航班上的可用座位數(shù)不能滿足團(tuán)隊(duì)旅客需求的時(shí)候，將團(tuán)隊(duì)拆分在同一航線的不同航班上可有效提高航班的客座率增加收益。但團(tuán)隊(duì)拆分的同時(shí)對(duì)于旅行代理商來說不僅意味著增加了管理難度，也可能引起旅客滿意度的下降。因此，航空公司在以收益最大化為目標(biāo)進(jìn)行團(tuán)隊(duì)拆分時(shí)也要兼顧到旅行代理商的可接受程度?；谶@種關(guān)系，可以用雙層規(guī)劃模型（Bi－level programming）來描述，上層規(guī)劃（U）描述為航空公司拆分團(tuán)隊(duì)時(shí)以航線總收益最大化為目標(biāo)。下層規(guī)劃（L）描述為航空公司將團(tuán)隊(duì)在分配在不同的航班上，其目標(biāo)是盡量提高旅行代理商的可接受度。上層規(guī)劃在散客預(yù)測(cè)的基礎(chǔ)上從收益最大化角度給出航空公司一個(gè)拆分方案，Belobaba在1987年提出了著名的EMSR理論，此后多年雖然有多種變化，但基于EMSR的艙位控制策略幾乎成了一種工業(yè)標(biāo)準(zhǔn)[3]。下層規(guī)劃即根據(jù)旅行代理商的可接受度來決定拆分到哪些航班上多少人。某些航班可能因?yàn)楹娇展臼找娓弑贿x擇，但在下層規(guī)劃中可能因?yàn)槁眯写砩坛鲇谀承┮蛩氐目紤]而安排團(tuán)隊(duì)旅客較少，甚至為零。上層規(guī)劃和下層規(guī)劃反復(fù)的相互影響，既可增加航空公司的收益，且同時(shí)兼顧旅行代理商，有益于航空公司的良性發(fā)展。

2 建立團(tuán)隊(duì)旅客收益模型

2.1 模型假設(shè)

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

1）航線上單一航班在散客預(yù)測(cè)的基礎(chǔ)上剩余座位不能滿足同一團(tuán)隊(duì)旅客的需求；

2）團(tuán)隊(duì)旅客不占用頭等艙、商務(wù)艙座位；

3）不同艙位的散客需求呈正態(tài)分布且獨(dú)立；

4）團(tuán)隊(duì)整體最多拆分在3個(gè)航班上。

2.2 模型建立

符號(hào)意義：

pgi：不同航班團(tuán)隊(duì)旅客的價(jià)格

ni：分配在不同航班上團(tuán)隊(duì)旅客的人數(shù)

ci：每個(gè)航班上散客人數(shù)

W：航班可用座位數(shù)

N：團(tuán)隊(duì)旅客總?cè)藬?shù)

pil：航班i上 l艙的的散客價(jià)格

D ：散客預(yù)測(cè)數(shù)量，Di=（di1，di2，…，dil），dil是散客在票價(jià) l的需求，為獨(dú)立正態(tài)分布，dil服從 N（μil，）分布上層規(guī)劃的目標(biāo)為航空公司的收益最大，目標(biāo)函數(shù)如下：

其中，

下層規(guī)劃目標(biāo)從考慮旅行代理接受拆團(tuán)方案的程度方面來分配團(tuán)隊(duì)旅客：

Bi為各影響因素的模糊評(píng)價(jià)值。

3 旅行社接受拆團(tuán)方案的評(píng)估

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

3.1 建立評(píng)價(jià)矩陣

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

3.2 評(píng)價(jià)矩陣歸一化

歸一化是一種簡(jiǎn)化計(jì)算的方式，即將有量綱的表達(dá)式，經(jīng)過變換，化為無(wú)量綱的表達(dá)式，成為純量[6]。 因評(píng)價(jià)矩陣中各影響因素的單位不一致，因而必須對(duì)數(shù)據(jù)進(jìn)行歸一化處理。

對(duì)于成本型指標(biāo)：

3.3 評(píng)價(jià)矩陣熵權(quán)的計(jì)算

各影響旅行商接受拆團(tuán)方案的因素在指標(biāo)上的值完全相同，熵值達(dá)到最大值1，熵權(quán)為0表示該指標(biāo)未向決策提供任何有用信息；若某一因素在指標(biāo)上的值相差較大，熵值較小，熵權(quán)較大時(shí)說明該因素提供了一定的信息量，對(duì)決策具有一定的影響，應(yīng)重點(diǎn)分析[5]。

各因素對(duì)全部樣本的比重為：

由評(píng)價(jià)特征矩陣R和綜合權(quán)重向量W，利用模糊數(shù)學(xué)理論可以得到模糊綜合評(píng)判模型：

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

4 模型求解

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

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

具體步驟如下：

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

2）將初始解I0帶入下層求最優(yōu)解，得旅客分配方案N0及下層規(guī)劃的目標(biāo)函數(shù)值fn+1；

3）基于N0求解上層規(guī)劃問題得到新的航班選擇方案In+1及上層規(guī)劃目標(biāo)函數(shù)值Fn+1；

5）得雙層規(guī)劃模型的最優(yōu)解和最優(yōu)值。

該算法的關(guān)鍵是對(duì)每層問題分別進(jìn)行求解，而單層規(guī)劃模型的求解已經(jīng)有較成熟的方法和計(jì)算機(jī)軟件可用利用，利用Maple軟件對(duì)模型進(jìn)行求解取得了較好的實(shí)驗(yàn)結(jié)果。

5 算例分析

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

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

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

標(biāo)準(zhǔn)化后的特征矩陣為：

熵 H=[0.846 0.864 0.883]，各影響因素熵權(quán) W=[0.326 0.333 0.341]，進(jìn)而得綜合評(píng)分B=[0.635 0.63 0.381 0.335]。通過用maple軟件編程得計(jì)算結(jié)果：

上層規(guī)劃：最優(yōu)解U=[1 1 0 0]，最優(yōu)值F=89.7

下層規(guī)劃：最優(yōu)解N=[18 27 0 0]，最優(yōu)值 f=145.34

由結(jié)果可以看出綜合得分較低的航班3沒有分配到團(tuán)體旅客，雖然其折扣比較低，與預(yù)期達(dá)到時(shí)間差也較小，4航班也沒有分配到團(tuán)體旅客，這是其準(zhǔn)點(diǎn)率較低的緣故。

6 結(jié) 論

提出利用雙層規(guī)劃模型對(duì)團(tuán)隊(duì)旅客進(jìn)行拆團(tuán)，上層規(guī)劃以航線上航班總收益最大為目標(biāo)，下層以旅行代理接受拆團(tuán)方案為目標(biāo)，使得航空公司在增加收益的同時(shí)又不會(huì)失去旅行代理商。其中下層規(guī)劃中影響旅行代理接受拆團(tuán)方案的因素用綜合評(píng)分得以體現(xiàn)，采用基于熵權(quán)法對(duì)影響旅行代理決策的因素進(jìn)行評(píng)價(jià)，先計(jì)算出各影響因素的權(quán)重，乘以標(biāo)準(zhǔn)判斷矩陣得出各旅行代理對(duì)拆團(tuán)方案的接受度。最后，設(shè)計(jì)了雙層迭代算法求解模型，并結(jié)合實(shí)例驗(yàn)證了模型和算法的有效性。

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

[2]高榮環(huán)，許莉.團(tuán)隊(duì)旅客收益管理研究[D].南京：南京航空航天大學(xué)碩士學(xué)位論文，2010.

[3]梅虎，朱金福，汪俠.基于旅客艙位選擇的航空收益管理[J].系統(tǒng)工程，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]姚韻，朱金福.基于可拓權(quán)重的航班延誤服務(wù)旅客滿意度多級(jí)模糊評(píng)價(jià)模型[J].商業(yè)研究，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]王旭，葛顯龍，林云.供應(yīng)商選擇的雙層規(guī)劃模型及求解分析[J].計(jì)算機(jī)工程與應(yīng)用，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.