轨道交通GPS数据约简的数学模型与算法研究概要

1、第30卷第4期铁道学报Vol. 30No. 4 2008年8月J OURNAL OF T H E CHINA RA IL WA Y SOCIET Y August 2008文章编号:100128360(2008 0420116204轨道交通GPS 数据约简的数学模型与算法研究陈德旺, 蔡伯根, 王剑, 唐涛(北京交通大学轨道交通控制与安全国家重点实验室, 北京100044摘要:利用实测轨道GPS 数据生成电子地图是实现列控智能化的一个重要环节。为减少存储空间和提高列车定位的实时性, 需要对大量GPS 数据进行约简, 找出其中的少量关键数据。通过数学建模和分析, 轨道交通GPS 数据约简问题是一

2、个N P 问题, 难以求得最优解。本文提出一种启发式线性算法, 并给出6个性能指标的定义。两个铁路区间的实测GPS 数据用于对算法的性能指标进行分析比较。计算结果表明, 该算法是有效的且运行速度较快。该算法能以较低的约简率在一定误差要求的前提下约简大量GPS 数据。在误差约束为1m 时, 约简率小于2%; 误差约束为2m 时, 约简率约为1%。随着轨道弯曲程度的增加, 约简率有所增加。关键词:轨道交通; 全球定位系统; 电子地图; 数据约简; 启发式算法中图分类号:U284文献标志码:AMathem atical Model andR eductionC EN CA I , G Jian ,

3、TAN G Tao(of Rail and Safety , Beijing Jiaotong University , Beijing 100044, China Abstract :data of railway GPS (Global Po sition System to generate an elect ronic map is an improtant step to realize t he intelligent train cont rol. To decrease t he memory space and enhance t he real 2time p ropert

4、y of t rain po sitioning , it is necessary to find an effective data reduction algorit hm for huge GPS data. Modeling and analysis indicate t hat t he p roblem of railway GPS data reduction is a N P p roblem and it is hard to get t he optimal solution. A heuristic algorit hm was p ut forward and 6pe

5、rformance indexes were defined in t his paper. The surveyed GPS data of two railway sections were used to analyze t he performance index of t he algo 2 rit hm. The comp utational result s show t hat t he algorit hm is effective and t he running speed of t he algorit hm is very high. The algorit hm c

6、an reduce t he huge GPS data in a very low reduction rate under certain error require 2 ment. When t he error requirement is 1m , t he reduction rate is less t han 2%; when t he error requirement is 2 m , t he reduction rate is about 1%.Wit h t he increase of t he camber of railway , t he reduction

7、rate increases. K ey w ords :rail traffic ; GPS ; electronic map ; data reduction ; heuristic algorit hm全球定位系统GPS 在城市车辆、飞机、船舶导航、大地测量、地图绘制和火箭导弹监控等众多领域得到广泛应用1。同样, 在铁路勘测、定位和监控方面有着好的发展前景2,3。目前欧洲各国铁路正在加强利用GPS 技术, 沿相应线路设置差分基站, 并使之与移动通信技术结合, 以提高铁路的通过能力和可靠性4。收稿日期:2006211227; 修回日期:2007204223基金项目:国家自然科学基金面上项目

8、(60776833 ;国家自然科学基金重点项目(60634010 ;轨道交通控制与安全国家重点实验室(北京交通大学 开放基金项目(SK L2007K005作者简介:陈德旺(1976 , 男, 安徽南陵人, 副教授, 博士。E 2m ail :dwchen . cn 列车调度指挥智能化是铁路运输现代化的重要标志5。实现列车的智能化调度和监控, 可消除行车安全隐患, 提高运行效率。精确的电子地图是列车智能化调度和监控的重要环节6。铁路传统的测量方法难以获取电子地图所需的大量基础数据。采用GPS 测量操作简便、进度快, 可极大提高工作效率7。在获取大量轨道GPS 数据之后, 一个重要

9、问题是采用有效的约简算法简单高效地表示轨道, 以减少存储空间和提高电子地图匹配效率, 同时要把误差控制在允许范围内。轨道可分为直线轨道和曲线轨道, 直线轨道表示相对简单, 曲线轨道在电子地图上的表示 方法则是一个难点。目前常用方法有NU RBS 表示8、B zier 曲线表示等9,10。这类曲线表示方法会导致数据存储量增大, 尤其是相应的地图匹配算法复杂。实际的曲线铁轨是渐近线形状, 曲率半径比较大。文献6发现, 只要取较少的点就可把分段直线替代曲线轨道的误差控制在一定范围内。本文提出可在轨道上依次取点, 用顺次相连的折线近似代表曲线轨道。用折线表示轨道形成的误差有两种:横向误差和纵向误差。横

10、向误差为折线偏离轨道的最大正交投影距离; 纵向误差即轨道长度与折线长度之差。本文推导了数据约简的组合数学模型, 提出一种启发式算法, 并以铁路实测的GPS 数据对算法性能进行分析和比较。1数据描述和数学模型1. 1数据描述本文所用的数据是青藏铁路的实测GPS 数据, 是用差分GPS 技术测量, 精度为cm 级。本文选取其中的两个区间数据对算法效果进行验证, 其中区间9935组数据, 区间2有8452距离为1. 5m 3m , km 。X Y坐标, , 如图1和图2所示 。对于约简算法而言, 同时控制两个误差指标比较困难, 本文以横向误差为约束条件, 再去检验纵向误差。复线区段上下行线路中心线之

11、间和车站内相邻股道之间的距离约为5m 。对于横向误差约束, 分别设为1m 和2m 。这显然可以区分出上下行列车轨道; 同样也可以区分开车站内不同股道。1. 2数学模型轨道交通GPS 数据约简, 其实就是在所测数据集中选择最少的关键数据点, 构成顺次相连的折线, 并使 得每个实测数据到相应分段上的最大正交距离不超过设定的横向误差约束。本文利用组合优化理论11推导了数学模型描述该问题:6ni =1z i (1 z i (0, 1 , i =2, n(2 z 1z n (3i , j (4 n , 设定的横向误差约束为(2 表示在这n 个数据点中, 如果第i, 则z i =1, 否则为0。约束条件式

12、(3 表示分段直线第一段的起点是该数据集的起点; 分段直线最后一段的终点是数据集的终点。所以数据集中还有n -2个点可以被选为分段点。约束条件式(4 表示实测数据到相应分段直线的正交距离不超过设定的横向误差, d i , j 表示分段点i 与下一分段点j 之间的点到这两点连线间的正交距离。该组合问题共有2n -2种可能的解。实际中, 一般以一个铁路区间的GPS 数据为一个基本单元进行约简, n 约为8000。由于点到直线的投影距离公式是非线性的, 并且求最大投影距离不超过设定横向误差的约束条件也是非线性的, 所以该问题是一个分段非线性的组合问题。不难看出, 该问题是一个大规模的N P 完全问题

13、, 在有限的时间内难以求得最优解, 必须结合工程实际寻求较优解。2算法和性能指标2. 1启发式算法该算法的基本思想是“步步为营, 不能进则退”。具体来说, 从起点开始试探下一个假设终点, 能前进(误差满足要求 尽可能地前进, 不能进则退后一步; 找到下一个终点后, 再以该终点为起点, 寻找下下个终点; 如此循环直到所有数据点都包括在各分段中。显然, 该算法是一个简单实用的局部优化的启发式算法。算法的步骤为:711第4期轨道交通GPS 数据约简的数学模型与算法研究第1步将区间起点设为起始点, 作为所有分段中的起始点, i =1。第2步从起点i 开始, 以该点之后的第2个点(i +2 为假设终点。

14、第3步将起点和假设终点连接成直线。如果起点和终点的X 坐标相等, 直线斜率为无穷大, 则用式( 5 计算正交距离, 其中的x 是起点或者终点的X 坐标; 否则, 求出该直线的斜率k 和截距b , 利用点到直线距离公式, 计算起点和假设终点之间的数据点x i 到该直线的正交距离, 如式(6 所示。d i =|x i -x |(5 d i =2+1(6 第4步求这些正交距离中的最大值D maxD max =max d i (7 第5步如果D max 小于设定的横向误差E , 则假设终点向前方(从起点到终点的方向为前方 移动一个点, 回到第3步。第6步如果D max 大于E ,终点的前面一点, ,2

15、第7步。, 算法的效率取决于数据集合的规模。2. 2算法性能指标在满足横向误差约束时, 算法的性能指标有:(1 分段数m :分段直线的总数, 越少越好。(2 数据约简率r :关键点数和所有数据点数n 之比, 反映数据约简的效率, 越小越好。实际上, 该指标与分段数密切相关, 因为关键点数等于分段数加1。r =n100%(8 (3 纵向误差L e :反映分段直线表示曲线轨道在长度上的损失, 越小越好。L e =1-6m i =1k i /6n-1j =1l j 100%(9 式中, k i 为分段直线i 的长度; l j 为相邻数据点间长度。(4 横向误差的平均值 E :所有点到相应直线段的投影

16、距离的平均值, 越小表明算法的鲁棒性越好。(5 横向误差的最大值E max :所有点到相应直线段投影距离的最大值, 以检验算法是否满足横向误差要求, 同时也间接表明算法的鲁棒性, 越小越好。(6 运行时间t :反映算法的时间效率, 越小越好。由于该算法在地图生成前离线运行, 不是用于列车实 时定位, 运行时间只要不太长就可接受。3计算结果及比较对两个区间的数据, 在不同的横向误差约束下, 算法性能指标的比较分别如表1和表2所示。表1区间1的算法性能指标比较性能指标数值E/m 12m/m 12087r/%1. 220. 89L e /%0. 0130. 025E max /m 0. 991. 9

17、9E /m 0. 581. 16t/s 148. 4156. 82区间E/212993r/%1. 541. 11L e /%0. 0160. 032E max /m 0. 991. 99E /m 0. 581. 08t/s 102. 7100. 3从表1和表2中可发现以下规律:(1 算法的约简率很低, 能以较少的关键数据描述大量的实测GPS 数据。横向误差约束为1m , 约简率不超过2%, 横向误差约束为2m , 约简率约为1%。(2 纵向误差非常小。随着横向误差约束的增大, 纵向误差有所增大。在横向误差约束为1m 时, 纵向误差不超过万分之二; 横向误差约束为2m , 纵向误差不超过万分之四

18、。(3 随着横向误差约束的增大, 算法的分段数减少, 约简率降低, 而纵向误差、横向误差的最大值和横向误差的平均值增大。(4 区间2的数据为较弯曲的曲线轨道, 在相同的横向误差前提下, 区间2数据的分段数和约简率要比区间1大, 而其他3项指标没有明显的区别。(5 算法的运行时间很短, 效率比较高。对于一个大规模的组合N P 问题, 只要运行时间不是太长就可以接受。算法是生成电子地图的前期环节, 是离线运行的, 应该说速度是较快的。区间1的数据规模大, 运行时间略长; 不同的横向误差约束对算法速度的影811铁道学报第30卷 响很小。这也说明该算法是一个线性算法, 算法运行时间和数据集的大小呈线性

19、关系。这里选择2个运行结果进行显示。区间1的数据在横向误差约束为1m 的情况下, 算法的运行结果如图3所示。区间2的数据在横向误差约束为2m 的情况下, 算法的运行结果如图4所示。图3、图4中的圆点为分段点。可发现在轨道弯曲的地方圆点密度高, 在轨道平直的地方圆点密度低 。4结束语把误差控制在允许的范围内, 对大量实测GPS 数据进行约简以尽可能简单高效地表示轨道, 对列控电子地图的自动生成和列车实时定位具有重要意义。今后在算法研究的基础上, 电子地图的数据格式、存储方式、长度误差的补偿、快速地图匹配算法还需做深入研究。参考文献:1刘基余, 等. 全球定位系统原理及应用M .北京:测绘出版社,

20、1995:1210.2Urech A , Perez Diestro J , G onzalez O. A G alileo Demon 2strator for Railway Operation SystemC/Proceedings of DASIA , Dublin , Ireland , 2002:4422447.3王江涛, 王剑, 蔡伯根. 基于GPS 和RFID 技术的铁路信号设备巡检系统J.铁道学报, 2006, 28(5 :90294.WAN G Jiang 2tao , WAN G Jian , CAI Bai 2gen. A Patrol System for Railw

21、ay Signal Devices Based on GPS and RFID J.Journal of the China Railway Society , 2006, 28(5 :90294.4Antonella Albanese , Livio Marradi , G iovanni Labbiento.The RUN E project :The Integrity Performances of GNSS 2Based Railway User Navigation Equipment C/Proceed 2ings of J RC2005Joint Rail Conference

22、 , Pueblo , Colorado USA , 2005:2112218.5唐涛, 等. 基于通信的列车运行控制技术发展战略探讨J.都市快轨交通,2005, 18(6 :25229.TAN G Tao , et al. A the CB TC Develop 2ment .Urban Transit , 2005,18(6 :229. J,2006, 28(1 :63267.Gui 2gui , CA I Bai 2gen. Research on the automatic e 2lectronic map generation algorithm for the train supervision systemJ.Journal of the China Railway Society , 2006,28(1 :63267.7G laus R , Peels G ,Muller U ,el a1. Precise Rail Track Sur 2veying J.G