基于遗传算法的列车调度仿真研究

基于遗传算法的列车调度仿真研究

高速铁路采用“一台快线”的运输模式，运营密度大，运营速度快。列车在行驶过程受到的不确定外界干扰(如风、雨、线路设备故障等)往往会造成众多的列车晚点,给列车运行调整带来较大的困难。与既有线的行车调度相比,高速铁路的行车调度具有高实时性和整体性两大特点。高实时性:列车的高速运行要求行车调度系统在尽可能短的时间内对异常情况做出判断。整体性:高速铁路上运行的高速列车和中速列车均为旅客列车,因此高速列车的行车调整策略不能采用高速列车无限占用中速列车时间资源的调整策略,对于高速铁路的列车调整必须全盘考虑,以保证列车安全正点运行。对于既有线的列车运行调整算法,国内众多学者进行了详细地研究,在理论上提出了各种不同的调整策略和调整模型。文献将列车运行调整问题看作一类有序加工的动态工件调度问题,对列车运行调整进行了分析,并建立了以列车运行时间为优化目标的数学模型。数学模型在理论上具有一定的意义,但却忽略了一个重要的方面:列车运行调整的目标不应单纯以列车的运行时间为优化目标,而应该以列车计划运行图为目标,保证调整后的列车能够尽可能地“按图行车”,以减少列车的晚点时间。文献在利用离散事件动态系统理论的基础上,建立了调整系统事件驱动的状态空间模型,用分层决策和滚动优化的方法设计了调整的通用算法。该算法在理论上具有重要的意义,但不适合高速铁路的行车调度,原因是算法所采用的分层决策有可能造成中速列车无限避让高速列车的局面。文献分别基于图论和模糊决策理论提出了不同的调整算法,但这些算法在实现时均具有相当大的难度。对于高速铁路的列车运行调整算法,国内的学者也进行了研究,但基本上只是基于决策支持系统思想提出了一些调整原则,并没有明确提出优化目标及相应的优化模型。本文在对高速铁路列车运行调整问题进行分析的基础上,以计划运行图为优化目标,提出基于遗传算法的行车调整优化模型,并在高速铁路综合调度仿真系统中进行应用。1行车调整问题的分类高速铁路列车运行调整涉及到工务、电务、机务、车辆以及运输等众多部门,它不但涉及到列车的运行状态、线路状况、铁路沿线的气候以及众多部门,而且涉及到有关规章制度,如计规、调规及站细等。可以说调度工作是运输生产过程与各种有关规章制度相结合的体现,是一项必须有人工参与的复杂工作。在理想情况下,每列列车按照计划运行图给定的时刻表运行以完成运输生产任务。但在实际的运输生产过程中,不可避免地发生一些难以预料的情况,例如机车车辆故障、固定设备故障、铁路沿线恶劣的气候、中速列车上线晚点等。这些难以预料的情况往往导致列车不能按照预定的时刻表运行,甚至导致全线停车等。高速铁路行车调整的工作目的就是当列车运行秩序发生紊乱时,通过对列车进行调整来恢复列车的运行秩序,尽量保证列车按图行车,做到“接晚不增晚,晚点赶正点”。根据外界因素对列车造成晚点的严重程度,可将调整问题分为2种情况。①不可恢复的晚点情况:例如,由于线路遭到破坏而造成的列车晚点、具有破坏性的自然灾害(如地震)而造成的全线停车等情况。②可恢复的晚点情况:外界因素对列车造成晚点的严重程度比较轻微,调度员可以通过在区间“赶点”而恢复列车的正常运行。对于第1种情况,行车调整问题是一个非结构化问题,要建立一个能够对其进行描述的数学模型是比较困难的事情,可采用专家系统或者决策支持系统的方法进行解决。对于第2种情况,行车调整问题实质是根据列车的运行情况重新确定列车时刻表的问题。运输部门在编制列车计划运行图时已对生产效率、设备利用率、区间通过能力等进行了充分的考虑,因此在重新确定时刻表时不必考虑效率问题,只需考虑在安全的基础上如何使得调整后的运行图尽可能地接近计划运行图。2行车调整问题的建模定义下列标识。m:调度区段内的车站数。n:在调整时间段内参与调整的列车数。g*:计划运行图。g*={(ga*i‚j‚gd*i‚j)|i=1‚2‚⋯‚ng∗={(ga∗i‚j‚gd∗i‚j)∣∣i=1‚2‚⋯‚n;j=1,2,…,m},其中ga*i‚ja∗i‚j,gd*i‚j分别表示列车i原计划在车站j的到达时刻和出发时刻。G:所有运行图所构成的集合。G={g|g为运行图},其中g={(gai‚j‚gdi‚j)|i=1‚2‚⋯‚n;j=1,2,…,m},gai,j,gdi,j分别表示列车i在车站j的到达时刻和出发时刻。定义∀p,q∈G,定义p,q之间的距离d(p,q)如下:d(p‚q)=n∑i=1m∑j=1√(pai‚j-qai‚j)2+(pdi‚j-qdi‚j)2可以证明,上述定义的距离满足以下3个条件:1)对于∀p,q∈G,有唯一确定的实数d(p,q)与之相对应;2)d(p,q)≥0,d(p,q)=0的充分必要条件为p=q;3)d(p,q)≤d(p,r)+d(r,q),对∀r∈G。可见,集合G在上述定义下为度量空间,完全可以利用距离d(p,q)对2个运行图之间的差距进行度量。在上述定义下,可将行车调整问题转换为如下的数学问题:f=min∀p∈Gd(p‚g*)列车运行调整问题即是在运行图空间中寻找一个运行图,该运行图与计划运行图之间具有最小的距离。考虑到高速铁路上列车的运行等级,加入权重因子,定义行车调整的优化模型如下:minf=n∑i=1m∑j=1ωi⋅√(pai‚j-ga*i‚j)2+(pdi‚j-gd*i‚j)2(1)式中:ωi为列车i的权重因子,ωi>0,ωi越大,表明列车i的级别越高;pai,j,pdi,j为优化变量。按照列车的发车时刻不能早于计划发车时刻的规定,有pdi,j≥gd*i‚j(j=1,2,…,m)(2)设sti‚j={1‚t时刻列车i占用或者即将占用车站j的一条到发线0‚其他根据股道数量约束,有n∑i=1sti‚j≤Dj(j=1‚2‚⋯‚m)(3)式中:Dj为车站j的到发线数量。根据列车在区间的运行时分,有式中:Tmin为列车i在区间[j,j+1]的最小运行时分。根据追踪运行间隔时间的要求,有|pdi‚j-pdk‚j|≥Ιz(i≠k‚j=1‚2‚⋯‚m)(5)式中:Iz为最小追踪列车间隔时间。根据维修天窗的时间要求,有或式中:tb,te分别为维修天窗的开始时间和结束时间。式(1)—式(6)表明,列车运行调整问题实质上是优化问题。优化模型的目标函数为式(1),约束条件为式(2)—式(6)。3非线性优化问题由上述分析可知,列车运行调整问题实质上是一个有约束的非线性优化问题。传统的优化方法由于采用梯度技术而受到许多局限。因此,本文在对数学模型改进的基础上,提出一种基于遗传算法的调整模型。3.1代表个别时段所通过的秒数列车运行调整问题实质上是重新确定列车时刻表的过程,即重新确定式(1)中的变量。为简单起见,可用从午夜零点到某个时刻所经过的秒数来代表某个时刻,例如,4000代表01:06:40。因此,对于列车运行调整问题,可采用染色体整数编码,编码格式如图1所示。在这种编码格式中,染色体的最大长度为2nm。3.2约束条件式的认定适应度函数是对染色体适应环境能力的评价函数,一个染色体的适应度值越大,表明该染色体的适应环境的能力越强,即性能越好。在定义适应度函数之前,首先对约束条件进行处理。按约束条件式(2)要求,列车在车站的出发时间不能早于计划发车时间。根据目标函数可以证明列车的出发时间越接近计划出发时间,则调整计划图越接近计划运行图。因此,对于约束条件式(2)可以采取罚函数的方法进行处理。约束条件式(3)—式(6)与约束条件式(2)不同,对于约束条件式(3)—式(6)只有2种情况:要么满足,要么不满足。凡满足约束条件式(3)—式(6)的调整运行图都有可能成为最优的调整运行图。因此,对于约束条件式(3)—式(6)必须加以改进,以适应遗传算法。对于约束条件式(3),定义函数:f1={0‚n∑i=1sti‚j≤Dj(j=1‚2‚⋯‚m)Μ‚其他对于约束条件式(4),定义函数:f2={0‚pai‚j+1≥pdi‚j+Τmin(i=1‚2‚⋯‚n；j=1‚2‚⋯‚m)Μ‚其他对于约束条件式(5),定义函数:f3={0‚|pdi‚j-pdk‚j|≥Ιz(i≠k‚j=1‚2‚⋯‚m)Μ‚其他对于约束条件式(6),定义函数:f4={0‚pai‚j‚pdi‚j≤tb或pai‚j‚pdi‚j≥te(i=1‚2‚⋯‚n；j=1‚2‚⋯‚m)Μ‚其他式中:M为正整数。在定义f1—f4的基础上,定义适应度函数如下:f(→p1‚⋯‚→pi‚⋯‚→pn)=Cmax-n∑i=1m∑j=1ωi√(pai‚j-ga*i‚j)2+(pdi‚j-gd*i‚j)2-wn∑i=1m∑j=1(pdi‚j-gd*i‚j)sgn(pdi‚j-gd*i‚j)-f1-f2-f3-f4式中:Cmax为计算机所能表达的最大正实数;→pi=(pai‚1‚pdi‚1‚⋯‚pai‚m‚pdi‚m)‚i=1‚2‚⋯‚n;w为约束条件式(2)的惩罚因子;sgn为符号函数。实际上,对约束条件式(3)—式(6)的处理也是采用了罚函数的方法:要么不进行处罚,要么进行处罚,惩罚因子为M。3.3交叉处理交叉算子是遗传算法区别于其他算法的主要特征,它是产生下一代群体的主要方法。根据编码格式,采用两点交叉算子,如图2所示。3.4变异算子群体经过多次交叉以后,群体中的染色体经常会趋于单一而产生过早收敛的现象。为克服这种现象,可采用变异算子。变异算子的作用是以一定的概率使染色体中的某些基因发生突变,以增加群体中染色体的多样性。根据染色体的编码格式,定义变异算子:S:p→p+αα∈[-30,30]且α为均匀分布的随机变量。变异算子即以一定的概率对优化变量p加以扰动,扰动的左右幅度不超过1min。3.5复制算子复制算子的目的是根据预先确定的策略在当前群体中选取某些染色体作为下一代群体中的染色体。对于复制算子,可采用赌轮盘的策略进行复制。3.6基于群体遗传模型的运行在确定编码、适应度函数以及3个算子的基础上,基于遗传算法的调整算法流程如图3所示。基于上述所描述的模型,开发列车运行调度仿真子系统。实际使用时的遗传参数设置为:群体的规模