1.   引言

航空公司采用收益管理技术提升了2%至8%的票务年收入^[1]。机票动态定价是收益管理的核心，旨在构建航班机票售价策略，将不同票价等级的机票适时地销售给不同的消费者，以实现收益最大化。

Gallego等人^[2]使用强度控制理论求解了不确定需求下预期收入的上限。Otero等人^[3]采用阶段类型分布和更新过程建模客户购买机票的时间及购买概率。Delahaye等人^[4]通过细分商务和休闲旅客的不同价格敏感度进行动态定价。高金敏等人^[5]研究了时变需求下动态定价模型。Selcuk等人^[6]针对4种不同的价格需求关系提出了精确的动态规划方法。除了上述面向垄断市场环境的定价研究^[1-6]，还有从竞争角度出发的定价研究^[7,8]。Lin等人^[7]构建了基于博弈论的实时价格预测模型。施飞等人^[8]通过航空公司与旅客的动态博弈解决各等级票价的售票时间。

现有机票动态定价方法都建立在提前预测各票价等级的需求量基础之上。然而，实际应用中各等级票价的需求量受节假日、季节、售票时机等诸多因素影响。基于历史销售数据进行函数拟合的需求量预测方法存在预测偏差，降低了建立在需求量预测方法之上的模型性能。为此，本文提出基于策略学习的机票动态定价算法。其核心是不再直接预测各票价等级的需求量，而是从历史购票数据上学习具有最大期望收益的机票定价策略。在两趟航班两年历史销售数据上的多组模拟定价结果表明：相比于现行定价策略，策略学习算法的票务收益平均提升率分别为30.94%和39.96%，且比需求量预测方法提升了6.04%和3.36%。

目前存在将强化学习应用于收益管理领域的研究，如电动汽车^[9]、广告竞价^[10]、可再生能源管理^[11]、机票超售及座位控制^[12-15]。Gosavii等人^[12]提出了面向超售和多等级票价的半马尔可夫决策模型。Shihab等人^[13]采用深度强化学习优化航班座位控制策略。Qiu等人^[14]建模了旅客行为驱动的航班定价。Lawhead等人^[15]提出一种航班座位收益有界的动作评论算法。不同于上述工作，本文聚焦于采用离线强化学习求解机票动态定价策略。

2.   航班机票动态定价算法

在机票销售期内以某票价等级出售机票，售票系统会得到立即收益，即座位销售数×票价等级×机票全价，同时减少航班剩余座位数。为了最大化后期座位收益，航班剩余座位数又影响下一时刻的机票定价。为此，机票动态定价受航班剩余座位数、定价策略和收益等相互影响，可建模为强化学习问题。

航班机票动态定价的强化学习要素分别为：(1)状态集${{S}}$表示航班剩余座位数。设$n$为某航班座位容量，航班在时刻$t$的状态(剩余座位数)${s_t} \in {{S}} =$$\{ n,n{\rm{ - 1}}, ··· ,{\rm{0}}\}$。(2)动作集${{A}}$表示所有的票价等级，本质为经济舱全票价的折扣率。航班在时刻$t$采用的动作(票价等级)为${\alpha _t} \in {{A}}$。(3)策略函数$\pi (\alpha {\rm{|}}s)$表示在状态$s$下执行动作$\alpha$的概率。策略函数是算法的学习目标，使得算法根据它产生动作序列。(4)收益函数$r(s,\alpha )$表示在状态$s$下执行动作$\alpha$的立即收益，取值为$p \times \alpha \times N$，其中$p,N$分别为经济舱全价和销售的座位数。

引入动作值函数${q_{\pi} }(s,\alpha )$以评估策略函数$\pi (\alpha {\rm{|}}s)$的好坏程度，见式(1)。式(1)的物理含义是给定状态$s$沿着策略$\pi$执行序贯性决策后预期总折扣奖励。

其中，${{\rm{E}}_{\pi} }[ \cdot ]$表示在策略$\pi$下的期望收益。$\gamma \in [0,1]$表示收益折扣因子，决定了未来收益的现值，即$t + 1$时刻的收益只有当前收益的${\gamma ^t}$倍。学习目标是构建具有最大值${q_{\pi} }(s,\alpha )$的最优策略${\pi ^*}$，使得对于任何状态$s$都有$q(s,{\pi ^*}(s)) \ge {q_{\pi} }(s,\alpha )$。此时最优策略${\pi ^*}$的Bellman方程展开为

其中，$\Pr ({s_{t + 1}}|{s_t} = s,{a_t} = a)$表示在状态${s_t}$下执行动作${a_t}$后跳转到状态${s_{t + 1}}$的概率。由于机票销售过程无法建模上述转移概率而仅可观察剩余座位数${s_{t + 1}}$，采用时序差分法^[16]更新动作值函数。

其中，$\eta$表示学习速率。当动作值函数通过更新达到收敛后，每个状态$s$在最优策略${\pi ^*}$的动作${\pi ^*}(s)$为

由于航班动态定价的状态空间和动作空间都离散且有限，提出基于策略学习的机票动态定价算法，见表1。算法首先初始化一个2维矩阵Q-table以表示动作值函数$q(s,\alpha )$，其中矩阵的行数为状态空间数$\left| {{S}} \right|$，列数是动作空间数$\left| {{A}} \right|$。其次，在航班的第1天到$T - 1$天的历史销售序列上依次据式(3)和式(4)进行策略$\pi$的评估和改进。重复上述循环操作，直至算法达到预先设定的最大迭代次数。

表 1  机票动态定价策略学习算法

输入 学习速率$\eta$，折扣因子$\gamma$，最大迭代次数${\rm{episodes}}$，航班总座位数$N$ 航班第1天到$T - 1$天的历史销售序列${\rm{\{ }}s_{\rm{0}}^{{\rm{(}}n)},a_{\rm{0}}^{(n)},r_{\rm{0}}^{(n)}, ··· ,s_v^{(n)},a_v^{(n)},r_v^{(n)}{\rm{\} }}_{n = {\rm{1}}}^{T - {\rm{1}}}$
初始化 对于任何状态$s$和$\alpha ,$$q(s,\alpha ) = 0,k = 0,n = 1$
Repeat：
Repeat (对于第1天到$T - 1$天的每趟离港航班)：
Repeat (对于此趟航班历史销售序列的每一步$(s_t^{(n)},a_t^{(n)},r_t^{(n)},s_{t + {\rm{1}}}^{(n)})$)：
策略评估：据式(3)更新动作值函数$q(s_t^{(n)},a_t^{(n)})$
策略更新：按式(4)调整策略$\pi (s_t^{(n)}) = \arg {\rm{ma}}{{\rm{x}}_\alpha }q(s_t^{(n)},a)$
Until 航班没有剩余座位或售票时间截止
$n \leftarrow n + 1$
Until $n > T - 1$
$k \leftarrow k + 1$
Until $k > {\rm{episodes}}$
输出 第$T$天的机票动态定价策略$\pi (s) = \arg {\max _\alpha }q(s,\alpha )$

下载: 导出CSV 

| 显示表格

3.   实验

3.1   实验设置

3.1.1   数据集

实验数据集是航班历史机票销售序列，是由2010年1月1日到2011年12月31日的民航旅客订票日志PNR (Passenger Name Record)生成的。一条PNR是一次订票信息，主要字段包括旅客身份证号码(信息加密)、航空公司、航班号、出发机场和到达机场(机场三字码表示)、订单编号、票价等级等，示例见表2。

表 2  旅客订票记录示例

身份证号	航空公司	航班号	出发机场	到达机场	出发日期	订单编号	票价等级
52893787	CA	1501	PEK	SHA	20100308	2273651247	0.5213
55503718	CA	1501	PEK	SHA	20100308	2745812364	0.8212

下载: 导出CSV 

| 显示表格

在民航旅客订票日志上第$n$天离港航班的机票销售序列生成过程为：首先按照组合字段(航班号，离港日期)筛选出此航班在第$n$天的订票记录，其次对筛选的记录按订单号升序排列，然后将具有相同订单号的订票记录合并以生成一个四元组$(s_t^{(n)},a_t^{(n)},r_t^{(n)},s_{t{\rm{ + 1}}}^{(n)})$。其中$s_t^{(n)}$表示第$n$天离港航班在时刻$t$销售前的航班剩余座位数；$a_t^{(n)}$为当前订单的票价等级；$r_t^{(n)}$表示执行动作$a_t^{(n)}$的收益，取值为当前订单机票销售数$\times$票价等级$\times$机票全价；$s_{t{\rm{ + 1}}}^{(n)}$表示时刻$t$销售后的航班剩余座位数。重复上述过程，直至生成航班机票销售序列。

折中于算法在民航旅客订票日志上所有航班的运行时间，以及评价航班每一天动态定价策略，挑选在航线热度、经济舱总数、实际销售等方面差异较大的两个航班CA1501和JR1505进行实验，其统计信息见表3。民航旅客订票日志中票价等级的精度为0.0001，且各票价等级销售的机票数比较稀疏。意味着很多二元组(剩余座位数，票价等级)未在历史数据中出现，使得这些元组对应的动作值函数无法更新，导致后期动态定价存在较大的偏差。比如航班CA1501历史销售轨迹中产生了5737种票价等级，而各票价等级产生平均机票数为22.68，这表明动作值函数矩阵Q-table中某一列平均至少有255–22.68个元素未被更新，累计有5737×(255–22.68)个元素未更新，其中255是航班CA1501的总座位数。精确度为千分位也会产生类似的结论。为此，实验中将票价等级精度降至百分位，并在实验中分析万分位精度对航班座位收益的影响。

表 3  实验数据集的统计信息

航班	售票记录 总数	销售 序列数	状态、动作等 四元组数	原始票价等级 (精确到万分位)			预处理后的票价 等级(精确到千分位)			预处理后的票价 等级(精确到百分位)
				票价 等级数	各等级 平均票数		票价 等级数	各等级 平均票数		票价 等级数	各等级 平均票数
CA1501	130118	718	102809	5737	22.68		1087	119.70		150	867.45
JR1505	22691	611	17102	2359	9.62		745	30.46		90	254.96

下载: 导出CSV 

| 显示表格

3.1.2   评价指标

为评价航班动态定价策略好坏程度，定义航班收益平均提升率ALR@T(Average Lift Rate at T days)：

其中，ALR@T计算从第2天到第$T$天航班收益提升率的均值。从第2天开始实验评价的原因是：第1天没有历史销售序列导致算法无法学习第1天的航班定价策略；${\rm{(}}G_{\pi} ^{(n)} - G_g^{(n)}{\rm{)}}/G_g^{(n)}$是第$n$天航班的收益提升率；$G_{\pi} ^{(n)}$表示根据第$n$天动态定价策略$\pi$产生的收益；$G_g^{(n)}$则是基准算法在第$n$天航班上定价策略的收益。

3.1.3   基准算法

(1)航班现行定价策略

历史销售序列本质反映航班现行定价策略。为了能与现行策略比较，动态定价策略$\pi$采取类似方法售票：在第$n$天离港航班的时刻$t$，若现行策略以票价等级$a_t^{(n)}$销售$N_t^{(n)}$张机票，则动态定价策略$\pi$在时刻$t$状态$s_t^{(n)}$会以票价等级$\pi (s_t^{(n)})$销售$N_t^{(n)}$张机票。此时现行策略的收益$G_g^{(n)}$和定价策略$\pi$的收益$G_{\pi}^{(n)}$分别为

(2)票价等级需求量预测方法

票价等级需求量预测方法利用前$n - 1$天机票销售记录，预测航班第$n$天各票价等级的需求量。在软件1stOpt上利用麦夸特法分别拟合航班CA1501和JR1505的票价等级需求函数，平均拟合优度为94.28%和92.37%。设航班第$n$天各票价等级${\alpha _1}, ··· ,{\alpha _{|{{A}}|}}$的需求量为${n_1}, ··· ,{n_{|{{A}}|}}$，需求量预测方法的收益$G _g^{(n)} = \displaystyle\sum\nolimits_{i = 1}^{|A|} {{a _i}{n_i}}$。

由于需求量预测方法无法产生机票销售序列，而策略$\pi$却需根据剩余座位数选择票价等级，两者无法直接对比。为了能够对比，策略$\pi$基于如下假设售票：(a)将航班机票售卖期划分为$m$个离散周期$l = 1,2, ··· ,m$；(b)各周期内旅客购买票价等级${\alpha _i}$的数量服从均值为${{{n_i}} / m}$的泊松分布；(c)每次仅售1张机票。使用${h_{li}}$表示第$l$周期中票价等级${\alpha _i}$的销售量，第$l$周期总销售量为${h_l} = \displaystyle\sum\nolimits_{i = 1}^{\left| {{A}} \right|} {{h_{li}}}$。两定价策略在第1张机票销售收益差${\varDelta _1}$：

其中，$\arg {\max _\alpha }q(s_0^{(n)},\alpha )$表示策略$\pi$在状态$s_0^{(n)}$下采取动作$a = \pi {\rm{(}}s_0^{(n)}{\rm{)}}$的收益。$\displaystyle\sum\nolimits_{i = 1}^{|{{A}}|} {{{{h_{1i}}{\alpha _i}}/ {{h_1}}}}$是需求量预测方法的第1张机票平均收益，其计算原理是：因无法建模机票销售顺序，假设所有销售序列都是等可能的，则第1周期内第1张机票以票价等级${\alpha _{\rm{1}}}, ··· ,{\alpha _{\left| {{A}} \right|}}$出售概率是${{{h_{{\rm{11}}}}} / {{h_{\rm{1}}}}}, ··· ,{{{h_{\rm{1}}}_{\left| {{A}} \right|}} / {{h_{\rm{1}}}}}$。依式(7)类推，第1周期内总收益差为

其中，$\left| {{S}} \right|$为航班总座位数。依式(8)计算$m$个周期的收益差，需求量预测方法和策略$\pi$在第$n$天航班收益差为

3.1.4   参数设置和运行环境

航班CA1501和JR1505经济舱总座位数$N$分别为255和52。算法需预先设置的参数分别为：学习速率$\eta = 0.2,0.4,0.6,0.8$、折扣因子$\gamma = 1$、算法总迭代次数${\rm{episodes }} = 5000$。算法硬件环境为Intel(R) Xeon(R) Silver 4110、主频3.4 GHz、内存126 GB。实验训练共耗约142 h。

3.2   实验对比及分析

3.2.1   航班 CA1501实验结果

在航班CA1501进行了717组实验，其结果见图1(a)。相比于现行定价策略，动态定价策略$\pi$的收益平均提升率${\rm{ALR@T}}$为30.94%；相比票价等级需求量预测方法，平均提升率为6.04%。

图 1  两个航班上定价策略的性能对比

下载: 全尺寸图片 幻灯片

图1(a)中动态定价策略$\pi$相比于现行定价策略的提升率曲线—策略$\pi$vs现行定价策略—可分为4段。在2010年1月2日到2010年2月10日，1月1日至1月3日票务收益较差，使得学习后的策略收益也低。1月4日收益较1月3日增长了115%，算法能快速学习此定价策略以用于后续定价。故此阶段内曲线出现骤增，平均提升率${\rm{ALR@T}}$稳定至约35%。在2010年2月11日到2010年2月19日曲线出现第2次骤增，其原因是：2010年2月11日为农历腊月二十八，出现“倒春运”，即机票销售数和价格都明显下跌，期间平均收益仅为整体的32.29%。然而，定价策略$\pi$是从2月11日之前销售数据上学习，导致策略$\pi$的机票价格要高于“倒春运”期间价格，出现较大收益差值。第3段为2010年2月11日到2011年1月30日，曲线逐渐降低并趋于平稳，收敛至约21%。其原因是：在大量历史数据上的学习，动态定价策略与现行定价策略的收益差值逐渐减小。最后一次曲线提升发生在2011年2月1日，其原因是：2011年2月1日为农历腊月二十九，也出现“倒春运”，因在大量历史数据上的学习避免了类似第1次突变，趋于平稳。

图1(a)也列出了定价策略$\pi$相比于需求量预测方法的提升率曲线—策略$\pi$vs需求量预测方法。实验初期因训练数据较少，动态定价策略产生的收益低于需求量预测方法。随着训练数据的增加，策略学习方法与需求量预测方法的收益差距逐渐减小，曲线平稳提升并趋于稳定，最终收益平均提升率为6.04%。

3.2.2   航班JR1505实验结果

相比于航班CA1501，航班JR1505收益更易受定价影响。航班JR1505上的610组实验结果见图1(b)。动态定价策略$\pi$相比于现行定价策略和需求量预测方法的收益平均提升率${\rm{ALR@T}}$分别为39.96%和3.36%。

从图1(b)可知，动态定价策略$\pi$相比于现行定价策略的提升率曲线—策略$\pi$vs现行定价策略，主要可分为3段。2010年1月26日到2010年11月10日为第1个增长期。定价策略$\pi$通过不断学习以往经验，平均提升率${\rm{ALR@T}}$逐渐提升，在4月20日趋于平稳，收敛至25%。第2个增长周期发生在2010年11月2日，其原因是：航班JR1505在此后一个月机票销售收益较前一月平均降低了43.80%，使得收益差值增加，曲线逐渐上升。第3个拐点发生在2011年4月20日，其原因是：航班由淡季转为旺季，此后一月较上月收益提升41.22%。实际收益的提升使得差值逐渐减小，曲线回落并重新收敛至39%。此外，相比于需求量预测方法，策略学习方法随着不断学习，平均提升率${\rm{ALR@T}}$平稳提升并趋于稳定，最终收敛至约3%。

3.3   票价等级精度对收益的影响

表4表明不同的票价等级精度产生不同规模的票价等级，为此分析票价等级精度对算法性能的影响。表4列出2011年6月22日航班CA1501在票价等级精度为0.0001和0.0100的实验结果。万分位精度产生了4590个动作，而百分位精度缩减至120个动作。百分位精度较万分位在平均提升率${\rm{ALR@T}}$上提升3.17%。

表 4  票价等级精确度影响分析

票价等级 精度	训练集中票价 等级总数	定价策略中出现 票价等级总数	收益平均提升率 ${\rm{ALR@T}}$(%)
0.0001	4590	128	13.21
0.0100	120	16	16.38

下载: 导出CSV 

| 显示表格

分析算法在精度为0.0100时性能提升的原因。图2(a)列出票价等级精度分别为0.0100和0.0001时定价策略$\pi$在各状态上的票价等级差值。统计表明，不同精度下的模型在所有状态上采取的票价等级总体相差不大，票价等级差的均值为0.05，方差为0.006。仍有部分点波动较大，造成收益差距。图2(b)以波动点—剩余座位数196为例分析。当精度为0.0001时，采取的票价等级为0.8453，落在区间(0.84,0.85]频数为8。当精度为0.0100时，采取的票价等级为1.04，落在区间(1.03,1.04]频数为65。为此，精度为0.0100更易捕捉具有明显集中趋势的“众数”票价等级，以代表此状态下整体票价水平，而非选择出现频次最高的单一票价等级。

图 2  2011年6月22日航班CA1501在精度为0.0100和0.0001下的实验对比

下载: 全尺寸图片 幻灯片

3.4   学习速率的影响分析

学习速率$\eta$影响着算法的收敛速度和定价策略的收益，以2011年12月31日航班CA1501为例分析学习速率的影响。图3(a)指出学习速率为0.2, 0.4, 0.6, 0.8时，算法收敛的迭代次数依次为4860, 2167, 1274, 788。因此，经验上学习速率在0.2以上就能保证算法收敛。图3(b)指出算法在5000次迭代时，增大学习率不会对收益平均提升率${\rm{ALR@T}}$产生影响，其中计算${\rm{ALR@T}}$的基准算法为航班现行定价策略。

图 3  学习速率对算法性能的影响

下载: 全尺寸图片 幻灯片

上述经验分析指出学习速率$\eta = {\rm{0}}{\rm{.2,}}0.4,0.6,0.8$都是可取范围，在实验过程中学习速率取值为0.6，其原因：(1)折中于算法整体运行时间。由于航班CA1501和JR1505分别需要进行717和610组实验，而每组实验的运行时间正比于算法迭代次数，当学习速率$\eta = 0.6$时，算法能够更快收敛。(2)突出同一趟航班上离起飞日期越近的座位票价影响要略大于较早售出座位的票价。当将式(3)重写为${q_{{\pi ^*}}}({s_t},{a_t}) = (1 - \eta ){q_{{\pi ^*}}}({s_t},{a_t}) + \eta (r({s_t},{\alpha _t}) + \gamma \mathop {\max }\limits_{{a_{t + 1}}} {q_{{\pi ^*}}}$$({s_t}_{{\rm{ + 1}}},{a_t}_{{\rm{ + 1}}}))$时，可知学习速率$\eta$越大，保留之前训练的效果就越少。如学习速率为1，则训练过程中只考虑新销售的座位的票价，不保留之前训练的效果，不符合实际。

4.   结论

针对航班票价定价过程中航班剩余座位数与机票价格相互影响，提出了基于策略学习的机票动态定价算法。算法通过定价策略评估和策略更新，输出具有最大期望收益的机票动态定价策略。在海量民航旅客订票日志上两个航班的多组模拟定价结果表明：相比于现行机票销售策略和需求量预测方法，算法在收益平均提升率上有显著的提升。后续将对航班状态的时序特征展开研究。