基于Max-Plus代数的列车运行图稳定性分析方法研究.pdf

运 营 管 理2023/07CHINA RAILWAY基于Max-Plus代数的列车运行图稳定性分析方法研究李义国（宁波市轨道交通集团有限公司，浙江 宁波 315101）摘要：列车运行图是行车组织工作的基础，其稳定性关乎整个路网线路的运输效率和运营质量。为评估列车运行图的稳定性，通过分析列车运行间隔限制、接续限制、运行线路限制3类列车运行过程限制事件的逻辑关系，总结出列车运行过程具有典型离散事件动态系统（DEDS）特征；采用Max-Plus代数求解DEDS分析理论，探索Max-Plus代数与运行图限制事件的映射关联，建立列车运行图稳定性分析的Max-Plus代数模型；通过模型计算，求解Max-Plus代数最大特征值及运行余量时间矩阵、延迟传播时间矩阵，并以此定量评估列车运行图稳定性。经过实验算例的建模、计算及指标分析，表明采用Max-Plus代数可以科学评估列车运行图的稳定性。此分析方法可为铁路部门改善运行图铺画质量、降低晚点造成的影响，提供有效的参考。关键词：列车运行图；稳定性；Max-Plus代数；模型；矩阵中图分类号：U292.4+1 文献标识码：A 文章编号：1001-683X（2023）07-0097-07DOI：10.19549/j.issn.1001-683x.2023.03.28.0040 引言 列车运行过程中，其运营质量的好坏是铁路管理部门和学术研究者关注的重点。在评估路网线路运营质量时，具有一定稳定性的列车运行图是其中一个重要指标。稳定的列车运行图不仅有助于提高运输效率和保证运营质量，还可以确保列车在发生延误后的运输能力不会受到显著影响。相反，不稳定的列车运行图可能会影响后续列车行驶，即后续列车的运行会受到前1辆列车延迟的影响，导致整个路网线路的运营质量下降，从而降低运输效率。国内外在早期研究中主要采用仿真计算、排队论、概率统计等方法来评估、调整列车运行图的稳定性。陈军华等1针对列车区间运行以及车站联锁控制，建作者简介：李义国（1974），男，高级工程师。Email：liyigou_-97基于Max-Plus代数的列车运行图稳定性分析方法研究 李义国运 营 管 理2023/07CHINA RAILWAY立相应的着色赋时Petri网模型，对列车运行图的稳定性进行了评估。马驷等2运用MATLAB软件进行仿真分析，研究列车运行干扰和冗余时间对运行图稳定性的影响。Hensen3通过排队论方法的应用，科学评估了列车运行图的稳定性。Herrmann4运用概率统计中的参数估计、概率分布分析等办法，对列车站内进路优化生成问题以及列车运行图稳定性分析进行了深度探讨。马建军等5运用概率统计方法构建了列车运行图指标评价体系来研究运行图稳定性。查伟雄等6使用数理统计中的参数估计方法，对列车区间运行缓冲时间的影响进行了深入分析。这些研究为列车运行图编制和优化提供了重要参考，大大推进了列车运行图稳定性的分析。自1998年Goverde7提出可采用Max-Plus代数分析列车运行图的稳定性，以及在2005年Goverde8更进一步阐述清晰列车运行图稳定性分析问题的内涵，通过Max-Plus代数根据用户需求编写指定的软件，采用Max-Plus代数对列车运行图的稳定性研究分析，逐渐成为探讨该问题的研究热点。杨意坚等9在列车运行图稳定性评估中引入Max-Plus方法，并提出一些定量评价指标。王昕等10采用Max-Plus代数建立相关列车运行图的状态动力学方程，实现对高速铁路列车运行图的鲁棒性定量分析。刘宇等11基于Max-Plus代数方法，对长三角城际铁路网的晚点传播进行了探讨。戴杨铖等12基于Max-Plus代数的时刻表递推思路，探讨高速铁路列车运行调整的优化策略。上述研究从多方面，对采用Max-Plus代数方法分析优化列车运行图进行了探索。基于这些研究的启示，在分析列车运行过程限制条件的基础上，采用Max-Plus代数将列车运行图模型化，定量评估运行图稳定性，为铁路部门提供相关参考，以保障和优化列车运营质量。1 列车运行过程的限制事件 在铁路运输过程中，列车运行必须遵循列车运行图，它是一份重要的技术文件，刻画的是列车在运行过程中的时间与空间关系。通过二维线条描述了区段内每列列车占用程序和区间运行时间，以及到达、出发、停站时间等信息13。列车运行图的组成要素包括区间运行时间、起停车附加时间、停站时间、车站间隔时间、在自动闭塞区间内的追踪列车间隔时间、在技术站的作业时间以及列车在机务段和折返段所在站的停留时间。基于以上要素，限制事件在只考虑时间的影响下大致可以分为3类。1.1列车运行间隔限制事件在列车的运行过程中，列车运行间隔限制事件可以从进站时间限制、出站时间限制及区间运行限制3个方面来考虑。若Ei，Ej代表列车进站、出站和区间运行的事件，j是i的上一个事件，xi（k），xj（k）表示第k周期中事件发生的时刻，而2事件发生的最小时间间隔为tij，则Ei和Ej需满足：xi(k)xj(k)+tij ，（1）式中：kN。1.2列车接续限制事件2列列车间的相互连接关系称为接续关系14，是为了保证列车连续运行以及旅客顺畅换乘设立的。这些关系包括等候接续、晚点换乘、列车折返等。若Ei，Ej代表此类事件，j是i的上一个事件，且前一个事件的等候时间为tij，则Ei和Ej需满足：xi(k)tij+xj(k-ij)，（2）式中：ij为延迟周期的次数。1.3运行线路限制事件运行线路限制事件包括预定时间限制、单线运行限制、禁止列车在同一轨道越行的限制、站内轨道及站台数限制、列车进出站相关限制等。预定时间限制表示列车只能按照预设时刻出发，一定不能早于运行图所规定的列车运行时刻，否则会影响列车的后续正常运行15。若以Ei代表列车出发事件、di代表图定时间，则有：xi(k)di(k)。（3）其余几种限制条件，只要确定是哪个事件要等候另一个事件，同样可根据其逻辑约束列出其数学限制式，此处不再一一列出。通过对上述3类限制事件内在逻辑分析，可知所有限制事件发生时刻的约束关系可表示为：xi(k)=max(max(tij+xj(k-ij)，di(k)。（4）根据上述内容分析可知，列车运行过程可以建模为一个标准的离散事件动态系统模型（DEDS模型）。-98基于Max-Plus代数的列车运行图稳定性分析方法研究 李义国运 营 管 理2023/07CHINA RAILWAY2 Max-Plus代数及建模 DEDS模型的分析求解方法较多，而采用Max-Plus代数求出矩阵特征值展开相关分析，可以快捷、有效地评估系统的稳定性。简要介绍该方法，以奠定列车运行图稳定性评估模型构建的理论基石。2.1Max-Plus代数理论Max-Plus代数用1个三元组来表示离散事件间的相互 关 系，即Rmax=(R -，)表 示 在 集 合R -上定义的2个运算8，14：ab=a+bab=max(a，b)。（5）另外，定义Rmax的零元=-及单位元e=0。对于任意Max-Plus代数a，b，cRmax，均有如下性质：交换律：ab=baab=ba ，（6）吸收律：a=a=aa=a=，（7）结合律：a(bc)=(ab)ca(bc)=(ab)c ，（8）分配律：a(bc)=(ab)(ac)，（9）其他性质：aa=a ，（10）ak=aaa ，（11）(ab)k=akbk 。（12）Max-Plus 代 数 同 样 适 用 于 矩 阵 的 运 算，定 义Mn（Rmax）为任意元素Rmax的 nn 矩阵集。对于任意矩阵 A=（aij），B=（bij）Mn（Rmax），定义矩阵的AB及AB为：ABij=aijbij=max(aij，bij)，（13）ABij=k=1n(aikbkj)=maxk=1，n(aik+bkj)。（14）定义nMn（Rmax）是的单位元，n中所有元素均为；定义enMn（Rmax）是的单位元，en中eii=e且eij=（ji）。当矩阵的维度不重要或不致误解时，省略下标n，根据定义及性质，可以得到：A2ij=maxk=1，n(aik+akj)，（15）Al=Al-1A=Al-2AA=AAen 。（16）将A，Al进行Max-Plus加运算，用A(k)来表示，即有：A(k)=l=0kAl ，（17）A+=l=1Al=AA2 。（18）2.2运行图稳定性评估模型的建立根据Max-Plus代数理论，上述式（4）所包含的运行图限制事件关系可相应地表示为：xi(k)=j=1n(tijxj(k-ij)di(k)，（19）式中：n为事件发生的总数。针对式（19）引入周期状态矩阵Al11，可得任意p阶Max-Plus线性系统状态方程为：x(k)=l=0pAl x(k-l)d(k)。（20）式（20）所示的任意p阶系统，计算较为繁琐，为此，借鉴Goverde方法8，14，将其转化为1个一阶Max-Plus线性系统多项式：x(k)=Ax(k-1)d(k)，x(0)=x0 ，（21）式中：x(k)=x(k)x(k-1)x(k-p+1)，A=A1A2ApEE=A*0A1A*0A2A*0ApEE ，d(k)=d(k)，x(0)=x0 x1-p 。3 运行图稳定性指标 Max-Plus代数模化运行图后，分析状态约束矩阵A（.）的最大特征值0以及恢复时间矩阵、列车延迟传播时间。以这3个特征量为指标，即可定量分析列车运行图的稳定性。3.1Max-Plus模型最大特征值分析通 过 相 关 理 论16对 Max-Plus 代 数 的 特 性 分析，状态约束矩阵 A（.）的最大特征值 0就是全部线路网络中的最大运行周期。如果 0e。整条运行线路中总缓冲时-99基于Max-Plus代数的列车运行图稳定性分析方法研究 李义国运 营 管 理2023/07CHINA RAILWAY间为：()T-()()T-()0=()(T-0)，（22）式中：（）为运行周期数量，（）为线路运行时间。所以，只有当0T，即0大于运行图的运行周期T时，系统将失去稳定性。这也就是说，在关键线路上没有缓冲时间和附加时间，就无法缓解延迟。意味着该线路上的所有列车都将被延迟，而后续列车的运行也会被传播的延迟影响到。3.2恢复时间矩阵分析一个稳定的运行图，预留了一定量的余量时间。若列车延误出现，余量时间可以用来进行调整和补偿，以确保列车能够尽快恢复正常运行。余量时间的大小可以直接用作量化列车可以承受的延迟时间总量的指标。假设列车运行图中对于任何一个周期内的事件（i，j），其终端活动的时间为di（k-ij）+tij，而新的初始活动预定时间为dj（k），那么，余量时间就是新的初始活动时间dj（k）与终端活动时间di（k-ij）+tij之间的差值。在1个周期性运行图中，其余量时间sij即为：sij=dj(0)-di(0)-tij+ijT 。（23）恢复时间是指在2个事件i和j之间的关键线路上的余量时间。在有向图中，关键线路理论可以计算出恢复时间矩阵8，14，其中任意一个（i，j）对应着多条有向运行线路，被吸收的延迟可以用运行线的大小来表示。在矩阵A（r）中，rij表示从i到j的所有运行线路上的最小余量时间；Pij表示从 i 到 j 的所有线路的集合；对于任何线路 Pij，可以用 （）表示线路的权重；（）表示在线路上的初始标记。基于以上的定义，对于所有的 kN，恢复时间矩阵R=-S+，且rij=min Pijdj(k+()-di(k)-()。（24）根据运行图的周期性，即可得到以下公式：rij=minPij(d0j+(k+()T)-(d0i+kT)-()=minPijd0j-d0i-()+()T=d0j-d0i-max()-()T=d0j-d0i-A+Tij 。（25）3.3列车延迟传播时间分析余量时间矩阵只能显示出初始延迟量和确定后续列车的延迟情况，但无法计算下一辆列车受到前一辆延迟传播所受到的影响程度，以及所产生的次要延迟量大小，也无法计算消除延迟所需的时间。因此，把列车延迟传播时间矩阵作为稳定性分析的另一项指标是非常必要的。可通过以下步骤计算初始延迟传播总量，首先，在初始周期内通过已知的初始状态矢量x（0）确定延迟传播的初始量大小；其次，延迟传播时间可通过列车运行的到达时间减去其预定到达时间计算。故延迟传播模型推算公式如下：d(k)=T d(k-1)x(k)=Al x(k-1)d(k)z(k)=x(k)-d(k)。（26）4 算例分析 为方便理解Max-Plus代数模型分析运行图稳定性的过程，将借助下面的这个算例进行阐述。以某地方单线铁路为例，在此单线铁路上开行方案如下：上行方向从A到C，运行时间段6：0018：00，A、B、C站分别停车，A、C站由于需要整备车辆等作业，停站时间最少需要3 min，B站会让作业最少需要2 min，A站到B站、B站到C站的最小运行时间分别为25 min、24 min；下行方向从 C 到 A，运行时间段6：0018：00，A、B、C站分别停车，A、C站最小停站时间3 min，B站最小停站时间2 min，C站到B站、B站到A站的最小运行时间分别为24 min、25 min。列车运行以12 h为周期，全图总计开行12对列车，每对列车以60 min为循环单元（小周期）占用运行线路。列车计划运行图见图1，其中下行方向比上行方向发车时间晚1 min。通过对列车计划运行图的分析，可使用以下4个事件来评估该运行图的稳定性，将从A到B记作出发事件x1，从C到B、B到A、B到C分别用出发事件x2、x3、x4表示。考虑到各对列车的循环周期性，故以某对列车S13、S31在第k周期占用运行线路的发生事件和运行约束（见表1）为代表展开分析。出发事件x1（k）必须等候前1个周期的出发事件x3（k-1），x3（k-1）的限制时间包括从B到A的运行时-100基于Max-Plus代数的列车运行图稳定性分析方法研究 李义国运 营 管 理2023/07CHINA RAILWAY间和列车在A站的等待时间，即：x1(k)253x3(k-1)。（27）出发事件x1还需满足预定时间限制，x1的图定出发时间为d1（k）=0+k60。所以，得到其满足所有限制条件的Max-Plus代数式：x1(k)=28x3(k-1)d1(k)。（28）同理，x2、x3、x4满足所有限制条件的Max-Plus代数式为：x2(k)=27x4(k-1)d2(k)，（29）式中：d2(k)=1+k60；x3(k)=26x2(k)25x1(k)d3(k)，（30）式中：d3(k)=27+k60；x4(k)=27x1(k)24x2(k)d4(k)，（31）式中：d4(k)=27+k60。将式（28）式（31）用矩阵表示即为：x(k)=25262724x(k)2827x(k-1)d(k)，（32）式中：d（k）=（0，1，27，27）。式（32）仍为多阶线性系统，将其化为一阶DEDS系统，具体做法示例如下：x3(k)=26x2(k)25x1(k)d3(k)=2627x4(k-1)26d2(k)2528x3(k-1)25d1(k)d3(k)=53x3(k-1)53x4(k-1)d3(k)。（33）故有：x(k)=282753535551x(k-1)d(k)，（34）得到状态约束矩阵：A=282753535551 。（35）根 据 相 关 理 论15，求 其 最 大 特 征 值 0=max（53/1，51/1，5355/2）=5460，即0T，所以此系统稳定。进一步分析运行图的稳定程度，利用式（23）计算余量时间，得：s=-5-7-200-2 。（36）根据式（24）、式（25），得恢复时间矩阵：R=-S+=755127912720770259 。（37）矩阵R提供了关于剩余缓冲时间的定量信息，通过分析此矩阵，R的元素r32、r41为0，表示剩余缓冲时间为0；此外，从R的首列数据可以推断，任何从车站A出发且受到干扰的列车运行事件产生的延迟都将会传图1列车计划运行图表1发生事件与运行约束车次S13S31事件x1(k)x4(k)x2(k)x3(k)发站到站ABBCCBBA约束等候k-1周期的x3到达列车同x1(k)，等候k周期的x2到达等候k-1周期的x4到达列车同x2(k)，等候k周期的x1到达-101基于Max-Plus代数的列车运行图稳定性分析方法研究 李义国运 营 管 理2023/07CHINA RAILWAY播到事件x4，若该延迟时间超过2 min，那么会进一步影响到事件x3。假设有2辆车分别从A、C车站出发且初始出发延迟均为12 min，利用式（26）表示的延迟传播模型进行相应计算：x(0)=A*x0=00252602724012132727=12133939，z(0)=12133939-012727=12121212 ，（38）x(1)=2827535355511213393960618787=67669294，z(1)=67669294-60618787=7557 ，（39）x(2)=28275353555167669294120121147147=120121147147，z(2)=120121147147-120121147147=0000 。（40）分析式（38）式（40）中的z（.），可以得到每个周期内各事件的延迟时间，z（2）=0表示列车运行2个周期后，延迟才可以完全被消除。5 结论及展望 通过深入分析列车运行过程的各种限制事件，揭示了列车运行过程即是一个典型离散事件动态系统（DEDS）的本质内涵。利用Max-Plus代数能很好解决DEDS问题的特性，将列车运行图模化成线性离散动态系统；并通过分析该Max-Plus模型状态约束矩阵A（.）的最大特征值0及恢复时间矩阵、延迟传播时间，科学定量地衡量列车运行图的稳定性。该方法对列车运行图的稳定性分析，为铁路部门铺画运行图提供了有效参考，对于改善运行图铺画质量、降低晚点造成的影响，具有重要实际意义。值得指出的是，目前尚未通过分析状态约束矩阵A（.），对任意一点延迟t时间所影响后行列车的数量和时间展开更深层次的研究；针对不同点不同初始延迟时间所传播的长度和广度问题，仍需通过工序统筹图等方法展开更进一步的探索。参考文献1 陈军华，张星臣，徐彬.基于着色赋时PETRI网的运行图稳定性评价研究 J.系统仿真学报，2011，23（4）：770-816.2 马驷，邓云霞.城际铁路列车运行图稳定性仿真分析 J.中国铁道科学，2016，37（2）：122-127.3 HANSEN I A.Station capacity and stability of train operationsC/Proceeding of the 7th International Conference on Computers in Railways.Bologna：WIT Press，2000：809-816.4 HERRMANN M T.Stability of timetables and train routings through station regionsD.Zurich：Swiss Federal Institute of Technology，2006.5 马建军，许红，胡思继，等.京沪高速铁路列车运行图指标评价体系的研究 J.北方交通大学学报，2003（5）：46-50，81.6 查伟雄，熊桂林.列车区间运行时分动态特性研究 J.系统工程，2001（1）：47-51.7 GOVERDE R M P.Max-plus algebra approach to railway timetable design C/Proceedings of the 6th International Conference on Computer Aided Design，Manufacture and Operation in The Railway and Other Advanced Mass Transit Systems.Lisbon：WIT Press，1998：339-350.8 GOVERDE R M P.Punctuality of railway operations and timetable stability analysis D.Delft：Delft University of Technology，TRAIL Research School，2005.9 杨意坚，何宇强.基于Max-plus方法的列车运行图 稳 定 性 评 价J.铁 道 学 报，2009，31（4）：14-19.10 王昕，聂磊，李文俊.基于动车运用的高速铁路列车运行图鲁棒性研究 J.铁道运输与经济，2014，36（11）：50-55.11 刘宇，黄凯.基于极大代数的城际高速列车晚点传 播 研 究J.综 合 运 输，2017，39（9）：68-73，107.-102基于Max-Plus代数的列车运行图稳定性分析方法研究 李义国运 营 管 理2023/07CHINA RAILWAY12 戴杨铖，宋瑞，毕明凯，等.高速铁路列车运行调整策略优化 J.大连交通大学学报，2017，38（6）：12-18.13 胡思继，彭其渊.铁路行车组织 M.北京：中国铁道出版社，2009.14 GOVERDE R M P.Railway timetable stability analysis using max-plus system theory J.Transportation Research Part B：Methodological，2007，41（2）：179-201.15 汤永.列车运行图的稳定性分析 D.北京：北京交通大学，2013.16 陈文德，齐向东.离散事件动态系统-极大代数方法 M.北京：北京科学出版社，1994.责任编辑 王艳丽收稿日期 2023-03-28Research on Stability Analysis Method of Train Working Diagram Based on Max-Plus AlgebraLI Yiguo(Ningbo Rail Transit Group Co.,Ltd.,Ningbo Zhejiang 315101,China)Abstract:Train working diagram is the basis of train operation organization,and its stability is related to the transport efficiency and operation quality of the whole railway network.In order to evaluate the stability of train working diagram,by analyzing the logical relationship between three types of train operation process limitation events:train operation interval limit,connection limit and operation line limit,it is summarized that the train operation process has typical discrete event dynamic system(DEDS)characteristics;Max-Plus algebra is used to solve the DEDS analysis theory,explore the mapping association between Max-Plus algebra and train working diagram restriction events,and establish a Max-Plus algebraic model for stability analysis of train working diagram;through model calculation,the maximum characteristic value of Max-Plus algebra,running margin time matrix and delay propagation time matrix are solved to quantitatively evaluate the stability of train working diagram.The modeling,calculation and index analysis of experimental examples show that the stability degree of train working diagram can be scientifically evaluated by using Max-Plus algebra.This analysis method can provide an effective reference for railway authority to improve the drawing quality of train working diagram and reduce the impact caused by delays.Keywords:train working diagram;stability;Max-Plus algebra;model;matrix-103