本发明公开了一种基于站台冗余的列车运行图调整方法和系统,方法包括当原站台失效时,对原运行图进行调整生成新运行图,该新运行图对每一辆受影响列车分配一个新站台;如果所述原站台被成功修复,则所述受影响列车继续使用该原站台,否则,所述受影响列车使用所述新站台。本发明充分考虑了站台失效时间的随机性本质,与传统方法相比可以有效地降低延迟时间与成本。
1.一种基于站台冗余的列车运行图调整方法,其特征在于,包括以下步骤:当原站台失效时,对原运行图进行调整生成新运行图,该新运行图对每一辆受影响列车分配一个新站台;该步骤进一步包括步骤一、地面信号系统向调度中心报告所述原站台的失效信息,所述失效信息包括该原站台的编号及其预估失效时间,所述预估失效时间为随机变量;步骤二、调度中心根据所述编号及其预估失效时间生成新运行图,并将该新运行图发送给车载信号系统与车站,该新运行图还包括列车进站新时刻和乘客更换站台时刻;步骤三、车载信号系统与车站分别将列车延迟信息通知给司机与候车乘客;步骤四、调度中心根据新运行图,对每一辆受影响列车设定一个通知时刻,所述通知时刻为所述列车进站新时刻与所述乘客更换站台所需时间的差;步骤五、地面信号系统在所述通知时刻向调度中心报告原站台的维修情况;如果所述原站台被成功修复,则所述受影响列车继续使用该原站台,否则,所述受影响列车使用所述新站台;该步骤具体包括如果原站台已经修复,车载信号系统将接收到调度中心指令,通知司机按所述原运行图进站;否则,新站台将启用,车载信号系统和车站将接收到调度中心指令,通知司机按所述新运行图进站,车站也将通知候车乘客更换站台。
2.根据权利要求1所述的基于站台冗余的列车运行图调整方法,其特征在于,所述步骤二、调度中心根据所述编号及其预估失效时间生成新运行图,并将该新运行图发送给车载信号系统与车站,该新运行图还包括列车进站新时刻和乘客更换站台时刻进一步包括:建立随机优化模型来模拟列车运行图的调整;其中,所述随机优化模型的决策变量为:列车i驶入区间j的时刻,用ntent="drawing" img-format="tif" inline="yes" orientation="portrait" wi="68"/>表示;以及,列车i驶离区间j的时刻,用ntent="drawing" img-format="tif" inline="yes" orientation="portrait" wi="65"/>表示;所述随机优化模型的目标函数为:minxa0D(x,p,r)+C(x,p,r)其中, D ( x , p , r ) = Σ i = 1 I Σ j = o i d i d ij max { x ij s - o ij s , 0 } . ]]> C ( x , p , r ) = Σ i = 1 I Σ j = o i d i Σ t = 1 m j Σ s = 1 m j q ijt p ijt c ij n ij d ( t , s ) Pr { ξ t ≥ x ij s - a ij } . ]]> 所述随机优化模型的约束条件包括列车驶离驶入时刻约束、最小运行时间约束、最小停站时间约束、列车离站时刻约束、列车运行次序约束、安全距离约束、决策变量范围和TBR约束;其中,所述TBR约束为: Σ t = 1 m j p ijt ≥ 1 , ∀ o i ≤ j ≤ d i , 1 ≤ i ≤ I . ]]>和 x ij s ≥ min 1 ≤ t ≤ m j ( b t p ijt + M ( 1 - p ijt ) ) , ∀ o i ≤ j ≤ d i , 1 ≤ i ≤ I . ]]>其中,i表示列车,i=1,2,...,I,j表示区间,j=1,2,...,J,D(x,p,r)表示所有列车驶离所有车站的延迟成本,C(x,p,r)表示站台更换成本,m_j表示区间j的站台的数目,d_ij表示列车i到达区间j的单位延迟成本,c_ij表示列车i在区间j的单位站台改变成本,n_ij表示在区间j等待列车i的乘客数量,a_ij表示乘客在区间j换乘所需时间,q_ijt表示原运行图中,如果列车i在区间j被指站台t,那么q_ijt=1,否则,q_ijt=0,ntent="drawing" img-format="tif" inline="yes" orientation="portrait" wi="60"/>表示原运行图中,列车i驶入区间j的时刻,o_i表示列车i的始发站,d_i表示列车i的终点站,ξ_t表示站台t的所述预估失效时间,其密度函数是φ(y),y∈[l_t,u_t],其中,l_t与u_t分别表示最小与最大可能失效时间,p_ijt表示如果列车i在区间j被指派站台t,那么p_ijt=1,否则,p_ijt=0,r_ilj表示如果列车i早于列车l进入区间j,那么r_ilj=1;否则,r_ilj=0。
3.根据权利要求2所述的基于站台冗余的列车运行图调整方法,其特征在于,所述步骤二、调度中心根据所述编号及其预估失效时间生成新运行图,并将该新运行图发送给车载信号系统与车站,该新运行图还包括列车进站新时刻和乘客更换站台时刻进一步包括:利用基于贪婪算法的遗传算法对所述随机优化模型求解最优调整策略;以及,根据所述最优调整策略生成所述新运行图。
4.根据权利要求3所述的基于站台冗余的列车运行图调整方法,其特征在于,所述贪婪算法包括:计算所有列车驶入车站的可能时刻,指定具备最小可能时刻的列车驶入该车站;计算剩余列车驶入车站的可能时刻,指定具备最小可能时刻的列车驶入该车站直到所有列车均已安培进站。
5.一种基于站台冗余的运行图优化调整模拟系统,其特征在于,该系统用于当原站台失效时,对原运行图进行调整生成新运行图,该新运行图对每一辆受影响列车分配一个备份站台;以及,用于如果所述原站台被成功修复,则所述受影响列车继续使用该原站台,否则,所述受影响列车使用所述备份站台。
6.一种运行图生成装置,其特征在于,该装置包括:建模单元,用于建立随机优化模型来模拟列车运行图的调整;所述随机优化模型的决策变量为:列车i驶入区间j的时刻,用ntent="drawing" img-format="tif" inline="yes" orientation="portrait" wi="60"/>表示;以及,列车i驶离区间j的时刻,用ntent="drawing" img-format="tif" inline="yes" orientation="portrait" wi="65"/>表示;所述随机优化模型的目标函数为:minxa0D(x,p,r)+C(x,p,r)其中, D ( x , p , r ) = Σ i = 1 I Σ j = o i d i d ij max { x ij s - o ij s , 0 } . ]]> C ( x , p , r ) = Σ i = 1 I Σ j = o i d i Σ t = 1 m j Σ s = 1 m j q ijt p ijt c ij n ij d ( t , s ) Pr { ξ t ≥ x ij s - a ij } . ]]> 所述随机优化模型的约束条件包括列车驶离驶入时刻约束、最小运行时间约束、最小停站时间约束、列车离站时刻约束、列车运行次序约束、安全距离约束、决策变量范围和TBR约束;其中,所述TBR约束为: Σ t = 1 m j p ijt ≥ 1 , ∀ o i ≤ j ≤ d i , 1 ≤ i ≤ I . ]]>和 x ij s ≥ min 1 ≤ t ≤ m j ( b t p ijt + M ( 1 - p ijt ) ) , ∀ o i ≤ j ≤ d i , 1 ≤ i ≤ I . ]]>其中,i表示列车,i=1,2,...,I,j表示区间,j=1,2,...,J,D(x,p,r)表示所有列车驶离所有车站的延迟成本,C(x,p,r)表示站台更换成本,m_j表示区间j的站台的数目,d_ij表示列车i到达区间j的单位延迟成本,c_ij表示列车i在区间j的单位站台改变成本,n_ij表示在区间j等待列车i的乘客数量,a_ij表示乘客在区间j换乘所需时间,q_ijt表示原运行图中,如果列车i在区间j被指站台t,那么q_ijt=1,否则,q_ijt=0,ntent="drawing" img-format="tif" inline="yes" orientation="portrait" wi="61"/>表示原运行图中,列车i驶入区间j的时刻,o_i表示列车i的始发站,d_i表示列车i的终点站,ξ_t表示站台t的预估失效时间,其密度函数是φ(y),y∈[l_t,u_t],其中,l_t与u_t分别表示最小与最大可能失效时间,p_ijt表示如果列车i在区间j被指派站台t,那么p_ijt=1,否则,p_ijt=0,r_ilj表示如果列车i早于列车l进入区间j,那么r_ilj=1;否则,r_ilj=0。
7.根据权利要求6所述的运行图生成装置,其特征在于,该装置还包括:计算单元,用于利用基于贪婪算法的遗传算法对所述随机优化模型求解最优调整策略;以及,新运行图生成单元,用于根据所述最优调整策略生成所述新运行图。
8.一种包括如权利要求6所述运行图生成装置的调度中心。
9.一种地面信号系统,其特征在于,该系统用于向调度中心报告原站台失效信息,所述原站台失效信息包括站台编号及其预估失效时间,所述预估失效时间为随机变量。技术领域
本发明涉及列车运行图的调整。更具体地,本发明涉及一种基于站台冗余的列车运行图调整方法和系统。
背景技术
列车运行图包括列车驶入、驶离车站的时刻、顺序、以及站台选择等相关信息。受自然条件、人为事故、设备故障的影响,一个或多个站台可能在某一时间段之内无法使用。在这种情况下,调度员需要及时调整列车运行图以避免事故的发生,同时最小化运行图调整所带来的负面影响。现有的列车运行图调整系统均使用确定的量来估计站台失效时间,虽然针对站台失效的列车运行图优化调整系统的研究十分广泛,但均没有考虑站台失效时间的随机性本质。然而,对失效时间的高估或低估都会对调整结果产生消极影响。一方面,失效时间估计过高会导致站台闲置,即,站台在修复完成的一段时间内没有被占用,从而加重列车延迟;另一方面,失效时间估计过低会使站台提前占用,即,站台尚未完全修复即被安排占用,引发运行图的再次调整、给乘客带来不便,甚至会引发事故。因此需要一种能够考虑到站台失效时间随机性的列车运行图调整方法和系统。
发明内容
本发明目的在于提供一种基于站台冗余的列车运行图调整方法和系统,目的在于充分考虑站台失效时间的随机性,降低延迟时间与调整成本。具体的技术方案为:一种基于站台冗余的列车运行图调整方法,包括以下步骤:当原站台失效时,对原运行图进行调整生成新运行图,该新运行图对每一辆受影响列车分配一个新站台;如果所述原站台被成功修复,则所述受影响列车继续使用该原站台,否则,所述受影响列车使用所述新站台。进一步地,所述当原站台失效时,对原运行图进行调整生成新运行图,该新运行图对每一辆受影响列车分配一个新站台包括以下步骤:步骤一、地面信号系统向调度中心报告所述原站台的失效信息,所述失效信息包括该原站台的编号及其预估失效时间,所述预估失效时间为随机变量;步骤二、调度中心根据所述编号及其预估失效时间生成新运行图,并将该新运行图发送给车载信号系统与车站,该新运行图还包括列车进站新时刻和乘客更换站台时刻;步骤三、车载信号系统与车站分别将列车延迟信息通知给司机与候车乘客;进一步地,所述如果所述原站台被成功修复,则所述受影响列车继续使用该原站台,否则,所述受影响列车使用所述新站台包括以下步骤:步骤四、调度中心根据新运行图,对每一辆受影响列车设定一个通知时刻,所述通知时刻为所述列车进站新时刻与所述乘客更换站台所需时间的差;步骤五、地面信号系统在所述通知时刻向调度中心报告原站台的维修情况;步骤六、如果原站台已经修复,车载信号系统将接收到调度中心指令,通知司机按所述原运行图进站;否则,新站台将启用,车载信号系统和车站将接收到调度中心指令,通知司机按所述新运行图进站,车站也将通知候车乘客更换站台。进一步地,所述步骤二、调度中心根据所述编号及其预估失效时间生成新运行图,并将该新运行图发送给车载信号系统与车站,该新运行图还包括列车进站新时刻和乘客更换站台时刻进一步包括:建立随机优化模型来模拟列车运行图的调整;其中,所述随机优化模型的决策变量为:列车i驶入区间j的时刻,用ntent="drawing" img-format="tif" inline="yes" orientation="portrait" wi="59"/>表示;以及,列车i驶离区间j的时刻,用ntent="drawing" img-format="tif" inline="yes" orientation="portrait" wi="63"/>表示;所述随机优化模型的目标函数为:minxa0D(x,p,r)+C(x,p,r)其中, D ( x , p , r ) = Σ i = 1 I Σ j = o i d i d ij max { x ij s - o ij s , 0 } . ]]> C ( x , p , r ) = Σ i = 1 I Σ j = o i d i Σ t = 1 m j Σ s = 1 m j q ijt p ijt c ij n ij d ( t , s ) Pr { ξ t ≥ x ij s - a ij } . ]]> 所述随机优化模型的约束条件包括列车驶离驶入时刻约束、最小运行时间约束、最小停站时间约束、列车离站时刻约束、列车运行次序约束、安全距离约束、决策变量范围和TBR约束;其中,所述TBR约束为: Σ t = 1 m j p ijt ≥ 1 , ∀ o i ≤ j ≤ d i , 1 ≤ i ≤ I . ]]>和 x ij s ≥ min 1 ≤ t ≤ m j ( b t p ijt + M ( 1 - p ijt ) ) , ∀ o i ≤ j ≤ d i , 1 ≤ i ≤ I . ]]>其中,i表示列车,i=1,2,...,I,j表示区间,j=1,2,...,J,D(x,p,r)表示所有列车驶离所有车站的延迟成本,C(x,p,r)表示站台更换成本,m_j表示区间j的站台的数目,d_ij表示列车i到达区间j的单位延迟成本,c_ij表示列车i在区间j的单位站台改变成本,n_ij表示在区间j等待列车i的乘客数量,a_ij表示乘客在区间j换乘所需时间,q_ijt表示原运行图中,如果列车i在区间j被指站台t,那么q_ijt=1,否则,q_ijt=0,ntent="drawing" img-format="tif" inline="yes" orientation="portrait" wi="59"/>表示原运行图中,列车i驶入区间j的时刻,o_i表示列车i的始发站,d_i表示列车i的终点站,ξ_t表示站台t的所述预估失效时间,其密度函数是φ(y),y∈[l_t,u_t],其中,l_t与u_t分别表示最小与最大可能失效时间,p_ijt表示如果列车i在区间j被指派站台t,那么p_ijt=1,否则,p_ijt=0,r_ilj表示如果列车i早于列车l进入区间j,那么r_ilj=1;否则,r_ilj=0。进一步地,所述步骤二、调度中心根据所述编号及其预估失效时间生成新运行图,并将该新运行图发送给车载信号系统与车站,该新运行图还包括列车进站新时刻和乘客更换站台时刻进一步包括:利用基于贪婪算法的遗传算法对所述随机优化模型求解最优调整策略;以及,根据所述最优调整策略生成所述新运行图。其中,所述贪婪算法包括:计算所有列车驶入车站的可能时刻,指定具备最小可能时刻的列车驶入该车站;计算剩余列车驶入车站的可能时刻,指定具备最小可能时刻的列车驶入该车站直到所有列车均已安培进站。本发明还提供一种基于站台冗余的运行图优化调整模拟系统,该系统用于当原站台失效时,对原运行图进行调整生成新运行图,该新运行图对每一辆受影响列车分配一个备份站台;以及,用于如果所述原站台被成功修复,则所述受影响列车继续使用该原站台,否则,所述受影响列车使用所述备份站台。本发明还提供一种运行图生成装置,该装置包括:建模单元,用于建立随机优化模型来模拟列车运行图的调整;所述随机优化模型的决策变量为:列车i驶入区间j的时刻,用ntent="drawing" img-format="tif" inline="yes" orientation="portrait" wi="63"/>表示;以及,列车i驶离区间j的时刻,用ntent="drawing" img-format="tif" inline="yes" orientation="portrait" wi="56"/>表示;所述随机优化模型的目标函数为:minD(x,p,r)+C(x,p,r)其中, D ( x , p , r ) = Σ i = 1 I Σ j = o i d i d ij max { x ij s - o ij s , 0 } . ]]> C ( x , p , r ) = Σ i = 1 I Σ j = o i d i Σ t = 1 m j Σ s = 1 m j q ijt p ijt c ij n ij d ( t , s ) Pr { ξ t ≥ x ij s - a ij } . ]]> 所述随机优化模型的约束条件包括列车驶离驶入时刻约束、最小运行时间约束、最小停站时间约束、列车离站时刻约束、列车运行次序约束、安全距离约束、决策变量范围和TBR约束;其中,所述TBR约束为: Σ t = 1 m j p ijt ≥ 1 , ∀ o i ≤ j ≤ d i , 1 ≤ i ≤ I . ]]>和 x ij s ≥ min 1 ≤ t ≤ m j ( b t p ijt + M ( 1 - p ijt ) ) , ∀ o i ≤ j ≤ d i , 1 ≤ i ≤ I . ]]>其中,i表示列车,i=1,2,...,I,j表示区间,j=1,2,...,J,D(x,p,r)表示所有列车驶离所有车站的延迟成本,C(x,p,r)表示站台更换成本,m_j表示区间j的站台的数目,d_ij表示列车i到达区间j的单位延迟成本,c_ij表示列车i在区间j的单位站台改变成本,n_ij表示在区间j等待列车i的乘客数量,a_ij表示乘客在区间j换乘所需时间,q_ijt表示原运行图中,如果列车i在区间j被指站台t,那么q_ijt=1,否则,q_ijt=0,ntent="drawing" img-format="tif" inline="yes" orientation="portrait" wi="50"/>表示原运行图中,列车i驶入区间j的时刻,o_i表示列车i的始发站,d_i表示列车i的终点站,ξ_t表示站台t的所述预估失效时间,其密度函数是φ(y),y∈[l_t,u_t],其中,l_t与u_t分别表示最小与最大可能失效时间,p_ijt表示如果列车i在区间j被指派站台t,那么p_ijt=1,否则,p_ijt=0,r_ilj表示如果列车i早于列车l进入区间j,那么r_ilj=1;否则,r_ilj=0。进一步地,所述运行图生成装置还包括:计算单元,用于利用基于贪婪算法的遗传算法对所述随机优化模型求解最优调整策略;以及,新运行图生成单元,用于根据所述最优调整策略生成所述新运行图。另外,本发明还提供一种包括所述运行图生成装置的调度中心。另外,本发明还提供一种地面信号系统,该系统用于向调度中心报告原站台失效信息,所述原站台失效信息包括站台编号及其预估失效时间,所述预估失效时间为随机变量。本发明的优点在于充分考虑了站台失效时间的随机性本质,与传统方法相比可以有效地降低延迟时间与成本。另外,贪婪算法的应用可以显著提高计算速度,基于京沪高铁数据,实验结果表明本发明与传统方法相比可以有效地降低运行图调整成本10.17%,同时在相对误差小于2.85%条件下的计算时间小于1.5秒,因此本发明具备实时计算能力。
附图说明
下面将参照附图并结合实施例对本发明进行具体说明。图1为本发明方法的流通图;图2为运行图生成装置结构示意图;图3为具体实施例中区间分布示意图。
具体实施方式
下面参照附图并借助本发明的实施例,对本发明的技术方案做详细描述。本发明是一种基于站台冗余的列车运行图调整方法,简称TBR(Track-Backupxa0Rescheduling)方法。该方法的基本思想是:根据原运行图,对每一个受失效站台影响的列车分配一个新站台,而把失效站台(即原运行图的站台,或称原站台)作为冗余备份,如果失效站台在新运行图所规定的列车进站时间内成功修复,则列车使用该站台以避免站台改变成本的发生;否则,列车使用新站台以减少延迟时间。失效站台会影响每一辆原定通过该站台的列车的驶入,以下称为受影响列车。TBR方法对每一辆受影响列车分配一个新站台,而把失效站台作为冗余备份。如果失效站台能够成功修复,则受影响列车继续使用该站台;否则,受影响列车使用新站台进站。相应地,本发明还提供一种基于站台冗余的列车运行图调整系统,包括地面信号系统、调度中心、车载信号系统和车站,该系统用于当原站台失效时,对原运行图进行调整生成新运行图,该新运行图对每一辆受影响列车分配一个新站台;以及,用于如果所述原站台被成功修复,则所述受影响列车继续使用该原站台,否则,所述受影响列车使用所述新站台。图1为本发明的列车运行图调整系统所执行的方法流程图,具体步骤如下:步骤一、所述地面信号系统向所述调度中心报告所述原站台的失效信息,该失效信息包括失效的所述原站台的编号及其预估维修时间,该预估维修时间即为预估失效时间,该时间为随机变量;步骤二、所述调度中心对原运行图进行调整,生成一个无冲突的新运行图,并将其发送给所述车载信号系统与所述车站。其中,新运行图给每一辆受影响列车分配一个新站台,所述无冲突是指不会引起列车相撞等事故;步骤三、所述车载信号系统与所述车站分别将运行图调整所引发的列车延迟信息通知给司机与候车乘客;步骤四、所述调度中心根据新运行图,对每一辆受影响列车设定一个通知时刻,该通知时刻为新运行图所规定的列车进站新时刻与乘客更换站台所需时间的差;步骤五、所述地面信号系统在该通知时刻向所述调度中心报告原站台的维修情况,也就是原站台是否已经修复的情况;步骤六、如果失效站台已经修复,所述车载信号系统将接收到所述调度中心指令,通知司机按原运行图进站。否则,新站台将启用,所述车载信号系统将接收到所述调度中心指令,通知司机按新运行图进站。所述车站的广播系统也将通知车站候车乘客更换站台,乘客在规定时间内更换站台。由于上述步骤二中,列车运行图调整是交通优化管理的重要组成部分,将原运行图生成新运行图是一个非常复杂的数学优化问题。本发明一方面由于考虑到了失效时间的随机性,需要增加所述预估失效时间(用ξ表示)这一随机变量,另一方面由于站台冗余的备份所产生的站台更换成本与上述随机变量有关,因此如何将本发明的TBR方法抽象成为数学模型是进一步需要解决的技术问题。为解决这一问题,进一步地,本发明列车运行图调整系统中的所述调度中心包括一种运行图生成装置,图2为该运行图生成装置的结构示意图,该装置包括建模单元、计算单元和新运行图生成单元。所述建模单元用于建立随机优化模型来模拟运行图的调整。该随机优化模型为一种混合整数规划模型。下面分别对该模型中表征各量的符号、约束条件、目标函数进行说明:其中,轨道线路上包括车站与站间,以下将其统称为区间。符号系统:i列车,i=1,2,...,Ij区间,j=1,2,...,Jt站台(或称为侧线)m_j区间j侧线的数目d_ij列车i到达区间j的单位延迟成本c_ij列车i在区间j的单位站台改变成本n_ij在区间j等待列车i的乘客数量a_ij乘客在区间j换乘所需时间q_ijt原运行图中,如果列车i在区间j被指站台t,那么q_ijt=1;否则,q_ijt=0 ntent="drawing" img-format="tif" inline="yes" orientation="portrait" wi="74"/>原运行图中,列车i驶入区间j的时刻 ntent="drawing" img-format="tif" inline="yes" orientation="portrait" wi="56"/>原运行图中,列车i驶离区间j的时刻o_i列车i的始发站d_i列车i的终点站 ntent="drawing" img-format="tif" inline="yes" orientation="portrait" wi="93"/>列车i在区间j的最小操纵时间,在车站所述最小操纵时间表示最小停站时间,在站间所述操纵时间表示最小运行时间Δ_j安全时间间隔,车站,即,前车离开车站Δ_j时间后,后车方可进入H_j安全时间间隔,站间,即,后车与前车的时间间隔ξ_t站台t的失效时间,随机变量,其密度函数是φ(y),y∈[l_t,u_t],其中,l_t与u_t分别表示最小与最大可能失效时间 ntent="drawing" img-format="tif" inline="yes" orientation="portrait" wi="62"/>列车i驶入区间j的时刻,为决策变量 ntent="drawing" img-format="tif" inline="yes" orientation="portrait" wi="61"/>列车i驶离区间j的时刻,为决策变量p_ijt如果列车i在区间j被指派站台t,那么p_ijt=1;否则,p_ijt=0r_ilj如果列车i早于列车l进入区间j,那么r_ilj=1;否则,r_ilj=0约束条件:约束条件包括列车驶离驶入时刻约束、最小运行时间约束、最小停站时间约束、列车离站时刻约束、列车运行次序约束、安全距离约束、决策变量范围和TBR约束,具体如下所示:(1)列车驶离驶入时刻约束,列车i驶离区间j的时刻应该等于进入区间j+1的时刻,即, x ij e = x i ( j + 1 ) s , ∀ o i ≤ j ≤ d i , 1 ≤ i ≤ I . ]]> (2)最小运行时间约束与最小停站时间约束,列车i在区间j的操纵时间应该满足以下约束 x ij e - x ij s ≥ d ij min , ∀ o i ≤ j ≤ d i , 1 ≤ i ≤ I . ]]> (3)列车离站时刻约束,列车i驶离车站j的时刻应该大于原运行图所规定时刻,即, x ij e ≥ o ij e , ∀ j = o 2 , o i + 2 , . . . , d i , 1 ≤ i ≤ I . ]]> (4)列车运行次序约束,列车i与列车l驶入区段j的次序约束: ntent="drawing" img-format="tif" inline="no" orientation="portrait" wi="700"/> 如果ntent="drawing" img-format="tif" inline="yes" orientation="portrait" wi="197"/>那么ntent="drawing" img-format="tif" inline="yes" orientation="portrait" wi="173"/>并且ntent="drawing" img-format="tif" inline="yes" orientation="portrait" wi="159"/>对于任意t<m_j;如果 r i 1 i 2 j = 1 , ]]>那么 r i 2 i 1 ( j + 1 ) = 0 ; ]]>如果 r i 1 i 2 j = 1 ]]>并且 r i 2 i 3 ( j - 1 ) = 1 , ]]>那么 r i 3 i 1 ( j + 1 ) = 0 . ]]>(5)安全距离约束,列车l与列车i相继驶入同一区间应该满足安全距离约束,即, ntent="drawing" img-format="tif" inline="yes" orientation="portrait" wi="700"/>其中,M是一个很大的正整数,例如,1000。(6)安全距离约束,列车l与列车i相继驶入同一车站应该满足以下约束, ntent="drawing" img-format="tif" inline="no" orientation="portrait" wi="700"/> (7)决策变量范围,决策变量ntent="drawing" img-format="tif" inline="yes" orientation="portrait" wi="58"/>和ntent="drawing" img-format="tif" inline="yes" orientation="portrait" wi="56"/>应该满足以下约束: x ij e , x ij s ≥ 0 , ∀ o i ≤ j ≤ d i , 1 ≤ i ≤ I , ]]> p ijt ∈ { 0,1 } , ∀ o i ≤ j ≤ d i , 1 ≤ t ≤ m j , 1 ≤ i ≤ I , ]]> ntent="drawing" img-format="tif" inline="no" orientation="portrait" wi="700"/> (8)TBR约束: Σ t = 1 m j p ijt ≥ 1 , ∀ o i ≤ j ≤ d i , 1 ≤ i ≤ I . ]]> x ij s ≥ min 1 ≤ t ≤ m j ( u t p ijt + M ( 1 - p ijt ) ) , ∀ o i ≤ j ≤ d i , 1 ≤ i ≤ I . ]]> 目标函数:所有列车驶离所有车站的延迟成本: D ( x , p , r ) = Σ i = 1 I Σ j = o i d i d ij max { x ij s - o ij s , 0 } . ]]> 站台更换成本: C ( x , p , r ) = Σ i = 1 I Σ j = o i d i Σ t = 1 m j Σ s = 1 m j q ijt p ijt c ij n ij d ( t , s ) Pr { ξ t ≥ x ij s - a ij } . ]]> 随机优化模型: min D ( x , p , r ) + C ( x , p , r ) s . t . Constraints ( 1 ) - ( 8 ) ]]> 从上述该混合整数规划模型可以看出,该模型包括数以万计的决策变量与约束条件,致使经典的混合整数规划算法难以满足计算时间的要求。如何在短时间内求解出一个令人满意的调整方案成为进一步需要解决的技术问题。优选地,除所述建模单元外,本发明所提供的所述运行图生成装置还包括计算单元,该计算单元用于利用基于贪婪算法的遗传算法对所述随机优化模型求解最优调整策略。其中,所述基于贪婪算法的遗传算法包括以下步骤:步骤S1、随机生成初始种群,令k=1,其中k表示遗传算法代次,k=1,2,...,K,K表示遗传算法迭代总次数;步骤S2、针对每一个个体,应用贪婪算法计算列车驶入、驶出车站的时刻与次序,进而计算该个体所对应的目标值,评估个体的适应度,即步骤S21、定义j=1;步骤S22、设计贪婪算法求解列车驶入、驶离第j个车站的时刻与次序,令j=j+1;步骤S23、如果j≤J,重复所述步骤S22;步骤S3、通过选择、交叉、变异更新种群,令k=k+1;步骤S4、如果k≤K,转到S2;步骤S5、返回目标值最小的个体作为最优解。上述步骤S22中所述贪婪算法求解的过程具体为:步骤S221:在所述最小运行时间约束、所述列车离站时刻约束和所述TBR约束条件下,计算所有列车驶入j站的可能时刻: Z ij s = max { O ij s , x i ( j - 1 ) s + d ij min , min 1 ≤ t ≤ m j ( u t p ijt + M ( 1 - p ijt ) ) } ]]> 指定具备最小可能时刻的列车驶入j站,该车的驶入、驶离时刻分别为 x ij s = z ij s , x ij e = max { o ij e , x ij s + d ij min } ; ]]> 步骤S222:在所述最小运行时间约束、所述列车离站时刻约束、所述列车运行次序约束、所述安全距离约束和所述TBR约束条件下,计算剩余列车驶入j站的可能时刻,指定具备最小可能时刻的列车驶入j站;步骤S223:如果所有列车均已安排进站,贪婪算法求解终止。否则,转至步骤S222。另外,如图2,所述运行图生成装置还包括新运行图生成单元,用于通过所述计算单元的计算过程获得的所述随机优化模型的最优解生成新运行图。实施例如图3为一段铁路包括三站二区间,每一个车站包括两个站台。有三列火车由车站1驶向车站3,另有一列火车由车站2驶向车站3。表1、原运行图 ntent="drawing" img-format="tif" inline="no" orientation="portrait" wi="700"/> 原运行图如表1所示。其中安全时间间隔等于H=Δ=5min。如果用u表示原运行图所规定操纵时间(指车站操纵时间或站间操纵时间),那么最小停站时间等于u-3,最小区间运行时间等于u-5,即在车站ntent="drawing" img-format="tif" inline="yes" orientation="portrait" wi="264"/>在站间 d ij min = u - 5 . ]]>步骤一、当第一车站第一站台因设备故障失效,地面信号系统向调度中心报告第一站第一站台的失效信息,所述失效信息包括该站台的编号“11”及其预估失效时间ξ₁₁,比如ξ₁₁为取值于[8:40,9:20]的均匀分布随机变量。步骤二、调度中心调整运行图,生成新运行图。具体地,把编号为“12”第一车站第二站台指派给列车1并把第一站台“11”作为其冗余备份。由于列车1、2、3可能进站时刻分别是9:00,9:05,9:20,根据贪婪算法,因为列车1的驶入第一站台的所述可能时刻最小,所以列车1第一个驶入车站,进站时刻是9:00,出站时刻是9:10。根据TBR方法,如果站台1在9:00时故障修复,列车1将占用站台1,否则,列车1将占用站台2。当列车1占用站台2时,基于所述安全时间间隔约束,列车2的进站新时刻应该在9:15进站,占用站台2。根据所述最小停站时间约束,列车2将停站时间缩短为7分钟,在9:22驶离第一站。此时,剩余列车仅有列车3,根据所述安全距离约束,列车3将在9:27驶入第一站。由于站台2无故障,根据TBR方法,列车3仍然占用第2站台,进一步根据所述最小停站时间约束,列车3在9:34驶离第一站。现在讨论列车在第二站的驶入、驶出时刻与次序。根据所述列车运行次序约束,列车1在10:00第一个进站并占用第一站台。为了减少延迟,列车2在第一站与第二站之间采用最小运行时间,在10:07进入第二站台。现在我们需要在列车1与列车2之间选择哪列车优先驶离。因为列车1可能驶离时间10:15小于列车2可能驶离时刻10:20,所以根据贪婪算法,列车1首先驶离车站2,时刻是10:15。然后,根据所述安全距离约束,列车3在10:20驶入第一站台。再一次,我们需要在列车2与列车3之间选择哪列车优先驶离。这一次,由于列车2的可能驶离时刻10:20小于列车3的可能驶离时刻10:35,所以根据贪婪算法,列车2首先驶离该车站,时刻是10:20。列车4在10:35驶入第二站台。再次,根据贪婪算法,由于列车3的可能驶离时刻10:35小于列车4的可能驶离时刻10:50,所以列车3先驶离该车站,时刻是10:35。最后,列车4最后驶离该车站,时刻是10:50。相似地,可以计算列车驶入、驶出第三车站的时刻与次序。新列车运行图见表2。表2、新运行图 ntent="drawing" img-format="tif" inline="no" orientation="portrait" wi="700"/> 应当理解,以上借助优选实施例对本发明的技术方案进行的详细说明是示意性的而非限制性的。本领域的普通技术人员在阅读本发明说明书的基础上可以对各实施例所记载的技术方案进行修改,或者对其中部分技术特征进行等同替换;而这些修改或者替换,并不使相应技术方案的本质脱离本发明各实施例技术方案的精神和范围。本发明的保护范围仅由随附权利要求书限定。