基于节点路由的高速铁路列车运行线次序优化方法

Optimization Method for Train Path Sequence of High-Speed Railway Based on Node Routing

摘要

针对部分高速铁路能力利用紧张的问题，提出1种基于节点路由的高速铁路列车运行线次序优化方法。首先，将列车运行线抽象为节点，其接续关系抽象为有向弧，从而使列车运行线次序优化问题转化为节点路由问题；其次，开发列车越行组合设计、弧权重计算、列车运行线次序优化和列车运行图编制等模块；最后，以京沪高铁的某区段为例，验证该方法的可行性，并分析列车运行线次序调整范围及列车越行组合设计对能力利用的影响规律。结果表明：通过对实际列车运行图进行优化，区段通过能力提高5.26%，列车平均旅行时间减少3.18%；随着列车运行线次序调整范围的逐步扩大，区段通过能力的增幅持续提升，最高可提升31.58%。该方法通过优化列车运行线次序有效提升了区段通过能力，为繁忙高速铁路的能力利用优化提供技术支撑。

Abstract

In response to the issue of tight capacity utilization on certain high-speed railways, an optimization method for train path sequence of high-speed railway based on node routing is proposed. First, train paths are abstracted as nodes, and the connection relationships between them are abstracted as directed arcs, thereby transforming the optimization problem of train path sequence into a node routing problem. Second, modules such as train overtaking combination design, arc weight calculation, train path sequence optimization, and train timetable scheduling are developed. Finally, a certain section of Beijing-Shanghai High-Speed Railway is taken as an example to verify the feasibility of the method, and the impact laws of the adjustment range of train path sequence and train overtaking combination design on capacity utilization are analyzed. The results show that through the optimization of the actual train timetable, the section carrying capacity increases by 5.26 %, and the average travel time of the trains decreases by 3.18%. As the adjustment range of train path sequence gradually expands, the increase in section carrying capacity continues to grow, with a maximum improvement of 31.58%. This method effectively enhances the section carrying capacity by optimizing the train path sequence, providing technical support for the optimization of capacity utilization on busy high-speed railways.

Graphical abstract

关键词

高速铁路 / 列车运行图 / 区段通过能力 / 节点路由 / 时空资源

Key words

High-speed railway / Train timetable / Section carrying capacity / Node routing / Time-space resources

随着我国经济的快速发展和出行需求的持续增长，高速铁路已成为重要的交通方式之一。在节假日客流高峰期，部分高速铁路客票供不应求，难以满足出行需求。每日加开少量列车不仅能显著提升铁路运输企业的经济效益，还能更好地满足旅客需求。然而，我国许多高速铁路（如京沪高铁和沪杭高铁）的列车运行图已接近饱和，难以进一步压缩或插入新的列车运行线。因此，研究高速铁路能力利用优化方法，探索能力利用规律，对于优化列车运行图、最大限度满足日益增长的旅客出行需求具有重要意义。

关于列车运行图优化与铁路能力利用率提升的研究，目前已有较为丰富的文献积累。基于现有研究成果，将主要优化策略归纳为4类：压缩法、插线法、列车开行方案优化法以及列车运行线次序优化法。在压缩法的应用方面，Yaghini等^［1］基于时空网络构建数学模型，结合分支定界算法，量化分析了不同种类列车混跑对线路通过能力的影响。张守帅^［2］考虑停站比例、越行比例和次数等约束条件，以最小化列车占用时间为目标，设计了列车运行图编制模型和算法。王高磊^［3］细化了列车运行图压缩和加密的具体实现步骤，为实际应用提供了操作性指导。在插线法的应用方面，Cacchiani等^［4］提出了1种基于固定旅客列车运行图的货运列车插入方法，结合运营商提供的理想发车时刻，验证了运行图优化效果。高如虎等^［5］针对基本运行图加线问题，建立了基于Time-Station-Track网络的0-1整数规划模型，以提高插入方案的可行性。曲云腾等^［6］面向区域城际铁路网络，构建了运行图加线优化模型，并设计了1种高效的滚动时域求解算法。在列车开行方案优化方面，路超等^［7］基于随机生成的若干组多等级列车开行方案备选集合，采用分支定界算法求解包含最多列车运行线的可行集合。Bešinović等^［8］以最大限度地满足运输需求为目标，提出列车开行方案及相应频率的确定方法。王宇强等^［9］构建了列车时刻表优化模型，运用交替方向乘子法求解模型，优化部分列车的停站方案以提升线路通过能力利用率。周文梁^［10］开发了列车开行方案与运行图综合优化模型，并采用基于模拟退火的综合优化算法进行求解。邹信诚^［11］以铁路运输企业收益最大化为目标，构建了高速铁路列车开行方案和运行图一体化优化模型，设计了滚动时间域算法。在列车运行线次序优化方面，Jamili等^［12］提出了1种基于模拟退火和粒子群算法的混合启发式算法，通过随机编码生成列车运行线初始序列并进行迭代优化。在给定备选列车集的情况下，文献［13—14］通过Fisher-Yates洗牌算法生成列车运行线次序，并设计了分支定界策略和禁忌搜索策略，有效平衡了计算效率。聂磊等^［15］针对周期性列车运行图编制问题，重点考虑了列车在各区间的占用次序。白紫熙等^［16］在固定列车类型、停站方案及频次的前提下，运用遗传算法优化高速列车开行顺序，并提出“部分平移＋冲突更新”方法实现中速列车的协同铺画。压缩法和插线法仅适用于尚有容余的列车运行图，对无容余运行图的通过能力提升无效。针对无容余运行图，列车开行方案优化法通过调整停站结构可提升通过能力利用率，但会显著影响开行方案、运行图和客流分配，可能降低服务质量。相较而言，列车运行线次序优化法仅局部调整列车次序，其实施难度更低且不改变既有方案。现有研究虽建立了次序优化与区段能力的迭代规则，但其优化效果缺乏定量评估，且未充分揭示次序对通过能力的影响机理，其决策支持作用有限。

本研究提出1种高速铁路列车运行线次序优化方法。基于复杂网络理论，将列车运行线次序优化问题转化为节点路由问题，构建网络优化模型。包含越行组合设计、弧权重计算、运行线次序优化和运行图编制4个关键模块。在提升线路通过能力的同时，也为高铁运输组织优化提供了新的决策支持工具。

1 列车运行线次序优化问题

节点路由问题是1类经典的数学优化问题，主要包括最短路问题、中国邮路问题、最小生成树问题和最大流问题等类型。其求解算法涵盖Dijkstra算法、动态规划算法、启发式算法以及数学优化求解器等。该问题在通信领域已有广泛应用（见文献［17—18］），而在铁道运输领域则主要集中于车流径路优化问题（见文献［19—20］）。典型的节点路由问题实例如图1所示。图中：{\mathrm{v}}_{\mathrm{1}}为起点；{\mathrm{v}}_{\mathrm{6}}为终点；{\mathrm{v}}_{\mathrm{2}}—{\mathrm{v}}_{\mathrm{5}}为中间节点；数字为节点间的路径长度。该问题的核心优化目标是寻找从起点到终点的最小成本路径。从建模方法论的角度来看，节点路由问题具有3个基本特征：①节点代表系统中的实体对象；②弧刻画对象间的关联关系；③有向弧权重量化了这些关系的成本或距离。这种基于图论的建模方法能将复杂的现实系统转化为可计算的形式化模型，并且可以充分利用成熟的图算法实现全局优化。

列车运行图包含可分配的时空资源（具体表现为运行图中可供铺画运行线的区域），而列车开行将占用部分时空资源。列车运行线次序优化的核心目标在于通过提高时空资源利用效率提升线路通过能力。假设列车\mathrm{G}\mathrm{1}，\mathrm{G}\mathrm{3}，\mathrm{G}\mathrm{5}和\mathrm{G}\mathrm{7}从车站\mathrm{E}始发，途经车站\mathrm{D}，\mathrm{C}和\mathrm{B}，到达车站\mathrm{A}，初始列车运行图中的时空资源分配情况如图2所示。图中描述的3类时空资源分别为：位于列车\mathrm{G}\mathrm{1}的运行线与运行图左侧边界线之间的时空资源S_{\mathrm{1}}；相邻列车运行线之间的时空资源S_{\mathrm{2}}，S_{\mathrm{3}}和S_{\mathrm{4}}；位于列车\mathrm{G}\mathrm{7}的运行线与运行图右侧边界线之间的时空资源S_{\mathrm{5}}。这些时空资源具有可量化的几何特征，可通过计算对应区域的时空面积进行精确度量。值得注意的是，时空资源可量化特性是列车运行线次序优化问题转化为节点路由问题的基本前提。

优化后的列车运行图如图3所示。与初始运行图相比，两者的列车间隔时间均被压缩至最小，但由于列车运行线次序的变化，优化后的列车运行图的时空资源利用率明显高于初始列车运行图，从而增强了区段通过能力。列车运行线次序优化问题可转化为节点路由问题。前者通过合理安排列车运行线的铺画顺序，在限定时段内使运行线数量最大化；而后者则聚焦于通过优化节点访问顺序确定最优路径。这2个问题在优化的目标和方法上具有紧密的相关性，具体转化方法为将每1条列车运行线抽象为1个节点，并通过有向弧表示运行线之间的接续关系。其中，有向弧的权重对应于运行线间占用的时空资源。此外，引入虚拟起点和虚拟终点分别表征运行图的左、右边界。基于此，列车运行线次序优化问题即转化为：在满足各弧权重之和不超过时空资源总量的约束条件下，寻找一条从虚拟起点出发、经过最多节点、最终抵达虚拟终点的最优路径。

基于节点路由的列车运行线次序优化问题示意图如图4所示。图中：\mathrm{G}\mathrm{0}为运行图左侧边界线；\mathrm{G}n为右侧边界线。边界线\mathrm{G}\mathrm{0}和\mathrm{G}n以及列车\mathrm{G}\mathrm{1}—\mathrm{G}\mathrm{9}等均被抽象为节点，各节点间通过有向弧相连接（为突出重点，图中未全部显示）。初始路径G0—G1—G3—G5—G7—Gn，对应于图2中的列车运行线次序。其中，被选弧C(\mathrm{G}\mathrm{1},\mathrm{G}\mathrm{3})表示列车\mathrm{G}\mathrm{1}的运行线位于\mathrm{G}\mathrm{3}左侧并与其相邻；未被选弧C(\mathrm{G}\mathrm{1},\mathrm{G}\mathrm{5})表示\mathrm{G}\mathrm{1}的运行线不在\mathrm{G}\mathrm{5}的左侧或不与其相邻；弧C(\mathrm{G}\mathrm{1}，\mathrm{G}\mathrm{3})的权重对应\mathrm{G}\mathrm{1}和\mathrm{G}\mathrm{3}运行线间的时空资源。弧C(\mathrm{G}\mathrm{0},\mathrm{G}\mathrm{1})的权重对应\mathrm{G}\mathrm{0}和\mathrm{G}\mathrm{1}运行线形成的类三角形区域所占用的时空资源；弧C(\mathrm{G}\mathrm{7},\mathrm{G}n)的权重对应\mathrm{G}\mathrm{7}运行线和右侧边界线\mathrm{G}n形成的类三角形区域所占用的时空资源。经优化后得到新路径G0—G1—G7—G5—G3—G9—Gn，对应于图3中的列车运行线次序。优化前、后所有被选弧的权重总和均满足时空资源约束，但通过调整运行线次序，优化后区段通过能力提升1列。随着时间跨度的延长，运行线次序对限定时段内可容纳列车数量的影响更为显著。然而，该方法的实施面临1个主要障碍，即弧权重并非静态的定值，其具有动态变化的特性，随前后列车在各站到发时刻的调整而发生变化。

2 基于节点路由的列车运行线次序优化算法

2.1　算法流程与符号定义

列车运行线次序优化是1个具有多层级耦合特性的复杂系统问题，其核心挑战在于处理各子问题间的动态反馈机制产生的影响，即运行线次序的调整会改变列车到发时刻，进而影响弧权重的计算，而更新后的弧权重又会反作用于最优次序的确定。此外，列车运行速度、追踪间隔时间和中间站停站时间都会对弧权重和时刻安排产生重要影响。

为解决这一复杂问题，将其拆分为列车越行组合设计、弧权重计算、运行线次序优化和运行图编制4个模块进行处理，其优化算法流程如图5所示。对于无法被压缩的运行图，算法保证了弧权重与时空资源占用量的严格等价性，以及次序优化模块与运行图编制模块计算的区段通过能力的全局一致性，从而在分解问题的同时保持最优解质量。该算法的假设条件为：暂不考虑车站到发线数量的限制，即假设车站具备充足的接发车能力；假定同等级列车在区间的纯运行时间保持恒定，且不考虑天气异常、设备故障等不可预见因素导致的区间慢行情况。

该算法涉及以下集合与元素：I为列车集合；i，i^{\text{'}}为列车，i,i^{\text{'}}\in I；i_{\mathrm{1}}，i_{\mathrm{2}}，…，i_{\mathrm{5}}为特定编号的列车；L为节点集合；l，l^{\text{'}}为节点，l,l^{\text{'}}\in L；l_{\mathrm{1}}，l_{\mathrm{2}}，…，l_{\mathrm{4}}为特定编号的节点；R为子集合编号集合；r为子集合编号，r\in R；K为车站集合；k，k^{\text{'}}为车站，k,k^{\text{'}}\in K；J为节点路由次序编号集合；j为节点路由次序编号，j\in J；L_{\mathrm{o}}为表示列车越行组合的特殊节点集合，l\in L_{\mathrm{o}}；L_{\mathrm{b}}为普通节点集合；L_r为节点子集合；I_r为列车子集合；I_l为列车越行组合。

集合I和L的映射关系如图6所示。图中：集合I包含5列列车，其中i_{\mathrm{4}}为待避列车，i_{\mathrm{5}}为越行列车；集合L包含4个节点，其中l_{\mathrm{4}}为对应列车越行组合I_{l_{\mathrm{4}}}的特殊节点。当存在列车越行情况时，将越行列车和待避列车组合为1个整体，此时集合I和L为满射关系，而非单射关系，其函数表示式为f:I\to L （f （i）表示列车i在映射f下对应的节点，f^{-\mathrm{1}} （l）表示节点l在映射f下对应的列车）。

2.2　列车越行组合设计

列车越行组合的设计需综合考虑越行的可行性及不同组合的时空资源占用量等因素。其关键要素包括列车数量、停站结构、开行次序和越行站位置等。组合内的列车数量根据列车速度差异、区间运行时分差异合理确定。该设计模块的原理是计算不同列车运行线线群占用的时空资源，并选取资源占用量最小的线群作为最优列车越行组合，具体流程如下。

步骤1：根据具体案例中的区段里程和不同等级列车的速度差异，设定越行组合内的列车数量w。

步骤2：从当前列车子集I_r中挑选任意w列列车，构成列车越行组合I_l=\{i_{\mathrm{1}},i_{\mathrm{2}},\dots ,i_w\}，其中，i_w为高等级高速列车（运行速度更快，停站次数更少）；其余为低等级高速列车。列车越行组合的时空资源占用量计算模型的目标函数z_{\mathrm{1}}和约束条件为

\begin{array}{l}{z}_{\mathrm{1}}=\mathrm{m}\mathrm{i}\mathrm{n}\left[{\displaystyle \sum _{k=\mathrm{1}}^{n-\mathrm{1}}}\left(\underset{i\in I_l}{\mathrm{m}\mathrm{a}\mathrm{x}}(d_{i,k})-\underset{i\in I_l}{\mathrm{m}\mathrm{i}\mathrm{n}}(d_{i,k})+\right.\right.\\ \left.\left.\underset{i\in I_l}{\mathrm{m}\mathrm{a}\mathrm{x}}(a_{i,k+\mathrm{1}})-\underset{i\in I_l}{\mathrm{m}\mathrm{i}\mathrm{n}}(a_{i,k+\mathrm{1}})\right)m_{k,k+\mathrm{1}}/\mathrm{2}\right]\end{array}（1）

s.t.

d_{i_{\mathrm{1}},\mathrm{1}}=t_{\mathrm{d}}（2）

a_{i_w,n}\le a_{i_{\mathrm{1}},n}（3）

\begin{array}{l}{a}_{i,k}=d_{i,k^{\text{'}}}+h_{i{k}^{\text{'}}}{\theta }_{i{k}^{\text{'}}}+t_{i{k}^{\text{'}}k}+h_{ik}^{\text{'}}{\theta }_{ik}\\ \forall i\in I,\mathrm{1}\le k^{\text{'}}\le n-\mathrm{1},k=k^{\text{'}}+\mathrm{1}\end{array}（4）

|d_{i,k}-d_{i^{\text{'}},k}|\ge t_k^{\mathrm{d}\mathrm{e}\mathrm{p}}\forall i,i^{\text{'}}\in I,\forall k\in K（5）

|a_{i,k}-a_{i^{\text{'}},k}|\ge t_k^{\mathrm{a}\mathrm{r}\mathrm{r}}\forall i,i^{\text{'}}\in I,\forall k\in K（6）

\begin{array}{l}{d}_{i,k}=a_{i,k}+t_k^{\mathrm{s}\mathrm{t}\mathrm{o}\mathrm{p}}{\theta }_{ik}+(t_k^{\mathrm{a}\mathrm{v}\mathrm{o}}-t_k^{\mathrm{s}\mathrm{t}\mathrm{o}\mathrm{p}})\alpha (i,i_w,k)\\ \forall i\in I_l,\forall k\in K\end{array}（7）

\sum _{k\in K}\alpha (i,i_w,k)=\mathrm{1}\forall i\in I_l,\forall k\in K（8）

式中：d_{i,k}为列车i从车站k出发的时刻；a_{i,k}为列车i到达车站k的时刻；m_{k,k+\mathrm{1}}为车站k和车站k+\mathrm{1}之间的里程；n为线路上的车站总数量；d_{i_{\mathrm{1}},\mathrm{1}}为列车i_{\mathrm{1}}从始发站发车的时间；t_{\mathrm{d}}为列车运行图的起始时刻；a_{i_{\mathrm{1}},n}和a_{i_w,n}分别表示列车i_{\mathrm{1}}和i_w到达终点站的时间；t_{i{k}^{\text{'}}k}为列车i在车站k^{\text{'}}和车站k之间的纯运行时间；h_{i{k}^{\text{'}}}为列车i在车站k^{\text{'}}的起动附加时间；h_{ik}^{\text{'}}为列车i在车站k的停车附加时间；{\theta }_{ik}表示列车i是否在车站k停车，若停车取值为1，否则取值为0；t_k^{\mathrm{d}\mathrm{e}\mathrm{p}}为列车在车站k的发车追踪间隔时间；t_k^{\mathrm{a}\mathrm{r}\mathrm{r}}为列车在车站k的到达追踪间隔时间；t_k^{\mathrm{s}\mathrm{t}\mathrm{o}\mathrm{p}}为列车在车站k的停站时间；t_k^{\mathrm{a}\mathrm{v}\mathrm{o}}为列车在车站k避让其他列车时的停站时间；\alpha (i,i_w,k)为0-1决策变量，若列车i_w在车站k越行列车i，其值取1，否则取0。

该模型以式（2）为列车始发时间约束、式（3）为列车终到时间约束、式（4）为列车运行时间约束、式（5）—式（6）为间隔时间约束、式（7）为停站时间约束及式（8）为禁止多次越行逻辑约束。通过MATLAB平台调用Gurobi求解器对模型进行求解（鉴于该方法可在较短时间内高效求得最优解，后续构建的各模型均以此作为求解策略）。z_{\mathrm{1}}的运行结果即为该组列车越行组合内的时空资源占用量s_{\mathrm{3}}(l)。

步骤3：重复步骤2，直至遍历当前列车子集的所有可能组合，为每一高等级高速列车设计最优的列车越行组合方案。

步骤4：记录越行站位置\alpha \left(i,i_w,k\right)，并采集列车越行组合内各列车在各站的出发间隔时间D_{i{i}^{\text{'}}k}和到达间隔时间A_{i{i}^{\text{'}}k}，其计算式分别为

D_{i{i}^{\text{'}}k}=d_{i^{\text{'}},k}-d_{i,k}\forall k\in K,\forall i,i^{\text{'}}\in I_l（9）

A_{i{i}^{\text{'}}k}=a_{i^{\text{'}},k}-a_{i,k}\forall k\in K,\forall i,i^{\text{'}}\in I_l（10）

步骤5：若列车子集合I_r为最后1个子集合，算法终止，否则，令r自增1，转入步骤2。

2.3　弧权重计算

2.3.1 无越行情况

无越行情况下列车运行线占用的时空资源如图7所示。假设列车i^{\text{'}}和i依次通过E—A区段，图中：S_{\mathrm{6}}表示因停站差异产生的额外资源占用（含停站时间、起停附加时分和运行速度等因素影响）；S_{\mathrm{7}}表示由最小追踪间隔决定的基本资源占用。相同速度下列车的S_{\mathrm{7}}恒定，但S_{\mathrm{6}}随停站模式变化显著。通过优化列车运行次序以最小化S_{\mathrm{6}}，可有效提升时空资源利用效率与区段通过能力。

列车运行线间的时空资源占用量可通过运行线围成的区间面积进行量化，其面积由区间里程（横向跨度）和列车到发时刻差（纵向跨度）共同决定。因此，列车i^{\text{'}}和i间的时空资源占用量s\left(f(i^{\text{'}}),f(i)\right)（对应节点f(i^{\text{'}})和f(i)间的弧权重）、列车i^{\text{'}}与运行图左边界线间的时空资源占用量s_{\mathrm{1}}\left(f(i^{\text{'}})\right)及列车i和运行图右边界线间的时空资源占用量s_{\mathrm{2}}\left(f(i)\right)的计算式分别为

s\left(f(i^{\text{'}}),f(i)\right)={\displaystyle \sum _{k=\mathrm{1}}^{n-\mathrm{1}}}(d_{i,k}-d_{i^{\text{'}},k}+a_{i,k+\mathrm{1}}-a_{i^{\text{'}},k+\mathrm{1}})m_{k,k+\mathrm{1}}/\mathrm{2}\forall f(i^{\text{'}}),f(i)\in L_{\mathrm{b}}（11）

\begin{array}{l}{s}_{\mathrm{1}}\left(f(i^{\text{'}})\right)={\displaystyle \sum _{k=\mathrm{1}}^{n-\mathrm{1}}}(d_{i^{\text{'}},k}-t_d+a_{i^{\text{'}},k+\mathrm{1}}-t_d)m_{k,k+\mathrm{1}}/\mathrm{2}\\ \forall f(i^{\text{'}})\in L_{\mathrm{b}}\end{array}（12）

\begin{array}{l}{s}_{\mathrm{2}}\left(f(i)\right)={\displaystyle \sum _{k=\mathrm{1}}^{n-\mathrm{1}}}(t_a-d_{i,k}+t_a-a_{i,k+\mathrm{1}})m_{k,k+\mathrm{1}}/\mathrm{2}\\ \forall f(i)\in L_{\mathrm{b}}\end{array}（13）

式中：t_{\mathrm{a}}为运行图终止时刻。

2.3.2 有越行情况

有越行情况下列车运行线时空资源占用情况如图8所示。图中，列车i_{\mathrm{1}}，i_{\mathrm{2}}，i_{\mathrm{3}}和i_{\mathrm{4}}依次从车站\mathrm{E}出发，途径车站\mathrm{D}，\mathrm{C}，\mathrm{B}，到达车站\mathrm{A}，其中列车i_{\mathrm{3}}的运行速度高于其余列车，为避免能力损失，安排其在车站\mathrm{C}越行列车i_{\mathrm{2}}。

利用线群组合的方法将待避列车i_{\mathrm{2}}和越行列车i_{\mathrm{3}}视为一个列车越行组合I_l，在节点路由问题中将其映射为特殊节点l。

I_l与后续列车i_{\mathrm{4}}运行线间的时空资源占用量s\left(l,f(i_{\mathrm{4}})\right)、I_l与前行列车i_{\mathrm{1}}运行线间的时空资源占用量s\left(f(i_{\mathrm{1}}),l\right)分别为

\begin{array}{l}s\left(l,f(i_{\mathrm{4}})\right)={\displaystyle \sum _{k=\mathrm{1}}^{n-\mathrm{1}}}\left(d_{i_{\mathrm{4}},k}-\underset{i^{\text{'}}\in I_l}{\mathrm{m}\mathrm{a}\mathrm{x}}(d_{i^{\text{'}},k})+a_{i_{\mathrm{4}},k+\mathrm{1}}-\right.\\ \left.\underset{i^{\text{'}}\in I_l}{\mathrm{m}\mathrm{a}\mathrm{x}}\left(a_{i^{\text{'}},k+\mathrm{1}}\right)\right)m_{k,k+\mathrm{1}}/\mathrm{2}\forall f(i_{\mathrm{4}})\in L_{\mathrm{b}},\forall l\in L_{\mathrm{o}}\end{array}（14）

\begin{array}{l}s\left(f(i_{\mathrm{1}}),l\right)={\displaystyle \sum _{k=\mathrm{1}}^{n-\mathrm{1}}}\left(\underset{i^{\text{'}}\in I_l}{\mathrm{m}\mathrm{i}\mathrm{n}}(d_{i^{\text{'}},k})-d_{i_{\mathrm{1}},k}+\underset{i^{\text{'}}\in I_l}{\mathrm{m}\mathrm{i}\mathrm{n}}(a_{i^{\text{'}},k+\mathrm{1}})-\right.\\ \left.\underset{}{a_{i_{\mathrm{1}},k+\mathrm{1}}}\right)m_{k,k+\mathrm{1}}/\mathrm{2}\forall f(i_{\mathrm{1}})\in L_{\mathrm{b}},\forall l\in L_{\mathrm{o}}\end{array}（15）

I_l与列车运行图左侧和右侧边界线之间的时空资源占用量s_{\mathrm{1}}(l)和s_{\mathrm{2}}(l)分别为

s_{\mathrm{1}}(l)={\displaystyle \sum _{k=\mathrm{1}}^{n-\mathrm{1}}}\left(\underset{i\in I_l}{\mathrm{m}\mathrm{i}\mathrm{n}}(d_{i,k})-t_{\mathrm{d}}+\underset{i\in I_l}{\mathrm{m}\mathrm{i}\mathrm{n}}(a_{i,k+\mathrm{1}})-\right.\left.\underset{}{t_{\mathrm{d}}}\right)m_{k,k+\mathrm{1}}/\mathrm{2}\forall l\in L_{\mathrm{o}}（16）

s_{\mathrm{2}}(l)={\displaystyle \sum _{k=\mathrm{1}}^{n-\mathrm{1}}}\left(t_{\mathrm{a}}-\underset{i\in I_l}{\mathrm{m}\mathrm{a}\mathrm{x}}(d_{i,k})+t_{\mathrm{a}}-\right.\left.\underset{i\in I_l}{\mathrm{m}\mathrm{a}\mathrm{x}}(a_{i,k+\mathrm{1}})\right)m_{k,k+\mathrm{1}}/\mathrm{2}\forall l\in L_{\mathrm{o}}（17）

I_l与I_{l^{\text{'}}}之间的时空资源占用量s(l,l^{\text{'}})为

\begin{array}{l}s(l,l^{\text{'}})={\displaystyle \sum _{k=\mathrm{1}}^{n-\mathrm{1}}}\left(\underset{i^{\text{'}}\in I_{l^{\text{'}}}}{\mathrm{m}\mathrm{i}\mathrm{n}}(d_{i^{\text{'}},k})\right.-\underset{i\in I_l}{\mathrm{m}\mathrm{a}\mathrm{x}}(d_{i,k})+\underset{i^{\text{'}}\in I_{l^{\text{'}}}}{\mathrm{m}\mathrm{i}\mathrm{n}}(a_{i^{\text{'}},k+\mathrm{1}})-\\ \left.\underset{i\in I_l}{\mathrm{m}\mathrm{a}\mathrm{x}}(a_{i,k+\mathrm{1}})\right)m_{k,k+\mathrm{1}}/\mathrm{2}\forall l,l^{\text{'}}\in L_{\mathrm{o}}\end{array}（18）

分别以式（11）—式（18）设置的各类型时空资源占用量最小化为目标函数，以式（4）为运行时间约束，式（5）和式（6）为间隔时间约束，式（7）为停站时间约束，式（9）和式（10）为越行组合到发时间间隔约束，构建有向弧权重计算模型。

2.4　列车运行线次序优化

2.4.1 建模原理

节点路由问题中的节点、有向弧及弧权重分别对应列车运行线次序优化问题中的列车运行线、运行线邻近关系及时空资源占用量。具体而言，节点被路由等价于列车运行线被铺画，节点路由次序直接决定列车运行线铺画次序，所有被路由的有向弧权重之和等于相应次序下列车运行线占用运行图的时空资源总量。节点路由问题与列车运行线次序优化问题的要素对比如图9所示。其中，弧权重的核心作用是约束时空资源消耗，要求所选有向弧的权重总和不得超过运行图时空资源总量，否则将导致末班列车终到时刻超出运行图终止时刻。

2.4.2 目标函数

模型的目标是使被路由的节点数量最大化，即尽可能增加列车运行图中被铺画的列车运行线数量。在目标函数z_{\mathrm{2}}中采用差异化权重设置策略：对于普通单列车节点，统一赋予权重1；对于包含w列列车的越行组合节点，则赋予权重w。通过这种权重设置方式，确保目标函数值精确等价于被铺画运行线的总数，z_{\mathrm{2}}的表达式为

z_{\mathrm{2}}=\mathrm{m}\mathrm{a}\mathrm{x}\left(\sum _{l\in L_{\mathrm{b}}}{x}_l+w\sum _{l\in L_{\mathrm{o}}}{x}_l\right)（19）

式中：x_l为二进制决策变量，表征节点l的路由状态，若节点被路由，其取值为1，否则取值为0。

2.4.3 约束条件

（1）流平衡约束：对于除路由起点或终点之外的任意节点，从该节点发出的有向弧数量之和为1，同时指向该节点的有向弧数量之和也为1，该约束可表示为

\sum _{l^{\text{'}}\in L}c(l,l^{\text{'}})=x_l-x_l^{″}\forall l\in L（20）

\sum _{l^{\text{'}}\in L}c(l^{\text{'}},l)=x_l-x_l^{\text{'}}\forall l\in L（21）

式中：c(l,l^{\text{'}})为弧选择变量，当节点l和l^{\text{'}}之间的有向弧被选择时，其取值为1，否则取值为0；x_l^{″}为终节点指示变量，当节点l为路由终点时，其取值为1，否则取值为0；x_l^{\text{'}}为始节点指示变量，当节点l为路由起点时，其取值为1，否则取值为0。

（2）有向弧选择约束：对于任意有向弧c(l^{\text{'}},l)，当其被选中时，须保证节点l的顺序编号比节点l^{\text{'}}的顺序编号大1，否则，两节点的顺序编号不受此弧影响。该约束可表示为

(v_l-v_{l^{\text{'}}}-\mathrm{1})c(l^{\text{'}},l)=\mathrm{0}\forall l,l^{\text{'}}\in L（22）

式中：v_l为节点l的路由次序。

（3）节点路由次序约束：节点l的路由次序v_l的计算方法可表示为

v_l=\sum _{j\in J}{\lambda }_l^{j}j\forall l\in L（23）

式中：{\lambda }_l^j表示节点l的路由次序是否为j，是为1，否为0。

（4）节点路由次序编号唯一约束：对于任意被路由节点l，其次序编号唯一，该约束表示为

\sum _{j\in J}{\lambda }_l^j=x_l\forall l\in L（24）

（5）节点路由次序变化范围约束：子集L_r和L_{r+\mathrm{1}}之间至多有1条有向弧相连接；若L_r中包含路由终点，那么它和L_{r+\mathrm{1}}之间无有向弧相连接；L_r与相邻子集L_{r-\mathrm{1}}，L_r，L_{r+\mathrm{1}}之间可连接，除此之外与其他非相邻子集均无有向弧相连接；若L_{r+\mathrm{1}}中的某个节点被路由，那么L_r中的所有节点均被路由。该约束可表示为

\sum _{l\in L_r}\sum _{l^{\text{'}}\in L_{r+\mathrm{1}}}c(l,l^{\text{'}})+\sum _{l\in L_r}{x}_l^{″}\le \mathrm{1}\forall r\in R（25）

\sum _{l\in L_r}\sum _{l^{\text{'}}\notin L_{r-\mathrm{1},}{L}_r,L_{r+\mathrm{1}}}c(l,l^{\text{'}})=\mathrm{0}\forall r\in R（26）

M{x}_l\ge \sum _{l^{\text{'}}\in L_{r+\mathrm{1}}}{x}_{l^{\text{'}}}\forall l\in L_r,\forall r\in R（27）

式中：M为1个极大的正数。

（6）时空资源总量约束：被占用的时空资源总量不大于运行图所包含的时空资源总量S，该约束可表示为

\begin{array}{l}\sum _{l^{\text{'}}\in L}\sum _{l\in L}s(l,l^{\text{'}})c(l,l^{\text{'}})+\sum _{l\in L}{s}_{\mathrm{1}}(l)x_l^{\text{'}}+\sum _{l\in L}{s}_{\mathrm{2}}(l)x_l^{″}+\\ \sum _{l\in L_o}{s}_{\mathrm{3}}(l)x_l\le S\end{array}（28）

2.4.4 模型求解

将非线性约束条件式（22）进行线性化处理，可转化为

v_l-v_{l^{\text{'}}}\ge c(l^{\text{'}},l)-M\left(\mathrm{1}-c(l^{\text{'}},l)\right)\forall l,l^{\text{'}}\in L（29）

v_l-v_{l^{\text{'}}}-\mathrm{1}\le M\left(\mathrm{1}-c(l^{\text{'}},l)\right)\forall l,l^{\text{'}}\in L（30）

使用Gurobi求解器求解得到最佳节点路由次序后，通过映射f:I\to L将节点路由次序转化为列车运行线次序。

2.5　列车运行图编制

基于上述优化得到的列车运行线铺画次序，以列车终到时间之和最小化为目标，构建运行图编制模型。其目标函数z_{\mathrm{3}}和约束条件如下。

z_{\mathrm{3}}=\mathrm{m}\mathrm{i}\mathrm{n}\sum _{i\in I}{a}_{i,n}（31）

s.t.

a_{i,k}\le t_{\mathrm{a}}\forall i\in I,\forall k\in K（32）

d_{i,k}\ge t_{\mathrm{d}}\forall i\in I,\forall k\in K（33）

a_{i,k}\ge a_{i^{\text{'}},k}c\left(f(i^{\text{'}}),f(i)\right)\forall i\in I,\forall k\in K（34）

该模型以式（4）为运行时间约束、式（5）和式（6）为间隔时间约束、式（7）为停站时间约束、式（9）和式（10）为越行约束，并添加式（32）和式（33）为运行图时段范围约束、式（34）为运行线次序约束。

3 案例验证

3.1　案例介绍

京沪高铁运输能力紧张，其中南京南站—上海虹桥站区段的运行图冗余度极低。以该区段为例，验证所提模型和算法在提升运输能力利用率方面的可行性与有效性。该区段同时运行350 km · h^－1和300 km · h^－1两种速度等级的高速列车，其在各区间的纯运行时间差异见表1。

基于列车运行图技术资料，设定模型参数见表2。通过分析不同越行组合对时空资源利用效率的影响，将该案例下的列车越行组合内的列车数量w定为3列，并将300 km · h^－1和350 km · h^－1高速列车分别定义为低等级和高等级高速列车。

2023年9月11：00—17：00内的列车运行图如图10所示，该时段内的区段通过能力为38列。图中，各列车均采用数字编号标注于运行线上，横线表示区间中心站位置。区间间隔按速度为300 km · h^－1的一站直达列车的区间运行时分比例确定，橙色运行线表示列车越行组合。该时段共开行5列350 km · h^－1和33列300 km · h^－1的高速列车。由图10可知：该段高速铁路列车运行图冗余度极低，无法插入新的运行线；列车待避次数较多，导致平均旅行时间增至84.9 min。以该时段内既有的38列列车和新增的12列列车（停站方案和开行时段已确定，新增列车均安排在既有列车之后），组成列车集合I。

3.2　结果分析

采用所提优化方法编制的运行图在实施过程中，首先划分列车子集合L_r，设定L_r中的列车数量为8列，每一子集内的列车大致对应于每1 h内的列车。为确保列车开行方案与客流需求在时间维度上的匹配性，算法约束列车次序调整仅在各子集合内部进行。

该方法能够在给定越行组合和运行线次序调整范围的约束条件下，精确求解出包含最大列车数量的最优时刻表方案，其生成的列车运行图如图11所示。由图11可知：优化后的运行图区段通过能力提升至40列，较原始运行图增加2列；运行线排列较为紧凑，可有效提升时空资源利用率；列车平均旅行时间降至82.2 min，较优化前减少2.7 min。这充分验证了所提方法在提升高速铁路通过能力和运行效率方面的有效性。

3.3　灵敏度分析

为系统研究列车运行线次序调整范围及越行组合规模对区段通过能力的影响规律，设计多组对比试验。首先，将子集合规模分别设置为8，16和50列，分别对应1 h，2 h和全日（6 h）运行时段，考察不同时间尺度的次序调整对通过能力的影响。其次，针对越行组合的影响，设计无列车越行、有列车越行（w=\mathrm{2}）和有列车越行（w=\mathrm{3}）3种方案。所有试验均保持相同的停站方案和运行时分标准以确保结果可比性。灵敏度分析试验结果见表3。由表3可知：随着列车运行线次序调整范围的扩大，区段通过能力增加明显；在子集合内列车数量固定的情况下，无越行方案的通过能力普遍优于有越行方案，这主要得益于节点路由算法采用“先快后慢、递远递停”的列车排序方式，通过优化列流组织有效避免了列车冲突，从而消除了越行需求，此外，由于该区段距离较短且不同等级车速差异有限，越行作业反而会导致一定程度的能力损失；随着列车越行组合中列车数量的增大，因待避作业次数增多，平均旅行时间相应延长。

包含50列列车且无越行作业的优化运行图结果如图12所示。由图12可知：该运行图时空资源利用率显著提升，主要体现在“递远递停”的列车排布方式（即较早停站的列车安排较晚发车），有效避免了前车制约后车的现象（如列车编号为10，26，2和3）；采用停站方案相似的列车成组追踪运行模式（如编号为17和45等7列列车在常州北—上海虹桥区段），可大幅减少运行线间的缓冲时间。然而，这种优化模式也存在明显局限：列流和客流的时空分布匹配度下降；短时间内相继发出的列车停站结构趋同。因此，在实际应用中，必须合理约束运行线次序的调整范围，在提升通过能力与保障客运服务质量之间寻求平衡。

4 结 语

本研究将高速铁路列车运行线次序优化问题建模为节点路由问题，提出了基于节点路由的列车运行线次序优化方法。通过重构列车发车次序提升时空资源利用效率，在不改变既有列车开行方案的前提下提高能力利用水平。该方法在提高区段通过能力的同时，可减少时空资源占用，且随着列车运行线次序变化范围的扩大，能力提升效果愈加显著。此外，该方法实施难度低，为人工调图提供了有效的加车优化方案，特别适用于既有高速铁路的能力挖潜。

未来研究方向主要包括2个方面：第一，突破现有城际铁路和高速干线繁忙区段的限制，深入探索高速铁路列车越行、长短途列车混跑和列车跨线等复杂场景下的时空资源占用规律及量化方法，并发展从区段优化到全网络扩展的衔接技术；第二，研究不同越行方案对区段通过能力的影响规律，进一步完善高速铁路列车运行优化理论体系，并为复杂条件下的运输能力提升提供新的方法支撑。

参考文献

[1] YAGHINI M， SARMADI M， NIKOO N， et al. Capacity Consumption Analysis Using Heuristic Solution Method for under Construction Railway Routes ［J］. Networks and Spatial Economics， 2014， 14 （3/4）： 317-333.

[2] 张守帅.高速铁路通过能力计算方法研究［D］.成都：西南交通大学，2014.

[3] ZHANG Shoushuai. Study on Calculation Method of High Speed Railway’s Passing Capacity ［D］. Chengdu： Southwest Jiaotong University， 2014. in Chinese

[4] 王高磊.基于列车运行图压缩加密的铁路通过能力计算方法研究［D］.北京：中国铁道科学研究院，2019.

[5] WANG Gaolei. Research on Calculation Method of Railway Passing Capacity Based on Train Working Diagram Compression and Encryption ［D］. Beijing： China Academy of Railway Sciences， 2019. in Chinese

[6] CACCHIANI V， CAPRARA A， TOTH P. Scheduling Extra Freight Trains on Railway Networks ［J］. Transportation Research Part B： Methodological， 2010， 44 （2）： 215-231.

[7] 高如虎，牛惠民，江雨星.基于多维网络的增开列车条件下高速铁路列车运行图调整［J］.铁道学报，2020，42（5）：1-8.

[8] GAO Ruhu， NIU Huimin， JIANG Yuxing. Train Timetable Rescheduling Based on a Time-Station-Track Multi-Dimensional Network under Condition of Running Extra Trains for High-Speed Railway ［J］. Journal of the China Railway Society， 2020， 42 （5）： 1-8. in Chinese

[9] 曲云腾，姚向明，赵鹏，等.考虑动车组接续的区域城际网运行图加线模型［J］.铁道学报，2024，46（1）：13-21.

[10] QU Yunteng， YAO Xiangming， ZHAO Peng， et al. Model for Inserting Additional Trains into Existing Timetable for Intercity Railway Network Considering EMU Connections ［J］. Journal of the China Railway Society， 2024， 46 （1）： 13-21. in Chinese

[11] 路超，周磊山，陈然.最大通过能力下高速铁路运行图优化研究［J］.铁道科学与工程学报，2018，15（11）：2746-2754.

[12] LU Chao， ZHOU Leishan， CHEN Ran. Optimization of High-Speed Railway Timetabling Based on Maximum Utilization of Railway Capacity ［J］. Journal of Railway Science and Engineering， 2018， 15 （11）： 2746-2754. in Chinese

[13] BEŠINOVIĆ N， QUAGLIETTA E， GOVERDE R M P. Resolving Instability in Railway Timetabling Problems ［J］. EURO Journal on Transportation and Logistics， 2019， 8 （5）： 833-861.

[14] 王宇强，魏玉光，商攀 等.考虑跨线列车的高速铁路能力最大化合理利用研究［J］.铁道学报，2020，42（10）：23-29.

[15] WANG Yuqiang， WEI Yuguang， SHANG Pan， et al. Research on Maximum Reasonable Utilization of High-Speed Railway Capacity Considering off-Line Trains ［J］. Journal of the China Railway Society， 2020， 42 （10）： 23-29. in Chinese

[16] 周文梁.客运专线网络列车开行方案与运行图综合优化模型及算法［D］.长沙：中南大学，2010.

[17] ZHOU Wenliang. Integrated Optimization Model and Algorithm of Train Plan and Diagram on Dedicated Passenger Network ［D］. Changsha： Central South University， 2010. in Chinese

[18] 邹信诚.高速铁路列车开行方案和运行图一体化优化方法研究［D］.北京：北京交通大学，2023.

[19] ZOU Xincheng. Research on the Integrated Optimization Method of High-Speed Railway Line Plan and Train Timetable ［D］. Beijing： Beijing Jiaotong University， 2023. in Chinese

[20] JAMILI A， SHAFIA M A， SADJADI S J， et al. Solving a Periodic Single-Track Train Timetabling Problem by an Efficient Hybrid Algorithm ［J］. Engineering Applications of Artificial Intelligence， 2012， 25 （4）：793-800.

[21] JENSEN L W， LANDEX A， NIELSEN O A， et al. Strategic Assessment of Capacity Consumption in Railway Networks： Framework and Model ［J］. Transportation Research Part C： Emerging Technologies， 2017， 74： 126-149.

[22] JENSEN L W， SCHMIDT M， NIELSEN O A. Determination of Infrastructure Capacity in Railway Networks without the Need for a Fixed Timetable ［J］. Transportation Research Part C： Emerging Technologies， 2020， 119： 102751.

[23] 聂磊，张渊，武鑫.计算机编制周期性列车运行图关键技术［J］.中国铁道科学，2014，35（1）：114-121.

[24] NIE Lei， ZHANG Yuan， WU Xin. Key Technologies for Computer Generation of Cyclic Train Timetable ［J］. China Railway Science， 2014， 35 （1）： 114-121. in Chinese

[25] 白紫熙，邵静静，周磊山，等.相同径路的高速列车运行图编制方法［J］.中国铁道科学，2015，36（6）：135-140.

[26] BAI Zixi， SHAO Jingjing， ZHOU Leishan， et al. Drawing Method for Working Diagram of High Speed Train with Same Path ［J］. China Railway Science， 2015， 36 （6）： 135-140. in Chinese

[27] 索雷.面向城市轨道交通自组织网络的多路径路由技术研究［D］.北京：北京交通大学，2023.

[28] SUO Lei. Research on Multipath Routing Technology for Urban Rail Ad Hoc Network ［D］. Beijing： Beijing Jiaotong University， 2023. in Chinese

[29] 李翠然，王雪洁，谢健骊，等.基于改进PSO的铁路监测线性无线传感器网络路由算法［J］.通信学报，2022，43（5）：155-165.

[30] LI Cuiran， WANG Xuejie， XIE Jianli， et al. Routing Algorithm for Railway Monitoring Linear WSN Based on Improved PSO ［J］. Journal on Communications， 2022， 43 （5）： 155-165. in Chinese

[31] 周明玺，郑平标，秦胜.考虑技术站编组去向的车流径路优化研究［J］.铁道运输与经济，2024，46（3）：17-28，64.

[32] ZHOU Mingxi， ZHENG Pingbiao， QIN Sheng. Traffic Routing Optimization Considering Train Destinations of Technical Stations ［J］. Railway Transport and Economy， 2024， 46 （3）： 17-28， 64. in Chinese

[33] 赵伊楠，林柏梁.需求不确定的铁路车流径路优化模型［J］.中国铁道科学，2024，45（1）：190-202.

[34] ZHAO Yinan， LIN Boliang. Optimization Model of Railway Wagon Flow Path with Uncertain Demand ［J］. China Railway Science， 2024， 45 （1）： 190-202. in Chinese

基金资助

中央高校基本科研业务费专项资金资助项目(2022JBQY006)