第30卷第4期铁道学报Vol.30No.42008年8月JOURNALOFTHECHINARAILWAYSOCIETYAugust2008:100128360(20080420116204轨道交通GPS数据约简的数学模型与算法研究陈德旺,蔡伯根,王剑,唐涛(北京交通大学轨道交通控制与安全国家重点实验室,北京100044摘要:利用实测轨道GPS数据生成电子地图是实现列控智能化的一个重要环节。为减少存储空间和提高列车定位的实时性,需要对大量GPS数据进行约简,找出其中的少量关键数据。通过数学建模和分析,轨道交通GPS数据约简问题是一个NP问题,难以求得最优解。本文提出一种启发式线性算法,并给出6个性能指标的定义。两个铁路区间的实测GPS数据用于对算法的性能指标进行分析比较。计算结果表明,该算法是有效的且运行速度较快。该算法能以较低的约简率在一定误差要求的前提下约简大量GPS数据。在误差约束为1m时,约简率小于2%;误差约束为2m时,约简率约为1%。随着轨道弯曲程度的增加,约简率有所增加。关键词:轨道交通;全球定位系统;电子地图;数据约简;启发式算法:U284文献标志码:AMathematicalModelandReductionCENCAI,G激an,TANGTao(ofRailandSafety,Bei激ng激aotongUniversity,Bei激ng100044,ChinaAbstract:dataofrailwayGPS(GlobalPositionSystemtogenerateanelectronicmapisanimprotantsteptorealizetheintelligenttraincontrol.Todecreasethememoryspaceandenhancethereal2timepropertyoftrainpositioning,itisnecessarytofindaneffectivedatareductionalgorithmforhugeGPSdata.ModelingandanalysisindicatethattheproblemofrailwayGPSdatareductionisaNPproblemanditishardtogettheoptimalsolution.Aheuristicalgorithmwasputforwardand6performanceindexesweredefinedinthispaper.ThesurveyedGPSdataoftworailwaysectionswereusedtoanalyzetheperformanceindexofthealgo2rithm.Thecomputationalresultsshowthatthealgorithmiseffectiveandtherunningspeedofthealgorithmisveryhigh.ThealgorithmcanreducethehugeGPSdatainaverylowreductionrateundercertainerrorrequire2ment.Whentheerrorrequirementis1m,thereductionrateislessthan2%;whentheerrorrequirementis2m,thereductionrateisabout1%.Withtheincreaseofthecamberofrailway,thereductionrateincreases.Keywords:railtraffic;GPS;electronicmap;datareduction;heuristicalgorithm全球定位系统GPS在城市车辆、飞机、船舶导航、大地测量、地图绘制和火箭导弹监控等众多领域得到广泛应用[1]。同样,在铁路勘测、定位和监控方面有着好的发展前景[2,3]。目前欧洲各国铁路正在加强利用GPS技术,沿相应线路设置差分基站,并使之与移动通信技术结合,以提高铁路的通过能力和可靠性[4]。收稿日期:2006211227;修回日期:2007204223基金项目:国家自然科学基金面上项目(60776833;国家自然科学基金重点项目(60634010;轨道交通控制与安全国家重点实验室(北京交通大学开放基金项目(SKL2007K005作者简介:陈德旺(1976─,男,安徽南陵人,副教授,博士。E2mail:dwchen@bjtu.edu.cn列车调度指挥智能化是铁路运输现代化的重要标志[5]。实现列车的智能化调度和监控,可消除行车安全隐患,提高运行效率。精确的电子地图是列车智能化调度和监控的重要环节[6]。铁路传统的测量方法难以获取电子地图所需的大量基础数据。采用GPS测量操作简便、进度快,可极大提高工作效率[7]。在获取大量轨道GPS数据之后,一个重要问题是采用有效的约简算法简单高效地表示轨道,以减少存储空间和提高电子地图匹配效率,同时要把误差控制在允许范围内。轨道可分为直线轨道和曲线轨道,直线轨道表示相对简单,曲线轨道在电子地图上的表示方法则是一个难点。目前常用方法有NURBS表示[8]、Bézier曲线表示等[9,10]。这类曲线表示方法会导致数据存储量增大,尤其是相应的地图匹配算法复杂。实际的曲线铁轨是渐近线形状,曲率半径比较大。文献[6]发现,只要取较少的点就可把分段直线替代曲线轨道的误差控制在一定范围内。本文提出可在轨道上依次取点,用顺次相连的折线近似代表曲线轨道。用折线表示轨道形成的误差有两种:横向误差和纵向误差。横向误差为折线偏离轨道的...