复杂约束条件的高速列车运行计划编制优化方法与系统

摘要

本发明公开了一种复杂约束条件的高速列车运行计划编制优化方法和系统，方法包括将运行线铺划时间分成多个初始的时间模块；对各个时间模块进行运行图结构优化；输出最优运行图。系统包括时间模块划分装置、运行图结构优化装置和输出装置。本发明通过从运行图结构优化的角度实现了旅行时间最小化和运能最大这两个相制衡的优化目标之间的双赢，动态实现运行图的合理优化。

说明书

技术领域

本发明涉及列车运行图编制。更具体地，本发明涉及复杂约束条件的高速列车运行计划编制优化方法与系统。 

背景技术

列车运行计划（或称为运行图）是在开行方案规定的列车服务频率、停站方案的基础上，根据固定运输资源（比如路网结构）和移动运输资源（比如动车组、乘务人员）属性，确定列车在始发、终到站以及途径车站的通过顺序和详细到发时刻。 

高速铁路列车运行计划优化是指在满足高速铁路各类作业时间标准等约束条件下，确定开行方案中运行在此线路上的各次列车在车站到达、出发和通过作业时间，在保证旅客列车于合理时间范围内始发、终到的同时，使得所选取的运行图优化目标达到最优。 

高速铁路列车运行计划的编制问题是一个复杂的、多约束、多维度、多目标的大规模求解问题。通过大量对运行图编制的研究和实践，可总结出3点关键：（1）高速铁路上，不同速度列车的运行线相互制约会引起旅速降低；（2）不同停站方案列车的到发顺序将有着不同的运行图结构，考虑到高中速混跑模式下列车的铺划顺序，应兼顾高速列车的有利发到时刻以及中速列车在既有线上时间的衔接。（3）列车初始布点方案的合理与否，直接影响着列车运行图的编制质量与实际使用价值，而且与机车交路、车站设备能力、车站作业进度和车流来源有关。 

高速铁路列车运行图结构（也就是运行线间的排列关系）有四种表现形式：（1）运行图可以用表格形式表示，叫时刻表；（2）运行图可以用矩阵的形式表示，主要有：停站方案矩阵、停站时间矩阵、区间运行时间矩阵、越行矩阵；（3）列车运行过程可以离散化为列车在车站和区间的到发作业，因此可以用离散事件动态系统来表示；（4）运行图可以用“二维时空”图解形式表示，就是传统意义的运行图。因此优化高速铁路列车运行图结构是非常必要和重要的。 

现有技术中的方法中，国外的方法包括：（1）基于周期运行图的PESP模型及其变种；（2）在传统运行图模型基础上，改进求解算法效率；（3）运行图均衡性。国内的方法比较典型的有：（1）运行图开行模式，如基于周期运行图的PESP模型；（2）运行图编制算法，主要有定序优化算法；（3）运行图优化及调整，有滚动优化策略及分层并行策略；（4）运行图均衡稳定性，如极大代数法的应用；（5）运行图的评价方面，如建立了高速铁路列车运行图的评价指标体系和计算方法。 

综上目前国内外的研究大都通过建立数学规划模型求解，由于我国高速铁路具有：“点多、线长、面广、客流分布不均匀”，在现有研究的基础上很难求得最优解。对于运行图优化问题来说，很难单线程的通过数学规划方法来优化，数学规划方法求得的是静态最优解，由于系统的动态性，难以实觋。此外，由于系统牵涉的因素多，导致变量数、约束条件增加，使得求解的迭代过程复杂化，极大地降低了求解效率，满足不了实时性要求，在现有研究的基础上无法求得最优解。因而，必须寻求一种新的优化方法。 

发明内容

本发明目的在于提供一种复杂约束条件的高速列车运行计划编制优化方法和系统，动态实现运行图的合理优化。 

具体技术方案如下： 

一种复杂约束条件的高速列车运行计划编制优化方法，包括以下步骤： 

将运行线铺划时间分成多个初始的时间模块； 

对各个时间模块进行运行图结构优化； 

输出最优运行图。 

所述对各个时间模块进行运行图结构优化进一步包括： 

S1、对列车发车组合进行优化； 

S2、对当前时间模块的发车排序进行优化； 

S3、通过运行线结构优化获得冲突最少的初始运行图作为备选方案； 

S4、通过对所述备选方案进行冲突化解获得该时间模块的最优运行图； 

S5、判断是否存在未优化的时间模块，如存在则进入S6，若不存在则执行步骤三输出最优运行图； 

S6、将该未优化的时间模块作为当前时间模块，重复执行步骤S2-S5。 

所述对列车发车组合进行优化进一步包括： 

根据列车服务频率、客流出行规律及客流适应度，并结合列车总停站次数一致的原则，对每个时间模块的列车组合进行划分。 

所述对当前时间模块的发车排序进行优化进一步包括以下步骤： 

根据Stirling公式，对列车排列采用序列法进行优化。 

所述通过运行线结构优化获得冲突最少的初始运行图作为备选方案进一步包括以下步骤： 

在不考虑冲突时进行运行线递推，获得初始运行图； 

将所述初始运行图中冲突最少的作为备选方案。 

所述在不考虑冲突时进行运行线递推，获得初始运行图是： 

以追踪列车间隔时间发车和最小停站时间停车作为约束条件，由以下公式递推获得： 

$a_{k+1}^i=d_k^i+r_k^i---\left(5\right)$

$a_k^i+{\delta }_k^i\times s_k^i=d_k^i---\left(6\right)$

其中，表示列车i在k站的停站情况，表示列车i在k站的离开时间；表示列车i在k站的到达时间；表示列车i在k站的停站时间；表示列车i在k区间的运行时间，γ_ik表示列车i在k站的最小停站时间，k表示车站索引，k=1,2,...n，n为车站总数；i表示列车索引，i=1,2,...m，m为车站总数。 

所述将该未优化的时间模块作为当前时间模块，重复执行步骤S2-S5还包括： 

将该未优化的时间模块进行模块过渡，将过渡后的下一时间模块作为当前时间模块，重复执行步骤S2-S5，所述模块过渡包括将被优化的上一时间模块的最后一条运行线作为下一时间模块的运行线之一，使该下一时间模块的起始时间调整为该最后一条运行线的发车时间。 

相应地，本发明还提供一种复杂约束条件的高速列车运行计划编制优化系统，该系统包括： 

时间模块划分装置，用于将运行线铺划时间分成多个时间模块； 

运行图结构优化装置，用于对各个时间模块进行运行图结构优化； 

输出装置，用于输出最优运行图。 

所述运行图结构优化装置进一步包括以下单元： 

发车组合优化单元，用于对列车发车组合进行优化； 

发车排序优化单元，用于对当前时间模块的发车排序进行优化； 

运行线结构优化单元，用于通过运行线结构优化获得冲突最少的初始运行图作为备选方案； 

冲突化解单元，用于通过对所述备选方案进行冲突化解获得该时间模块的最优运行图； 

判断单元，用于判断是否存在未优化的时间模块，如存在则启动重复执行单元，若不存在则启动所述输出装置； 

重复执行单元，用于将该未优化的时间模块作为当前时间模块，并启动所述发车排序优化单元。 

所述发车组合优化单元，进一步用于根据列车服务频率、客流出行规律及客流适应度，并结合列车总停站次数一致的原则，对每个时间模块的列车组合进行划分； 

所述发车排序优化单元，进一步用于根据Stirling公式，对列车排列采用序列法进行优化； 

所述运行线结构优化单元，进一步用于在不考虑冲突时进行运行线递推，获得初始运行图，以及用于将所述初始运行图中冲突最少的作为备选方案； 

所述重复执行单元进一步包括模块过渡子单元，该模块过渡子单元用于将该未优化的时间模块进行模块过渡，将过渡后的下一时间模块作为当前时间模 块，重复执行步骤S2-S5，所述模块过渡包括将被优化的上一时间模块的最后一条运行线作为下一时间模块的运行线之一，使该下一时间模块的起始时间调整为该最后一条运行线的发车时间。 

本发明对运行图的优化进行了完善，突破了过去的静态数学优化求解方法，从结构的角度动态实现了运行图的最合理优化。 

附图说明

下面将参照附图并结合实施例对本发明进行具体说明。 

图1为运行图结构优化步骤流程图； 

图2为高速铁路用于铺画不同速度等级列车时间模块示意图； 

图3为“零冲突”初始运行图； 

图4为“4个冲突”初始运行图； 

图5为最优方案的运行图； 

图6为优化过渡示意图。 

具体实施方式

下面参照附图并借助本发明的实施例，对本发明的技术方案做详细描述。 

本发明将高速列车运行图编制的优化转化为对运行图结构的优化，从运行图结构优化的角度出发，将列车间的约束关系融入到模型的目标中，在可行中求最优，代替了以往的以约束求可行的思想。提出了多决策地分步动态优化策略，通过优化列车发车组合比例以及发车顺序，最小化了运行线之间的制约关系；提出了基于全局优化的发车设计：以“追踪列车间隔时间I_Z发车，最小停站时间停车，也就是令作为约束条件，高密度地排列运行线，其实隐性包含了“旅行时间最小化”和“运能最大”的优化目标；以“冲突数最少”作为优化目标，从结构的角度动态实现了“旅行时间最小化”和“运能最大”这两个相制衡的优化目标之间的双赢。 

本发明所使用的运行图结构优化模型为： 

（一）参数定义： 

t：时间窗； 

k：车站索引，k=1,2,...n，n为车站总数； 

i,j：列车索引（j表示列车i的后续列车），i=1,2,...m，m为车站总数； 

γ_ik：列车i在k站的最小停站时间； 

λ_i：列车i的时间损失价值，即列车i每耽误一分钟对应的损失的价值； 

I_Z：追踪列车间隔时间；追踪运行列车之间的最小间隔时间，称为追踪列车间隔时间； 

I_d：按列车到达车站考虑，不同运行方式的相邻列车之间，到达车站的最 小间隔时间； 

I_f：按列车从车站出发考虑，不同运行方式的相邻列车之间，从车站出发的最小间隔时间 

（二）决策变量： 

1、二进制变量 

列车i在k站的停站情况； 

2、整数变量 

列车i在k站的离开时间； 

列车i在k站的到达时间； 

列车i在k站的停站时间； 

列车i在k区间的运行时间，也是在k站和k+1站之间的运行时间，包含列车在该区间的启停附加时分； 

（三）约束条件: 

1、区间运行时间约束 

假定列车在区间的运行时间是固定的，那么根据列车从车站的发车时间可唯一的确定下一站列车的到达时间。 

$a_{k+1}^i=d_k^i+r_k^i---\left(8\right)$

2、停站时间约束 

有列车的发车时间和停站时间可唯一的确定列车的离站时间 

$a_k^i+{\delta }_k^i\times s_k^i=d_k^i---\left(9\right)$

3、车站安全间隔约束，保证连续的两个事件之间有最小安全的时间间隔，无冲突发生。包括车站发车间隔时间I_f和车站到达间隔时间I_d约束 

车站发车间隔时间I_f约束： 

$d_k^{i+1}\ge d_k^i+I_f---\left(10\right)$

车站到达间隔时间I_d约束： 

$a_k^{i+1}\ge a_k^i+I_d---\left(11\right)$

该车站安全间隔约束用于在冲突化解模块中，作为约束条件，通过约束相邻列车之间有最小的安全时间间隔，从而实现运行图的冲突化解。 

（四）优化目标 

高速铁路上，不同速度列车的运行线相互制约引起旅速降低，不同列车的到发顺序将有着不同的运行图结构，因此优化高速铁路列车运行图结构是非常必要和重要的。 

1、运能最大 

在给定时间内，铺划更多的列车，提高运行图的能力，是运行图优化的第一个重要目标。 

2、旅行时间损失最小 

列车的旅行时间损失主要是由于在车站停车造成的，超过标准停站时间的停站时间部分，我们定义为旅行时间损失Z，将旅行时间损失降到最低可看作运行图优化的第二个重要目标。最低旅行时间损失用下列公式表示： 

$\mathrm{MinZ}=\underset{i=1}{\overset{m}{\Sigma }}\underset{k=1}{\overset{n}{\Sigma }}[{\lambda }_i\times (s_k^i-{\gamma }_{\mathrm{ik}})]---\left(12\right)$

由于运行图优化的目标是旅行时间损失的最小化和运能的最大化，该两者目标存在一定的矛盾，为了保障总旅行时间的最小化，必然会牺牲掉运行图的能力，而为了增加运行图能力，列车的旅行速度又受到影响。因此在始发站列车以最小追踪间隔运行的前提下，尽可能减小由于运行线相互制约而引起的时间损失，成为了协调这两者目标的唯一方法。 

本发明采用多决策地分布动态优化策略，将运行图结构的优化分为以下4个关键步骤技术，如图1所示。 

一、发车组合的优化 

根据客流的出行规律和列车服务频率，为了保证每个模块每个车站都可以满足停站的需求，及客流的适应度，结合列车总停站次数一致的原则，对每个时间模块的列车组合进行划分。我们将列车看做组成运行图的骨架，由于不同速度等级、不同停站方案的列车相互制约，因此不同的列车组合在运行图中会表现为不同的运行图结构，对发车组合进行优化，就是对列车的组合进行优化，也就是对运行图的结构进行了初步的优化，从而发车组合优化的这一步骤，可以为后面对运行图结构的优化提供初始框架。 

二、对发车排序的优化。 

合理对运行线进行排序，确定运行线在各站的作业时间，这是一个超大规模优化问题。根据Stirling公式，随着n的增大，全排列的计算量庞大，本文考虑在排列和一种特殊的序列之间建立一种一一对应关系，然后由序列产生排列。 

将n-1个元素的序列(a_n-1,a_n-2,...a₁)与n个元素的排列建立起一一对应关系，因为满足条件0≤a_i≤i,1≤i≤n-1的序列(a_n-1,a_n-2,...a₁)共有n!个，这恰好与n个元素的全排列n!个整数一一对应。考虑到a_i的数学特点（0≤a_i≤i,i=1,2,...,n-1），本文建立一种逻辑关系，设a_i表示排列P中数i+1所在位置的右边比i+1小的数的个数，则序列(a_n-1,a_n-2,...a₁)可确定其唯一对应的排列P。由序列产生排列的方法如下： 

我们可以从1开始构造排列: 

1、写下1； 

2、考虑a₁,它只可取0或1。若取0，则2必在1的后边；否则，它在1的前边。 

3、考虑a₂,它可取0，1，2。若取0，3必放在上一步得到的两个数的排 列的后边，若a₂=1,则3必放在第二步得到的两数的排列的中间，若a₂=2,则3必放在第二步得到的排列的两数的前边。 

k+1、考虑a_k，0≤a_k≤k 

(1)a_k=0,k+1必放在第k步得到的排列的这k个数的最后面； 

(2)a_k=1,k+1必放在第k步得到的排列的k个数的倒数两个数中间； 

(j)a_k=j,k+1必放在第k步得到的排列的k个数的倒数j和j+1这两个数之间。 

三、运行线结构优化 

运行线结构优化包括运行线递推和寻找冲突最少运行图的过程。关于运行线递推，对每一排列情况根据“追踪列车间隔时间I_Z发车，最小停站时间停车，也就是令由式（1）-（3）的递推关系可得到初始运行图，比较所有排列情况下，哪种冲突最少，则说明了该组合方式下运行线之间的相互制约关系最弱，出于尽可能减小由于运行线相互制约而引起的时间损失的目标，则该排列可视为最优发车排列顺序。 

需要解释的是，以“追踪列车间隔时间I_Z发车，和最小停站时间停车（令 ）”作为约束条件，高密度地排列运行线，并以“冲突数最少”作为优化目标，其实隐性包含了“旅行时间最小化”和“运能最大”的优化目标。以“冲突数最少”为目标，从结构上实现了“旅行时间最小化”和“运能最大”这两个相制衡的优化目标之间的双赢，对运行图的优化进行了完善，突破了过去的静态数学优化求解方法，从结构的角度动态实现了运行图的最合理优化。 

四、冲突化解 

运行线冲突化解，归根到底就是处理列车交会、越行方案。同等级的列车之间不存在避让问题，列车的越行只发生在不同等级列车之间，我们规定低等级列车避让高等级列车，最小化由于避让产生的等待时间。 

冲突化解的关键是，将初始运行图中所有列车的在各车站的到发事件看做节点，式（4）-（5）作为约束条件，最小化所有到发事件之间带有顺序的间隔时间之和。列车运行图冲突化解的方法归纳起来主要有以下6种:（1）平移列车运行线；（2）交换作业顺序；（3）变更停站方案；（4）增设列车车站待避；（5）延长列车停站时间；（6）调整列车始发时间域。 

如图本发明的系统包括时间模块划分装置、运行图结构优化装置以及输出装置。所述时间模块划分装置用于将运行线铺划时间分成多个时间模块；所述运行图结构优化装置，用于对各个时间模块进行运行图结构优化；所述输出装置，用于输出最优运行图。 

本发明的方法包括： 

Step1.将本发明的系统初始化。为了方便描述，以下以京沪线某一开行方案为例进行说明。 

Step2.读取线路、车站、区间、列车数据及运行图标尺。在本例中，I_Z=5min， I_d=2min，I_f=3min，γ_ik=2min。 

Step3.在所述时间模块划分装置中进行运行图初始时间模块划分，确定可供铺划运行线的时间区段，之后将运行图根据列车比例及时间轴初始划分成不同的时间模块。 

考虑高速铁路的运营特点，如图2所示，0：00-4：00维修天窗，6:00-7:00为列检车时间，如图2所示，故实际可用于铺划运行线的时间区间为7:00-24：00（即17个小时），可根据开行方案的不同将该时间区间均分为比如3，4，5，6，7，8个初始时间模块，对各时间模块进行运行图的铺划。 

不同种类客运列车（如我国的G，D，Z，K，T等字头列车）在始发站发车的搭配由客流的类型和数量决定的。因此，确定合理的列车始发站的先后搭配关系要深入分析不同种类客流的出行规律。（1）若某始发站的全天客流出行规律具有上午、下午的双峰特点，那么，在高峰期列车会安排阶段密集发车；（2）统计不同层次需求的旅客出行时机特点，确定不同等级或者种类的列车发车数量及发车的先后关系。客流出行规律与相应的列车开行密度性匹配，这将决定不同种类列车发车先后顺序。 

京沪线各区段开行列车对数如表1所示。结合目前我国京沪线的作业时间，可供铺划运行线的时间区段有17个小时（1020分钟），将运行线的铺划区间分为8个初始时间模块，则每个时间模块各有127.5分钟,8个时间模块分别为：[7:00:00-9:07:30],[9:07:30-11:15:00],[11:15:00-13:22:30],[13:22:30-15:30:00],[15:30:00-17:37:30],[17:37:30-19:45:00],[19:45:00-21:52:30],[21:52:30-24:00:00]。 

表1京沪线列车开行对数 

所述运行图结构优化装置进一步包括发车组合优化单元、发车排序优化单元、运行线结构优化单元、冲突化解单元、判断单元和重复执行单元。各单元所执行的步骤将在下面进行详细说明。 

Step4.所述发车组合优化单元对列车发车组合优化，具体如下： 

Step4.1根据列车服务频率一致的原则，对每个时间模块平均分配列车。 

由北京南站始发，至虹桥方向共有47列车，其中41列A等级类车，6列B等级列车，则每个时间模块平均可铺划6列列车。 

Step4.2根据客流的出行规律，对不同速度等级的列车进行需求分配：客流的出行规律指的是旅客的偏好，也就是旅客在该8个时间模块，根据乘客在不同时间对列车等级的要求，分配相应速度等级的列车到不同时间模块。一般情况下，我们会令不同时间模块的列车等级分配均匀，不会一个时间模块全部高等级或是低等级。这里，每个时间模块平均有5列A类车，1列B类车。 

Step4.3客流适应度：保证每个时间模块每个车站都可以满足停站的需求，并结合列车总停站次数一致的原则，对每个时间模块的列车组合进行分配。通俗意义上说就是，旅客在一天的任意一个时间段到达他所属的车站，他可以实现旅行的目的。北京南始发列车的停站方案表2（见说明书21-22页）所示。 

8个时间模块列车发车组合的优化结果如下： 

第一时间模块：[A2601(3),A2602(3),A201(4),A1(9),A11(8),B3(14)]     共41次停站 

第二时间模块：[A2603(3),A2604(3),A202(4),A2(9),A4(8),A12(9)]     共36次停站 

第三时间模块：[A2605(3),A2606(3),A203(4),A3(9),A10(9),A7(9)]     共37次停站 

第四时间模块：[A2607(3),A2608(3),A204(4),A5(9),A13(8),B1(10)]     共37次停站 

第五时间模块：[A2609(3),A2610(3),A205(4),A6(8),A15(8),B2(14)]     共40次停站 

第六时间模块：[A2611(3),A2612(3),A206(4),A8(8),A17(8),B4(17)]     共43次停站 

第七时间模块：[A2613(3),A2614(3),A14(7),A16(7),A19(8),B5(15)]     共43次停站 

第八时间模块：[A2615(3),A2616(3),A9(9),A18(8),B6(17)]共40次停站 

其中：圆括号中的数字代表停站次数，A，B表示列车种类。以下选择列车组[A2601(3),A2602(3),A201(4),A1(9),A11(8),B3(14)]进行实例分析，该列车组的停站方案见表3（见说明书22页）。 

Step5.读取当前时间模块内的停站方案、区间运行时间和停站时间。 

Step6.对当前时间模块，进行运行图结构最优方案的初始寻优 

Step6.1由所述发车排序优化单元对当前时间模块的发车排序进行优化： 

对于第一时间模块的列车组合[A2601(3),A2602(3),A201(4),A1(9),A11(8),B3(14)]，其排列数总共有全排列种，而本文对排列顺序优化采用序列法，可排除一半相同的方案，最后共有360种排列情况。在本发明中，为了方便描述，将列车组集合[A2601(3),A2602(3),A201(4),A1(9),A11(8),B3(14)]用集合S={1,2,3,4,5,6}来表示，并用序列法生成S的全部排列，各个序列对应生成的列车的各排列P,如表4（见说明书23-25页）所示。 

Step6.2所述运行线结构优化单元在不考虑冲突的前提下，依据运行图标尺和运行线递推，以“追踪列车间隔时间I_Z发车，最小停站时间停车（就是令 ）”作为约束条件，由式（1）-（3）的递推关系，铺划初始运行图，该初始运行图包括对应于集合S中各列车排列的运行图。 

Step6.3该运行线结构优化单元进一步寻找所有发车排列顺序所对应的初始运行图中，冲突数最少的初始运行图作为备选方案。 

例如，对于第一时间模块的列车组合[A2601(3),A2602(3),A201(4),A1(9),A11(8),B3(14)]，图3为“零冲突”初始运行图，这种初始运行图的列车组合方式我们可看作运行图结构最优的备选方案之一。由图3可看出，虽然“零冲突”初始运行图没有冲突，可是其占用运行图的时间为140min较长。接着寻找次优运行图，我们找到只有“4个冲突”的运行图如图4所示。该图中的列车组合排列方式占用运行图时间为100min，占用运行图的时间较短，我们同样选择该组合排列方式作为运行图结构最优的备选方案之二。 

Step7.所述冲突化解单元对所述备选方案进行冲突化解求得该时间模块的最优运行图。具体地，采用式（4）-（5）对所述冲突数最少的初始运行图进行冲突化解，寻找占用运行图时间最少的方案。 

比如，对图4的有4个冲突的运行图进行冲突化解，优化后的方案占用运行图的时间为120min，如图5所示。化解后的图5运行图与图3的“零冲突”运行图作对比，其占用运行图的时间最少，因此该备选方案之二为运行图结构最优的方案，从而可得到运行图结构最优的方案，如表5所示（见说明书26-27页），以及发车排列：[B3,A2601,A2602,A11,A201,A1]。 

Step8.所述判断单元判断是否存在未优化的时间模块，若存在进入Step9.，启动所述重复执行单元，若不存在，进入Step10.，启动输出装置。 

Step9.一般地，所述重复执行单元将该未优化的时间模块直接作为当前时间模块，启动所述发车排序优化单元从而重复执行步骤Step5至Step8。优选地，本实施例中所述重复执行单元还包括模块过渡子单元，该模块过渡子单元对该未优化的时间模块进行模块过渡，将过渡后的下一时间模块作为当前时间模块，然后再启动所述发车排序优化单元从而重复执行步骤Step5至Step8。所述模块过渡包括Step9.1和Step9.2： 

Step9.1时间模块的边界调整：在调整过程中，根据已优化的时间模块中最后一条运行线的位置确定下一时间模块的边界，同时该位置也是该已优化时间模块的结束时间边界。如图6所示，设每一初始时间模块的时间长度为T，图中存在两个初始时间模块[t₀,t₀+T]和[t₀+T,t₀+2T]，设初始时间模块[t₀,t₀+T]已经被优化,那么根据该时间模块的最后一条运行线（粗线所示）的位置可确定时间模块的边界，该运行线在始发站a站的发车时间t₁则为下一时间模块的新的时间边界，也就是说下一时间模块的起始时间由初始设置的时间t₀+T调整为t₁，则当前未优化的时间模块的起止时间为[t₁,t₀+2T]。其中，已优化的时间模块中最后一条运行线只作为下一时间模块优化的参考，不参与下一模块的发车排列优化，也就是说当对下一时间模块的运行图进行优化时不能改变该最后一条运行线的参数。 

Step9.2模块过渡，转入Step5。 

将前一时间模块内的最后一条运行线（粗线所示）重新放入当前未优化的时间模块，从而组成具有7条运行线的下一优化模块。之后，对于该下一时间模块[t₁,t₀+2T]的运行图结构，执行Step5至Step8进行优化。不过由于该最后一条运行线的位置是确定的，因此实际上还是对该下一时间模块中的6列列车[A2603,A2604,A202,A2,A4,A12]，执行发车排列优化、运行线结构优化和冲突化解。 

模块过渡这一技术，主要有2点作用：（1）进行相邻时间模块的边界定位，避免运行图时间浪费。需要说明的是，本发明的优化不是矩形窗口形式的优化，而是灵活的紧挨着已优化时间模块的结束时间，开始新模块的优化，比如第一时间模块7点开始，8点就结束了，那么当前未优化的时间模块就从8点开始优化，避免时间浪费。（2）相邻两时间模块之间的冲突检测作用，由于Step7仅针对时间模块的冲突化解，采用模块过渡技术，将上一时间模块的最后一条运行线放入当前的未优化时间模块，在对该当前未优化的时间模块进行优化的过程中，就会实现跨模块的冲突化解，避免了单纯优化8个时间模块的冲突遗漏。 

Step10.运行图优化完成，输出完整的最优运行图。 

应当理解，以上借助优选实施例对本发明的技术方案进行的详细说明是示意性的而非限制性的。本领域的普通技术人员在阅读本发明说明书的基础上可以对各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的精神和范围。本发明的保护范围仅由随附权利要求书限定。 

表5第一时间模块的运行图结构最优的方案（时刻表）