轨道运输监控系统长进路的自动生成.pdf

中国矿业大学学报990 32 3 中国矿业大学学报 JO U RNA L O F CH I NA U NI VERSI T Y O F M I NI NG T P 391 A u t o -G e n e r a t i o n o f Lo n g A d m i s s i o n Pa s s a g e i n Ra i l w a y Co n v e y i n g M o n i t o r i n g Sy s t e m H u a G a n g Zu o M i n g Co l l e g e o f In f o r m a t i o n a n d El e c t r i c a l En g i n e e r i n g , CU M T , Xu z h o u , Ji a n g s u 2 2 10 0 8 A b s t r a c t In d e s i g n o f r a i l w a y c o n v e y i n g m o n i t o r i n g s y s t e m , a u t o -g e n e r a t i o n o f l o n g a d m i s s i o n p a s s a g e s i s a p r o b l e m h a v i n g n o t b e e n s o l v e d . O n t h e b a s i s o f a n a l y z i n g f e a t u r e o f r a i l w a y c o n v e y i n g s y s t e m , a n y r a i l w a y c o n v e y i n g s y s t e m m a y b e r e g a r d e d a s a s i m p l e d i g r a p h , i n w h i c h n o d e s o f t h e s i m p l e d i g r a p h a r e c o n s i s t o f b a s i c a d m i s s i o n p a s s a g e s , a n d s i d e s o f s i m p l e d i g r a p h p r e s e n t t h e c a s c a d e d i r e c t i o n b e t w e e n a d m i s s i o n p a s s a g e s . No d e s s e q u e n c e p a s s e d b y l o n g a d m i s s i o n p a s s a g e s h o w s t h a t l o n g a d m i s s i o n p a s s a g e i s c o m p o s e d b y t h o s e b a s i c a d m i s s i o n p a s s a g e s . U s i n g m a t r i x t h e o r y , j u d g m e n t t h e o r e m t o d e c i d e w h e t h e r t h e r e a r e r o u t e s b e t w e e n n o d e s a n d a g e n e r a l m e t h o d a n d e x a m p l e o f s e e k i n g s h o r t e s t r o u t e a r e g i v e n o u t . K e y w o r d s l o n g a d m i s s i o n p a s s a g e , s i g n a l c o n c e n t r a t i n g l o c k i n g s y s t e m , m o n i t o r i n g s y s t e m , p r o d u c i n g m e t h o d 将轨道运输监控系统划分成一些基本进路后［1］，在传统的轨道运输监控系统设 计中，接下来就要根据电机车的作业流程，由人工一次性排定长进路［2 ］，这既费时 又容易出错，且一旦基本进路发生变化，这些工作又要从头做起. 那么，在轨道运输监 f i l e / / / E| / q k / z g k y d x x b / z g k y 99/ z g k y 990 3/ 990 32 3. h t m （第 1／7 页）2 0 10 -3-2 3 15 57 59 中国矿业大学学报990 32 3 控系统中，能否自动排定长进路，应该采用什么准则来自动生成长进路，生成长进路 的方法又是什么针对这些问题本文将进行深入细致的研究. 1 轨道运输监控系统与有向图 如图1所示，依据轨道运输监控系统中已装备的传感器、信号机和电动道岔，按照 进路的运行方向和连接关系，将整个轨道运输监控系统简化成一个由基本进路为结点 的信号布置图（不含有平行边和环的图）. 图1 轨道运输监控系统信号布置 Fi g . 1 T h e d i g r a p h o f r a i l w a y c o n v e y i n g m o n i t o r i n g s y s t e m 系统共设置基本进路19条，见表1所示. 表1 进路划分 T a b l e 1 T h e d i v i s i o n o f a d m i s s i o n p a s s a g e 进路号区 间进路号区 间 1X2 X511X7 X4 2X5X612X4翻车机1 3X6 X813X4翻车机2 4X8 X914X14X11 5X8 X1215X11X10 6X12 X1316X10 X7 7X13X1417X17 X2 2 f i l e / / / E| / q k / z g k y d x x b / z g k y 99/ z g k y 990 3/ 990 32 3. h t m （第 2 ／7 页）2 0 10 -3-2 3 15 57 59 中国矿业大学学报990 32 3 8X13X1618X2 2 X11 9X16 X1719X3X5 10X9X7 以进路为结点构成的简单有向图 见图2 . 图2 系统简单有向图 Fi g . 2 T h e s i m p l e d i g r a p h o f s y s t e m 2 长进路的数学排定方法 在简单有向图中，用什么方法和准则能找出源结点到目标结点的最佳路径为方 便分析和研究我们作以下假设 有向图相邻结点的顺向距离为1，逆向距离为∞，非相邻结点间的距离为∞；以源 结点到目标结点距离最短为路径搜索原则. 2 . 1 源节点到目标结点的可达性判断［3］ 在搜索源节点和目标结点之间最短距离之前，首先要判断源节点和目标结点之间 是否存在通路. 定义1 给定图G 〈V, E〉, 设v 0, v1, ⋯, vn ∈V, e 1, e2, ⋯, en ∈E，其中e i i 1, 2 , ⋯, n 是关 联于结点v i -1, vi 的边，交替序列v 0e1v1e2⋯en v n 称为联结v 0到vn 的路. 定理1 在一个具有n 个结点的图中，如果从结点v j 到v k 存在一条路，则从结点v j 到 v k 必存在一条不多于n -1条边的路. 推论 在一个具有n 个结点的图中，若从结点v j 到v k 之间存在一条路，则必存在一 条从v j 到v k 而边数小于n 的通路. 定义2 设G 〈V, E〉是一个简单图，它有n 个结点V { v 1, v2, ⋯, vn } , E是连接结点的 f i l e / / / E| / q k / z g k y d x x b / z g k y 99/ z g k y 990 3/ 990 32 3. h t m （第 3／7 页）2 0 10 -3-2 3 15 57 59 中国矿业大学学报990 32 3 边集，则n 阶方阵A （G ） （a i j ）称为G 的邻接矩阵. 其中 a d j 表示邻接，n a d j 表示不邻接. 当给定的简单图是无向图时，邻接矩阵是对称的，当给定图是有向图时，则邻接 矩阵并不一定对称. 邻接矩阵A 中，第i 行元素是由结点v i 出发的边所决定，第i 行中值为1的元素的数目 等于v i 的出度. 同理，第j 列中值为1的数目是v i 的入度. a i j ≠0 表明i , j 两结点必直接相连. 这 就是邻接矩阵的物理意义. 从图G 的邻接矩阵中，可以得到图的很多重要性质. 定理2 设A （G ）是图G 的邻接矩阵，则 A G l 中的i 行, j 列元素a i j l 等于G 中v i 与v j 的长度为l 的路的数目. 在许多应用中，常常要判断有向图的一个结点v i 到另一结点v j 是否存在通路的问题. 如果利用图G 的邻接矩阵A ，则可计算A 1，A2，A3，⋯, An , 当发现其中某个A m的a i j m ≥1, 就表明结点v i 是可达的. 但这种计算十分繁琐且A m不知道计算到何时为止. 根据定理1 的推论可知，如果有向图G 有n 个结点，V { v 1, v2, ⋯, vn } , v i 到v j 有一条路，则必然有一条 长度不超过n 的通路，因此只要考察a i j m , 其中1≤m ≤n . 定义3 令G 〈V, E〉是一个简单有向图, | V| n ；假定G 的结点已编序，即V { v 1, v2, ⋯, v n } , 定义一个n n 阶矩阵P （p i j ），其中 称矩阵P是图G 的可达矩阵. 一般而言，从图G 的邻接矩阵A 得到可达矩阵P可由下式求出 P A （1）∨A（2 ）∨A（3）∨⋯∨A n ， 其中A i 表示在布尔运算意义下A 的i 次方，∨表示布尔“或”运算. 一旦轨道运输监控系统配置完毕, A 和n 都是已知的，故P可求得，所以系统配置完 成后系统中任意两进路之间是否可达完全可以确定. 系统发生变化只需重新求A 和n 并重 新计算P即可. 2 . 2 搜索方法［4］ 若已知v s , v i 两结点间有通路存在，现在研究用怎样的方法和准则，在有向图中找出 源结点到目标结点的最佳路径. f i l e / / / E| / q k / z g k y d x x b / z g k y 99/ z g k y 990 3/ 990 32 3. h t m （第 4／7 页）2 0 10 -3-2 3 15 57 59 中国矿业大学学报990 32 3 s 为源结点，j 为中间结点，两结点之间的路径长用D s , i 表示，j 是i 的相邻结点，l j , i 是j 到i 的最短路径长，则 s 到i 的路径长D s , i D s , j l j , i . 图3 s 结点到i 结点的距离 Fi g . 3 T h e d i s t a n c e f r o m n o d e s t o n o d e i 2 . 2 . 1 算法 1 建立一个节点集N，N开始只包含源结点，计算源结点与其他结点的距离，若i 结点不与s 结点相邻，则i 至s 的距离为D i ∞. D s , i 简写为D i . 2 找出N集中相邻且源结点距离最小的结点j 加入结点集N中，对N集外的其它结点 进行更新距离计算 D i 新 m i n D i 老, D j l j , i 直到图内全部结点都包含在N集中为止. 2 . 2 . 2 算法举例 我们利用上述算法求结点1到各结点的最短路径. 1） 开始时N { 1} ，D 2 1，其余D i ∞ i ≠1 . 2 ） 将最近的相邻结点2 ，加入N集中，N { 1, 2 } ，对N集外的其它结点进行更新距 离运算. 3 当所有结点全部加入N集中时，得到如下1结点距其他各结点的最短距离为D 2 1, D 3 2 , D 4 3, D 5 3, D 6 4, D 7 5, D 8 5, D 9 6 , D 10 4, D 11 5, D 12 6 ， D 13 6 , D 14 6 , D 15 7 , D 16 8 , D 17 7 , D 18 8 , D 19 ∞, D 副井 6 ，D 翻入1 7 ，D （翻入2 ） 7 . 从而得到1结点的最短路径图，如图4所示. 从图4不难看出结点1～11的最短路径为1 2 3410 11. 有了图4中1结点到各结点的最短路径，容易从该图上求出最短路 径. 对其它结点为源节点的处理方法与上相同. f i l e / / / E| / q k / z g k y d x x b / z g k y 99/ z g k y 990 3/ 990 32 3. h t m （第 5／7 页）2 0 10 -3-2 3 15 57 59 中国矿业大学学报990 32 3 图4 1结点到其它各结点的最短距离图 Fi g . 4 T h e m i n i m u m d i s t a n c e f r o m n o d e 1 t o t h e o t h e r n o d e s 3 在实际系统中的应用方法 在实际应用中，直接输入源和目标进路号的方法是不实用的. 为了方便用户使用， 利用每一进路都与一个信号机相关联的事实，对于三显示信号机可以认为是由2 个二显 示信号机组成的. 这样我们就得到以下映射关系. 设X为全体信号机的集合，即X { x 1, x2, ⋯, xn } ，J为系统中全体进路的集合，即J { j 1, j 2, ⋯, jn } ，则必存在一个从X集合到J集合的映射T ，对任意x i ∈Z, 则必存在j k ∈J使T （x i ） j k ，其中1≤i ≤ n , 1≤k ≤n ，显然，这个映射是一一映射. 通过上面的讨论，我们已经解决了在长进路生成中需要解决的全部理论问题，并 已在实际中得到了验证. *煤炭科学基金资助项目 94电10 10 7 作者简介 华 钢，男，196 3年生，工学硕士 博士研究生 ，讲师 作者单位中国矿业大学信息与电气工程学院 江苏徐州 2 2 10 0 8 参考文献 1 华 钢，左 明. 轨道运输监控系统的建模与控制算法的研究. 中国矿业大学学报， 1998 , 2 7 1 90 ～94 2 李玉良. 进路式调车方法. 中国矿业大学学报，1998 ，2 7 4 437 ～440 3 左孝凌，李为鉴 ，刘永才. 离散数学. 上海上海科学技术文献出版社， 198 2 . 2 7 2 ～ 2 94 4 李增智. 计算机网络原理. 西安西安交通大学出版社， 1991. 142 ～145 收稿日期 1998 -0 7 -0 6 f i l e / / / E| / q k / z g k y d x x b / z g k y 99/ z g k y 990 3/ 990 32 3. h t m （第 6 ／7 页）2 0 10 -3-2 3 15 57 59 中国矿业大学学报990 32 3 f i l e / / / E| / q k / z g k y d x x b / z g k y 99/ z g k y 990 3/ 990 32 3. h t m （第 7 ／7 页）2 0 10 -3-2 3 15 57 59