城际铁路动车组交路计划优化模型

李　健，王　莹，李海鹰，张哲铭

(1. 北京交通大学 交通运输学院，北京 100044；2. 北京交通大学 轨道交通控制与安全国家重点实验室，北京 100044)

至2016年9月我国已建成并运行包括京津、沪宁、沪杭城际等在内共 20条城际铁路，据十三五规划纲要中的《中长期铁路网规划》，未来我国城际铁路系统建设规模将继续扩大。为了降低铁路部门的运营成本，动车组作为高速铁路和城际铁路的主要运载工具，其运用优化一直是国内外学者不断研究的问题。目前，国外学者对动车组交路计划的研究主要集中在考虑多车种、列车摘解与重联等不同的约束条件和不同的优化目标建立数学优化模型，多采用CPLEX等商业化软件、分支定界等确定性算法进行求解。其中，以Arianna等[1−4]为代表对此展开了大量的研究[1-4]。国内学者主要将动车组运用问题转化成指派和(多)旅行商 2类问题。前者均不考虑检修约束，后者主要考虑动车组一级检修约束，个别学者还考虑了二级检修约束。由于我国路网和列车开行数量规模较大，因此在求解时常采用启发式算法，包括基于概率的局域搜索算法、蚁群算法、模拟退火算法、遗传算法以及大规模邻域搜索算法[5−8]，也有学者采用列生成法等精确算法求解[9]。其中，接续网络[10−12]被广泛用于刻画运行线间的关系，并基于此进行建模和求解。然而，由于城际铁路列车开行密度大的特点，列车间可行接续关系多而复杂，基于接续网构建的优化模型可能因其规模较大而出现求解效率低下的情况。因此，本文引入时间轴线网络[13]建立城际铁路动车组交路计划的优化模型，以期更为快速、高效地求解该问题。在构建动车组运用网络时，接续网将运输任务即列车运行线以一个超节点表示，在时间和空间上均满足接续条件的任意两运输任务节点间均建立一条可行接续弧，而时间轴线网则是将列车运行线以一个始发节点和一个终到节点表示，在同一站点的相邻节点间建立时间轴线连线。图1(a)和图1(b)分别为接续网络和时间轴线网络 2种表示方法的简单示意图，2图中均包含3对即6条列车运行线1，2，3，…，6。图1(a)接续网络中a，b，c…，i为满足列车间可行接续的接续弧，而图 1(b)时间轴线网络中a，b…，e为同一站点相邻节点间建立的时间轴线连接弧, 弧的规模有所降低。此外，在动车组车底接续关系表示方法上两者也存在差异，接续网中单独的一条接续弧即可表示动车组车底的接续关系, 而时间轴线网中的动车组车底接续关系一般需要多条连接弧组合在一起才能表示。

图1　接续网络和时间轴线网络示意图对比Fig.1　Comparison of schematic diagrams between connection network and time-line network

1　城际铁路的列车开行模式和特点

作为我国铁路快速客运网的重要组成部分，城际铁路主要服务于经济发达、人口稠密的都市圈和城市带之间，承担区域内或2个城市间的短途客流。总结我国实际运营的城际铁路列车开行模式及特点主要有：

1) 城际铁路上通常只开行本线运输的高速动车组列车；

2) 列车开行具有高频率、短运距、短发车间隔的公交化运营特点，列车开行密度大。

这种列车开行模式不仅提高了城际铁路线路能力的利用率，也使得旅客出行有了更多的选择，使旅客的出行更为方便、快捷。以京津城际为例，北京南−天津的全程直达运行时间为30 min左右，实际平日开行列车达 172列，最小发车间隔仅 5 min，其他时段间隔不超过25 min，公交化运营特点明显。

针对城际铁路的列车开行模式和特点，时间轴线网因其建弧和建网方法的不同，能够有效降低弧的数量和网络规模，更易于求解，因此本文建立了基于时间轴线网络的城际铁路动车组交路计划优化模型。

2　动车组交路计划优化模型

假设列车运行图已给定，且各动车段所的检修能力充足，以动车组使用数量最少为优化目标，考虑运行图和一级检修等约束，建立基于时间轴线网络的动车组交路计划优化模型。

2.1　时间轴线网络的构建

基于给定的列车运行图构建动车组运用的时间轴线网络G(V,A)，V为所有运行线始发、终到节点和检修基地节点的集合，A为网络中所有类型弧的集合。时间轴线网络图中横轴表示时间，纵轴表示空间即车站(包括检修基地所在站或连接站在内)，运行图中的任一列车运行线r∈R均具有 4个属性，分别表示各列车的始发车站、终到车站、始发时刻和终到时刻，时间以分钟为单位。由于列车运行图上的列车开行周期为 1 d，因此建立 1 d的时间轴线网，具体的网络构建方法如下：

1) 设 R = { r|r = 1 ,2,· · ·,m } 为所有列车运行线的集合，m为列车运行线总数，对任一列车运行线r∈R，在其始发站的始发时刻处建立始发节点，在其终到站的时刻建立终到节点，其中tc表示列车间的最小接续时间，将其取值为15 min，并建立列车弧()，定义弧的权重。记所有列车弧集合为AR，所有列od车运行线的始发、终到节点的集合为VR。

2) 对每一车站所在的时间横轴上任何相邻的2个节点i和j(i和j均可能为运行线的始发或终到节点)之间建立一条日连接弧，记弧的权重，同时建立一条从该车站末节点指向始节点的夜连接弧，弧的权重记为 t始+ 1 440-t末，其中t始和t末分别表示该车站所在时间横轴上的始节点时刻和末节点时刻。特别地，如果在某一时刻存在某一列车运行线的终到节点与另一列车运行线的始发节点重合，仍在该两点间建立一条连接弧，弧的方向为终到节点指向始发节点且记弧的权重为 0。记所有日连接弧集合为，所有夜连接弧集合为，所有连接弧集合。

3) 设所有检修基地集合为K，对每一个检修基地 k∈K，建立一对虚拟检修出、入节点 ok和 dk来代替该检修基地，所有虚拟检修出节点集合和虚拟检修入节点集合分别记为VO和VD，则所有节点集合。对任意始发车站为检修基地k所在站或连接站的列车运行线r建立检修出段弧()，表示某个动车组从检修基地k检修完出来即将上线担当运输任务。类似地，对任意终到车站为检修基地k所在站或连接站的列车运行线r′建立检修入段弧()，表示某个动车组担当完某一运输任务后回检修基地k进行检修，虚拟检修出、入段弧的建立可以将动车组回检修基地进行检修和在检修基地进行夜间驻留进行区分。记检修出、入段弧的权重均为0，所有检修出段弧集合为AO，所有检修入段弧集合为 AD，则所有弧集合。

图2为动车组运用时间轴线网络示意图，图中有8条列车运行线、3个车站和1个动车所/段，其中站A为动车所/段所在或所连接的车站，对该动车所/段我们建立一对虚拟检修出入节点 ok和 dk，并用不同线条、粗细的有向箭头来表示不同类型的弧，如图2所示。

图 2 动车组运用时间轴线网络示意图Fig.2　Schematic diagram of time-line network of train-set utilization

2.2　数学优化模型

基于2.1节构建的时间轴线网络G(V,A)，建立动车组交路计划的数学优化模型。

2.2.1符号定义

基于动车组运用时间轴线网络，定义如下符号：

P为所有交路的集合，交路数作为未知参数求解前需给其设定初值；p为P中任一条交路；为以j为起点的所有出边弧的集合；为以j为终点的所有入边弧的集合；为动车段/所 k的所有检修出段弧集合；为动车段/所 k的所有检修入段弧集合；为决策变量，表示最优解中弧(i,j)被交路p选中的次数；lij和tij分别为弧(i,j)的运行距离和运行时间；为动车组一级检修的累计运行里程标准和累计运行时间标准。

2.2.2目标函数

选取动车组交路计划优化问题中最直观常见的动车组数最少作为目标函数。由于运用动车组数等于交路段的数量，交路数等于检修出段弧数，而交路段的数量又等于交路数和夜连接弧数之和，因此将检修出段弧数与夜连接弧数之和最少作为动车组数最少的等价目标函数，如式(1)所示。

2.2.3约束条件

需考虑的约束条件如式(2)～(8)所示。

其中：式(2)为覆盖约束，表示任何一条列车弧必须被某个交路选中且只能选中一次；式(3)为守恒约束，表示对任一交路p而言，任一列车节点的出边弧数均等于其入边弧数；式(4)和(5)分别表示动车组一级检修累计运行里程和运行时间约束；式(6)和(7)为回所检修约束，表示对每个交路来说动车组只能从一个动车段/所出发，最后回到同一动车段/所进行检修；式(8)为决策变量取值约束。

3　模型求解

3.1　动车组交路数下界值的确定

模型中，列车运行线、车站与检修基地等相关参数均可根据实际案例的数据输入，而交路数作为未知参数且决策变量是一个与弧和交路均有关的二维变量，因此需预先给交路数设定一个初值，而该初值设定的合适与否将直接影响求解的结果，若值偏大则所求解不是最优解，相反若值偏小则会出现无可行解。因此，在参照式(9)动车组数量计算方法[10]基础上给交路数设定一初始下界值。

对于一个给定的列车运行图，总列车旅行时间和运行图周期是定值，将任意2列列车间的接续时间均按紧接续即最小动车组运用接续时间标准 15 min进行计算，向上取整后则可得动车组数量的下界值，另外考虑到一个交路大多由1个交路段或2个交路段组成，而交路段的数量即等于动车组数量，因此交路数的下界初值可按式(10)计算得出。

3.2　求解步骤

首先初始化动车组运用时间轴线网络，在计算确定动车组交路下界值后即可进行模型求解，通过反复调用CPLEX求解引擎和迭代不断调整参数交路数规模，直至模型第一次成功求解为止，则所得解即为最优解，具体步骤如下。

Step 1: 输入运行线、车站、动车段/所等数据，初始化动车组运用时间轴线网络；

Step 2: 计算并初始化交路规模，记交路数初始下界值为n0，调用CPLEX求解引擎求解模型；

Step 3：若模型成功求解，则所求解即为最优解，转Step 5；若求解结果为无可行解，转Step 4；

Step 4：调整交路数参数值，将该参数值增加1并重新开始求解；

Step 5：若成功求解，则所求解即为最优解，转Step 5；若仍无可行解，则转Step 4，直至模型第一次成功求解为止；

Step 6：输出最优解，算法结束。

4　算例分析

选取 4条国内已实现运营的城际铁路在 2017年3月平日的列车运行图作为算例，并基于这些算例对比分析时间轴线网模型和接续网模型[14]的求解性能。时间轴线网的构建是在Visual Studio 2013平台上使用C#编程语言实现的，求解引擎调用的是ILOG CPLEX V12.3软件，求解环境为一台CPU为Intel(R) Core(TM) i7-4770，3.40GHZ×2，4GB内存的台式计算机。

实际选作算例的各城际铁路的动车段/所、列车及车站数基本信息如表1所示。根据我国《铁路动车组运用维修规程》，动车组一级检修的累计里程标准为4 000 km，一级检修的累计运行时间标准为48 h。

针对同一案例数据，首先对比分析2种动车组运用网络模型的求解性能，见表2；图3是利用时间轴线网模型的求解结果在城际铁路1运行图基础上所勾画出的交路图，图中的交路1(1)和交路1(2)表示交路1为2 d的交路，这里的(1)和(2)分别表示交路1的第1 d交路段和第2 d交路段，其他的2 d交路类似。之后再进一步对比分析2种不同的建网方法下的弧和决策变量数以及它们随列车数量的变化关系，见图4。

表1　各城际铁路动车段/所、运行线及车站基本信息Table1　General information of corresponding depot,train path, station of each intercity railway

表2　求解性能分析Table2　Analysis of solving performance

图3　列车运行图及动车组交路图Fig.3　Train diagram and rolling stock circulation diagram

从表2和图4可得出以下结论：

1) 基于 2种动车组运用网络构建的模型在求解城际铁路动车组交路计划问题时求解效率存在较大差异。同一算例数据下，时间轴线网求解时间更短、求解效率更高，说明时间轴线网模型和求解方法可快速有效地求解城际铁路动车组交路计划。

2) 随着运行线数的增加，接续网中弧数量呈指数上升，而时间轴线网中弧数量呈线性上升。实际

上，接续网络模型中决策变量数即等于弧数，而时间轴线网模型中决策变量数为弧数与交路数的乘积，由于城际铁路运距较短，一条交路可覆盖多条列车运行线，因此在运行线规模较大时，时间轴线网络模型由于所需交路数较少而不会导致对应数学模型规模快速增加，仍能保持较高效的求解效率。

图4　弧规模和决策变量数随运行线数量变化关系Fig.4　Performance of arc size and the number of decision variables with the change of the number of train paths

5　结论

1) 基于城际铁路列车开行特点，本文通过构建动车组运用时间轴线网络建立了动车组交路计划优化模型，通过设计嵌入CPLEX求解引擎的迭代求解方法，成功实现了模型的快速求解。

2) 对比分析时间轴线网和接续网 2种动车组运用网络优化模型，算例求解结果表明：2种优化模型均能求得问题的最优解，但时间轴线网模型的求解规模较小，求解快速、求解效率较高。且随着运行线数的增加，其求解优势更加明显，成功验证了时间轴线网建网方法更适用于城际铁路这类列车开行密度大、运距短的动车组交路计划的编制和求解。

3) 随着如今我国高速铁路成网规模的扩大，作为一类典型的大规模NP-hard组合优化问题，动车组交路计划的求解变得更加复杂，鉴于能够有效降低数学规模的优点，时间轴线网仍具有较大适用性，但实际大多需要结合一些优化算法才能实现快速求解。