軌道交通GPS數(shù)據(jù)約簡(jiǎn)的數(shù)學(xué)模型與算法研究

1、第30卷第4期鐵道學(xué)報(bào)Vol. 30No. 4 2008年8月J OURNAL OF T H E CHINA RA IL WA Y SOCIET Y August 2008文章編號(hào):100128360(2008 0420116204軌道交通GPS 數(shù)據(jù)約簡(jiǎn)的數(shù)學(xué)模型與算法研究陳德旺, 蔡伯根, 王劍, 唐濤(北京交通大學(xué)軌道交通控制與安全國(guó)家重點(diǎn)實(shí)驗(yàn)室, 北京100044摘要:利用實(shí)測(cè)軌道GPS 數(shù)據(jù)生成電子地圖是實(shí)現(xiàn)列控智能化的一個(gè)重要環(huán)節(jié)。為減少存儲(chǔ)空間和提高列車(chē)定位的實(shí)時(shí)性, 需要對(duì)大量GPS 數(shù)據(jù)進(jìn)行約簡(jiǎn), 找出其中的少量關(guān)鍵數(shù)據(jù)。通過(guò)數(shù)學(xué)建模和分析, 軌道交通GPS 數(shù)據(jù)約簡(jiǎn)問(wèn)題是一

2、個(gè)N P 問(wèn)題, 難以求得最優(yōu)解。本文提出一種啟發(fā)式線性算法, 并給出6個(gè)性能指標(biāo)的定義。兩個(gè)鐵路區(qū)間的實(shí)測(cè)GPS 數(shù)據(jù)用于對(duì)算法的性能指標(biāo)進(jìn)行分析比較。計(jì)算結(jié)果表明, 該算法是有效的且運(yùn)行速度較快。該算法能以較低的約簡(jiǎn)率在一定誤差要求的前提下約簡(jiǎn)大量GPS 數(shù)據(jù)。在誤差約束為1m 時(shí), 約簡(jiǎn)率小于2%; 誤差約束為2m 時(shí), 約簡(jiǎn)率約為1%。隨著軌道彎曲程度的增加, 約簡(jiǎn)率有所增加。關(guān)鍵詞:軌道交通; 全球定位系統(tǒng); 電子地圖; 數(shù)據(jù)約簡(jiǎn); 啟發(fā)式算法中圖分類(lèi)號(hào):U284文獻(xiàn)標(biāo)志碼: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全球定位系統(tǒng)GPS 在城市車(chē)輛、飛機(jī)、船舶導(dǎo)航、大地測(cè)量、地圖繪制和火箭導(dǎo)彈監(jiān)控等眾多領(lǐng)域得到廣泛應(yīng)用1。同樣, 在鐵路勘測(cè)、定位和監(jiān)控方面有著好的發(fā)展前景2,3。目前歐洲各國(guó)鐵路正在加強(qiáng)利用GPS 技術(shù), 沿相應(yīng)線路設(shè)置差分基站, 并使之與移動(dòng)通信技術(shù)結(jié)合, 以提高鐵路的通過(guò)能力和可靠性4。收稿日期:2006211227; 修回日期:2007204223基金項(xiàng)目:國(guó)家自然科學(xué)基金面上項(xiàng)目

8、(60776833 ;國(guó)家自然科學(xué)基金重點(diǎn)項(xiàng)目(60634010 ;軌道交通控制與安全國(guó)家重點(diǎn)實(shí)驗(yàn)室(北京交通大學(xué) 開(kāi)放基金項(xiàng)目(SK L2007K005作者簡(jiǎn)介:陳德旺(1976 , 男, 安徽南陵人, 副教授, 博士。E 2m ail :dwchen . cn 列車(chē)調(diào)度指揮智能化是鐵路運(yùn)輸現(xiàn)代化的重要標(biāo)志5。實(shí)現(xiàn)列車(chē)的智能化調(diào)度和監(jiān)控, 可消除行車(chē)安全隱患, 提高運(yùn)行效率。精確的電子地圖是列車(chē)智能化調(diào)度和監(jiān)控的重要環(huán)節(jié)6。鐵路傳統(tǒng)的測(cè)量方法難以獲取電子地圖所需的大量基礎(chǔ)數(shù)據(jù)。采用GPS 測(cè)量操作簡(jiǎn)便、進(jìn)度快, 可極大提高工作效率7。在獲取大量軌道GPS 數(shù)據(jù)之后, 一個(gè)重要

9、問(wèn)題是采用有效的約簡(jiǎn)算法簡(jiǎn)單高效地表示軌道, 以減少存儲(chǔ)空間和提高電子地圖匹配效率, 同時(shí)要把誤差控制在允許范圍內(nèi)。軌道可分為直線軌道和曲線軌道, 直線軌道表示相對(duì)簡(jiǎn)單, 曲線軌道在電子地圖上的表示 方法則是一個(gè)難點(diǎn)。目前常用方法有NU RBS 表示8、B ézier 曲線表示等9,10。這類(lèi)曲線表示方法會(huì)導(dǎo)致數(shù)據(jù)存儲(chǔ)量增大, 尤其是相應(yīng)的地圖匹配算法復(fù)雜。實(shí)際的曲線鐵軌是漸近線形狀, 曲率半徑比較大。文獻(xiàn)6發(fā)現(xiàn), 只要取較少的點(diǎn)就可把分段直線替代曲線軌道的誤差控制在一定范圍內(nèi)。本文提出可在軌道上依次取點(diǎn), 用順次相連的折線近似代表曲線軌道。用折線表示軌道形成的誤差有兩種:橫向誤差和

10、縱向誤差。橫向誤差為折線偏離軌道的最大正交投影距離; 縱向誤差即軌道長(zhǎng)度與折線長(zhǎng)度之差。本文推導(dǎo)了數(shù)據(jù)約簡(jiǎn)的組合數(shù)學(xué)模型, 提出一種啟發(fā)式算法, 并以鐵路實(shí)測(cè)的GPS 數(shù)據(jù)對(duì)算法性能進(jìn)行分析和比較。1數(shù)據(jù)描述和數(shù)學(xué)模型1. 1數(shù)據(jù)描述本文所用的數(shù)據(jù)是青藏鐵路的實(shí)測(cè)GPS 數(shù)據(jù), 是用差分GPS 技術(shù)測(cè)量, 精度為cm 級(jí)。本文選取其中的兩個(gè)區(qū)間數(shù)據(jù)對(duì)算法效果進(jìn)行驗(yàn)證, 其中區(qū)間9935組數(shù)據(jù), 區(qū)間2有8452距離為1. 5m 3m , km 。X Y坐標(biāo), , 如圖1和圖2所示 。對(duì)于約簡(jiǎn)算法而言, 同時(shí)控制兩個(gè)誤差指標(biāo)比較困難, 本文以橫向誤差為約束條件, 再去檢驗(yàn)縱向誤差。復(fù)線區(qū)段上下行

11、線路中心線之間和車(chē)站內(nèi)相鄰股道之間的距離約為5m 。對(duì)于橫向誤差約束, 分別設(shè)為1m 和2m 。這顯然可以區(qū)分出上下行列車(chē)軌道; 同樣也可以區(qū)分開(kāi)車(chē)站內(nèi)不同股道。1. 2數(shù)學(xué)模型軌道交通GPS 數(shù)據(jù)約簡(jiǎn), 其實(shí)就是在所測(cè)數(shù)據(jù)集中選擇最少的關(guān)鍵數(shù)據(jù)點(diǎn), 構(gòu)成順次相連的折線, 并使 得每個(gè)實(shí)測(cè)數(shù)據(jù)到相應(yīng)分段上的最大正交距離不超過(guò)設(shè)定的橫向誤差約束。本文利用組合優(yōu)化理論11推導(dǎo)了數(shù)學(xué)模型描述該問(wèn)題:6ni =1z i (1 z i (0, 1 , i =2, n(2 z 1z n (3i , j (4 n , 設(shè)定的橫向誤差約束為(2 表示在這n 個(gè)數(shù)據(jù)點(diǎn)中, 如果第i, 則z i =1, 否則為0

12、。約束條件式(3 表示分段直線第一段的起點(diǎn)是該數(shù)據(jù)集的起點(diǎn); 分段直線最后一段的終點(diǎn)是數(shù)據(jù)集的終點(diǎn)。所以數(shù)據(jù)集中還有n -2個(gè)點(diǎn)可以被選為分段點(diǎn)。約束條件式(4 表示實(shí)測(cè)數(shù)據(jù)到相應(yīng)分段直線的正交距離不超過(guò)設(shè)定的橫向誤差, d i , j 表示分段點(diǎn)i 與下一分段點(diǎn)j 之間的點(diǎn)到這兩點(diǎn)連線間的正交距離。該組合問(wèn)題共有2n -2種可能的解。實(shí)際中, 一般以一個(gè)鐵路區(qū)間的GPS 數(shù)據(jù)為一個(gè)基本單元進(jìn)行約簡(jiǎn), n 約為8000。由于點(diǎn)到直線的投影距離公式是非線性的, 并且求最大投影距離不超過(guò)設(shè)定橫向誤差的約束條件也是非線性的, 所以該問(wèn)題是一個(gè)分段非線性的組合問(wèn)題。不難看出, 該問(wèn)題是一個(gè)大規(guī)模的N

13、P 完全問(wèn)題, 在有限的時(shí)間內(nèi)難以求得最優(yōu)解, 必須結(jié)合工程實(shí)際尋求較優(yōu)解。2算法和性能指標(biāo)2. 1啟發(fā)式算法該算法的基本思想是“步步為營(yíng), 不能進(jìn)則退”。具體來(lái)說(shuō), 從起點(diǎn)開(kāi)始試探下一個(gè)假設(shè)終點(diǎn), 能前進(jìn)(誤差滿足要求 盡可能地前進(jìn), 不能進(jìn)則退后一步; 找到下一個(gè)終點(diǎn)后, 再以該終點(diǎn)為起點(diǎn), 尋找下下個(gè)終點(diǎn); 如此循環(huán)直到所有數(shù)據(jù)點(diǎn)都包括在各分段中。顯然, 該算法是一個(gè)簡(jiǎn)單實(shí)用的局部?jī)?yōu)化的啟發(fā)式算法。算法的步驟為:711第4期軌道交通GPS 數(shù)據(jù)約簡(jiǎn)的數(shù)學(xué)模型與算法研究第1步將區(qū)間起點(diǎn)設(shè)為起始點(diǎn), 作為所有分段中的起始點(diǎn), i =1。第2步從起點(diǎn)i 開(kāi)始, 以該點(diǎn)之后的第2個(gè)點(diǎn)(i +2

14、為假設(shè)終點(diǎn)。第3步將起點(diǎn)和假設(shè)終點(diǎn)連接成直線。如果起點(diǎn)和終點(diǎn)的X 坐標(biāo)相等, 直線斜率為無(wú)窮大, 則用式( 5 計(jì)算正交距離, 其中的x 是起點(diǎn)或者終點(diǎn)的X 坐標(biāo); 否則, 求出該直線的斜率k 和截距b , 利用點(diǎn)到直線距離公式, 計(jì)算起點(diǎn)和假設(shè)終點(diǎn)之間的數(shù)據(jù)點(diǎn)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 小于設(shè)定的橫向誤差E , 則假設(shè)終點(diǎn)向前方(從起點(diǎn)到終點(diǎn)的方向?yàn)榍胺?移動(dòng)一個(gè)點(diǎn), 回到第3步。第6步如果D max 大于E ,終點(diǎn)的前面

15、一點(diǎn), ,2第7步。, 算法的效率取決于數(shù)據(jù)集合的規(guī)模。2. 2算法性能指標(biāo)在滿足橫向誤差約束時(shí), 算法的性能指標(biāo)有:(1 分段數(shù)m :分段直線的總數(shù), 越少越好。(2 數(shù)據(jù)約簡(jiǎn)率r :關(guān)鍵點(diǎn)數(shù)和所有數(shù)據(jù)點(diǎn)數(shù)n 之比, 反映數(shù)據(jù)約簡(jiǎn)的效率, 越小越好。實(shí)際上, 該指標(biāo)與分段數(shù)密切相關(guān), 因?yàn)殛P(guān)鍵點(diǎn)數(shù)等于分段數(shù)加1。r =n×100%(8 (3 縱向誤差L e :反映分段直線表示曲線軌道在長(zhǎng)度上的損失, 越小越好。L e =1-6m i =1k i /6n-1j =1l j ×100%(9 式中, k i 為分段直線i 的長(zhǎng)度; l j 為相鄰數(shù)據(jù)點(diǎn)間長(zhǎng)度。(4 橫向誤差的平

16、均值 E :所有點(diǎn)到相應(yīng)直線段的投影距離的平均值, 越小表明算法的魯棒性越好。(5 橫向誤差的最大值E max :所有點(diǎn)到相應(yīng)直線段投影距離的最大值, 以檢驗(yàn)算法是否滿足橫向誤差要求, 同時(shí)也間接表明算法的魯棒性, 越小越好。(6 運(yùn)行時(shí)間t :反映算法的時(shí)間效率, 越小越好。由于該算法在地圖生成前離線運(yùn)行, 不是用于列車(chē)實(shí) 時(shí)定位, 運(yùn)行時(shí)間只要不太長(zhǎng)就可接受。3計(jì)算結(jié)果及比較對(duì)兩個(gè)區(qū)間的數(shù)據(jù), 在不同的橫向誤差約束下, 算法性能指標(biāo)的比較分別如表1和表2所示。表1區(qū)間1的算法性能指標(biāo)比較性能指標(biāo)數(shù)值E/m 12m/m 12087r/%1. 220. 89L e /%0. 0130. 025

17、E max /m 0. 991. 99E /m 0. 581. 16t/s 148. 4156. 82區(qū)間E/212993r/%1. 541. 11L e /%0. 0160. 032E max /m 0. 991. 99E /m 0. 581. 08t/s 102. 7100. 3從表1和表2中可發(fā)現(xiàn)以下規(guī)律:(1 算法的約簡(jiǎn)率很低, 能以較少的關(guān)鍵數(shù)據(jù)描述大量的實(shí)測(cè)GPS 數(shù)據(jù)。橫向誤差約束為1m , 約簡(jiǎn)率不超過(guò)2%, 橫向誤差約束為2m , 約簡(jiǎn)率約為1%。(2 縱向誤差非常小。隨著橫向誤差約束的增大, 縱向誤差有所增大。在橫向誤差約束為1m 時(shí), 縱向誤差不超過(guò)萬(wàn)分之二; 橫向誤差約

18、束為2m , 縱向誤差不超過(guò)萬(wàn)分之四。(3 隨著橫向誤差約束的增大, 算法的分段數(shù)減少, 約簡(jiǎn)率降低, 而縱向誤差、橫向誤差的最大值和橫向誤差的平均值增大。(4 區(qū)間2的數(shù)據(jù)為較彎曲的曲線軌道, 在相同的橫向誤差前提下, 區(qū)間2數(shù)據(jù)的分段數(shù)和約簡(jiǎn)率要比區(qū)間1大, 而其他3項(xiàng)指標(biāo)沒(méi)有明顯的區(qū)別。(5 算法的運(yùn)行時(shí)間很短, 效率比較高。對(duì)于一個(gè)大規(guī)模的組合N P 問(wèn)題, 只要運(yùn)行時(shí)間不是太長(zhǎng)就可以接受。算法是生成電子地圖的前期環(huán)節(jié), 是離線運(yùn)行的, 應(yīng)該說(shuō)速度是較快的。區(qū)間1的數(shù)據(jù)規(guī)模大, 運(yùn)行時(shí)間略長(zhǎng); 不同的橫向誤差約束對(duì)算法速度的影811鐵道學(xué)報(bào)第30卷 響很小。這也說(shuō)明該算法是一個(gè)線性算法

19、, 算法運(yùn)行時(shí)間和數(shù)據(jù)集的大小呈線性關(guān)系。這里選擇2個(gè)運(yùn)行結(jié)果進(jìn)行顯示。區(qū)間1的數(shù)據(jù)在橫向誤差約束為1m 的情況下, 算法的運(yùn)行結(jié)果如圖3所示。區(qū)間2的數(shù)據(jù)在橫向誤差約束為2m 的情況下, 算法的運(yùn)行結(jié)果如圖4所示。圖3、圖4中的圓點(diǎn)為分段點(diǎn)。可發(fā)現(xiàn)在軌道彎曲的地方圓點(diǎn)密度高, 在軌道平直的地方圓點(diǎn)密度低 。4結(jié)束語(yǔ)把誤差控制在允許的范圍內(nèi), 對(duì)大量實(shí)測(cè)GPS 數(shù)據(jù)進(jìn)行約簡(jiǎn)以盡可能簡(jiǎn)單高效地表示軌道, 對(duì)列控電子地圖的自動(dòng)生成和列車(chē)實(shí)時(shí)定位具有重要意義。今后在算法研究的基礎(chǔ)上, 電子地圖的數(shù)據(jù)格式、存儲(chǔ)方式、長(zhǎng)度誤差的補(bǔ)償、快速地圖匹配算法還需做深入研究。參考文獻(xiàn):1劉基余, 等. 全球定位系

20、統(tǒng)原理及應(yīng)用M .北京:測(cè)繪出版社,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 技術(shù)的鐵路信號(hào)設(shè)備巡檢系統(tǒng)J.鐵道學(xué)報(bào), 2006, 28(5 :90294.WAN G Jiang 2tao , WAN G Jian , CAI Bai 2gen. A Patro

21、l System for Railway 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 RC2005Joi

22、nt Rail Conference , Pueblo , Colorado USA , 2005:2112218.5唐濤, 等. 基于通信的列車(chē)運(yùn)行控制技術(shù)發(fā)展戰(zhàn)略探討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