基于偏好序的高铁票价与售票时间窗联合优化

闫振英，王宇，韩宝明，李晓娟*

(1.内蒙古大学，交通学院，呼和浩特 010020；2.北京交通大学，交通运输学院，北京 100044）

0 引言

经过大规模建设，我国高铁运营里程已达4 万km。高铁建设成本和运营成本较高，改善高铁收益是实现高铁可持续发展的重要保障。自2016年高铁定价权下放，国铁集团不断探索“一车一价”“一日一价”等灵活定价方式，以调节客流需求，平衡运力资源，提升客票收益。研究有效的灵活定价与售票控制机制，是改善高铁收益的重要途径。

收益管理技术大致可分为存量控制(Inventory Control)与动态定价两大类。近年来，收益管理理论研究聚焦在考虑旅客选择行为的网络收益管理(Choice-Based Network Revenue Management,CNRM)上[1]。其中，存量控制多用于独立需求的研究中，而在CNRM 中常用到可售控制(Availability Control)；动态定价可分为连续价格和离散价格。

铁路运输领域积极探索收益管理的应用研究。动态定价由史峰等[2]最早引入我国铁路运输领域，采用马氏纯灭过程得到离散价格的最优策略和实用策略。张小强等[3]针对单列车多停站服务网络，使用最大凹向包络法缩小离散价格备选集规模，提升求解速度。后续研究拓展到多列车多停站动态定价问题，例如，蔡鉴明等[4]基于多项Logit 模型优化各时段的连续价格。存量控制方面重点研究多列车多停站的网络售票控制问题。WANG等[5]在单一票价下基于多项Logit 模型优化不同类型列车的票额分配；骆泳吉等[6]提出设置通售席位的票额分配模型；YAN 等[7]放松容量约束，设置多等级票价，提出基于灵活编组的票额分配模型。考虑到票价和售票控制分别影响着需求和供给，两者的联合优化能够有效改善收益。赵翔等[8]将高铁列车差别定价和票额分配联合优化，采用人工蚁群算法求解；秦进等[9]将动态定价与票额分配协同优化，并设计分布求解算法；XU 等[10]将该协同优化模型重构线性化后，通过迭代求解获得全局最优解。既有联合优化的研究多采用多项Logit模型刻画旅客选择行为。该模型方便嵌入收益管理模型，获得较高效的近似控制策略，但确定概率函数需精确识别属性和标定大量参数，且受IIA (Independent of Irrelevant Alternatives)特性影响，需求估计易出现偏差。

基于偏好序的无参数选择模型不假定任何概率形式，由大量历史数据驱动，对需求的刻画更精确[11]。偏好序模型逐渐在收益管理中应用，例如，HOSSEINALIFAM等[12]提出存量控制模型，并设计列生成求解算法；BARBIER 等[13]提出可高效求解的可售控制模型，但缺乏对票价与售票控制联合优化的探索。

本文采用偏好序模型研究高铁票价与售票控制联合优化的方法，针对多列车多停站的服务网络，建立票价与售票时间窗的联合优化模型。考虑运营企业的售票要求将客票进行排序，设计粒子群与线性规划模型求解相结合的算法快速求解模型。结果可为高铁列车客票定价和制定售票控制策略提供决策支持。

1 模型构建

1.1 问题描述

针对多列车和多停站的高铁服务网络，为每列车每个OD的相同类型座位(例如二等座)设置若干客票等级，各等级票价允许在一定范围内波动。按照列车、OD和票价等级设置客票产品j，J表示所有客票产品集合。将每列车在每个区段上的座位资源表示为i，资源集合为I。客票产品与列车席位资源的占用关系用矩阵A=表示，其中，客票产品j占用列车区段资源i时，aij=1；否则，aij=0。rj表示客票产品j的票价，设置票价上限及下限保证票价优化不改变其客票等级。将客票销售期划分为τ个时段，t=0，售票开始；t=τ结束时，售票结束。一般来说，低价客票需提前开售，而高价客票提前开售也有利于增加收益，因此，将售票开始时间均设在t=0，通过优化停售时间设定售票时间窗进行售票控制。Tj表示客票产品j的停售时间，Tj∈[ ]0,τ。售票时间窗为[0,Tj]，即客票产品j在该时间段内可售，由于所有客票产品售票开始时间均设为0，售票时间窗也可直接表示为Tj。考虑旅客购买偏好的差异，l∈L表示购买行为相似的一类旅客，L为旅客类别集合，λl表示每个时段l类旅客的平均到达率。旅客购票需求具有价格弹性，票价可调节购票需求。售票时间窗则用来控制客票产品的供给状态。铁路运营企业通过决策每个客票产品j的最优票价rj和对应的停售时间Tj，同时调节旅客需求和客票产品供给，促进供需精细匹配，实现客票期望总收益最大。不考虑列车超员或超售的情况，也不考虑旅客的退票和改签行为。

1.2 偏好序模型

采用偏好序描述旅客的购票选择行为。将具有相同购买行为的旅客归为一类，该类旅客l的可选客票产品集合相同，为Cl，该集合中有nl个产品。Cl中客票产品排序反映了旅客的购买偏好顺序。当排名靠前的客票产品可售时，直接购买；否则，将以一定概率转移购买后续客票产品，依此类推，直到旅客购买某种客票或离开。用ϕl,j表示产品j在Cl中的排序，若j∈Cl，ϕl,j∈[1,nl]；若j∉Cl，ϕl,j=0。θ(lk-1,k)表示l类别旅客在前一个客票不可售时转移购买后一个客票的概率，方便起见，设定θ(l0,1)=1。子集C[lk]⊆Cl(k∈[1,nl])表示Cl中排在前k位的客票集。用S表示当前可售客票集合，旅客类别l面临可售客票集合S时，选择客票产品j的概率Pl(j|S)为

根据式(1)，旅客购买产品j的概率为Cl中排序在该产品之前的所有产品的转移概率的乘积。可将l类别旅客购买客票产品j的概率表示为Pl(j|{j})。转移概率的估计可参考文献[11]。

1.3 弹性需求

旅客购票需求相对价格具有一定弹性。各类旅客的平均到达率λl受到其偏好产品的价格影响。将l类旅客购买各偏好客票产品的概率Pl(j|{j})作为权重，近似得到l类旅客偏好客票产品的平均票价为

式中：为l类旅客偏好客票产品的平均票价。假设l类旅客的到达率受其偏好客票产品的平均票价影响，则l类旅客的弹性需求函数[9]为

式中：η为弹性系数；为根据历史售票数据推测得到的基准到达率；为根据历史销售情况推测得到的基准平均票价。

1.4 售票时间窗

客票产品j的售票时间窗可表示为Tj。依据偏好序购买逻辑，当排序靠前的客票产品可售时，旅客便不会购买排序靠后的客票产品，所以，售票时间窗并不是各类旅客实际购买客票产品j的持续时间段。为了计算客票销售量，需要根据售票时间窗Tj计算旅客购买客票产品的实际时间段。定义和分别表示各类别旅客购买各类客票的时间窗和客票停售时间。定义ψ(lk)∈Cl表示旅客类别l的偏好集合中第k个客票。定义γ∈[1,k-1]表示在偏好集合中客票排序在k之前。要使旅客类别l选择第k个客票，就需要设置第k个客票的停售时间晚于排序更靠前的客票。因此，类别l旅客购买产品k的时间窗为

1.5 票价与售票时间窗联合优化模型

旅客到达服从泊松过程，动态定价下的旅客平均到达率为λl，票价优化后产品j的售票量为

式中：为l类旅客可选集合中产品j的售票时间窗；λl依据弹性需求函数式(3)计算。

根据上述假设，以客票收益最大化为目标函数，以票价rj和停售时间Tj为决策变量，构建联合优化模型为

式中：Q为由Qj组成的向量；ci为各列车在各区段的席位资源i的最大席位数；c为由ci组成的向量。

式(7)以期望客票收益最大为目标函数；式(8)为列车容量约束；式(9)为各类旅客购买各客票产品的时间窗与停售时间的关系；式(10)为各类旅客任意前k个客票产品最晚停售时间；式(11)为客票产品停售时间的取值范围，由售票期决定；式(12)为票价的上下限约束，使票价波动不足以改变产品排序。

在停售时间控制中，可以用客票产品停售时间排序满足嵌套销售的需求。定义客票产品排序H={Hj}j∈J，如果对于客票产品∀u,v∈J,Tu ＞Tv，则Hu ＞Hv；若Tu=Tv，则Hu=Hv。一般来说，可按照运营企业的需要进行排序，例如，客票价格，价格除以资源数及单位里程价格等。当给定排序H时，模型中的非线性约束条件式(10)可以转化为

然后，上述联合优化模型可转换为以式(7)为目标函数，约束条件为式(8)，式(9)，式(11)～式(13)的等价模型。

2 求解算法

本文提出的联合优化模型为非线性规划，该类模型难以精确求解。价格需求弹性的引入使模型变得更为复杂，因此，本文构造粒子群与线性规划嵌套的求解算法。

外层采用粒子群迭代优化票价。将粒子位置定义为票价。迭代中，粒子按照一定速度更新位置。粒子速度更新规则为

式中：sg(m)为第g个粒子第m次迭代时的速度；Pg(m)为第m次迭代时自身最优位置；O(m)为第m次迭代时全局最优位置；rg(m)为第g个粒子第m次迭代时的位置；θ1和θ2为在区间(0,1)内的随机数；ω为惯性因子；c1为自身学习因子；c2为全局学习因子，通常取ω=c1=c2=0.5。粒子位置更新为

式中：μ=0.01。

内层调用CPLEX 求解线性规划，计算适应度函数。将适应度函数定义为期望总收益R，即式(7)目标函数。将粒子产生的票价方案输入式(3)，计算弹性客流需求。此时，等价模型转化为决策变量仅为售票时间窗的线性规划模型，调用CPLEX求解。将得到的适应度函数值返回到外层迭代，找到满意的票价和售票时间窗。

算法步骤如下。

Step 1 参数初始化。设定最大迭代次数M，粒子群规模G，在各客票允许的票价优化范围内随机产生初始粒子位置矩阵r(0)，置粒子的初始速度矩阵s(0)=0，迭 代次数m=0，粒 子序号g=0，O(m)=0。

Step 2 置g=g+1，将rg(0)带入式(3)计算λ；将λ与rg(0)输入式(8)，式(9)，式(11)～式(13)，调用CPLEX 得到停售时间矩阵Tg(0)和期望总收益Rg(0)；置Pg(0)=rg(0)，粒子g最优位置对应的适应度函数(0)；重复Step 2，直到g=G。

Step 4 置m=m+1，g=1，根据式(14)和式(15)更新粒子的速度sg(m)和位置rg(m)。

Step 5 判断当前粒子票价矩阵rg(m)中的各元素是否满足约束条件式(11)，若全部满足，则转至Step 6；否则，将置其适应度函数Rg(m)=0。

Step 6 将rg(m)输入式(3)更新λ；将λ与rg(m)输入式(8)，式(9)，式(11)～式(13)，调用CPLEX求解，得到适应度函数Rg(m)和停售时间矩阵Tg(m)。

Step 7 若Rg(m)，置Pg(m)=rg(m)，(m)；否则，置Pg(m)=Pg(m-1)。 若Rg(m)，置Og(m)=rg(m)，(m)；否则，置Og(m)=Og(m-1)。

Step 8 若g≤G，置g=g+1，返回Step 5。

Step 9 若m≤M，返回Step 4；否则，输出最优票价方案O(M)、期望总收益R(opt)和对应的最佳客票停售时间T*。

3 算例分析

3.1 基础数据

选择京沪高铁4趟列车的二等座进行实验，服务网络如图1[9]所示。

图1 列车服务网络Fig.1 Train service network

客票产品由列车、OD和票价等级来区分，将现状客票全价和8 折作为基准票价设置两个票价等级，并将各OD 的客票按照价格和运行时间排序，如表1所示。

表1 客票产品与票价Table 1 Ticket products and fares

在基准票价上下浮动10%的范围内优化票价。各OD旅客类别、基准票价下的平均到达率和偏好产品集合如表2所示。

表2 各OD旅客类别、平均到达率和偏好产品集合Table 2 Collection of each OD passenger category,average arrival rate and preferred products

将预售期划分为30 个时段。为计算方便，各产品间的转移概率取相同的值，即各车次座位容量为1120个。价格弹性系数η=2。

3.2 实验结果

为对比本文模型的收益效果，将票价固定仅优化售票时间窗的方案作为对比方案。前者称为联合优化方案，后者称为固定票价方案。固定票价下，售票时间窗优化模型为线性规划模型，使用CPLEX求解。取最大迭代次数M=100，粒子群规模G=30，算法收敛如图2所示。

图2 迭代优化过程Fig.2 Iterative optimization process

结果表明，联合优化方案总收益为2315554.07元，较固定票价方案提升收益约4.54%。最优售票时间窗和票价如表3所示。

表3 客票产品售票时间窗及票价Table 3 Ticket time window and price of ticket products

模型通过价格弹性将票价与购票需求联动，利用售票时间窗调节席位资源在不同客票产品间优化分配，优化后的票价有升有降。

3.3 讨论

(1)不同旅客平均到达率的情况

保持供给不变，将基准价格下的平均到达率乘以一定倍数，计算不同需求规模下的客票收益情况如图3所示。

由图3可知，联合优化方案的客票收益均优于固定票价方案，收益提升4.32%～8.49%。需求规模较小时，收益增加比例更大，应重视票价优化改善收益。当需求达到一定规模，受列车席位容量和票价上限的约束，优化票价对提升收益的贡献趋于平稳。

图3 不同到达率下的客票收益情况Fig.3 Ticket revenue under different arrival rates

需求变化时，截取OD(1,8)的客票产品观察票价和售票时间窗的变化，如图4和图5所示。

图4 不同需求下部分客票产品的票价Fig.4 Ticket prices of some ticket products under different demand

图5 不同需求下部分客票产品的售票时间窗Fig.5 Ticket time window of some ticket products under different demand

在不同需求下，客票产品票价出现一定差异。随着需求的增大，部分客票产品售票时间窗缩小。由于需求增加后提前停售部分偏好序排名靠前的低价产品，能够为排名靠后的高价产品预留更多席位资源。计算不同需求水平下的列车客座率如表4所示。

表4 客座率对比Table 4 Comparation of passenger load factors

相比固定票价方案，联合优化方案总体上提升了客座率，有利于满足更多旅客的出行需求。

(2)不同转移概率的情况

转移概率越高，客票产品被转移购买的可能性越大，增加了排序靠后的客票产品需求。保持其他数据不变，仅改变转移概率，计算联合优化方案和固定票价方案的总收益变化情况如表5和图6所示。

图6 不同转移概率下的客票收益情况Fig.6 Ticket revenue under different transfer probabilities

表5 不同转移概率下的客票收益增加情况Table 5 Increase of ticket revenue under different transfer probabilities

转移概率越大，期望客票总收益越大，且联合优化方案的期望总收益均高于固定票价方案。实际运营中应重视转移概率的估计精度。

选取OD(1,8)的客票产品观察不同转移概率下票价和时间窗的变化，如图7和图8所示。

图7 不同转移概率下部分客票产品的票价Fig.7 Ticket prices of some ticket products under different transfer probabilities

图8 不同转移概率下部分客票产品的售票时间窗Fig.8 Ticket time window of some ticket products under different transfer probabilities

随着转移概率增加，偏好序排名靠后的高价产品需求增加，票价的浮动有利于调整供需适配关系，偏好序中排名靠前的客票产品停售时间提前，为高价产品保留更多席位资源。

4 结论

(1)本文基于偏好序选择行为构建了高铁票价和售票时间窗的联合优化模型。综合考虑多趟高铁列车，通过价格调节弹性需求，采用售票时间窗调节席位资源在各OD 和各等级客票间的优化分配，寻求供给和需求的最佳匹配，实现运营企业收益最大化。根据模型特点，设计粒子群算法分层求解。外层由粒子群随机产生票价，内层已知票价后引入客票销售排序，将模型转化为等价的线性规划模型，调用CPLEX求解，通过迭代比选获得模型的满意解。

(2)与已知固定票价优化售票时间窗的方案相比，本文提出的联合优化模型能够根据弹性客流需求为每个客票产品确定最佳的票价和售票时间窗，从而提升总体客票收益。数值实验表明：不同需求水平下，联合优化方案能够提升期望总收益4.32%～8.49%。

(3)偏好序模型中的转移概率对期望总收益具有显著影响，但联合优化方案总是优于固定票价方案。转移概率越大，偏好序列表中排名靠后的高价客票产品被购买的概率越大。数值实验表明：随着转移概率增加，期望总收益增加，且期望总收益增加比例在16.09%～4.08%变化。实际应用中运营企业应重视旅客转移概率的估计精度。