协同能力目标和停站需求的高速铁路列车基本运行图优化

摘要

考虑高速铁路站、车一定的服务频次要求，提出列车运行图生成与压缩的协同优化的混合整数规划模型。模型以铺画一定数量列车运行线占用列车运行图横轴的时间长度和所有列车全程旅行时间最小为优化目标，提出二阶段求解算法：先固定标杆列车运行线，求解列车停站方案、越行方案、股道运用方案，即生成列车运行图；在不改变上述3个方案下，减少列车运行图中的非必要的冗余时间，并向前移动列车运行线，即压缩列车运行图。以京沪高速铁路为案例，结果表明，二阶段法可降低两列车之间运行关系判定的复杂度，实现对模型大规模数据的快速有效求解。

关键词

高速铁路; 站车服务频次; 列车运行图生成与压缩; 二阶段

我国高速铁路繁忙干线客流量逐年增长，线路通过能力紧张和供需不平衡的矛盾并存，导致运输能力不能得到有效发挥，造成这种问题的原因是列车运行图的不均衡，不规律。将车站经停需求和列车停站需求纳入列车运行图优化，有利于强化服务导向的线路通过能力，使得优化得到的列车运行图能够适应实际需求。

既有对繁忙高铁干线列车运行图的研究主要聚焦于停站方案、列车运行图生成与压缩的研究。高速铁路列车停站方案编制^［1-4］主要着眼于面向客流需求的能力结构化布局，但较少结合线路条件。曲思源等^［1］研究了通道型高速铁路列车运行图结构并提出停站方案优化建议。Chen等^［2］以停站成本最小和旅客便利性最大为目标函数，构建停站方案多目标优化模型。李得伟等^［3］构建带有叉乘约束的非线性规划模型，并提出随机优化算法研究停站方案。邵长虹等^［4］以通过能力最大化为目标构建周期化停站方案优化模型。对于列车运行图生成的研究，廖正文等^［5］、Meng等^［6］设计拉格朗日松弛求解算法求解运行图模型，但未求解具体的列车时刻表。Tian等^［7］建立基于时空弧变量的线性整数规划模型。田小鹏等^［8］构建双目标整数规划模型。赵子洪^［9］设计基于遗传原理的综合优化算法对模型进行求解。张春田等^［10］构建停站方案与时刻表两阶段随机规划模型。Zhang等^［11］提出了周期化列车开行结构，构建停站方案与列车运行图协同编制模型。Wang等^［12］构建整数规划模型，运用改进分支定界法求解。Jiang等^［13］构建停站方案和列车运行图协同优化模型。Niu等^［14］在给定列车停站方案下，构建二次整数规划模型。文献［7-13］均未同时考虑列车越行，不同速度列车混跑，站、车服务水平等多个条件。对于列车运行图压缩的研究，单杏花^［15］提出了列车运行图的压缩方法。马寓^［16］基于UIC406方法，提出了压缩时刻表的通过能力计算模型。王高磊等^［17-18］提出了列车运行图冗余时间的压缩方法，加密列车运行线的方法及通过能力计算公式。文献［15-18］较少考虑列车行车次序和停站时间调整。

本文拟从线路能力利用的角度出发，提出考虑站、车服务质量的列车运行图生成与压缩一体化的快速和较精确求解方法，可以较好地解决能力利用与服务水平协调的问题。本文提出的方法适应于非线性模型的大规模求解需要，可在较短时间内生成具体的列车时刻表，为列车运行图编制提供辅助决策，减轻既有人工编图的负担。

1 问题描述

选取一条高速铁路为研究对象，如图1所示，全线车站分为枢纽站和中间站两种类型，把全线按枢纽站分为若干个区段。为了体现差异化的服务，线路上开行两种类型的列车，标杆列车和普通列车。标杆列车等级高、速度快，构成列车运行图的基本骨架，以服务节点大站为主，只停靠枢纽站。普通列车是列车运行图的主要组成部分，具有多样性，以服务沿途客流为主，除了停靠枢纽站外，还停靠中间站，停靠方式为交错停，每列车规定一定范围的停站数量要求，不规定具体的中间站停站。标杆列车可以越行普通列车。为了保证普通列车停站的均衡性，避免列车在某些地段集中停靠，每列车在每个区段的停站数量也应满足相关要求。同时，每个车站的列车停靠数量也需要满足一定的范围水平，考虑各个车站的站场、客流等因素，不同车站的列车停靠数量有所差异。

图1  研究对象示意图

Fig. 1  Diagram of research object

2 列车运行图优化模型

2.1　参数

$S$代表车站集合，$S=\{\mathrm{1,2},\dots ,S\}$。

$s$代表车站索引序列，$s\in S$，也代表区间索引序列，如区间$s$，代表了车站$s$与车站$s+\mathrm{1}$之间的区间。

$U$代表区段集合，$U=\{\mathrm{1,2},\dots ,U\}$。

$u$代表区段索引序列，$u\in U$。

S_u代表区段u内的车站集合，S_u⊆ S。

$W_s$代表车站$s$的旅客乘降功能，$W_s=\{\mathrm{0,1}\}$，1代表旅客可以乘降，0代表旅客不可以乘降。

$v$代表列车类型，$v=\{\mathrm{0,1}\}$，1代表标杆列车，0代表普通列车。

$D/A$代表开始/结束时刻。

$e_{s,v}$代表列车类型为$v$的列车在区间$s$的纯运行时间。

$f_s$代表列车在区间$s$的最大运行冗余时间。

$x_{s,v}/y_{s,v}$代表列车类型为$v$的列车在车站$s$的起车/停车附加时间。

$t_{s,v}^{\mathrm{m}\mathrm{i}\mathrm{n}}/t_{s,v}^{\mathrm{m}\mathrm{a}\mathrm{x}}$代表列车类型为$v$的列车在车站$s$的最小/最大停站时间。

$t_{\mathrm{d}\mathrm{d},s}/t_{\mathrm{a}\mathrm{a},s}$代表车站$s$的列车出发/到达追踪最小间隔时间。

$t_{\mathrm{a}\mathrm{p},s}/t_{\mathrm{p}\mathrm{d},s}$代表车站$s$的到通/通发最小间隔时间。

$t_{\mathrm{d}\mathrm{a},s}$代表车站$s$的同一股道发到最小间隔时间。

$n_s^{\mathrm{m}\mathrm{i}\mathrm{n}}/n_s^{\mathrm{m}\mathrm{a}\mathrm{x}}$代表车站$s$停靠列车最低/最高数量。

$L$代表列车集合，$L=\{\mathrm{1,2},\dots ,L\}$。对于列车集合$L$，令集合中的$\{\mathrm{1,2},\dots ,Q\}$为标杆列车，集合中的$\{Q,Q+\mathrm{1},\dots ,L\}$为普通列车，分别按在始发站的发车顺序排序。

$l_v$代表列车索引序列和性质，$l_v\in L$，$l_{\mathrm{0}}$为普通列车，$l_{\mathrm{1}}$为标杆列车。

$n_v^{\mathrm{m}\mathrm{i}\mathrm{n}}/n_v^{\mathrm{m}\mathrm{a}\mathrm{x}}$代表列车类型$v$的列车全程停靠车站的最低/最高数量。

$n_{v,u}^{\mathrm{m}\mathrm{i}\mathrm{n}}/n_{v,u}^{\mathrm{m}\mathrm{a}\mathrm{x}}$代表列车类型$v$的列车在区段$u$停靠车站的最低/最高数量。

$R_s$代表车站$s$的某一方向股道集合，$R_s=\{{\mathrm{1}}_s,{\mathrm{2}}_s,\dots ,R_s\}$。其中，${\mathrm{1}}_s$为正线，供通过列车使用，${\mathrm{2}}_s~R_s$为到发线，供停靠列车使用。

$M$为数值很大的一个正整数。

2.2　决策变量

整数变量$d_{s,l_v}$代表列车$l_v$在车站$s$的出发时刻或通过时刻。

整数变量$a_{s,l_v}$代表列车$l_v$在车站$s$的到达时刻或通过时刻。

0‒1变量${\rho }_{s,l_v}$代表列车$l_v$在车站$s$的停靠性质，${\rho }_{s,l_v}$=｛0，1｝，1代表停靠，0代表通过。

0‒1变量${\alpha }_{s,l_{v\mathrm{1}},l_{v\mathrm{2}}}$代表列车$l_{v\mathrm{1}}$和列车$l_{v\mathrm{2}}$在车站$s$的先后出发（通过）顺序，若$l_{v\mathrm{1}}$先发（通过），$l_{v\mathrm{2}}$后发（通过），则${\alpha }_{s,l_{v\mathrm{1}},l_{v\mathrm{2}}}=\mathrm{1}$，否则${\alpha }_{s,l_{v\mathrm{1}},l_{v\mathrm{2}}}=\mathrm{0}$。

0‒1变量${\beta }_{s,l_{v\mathrm{1}},l_{v\mathrm{2}}}$代表列车$l_{v\mathrm{1}}$和列车$l_{v\mathrm{2}}$在车站$s$的先后到达（通过）顺序，若$l_{v\mathrm{1}}$先到（通过），$l_{v\mathrm{2}}$后到（通过），则${\beta }_{s,l_{v\mathrm{1}},l_{v\mathrm{2}}}=\mathrm{1}$，否则${\beta }_{s,l_{v\mathrm{1}},l_{v\mathrm{2}}}=\mathrm{0}$。

0‒1变量${\theta }_{l_{v,}{r}_s}$代表列车$l_v$在车站s是否被分配到股道$r_s$上，若是则${\theta }_{l_{v,}{r}_s}=$1，若否则${\theta }_{l_{v,}{r}_s}=$0。

2.3　目标函数

目标函数$F_{\mathrm{1}}$：首要优化目标，以铺画一定数量列车运行线占用列车运行图横轴的时间长度最小为优化目标，表现为列车运行图所有列车中最后到达终到站$S$的列车的到达时刻最早。本优化目标确定了列车运行图的停站方案和越行方案，生成了列车运行图。

$$F_{\mathrm{1}}=\mathrm{m}\mathrm{i}\mathrm{n}\left(\mathrm{m}\mathrm{a}\mathrm{x}\left(a_{S,\mathrm{1}},\dots ,a_{S,l_v},\dots ,a_{S,L}\right)\right)$$

（1）

目标函数$F_{\mathrm{2}}$：次要优化目标，以列车运行图所有列车全程旅行时间之和最小为优化目标。本优化目标在停站方案和越行方案不变的基础上，结合目标函数$F_{\mathrm{1}}$，即$F_{\mathrm{1}}+F_{\mathrm{2}}$，可减少列车非必要的区间运行冗余时间和在中间站的冗余停站时间，实现对列车运行图的压缩。

$$F_{\mathrm{2}}=\mathrm{m}\mathrm{i}\mathrm{n}(\sum _{l_v\in L}(a_{S,l_v}-d_{\mathrm{1},l_v}))$$

（2）

2.4　约束条件

2.4.1　列车运行时间约束

（1）区间运行时间约束

$$a_{s+\mathrm{1},l_v}-d_{s,l_v}\le x_{s,v}{\rho }_{s,l_v}+e_{s,v}+y_{s+\mathrm{1},v}{\rho }_{s+\mathrm{1},l_v}+f_s,\forall l_v\in L,s\in \{\mathrm{1},\dots ,S-\mathrm{1}\}$$

（3）

$$a_{s+\mathrm{1},l_v}-d_{s,l_v}\ge x_{s,v}{\rho }_{s,l_v}+e_{s,v}+y_{s+\mathrm{1},v}{\rho }_{s+\mathrm{1},l_v},\forall l_v\in L,s\in \{\mathrm{1},\dots ,S-\mathrm{1}\}$$

（4）

（2）停站时间约束

$$d_{s,l_v}-a_{s,l_v}\ge t_{s,v}^{\mathrm{m}\mathrm{i}\mathrm{n}}{\rho }_{s,l_v},\forall l_v\in L,s\in \left\{\mathrm{2},\dots ,S-\mathrm{1}\right\}$$

（5）

$$d_{s,l_v}-a_{s,l_v}\le t_{s,v}^{\mathrm{m}\mathrm{a}\mathrm{x}}{\rho }_{s,l_v},\forall l_v\in L,s\in \left\{\mathrm{2},\dots ,S-\mathrm{1}\right\}$$

（6）

2.4.2　列车间隔时间约束

（1）出发间隔约束

$$d_{s,l_{v\mathrm{2}}}-d_{s,l_{v\mathrm{1}}}\ge (t_{\mathrm{d}\mathrm{d},s}+x_{s,v\mathrm{1}}{\rho }_{s,l_{v\mathrm{1}}}-x_{s,v\mathrm{2}}{\rho }_{s,l_{v\mathrm{2}}}){\alpha }_{s,l_{v\mathrm{1}},l_{v\mathrm{2}}}-M\left(\mathrm{1}-{\alpha }_{s,l_{v\mathrm{1}},l_{v\mathrm{2}}}\right),$$$$\forall l_{v\mathrm{1}}\in L,l_{v\mathrm{2}}\in L,l_{v\mathrm{1}}\ne l_{v\mathrm{2}},s\in \left\{\mathrm{1},\dots ,S-\mathrm{1}\right\}$$

（7）

$$d_{s,l_{v\mathrm{1}}}-d_{s,l_{v\mathrm{2}}}\ge -M{\alpha }_{s,l_{v\mathrm{1}},l_{v\mathrm{2}}}+(t_{\mathrm{d}\mathrm{d},s}+x_{s,v\mathrm{2}}{\rho }_{s,l_{v\mathrm{2}}}-x_{s,v\mathrm{1}}{\rho }_{s,l_{v\mathrm{1}}})\left(\mathrm{1}-{\alpha }_{s,l_{v\mathrm{1}},l_{v\mathrm{2}}}\right)$$，

$$\forall l_{v\mathrm{1}}\in L,l_{v\mathrm{2}}\in L,l_{v\mathrm{1}}\ne l_{v\mathrm{2}},s\in \left\{\mathrm{1},\dots ,S-\mathrm{1}\right\}$$

（8）

（2）到达间隔约束

$$a_{s,l_{v\mathrm{2}}}-a_{s,l_{v\mathrm{1}}}\ge (t_{\mathrm{a}\mathrm{a},s}-y_{s,v\mathrm{1}}{\rho }_{s,l_{v\mathrm{1}}}+y_{s,v\mathrm{1}}{\rho }_{s,l_{v\mathrm{2}}}){\beta }_{s,l_{v\mathrm{1}},l_{v\mathrm{2}}}-M\left(\mathrm{1}-{\beta }_{s,l_{v\mathrm{1}},l_{v\mathrm{2}}}\right)$$，

$$\forall l_{v\mathrm{1}}\in L,l_{v\mathrm{2}}\in L,l_{v\mathrm{1}}\ne l_{v\mathrm{2}},s\in \left\{\mathrm{2},\dots ,S\right\}$$

（9）

$$a_{s,l_{v\mathrm{1}}}-a_{s,l_{v\mathrm{2}}}\ge -M{\beta }_{s,l_{v\mathrm{1}},l_{v\mathrm{2}}}+(t_{\mathrm{a}\mathrm{a},s}-y_{s,v\mathrm{1}}{\rho }_{s,l_{v\mathrm{1}}}+y_{s,v\mathrm{2}}{\rho }_{s,l_{v\mathrm{2}}})\left(\mathrm{1}-{\beta }_{s,l_{v\mathrm{1}},l_{v\mathrm{2}}}\right)$$，$$\forall l_{v\mathrm{1}}\in L,l_{v\mathrm{2}}\in L,l_{v\mathrm{1}}\ne l_{v\mathrm{2}},s\in \left\{\mathrm{2},\dots ,S\right\}$$

（10）

（3）同一股道发到间隔约束

$$\begin{array}{l}{a}_{s,l_{v\mathrm{2}}}-d_{s,l_{v\mathrm{1}}}\ge t_{\mathrm{d}\mathrm{a},s}{\theta }_{l_{v\mathrm{1},}{r}_s}{\theta }_{l_{v\mathrm{2},}{r}_s}{\alpha }_{s,l_{v\mathrm{1}},l_{v\mathrm{2}}}-\\ M\left(\mathrm{2}-{\theta }_{l_{v\mathrm{1},}{r}_s}{\theta }_{l_{v\mathrm{2},}{r}_s}-{\alpha }_{s,l_{v\mathrm{1}},l_{v\mathrm{2}}}\right),\end{array}$$ $$\begin{array}{l}\forall l_{v\mathrm{1}}\in L,l_{v\mathrm{2}}\in L,l_{v\mathrm{1}}\ne l_{v\mathrm{2}},r_s\in \{{\mathrm{2}}_s,\dots ,R_s\},\\ s\in \left\{\mathrm{2},\dots ,S-\mathrm{1}\right\}\end{array}$$

（11）

2.4.3　股道占用约束

（1）接发股道唯一性约束

$$\sum _{r_s\in R_s}{\theta }_{l_{v,}{r}_s}=\mathrm{1},\forall l_v\in L,s\in S$$

（12）

（2）占用正线股道约束，当列车$l_v$在车站$s$通过时，只能占用正线股道。

$${\theta }_{l_{v,}{\mathrm{1}}_s}=\mathrm{1}-{\rho }_{s,l_v},\forall l_v\in L,\forall s\in \left\{\mathrm{2},\dots ,S-\mathrm{1}\right\}$$

（13）

2.4.4　车站接发停站列车数量约束

对每个车站的停靠列车数限制在一个范围内，避免列车过量停靠或停靠不足。

$$\sum _{l_v\in L}{\rho }_{s,l_v}\ge n_s^{min},\forall s\in S,\forall l_v\in L$$

（14）

$$\sum _{l_v\in L}{\rho }_{s,l_v}\le n_s^{max},\forall s\in S,\forall l_v\in L$$

（15）

2.4.5　列车停靠车站数量约束

对每列车的全线停站数量和列车经过的每一个区段的停站数量限制在一个范围内。

$$\sum _{s\in S}{\rho }_{s,l_v}\ge n_v^{min},\forall v\in \left(\mathrm{0,1}\right),\forall l_v\in L$$

（16）

$$\sum _{s\in S}{\rho }_{s,l_v}\le n_v^{max},\forall v\in \left(\mathrm{0,1}\right),\forall l_v\in L$$

（17）

$$\sum _{s\in S_u}{\rho }_{s,l_v}\ge n_{v,u}^{min},\forall v\in \left(\mathrm{0,1}\right),\forall u\in U,\forall l_v\in L$$

（18）

$$\sum _{s\in S_u}{\rho }_{s,l_v}\le n_{v,u}^{max},\forall v\in \left(\mathrm{0,1}\right),\forall u\in U,\forall l_v\in L$$

（19）

$$\sum _{s\in S}{\rho }_{s,l_v}=\sum _{u\in U}\sum _{s\in S_{\mathrm{u}}}{\rho }_{s,l_v},\forall v\in \left(\mathrm{0,1}\right),\forall l_v\in L$$

（20）

2.4.6　起始结束时间段约束

$$d_{s,l_v}\ge D,\forall l_v\in L,\forall s\in S$$

（21）

$$a_{s,l_v}\le A,\forall l_v\in L,\forall s\in S$$

（22）

2.4.7　列车停靠性约束

$${\rho }_{s,l_v}\le W_s,\forall l_v\in L,\forall s\in S$$

（23）

3 求解过程

3.1　算法总体流程

本文提出的二阶段求解算法流程图如图2所示，第一阶段求解列车运行图的生成，得到初始可行解，第二阶段实现列车运行图的压缩，得到满意解。具体过程如下所示。

图2  算法总体流程图

Fig. 2  Flowchart of algorithm

Step 1：模型参数输入，包括车站基础性质参数、列车停站数量与车站停靠车次数量、区间纯运行时间、起停附加时间、车站最小最大停站时间、区间最大运行冗余时间等。

Step 2：第一阶段列车运行图生成求解，得到列车停站方案、越行方案、股道运用方案，即初始方案列车运行图。

Step 3：若第一阶段无解，返回Step 2，调整仿真参数的值；若第一阶段有解，则进入Step 4。

Step 4：第二阶段列车运行图压缩求解，在列车停站方案、越行方案、股道运用方案不变的情况下，求解列车时刻表，即优化方案的列车运行图。

Step 5：求解结束，或返回Step 1，重新输入参数，进行新一轮求解。

3.2　列车越行条件判定

由于标杆列车会越行普通列车，需要考虑两种列车在相邻两站的运行顺序关系，二者之间列车到发顺序关系如图3所示。对于方式（1） $~$ （2），标杆列车在$s$站越行普通列车，两种列车在$s$站需要满足最小间隔时间标准。对于方式（3） $~$ （5），标杆列车在$s+\mathrm{1}$站越行普通列车，两种列车在$s+\mathrm{1}$站需要满足最小间隔时间标准，两种列车在$s$站需要满足最小间隔时间标准和基于在$s+\mathrm{1}$站满足最小间隔时间标准的基础上推出的在$s$站需要满足的间隔时间。

图3  标杆列车和普通列车到发顺序方式图

Fig. 3  Arrival and departure sequence of express and ordinary trains

综合上述5种越行方式及式（7）~（10），标杆列车越行普通列车关系约束表达式有：

$$d_{s,l_{v\mathrm{2}}}-d_{s,l_{v\mathrm{1}}}\ge (t_{\mathrm{p}\mathrm{d},s}(\mathrm{1}-{\rho }_{s,l_{v\mathrm{1}}})+t_{\mathrm{d}\mathrm{d},s}{\rho }_{s,l_{v\mathrm{1}}}){\alpha }_{s,l_{v\mathrm{1}},l_{v\mathrm{2}}}-M\left(\mathrm{1}-{\alpha }_{s,l_{v\mathrm{1}},l_{v\mathrm{2}}}\right)$$

$$\forall l_{v\mathrm{1}}\in \{\mathrm{1},\dots ,Q\},\forall l_{v\mathrm{2}}\in \{Q+\mathrm{1},\dots ,L\},s\in \left\{\mathrm{2},\dots ,S-\mathrm{1}\right\}$$

（24）

$$d_{s,l_{v\mathrm{1}}}-d_{s,l_{v\mathrm{2}}}\ge -M{\alpha }_{s,l_{v\mathrm{1}},l_{v\mathrm{2}}}+\left(t_{\mathrm{a}\mathrm{p},s}+x_{s,\mathrm{0}}+e_{s,\mathrm{0}}+y_{s+\mathrm{1,0}}-x_{\mathrm{s},\mathrm{1}}{\rho }_{s,l_{v\mathrm{1}}}-e_{s,\mathrm{1}}\right)\left(\mathrm{1}-{\alpha }_{s,l_{v\mathrm{1}},l_{v\mathrm{2}}}\right)$$

$$\forall l_{v\mathrm{1}}\in \{\mathrm{1},\dots ,Q\},\forall l_{v\mathrm{2}}\in \{Q+\mathrm{1},\dots ,L\},s\in \left\{\mathrm{2},\dots ,S-\mathrm{1}\right\}$$

（25）

$$\begin{array}{l}{a}_{s,l_{v\mathrm{2}}}-a_{s,l_{v\mathrm{1}}}\ge t_{\mathrm{a}\mathrm{a},s}{\beta }_{s,l_{v\mathrm{1}},l_{v\mathrm{2}}}-M\left(\mathrm{1}-{\beta }_{s,l_{v\mathrm{1}},l_{v\mathrm{2}}}\right),\forall l_{v\mathrm{1}}\in \{\mathrm{1},\dots ,Q\}\\ \forall l_{v\mathrm{2}}\in \{Q+\mathrm{1},\dots ,L\},s\in \left\{\mathrm{2},\dots .,S-\mathrm{1}\right\}\end{array}$$

（26）

$$a_{s,l_{v\mathrm{1}}}-a_{s,l_{v\mathrm{2}}}\ge -M{\beta }_{s,l_{v\mathrm{1}},l_{v\mathrm{2}}}+(t_{\mathrm{a}\mathrm{p},s}(\mathrm{1}-{\rho }_{s,l_{v\mathrm{1}}})+t_{\mathrm{a}\mathrm{a},s}{\rho }_{s,l_{v\mathrm{1}}})\left(\mathrm{1}-{\beta }_{s,l_{v\mathrm{1}},l_{v\mathrm{2}}}\right)$$

$$\forall l_{v\mathrm{1}}\in \{\mathrm{1},\dots ,Q\},\forall l_{v\mathrm{2}}\in \{Q+\mathrm{1},\dots ,L\},s\in \left\{\mathrm{2},\dots ,S-\mathrm{1}\right\}$$

（27）

3.3　第一阶段列车运行图生成求解

由于0‒1变量${\alpha }_{s,l_{v\mathrm{1}},l_{v\mathrm{2}}}$、${\beta }_{s,l_{v\mathrm{1}},l_{v\mathrm{2}}}$为三维变量，空间复杂度为o（n³），占用空间过大。对于标杆列车，由于其数量少，停站只停枢纽站，设定在始发站按固定时刻发车，把标杆列车的运行线先确定，即$d_{s,l_{\mathrm{1}}}、a_{s,l_{\mathrm{1}}}、{\rho }_{s,l_{\mathrm{1}}}、{\theta }_{l_{\mathrm{1},}{r}_s}$做为参数代入模型，求解出列车越行方案，低等级列车的停站方案、到发时刻、股道选择，得到初始方案列车运行图。第一阶段以式（1）为目标函数，式（3）$~$（27）为约束条件，由于$d_{s,l_{\mathrm{1}}}\mathrm{、}{a}_{s,l_{\mathrm{1}}}\mathrm{、}{\rho }_{s,l_{\mathrm{1}}}\mathrm{、}{\theta }_{l_{\mathrm{1},}{r}_s}$做为参数代入模型，减小了决策变量的数量。对于式（11），引入辅助0‒1变量以文献［19］线性化处理方法进行处理，如式（28）所示。

$$c=ab\Rightarrow \left\{\begin{array}{l}a\ge c\\ b\ge c\\ c\ge a+b-\mathrm{1}\\ a,b,c\in [\mathrm{0,1}]\end{array}\right.$$

（28）

3.4　第二阶段列车运行图压缩求解

由于第一阶段标杆列车运行线固定，故运行线中可能存在能力未能被利用的情况。对于初始方案的结果，把${\rho }_{s,l_v}$、${\alpha }_{s,l_{v\mathrm{1}},l_{v\mathrm{2}}}$、${\beta }_{s,l_{v\mathrm{1}},l_{v\mathrm{2}}}、{\theta }_{l_{v,}{r}_s}$的值作为参数，同时，标杆列车的到达时刻、出发时刻不再固定。对于式（25），由于列车越行方案已经确定，不需进行二次判断，可简化为式（29）。由于式（11）变为线性表达式，模型转换为线性规划模型，模型的空间复杂度降为o（n²）。第二阶段以式（1）+（2）为目标函数，式（3）$~$（11）、（21）$~$（22）、（24）、（26）、（27）、（29）为约束条件，可再次求得列车在车站的到达时刻、出发时刻。本次求解，在保持列车停站方案、越行方案、股道方案与第一阶段一致的前提下，减少了列车运行线之间的空隙，向前移动了列车运行线，压缩了列车在中间站的非必要的停站时间和区间运行冗余时间，提升了列车的旅行速度，完善了初始方案，求得最优满意解。

$$\begin{array}{l}{d}_{s,l_{v\mathrm{1}}}-d_{s,l_{v\mathrm{2}}}\ge -M{\alpha }_{s,l_{v\mathrm{1}},l_{v\mathrm{2}}}+t_{\mathrm{d}\mathrm{d},s}\left(\mathrm{1}-{\alpha }_{s,l_{v\mathrm{1}},l_{v\mathrm{2}}}\right),\forall l_{v\mathrm{1}}\in \{\mathrm{1},\dots ,Q\},\\ \forall l_{v\mathrm{2}}\in \{Q+\mathrm{1},\dots ,L\},s\in \left\{\mathrm{2},\dots ,S-\mathrm{1}\right\}\end{array}$$

（29）

4 案例分析

4.1　求解准备

本案例分析运行在Windows 10系统环境下，运用C#语言并调用Gurobi求解器编写程序代码，在Visual Studio 2017环境下编译。以京沪高速铁路北京南—上海虹桥下行方向为求解线路，该线路共有29个节点。根据既有京沪高速铁路列车运行图规律，车站等级分类如表1所示，列车的停站要求如表2所示。标杆列车和普通列车在始发站北京南站按照1∶9和1∶10的发车比例模式发车。

表1  车站停靠参数

Tab. 1  Stopping parameters of stations

停靠率/%	车站（下行方向列车可使用到发线股道数）	车站描述
100	北京南（12）、济南西（7）、南京南（5）、上海虹桥（19）	直辖市或省会级别车站，拥有最高的级别
80$~$90	徐州东（6）	铁路枢纽重要客运大站，处于线网中的关键位置，站场规模大、客流量大
45$~$65	德州东（2）、蚌埠南（4）、常州北（2）、无锡东（2）、苏州北（2）	车站有多条线路交汇、站场规模较大或者经济发达、客流量较大的地级车站
25$~$45	天津南（2）、沧州西（2）、泰安（2）、曲阜东（2）、枣庄（2）、 宿州东（2）、滁州（2）、镇江南（2）	站场规模为2台6线或地级车站
10$~$25	廊坊（1）、滕州东（1）、定远（1）、丹阳北（1）、昆山南（2）	站场规模为2台4线或县级车站

表2  列车停站参数

Tab. 2  Stopping parameters of trains

列车类型	总停站数/个	区段内中间站停站数/个
		北京南—济南西	济南西—徐州东	徐州东—南京南	南京南—上海虹桥
标杆列车	4	0	0	0	0
普通列车	9$~$12	1$~$2	1$~$2	1$~$2	1$~$3

4.2　小规模算例求解及分析

为了测试算法的有效性，求解1∶9发车比例模式下，始发站发车时间段时长为2$~$5 h的北京南—济南西区段的小规模算例，分别用直接计算法和本文提出的二阶段求解方法进行对比，求解结果如图4、表3所示。由于二阶段法求解原理与直接计算法不同，且搜索范围较直接计算法大大缩小，普通列车平均用时最大差异为2 min 46 s，平均停站数最大差异为0.3，末班车到达时间最大差异为4 min 25 s，二者的求解指标差异较小且比较稳定，并没有因数据的增加而放大。由于模型是非线性模型，随着求解规模的不断增加，直接计算法无效的搜索范围过多，导致求解时间呈现指数型的增长，当发车时段长达到5 h时，求解则非常困难，直接计算法面向现实工程应用中并不可行。相对于直接计算法，二阶段法可大幅度提升模型的求解的速度，求解过程稳定，适用于大规模求解的需要，故本文提出的二阶段法具有一定的合理性。

图4  1∶9模式， 2$~$4 h发车时段北京南—济南西列车运行图对比图

Fig. 4  Comparison of train diagram between Beijing South Railway Station and Jinan West Railway Station in the 1∶9 scheme at 2 to 4 h departure period

表3  求解方法对比

Tab. 3  Comparison of solutions

始发站 连续发车 时长/h	标杆列车 数量/列	普通列车 数量/列	列车运行线占用时间		普通列车平均旅行时间		普通列车平均 停靠次数		求解时长/s
			直接计算法	二阶段法	直接计算法	二阶段法	直接计 算法	二阶 段法	直接计算法	二阶 段法
2	2	18	3 h 7 min 16 s	3 h 8 min 32 s	1 h 40 min 40 s	1 h 43 min 26 s	3.2	3.5	14	2
3	3	27	3 h 59 min 50 s	4 h 3 min 30 s	1 h 40 min 56 s	1 h 41 min 54 s	3.2	3.3	59	2
4	4	36	4 h 50 min10 s	4 h 54 min 35 s	1 h 40 min 35 s	1 h 40 min 45 s	3.2	3.2	1 164	3
5	5	45		5 h 56 min 57 s		1 h 41 min 36 s		3.2	>7 200	4

4.3　大规模算例求解及分析

为了测试模型的性能，分别求解1∶9、1∶10发车比例模式下，始发站发车时间段时长为3$~$12 h的结果。由于篇幅限制，图像只给出12 h的求解结果，各种结果如图5、6，表4~6所示，可得到以下结论：

图5  1∶9模式， 12 h发车时段北京南—上海虹桥列车运行图

Fig. 5  Train diagram from Beijing South Railway Station to Shanghai Hongqiao Railway Station in the 1∶9 scheme at 12 h departure period

图6  1∶10模式， 12 h发车时段北京南—上海虹桥列车运行图

Fig. 6  Train diagram from Beijing South Railway Station to Shanghai Hongqiao Railway Station in the 1∶10 scheme at 12 h departure period

表4  1∶9模式北京南—上海虹桥优化计算指标

Tab. 4  Optimization calculation index of Beijing South Railway Station to Shanghai Hongqiao Railway Station in the 1∶9 scheme

始发站连续发车时长/h	标杆列车 数量/列	普通列车 数量/列	列车运行线 占用时间	标杆列车平均 旅行时间	普通列车平均 旅行时间	普通列车平均停靠次数	求解时长/ s
3	4	27	8 h 18 min 59 s	4 h 23 min 23 s	5 h 53 min 40 s	10.7	61
4	5	36	9 h 18 min 51 s	4 h 23 min 23 s	5 h 57 min 24 s	10.8	72
5	6	45	10 h 16 min 29 s	4 h 23 min 23 s	5 h 57 min 57 s	10.6	106
6	7	54	11 h 14 min 3 s	4 h 23 min 23 s	5 h 57 min 56 s	10.6	109
7	8	63	12 h 9 min 50 s	4 h 23 min 33 s	5 h 59 min 56 s	10.6	107
8	9	72	13 h 8 min 23 s	4 h 23 min 25 s	6 h 0 min 30 s	10.7	231
9	10	81	14 h 2 min 27 s	4 h 23 min 26 s	5 h 59 min 0 s	10.7	141
10	11	90	15 h 4 min 26 s	4 h 23 min 23 s	5 h 58 min 52 s	10.7	346
11	12	99	16 h 2 min 28 s	4 h 23 min 42 s	6 h 1 min 27 s	10.6	306
12	13	102	16 h 30 min 45 s	4 h 23 min 38 s	5 h 57 min 42 s	10.7	274

表5  1∶10模式北京南—上海虹桥优化计算指标

Tab. 5  Optimization calculation index of Beijing South Railway Station to Shanghai Hongqiao Railway Station in the 1∶10 scheme

始发站连续发车时长/h	标杆列车 数量/列	普通列车 数量/列	列车运行线 占用时间	标杆列车平均 旅行时间	普通列车平均 旅行时间	普通列车平均停靠次数	求解时长/ s
3	4	30	8 h 24 min 21 s	4 h 23 min 23 s	5 h 53 min 17 s	10.4	177
4	5	40	9 h 22 min 44 s	4 h 23 min 27 s	5 h 54 min 23 s	10.5	354
5	6	50	10 h 24 min 9 s	4 h 23 min 25 s	5 h 56 min 2 s	10.6	424
6	7	60	11 h 22 min 24 s	4 h 23 min 23 s	5 h 56 min 51 s	10.6	346
7	8	70	12 h 22 min 2 s	4 h 23 min 23 s	6 h 2 min 11 s	10.7	357
8	9	80	13 h 24 min 40 s	4 h 23 min 23 s	6 h 1 min 7 s	10.6	594
9	10	90	14 h 23 min 56 s	4 h 23 min 23 s	5 h 59 min 14 s	10.5	866
10	11	100	15 h 23 min 7 s	4 h 23 min 23 s	6 h 0 min 33 s	10.5	1 176
11	12	110	16 h 21 min 19 s	4 h 23 min 23 s	6 h 0 min 54 s	10.5	1 437
12	13	113	16 h 46 min 23 s	4 h2 3 min 23 s	6 h 2 min 36 s	10.8	1 043

表6  实际列车运行图与求解列车运行图在普通列车计算指标上的对比

Tab. 6  Comparison of calculation indexes of ordinary trains between actual train diagram and solving train diagram

列车运行图类型	列车数量/列	最短旅行 时间	最长旅行 时间	全程平均旅行 时间	全程平均旅行 速度/（km$·$h-1）	最少停靠次数	最多停靠次数	平均停靠次数
2023年10月列车运行图基本图	27	5 h 35 min 0 s	6 h 23 min 0 s	5 h 59 min 44 s	219.8	8.0	14.0	11.0
本文求解案例	1 412	5 h 32 min 40 s	6 h 14 min 44 s	5 h 55 min 56 s	222.2	9.0	12.0	10.6

（1）随着列车数量的增加，模型的求解时间未出现指数型增长，模型能够适应大规模求解的需求。模型求解的gap值均为0，在较短时间内实现了精确求解，模型的求解性能稳定。

（2）随着列车数量的增加，标杆列车全程平均用时，普通列车全程平均停靠次数指标基本稳定。标杆列车数量增加时，普通列车全程平均用时呈缓慢上升趋势。总体上看，列车运行线符合停站由远及近特征，符合高速铁路列车运行图能力利用最大化的规律。模型能够适应不同的条件场景，模型的求解功能稳定。

（3）由于各站停站比例要求不同、各区间行车时间不同，即使对于N=10的列车运行图，在普通列车运行线内，北京南—京津所，津沪所—济南西，济南西—徐州东，徐州东—南京南区段仍然存在个别空隙可加开列车，说明通过能力并不能在全线所有区段所有时段内均被完全利用。

（4）2023年10月全国铁路列车运行图调图中，京沪高速铁路下行27列全程本线普通列车的平均用时为5 h 59 min 44 s，平均运行速度为219.8 km$·$h^-1，平均停靠数为11个。本模型的大量求解结果指标与实际列车运行图相近，具有一定的合理性，可作为一种有效的初始化基本图生成方法。

5 结论

将车站经停需求和列车停站需求纳入列车运行图优化约束条件，以到发时刻、停站方案、两列车之间运行顺序关系、股道选择为决策变量，构建列车运行图优化模型。提出了二阶段求解的策略，实现了列车运行图生成与压缩一体化处理，能够适应大规模求解的需求。以京沪高速铁路为案例，研究结果表明，随着列车数量不断增加，本模型并没有因为求解复杂度增加而导致功能降低，依然能够保持较高的稳定性能。提出的方法有利于制定适应市场需求的高速铁路客运服务产品，可为铁路部门提供运输组织参考决策。未来，可以从以下几个方面对模型进行进一步的深化。

（1）由于约束条件的设置，有时可造成列车运行图中一部分能力未能被利用，但这部分未能被利用的能力不能开行全程列车，可研究短程列车的开行，充分利用运行图的空余时段。

（2）面向工程化应用，可结合起点和终点的客流量，进一步细化列车停站方案和车站停车数量的设置，使得列车运行图的铺画在考虑站、车因素的同时，进一步考虑客流因素的影响。

作者贡献声明

高金科：论文撰写与修改，模型的计算机编码与实现。

滕 靖：论文选题，方法设计与指导，统筹研究工作。

曲思源：论文数据支持与专业性理论指导。