（交通信息工程及控制专业论文）城市轨道交通系统的极大代数模型研究.pdf

中文摘要 摘要：通过对城市轨道交通系统的列车运行特点分析发现：城市轨道交通系 统的列车运行过程是一个典型的离散事件动态系统，而且整个城市轨道交通系统 完全可以看作是一条串行生产线，其中系统中的列车可以看作是线上加工的工件， 车站和区间( 或闭塞分区) 则可以看作是线上的加工机器。基于此，本文利用研 究串行生产线比较成熟的极大代数方法建立了一线开环型城市轨道交通系统的数 学模型，并基于该模型对城市轨道交通系统展开了一系列的研究，主要包括： 1 通过对城市轨道交通系统的极大代数模型引入周期输入控制，讨论了在等 发车间隔下的系统可控性、周期稳态特性以及系统无阻塞运行的条件和系 统的鲁棒性，并利用算例验证了相关结论。 2 基于城市轨道交通的极大代数模型，讨论了出站晚点对系统造成的影响， 并基于晚点对系统造成的不同影响制定了相应的调整措施，主要包括列车 的自动调整，多列车的运行参数调整以及抽掉计划运行线等。同时针对线 路故障下的运行调整也给出了一定的调整措旖。 3 通过对发车间隔和列车晚点造成的影响关系分析，讨论了基于晚点理论的 发车间隔的优化设计方法。 该论文的研究结果将对计划阶段的列车运行图的编制以及调度阶段列车运行 图的调整提供一定的理论指导，并为以解析的方法研究城市轨道交通运输组织问 题提供了一种可行的研究方法。 关键词：城市轨道交通；极大代数；周期输入；无阻塞；运行调整；发车间隔； 分类号：u 2 9 2 4 2 a b s t r a c r b v 锄a l y z i n gt h et r a j n s m o v e m tc h 撒c t 撕s t i c so fu i 叫u r b 柚 i h i l1 r 柚s i t ) s y s t e m ，w ef i i i dt h a tt h et r a i ：啮m o v e m e n to fu r ts y s t e mi sat l m i c a l d e d s i s c r e t ee v e n td 1 i r i l 锄i cs v s t e m ) 锄dt h eu r ts y s t e mc 锄b et l l o u g l l to fa sa s e r i a lp r o d u c t i o nl i n e ，o fw h i c ht l l e 仃a i n so fu r ts y s t e ma r ct h o u 曲to fa si o b sa n dt l l c s t a t i o n sa n ds c c t i o n s 佃rb l o c ks e c t i o n s ) o ft h eu r ts y s t e m 砌et h o u 曲to f 弱 m a c h i n e sh e n c et h em a xa 1 日e b r aa p p r o a c ht l l a th a sb e e nw i d e l yu s e di nt h e p e 一 b m 柚c c 柚a l y s i so fs e r i a lp r o d u c t i o nl i n ei sa p p l i e dt ob u i l du pt h el i i l e a r - s y s t e m m o d e lo ft r a i n s m o v e m e n to fu i 一书中系统总结了极大代数的数 学理论。法国学派在7 0 年代至年代对双子( d i o i d ) 代数结构及双子上的线性 代数做了系统研究，极大代数是双子的特例。法国自动控制与应用数学专家 g c 0 h e n 博士等人在上述科学家工作的基础上，从年代初开始，以极大代数为 工具，系统研究了离散事件动态系统( d e d s ) 的线性系统理论。d e d s 本来是复 杂的非线性系统，但经过适当的建模，g c 铀曲等人把它看成了建立在极大代数上 的线性系统。g c o h e n 博士等人的论文【1 2 l 于1 9 8 5 年在著名的刊物e e ，t r a n s a c 上发表盾，引起了控制理论界广泛的关注与兴趣。荷兰控制理论专家g j o l s d e i “1 r 教授在这个领域做了大量工作；g c 0 h e n 等人则继续他们的工作，其中涉及到了极 大代数以外的几类双子的应用，并开拓了2 d 域方法，“频率”域方法等。我国学 者从8 0 年代后期至今也在这个领域做了大量的研究工作。目前，极大代数方法已 成为d e d s 研究方法三个层次的代数层次中的一个主要方法，并有重要理论价值 与应用前景。 离散事件动态系统( d e d s ) 的第一个重要问题是建模。建模有多种方法，极 大代数方法建模的优点是可以建成与传统线性系统理论的( a ，b ，c ) 模型相对应的模 型，只不过这里不是传统域上的线性系统，而是极大代数这种特殊的没有减法的 代数结构上的线性系统。d e d s 本身是极为复杂的非线性系统，因而g c o h 等人 把极大代数的建摸方法称为伪线性方法。这个模型是最接近数学理论的模型。在 研究方法上也可仿效传统做法，得出能控、能观、周期等指标，也可通过引入反 馈在一定范围内任一配置周期，从而达到控制生产率的目的。 总之，使用极大代数方法建模已经取得相当多的成果。但是由于极大代数本身 没有减法，同时由于研究方法也仅局限在沿用传统的w b h 卸d o m 几何理论，研究 难度大，相对于传统的线性系统，成果要逊色的多。同时并非所有的离散事件动 态系统都可以用极大代数来描述，可建成这样的模型的系统有一定的特殊性。 北京交通大学硕士学位论文 对于城市轨道交通问题一般都是利用排队论进行研究的，但是这种方法比较 复杂，而且不易理解，所以本文利用极大代数方法研究城市轨道交通问题，建立 数学模型，从控制理论出发来研究城市轨道交通的运输组织问题，使问题更清楚 明白，便于理解下面介绍极大代数的基础知识。 2 2 极大代数基础知识 2 2 ，1 极大代数 “极大代数”是一类特殊的代数结构，c u n i n g l l 枷c 一渐湖把它称为“极小代 数”，也有学者把它称为“双子代数”。本文摘录c o h 强及陈文德引入的有关概念 和理论【1 0 1 嘲l 。 定义2 4所谓的极大代数，是指定义在r 的一组二元运算： 口0 6 - m 戤( 口，6 ) 口6 = 口+ 6v 4 扫i 其中面。尺u ) ，；一，+ 是一般意义下的加法。令d 一 - ，。， ，则称d 为一个极大代数。 可以看出，和0 分别是d 的加法零元和乘法的单位元，对于加法它是一个 半群，没有逆运算，即没有减法。 与线性代数相似，我们可以定义极大代数上的矩阵的加法和乘法。设d ”表 示极大代数上所有mx 以矩阵组成的集合。 定义2 s 设4 ，日d “”，a 一( 口；f ) ，矗一蛾) t 则4 0 b 一0 # 0 6 b ) 。 定义2 6 设4 ”，b ”，则棚。瓴) 其中：c 口一o 口* 6 材- 口j 1 吒，o 口j 2 6 2 j o o4 驴 相应的，方阵爿的詹次幂为- 州h 1 。方阵彳的4 运算定义如下： 4 = e 0 4 0 彳o 。o - 4 p 。1 ( p = d i n a ( 功； 定义2 7 设口r ，彳d ”，则纯量与矩阵相乘定义为：日4 = 0 ) 结论2 1 设e d ” e = o ， 占，o ， ，0 2 极大代数预备知识 则e 是d 上的n 阶单位矩阵。 定义2 8 设4 d 。”，若存在曰d “，满足4 口一删，e 则称矩阵a 可逆，b 称为a 逆矩阵，a 的逆通常记为4 1 2 2 2 有向图分析法 离散事件动态系统的动态行为，特别是周期性稳态过程行为，是由系统在极 大代数上的特征结构所决定的。在极大代数框架下，对系统特征结构的分析是以 有向图的概念和特性为基础的为此，首先给出有向图的一些基础知识 定义2 9 一个赋权有向图可用一个三元组g p ，4 ) 来表示，其中u 表示 节点集，可用自然数1 ，2 ，n 对图中所有的n 个点进行标号。y 是弧集，用g d 表 示点f 到点j 有弧，图中所有弧的权重用集合口表示，口甘表示弧( f ，j ) 的权重 定义2 1 0 若存在k 个点亏l ，之，对任意l p c 七，点f ，和+ ，之间有弧 酢，。) ，则称，( ，f 2 ) 之，也，) ，( f i 。，) ，t 为到的一条有向通道，简记为 ，乞，t 。通道上弧的条数k 称为通道的长度。如果和f i 为同一个点，则称通道 为闭通道。如果闭通道中的所有点都不相同，则称它为一个回路。如果点f 到其自 身有一条弧( f ，f ) ，则称o ，d 为一条自回路。 定义2 1 l 如果图中任意两个不同的点f 和，从f 到f 以及从，到f 都有路， 则称图是强连通的。所有具有强连通关系的点以及它们之间的弧放在一起构成子 图成为图的一个强连通分支。 定义2 1 2 称矩阵4 d ，为图g 缈，y ，4 ) 的关联阵。 f ，如果f 珊有弧( i ，j ) 、” l e ，否则 则图g ，y ，口) 和a 有一一对应关系，简记为g 似) 。 定义2 1 3 称通道上所有弧的权重在极大代数意义下的积为路的权重。称 路的权重除以它的长度为这条路的平均权重。 定义2 1 4 称强连通分支中平均权重最大的回路( 一定存在) 为这个强连 通分支的临界回路。 结论2 2 设4 d “”，则对所有的i ，( 1 s f ，s 玎) 和r2 1 ，有： 似7 b - 哆 ， 其中p 是g o ) 中从f 到，的任一条长为，的路，耽表示这条路的权重。 结论表明的第所亍第j 列上的元素等于g 似) 图中f 到j 的任一条长为，的路 径中具有最大权重的路径的的权重 北京交通大学硕士学位论文 定义2 1 5 如果图g o ) 是强连通的，则称为爿不可简约的，否则称4 为可 简约的如果图中只有一个点，不管它是否含有自回路，都认为是不可简约的。 结论2 3 设彳d ”，g ) 含有个强连通分支，则存在置换阵，使： b 4 f 一 4 ，4 ：，4 ， 咖4 ，如 咖以”4 ( 2 1 ) 其中4 ，4 ，也都是不可约的，它们对应g o ) 的个强连通分支，妒是每个 元素都为s 的阵。 2 2 3 极大代数上矩阵的特征问题 极大代数上矩阵的特征向题不仅有理论意义，而且有应用价值。 r a c 岫i i l g l l 枷e g r c e n 首先解决了不可简约矩阵的特征问题。g c o h 锄等人对不可 简约矩阵以及含有两个强连通分支的情况作了分析，陈文德、齐向东解决了一般 可简约矩阵的特征问题。下面分别介绍。 定义2 1 6 设4 ”，如果存在实数a ，a _ f ，以及d 上的n 维行向量 x ，z _ 一，使得 x a ；九x 成立，则称a 为4 的特征值，z 为4 l 拘特征向量，如果x 的每一个分量均不 为，则称x 为a 的有限特征向量。 定理2 1设a d ，a 为a 的特征值，则图g 似) 中至少存在一条回路 其平均权重等于a ，且此回路到所有平均权重大于a 的回路都没有路。 定理2 2令s - 仃l ，g 到任何平均权重比自己大的回路都没有路， 则s 中每一条回路的平均权重都是爿的特征值。 定理2 34 d ，4 的所有特征值可由下列算法求得： 1 找出图g ) 的所有的个强连通分支； 2 找出图g 似) 所有既没有出去的路又没有进来的路的、独立的强连通分 支，即在凝图中是孤立点，共p 个 3 ，取出上面的强连通分支，得余图g + ； 4 找出余图g 中这样的强连通分支，它没有进路，只有出路，共儡个； 5 对这a ，个强连通分支，按照他们的临界回路平均权重由大到小的顺序 进行编号。把其中临界回路平均权重最大的强连通分支编号为g 。( 如果有两 个以上的强连通分支的临界回路的权重相等，则对其中一个先进行编号) ，把 临界回路平均权重次大的强连通分支编号为g 2 + 。，把临界回路平均权重最小的 2 极大代数预备知识 强连通分支编号为瓯+ ，； 6 再去除上述儡个强连通分支及其出去的路，余图中重复过程4 、5 ，直 到最后一个分支g - 。 7 选出g 0 ，吆，g 0 中临界回路平均权重最大的者，设为q ，合并 瓯，g 知，q ，仍记为q ； 8 再在g ，g 中重复过程7 ，直到瓯，得到q ，g - ，6 0 ； 9 把过程2 中找到的p 个强连通分支按从大到小的顺序插入到 ，吒，g 中，仍记为q ，吒，g ； 1 0 把g ) 中点按g - ，g t 。，g 0 的顺序重新编号，这样构成的新图对应 的矩阵有下列形式：只t p 。 4 ，4 ：，气 妒，4 ，如 妒，妒，4 则五，互，互得所有临界回路组成的集合为s ：即若设五，互，互的临晃回 路平均权重分别为 ，九， ，丸，则 ，九，五，是4 的所有特征值，且 z 毛”2 丸 由于求临界回路平均权重的算法已由m k a r p 在1 9 7 7 年得出，定理2 1 、2 2 又从理论上找出了矩阵的所有特征值，再由定理2 - 3 把他们实现为算法，综合起来 可以达到求出矩阵所有特征值的目的。 2 2 4 极大代数意义下矩阵的周期分析 在极大代数意义下，研究离散事件动态系统及其性质，周期分析是不可缺少 的内容，近年来国内外学者作了相当多的工作。g c 0 h e n 等人提出了a 周期的概念， 并在假设4 的任意阶积均是不可简约阵的情况下，得出了一些结论。 定义2 1 7 在极大代数下d 下，若存在a d ，a - * 和正整数，d 使 得4 4 ”；a 4 么“，v ，l 则称4 是d 阶a 周期阵。 对于串行生产线，定义2 1 7 中的各个参量都有非常直观的含义。表示演化 过程的过渡过程节拍数，d 表示稳态周期过程中一个周期内输出的工件产品批量， 表示一个周期的时间，a 表示平均的批稳态周期。这些参数定量的描述了工件 生产的稳态性能。直观含义为，经过个批次后，工件产品的输出进入稳态且呈 现周期过程，输出稳态过程以每d 批而重复，一个周期时间为，即普通的d a ， 北京交通大学硕士学位论文 输出一批工件的平均时间为a 结论2 4设4 是不可简约阵，则爿是周期阵，周期为特征值，阶如下： d - 7 缈 g 暑彳他) ) 其中，d 。是由图中全部的临界回路及他们所包含的点所构成的图g 的第r 个 连通分支中的第s 条特征回路的长，z c 埘表示最小公倍数；窖厶d 表示最大公约数。 结论2 5 若在标准型( 2 1 ) 下，若的对角块，以。均为不可简约阵 或一阶方阵，则4 是 周期阵的充要条件是所有的4 具有相同的特征值，都为a ， 且阶为d ，其中，d f 肋f r 朋位f 矗虻 ，叱是由图4 中全部临界回路及他们所 含的点所构成的图的第r 个连通分支中的第j 条特征或路的长。 2 3 离散事件动态系统的建模 以下介绍陈文德等采用的、o d h c n 等人建立的离散事件动态系统的极大代数模 型。 串行生产线也称为流水生产线，它是一类特殊的制造系统，如图2 1 所示，系 统有两台机器玛和鸭，先有一批工件置，罡，它们都先在鸭上加工，再在上 加工。两台机器加工工件的顺序是一样的，都是先加工号，在加工昱，一 图2 1 一条典型的串行生产线 现假设和小：加工第七个工件的开始时可分别为 ) ，而 ) ，加工时间分 别为f l ( 七) ，f 2 ( 七) ，第七个工件输入到鸭的时刻为“( 七) ，离开的时刻为y ) ，则此 系统可以用一个计时p e t r i 网描述，如图2 2 所示： 1 6 2 极大代数预备知识 图2 2 p c 仃i 网描述 h ) 一f l 一1 h 0 1 ) o 口 ) 而僻) 一f l ) 五 ) o f 2 僻一1 ) 而他一1 ) i y ) 一乞 ) 而 ) 令石 ) - k ) 屯 ) 】，整理并合并上述方程，得： 删“( 篙z 峨卜丁 y ) - 石( 七【f 2 ) j 叫篆罢哦) 一附腓，。 则；z ) i 工伪一1 m 0 ) o u 归( 七) ( 2 2 ) y ) - x ( 七f ) 若( 2 - 2 ) 中的系数矩阵爿( 七) ，口作) ，c 很) 是不随七变化而变化，即为常量，则称 工( 七) i x 一1 ) _ o u 仲) 口 ( 2 3 ) 1 7 3 城市轨道交通系统的建模与分析 3 1 引言 3 城市轨道交通系统的建模与分析 城市轨道交通系统是一种典型的离散事件动态系统( d i s 仃c t ee v e n td y n 锄i c s v s t c m s d e d s ) ，它具有d ) s 的明显特征。列车的运行组织就是处理列车在车站、 区间的关系，规定列车占用区间和车站的时机。正常情况下，不允许列车在区间 停车，所有的技术作业都必须在车站办理。相邻列车问必须保持一定的间隔，因 此，列车的运行过程和列车的出现时机都可以看成是离散的。受非常规情况的影 响，列车占用区间和车站的时机也不是固定的，丽是经常偏离基本运行图，是动 态的。因此，如果以列车占用区间或车站为一个事件，那么，由列车、区间和车 站以及各种技术设备和信联闭设备组成的列车运行系统就是一个离散事件动态系 统。由此可见，离散事件动态系统理论非常适合解决列车运行组织问题。 离散事件动态系统的理论研究近年来引起了国内外学者的高度重视。生产调 度系统、柔性加工系统、计算机系统、交通运输系统等都属于d e d s 。对d e d s 的研究，目前主要集中在系统的建模和分析上。对系统的构模方法由时问域上的 状态空间法发展到事件域上的状态空间法，再到同时面向事件和状态的事件驱动 的状态空间模型。面向事件的空间模型更接近于系统的自然特性，易于分析和求 解。d e d s 的一个优点就是模型本身包含了求解递推算法。因此，适当定义系统的 事件，根据城市轨道交通列车运行的特性，我们便可以建立列车运行过程的状态 空间模型，从而易于分析列车运行以及行车组织问题。 八十年代以来，法国g c 0 h c n 【1 2 】等人，把极大代数用于确定性的离散事件动态 系统( d e d s ) 的建模和分析，通过极大代数中的特殊运算规则，将逻辑非线性关 系转化为这种代数意义下的线性关系，为对d e d s 建立形式简单的代数层次线性 模型，并定量分析d e d s 演化过程的规律开辟了一条可行的途径。我国学者涂奉 生f 1 3 l 、陈文德【1 4 1 、郑大钟1 1 5 】等人利用这种理论对串行生产线问题进行了一系列研 究，并得出了许多有价值的结论。由于城市轨道交通具有串行生产线的相关特性， 因此利用研究比较成熟的串行生产线的极大代数理论建立城市轨道交通模型，并 基于该模型对城市轨道交通运营中的相关问题进行分析和讨论，为揭示城市轨道 交通中的列车运行规律和特性提供了一种简单而有效的研究方法。 北京交通大学硕士学位论文 3 2 城市轨道交通系统的结构化分析 3 2 1 城市轨道交通线概述 考虑一条典型的城市轨道交通线：列车有序地运行在一系列的站台之间，并 且列车需在每站停车以便乘客上下车每趟列车与每个站台均为独立的，有各自 特征的，需要将所有列车与所有站台进行编号。在本文中，我们仅仅考虑顺序结 构的城轨线，不包括分支结构与树型结构的线路【坷。这意味着： 对于每趟列车来说，车站的顺序是不会发生变化的，这条线上的所有列车均为 这样； 对于每个车站来说，列车的顺序是不会发生变化的，这条线上的所有车站均为 这样； 连续线路可以划分为两类：一线型开环线与闭环线，下面给出它们的定义： 一线型开环线：一条开环线被定义为拥有n 个连续站台与运营m 列列车。站台 被依次编号为从 到 ，列车被依次编号为从 到 。列车从站台 出发， 从站台 离开( 见图3 1 ) 。若只考虑北京地铁1 号线的单方向，例如从苹果园一 一四惠东就是这种一线型开环线。 l2 n - l n _ 一一 图3 1 有n 个站台的一线型开环线 闭环线：一条闭环线是一条拥有封闭线路，n 个连续站台被依次编号为从 到 ，且站台 与车站 相连( 见图3 2 ) 北京地铁2 号线( 西直门东 直门) 就是这种闭环线。 - 2 i 兰i 图3 2 有n 个站台的闭环线 i i 3 城市轨道交通系统的建模与分析 3 2 2 城市轨道交通的运营特点 要研究城市轨道交通列车运行的调度指挥和运营管理，首先有必要对城轨交 通的运营特点做一下分析，简单说来，城轨交通的运营特点分列如下枷嘲“小嘲： 1 1 全旅客运输、运行距离短、高峰时段明显、季节性客流，地铁设计： 站问距短( 通常一公里) 、行车密度高( 2 4 分钟) 、运行速度低( 2 5 3 5 公里， 小时) ，因此，与干线铁路运输系统不同，地铁列车平行成对运行图具有“高 行车密度，短追踪间隔”的明显特点 2 ) 由于地铁系统通常仅在端点车站设置存车线以及折返线( 或到发场) ， 区间中转车站上、下方向各保持一条站线，且与区间正线之间实现无道岔连接， 因此中转车站上基本不存在会让与越行，列车只在运营线上停车上、下旅客， 且列车之间只存在发到间隔而不存在到发间隔。 3 1 根据地铁列车“等级相同”的运行特点以及地铁列车运行图“平行成 对”的追踪间隔特性，在正常情况下，列车区间运行时分以及列车站停作业时 分对所有车次同样适用。 4 ) 为了保证高密度运行下列车运行的安全性，利用信号灯将区间划分为 多个闭塞区间，并规定一个闭塞区间内最多只能一辆车在运行。 3 2 3 城市轨道交通系统与串行生产线的对等化 通过上述分析，可以发现：列车在顺序结构的城市轨道交通线上运行，列车 占用区间和车站的顺序是固定的，列车在区间的运行时间和在车站的作业时间具 有很大的规律性，并且可以认为所有的车具有相同的区间运行时间和车站作业时 间，也就是说时间参数是确定的，并且为了保证列车运行的安全，还规定一个闭 塞分区内最多被一辆列车占用，车站上由于只有一条主线，因此也只能同时被一 辆列车占用，因此顺序结构的城市轨道交通系统和串行生产线具有很大的相似性。 如果将其看作一条串行生产线，那么线路上循环运行的列车相当于串行生产线上 的加工工件，而线路上的车站和区间就相当于该串行生产线上的加工机器，列车 在区问的运行时间和在车站的停留时间就相当于工件在加工机器上的加工时间。 另外对于城市轨道交通线来说，同一车站或闭塞分区最多被同方向的辆列车占 用，因此顺序结构的城市轨道交通系统就是一个刚性生产线系统。为了便于研究 问题，我们以一线型开环线的城市轨道交通系统进行分析，闭环线可按照同样的 方法进行分析。由于目前，我国的城市轨道交通技术不高，站间距离比较短，因 此在一个区间内最多有一列车在运行，因此我们对站问闭塞的一线开环线的城市 轨道交通系统进行建模、分析。站问分成多个闭塞分区建模方法一样，只是维数 北京交通大学硕士学位论文 较高，进行理论研究，效果一样。 3 3 一线型开环线的建模 假设我们将一线型开环线等效成图3 3 所示的情况。 图3 3 线型开环线等效图 其中，m 。，膨：，帆为该线上按照上行方向依次排列的车站和区间， 五，五，瓦为依次通过这些车站和区间的列车。我们将该城市轨道交通线看作一 条串行生产线，其中m 。， 如，m 作为串行生产线上的加工机器，且每个机器前 面不存在缓冲器，即该生产线为刚性连接的，列车瓦，瓦，则是该串行生产线 上待加工工件。下面利用刚性生产线的极大代数理论建立城市轨道交通模型。 3 3 1 模型参数 在城市轨道交通运营线上，所有列车按照列车运行时刻表运行。列车运行时 刻表包括了列车的运行时间、每站到发时问以及在车站的停留时间。在如上的描 述中，由于把区间和站台都看作串行生产线上的加工机器，所以列车的运行时间 和车站的作业时间就相当于串行生产线上的工件加工时间 区间运行时间表示列车从前站占用出站的第一个轨道区段算起到列车进入下 车站，开始占用站台轨道区段为止； 列车的车站作业时间则是由三部分组成的：一：当列车在车站进站占用车站 站台轨道区段时，此时开始认定列车进入了车站，这时列车将减速运行直到列车 在车站上停稳，也就是列车在车站的减速制动过程时间；二：列车停稳后，打开 车门，开始进行乘客上下车，关闭车门，等待发车，也就是列车在车站的停站时 间：三：列车启动，并占用出站的第一个轨道区，也就是列车的启动时间。 另外，列车在车站发车时，列车压上发车进路，出站信号机关闭，即认为列 车出站，但站内股道并未出清，发车进路出清、解锁还要时间，完成后，给后续 进站列车排列进路还需要时间，所以前车出站，后车并不能马上进站，有一间隔 时间，即车站上的发到间隔时间。由于地铁并不是每个站都是联锁站，有半数左 右的站是非联锁站，不需要排进路；进路解锁，捧进路，进路锁闭，所需要的时 问，跟道岔数量关系很大，地铁道岔数量很小；地铁列车通常走的进路都一样， 3 城市轨道交通系统的建模与分析 所以道岔转换次数很少，这样即使排进路，所需时间不多，主要是检查联锁关系， 因此，对于城轨列车来说前后列车在车站上的发到时问间隔时间比较小，为了方 便建模，我们直接将车站上的发到问隔时间考虑到列车车站作业时间中去 假设第k 辆车在城市轨道交通线上车站和区间的作业时间依次为茸，c ， 为了表达方便我们将其用一向量五表示瓦一瞄，艺，c ) 为了便于表达每站的到 发时间，现如下定义系统中的输入变量，状态变量和输出变量。 设第k 列列车进入运行线路的时刻为h ( 七) ，最早占用各个区间或车站的时刻 为鼍似) ( 其中i 代表线路上的第i 个车站或区间) ，离开运行线路的时刻为) ，( 七) 。 将上述变量利用向量表示，并分别表示状态向量、输出向量和输入向量： 状态向量为：捌砷- ( 玉( 对焉七) ，戎( 日) 输出向量为：喇卅| i j 输入向量为：叫柚叫 其中输入变量表示了每列列车进入线路的时刻，状态变量则表示了每站的到 发时刻，输出变量则可以用来衡量车辆运行完全程的时闻 3 3 2 系统模型 由于缓冲容量为l ，所以对于第k 辆车来说，最早占用第i 个区间或是车站的 时刻分两种情况进行考虑： ( 一) ：如果第i 个区间或是车站没有被前一辆列车占用，那么只要该车辆在 第i 1 个区间或车站运行完毕就可以占用第i 个区问或是车站，这样有 薯( 七) - i 而- l ( 七) ； ( 二) ：如果第i 个区间或是车站仍被前一辆列车占用，而该车辆在第i 1 个区 间或是车站已经运行结束，那么此时列车需要等待，必须等到该区阅或是车站不 被前一辆列车占用，也就是前一辆车必须占用了第i + 1 个区间或是车站。因此列车 此时最早占用区间或车站i 的时刻为毛仁) 一o o k ，( 七一1 ) ； 所以对于第k 辆车来说，其在第i 个区间或是车站的最早开始运行时间应为： 玉( t ) - 删帕吖。( t ) ，o 十( t 一1 ) t 乞魄。( i ) o 呕( t 1 ) 当i 为1 时，即第k 辆车最早占用第一个车站的时刻，此时必须满足列车准备 好占用该车站，且满足前一辆车已从该车站发出，所以有 玉( 七) 一i 衄【 o + “( 味o 鸭( 七一1 ) ) 一o i “( 七) o o ：g ( 七一1 ) 当i 为n 时，即第k 辆车最早占用最后一个区间的时刻应满足那么应有 ( 七) 一m 觚忙。+ 铀( 七) ，r + 毛忙1 ) ) 一。毛。矿。毛 一1 ) 北京交通大学硕士学位论文 输出变量) ，( 七) 表示列车结束线上的运行的时刻，因此有y ( 七) - f ：o ) 。 基于以上分析和系统变量的定义，系统的状态方程和输出方程如下所示： 阿砷_ 4 酬句嘲酬删鸥 【，( 砷件，、 l y l 七) - c ；蚓七) 对于上述模型来说，矩阵4 表示了第k 辆车在线路上运行时，它最早占用当 前区间或车站的时刻和最早占用前一个区间或车站的时刻之间的关系。矩阵e 表 示了第k 辆车最早占用各个区间或车站的时刻和第k 辆车准备进入该线路的时刻 之间的关系。矩阵最表示了第k 辆车在线路上运行时，它最早占用当前区间或车 站的时刻和前一辆车的运行状况之间的关系。矩阵g 表示了第k 辆车离开运行线 的时刻和最早占用各个区间或车站的时刻之间的关系。矩阵4 ，只，最，q 分别如下 所示： 4 = 导 彳，岛占i 岛耋，。善l ，戽= 如。，l g 。p ，e k 肛 根据地铁列车“等级相同”的运行特点以及地铁列车运行图“平行成对”的 追踪间隔特性，在正常情况下，列车区间运行时分以及列车站停作业时分对所有 车次来说基本上是一样的，因此为了便于研究正常情况下的列车运行规律，我们 将所有线上列车的运行时间矩阵都记作r - 瓴，f 2 ，) 。那么3 1 式中的矩阵 4 ，4 ，五，c 对于任意的k 值来说是一样的，因此系统的状态方程和输出方程可以 表达成 脬? 2 1 粤_ 。，凹( “1 ) 鲫跚( 七) ( 3 - 2 ) l 小) 一c ( 七) 7 矩阵以口，c 分别如下所示： 么= z f l ，岛- 善 ，乞，e “占k 卜一n 厶q 善 ，q ，。 占厶，0 厶乇 3 城市轨道交通系统的建模与分析 对矩阵a 定义爿运算，那么系统方程3 2 式就可以表示成如下所示的表达式l 明： p 忙) 一一f o 石忙一1 ) o 彳口 u 忙)， t y ( 七) 一c 固x ( 七) u q 该式通过逐次替代，将第k 辆车的状态量和其本身状态、前一列车状态以及 进入线路的时刻之间的关系，直接转化为系统的状态变量和前一辆车运行时的状 态量以及该车进入线路的时刻之问的关系，简化了系统表达式。其中，矩阵4 。，表 示了第k 辆车的状态和第k 1 辆车的状态之间的关系，矩阵彳曰表示了第k 辆车的 状态和该车进入线路的时刻之间的关系。矩阵4 f ，4 冶如下所示： 4 ，一 ，0 ，j 1f 0 e ，f l ，0 ， ，f l + 乞，乞，0 ， s ，f 1 + 乞+ 岛，乞+ 岛，岛，o ，f ，占 ，- 1 + 一2 + + ，- 2 + 一1 ，o _ lj 珥 ，4 曰。 f l f 1 + f 2 f 1 + f 2 + f 3 l - 1 + 2 + + f l j 。d 上述模型将城市轨道交通系统的列车间到发时同之间的关系利用极大代数方 法表达为线性代数表达式，从而便于推导列车运行时刻表之间的演化过程。该表 达式可以帮助我们编制已知时间参数下的列车时刻表。 3 4 周期输入下的系统性能分析 对于一个城市轨道交通系统而言，服务质量评价的一个重要参数就是列车应 以一个比较规则的问隔到达车站，保证车站客流的均匀吸纳，这就是城市轨道交 通列车运行特有的均匀性。为此，在实际运营中通常根据单位时间内的客流量， 确定单位时间内列车的发车间隔，来保证列车以一定的间隔到达车站为此引入 周期输入对系统进行控制。首先给出周期输入的定义： 定义3 1 【1 川设是极大代数瓦上的一个非数且为正数，令【啦) 一，耵位一1 ) ， 则称u 是一个周期输入 对于城市轨道交通列车运行来说，此处的就是列车在始发站的发车间隔。 3 4 1 系统的能控性嘲 能控性是系统的一个重要结构特性。对于离散事件动态系统的控制问题，能 控性具有基本的重要性直观上，能控性反映系统输入对系统状态或事件的可影 响性。对串行生产线一类的d e d s ，输入对状态或事件的可影响性体现为，能否通 过改变系统资源的投入时刻来影响和调整系统加工活动的开始时刻。在此我们就 北京交通大学硕士学位论文 是通过系统能控性的分析来讨论能否通过调整列车的发车时刻来对列车的运行进 行调整 首先系统的能控性讨论是针对系统模型具有如下的递推方程形式的一类 d e d s ： p ( | | + 1 ) - 彳z ( 七) o 曰u ( 七) ，七一1 2 玉。，。 、 t y ( j i ) - a ( 七) 其中，圈乘圆运算符号已经被省略，x r ，y 彤，硝 d e d s 的状态能控性问题。最早是由法国学者c 0 h c n 等，针对串行生产线类 型的可表征为极大代数上线性系统的一类d e d s 研究和引入的。随后对状态能控 性的研究被拓展到更为一般的框架上，更得到了更具一般意义的结果。 状态能控性的早期定义是基于系统的事件图描述来绘出的。事件图实质上是 一种特殊的佩特里网，是对系统的一种图形式的描述。对给定的一个d e d s ，引入 其对应的事件图，则称系统的一个状态五为能控的，如果在系统的事件图中表征 状态矗的结点至少和一个输入变迁结点存在通路。称系统为状态完全能控的，如 果系统的全部状态变量都是能控的。 可以看出，上述状态能控的事件图定义有着四个基本特点。( 1 ) 直观性。状 态变量和状态的能控性直接被表征为系统事件图中状态变量结点和输入变迁结点 间的连通关系，使状态能控性成为系统事件图的一种结构特征。( 2 ) 实用性。状 态能控性的判断归结为检验事件图中状态变量结点和输入变迁结点之间的连通 性，便于应用和分析。( 3 ) 因果性。能控性定义之间显示了系统输入和状态闯的 因果影响关系。( 4 ) 非形式化。定义表达形式为非形式化的，一般不便于从理论 层面上对能控性作展开性的研究。 这就表明，为使能控性的研究建立在更一般性的基础上，有必要对状态能控 性引入形式化定义。并且，考虑到d e d s 的状态能控性只涉及到输入对状态问的 因果影响性，所以可仿照连续变量动态系统中的能达性那样，在定义d e d s 的状 态能控性中把系统初始状态总是取为极大代数意义下的零向量工w j 。矿。在此基础 上，我们有如下的形式化定义。 定义3 2 【状态变量能控性】对由线性递推模型( 3 4 ) 描述的一类d e d s ， 设初始状态x w j 2 尹，则称系统一个状态变量羞是能控的，如果对任给一个有限实 数声，必存在k 和一组输入向量恤( 0 ) ，“( 1 ) ，以( ) ，使有乇瓴+ 1 ) - 芦。 定义3 3 【状态能控性】对由线性递推模型( 3 - 4 ) 描述的一类d e d s ，设初 始状态x 爹，则称系统状态为完全能控的，如果系统的每一个状态变量 薯a 一1 2 ，p ) 均为能控的。 形式化定义的优点之一，是可比较容易的从一般性角度研究d e d s 的状态能 3 城市轨道交通系统的建模与分析 控性，建立起判别系统状态能控性的代数化判据 能控性判据1 ：对由线性递推模型( 3 - 4 ) 描述的一类d e d s ，则系统状态为 完全能控的一个充分条件是，矩阵口不含有极大代数意义下的零行 对于我们的系统模型，通过引入周期输入控制，可以发现系统的方程变为： p 似) 一爿f o z 体一1 ) o 爿却 ，忙一1 )r ，一5 、 1 y ( 小c 固z ( 七) ”“ 对照( 3 - 4 ) 和( 3 - 5 ) 可以发现，此处的4 冶| e i 就是( 3 4 ) 中的矩阵口，由于 大于零，且矩阵口如上所示，因此系统是状态完全能控的。因此我们可以通过 对输入变量的控制来改变系统的状态变量，也就是说我们可以通过改变列车在始 发站的发车间隔时问来控制列车在车站的到发时刻。 3 4 2 系统的稳态特性 出于旅客使用城市轨道交通列车的方便程度以及车站对于非均匀分布客流的 实际吸纳效果考虑，从客流平均的有效乘车时段的角度出发，提高车站列车发到 间隔( 当前客流乘车出站后，后继客流逐渐汇集等乘下一列车的平均时间间隔) 的 均匀水平，避免过小的车站列车发到间隔造成晚点( 前行) 列车超载而后行列车欠 载的不利局面( 即当前旅客集中搭乘前行列车，而由于后续客流汇集时间过短导致 可供后行列车吸纳的乘客数量低于预期数目) ，应是运营服务水平改善的重要目 标。因此对于城市轨道交通系统列车之间的车站追踪间隔的均匀分布问题的研究 具有重要的意义。该特性可以利用串行生产线的周期稳定特性来说明。下面首先 说明串行生产线的周期稳定的相关知识。 直观上说，系统状态演化过程的稳定性是指，演化过程的有界性和对其平衡 状态的有限节拍的收敛性。研究表明，对串行生产线一类可表征为极大代数上线 性系统的d e d s ，演化过程的有界性总可保证的，因此稳定性问题归结为演化过程 能否在有限个节拍内收敛到其平衡状态。对于这里讨论的一类d e d s ，平衡状态是 一个周期过程，通常称此周期过程为周期性稳态。下面首先给出稳定性的数学定 义【冽。 考虑极大代数上定常线性系统( 2 3 ) ，对任意初值 墨- ，r ，黾- e ，f g ，稽) ，若有 觊k 阵胪 此处开方是在极大代数意义下的，则称系统( 2 3 ) 关于分量墨是稳定的；若 对所有的分量均是稳定的，则称系统是弱稳定的，进一步若有 北京交通大学硕士学位论文 九一- - a - 常数，则称系统( 2 3 ) 是稳定的。 若对任意初值磊一【，】r ，- 岛f q ，厅) ，存在l 【o ，当k k o 时，有 五+ 1 j 一 毛陋】，则称系统相对于五是一致稳定的，类似可定义系统的一致弱稳 定和一致稳定。 。 三疆兰 并假设为其特征值，那么有当m a 【口) 时，。m a 】【( r ) ，而当p ，m a x 叮) 时， 结论3 2 设a 为矩阵爿，的特征值即m a ) 【( 了) ，那么当p a 时，则一定存 3 城市轨道交通系统的建模与分析 在，使得对于任意的 ，有z o + 1 ) 。腰o ) 。那么当p ，a 时，则一定存在 磊，使得对于任意的一，露，有x o + 1 ) 。p x o ) 。 证明：由结论3 1 可知，矩阵彳- ，为周期矩阵，且特征值为a ，周期阶数 为1 ，所以存在 ，使得对于任意的 ，有 ( 4 f y “- 0 ，) 而矩阵肌e 国一，也是周期矩阵，而且其周期阶数仍然为1 ，并假设为其特 征值，那么有当一s m x 口) 时，- m 瓤口) ，而当弘 m 越仃) 时，- p ，所以一 定存在也，使得对于任意的弹，有似e o 彳，y “- 烈p o 彳乍y 又因为删一捌 9 口矽 【嘞彳酶哟z 盯，所以 当p s a 时，有z o + 1 ) 。a x o ) ，h ，m 积( ，j 1 2 ) ，则状态是周期的。 当p 时，对任意的万 ，l l ，则一一 + z 因为系统的每一个状态都是可控的，所以【，( 刚联肛e 0 4 。f r 中每一个元素 都是有限的。取【，( o 、m b ( 胪e o 一，r 中元素的最小值与工( o ) f r 中最大值( 若 其元素为，则结论显然成立) 之差为肼，则存在正整数k ： “。一( o i 兰1 ) + 1 l p 一 j 使当b l 时有_ f i f 一工f m ， a 。石( 0 ) o ，) p u ( 0 m b ( 肛o _ ，p 所以说当n + k 时有x o + 1 ) 一t 0 ) 彳b ( p e o 彳f y 叫z o ) 结论得证 该结论说明，在周期输入控制下，系统的状态量必定经过有限的过渡批次进 入周期为1 的周期稳态，也就是说当系统处于平衡状态时，对于所有的车站或区 间，每个车站或区间平均每隔一定时间( a 或时间) 便被一辆列车占用，该时间 取决于列车的发车间隔和时间矩阵r 中的最大值，该值也就是列车问的追踪问隔。 因此，均匀发车可以保证列车在车站的到发间隔的均匀分布，而且列车间的到发 间隔取决于于列车的发车间隔和时间矩阵r 中的最大值。 实际中，我们都希望列车运行过程能够一开始就进入平衡过程，即系统能够 直接进入周期稳态。经分析，有下面这个结论。 结论3 3 当耻 ，且x ( o ) u ( o m 口，那么系统的状态将直接进入周期 为1 的均匀周期性稳态。 证明：当z ( 0 ) s u ( o 阳占且一 a 时，矩阵肛e o 一+ f 的每一行的最大元素就 是p ，所以对于任意的正整数万，都有x 加) - 卢工0 1 ) ，此时系统将直接进入周 期为1 的周期稳态过程。 北京交通大学硕士学位论文 该结论说明，在满足z ( 0 ) s u ( 0 m 丑时，配置列车的发车间隔不小于列车在线 路上运行的最大时间，就可以使列车运行直接进入周期稳态过程。由于对于城市 轨道交通系统来说，初始状态均为o ，所以z ( o ) s u ( 0 m 氇一定可以满足，因此只 要使得发车间隔大于时间矩阵r 中的最大量，既满足发车间隔大于追踪间隔的最 小标准，就能使系统直接进入周期稳态，而且列车闻的追踪间隔就是发车间隔时 间。 为了便于对系统的稳态特性进行评价，下面引入串行生产线上的几个相关定 义嘲。 定义3 4 称系统中加工产品所需时间最长，即最忙的机器处于忙的时间为系 统忙时。 定义3 5 称系统忙时与整个时间之比为系统忙的概率，简称忙率 定义3 6 称某时刻某节点处等待加工处理产品的个数为队长。 由前面的分析可知，系统进入周期状态后，城轨交通线上的每一个车站或区 间平均接受