基于旅客出行选择行为的高速铁路列车开行方案优化

Optimization of Train Operation Plan for High-Speed Railway Based on Passenger Travel Choice Behavior

摘要

基于机器学习方法分析影响旅客选择行为的关键因素，从而在优化列车开行方案时有效提升方案与需求的匹配程度。首先，提出包含数据收集、预测算法设计和可解释性分析的高速铁路旅客出行选择行为分析框架，剖析影响高速铁路旅客选择行为的关键特征；其次，考虑客流需求、列车定员、变量耦合、始发终到站、通过区段列车和停站次数等约束条件，以列车开行成本最小和旅客总停站次数成本最小为目标，构建高铁列车开行方案优化模型；然后，为求解这一混合整数非线性规划模型，提出基于约束变形和大M法的非线性模型近似线性化方法；最后，以武广高铁武汉—广州南段为背景，验证模型和求解方法的有效性。结果表明：停站次数是影响旅客出行选择行为的最关键特征；优化模型目标在考虑旅客总停站次数成本最小后，武广高铁武汉—广州南方向所得开行方案的旅客总停站次数成本降幅达91.11%左右，引入大M法处理后，模型求解效率提升明显。

Abstract

The key factors affecting passenger choice behavior are analyzed based on machine learning methods, so as to effectively enhance the matching degree between the plan and demand while optimizing the train operation plan. Firstly, an analytical framework for travel choice behavior of high-speed railway passengers is proposed, which includes data collection, prediction algorithm design, and interpretability analysis, exploring the key features influencing high-speed railway passengers’ choice behavior. Secondly, considering constraints such as passenger flow demand, train capacity, variable coupling, departure and arrival stations, trains passing through sections, and number of stops, the optimization model of train operation plan for high-speed railway is constructed with the objectives of minimizing operation costs and the cost of total passenger stops. Then, in order to solve the mixed integer nonlinear programming model, an approximate linearization method for the nonlinear model is proposed, which is based on constrained deformation and the Big-M method. Finally, taking the Wuhan-Guangzhou south section of the Wuhan-Guangzhou High-Speed Railway as the research background, the effectiveness of the proposed model and solution method is verified. The results show that the number of stops is the most critical feature affecting travel choice behavior of passengers. After considering the minimum cost of total passenger stops in the optimization model goal, the cost reduction of total passenger stops in Wuhan-Guangzhou south direction of Wuhan-Guangzhou High-Speed Railway reaches about 91.11%. Moreover, the solution efficiency is significantly improved after introducing the Big-M method.

Graphical abstract

关键词

高速铁路 / 旅客出行选择行为 / 列车开行方案 / 混合整数非线性规划 / 线性化

Key words

High-speed railway / Passenger travel choice behavior / Train operation plan / Mixed integer nonlinear programming / Linearization

自我国高速铁路由“大基建”进入“大运营”时代以来，高铁运输的主要矛盾从运量与运能之间的矛盾，逐步转化为服务需求升级与运输供给不平衡不充分之间的矛盾。如何基于对旅客出行行为的分析，以旅客需求为导向设计高质量的列车开行方案就成为亟待研究的重要问题。

列车开行方案包含列车开行区段、开行数量和停站方案三要素^［1］。传统列车开行方案问题主要是在确定或不确定需求条件下，以列车开行成本最小为目标，决策列车开行方案三要素。文献［2］以包含列车开行数量和运行区段的列车开行总成本最小为目标，研究了不确定需求下旅客列车开行方案优化问题；文献［3］以最小化区段内开行列车的总停站次数为优化目标，构建了高速铁路列车停站方案设计问题的机会约束规划模型。为提升列车开行方案服务质量，文献［4-5］考虑了由列车开行数量和列车运行里程构成的运输成本，并在目标函数中引入了旅客旅行时间。近年来，越来越多的学者认为在优化列车开行方案时，需要考虑旅客选择行为，文献［6-8］基于离散选择模型研究了旅客对列车的选择行为，构建了列车开行方案双层规划模型，并设计模拟退火启发式算法求解；文献［9］将旅客对列车选择概率嵌入目标函数，构建以系统成本最小为目标的非线性混合整数规划模型，设计模拟退火算法求解。在列车开行方案优化问题的相关研究中，尽管大量文献使用离散选择模型刻画旅客对列车的选择行为，但该模型存在参数标定困难的问题，嵌入离散选择模型的数学模型大多为非线性模型，也较难求解到高质量解。

我国高铁运营实践积累的列车开行方案和客票数据可以直观反映旅客对列车的选择行为。既有的旅客出行行为分析研究多聚焦旅客对不同交通方式的选择行为，文献［10］研究了沪杭通道内旅客对公路中的巴士和小汽车以及铁路中的客运专线和既有线等交通方式的选择；文献［11］研究了京沪通道不同类型旅客对高速铁路、普速铁路、民航和长途汽车的选择行为。铁路旅客的出行选择行为分析研究或是主要聚焦旅客对高速铁路和普速铁路的选择行为，如文献［12-13］研究了旅客对G类列车和D类列车的选择行为；或是主要聚焦高铁旅客对不同价格和席位列车的选择行为，如文献［14］考虑异质性条件，研究了旅客对不同列车运行时间、票价、发车时段及车上服务水平的选择行为。既有旅客选择行为的研究主要基于调查问卷数据，使用各类离散选择模型（多项式Logit模型^［15］、Nested Logit模型^［16］和混合Logit模型^［17］等）分析旅客选择行为，调查问卷数据虽能直观反映旅客对列车选择的心理期盼，但较难验证该结果的可靠性。近年来，机器学习理论在旅客出行行为分析中得到广泛应用^［18-19］，机器学习能够从历史开行方案和客票数据中挖掘影响旅客选择行为的关键因素，并准确识别其选择行为，但相关研究较为少见。

基于机器学习方法厘清影响旅客选择行为的关键因素，可以明确列车开行方案优化问题的优化目标，避免了因经验法造成的优化目标偏差，由此得到的开行方案能更好匹配旅客选择行为，有效提升高铁客运服务质量。本文基于历史列车开行方案和客票数据，运用机器学习方法分析旅客出行选择行为；在考虑列车开行成本最小的同时也以旅客出行行为分析结果中影响旅客出行选择的关键特征旅客总停站次数成本最小为优化目标，构建得到高速铁路列车开行方案优化模型，并提出基于约束变形和大M法的近似线性化方法。

1 基于机器学习的高铁旅客出行选择行为

机器学习算法能够基于历史数据学习旅客的偏好和行为规律，可解释机器学习方法可用于判断特征重要性，揭示旅客出行选择行为与特征之间的关系。基于机器学习的高铁旅客出行选择行为分析框架如图1所示。图中：SHAP（shapley additive explanations）即预测解释框架，是一种广泛用于解释机器学习算法的方法；极端梯度提升（XGBoost）、轻量梯度提升机（LightGBM）和类别提升（CatBoost）分别是3种改进的提升树算法。首先，基于历史列车开行方案数据和客票数据，选择影响旅客出行选择行为的特征；其次，构建基于树模型的机器学习预测算法，预测不同特征影响下选择列车的旅客数量；最后，以预测性能最优的算法为基准算法，运用可解释机器学习方法，揭示影响旅客出行选择行为的关键特征。可以看出，本文所用机器学习算法主要有单决策树、集成装袋树（Bagging trees）和提升树（Boosting trees）。其中单决策树主要指决策树（DT）；集成装袋树主要包括随机森林（RF）和极限树（Exrea Tree）；提升树主要包括极端梯度提升（XGBoost）、轻量梯度提升机（LightGBM）和类别提升（CatBoost）^［20］。

SHAP模型计算得到的输入特征对预测结果的贡献即SHAP值，可以反映特征对预测结果的重要性，并有效筛选旅客出行选择的关键特征。SHAP值的计算方法为

{\varphi }_j=\sum _{A\subseteq E\setminus \left\{j\right\}}\frac{\left|A\right|!(D-\left|A\right|-\mathrm{1})!}{D!}[f(A\bigcup \{j\})-f(A)]（1）

式中：{\varphi }_j为第j个特征的贡献值，即SHAP值；|A|为特征变量子集的元素数量；\{j\}为第j个特征的集合；E\setminus \{j\}为将第j个特征从总集中删除后剩余特征变量集合；D为影响旅客选择行为特征的数量；f(S)为样本中仅含S特征集时预测算法结果。

1.1　数据和特征

选取2023年3月1日—4月27日武广高铁武汉—广州南间的数据，重点分析平峰期高铁运营特征。该时段数据避开了节假日、春运和暑运等特殊高峰期，能更稳定地反映常态运营下旅客的出行需求与出行模式，有助于研究聚焦常态运营条件下的列车开行方案优化。同时，尽管时间跨度相对较短，但因数据的平峰期代表性较强，研究结果能为类似的运营场景提供参考。

各机器学习算法输入的源数据包括日期、星期、停站次数、编组、定员、车次、出发时间、到达时间、旅行时间、动车组型号、票价和客流等。其中出发时间、到达时间和旅行时间均为时间数据，通过时间格式转化为分钟数据；动车组型号、日期和星期等信息为文本格式，通过文本编码方法转化为数值型数据^［21］。处理后的数据信息见表1，由于篇幅原因，仅列出数据格式示例。

对处理后的所有数据，运用皮尔逊相关系数（Pearson Correlation coefficient）计算特征之间的相关性，计算方法为

\rho \left(X,Y\right)=\frac{\mathrm{C}\mathrm{o}\mathrm{v}\left(X,Y\right)}{{\sigma }_X{\sigma }_Y}（2）

式中：\rho (X,Y)为特征X和特征Y的相关性系数，取值范围在［-1，1］；\mathrm{C}\mathrm{o}\mathrm{v}(X,Y)为特征X和特征Y的协方差；{\sigma }_X和{\sigma }_Y分别为特征X和特征Y的标准差。

计算得到的特征相关性及删除冗余后的特征相关性如图2所示。图中相关性系数接近1表示强正相关；接近-1表示强负相关；接近0表示几乎无线性相关；-0.00表示相关性接近于0，但具体取值为一个非常小的负数。由图2可以得到以下结论。

（1）对所有特征计算相关性系数时，出发时间与到达时间、编组与定员之间的相关系数均为1，说明2组变量之间存在完全线性相关性，属于典型的多重共线性现象；停站次数与旅行时间的相关系数为0.96，也显示出强线性相关关系；多重共线性可能导致算法估计不稳定、解释性减弱，因此有必要删除其中的信息冗余变量，保留能够代表特征含义的关键变量。

（2）进一步分析各特征与客流的相关性，发现出发时间与客流的相关系数为0.27，略高于到达时间与客流的0.23；停站次数与客流的相关性为0.61，高于旅行时间与客流的0.55；编组与客流的相关性为0.49，也高于定员与客流的0.46。在每组高度相关的变量中，都是前者对客流的解释能力略优于后者，由此，综合考虑变量间的共线性和其与目标变量客流的相关性指标，保留出发时间、停站次数和编组3个特征，删除与其高度共线且解释力较弱的到达时间、旅行时间和定员，以提升算法的稳定性和预测性能。

（3）删除冗余后，特征总数从12个下降为9个，特征之间的相关性显著降低，避免了高度相关特征对算法训练的干扰，从而使得数据结构更加合理，有利于后续特征重要性分析。

1.2　机器学习拟合结果

选取决定系数（R^{\mathrm{2}}）、平均绝对误差（MAE）和均方根误差（RMSE），作为所提高铁旅客出行行为分析框架中6种机器学习算法的评价指标。各指标计算方法见文献［22］。在算法训练过程中，采用训练集与测试集之比为8∶2的随机划分，得到各算法的预测性能见表2。

由表2可知，XGBoost在训练集中的决定系数为0.993 7，在测试集中的决定系数为0.815 0，预测精度优于其他算法，体现出较强的拟合能力和良好的泛化性能。因此，选取XGBoost作为代表算法，进一步分析其拟合性能。

XGBoost在训练集和测试集的预测值分布如图3所示。可以看出在训练集中，预测值均分布在等值线附近，拟合效果较好；在测试集中，个别预测值与真实值的偏差较大。该算法在训练集和测试中的误差如图4所示。可以看出训练集和测试集中的误差基本服从正态分布，大部分误差集中在0附近，再次证明算法的拟合性能较好。由此，选取性能最优的XGBoost，进一步计算删除冗余特征后的各特征SHAP值。

1.3　SHAP分析结果

以XGBoost作为代表算法，进一步计算删除冗余特征后的各特征SHAP值，结果如图5所示。需要说明的是，客流在算法中作为目标变量而非输入特征，因此未在特征重要性分析中展示。可以看出，停站次数、星期、动车组型号、车次和日期等特征是影响旅客出行选择的重要因素，特别是停站次数的特征重要度远大于其他特征，是最重要的特征。

综上，可认为影响旅客选择列车最关键的特征是停站次数。因此，从匹配旅客出行选择行为角度，需要将旅客总停站次数成本纳入列车开行方案优化模型的目标函数中考虑。

2 列车开行方案优化模型构建

基于高铁旅客选择行为分析结果，在目标函数中引入旅客总停站次数成本；同时，与既有列车开行方案优化问题一致，目标函数中还需要考虑列车开行成本^［4-9］。在此基础上，构建以列车开行成本最小和旅客总停站次数成本最小为目标的高速铁路列车开行方案优化模型，并综合考虑客流需求、列车能力、变量耦合、列车始发终到站、列车通过区段和列车停站次数等约束。为便于建立数学解析模型，提出以下假设。

（1）同一高速铁路线路的上下行方向旅客出行需求不对称，仅优化单一方向列车开行方案。

（2）根据线路的技术条件不同，允许开行列车数量的上限已知。

（3）旅客在线路上不进行换乘，即旅客只选择乘坐在出发站和到达站均停站的列车。

（4）列车采用固定编组的方式，即每列列车定员已知。

2.1　符号定义

对于任意高速铁路线路，S为车站集合；s,s^{\text{'}},v为车站索引，S=\left\{\mathrm{1,2},\dots ,s,\dots ,\left|S\right|\right\}，\left|S\right|为车站数量；I为备选列车集合；i为备选列车索引，I=\left\{\mathrm{1,2},\dots ,i,\dots ,\left|I\right|\right\}，\left|I\right|为备选列车数量；L为区段集合；\left|L\right|为区段数量，l为区段索引，L=\left\{\mathrm{1,2},\dots ,l,\dots ,\left|L\right|\right\}，\left|L\right|=\left|S\right|-\mathrm{1}；O和D分别为备选列车的始发站和终到站集合，O\subseteq S，D\subseteq S；o和d分别为始发站和终到站索引，O=\left\{\mathrm{1,2},\dots ,o,\dots ,\left|O\right|\right\}，D=\left\{\mathrm{1,2}\right.,\dots，\left.d,\dots ,\left|D\right|\right\}；o^k为第k个始发站对应的实际车站索引，，o^k\in S；d^k为第k个终到站对应的实际车站索引，，d^k\in S。因所建模型不涉及次方计算，上标只用于区分变量，不表示幂运算。

对于任意备选列车i\in I，c_i为备选列车i的固定开行成本；v_i为备选列车i的单位里程运行成本；E_i为备选列车i的定员；N_i为备选列车i的最大停站次数。对于任意区段l\in L，d_l为区段l的距离；N_l为必须通过区段l的最少列车数量。对于任意车站s\in S，N_s为经停车站s的所有列车的最大停站次数。对于任意车站s和车站v组成的OD，Q_{s,v}为2站间选择高速铁路出行总客流量。N_{\mathrm{Y}}为所有列车在所有车站的最大停站次数；M为一个很大的实数。

x_i为0-1决策变量，若备选列车i被选择则取值为1，否则取值为0；y_i^s为0-1决策变量，若备选列车i在车站s停车则取值为1，否则取值为0；z_i^l为0-1决策变量，若备选列车i通过区段l取值为1，否则取值为0；q_i^{s,v}为整数变量，表示在车站s和车站v间选择备选列车i的出行旅客人数。

2.2　目标函数

列车开行方案的优化目标中，既要考虑企业运营成本，又要考虑旅客总停站次数成本，二者在优化过程中难以同时兼顾。本文从企业角度考虑最小化的列车开行成本，从旅客角度考虑最小化的旅客总停站次数成本，得到对应的目标函数Z_{\mathrm{1}}和Z_{\mathrm{2}}分别如式（3）和式（4）所示。

Z_{\mathrm{1}}=\mathrm{m}\mathrm{i}\mathrm{n}\left(\sum _{i\in I}{c}_i{x}_i+\sum _{i\in I}\sum _{l\in L}{z}_i^l{d}_l{v}_i\right)（3）

式（3）中，目标函数Z_{\mathrm{1}}由开行备选列车i时可能产生的固定成本和可变成本构成。固定成本由备选列车i的选择变量与固定成本的乘积累加求和计算；可变成本由区段选择变量、单位里程成本与区段距离的乘积累加求和计算。固定成本反映列车开行数量对开行成本的影响，可变成本反映列车开行区段对开行成本的影响，二者越小，则列车开行成本越小。

（4）

式（4）中，目标函数Z_{\mathrm{2}}由列车停站变量与客流分配变量的乘积累加求和计算，表示旅客总停站次数成本。对旅客而言，旅客总停站次数成本可以在某种层面上反映列车开行方案的服务质量，该值越小，意味着旅客总停站次数越少，旅客的旅行时间也越短，符合旅客对列车选择行为的特点。

Z_{\mathrm{1}}可体现列车开行成本，Z_{\mathrm{2}}可反映旅客服务水平，采用线性加权方法将目标函数转化为单目标模型，转化后的目标函数Z为

Z=\mathrm{m}\mathrm{i}\mathrm{n}\left({\theta }_{\mathrm{1}}{Z}_{\mathrm{1}}+{\theta }_{\mathrm{2}}\delta Z_{\mathrm{2}}\right)（5）

其中，

{\theta }_{\mathrm{1}}+{\theta }_{\mathrm{2}}=\mathrm{1}

式中：\delta为旅客总停站次数成本转换系数，元 · 次^-1；{\theta }_{\mathrm{1}}和{\theta }_{\mathrm{2}}分别为权重系数。

2.3　约束条件

为刻画基于旅客出行选择行为的高速铁路列车开行方案优化问题，保证模型可行性，考虑客流需求、列车能力、变量耦合、列车始发终到、列车通过区段、列车停站次数等约束。

1）客流需求约束

任意OD间的客流需求Q_{s,v}，都应全部得到满足，即

（6）

2）列车定员约束

任意车站构成的列车运行区间断面，选择乘坐列车的旅客数量不应超过列车的定员限制，即

（7）

3）客流分配变量与停站方案变量耦合约束

由s站和v站组成的OD中，旅客只能选择乘坐在s站和v站同时停站的列车，即

（8）

（9）

4）列车开行变量与停站变量耦合约束

任意备选列车i\in I，需保证列车在开行的前提下在车站s停站，即

y_i^s\le x_i\forall i\in I,s\in S（10）

5）运行区段变量与列车开行变量耦合约束

任意备选列车i\in I，需保证列车在开行的前提下通过区段l，即

z_i^l\le x_i\forall i\in I,l\in L（11）

6）运行区段变量与停站变量耦合约束

任意区段l\in L，借助停站变量y_i^s，确保只有当备选列车i通过区段l时才有z_i^l=\mathrm{1}。运行区段变量与停站变量耦合关系示例如图6所示。在4个车站和3个区段组成的示例中，任意备选列车i在区段2中运行时，若z_i^{\mathrm{2}}=\mathrm{1}，则必须同时满足\mathrm{m}\mathrm{a}\mathrm{x}\left\{y_i^{\mathrm{1}},y_i^{\mathrm{2}}\right\}=\mathrm{1}和\mathrm{m}\mathrm{a}\mathrm{x}\left\{y_i^{\mathrm{3}},y_i^{\mathrm{4}}\right\}=\mathrm{1}，如图6（c）所示；并且此时不满足图6（a）所示的y_i^{\mathrm{1}}+y_i^{\mathrm{2}}=\mathrm{0}以及图6（b）所示的y_i^{\mathrm{3}}+y_i^{\mathrm{4}}=\mathrm{0}。

由图5示例推导到一般场景，则运行区段和停站变量耦合约束为

\begin{array}{l}\left(\sum _{s\le l,s\in S}{y}_i^s=\mathrm{0}\vee \sum _{s>l,s\in S}{y}_i^s=\mathrm{0}\right)\Rightarrow z_i^l=\mathrm{0}\\ \forall i\in I,l\in L\end{array}（12）

\begin{array}{l}\left(\underset{s\le l,s\in S}{\mathrm{m}\mathrm{a}\mathrm{x}}{y}_i^s=\mathrm{1}\wedge \underset{s>l,s\in S}{\mathrm{m}\mathrm{a}\mathrm{x}}{y}_i^s=\mathrm{1}\right)\Rightarrow z_i^l=\mathrm{0}\\ \forall i\in I,l\in L\end{array}（13）

7）列车始发终到站约束

高铁列车始发和终到车站一般在特定车站执行。引入0-1辅助变量{\alpha }_i^o和{\alpha }_i^d分别表示备选列车i在始发站o和终到站d是否停站，若停站则取值为1，否则取值为0，即

{\alpha }_i^o\ge y_i^o\forall i\in I,o\in O（14）

{\alpha }_i^d\ge y_i^d\forall i\in I,d\in D（15）

对任意备选列车i\in I，在6座车站4列列车的示例中，若始发站o^{\mathrm{1}}和o^{\mathrm{2}}之间、或终到站d^{\mathrm{1}}和d^{\mathrm{2}}之间存在车站s，则可得到始发终到约束的示例如图7所示。可以看出，若列车1在始发车站o^{\mathrm{1}}停站，则列车1在车站2既可以停站，也可以不停站；若列车2在始发站o^{\mathrm{1}}不停站，则列车2在车站2必不停站；列车3和列车4同理。

由图6示例推导到一般场景，即备选列车i在s车站的停站变量需要满足

y_i^s\le y_i^{o^k}\forall i\in I,k\in O\backslash \left\{\left|O\right|\right\}（16）

其中，

y_i^s\le y_i^{d^{k+\mathrm{1}}}\forall i\in I,k\in D\backslash \left\{\left|D\right|\right\}（17）

其中，

y_i^s\le {\alpha }_i^o\forall i\in I,s\in S（18）

y_i^s\le {\alpha }_i^d\forall i\in I,s\in S（19）

8）列车通过区段约束

为保证基本运输服务水平，任意区段的通过列车数量应满足设定的服务下限，即

\sum _{i\in I}{z}_i^l\ge N_l\forall l\in L（20）

9）列车停站次数约束

为保证沿途各站旅客乘降需求，在任意车站s\in S，所有列车在该车站的总停站次数需满足最低服务要求，即不少于规定的最低停站次数。即

\sum _{i\in I}{y}_i^s\ge N_s\forall s\in S（21）

列车停站次数直接决定企业运营成本，对单趟列车，停站次数越多，旅客的旅行时间越长、服务质量越低；对所有列车，总停站次数越多，企业运营成本越大。因此，单趟车停站次数与所有列车总停站次数约束分别为

\sum _{s\in S}{y}_i^s\le N_i\forall i\in I（22）

\sum _{i\in I}\sum _{s\in S}{y}_i^s\le N_{\mathrm{Y}}（23）

2.4　模型复杂度分析

列车开行方案模型为多目标非线性混合整数规划模型，模型中变量、目标函数和约束条件的类型和规模见表3。模型存在2个求解难点：①式（13）和式（14）为非线性约束；②目标函数式（4）中存在二次非线性项。

结合表3可知：对于模型变量而言，总数量达到\left|I\right|+\left|I\right|\times \left|S\right|+\left|I\right|\times (\left|S\right|-\mathrm{1})+\left|I\right|\times \left|S\right|\times (\left|S\right|-\mathrm{1})，决定数量的主导项为\left|I\right|\times \left|S\right|\times (\left|S\right|-\mathrm{1})，变量复杂度约为O(\left|I\right|\times {\left|S\right|}^{\mathrm{2}})；同理，目标函数和约束条件复杂度均为O(\left|I\right|\times {\left|S\right|}^{\mathrm{2}})；模型的时间复杂度为O(\left|I\right|\times {\left|S\right|}^{\mathrm{2}})，空间复杂度主要取决于存储所有变量和约束所需的内存空间，q_i^{s,v}是规模最大的决策变量，因此，模型空间复杂度为O(\left|I\right|\times {\left|S\right|}^{\mathrm{2}})。针对模型中的非线性式求解难点，采用多种线性化技术线性处理后，使用求解器求解模型。

3 求解方法

通过等价转换和引入新变量等方法将式（12）和式（13）转化为线性约束，基于大M法等价线性转换将目标函数转化为线性式，采用线性加权方法将多目标优化问题转化为单目标问题，便可使用Gurobi求解处理后的模型。

3.1　约束条件线性化处理

运行区段变量与停站变量耦合约束为非线性约束，难以直接求解。其中式（12）可通过列车运行区段变量和列车停站变量表示为

z_i^l\le \sum _{s\le l,s\in S}{y}_i^s\forall i\in I,l\in L（24）

z_i^l\le \sum _{s>l,s\in S}{y}_i^s\forall i\in I,l\in L（25）

式（24）和式（25）是对式（12）的约束加紧，当s\le l和s>l时，若y_i^s=\mathrm{0}，则必有z_i^l=\mathrm{0}；引入的线性化约束更加严格限制了变量的范围，若y_i^s=\mathrm{1}，则z_i^l=\mathrm{1}或z_i^l=\mathrm{0}。

为将式（13）线性化，引入0-1辅助变量{\beta }_i^l和{\gamma }_i^l，{\beta }_i^l和{\gamma }_i^l分别表示当和s>l时y_i^s的最大值。式（13）可转化为

z_i^l\ge {\beta }_i^l+{\gamma }_i^l-\mathrm{1}\forall i\in I,l\in L（26）

（27）

（28）

由式（26）—式（28）可知，当且仅当{\beta }_i^l和{\gamma }_i^l同时等于1时，z_i^l=\mathrm{1}成立；此时，若同时满足1<s≤l和，s站停站变量的最大值需等于1。

记式（12）和式（13）线性化处理后的模型为模型M0，即目标函数为式（5），约束条件为式（6）—式（11）、式（14）—式（23）、式（24）—式（28）。

3.2　目标函数处理

使用大M法对目标函数线性化。定义辅助变量w_i^{s^{\text{'}},v}=y_i^{s^{\text{'}}}{q}_i^{s,v}，已知\mathrm{0}\le y_i^{s^{\text{'}}}\le \mathrm{1}，\mathrm{0}\le q_i^{s,v}\le E_i，从而有

（29）

w_i^{s^{\text{'}},v}\le M{y}_i^{s^{\text{'}}}\forall i\in I,s^{\text{'}}\in S（30）

（31）

（32）

w_i^{s^{\text{'}},v}\ge \mathrm{0}\forall i\in I,s^{\text{'}}\in S（33）

对目标函数Z_{\mathrm{2}}进行线性化处理后，式（30）和式（32）中大M的取值为决策变量q_i^{s,v}的上界，对于客流分配变量而言，其上界等于列车的最大定员，即M=E_i。

将目标函数线性化后的新模型记为模型M1，其目标函数和约束条件分别为：目标函数为式（3）和式（29），约束条件为式（6）—式（11），式（14）—式（28），式（30）—式（33）。线性化处理后的模型M1等价于原模型M0，等价性证明如下。

对于0-1决策变量y_i^{s^{\text{'}}}，当y_i^{s^{\text{'}}}=\mathrm{0}时，由式（30）可知w_i^{s^{\text{'}},v}\le \mathrm{0}，结合非负约束式（33），可得w_i^{s^{\text{'}},v}=\mathrm{0}，即此时线性化约束成立，满足目标关系；当y_i^{s^{\text{'}}}=\mathrm{1}时，由式（30）可知w_i^{s^{\text{'}},v}\le M，由式（31）可知w_i^{s^{\text{'}},v}\le q_i^{s,v}，由式（32）可知w_i^{s^{\text{'}},v}\ge q_i^{s,v}，即此时w_i^{s^{\text{'}},v}=y_i^{s^{\text{'}}}{q}_i^{s,v}=q_i^{s,v}，线性化约束成立，满足目标关系。综上，可认为对于y_i^{s^{\text{'}}},始终存在w_i^{s^{\text{'}},v}严格满足w_i^{s^{\text{'}},v}=y_i^{s^{\text{'}}}{q}_i^{s,v}，即线性化处理后新增约束等价于原二次乘积项，证明完毕。

4 案例分析

4.1　基础数据

1）线路数据

沿武广高铁武汉—广州南方向共16座车站，车站编号、站间距离、最少通过列车数和区间起始站的最少停站数量见表4^［2］。

2）需求数据

研究时段内各OD的旅客出行需求如图8所示。可以发现其中客流需求较大的OD有：武汉—长沙南、长沙南—广州南和长沙南—衡阳东等。

3）备选列车及其他参数

给定研究时段为6：00—24：00，在既有OD旅客出行需求条件下，分析历史列车开行方案。结合实际开行列车数量，假定备选开行列车数量为35列、列车最大能力为576人 · 列^-1时能够满足旅客出行需求；根据历史运营经验，取列车总停站次数最大为380；参考文献［2］，取列车固定运营成本为10万元，可变成本为0.01万元 · km^-1；取\delta为2元 · 次^-1，{\theta }_{\mathrm{1}}和{\theta }_{\mathrm{2}}均为0.5。

算例采用Python调用Gurobi求解，终止条件为：上下界间隙（Gap）小于0.1%或求解时间大于3 600 s。

4.2　优化结果

1）基本结果

基于Gurobi求解处理后的模型，得到优化后目标函数值为2 995 449元，其中列车开行成本为5 940 900元，旅客总停站次数成本为49 998元。优化后列车开行方案如图9所示。

由图9可知：优化后的旅客列车开行数量共计31列，其中武汉—广州南23列，武汉—郴州西7列，长沙南—广州南1列；列车总停站260次，武汉—广州南列车的最大停站次数为8次，武汉—郴州西的最大停站次数为7次；优化后列车开行方案满足各项约束，验证了模型正确性。

2）不同目标函数优化结果

通过权重系数{\theta }_{\mathrm{1}}和{\theta }_{\mathrm{2}}调节企业列车开行成本与旅客总停站次数成本权重，并对比单一目标与双目标规划的优化效果见表5。由表5可以发现：3组参数取值下的结果在目标函数值、列车开行成本和旅客总停站次数成本之间存在明显差异；当{\theta }_{\mathrm{1}}=\mathrm{0}，{\theta }_{\mathrm{2}}=\mathrm{1.0}时，目标函数为旅客总停站次数成本最小，该值仅为49 998元，但列车开行成本为6 557 000元，为3组方案中最高，但由于客流分配耦合作用的存在，此时列车总停站次数并不是最低的，为265次；当{\theta }_{\mathrm{1}}=\mathrm{0.5}，{\theta }_{\mathrm{2}}=\mathrm{0.5}时，列车开行成本与旅客总停站次数成本权重相同，此时列车开行成本为5 940 900元，较上一方案降低了约10.4%，旅客总停站次数成本维持在49 998元，列车总停站次数最小；当{\theta }_{\mathrm{1}}=\mathrm{1},{\theta }_{\mathrm{2}}=\mathrm{0}时，目标函数为列车开行成本最小，此时列车开行成本为5 940 900元，为3组方案中的最优值，但旅客总停站次数成本大幅增加到562 320元，列车总停站次数为262次。综上，考虑旅客出行选择行为后，旅客总停站次数成本明显降低。

列车在各站的停站次数和经停比如图10所示。

由图10可以发现，当目标函数考虑旅客总停站次数成本后，大部分中间各站的列车经停比低于不考虑旅客总停站成本时的情况，即对旅客而言，得到的列车开行方案能够更好地匹配旅客的出行选择行为。

3）大M法处理目标函数求解性能

调用Gurobi求解模型M1，运行6.39 s后求解得Gap为0.00%的解；用Gurobi直接求解模型M0，运行3 600 s后仅求解得Gap为9.48%的解。这说明经过大M法处理后，可以在较短时间内求得原问题的解，求解性能较好。

为验证大M法在不同规模案例中的有效性，在算例其他参数不变条件下，构造不同车站数量和列车数量的9组算例，不同求解方法计算结果见表6。由表6可知：当车站达到20座时，大M法可以在较快时间内得到近似最优解，但Gurobi在3 600 s内较难得到较好的可行解；大M法对带有二次项的大规模混合整数规划模型具有较好的求解效率。

5 结语

本文运用机器学习树算法和SHAP方法研究旅客选择行为，得到停站次数是影响旅客选择列车的最重要特征；再以列车开行成本和旅客总停站次数成本最小为目标，构建高速铁路列车开行方案优化模型；该模型属于多目标规划非线性模型，为便于求解，基于等价转换方法线性化处理非线性约束条件，并使用大M法将目标函数线性化。武广高铁武汉—广州南方向的实例表明，基于所建高速列车开行方案优化模型，得到旅客列车共开行31列，列车总停站260次，旅客总停站次数成本为49 998元，能优化使旅客总停站次数成本最小的列车开行方案。考虑客总停站次数成本最小后，得到的开行方案使成本显著降低，较不考虑该成本的开行方案下降约91.11%。不同规模的案例求解结果表明，使用大M法对目标函数二次项线性化能够有效提升模型求解效率。该优化方法既能为旅客提供高质量的列车开行方案，满足旅客出行需求，又能降低企业运营成本；可为高速铁路运营企业开行方案设计提供技术支撑，具有较大的现实意义。

在未来的研究中，可考虑收集更长时间尺度下的客票和列车开行方案数据，研究旅客出行选择行为；或进一步考虑节假日和春运等客流饱和条件下列车开行方案优化问题，研究考虑路网条件下列车开行方案优化问题。

参考文献

[1] 倪少权.铁路旅客运输组织［M］.北京：科学出版社，2020.

[2] NI Shaoquan. Organization of Rail Passenger Transport ［M］. Beijing： Science Press， 2020. in Chinese

[3] 张春田，戚建国，杨立兴，等.基于不确定旅客需求的高速铁路鲁棒列车开行方案研究［J］.交通运输系统工程与信息，2022，22（1）：115-123.

[4] ZHANG Chuntian， QI Jianguo， YANG Lixing， et al. Robust Train Operation Plan Based on Uncertain Passenger Demands for High-Speed Railway Corridors ［J］. Journal of Transportation Systems Engineering and Information Technology， 2022， 22 （1）： 115-123. in Chinese

[5] 牛丰，戚建国，秦进.基于不确定客流的高速铁路列车停站方案优化方法［J］.铁道学报，2016，38（7）：1-7.

[6] NIU Feng， QI Jianguo， QIN Jin. Optimization Model for Train Stopping Plan on High-Speed Railway Corridor with Uncertain Passenger Demands ［J］. Journal of the China Railway Society， 2016， 38 （7）： 1-7. in Chinese

[7] 蒲松，吕红霞，陈钉均，等.基于改进列生成算法的高速列车开行方案优化研究［J］.铁道学报，2015，37（9）：1-7.

[8] PU Song， Hongxia LÜ， CHEN Dingjun， et al. High Speed Railway Passenger Train Line Planning Optimization Based on Improved Column Generation Algorithm ［J］. Journal of the China Railway Society， 2015， 37 （9）： 1-7. in Chinese

[9] 付慧伶，聂磊，杨浩，等.基于备选集的高速铁路列车开行方案优化方法研究［J］.铁道学报，2010，32（6）：1-8.

[10] FU Huiling， NIE Lei， YANG Hao， et al. Research on the Method for Optimization of Candiate-Train-Set Based Train Operation Plans for High-Speed Railways ［J］. Journal of the China Railway Society， 2010， 32 （6）： 1-8. in Chinese

[11] 秦进，谭宇超，张威，等.基于时空网络的城际高速铁路列车开行方案优化方法［J］.铁道学报，2020，42（2）：1-10.

[12] QIN Jin， TAN Yuchao， ZHANG Wei， et al. Train Planning Optimization for Intercity Railway Based on Space-Time Network ［J］. Journal of the China Railway Society， 2020， 42 （2）： 1-10. in Chinese

[13] 史峰，邓连波，霍亮.旅客列车开行方案的双层规划模型和算法［J］.中国铁道科学，2007，28（3）：110-116.

[14] SHI Feng， DENG Lianbo， HUO Liang. Bi-Level Programming Model and Algorithm of Passenger Train Operation Plan ［J］. China Railway Science， 2007， 28 （3）： 110-116. in Chinese

[15] 史峰，李彦霖，胡心磊，等.面向服务水平的高速铁路列车开行方案优化［J］.中国铁道科学，2018，39（5）：127-136.

[16] SHI Feng， LI Yanlin， HU Xinlei， et al. Service Level Oriented Optimization of Train Operation Plan for High Speed Railway ［J］. China Railway Science， 2018， 39 （5）： 127-136. in Chinese

[17] 孙国锋，景云，马亚雯.考虑旅客多维出行需求的动态列车开行方案优化［J］.铁道学报，2022，44（11）：10-18.

[18] SUN Guofeng， JING Yun， MA Yawen. Optimization of Dynamic Train Line Planning Considering Multi-Dimensional Travel Demand of Passengers ［J］. Journal of the China Railway Society， 2022， 44 （11）： 10-18. in Chinese

[19] 叶玉玲，王艺诗.沪杭运输通道内旅客出行方式选择行为研究［J］.铁道学报，2010，32（4）：13-17.

[20] YE Yuling， WANG Yishi. Research on Travel Mode Choice Behavior in Shanghai-Hangzhou Transport Corridor ［J］. Journal of the China Railway Society， 2010， 32 （4）： 13-17. in Chinese

[21] 张迦南，赵鹏.综合运输通道旅客出行方式选择行为研究［J］.中国铁道科学，2012，33（3）：123-131.

[22] ZHANG Jia'nan， ZHAO Peng. Research on Passenger Choice Behavior of Trip Mode in Comprehensive Transportation Corridor ［J］. China Railway Science， 2012， 33 （3）： 123-131. in Chinese

[23] JING Y， LIU Y K， ZHANG Z H， et al. Passenger Travel Behaviour on Chinese High‐Speed Railways Using Machine Learning Based on Revealed-Preference Data ［J］. Expert Systems， 2019， 36 （4）： e12422.

[24] 王文宪，倪少权，吕红霞，等.基于非集计理论的高速铁路旅客乘车选择行为研究［J］.交通运输系统工程与信息，2015，15（3）：13-18，43.

[25] WANG Wenxian， NI Shaoquan， Hongxia LÜ， et al. Boarding Choice for High-Speed Railway Passengers Based on Disaggregate Theory ［J］. Journal of Transportation Systems Engineering and Information Technology， 2015， 15 （3）： 13-18， 43. in Chinese

[26] 赵鹏，翟茹雪，宋文波.考虑个体异质性的高速铁路旅客选择行为［J］.北京交通大学学报，2019，43（2）：117-123.

[27] ZHAO Peng， ZHAI Ruxue， SONG Wenbo. Passenger Choice Behavior of High-Speed Railway Considering Individual Heterogeneity ［J］. Journal of Beijing Jiaotong University， 2019， 43 （2）： 117-123. in Chinese

[28] LEE D， DERRIBLE S， PEREIRA F C. Comparison of Four Types of Artificial Neural Network and a Multinomial Logit Model for Travel Mode Choice Modeling ［J］. Transportation Research Record： Journal of the Transportation Research Board， 2018， 2672 （49）： 101-112.

[29] ZHU Z J， ZENG J， GONG X L， et al. Analyzing Influencing Factors of Transfer Passenger Flow of Urban Rail Transit： a New Approach Based on Nested Logit Model Considering Transfer Choices ［J］. International Journal of Environmental Research and Public Health， 2021， 18 （16）： 8462.

[30] LI H Y， LI X， XU X Y， et al. Modeling Departure Time Choice of Metro Passengers with a Smart Corrected Mixed Logit Model - a Case Study in Beijing ［J］. Transport Policy， 2018， 69： 106-121.

[31] SALAS P， DE LA FUENTE R， ASTROZA S， et al. A Systematic Comparative Evaluation of Machine Learning Classifiers and Discrete Choice Models for Travel Mode Choice in the Presence of Response Heterogeneity ［J］. Expert Systems with Applications， 2022， 193： 116253.

[32] CHANG X M， WU J J， LIU H， et al. Travel Mode Choice： a Data Fusion Model Using Machine Learning Methods and Evidence from Travel Diary Survey Data ［J］. Transportmetrica A： Transport Science， 2019， 15 （2）： 1587-1612.

[33] HU S H， XIONG C F， CHEN P， et al. Examining Nonlinearity in Population Inflow Estimation Using Big Data： an Empirical Comparison of Explainable Machine Learning Models ［J］. Transportation Research Part A： Policy and Practice， 2023， 174： 103743.

[34] 孙国锋，景云，李和壁，等.基于可解释机器学习框架的列车乘车区段客流分布预测方法［J］.交通运输系统工程与信息，2024，24（2）：249-262.

[35] SUN Guofeng， JING Yun， LI Hebi， et al. An Interpretable Machine Learning Framework-Based Approach for Predicting Passenger Flow Distribution in Train Riding Sections ［J］. Journal of Transportation Systems Engineering and Information Technology， 2024， 24 （2）： 249-262. in Chinese

[36] SHI R， XU X Y， LI J M， et al. Prediction and Analysis of Train Arrival Delay Based on XGBoost and Bayesian Optimization ［J］. Applied Soft Computing， 2021， 109： 107538.

基金资助

国家自然科学基金资助项目(52372300)

中央引导地方科技发展资金资助项目(25ZYJA015)