考虑多种资源约束的城际铁路运输能力计算方法

廖正文，李海鹰，王 莹，苗建瑞

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

铁路运输能力既取决于固定设备的配置数量和结构，又取决于活动设备(或称移动设备)的配属，还取决于固定设备与活动设备的相互适配[1]。传统的运输能力通常采用通过能力和输送能力两种概念。通过能力仅取决于固定设备设置条件，而输送能力还需要考虑与活动设备相关的多种运输资源配置条件。城际铁路一般采用动车组独立配属的活动设备配置方法，是以动车组立即折返实现公交化的运输组织模式[2]，具有发车密度大、运行距离短、固定设备资源利用率高等特点。在这种资源配置和运用方式下，活动设备和固定设备之间存在较强的制约关系。若不考虑动车组数量和运用约束，仅基于固定设备配置计算通过能力，很可能高估了实际可能运行的列车数量，难以用于实际运营决策。因此，有必要将动车组这类采购周期长且价格昂贵的活动资源纳入城际铁路运输能力研究的范围。本文研究的“城际铁路运输能力”是在一定的固定设备、动车组类型和行车组织方法条件下，利用一定数量的动车组，在单位时间(一昼夜)内最多能够开行的列车数量。该运输能力除了考虑固定设备资源的制约外，还将“输送能力”定义中关于活动设备的动车组数量因素考虑在内，突破了“通过能力”的研究范畴，是面向城际铁路运营特点的一种用于衡量区间、车站到发线与动车组等多种资源约束下的运输能力。

国内外关于铁路运输能力的研究以通过能力为主。为了使通过能力计算简便易行，忽略部分复杂的影响因素，简化了计算条件。一些研究为克服既有方法的弊端，改进了分析计算法，以得到更符合实际的通过能力[3-7]。部分学者利用优化方法模拟编制列车运行图、车站作业计划等计算通过能力[8-12]。在欧洲的铁路运输能力研究中，列车运行图压缩法是用于计算铁路运输能力利用饱和度的常用方法，如文献[13]。由于固定设备建设成本高，投产周期长，是运输能力研究主要关注的对象，国内的研究普遍未将活动设备的运用对运输能力的影响考虑在内，忽略了固定设备与活动设备的适配关系，难以准确地反映实际运输能力。本文针对城际铁路运输能力受多种资源相互制约的问题，以动车组数量为约束，考虑动车组运用与运行图、车站股道运用间相互制约关系，提出一种针对城际铁路运输能力的计算方法，可计算得到更准确的运输能力，以支撑运营决策。

1 城际铁路运输能力计算模型

根据上述城际铁路运输能力的定义，本文研究的城际运输能力计算问题是在给定铁路网拓扑、运行图标尺和追踪间隔时间、车站股道占用间隔时间、动车组数量、立即折返最小接续时间等条件下，计算当前城际铁路区段一昼夜内各方向最多可以开行的列车总数。为此，给出一种向基本运行图中循环插入虚拟列车，直至获得满表运行图的城际铁路运输能力计算方法。该方法以给定的基本运行图为框架，以运行图铺画规则、股道运用规则与动车组运用规则为约束条件。根据涉及的运输资源类别，城际铁路运输能力计算问题可进一步划分为列车运行图、动车组运用和车站股道分配3个子问题，三者之间存在关联关系。本节运用数学模型刻画三者对运输能力的影响及其相互关联关系。

1.1 符号说明

1.2 列车运行图子问题

列车运行图子问题的主要决策变量是列车在各车站的到达和出发时刻。从运输能力利用的角度看，列车运行图的铺画是对铁路区间时空资源的分配。本文使用以下约束条件表示列车运行图问题变量间的关联关系

(1)

∀f∈F*e∈Πf

(2)

(3)

(4)

∀f∈F*f′∈F*-fs∈Γf∩Γf′

(5)

(6)

∀f∈F*f′∈F*-fe∈Πf∩Πf′

(7)

∀f∈F*f′∈F*-fe∈Πf∩Πf′

(8)

1.3 动车组运用子问题

动车组运用子问题的关键在于确定折返列车间的衔接关系，在数学上是一个0-1指派问题，是对有限的活动设备资源的时空调拨与分配。以下是动车组接续关系的基本约束。

(9)

(10)

∀s∈Γf∈F*f′∈F*:ω(f)=δ(f′)=s

(11)

图1 动车组接续条件示意图

1.4 车站股道分配子问题

车站股道分配子问题的决策内容是列车在各车站的股道选择，保证股道占用不冲突，是对车站股道这一时空资源进行优化分配。股道分配问题的基本约束为

(12)

(13)

式(12)、式(13)表示列车股道选择的唯一性约束，列车若在当前车站停站，则须选择具备乘降条件的股道停站，否则须选择正线股道通过。股道的占用与列车的到达和出发时刻、动车组的接续关系有密切的关联，约束条件为

(14)

式(14)表示中间站股道的占用间隔时间约束，即当两列车均选用同一股道k时，后行列车须在前行列车离开若干时间后才允许进入该股道，如图2中的f1与f3。

ω(f)=δ(f′)=sk∈Ks

(15)

ω(f)=δ(f′)=sk∈Ks

(16)

(17)

图2 股道分配时间条件示意图

1.5 城际铁路运输能力计算一体化模型

由列车运行图、动车组运用、车站股道分配3个子问题的数学模型可知，上述3个子问题共用部分决策变量。这些共用的决策变量是子问题间互相关联的纽带，体现了运输能力的组成要素间存在着相互作用、相互影响的耦合关系，运输能力影响要素互动关系示意见图3，分别为：

图3 运输能力影响要素互动关系示意图

耦合关系1：列车运行图与股道分配耦合关系。列车在车站的到达、出发时刻与列车进入、离开相应股道的时刻有对应关系。

耦合关系2：列车运行图与动车组运用耦合关系。具有立即折返接续关系的2列车，其前序列车的到达时刻与后序列车的出发时刻须满足动车组的接续时间标准。

耦合关系3：股道分配与动车组运用耦合关系。具有立即折返接续关系的2列车在立即折返车站必须分配在同一股道。

根据上述运输能力的影响因素及关联关系分析，可构建城际铁路运输能力计算的一体化模型P1：

max ‖F*‖

s.t.

式(1)～式(17)

FB⊆F*

(18)

F*⊆F

(19)

该模型的第1个目标函数为运输能力计算的主要目标，即尽可能多地在运行图中铺画满足约束条件的列车。其中集合F*表示入选列车集合，是决策变量。第2个目标函数为次要目标，即在满足规划列车尽可能多的条件下，令获得的运行图尽可能紧凑。式(1)～式(8)为运行图子问题约束，式(9)、式(10)为动车组接续子问题约束，式(12)、式(13)为股道分配子问题的约束。式(11)、式(14)～式(17)表示各子系统间关联关系的耦合约束。式(18)表示所有的基本图列车必须被铺画，式(19)表示入选列车须从可能被铺画的列车全集中选出。

2 运输能力计算分时段滚动压力测试算法

文献[8]提出向运行图中不断增加列车，直到无法在给定的时间内铺画所有列车为止的铁路运输能力计算“压力测试法”。本文依据该方法的基本思路，考虑车站股道分配和动车组数量约束，利用模型P1对列车运行图进行压力测试，计算城际铁路运输能力。模型P1存在约束F*⊆F，表示从列车全集中选择符合约束条件的列车进行铺画。由于运行线铺画的可能情况非常多，F*集合难以被穷举，因此在求解时采用压力测试算法，在基本运行图框架下(基本图中的运行线必须被铺画，但到发时刻可在给定范围内调整)不断加入新列车以扩充列车集合F*，最终可获得满表运行图，其中包含的列车数量‖F*‖即可视为城际铁路的运输能力。

在扩充列车集合F*时，首先依据停站方案比例，以一定的概率随机生成将要加入的列车集合FI，与已成功插入的列车合并生成待验证列车集合FQ，再使用商业求解软件求解混合整数规划模型P2验证集合FQ的可行性，若可行，则将这些虚拟列车加入集合F*，然后继续加车；若不可行，则认为当前的可行列车集合F*即包含了可被铺画的所有列车，压力测试结束。其中数学规划模型P2为

s.t.

式(1)～式(18)

式中：FQ为待验证可行性的列车集合，用以替换各约束式中的F*集合，表示测试FQ是否满足约束式(1)～式(18)。

上述数学规划模型是大规模的组合优化问题，直接计算全天的运行图存在困难。依据编图人员编制大规模列车运行图与动车组交路计划的经验，本文遵循“从前往后”顺次铺画的原则，设计了分时段滚动的求解算法。该算法设置了时间宽度为T的滚动时间窗，每次只“压力测试”求解该时间窗涉及的变量。当某时间窗求解完毕后，首先固定该时间窗内所有决策变量的值，然后平移该时间窗至下一位置继续进行“压力测试”求解，直至完成线路全天运输能力的压力测试计算，见图4。设置过长的时间窗宽度T会导致模型规模过大，商业求解软件在较短时间内得不到可行解；而设置过短的时间窗宽度T，运行图在时间维度上分割过细，可能导致全局运行图质量不佳。因此，滚动时间窗宽度T应根据问题规模和求解器的求解效率合理设置。

图4 分时段滚动压力测试求解示意图

具体实现步骤为

Step1初始化。定义滚动时间窗时间宽度为T，据此生成滚动时间窗的开始时间序列t0,t1,…,tN-1(其中N为滚动时间窗数)；定义n为时间窗的序号，令n:=0，F*(n):=∅。

Step2确定当前铺画的时间窗范围[tn,tn+1]。

Step3筛选始发站出发时间范围与当前铺画时间窗范围有重叠的基本图列车，并将其添加至当前铺画时间窗的待验证列车集合中，即

FQ(n):=F*(n-1)∪{f∈FB|[tn,tn+1]∩[Ef,lf]≠∅}

Step4在给定待验证列车集合FQ(n)的条件下，对当前时间窗进行压力测试求解：

Step4.1求解模型P2，若模型求得可行解，令F*(n):=FQ(n)；否则转跳至Step4.3；

Step4.2按照给定的概率随机生成插入的虚拟列车集合FI，令FQ(n):=FI∪FQ(n)，转跳至Step4.1；

Step4.3无列车可加入当前时间窗，获得当前时间窗的局部最优满表运行图。

Step5固定当前时间窗内已经求得的变量：

Step6若全天运行图已计算完成，输出运输能力计算结果‖F*‖及对应的运行图、股道运用方案和动车组接续方案，退出算法；否则向前平移时间窗至下一时段，即令n:=n+1，转跳至Step3继续求解。

3 算例验证

本文以京津城际铁路北京南至天津区段为例，通过对比分析考虑与不考虑动车组运用与股道分配的运输能力计算结果，说明考虑多种资源约束在运输能力计算中的必要性；通过分析动车组数量与运输能力之间的对应关系，说明在不同条件下运输能力的实际限制条件可能不同。算例分析了可行解搜索时限对运输能力计算结果的影响，验证上述模型与算法的可行性。在此暂不考虑跨线列车和北京南至于家堡长交路列车对运输能力的影响，采用的基础数据见表1。

表1 算例基础参数

算法的计算机程序利用C# (.NET Framework 4.5.1)语言编写，在1台CPU为Intel Core i7-4770 3.40 GHz，8 GB内存的台式计算机上运行，混合整数规划模型的求解引擎采用Gurobi 8.0.0。

3.1 考虑动车组运用与股道分配的运输能力计算结果

为了对比考虑动车组运用、股道分配前后运输能力计算的结果，本算例设计了3种列车加压场景，即

场景1：全部加入武清站不停站列车；

场景2：全部加入武清站停站列车；

场景3：按1∶1的比例通过随机函数产生武清站停站或武清站不停站列车。

同时，根据考虑的资源约束不同，在模型P1的基础上，通过松弛相关约束设计了4种运输能力计算模型，以此对比考虑多种影响因素的运输能力计算结果差异：

模型1：仅加压列车运行图(松弛约束式(9)～式(17))；

模型2：仅考虑中间站股道分配加压列车运行图(松弛约束式(9)～式(11)及式(15)～式(17))；

模型3：仅考虑动车组立即折返接续加压列车运行图(松弛约束式(12)～式(17))；

模型4：考虑动车组立即折返及股道分配加压列车运行图(包含所有约束)。

实验中的动车组数量按17组标准动车组给定。根据上述场景和模型划分进行交叉实验，可得运输能力计算结果，见表2。

表2 各模型在不同停站方案下的计算结果对比 列

上述结果说明了考虑动车组资源约束的运输能力计算模型的计算结果更加准确。以全部停站的方案为例，若仅考虑运行图约束计算运输能力，上下行列车数量分别为200列和208列；加入中间站股道分配约束后，列车数量变化不大，这是因为对于城际铁路而言中间站股道分配不是运输能力的制约因素；当加入动车组接续约束后，上下行列车数量分别降为155列和156列，该结果能够在一定程度上反映动车组数量影响了运行图通过能力的实现。若考虑动车组立即折返作业中股道分配冲突，上下行列车数量则进一步降为145列，该结果说明在股道资源紧张的条件下，忽略立即折返作业在股道分配冲突而仅考虑动车组接续对运输能力的影响，将会导致计算结果偏大。以上的计算结果表明，运输能力是多种资源协同运用下运输供给量的体现，采用考虑多种资源的一体化运输能力计算模型，能充分体现多种资源的制约与互动，使运输能力计算结果更加贴近实际。

3.2 动车组数量对运输能力的影响

动车组的数量和配属是运输能力的重要影响因素。算例通过对动车组数量进行加压，研究动车组数量对运输能力的影响。各方案除了提供的动车组数量有所差异以外，其他的参数设置完全相同，以相等的比例插入在武清站停站或不停站的列车，并统计在不同动车组数量供给的情况下开行的列车数量及始发终到车站的股道占用率，以分析动车组数量与运输能力之间的规律。

当动车组数量较少时，动车组数量是运输能力的决定因素，而区间通过能力相对较为富余，列车的数量与动车组数量呈近似线性的关系，见图5。当动车组数量较多时(多于16组)，区间通过能力开始成为运输能力的制约因素。当动车组数量大于22组时，列车数量不再随动车组数量的增加而增加，此时线路和车站的通过能力是整体运输能力的决定因素，无法通过投入更多的动车组以提升运输能力。

图5 动车数量与列车数量关系折线图

随着动车组数量的增加，动车组的折返需占用更多的股道资源，因此始发终到车站的股道占用率也随之增加，见图6。但动车组数量增加到一定程度后，每条动车交路长度变短，动车组在执行完几个列车任务后即迅速入段，不在终到车站产生过长时间的停留，因此股道的占用率呈不变或下降趋势。

图6 动车数量与车站股道占用率关系折线图

3.3 可行解搜索时限对结果的影响

在实际求解当中，求解器判别部分比较复杂的列车集合的可行性需要耗费大量计算时间。由于压力测试的目的是为了获得可行解而并非最优解，对解的优化质量要求相对较低，因此为了提升压力测试的效率，在前述实验中为每次求解设定了搜索可行解的时间限制为60 s(到达该时间限制尚未搜索到可行解则认为当前输入无可行解)。进一步地，研究了单次最大求解时间的设置对求解效率和求解质量的影响，见表3。

表3 单次最大求解时限对压力测试求解质量的影响

实验数据说明，单次求解时间会影响压力测试计算的质量。当单次求解时间限制较短时，可以在较快时间内获得运输能力计算结果，但结果的优化程度较低。随着单次求解时间长度的增加，运输能力计算压力测试的结果逐步趋于稳定，说明适当扩大单次最大求解时间有利于提升压力测试结果的质量。但是，过大的单次最大求解时间对结果质量提升意义不大，反而延缓了计算进度。综合权衡求解计算时间和求解质量，本案例将单次搜索时限设置为40 s较为合理。

4 结论

论文提出了针对城际铁路的考虑多种资源协同运用的运输能力计算方法。提出了考虑运行图、股道分配、动车组接续的运输能力计算数学模型，以及针对运营全日的运输能力计算分时段滚动压力测试算法。算例对比分析了求解参数设置对运输能力计算结果的影响，可用于分析不同运营参数条件下的运输能力。算例表明，相比于只考虑运行图的通过能力计算结果，考虑股道运用与动车组接续的运输能力计算结果能够更加准确地反映运营的实际运输能力利用情况，能识别特定场景下运输能力的决定性因素，对运行图、动车组运用计划编制等工作更具有指导意义。未来的研究可考虑将其他运输能力的影响因素(如车站进路冲突等)纳入本论文构建的多种资源协同运用框架中，完善和丰富本论文提出的运输能力计算方法。