高速铁路列车开行方案两阶段优化方法研究

Two-stage Optimization Method of High Speed Railway Train Operation Scheme

摘要

我国高速铁路客流时空分布复杂且有明显的时变特征，这就要求铁路运营企业能够根据客流出行的时空分布特征设计相吻合的列车开行方案，并根据客流需求变化来制定和调整列车开行方案以提供相应的运输产品。根据高速铁路客流出行需求，提出了列车开行方案两阶段优化方法，生成研究时段内备选开行列车集合，以最小化列车旅行时间和动车组车小时数为目标构建初始开行方案模型M1，然后以旅客总旅行时间最小为目标构建客流分配模型M2。针对模型M1的特点，设计基于遗传算法的启发式求解方法，模型M2运用商业软件ILOG CPLEX进行求解。通过京兰通道北京北—呼和浩特东段的实际案例分析，验证模型的正确有效性和算法的适用性。

Abstract

The time-space distribution of passenger flow of high speed railway in China is complex and has obvious time-varying characteristics, which requires railway operators to design train operation schemes according to the time-space distribution characteristics of passenger flow, and formulate and adjust train operation schemes according to the changes in passenger flow demand to provide corresponding transport products. According to the passenger travel demand of high speed railway, a two-stage optimization method of preparing the train operation scheme was proposed. By constructing a space-time network, all trains that can be operated in the study period were depicted. The outline model M1 of the operation scheme was constructed to minimize the train travel time and the number of EMU hours, and then the passenger flow distribution model M2 was constructed to minimize the total travel time of passengers. According to the characteristics of model M1, a heuristic solution method based on a genetic algorithm was designed. Model M2 was solved by commercial software ILOG CPLEX. The correctness and validity of the model and the applicability of the algorithm were verified by the actual case study of the Beijingbei-Huhehaotedong section of the Beijing-Lanzhou corridor.

Graphical abstract

关键词

高速铁路 / 列车开行方案 / 两阶段优化 / 初始开行方案模型 / 客流分配模型

Key words

High Speed Railway / Train Operation Plan / Two-stage Optimization / Model of Initial Train Operation Scheme / Passenger Flow Distribution Model

截至2021年底，我国铁路营业里程突破15万km，其中高速铁路超过4万km，2021年在疫情防控常态化背景下，全国高速铁路旅客发送量实现恢复性增长，达25.3亿人次，同比增长16.8%。旅客列车开行方案作为连接客流需求和运输计划的桥梁^[1]，一般是在确保出行需求的前提下，确定列车的起讫点、运行径路、开行频率、停站方案以及列车编组等内容。作为旅客列车时刻表的编制基础，旅客列车开行方案的优劣直接决定了企业的运输成本和服务水平，因此，研究旅客列车开行方案的优化调整问题对铁路企业降本增效、提升旅客服务体验具有重要意义。

旅客列车开行方案编制与优化一直是国内外学者重点研究的领域。早期关于列车开行方案的研究主要集中于优化列车开行径路、开行频率和停站方案等内容，史峰等^[2]提出运用双层规划模型解决列车开行方案问题，均衡考虑企业利益和旅客需求，将列车开行方案与旅客换乘方案结合起来，以客流在铁路换乘网络上的分配为下层规划，以列车开行方案优化为上层规划，建立旅客列车开行方案的双层规划模型。牛丰等^[3]研究了不确定客流条件下的高速铁路列车停站方案优化方法，以最小化开行列车总停站次数为目标，构建停站方案优化的机会约束规划模型。蒲松等^[4]分别以列车开行对数、开行区段、停站方案及编组形式为目标，建立了列车开行方案多目标优化模型，并设计改进的列生成算法进行求解。付慧伶等^[5]研究了基于备选集的高速铁路列车开行方案优化方法，在生成备选集方案的基础上，建立了列车开行方案的混合整数规划模型，在客流分配的同时得到列车开行方案，并设计朗格朗日松弛启发算法求解。

近年来，考虑客流时变需求的列车开行方案优化问题及列车开行方案与时刻表综合优化问题得到了广泛研究，史峰等基于双层规划理论，研究了基于时变需求的列车开行方案优化问题^[6-7]，苏焕银^[8]构建了时变需求下的列车开行方案Stackelberg博弈模型。Zhang等^[9]在考虑旅客期望出发时间基础上，以列车运行成本和总运行时间最小化为目标，建立了列车开行方案和列车时刻表综合优化模型。周文梁等^[10]研究了基于候选列车集与弹性需求的城际铁路列车开行方案优化问题，以列车开行收益最大为优化目标构建优化模型，达到优化列车径路、停站方案和列车始发时刻的目的。此外，周文梁等^[11]还研究了列车开行方案与运行图综合优化方法，以铁路企业效益最大化为优化目标，建立旅客列车开行方案与运行图综合优化的双层规划模型，并设计基于模拟退火的综合优化算法。

综上所述，既有研究在开行方案优化过程中多基于OD客流需求优化列车开行频率、开行对数及停站方案等，在模型建立中较少考虑列车编组因素，在方案优化中，较少考虑旅客对列车出行时段的需求，在旅客出行需求方面，较少有研究从站点需求角度出发优化列车开行方案；模型求解方面，许多既有研究虽然设计启发式求解方法，但较难在实际编制列车运行图工作中应用，在我国实际列车运行图优化过程中，目前仍主要依靠人工经验调整列车开行方案。因此，亟需研究适用于现场实际列车运行图编制的列车开行方案优化模型和算法。

基于此，研究提出高速铁路开行方案两阶段优化方法，在第一阶段，以各车站时变的进站和出站客流需求为基础，构建基于站点时变需求的非线性混合整数规划模型，第二阶段，构建客流分配线性规划模型，基于客流分配结果，进一步优化列车停站方案和起讫点。值得说明的是，与基于OD客流需求的列车开行方案相比，采用站点客流需求可以在宏观层面得到某一时段内的客流分配及开行方案，在此基础上，运用第二阶段模型，将时段内的站点客流需求分配至具体列车上，可以达到与OD客流需求同等的效果。

1　问题分析及备选列车生成

1.1　问题分析

考虑一条高速铁路线路，调整优化某一运行方向上列车开行方案。沿列车运行方向，车站集合用s表示，其中s\in S，车站依次编号为\mathrm{1}，\mathrm{2}，\mathrm{3}，\dots ,m。高速铁路线路示意如图1所示。

研究线路上，开行方案中所有备选列车用集合I=\left\{\mathrm{1}，\mathrm{2}，\mathrm{3}，\cdots ，n\right\}表示，对于所有备选开行列车，预先给定列车的始发站和终到站，对任意列车i，途经的所有车站集合为S_i，显然对于开行方案中所有列车来说，其必须在始发站和终到站停车。假设在研究时段内该高速铁路沿线各站客流需求为已知，并将客流数据换算为研究最小时段内的车站进站人数与出站人数，在此基础上，在第一阶段优化列车开行数量、停站方案和列车编组，在第二阶段基于客流分配结果优化列车开行区段，使最终优化方案在满足旅客出行需求的同时，实现运营企业收益最大。

研究提出高速铁路旅客列车开行方案两阶段优化架构，优化思路如下。

第一阶段：确定该高速铁路线路列车最小发车间隔，即该线路通过能力为最大时的发车间隔，以最小发车间隔为基础，依次生成备选开行列车；以开行列车旅行时间和动车组车小时数为目标，构建第一阶段初始列车开行方案模型，优化列车开行数量、停站方案和列车编组。

第二阶段：以旅客总旅行时间最短为目标，构建客流分配模型，基于客流分配结果，对于部分未被分配至客流的弧段，执行删除列车操作，以进一步优化列车开行起讫点和停站方案。

基于此方法得到的开行方案考虑了客流时变需求，在优化列车开行频率的同时考虑了停站方案与编组形态的优化，达到系统效用最大化；同时，给出了列车始发时刻和终到时刻初始值范围，提高了从开行方案到运行图落成的可行性，为编图工作和列车运行图优化奠定了基础。

为实现优化方案列车运行线时间分布与客流需求尽可能耦合，需要综合考虑开行列车与客流需求在上车时间和可上车人数方面的匹配。在上车时间方面，列车在任意停靠站的发车时刻要尽可能满足该站旅客的出发时段需求；在上车人数方面，列车的上车人数不能超过其最大上座率约束，同时又不能小于最小上车人数约束，这种时间和数量方面的双重约束，使得旅客需求和列车的匹配关系变得异常复杂。

在考虑高精度需求的客流分配时，往往会大幅提高建模和求解的复杂性，因此在第一阶段运用小时站点客流需求来计算初始列车开行方案，与小时OD客流需求不同，小时站点客流需求是将研究时段划分为若干小时，在每小时内，各个车站有期望出发乘客和期望到达乘客，该车站的期望出发和到达客流即为小时站点客流需求^[12-14]。在第二阶段，进一步对站点客流进行分解，通过客流分配模型，对客流进行再分配，得到列车开行和客流分配最优方案。

1.2　符号说明

以下给出了时空网络和模型涉及的集合、索引、参数、函数和变量。

集合：S为车站集合，S=\left\{\mathrm{1,2},\dots ,m\right\}；\tilde{S}为除去首末站的中间车站集合，\tilde{S}=S\backslash \left\{\mathrm{1},m\right\}；G为车站之间形成的区段集合，G=\left\{\mathrm{1,2},\dots ,m-\mathrm{1}\right\}；I为备选列车集合，I=\left\{\mathrm{1,2},\dots ,n\right\}；K为时段集合，K=\left\{\mathrm{1,2},\dots ,n^{sd}\right\}；V为网络中时空节点集合；E为时空网络弧集合；L_k^{rs}为k时段OD为（r，s）的客流路径集合。

索引：i为列车索引，i\in I；s为车站索引，s\in S；g为区段索引，g\in G；l为客流路径索引，l\in L_k^{rs}。

参数：m为车站数量，个；n为备选列车数量，列；P_i为乘坐列车i旅客数量，人；n^{\mathrm{s}\mathrm{d}}为时段数量，个；T^{\mathrm{j}\mathrm{g}}为列车最小发车间隔，min；t_{i,\mathrm{1}}^{\mathrm{d}\mathrm{e}\mathrm{p}}为列车在始发站的出发时刻；T_z^{\mathrm{q}\mathrm{d}}为区段运行时间，\forall z\in Z，min；T^{\mathrm{t}\mathrm{z}}为列车停站时长，min；t_{i,s}^{\mathrm{a}\mathrm{r}\mathrm{r}}为列车i在车站s的到达时刻；t_{i,s}^{\mathrm{d}\mathrm{e}\mathrm{p}}为列车i在车站s的出发时刻；T^{\mathrm{s}\mathrm{d}}为特定时段时长；l_{i,s}^{\mathrm{a}\mathrm{r}\mathrm{r}}为列车i在车站s的到站时段；l_{i,s}^{\mathrm{d}\mathrm{e}\mathrm{p}}为路径i在车站s的出发时段；d_{s,k}^{\mathrm{a}\mathrm{r}\mathrm{r}}为s车站在k时段特定运行方向总出站人数，\forall s\in S\backslash \left\{\mathrm{1}\right\},\forall k\in K，人；d_{s,k}^{\mathrm{d}\mathrm{e}\mathrm{p}}为s站在k时段特定运行方向总进站人数，\forall s\in \mathrm{𝒮}\backslash \left\{m\right\},\forall k\in K，人；q_{i,s}^{\mathrm{a}\mathrm{r}\mathrm{r}}为列车i到达车站s的到站客流，\forall i\in I,\forall s\in S\backslash \left\{\mathrm{1}\right\}，人；q_{i,s}^{\mathrm{d}\mathrm{e}\mathrm{p}}为列车i在车站s的出发客流，\forall i\in I,\forall s\in S\backslash \left\{m\right\}，人；C^{\mathrm{d}\mathrm{y}}为动车组标准组定员，人；\alpha为旅客时间成本参数；\omega为动车组车小时数的单位时间价值；{\lambda }_{\mathrm{1}}为旅客出行成本的权重系数；{\lambda }_{\mathrm{2}}为企业运营成本的权重系数；Y_i^{\mathrm{m}\mathrm{a}\mathrm{x}}为列车i的最大停站次数，次；c_e为旅客从弧段e出行的旅行时间，min；q_{r,s,k}^{\mathrm{o}\mathrm{d}}为k时段内OD对(r，s)之间的客流需求，人；U_e为弧段e的能力，即列车定员，人。

函数：c_i^{\mathrm{c}\mathrm{k}}为旅客出行成本函数，c_i^{\mathrm{g}\mathrm{s}}为开行列车成本函数。

辅助变量：o_{i,s,k}^{\mathrm{a}\mathrm{r}\mathrm{r}}为列车i到达车站s的时段标记，o_{i,s,k}^{\mathrm{a}\mathrm{r}\mathrm{r}}等于1表示列车i到达s车站的到站时段在研究时段k内，否则为0，\forall i\in I,\forall s\in S\backslash \left\{\mathrm{1}\right\},\forall k\in K；o_{i,s,k}^{\mathrm{d}\mathrm{e}\mathrm{p}}为列车i在车站s出发时段的标记，o_{i,s,k}^{\mathrm{d}\mathrm{e}\mathrm{p}}等于1表示列车i在车站s出发的时段在研究时段k内，否则为0，\forall i\in I,\forall s\in S\backslash \left\{m\right\},\forall k\in K；{\delta }_l^e为0-1辅助变量，等于1表示弧段e在路径l上，否则为0；z_e为实数变量，表示弧段e分配的客流量。

决策变量：x_i等于1表示列车i被使用，否则为0；y_{i,s}等于1表示列车i在s站停车，否则为0；b_i为列车i的编组辆数，辆；f_l为路径l上分配的客流量，人。

1.3　备选开行列车生成

在规划时段内，首先生成开行列车备选集合。对于每一列备选列车，以固定发车间隔生成每一备选列车的发车时刻，第一列备选列车在规划时段的起始时刻发车，其余每列车在始发站的发车时刻如公式⑴所示。

t_{i,\mathrm{1}}^{\mathrm{d}\mathrm{e}\mathrm{p}}={\displaystyle \sum _{i=\mathrm{1}}^n}{x}_i{T}^{\mathrm{j}\mathrm{g}}\forall i\in I⑴

任意备选列车i在车站s的到达时刻表示为在s-1站的出发时刻与s-1站与s站之间区段运行时间之和，到达时刻和出发时刻分别由公式⑵和⑶计算得到。

t_{i,s}^{\mathrm{a}\mathrm{r}\mathrm{r}}=t_{i,s-\mathrm{1}}^{\mathrm{d}\mathrm{e}\mathrm{p}}+T_{s-\mathrm{1}}^{\mathrm{q}\mathrm{d}}\forall i\in I,\forall s\in S\backslash \left\{\mathrm{1}\right\}⑵

t_{i,s}^{\mathrm{d}\mathrm{e}\mathrm{p}}=t_{i,s}^{\mathrm{a}\mathrm{r}\mathrm{r}}+y_{i,s}{T}^{\mathrm{t}\mathrm{z}}\forall i\in I,\forall s\in S\backslash \left\{\mathrm{1},m\right\}⑶

任意备选列车i到达车站s的到站时段的计算方法如公式⑷所示，例如，当研究时段开始时刻为6:00，备选列车i在车站s的到达时刻为7:20，则离散化后列车i在车站s的到达时刻为80；划分时段长为60 min，则此时列车i在车站s的到达时刻在第2个时段内。同理，备选列车i在车站s的离站时段计算方法如公式⑸所示。

l_{i,s}^{\mathrm{a}\mathrm{r}\mathrm{r}}=⌈\frac{t_{i,s}^{\mathrm{a}\mathrm{r}\mathrm{r}}}{T^{\mathrm{s}\mathrm{d}}}⌉\forall i\in I,\forall s\in S\backslash \left\{\mathrm{1}\right\}⑷

l_{i,s}^{\mathrm{d}\mathrm{e}\mathrm{p}}=⌈\frac{t_{i,s}^{\mathrm{d}\mathrm{e}\mathrm{p}}}{T^{\mathrm{s}\mathrm{d}}}⌉\forall i\in I,\forall s\in S\backslash \left\{m\right\}⑸

在研究的列车开行方案优化问题中，由于各列车停站方案之间的组合优化关系，使得各列车之间可能存在运行冲突的情况，在编制列车开行方案阶段出现该情况是合理的，可以在列车运行图编制过程中对列车运行冲突进行合理的消解。

2　列车开行方案两阶段优化模型

2.1　基于站点客流的初始开行方案优化模型(Model-1)

在编制列车开行方案时，可以基于站点客流信息，预先确定列车开行方案的决策要素，主要包括列车开行数量、停站方案和编组方案。构建基于站点客流的开行方案初始方案优化模型(Model-1，以下简称“M1”)如下。

2.1.1　目标函数

高速铁路列车开行方案在满足旅客出行需求的基础上，应尽可能使企业运营成本最小。分别用列车旅行时间和动车组车小时数表示企业运营成本。

列车旅行时间直接决定着列车的运行成本，是列车完成旅行任务花费的所有时间，等于列车在终到站的到达时刻减去在起始站的出发时刻^[15]。则每列车的旅行时间成本如公式⑹所示。

c_i^{\mathrm{l}\mathrm{x}}=\alpha \bullet \left(t_{i,m}^{\mathrm{a}\mathrm{r}\mathrm{r}}-t_{i,\mathrm{1}}^{\mathrm{d}\mathrm{e}\mathrm{p}}\right)\forall i\in I⑹

动车组车小时数能够表征列车编组辆数与铁路运营成本之间的关系^[6]，一般来说，高速铁路的编组辆数主要为8辆和16辆编组，动车组编组辆数与铁路运营成本之间呈正相关关系，则

c_i^{\mathrm{b}\mathrm{z}}=\omega \bullet \frac{\left(t_{i,m}^{\mathrm{a}\mathrm{r}\mathrm{r}}-t_{i,\mathrm{1}}^{\mathrm{d}\mathrm{e}\mathrm{p}}\right)\bullet b_i}{\mathrm{8}}\forall i\in I⑺

对于我国高速铁路来说，由于编组不同引起的成本变化并非2倍关系，所以引入变量{\gamma }_i为列车i的折算动车组数量^[6]。

c_i^{\mathrm{b}\mathrm{z}}=\omega \bullet \left(t_{i,m}^{\mathrm{a}\mathrm{r}\mathrm{r}}-t_{i,\mathrm{1}}^{\mathrm{d}\mathrm{e}\mathrm{p}}\right)\bullet {\gamma }_i\forall i\in I⑻

其中，当i列车的编组数量b_{i,r}=\mathrm{8}辆时，{\gamma }_i=1；当i列车的编组数量b_{i,r}=16辆时，1<{\gamma }_i<2，所以{\gamma }_i\in [\mathrm{1,2})，根据高速铁路运营实践经验，当b_{i,r}=\mathrm{16}时，{\gamma }_i=\mathrm{1.7}。

因此，目标函数为最小化旅客出行成本和企业运营成本。

\mathrm{m}\mathrm{i}\mathrm{n}{\displaystyle \sum _{i=\mathrm{0}}^n}\left({\lambda }_{\mathrm{1}}{c}_i^{\mathrm{l}\mathrm{x}}+{\lambda }_{\mathrm{2}}{c}_i^{\mathrm{b}\mathrm{z}}\right)\bullet x_i⑼

2.1.2　约束条件

（1）站点客流需求约束。基于站点需求的列车开行方案优化问题不考虑OD之间客流加载情况，只对每个车站的客流需求进行加载。除终到站外，对于任意时段的任意车站的出发客流，需要满足总客流出行需求。即车站出发客流需求约束如公式⑽所示。

{\displaystyle \sum _{i=\mathrm{1}}^n}{x}_i{o}_{i,s,k}^{\mathrm{d}\mathrm{e}\mathrm{p}}{q}_{i,s}^{\mathrm{d}\mathrm{e}\mathrm{p}}\ge d_{s,k}^{\mathrm{d}\mathrm{e}\mathrm{p}}\forall s\in S\backslash \left\{m\right\},\forall k\in K⑽

同理，车站到达客流需求约束如公式⑾所示。

{\displaystyle \sum _{i=\mathrm{1}}^n}{x}_i{o}_{i,s,k}^{\mathrm{a}\mathrm{r}\mathrm{r}}{q}_{i,s}^{\mathrm{a}\mathrm{r}\mathrm{r}}\ge d_{s,k}^{\mathrm{a}\mathrm{r}\mathrm{r}}\forall s\in S\backslash \left\{\mathrm{1}\right\},\forall k\in K⑾

（2）列车—区段能力约束。任意列车在任意区段中，其加载到列车上的客流不能超过列车定员约束。列车—区段满足能力约束如公式⑿所示。

{\displaystyle \sum _{g=\mathrm{1}}^{m-\mathrm{1}}}{q}_{i,g}^{\mathrm{d}\mathrm{e}\mathrm{p}}-{\displaystyle \sum _{g=\mathrm{2}}^{m-\mathrm{1}}}{q}_{i,g}^{\mathrm{a}\mathrm{r}\mathrm{r}}\le b_i{C}^{\mathrm{d}\mathrm{y}}\forall i\in I,\forall g\in G⑿

（3）列车—区段客流非负约束。列车在任意区段中加载的客流必须满足非负约束，如公式⒀所示。

{\displaystyle \sum _{g=\mathrm{1}}^{m-\mathrm{1}}}{q}_{i,g}^{\mathrm{d}\mathrm{e}\mathrm{p}}-{\displaystyle \sum _{g=\mathrm{2}}^{m-\mathrm{1}}}{q}_{i,g}^{\mathrm{a}\mathrm{r}\mathrm{r}}\ge \mathrm{0}\forall i\in I,\forall g\in G⒀

（4）列车总载客量守恒约束。任意列车各区段加载客流需要满足总客流守恒约束，即列车在所有停站的上车总人数与下车总人数相同，如公式⒁所示。

{\displaystyle \sum _{g=\mathrm{1}}^{m-\mathrm{1}}}{q}_{i,g}^{\mathrm{a}\mathrm{r}\mathrm{r}}-{\displaystyle \sum _{g=\mathrm{2}}^{n-\mathrm{1}}}{q}_{i,g}^{\mathrm{d}\mathrm{e}\mathrm{p}}=\mathrm{0}\forall i\in I⒁

（5）列车停站次数约束。高速铁路列车的停站次数不能超过列车的最大停站次数。

{\displaystyle \sum _{s=\mathrm{1}}^m}{y}_{i,s}\le Y_i^{\mathrm{m}\mathrm{a}\mathrm{x}}\forall i\in I⒂

（6）列车编组约束。假设研究方案列车车底为非长编复兴号动车组，沿线各车站站台均可满足重联下的列车停靠，编组形态包括单组(8辆)与重联(16辆)2种编组形态，即

b_i\in \left\{\mathrm{8}，\mathrm{16}\right\}\forall i\in I⒃

{\delta }_i\in \left[\mathrm{1,2}\right)\forall i\in I⒄

（7）0-1变量约束。

x_i\in \left\{\mathrm{0,1}\right\}\forall i\in I⒅

{\mathrm{y}}_{i,s}\in \left\{\mathrm{0,1}\right\}\forall i\in \mathrm{I},\forall s\in \tilde{\mathrm{S}}⒆

{\mathrm{o}}_{i,s,k}^{\mathrm{a}\mathrm{r}\mathrm{r}}=\left\{\begin{array}{c}\mathrm{1}\mathrm{i}\mathrm{f}k=l_{i,s}^{\mathrm{a}\mathrm{r}\mathrm{r}}\\ \mathrm{0}\mathrm{i}\mathrm{f}k\ne l_{i,s}^{\mathrm{a}\mathrm{r}\mathrm{r}}\end{array}\right.\forall i\in \mathrm{I},\forall \mathrm{s}\in \mathrm{S}\backslash \left\{\mathrm{1}\right\},\forall k\in \mathrm{K}⒇

o_{i,s,k}^{\mathrm{d}\mathrm{e}\mathrm{p}}=\left\{\begin{array}{c}\mathrm{1}\mathrm{i}\mathrm{f}k=l_{i,s}^{\mathrm{d}\mathrm{e}\mathrm{p}}\\ \mathrm{0}\mathrm{i}\mathrm{f}k\ne l_{i,s}^{\mathrm{d}\mathrm{e}\mathrm{p}}\end{array}\right.\forall i\in \mathrm{I},\forall s\in \mathrm{S}\backslash \left\{m\right\},\forall k\in \mathrm{K}

模型M1为非线性整数规划模型，可使用元启发式算法进行求解。通过求解模型M1，在宏观层面实现了列车开行方案中列车开行数量、列车停站和编组方案的确定。模型M1只从宏观层面对车站时段内的客流进行分配，为了寻找更优方案并且对列车开行起讫点进行优化，设计基于客流分配模型的开行方案再优化方法。

2.2　基于客流分配模型(Model-2)的开行方案再优化策略

第一阶段模型M1从站点客流需求出发，将小时时段内站点客流分配至该时段内的多列车上，没有细化将客流分配至具体的列车上。因此，为了进一步优化列车开行初始方案，在第二阶段首先构建客流分配模型(Model-2，以下简称“M2”)，然后基于客流分配模型的求解结果，设计启发式开行方案再优化策略。

2.2.1　客流分配模型M2

在构建客流分配模型M2时，假设给定时段内的客流必须在该时段内上车，不考虑旅客在相同列车运行径路车次间的换乘情况，旅客出行网络及出行方案图如图2所示。

图2中，q_{s\mathrm{1},s\mathrm{4},k}^{\mathrm{o}\mathrm{d}}表示k时段车站s₁到s₄的出行OD客流需求，可通过3条运行径路(灰色实线)完成运输，灰色实线表示列车运行径路，构建模型M2可实现将时段内到达的OD客流分配到不同的列车径路上完成运输。基于此出行网络，构建客流分配模型如下。

（1）目标函数。客流分配模型的目标函数为旅客总旅行时间最小，目标函数如公式 所示。

\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{Z}=\sum _{e\in E}{c}_e\bullet z_e

（2）约束条件，分为以下几种。

① 客流分配总量约束。所有客流必须全部分配至开行列车上。即

q_{r,s,k}^{\mathrm{o}\mathrm{d}}=\sum _{l\in L_k^{rs}}{f}_l\left(r,s\right)\in RS,k\in K

② 弧段分配流量约束。第一阶段模型M1中计算出的方案中有效弧上分配的客流量满足约束 。

z_e=\sum _{\left(r,s\right)\in RS}\sum _{k\in K}\sum _{l\in L_k^{rs}}{f}_l\bullet {\delta }_l^{e}e\in E

③ 弧段流量(列车定员)约束。分配到各弧段的客流需要满足弧段最大流量约束，如公式 所示。

z_e\le U_{e}e\in E

④ 客流路径约束。分配到路径l的客流须大于等于0，如公式 所示。

f_l\ge \mathrm{0}l\in L_k^{rs},\left(r,s\right)\in RS,k\in K

客流分配模型M2为线性规划模型，可以使用求解软件CPLEX求解。

2.2.2　开行方案再优化策略

通过求解模型M2，在客流分配的基础上对第一阶段初始方案进行验证并优化，进一步优化了列车的停站内容、起讫点，得到最终的列车开行方案。具体优化策略如下。

（1）停站方案再优化。检查客流分配后是否存在某些停靠站没有旅客上下车的情况，若存在，则取消列车在该站的停车办客作业。

（2）删除列车。检查客流分配后初始方案中各列车在各区段的上座率，如果存在没有被分配客流的列车，则删除该列车。

（3）拆分列车。检查客流分配后各列车在各区间的上座率，如果存在列车在某些区间的上座率为0的情况，则对列车进行拆分，停开部分区间上座率为0的列车。

通过停站方案再优化、删除列车和拆分列车操作，可实现对初始列车开行方案的进一步优化，得到更加匹配旅客出行需求的列车开行方案。

3　模型M1求解方法设计

模型M1为非线性混合整数规划模型，具有求解规模大的特点，很难在多项式时间内进行求解。元启发式算法对求解大规模组合优化问题具有较好的效果，遗传算法被多次运用于列车开行方案的求解问题^[16-17]，具有较高的求解效率，所以采用遗传算法求解模型。算法的核心思想是在满足客流需求、列车定员、列车停站和列车编组等约束的基础上，通过交叉、变异操作不断改变列车与停站方案、编组方案的匹配关系，从而寻求较好的列车开行方案。研究设计的遗传算法具体步骤如下。

（1）染色体编码。采用混合编码的方案，每条染色体由3部分组成：第一部分为是否开行列车，所含基因的数量为备选开行列车的数量，取值为0或1；第二部分为列车的编组，染色体长度为第一部分基因所含1的数量，取值为8或者16；第三部分为列车停站，染色体的长度等于第二部分染色体长度乘以车站数量决定，取值为0或1。染色体编码示意图如图3所示，第一部分中2个基因的值为1，表示第二列车被选中开行；此时，这个基因对应第二部分的列车编组和第三部分的列车停站，并且对于列车的停站方案，每列车的第一个基因位和最后一个基因位均为1。

显然，当采用上述编码方案时，染色体在遗传操作过程中始终满足列车编组约束。

（2）初始种群和染色体修复。初始种群生成过程中，首先根据研究时段总时长T、离散化列车间隔\tau、区间运行时分和停站时间，反推出列车在始发站的发车域，发车域的开始时刻为离散化时间的起始时刻，最晚发车时刻根据研究时段的总长、区间运行时分和列车停站时长进行反推，得到始发站发车时段总长为T^{\mathrm{d}\mathrm{e}\mathrm{p}}，则研究时段内最多开行列车的数量n=T^{\mathrm{d}\mathrm{e}\mathrm{p}}/\tau；对于每列车，首先随机生成第一部分的染色体，然后根据第一部分的染色体中1元素的数量，随机生成等数量第二部分染色体，为增加初始染色体的可行性，加速最优染色体获取，首先将第三部分染色体在列车停站时全部设置为1，通过设置列车在每一车站的初始停站概率，生成第三部分的染色体。

此种方法生成的染色体可能存在不满足约束的情况，所以设计启发式的染色体修复规则。实现过程为：计算并检验染色体开行列车的数量，若在第k时段，随机生成的染色体没有足够的能力满足客流需求，此时任意选出k时段染色体第一部分的1个取值为0的基因，将其改变为1，相应的，对于染色体第二部分，增加1个基因位，随机生成1个取值为8或16的基因，同理修补第三部分的基因。修补之后判断染色体的可行性，若不可行，重复上述过程，直至染色体可行。

（3）交叉操作。交叉操作首先判断所选可行染色体长度是否相同，若染色体长度相同，采用多点有效交叉，在给定交叉点数量n_{cross}的基础上，随机生成多点交叉位置，对其染色体第一部分进行交叉，同时对第二部分和第三部分的染色体也对应同步交叉。若染色体长度不同，交叉操作示意图如图4所示，则在染色体的第一部分采用多点交叉的方式，第二、第三部分采用多点交叉与基因补齐的方式完成交叉。

基于以上关键步骤，设计遗传算法流程如下。

步骤0：生成初始种群，并修复不可行初始种群。

步骤1：适应度函数。令目标函数为适应度函数，将当前染色体带入适应度函数计算适应度值。

步骤2：选择操作。采用轮盘赌和精英保留的策略进行选择。

步骤3：交叉操作。按照上述交叉操作方式进行，并在交叉操作结束后，修复不可行染色体。

步骤4：变异操作。在执行变异操作的染色体中，对染色体中第一部分按照概率选择n_{hete}个变异点进行变异操作，对染色体第二、三部分也对应执行变异操作，变异操作结束后，修复不可行染色体。

步骤5：终止条件，若迭代次数没有达到设定的最大循环次数，则转步骤2；否则算法结束，输出结果。

4　算例分析

4.1　参数输入

以京兰高速铁路(北京北—兰州西)北京北—呼和浩特东沿线各站客流需求为例，采用研究提出的方法进行仿真计算。此线路主要途经14个车站，线路运营里程459 km，根据线路结构特点，可将北京北站和清河站合并为北京北站，客流需求数据也相应合并处理。由于沙河站和旗下营南站客流极少，因此暂不考虑这2个车站，经合并处理后的线路共13个车站，车站编号依次为1—13，北京北—呼和浩特东线路示意图如图5所示。

选取研究时段为6:00—24:00，以2021年7月31日客流和运行图相关数据进行计算验证，优化前实际开行列车30列，研究时段内各站进出站客流需求如表1所示。模型中涉及其余参数取值分别为：\alpha =\mathrm{10}；\omega =\mathrm{1}；{\lambda }_{\mathrm{1}}=\mathrm{0.4}；{\lambda }_{\mathrm{2}}=\mathrm{0.6}；C^{\mathrm{d}\mathrm{y}}=\mathrm{576}；T^{\mathrm{j}\mathrm{g}}=\mathrm{5}\mathrm{m}\mathrm{i}\mathrm{n}；T^{\mathrm{s}\mathrm{d}}=\mathrm{60}\mathrm{m}\mathrm{i}\mathrm{n}；T^{\mathrm{t}\mathrm{z}}=\mathrm{2}\mathrm{m}\mathrm{i}\mathrm{n}。算法中相关参数取值分别为：种群规模取80，交叉概率取0.9，变异概率取0.1，交叉点数量n_{cross}取20，变异点数量n_{hete}取6，设置最大迭代次数为3 000。

4.2　计算结果

模型M1使用遗传算法求解，算法在Visual Studio Code 平台上使用Python语言实现；模型M2运用CPLEX求解，采用C#语言编写控制台应用程序，通过调用CPLEX动态库实现模型求解；案例测试环境为1台Intel Core i7-11700 @ 2.50 GHz CPU，16 GB RAM的个人计算机。

模型M1的适应度函数值变化情况如图6所示，算法在迭代至2 581代时得到最优解，算法收敛性较好，模型M1求解时间为38 min，模型M2求解时间为2.5 min，列车开行方案两阶段编制方法计算效率较好。

第一阶段优化后列车开行方案如图7所示，第二阶段优化后列车开行方案如图8所示，图7和图8中红色和蓝色分别代表列车编组为8辆和16辆，空心圆圈代表列车的中途停靠站。通过第一阶段优化，得到列车的开行数量为23列；通过客流分配对第一阶段得到的开行方案进一步优化，主要包括对21次、33次、43次列车的停站方案进行优化，对35次、43次列车的起讫点进行优化。与2021年7月31日实际列车开行方案相比，优化后实际开行列车23列，比优化前减少7列；优化前开行列车均为北京北(清河)—呼和浩特东间的长途列车，优化后增开了2列北京北(清河)—张家口间的短途列车。

对比两阶段优化前后每个车站经过的列车数、停站列车数，各车站列车停站情况如图9所示。图9中横坐标为各车站的站顺，左侧纵坐标为停站列车数，右侧纵坐标为经停比。相比优化前的列车停站方案，经过两阶段优化后，列车平均停站次数小于优化前，优化效果较好。比较优化前与两阶段优化后列车开行方案各项指标，优化前后指标对比如表2所示。优化后列车开行数量减少了23.3%，列车总旅行时间减少了20.96%，动车组车小时数减少了12.41%，总停站次数减少了34.88%，旅客总旅行时间减少了0.92%，平均客座率提高了13.28%。考虑旅客列车开行全成本、全收入数据测算列车开行盈亏情况得知，北京北—呼和浩特东之间客座率标准盈亏点为56.5%，优化后平均客座率达到74.92%，较优化之前平均客座率有一定提升，可以有效增加客运收入。与第一阶段优化结果相比，经过第二阶段优化，可以发现，列车总旅行时间、列车总停站时间等指标均有明显优化，说明研究设计的两阶段优化方法效果较好。

对比优化前后列车在各个时段的开行列车数量，各时段列车开行数量对比如图10所示。相比实际各时段列车开行情况，优化后各时段开行列车数量更加均衡，能够更好响应旅客出行需求。

原方案在19：00—20：00开行4列单组列车，客座率分别为47.54%，24.63%，19.23%，51.25%，优化后在19：00—20：00时段仅开行1列重联列车，同时在20：00整点附近开行北京北—张家口区段单组列车，优化方案满足了时段出行客流需求，同时提升了列车客座率，优化后重联列车客座率为85.86%，单组区段列车客座率为62.65%。同样，在9：00—11：00时间段内也有类似优化效果，原方案9：00—10：00时段从始发站开行1列单组列车，而上车客流主要集中在第4站之后，10：00—11：00时段开行3列单组列车，优化后仅在10：00—11：00时段开行1列重联列车，并且在11：00整点附近开行1列单组列车，优化后重联列车客座率达到93.56%。数据表明，该优化方法可以有效降低企业运营成本，在满足客流需求的同时提升企业运营效率。

分时段客流能力与发送能力示意如图11所示，车站时段客流需求如图11a所示，优化方案时段发送能力如图11b所示。可以发现，优化后相同车站各时段的运输能力均大于客流需求，且整体变化趋势相似，说明优化后开行方案的列车分布与出行需求的时变性吻合较好。

5　结束语

为解决响应需求的高速铁路列车开行方案优化问题，提出了旅客列车开行方案两阶段优化方法，在第一阶段考虑了旅客在车站到发的时空分布特征，以最小化列车旅行时间和动车组车小时数最小为目标，构建了决策列车开行数量、列车停站和编组的非线性混合整数规划模型，根据模型特点，设计遗传算法进行求解；在第二阶段，基于旅客出行路径，以旅客总旅行时间最小为目标，构建了客流分配线性规划模型，并运用商业软件求解。研究运用北京北—呼和浩特东间的实际案例进行验证。

实际案例结果表明：建立的模型和设计的算法具备解决大规模开行方案优化问题的能力，并且计算得到的开行列车数量、列车停站、编组、起讫点等方案很好地响应车站旅客出行需求，可为铁路企业进行列车开行方案调整优化提供决策参考。

在未来的研究中，将进一步考虑动车组资源数量限制对高速铁路开行方案优化问题的影响。

参考文献

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

[2] 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.

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

[4] 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.

[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.

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

[8] PU Song， Hongxia LYU， 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.

[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.

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

[12] 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.

[13] ZHAO S， WU R F， SHI F. A Line Planning Approach for High Speed Railway Network with Time-Varying Demand[J]. Computers & Industrial Engineering，2021，160：107547.

[14] 苏焕银，史　峰，邓连波，等. 面向时变需求的高速铁路列车开行方案优化方法[J]. 交通运输系统工程与信息，2016，16(5)：110-116，135.

[15] SU Huanyin， SHI Feng， DENG Lianbo，et al. Time-Dependent Demand Oriented Line Planning Optimization for the High Speed Railway[J]. Journal of Transportation Systems Engineering and Information Technology，2016，16(5)：110-116，135.

[16] ZHANG C T， QI J G， GAO Y，et al. Integrated Optimization of Line Planning and Train Timetabling in Railway Corridors with Passengers' Expected Departure Time Interval[J]. Computers & Industrial Engineering，2021，162：107680.

[17] 周文梁，刘晓航，姜敏，等. 基于候选列车集与弹性需求的城际铁路列车开行方案优化[J]. 铁道学报，2020，42(3)：1-10.

[18] ZHOU Wenliang， LIU Xiaohang， JIANG Min，et al. Optimization of Train Plan on Intercity Railway Based on Candidate Train Set and Elastic Demand[J]. Journal of the China Railway Society，2020，42(3)：1-10.

[19] 周文梁，史　峰，陈　彦，等. 客运专线网络列车开行方案与运行图综合优化方法[J]. 铁道学报，2011，33(2)：1-7.

[20] ZHOU Wenliang， SHI Feng， CHEN Yan，et al. Method of Integrated Optimization of Train Operation Plan and Diagram for Network of Dedicated Passenger Lines[J]. Journal of the China Railway Society，2011，33(2)：1-7.

[21] CHANG Y H， YEH C H， SHEN C C. A Multiobjective Model for Passenger Train Services Planning：Application to Taiwan’s High Speed Rail Line[J]. Transportation Research Part B：Methodological，2000，34(2)：91-106.

[22] LIN D Y， KU Y H. An Implicit Enumeration Algorithm for the Passenger Service Planning Problem：Application to the Taiwan Railways Administration Line[J]. European Journal of Operational Research，2014，238(3)：863-875.

[23] TIAN X P， NIU H M. Optimization of Demand-Oriented Train Timetables under Overtaking Operations：A Surrogate-Dual-Variable Column Generation for Eliminating Indivisibility[J]. Transportation Research Part B：Methodological，2020，142：143-173.

[24] 戚建国. 铁路列车时刻表与停站方案协同优化研究[D]. 北京：北京交通大学，2019.

[25] 易晨阳，查伟雄，李　剑. 管内零散货物快运列车开行方案研究[J]. 铁道学报，2021，43(5)：1-8.

[26] YI Chenyang， ZHA Weixiong， LI Jian. Research of the Line Plan for Regional Scattered Freight Express[J]. Journal of the China Railway Society，2021，43(5)：1-8.

[27] YANG A N， WANG B， HUANG J L，et al. Service Replanning in Urban Rail Transit Networks：Cross-Line Express Trains for Reducing the Number of Passenger Transfers and Travel Time[J]. Transportation Research Part C：Emerging Technologies，2020，115：102629.

基金资助

中国铁道科学研究院集团有限公司科研项目(2021YJ017)

中国铁道科学研究院集团有限公司科研项目(2021YJ191)