考虑动车组接续的列车运行图智能调整方法

周晓昭，张 琦，许 伟，王 涛，宋鹏飞

(1. 中国铁道科学研究院，北京 100081； 2. 中国铁道科学研究院 通信信号研究所，北京 100081；3. 国家铁路智能运输系统工程技术研究中心,北京 100081)

受恶劣天气、自然灾害、设备故障等原因的影响，高速铁路列车的运行将偏离图定计划，这种情况下调度系统需及时对干扰后的运行图进行有效调整，减少晚点时间，控制晚点传播范围，将受晚点影响的列车数量控制到最小，保证行车安全，提高运输效率。动车组的合理接续可以提高动车组使用效率和降低运输成本。目前已有文献对动车组的接续优化和列车运行图调整展开研究。文献[1]将动车组接续优化视为TSP问题并采用元胞蚁群算法分两阶段求解动车组定点检修和动车组接续方案。文献[2]采用协同思想，将高速铁路列车运行计划与动车组交路计划协同编制，编制基于紧交路的动车组接续方案实现动车组的高效利用。文献[3]采用蚁群算法求解所构建的动车组运用计划问题的整数规划模型，实现快速求解得到有效的动车组接续优化方案。文献[4]采用交路接续思想构建动车组接续网络，以最小化动车组担当交路的接续时间总和与最大化动车组检修前累计运行里程为目标，建立动车组运用0-1整数规划模型，求解优化方案。文献[5]运用马氏决策过程构建高速铁路列车运行调整模型，采用策略优化方法给出列车顺晚开行和越行调整等行动的最优调整方案。考虑我国高速铁路动车组运用的特点，一列动车组担当某一车次的运输任务达到终点站后会继续担当另一车次的运输任务。因此一列列车的晚点不仅会影响到线路上的后行列车，也会影响到晚点列车的接续列车。前续列车晚点会造成后续列车无法正点始发。该场景一般会发生在具有大量始发终到作业车站所在的调度区段。

本文建立考虑动车组接续的高速铁路列车运行图智能调整多目标优化模型，采用基于改进和声搜索算法对所建立的模型进行求解，以京津城际延伸线的实际列车运行数据进行实例验证。

1 动车组接续关系分析

动车组接续是一趟列车终到后在车站衔接另一趟始发列车。动车组接续是为了解决动车组车底担当不同车次的运营任务在车站的合理衔接问题，明确终到动车组车底的去向及下一运营担当的车次，始发动车组车底的来源及上一运营担当的车次。具有大量始发终到作业的车站有两种类型：一种是通过式车站，另一种是尽头式车站。通过式车站可以衔接两条或两条以上不同的线路，其正线和到发线是贯通的，在两个咽喉区能分别办理接发车作业，如天津站城际场、成都东站等。尽头式车站的到发线是尽头式的，只衔接一个方向，只有一个咽喉可以办理接发车作业，如于家堡站、峨眉山站等。

动车组在车站的接续运用通常有两种方式：一种是顺向接续，另一种是逆向接续。顺向接续是指列车从车站一端接入到发线后接续下一趟动车组列车，列车的进出站进路均不切割车站咽喉区，通常只发生在通过式车站。逆向接续是指列车从车站一端接入到发线后接续下一趟动车组列车，列车的进出站进路要纵向切割咽喉区。根据接发车进路及到发线使用的不同，逆向接续方式可再分为顺接反发和反接顺发。动车组采用逆向接续方式时，接车作业或发车作业时会纵向切割车站咽喉，这将会与其他列车的接发车进路构成冲突，当车流密度高时会降低车站的通过能力和作业效率，同时也构成了列车运行图调整时的约束条件。

动车组的接续时间由旅客乘降、司机换端、座椅调整、车厢清扫保洁、上水、吸污、送餐、货物乘降等时间组成。动车组的接续时间与旅客数量、动车组的编组形式、动车组的性能、车体结构、车站的拓扑结构、停靠站台、进出站口的位置及数量等因素有关。在动车组交路计划编制和列车开行方案编制过程中，动车组间的接续时间一般由最小交路时间和冗余时间构成。

2 考虑动车组接续的列车运行图智能调整模型

2.1 建模约定

已知开行方案基本图、动车组交路关系和车站拓扑结构。不考虑列车反向运行，不改变动车组的规定接续关系。

2.2 参数定义

式中：i为接续的前车；j为接续的后车，存在接续关系的动车组对数量为Nconn。

λstart为列车起车附加时分，λstop为列车停车附加时分，TR为列车实际到达出发时刻的m×2n矩阵。

2.3 约束条件

(1)动车组接续需发生在同一车站的同一股道。

(2)旅客列车在有旅客乘降车站(有作业的车站)的发车时间不得小于图定发车时间。

(3)存在接续关系的列车，需满足动车组最小接续时间。

(4)某动车组车底同一时刻只能担当唯一一趟列车的运输任务。

(5)区间运行时分不得小于最小区间运行时分。

(6)同向相邻列车的发车时间间隔和接车时间间隔约束。

ε取值为3 min。

(7)动车组接续对车站咽喉区占用的约束。设列车i和列车j在车站s存在接续关系，列车i为接续前车，列车j为接续后车，列车e∈Train。

(8)列车的交会和越行只能发生在车站，列车占用区间顺序的约束。

(9)列车在车站的作业时间不得小于最小作业时间[6]。

(10)车站到发线使用约束。

2.4 目标函数

(1)总晚点时间最小，提高正点率。

(2)晚点波及到的列车数量最少。

3 求解算法

列车运行调整问题属于动态的大规模组合优化问题，约束条件多且复杂，求解难度较大。本文采用改进的和声搜索算法求解考虑动车组接续的列车运行图智能调整模型。

和声搜索HS(Harmony Search)算法是2001年由GEEM Z W等人提出的一种启发式智能优化算法[7]。和声搜索算法模拟乐队演奏过程。不断调整各种乐器的音调寻找一个最美妙的和声类比于优化算法中通过不断迭代求得一个解使得目标函数最优，演奏中最美妙的和声类比于优化问题中的最优解，美学评估类比于目标函数，各种乐器的音调类比于各变量的取值，每一次的练习类比于每一次的迭代。基本和声搜索算法流程如下：

步骤1初始化算法参数。和声记忆库的规模HMS、和声记忆库取值概率HMCR、微调概率PAR、音调调节带宽BW和算法终止条件NI(最大迭代次数)[8]。

步骤2初始化和声库。随机产生HMS个候选解至和声库。

步骤3基于和声库构造新的和声。以和声记忆库取值概率HMCR在和声记忆库内搜索新解，以1-HMCR概率在和声记忆库外自变量值域内搜索新解，然后以微调概率PAR对新解进行局部扰动。

步骤4如果新产生的和声解优于和声记忆库中最差和声解，则用新产生的和声解代替和声库中的最差和声解。

步骤5若满足算法终止条件，则算法结束，输出最优解，否则返回步骤3继续求解。

和声搜索算法通用性强，无复杂理论公式，参数少，易于收敛，易于编程实现，适合非线性问题的求解；具有群体搜索的特点，能够记忆最优解；同时也具有协同搜索的特点，通过各体局部信息与群体全局信息的交互指导算法的搜索方向，然而基本的和声搜索算法也存在着一定的缺陷。由于和声搜索算法主要是基于邻域搜索进行寻优的，初始解选取的质量对算法搜索的性能影响较大。在整个优化过程中HMCR和PAR值固定不变，使得算法容易出现“早熟”收敛，陷入局部最优，群体多样性降低，搜索能力受到限制。

对于列车运行图调整问题，即求解TR，解是一个m×2n的矩阵。矩阵中第p行q列变量表示为TRp,q，和声记忆库可表示为

针对基本和声搜索算法的固有缺陷及结合列车运行图调整的特点，从以下几个方面进行改进。

(1)对于列车运行图调整问题，随机解是不可行的。因此由运行图终端程序按不同的区间运缓时间生成HMS个初始化和声库中的初始解，以提高算法的执行效率。

(2)HMCR在优化的不同阶段取不同值，HMCR∈[HMCRmin,HMCRmax)，HMCR=HMCRmax-(HMCRmax-HMCRmin)×gn/NI，gn表示当前迭代次数。优化初期，较大的HMCR值有利于找到局部最优解；优化末期，较小的HMCR值可增加提高解的多样性。

(5)和声记忆库外的变量值取该调度台同时段的历史行车数据。

改进后的和声搜索算法流程如图1所示。

4 算例验证与分析

采用北京局管内京津城际二台(京津城际延伸线)的实际应用情况做仿真验证。京津城际延伸线正线全长44.75 km，按高速铁路客运专线标准设计，设计时速350 km。自天津站城际场引出，沿途经机场西线路所、军粮城北站、滨海西线路所、塘沽城际场站，终到于家堡站。天津站城际场示意图如图2所示，于家堡站示意图如图3所示。京津城际二台8:00—12:00的基本图如图4所示。京津城际二台8:00—12:00各列车次在各站的到发时刻及端头站股道使用情况见表1。期间动车组交路情况为：C2581-C2584，C2314-C2315-C2318，C2332-C2333，C2583-C2302-C2303，C2316-C2317，C2585-C2586(“-”表示接续)。

图1 改进和声搜索算法流程图

图2 天津城际场示意图

图3 于家堡站示意图

图4 京津城际二台8:00—12:00基本图

车次站 名天津城际场机场西线路所军粮城北城际场滨海西线路所塘沽城际场于家堡到达出发股道到达出发到达出发到达出发到达出发到达出发股道C25817:588:01ⅡG8:098:098:108:108:128:128:198:208:29×2GC2315×8:42Ⅰ7G8:508:508:518:518:538:538:578:579:04×6GC2333×9:03Ⅰ5G9:119:119:159:169:209:209:279:289:37×1GC25839:199:21Ⅰ7G9:299:299:339:349:389:389:459:469:55×2GC2317×10:30Ⅰ6G10:3810:3810:3910:3910:4110:4110:4510:4510:52×5GC258511:0211:04Ⅰ7G11:1211:1211:1311:1311:1511:1511:2211:2311:32×ⅣGC2303×11:12Ⅰ6G11:2011:2011:2411:2511:2911:2911:3611:3711:46×ⅢGCZ3148:11×Ⅰ7G8:038:038:018:017:597:597:567:56×7:506GC23328:35×Ⅰ5G8:278:278:258:258:238:238:208:20×8:141GCZ5849:219:23Ⅰ6G9:139:139:119:119:099:099.:039:04×8:542GCZ31610:08×Ⅰ6G10:0010:009:589:589:569:569:509:51×9:415GC230210:40×Ⅰ6G10:3210:3210:2710:2810:2210:2210:1910:19×10:132GC231811:22×Ⅰ6G11:1411:1411:0911:1011:0411:0411:0111:01×10:556GC258612:2212:25Ⅰ6G12:1412:141212121212:1012:1012:0412:05×11:55ⅣG

基于以上数据可以得出，C2315到达于家堡站进入6G纵向切割下行咽喉；C2317由天津城际场Ⅰ6G出发纵向切割上行咽喉，C2317到达于家堡站进入5G纵向切割下行咽喉；C2303由天津城际场Ⅰ6G出发纵向切割上行咽喉；C2332由于家堡站1G出发纵向切割下行咽喉;C2332到达天津城际场进入Ⅰ5G纵向切割上行咽喉；C2854由于家堡站2G出发纵向切割下行咽喉；C2314到达天津城际场进入Ⅰ7G纵向切割上行咽喉。

模拟4种干扰场景，场景1：C2315由于某种原因在机场西线路所至军粮城北城际场下行区间运缓，导致在军粮城北城际场通过时晚点5 min。场景2：C2583由于某种原因在塘沽城际场至于家堡站下行区间运缓，导致在于家堡站到达晚点2 min。场景3：C2583由于某种原因在塘沽城际场至于家堡站下行区间运缓，导致在于家堡站到达晚点10 min。场景4：C2332由于某种原因在军粮城北城际场至机场西线路所上行区间运缓，导致在机场西线路所通过时间晚点6 min。

将建立的模型和改进和声搜索算法采用VC++编程植入运行图终端自动调整模块中，设动车组接续最小交路时间为15 min，已转实绩的点不参与调整，设置改进和声搜索算法参数：HWS=10，HMCR=[0.35,0.95]，PAR=[0.1,0.5]，NI=10 000。注入上述4种干扰场景后，经运行图终端程序的自动调整后输出的结果如图5～图8所示。

图5 场景1调整结果

图6 场景2调整结果

图7 场景3调整结果

图8 场景4调整结果

算例仿真分析：场景1中C2315在机场西线路线路所通过晚点5 min后，该运行线后续各点均晚点5 min，在于家堡站终到晚点5 min的时刻为09:09。由于C2315的接续动车组C2318在于家堡站的始发时刻为11:05，因此C2315的晚点不会影响接续动车组C2318。仿真结果与预期一致。场景2中C2583在于家堡站终到后接续C2302，图定动车组接续时间为18 min，实际C2583在于家堡站到达晚点2 min，由于最小动车组接续时间为15 min，没有对接续的C2302在于家堡站的始发造成影响，仿真结果与预期一致。场景3中C2583在于家堡站终到后接续C2302，图定动车组接续时间为18 min，实际C2583在于家堡站到达晚点10 min，由于最小动车组接续时间为15 min，利用动车组接续的冗余时间将晚点缩小至7 min，C2302在天津城际场到达晚点7 min，C2302的接续动车组为C2303，图定动车组接续时间为32 min，利用该动车组接续的冗余时间，消除了晚点，C2303在天津城际场可正点发车。仿真结果与预期一致。从场景4的调整结果可以看出在天津城际场变更了C2332与C2315的接发车顺序。由于C2332在机场西线路所通过晚点6 min，进而导致在天津城际场到达也晚点6 min，即08:41到达天津城际场，由于C2332进入15G时纵向切割上行咽喉将与图定08:42由该站17G发车的C2315发生进路冲突，若不改变C2332和C2315在天津城际场的接车列车顺序，将导致C2315在各站都晚点。改变接发车顺序后使得接续列车C2315正点发车，同时不影响其接续动车组C2333的发车，可减小总晚点时间，缩小晚点波及的影响范围，有效控制晚点传播，仿真结果与预期一致。

5 结束语

本文针对具有大量始发终到作业车站所在的调度区段动车组接续的特点，建立考虑动车组接续的高速铁路列车运行图智能调整模型，采用基于改进和声搜索算法对所建立的模型进行求解，从4种模拟干扰场景的调整结果看，考虑动车组接续的高速铁路列车运行图智能调整模型可根据晚点时间程度的不同，利用动车组接续的冗余时分及区间运行的冗余时分减少晚点时间，同时考虑晚点后车站接发车进路的相互影响，适当调整在车站的接发车顺序，能够有效缩小晚点的影响范围，控制晚点传播。

综上所述，考虑动车组接续的高速铁路列车运行图智能调整模型及采用的改进和声搜索算法，具有可行性和有效性。考虑动车组接续的高速铁路列车运行图智能调整研究为实现高速铁路智能调度系统提供了理论与应用技术支撑。