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

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

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

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

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

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

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

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

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

14、第3步將起點和假設(shè)終點連接成直線。如果起點和終點的X 坐標相等, 直線斜率為無窮大, 則用式( 5 計算正交距離, 其中的x 是起點或者終點的X 坐標; 否則, 求出該直線的斜率k 和截距b , 利用點到直線距離公式, 計算起點和假設(shè)終點之間的數(shù)據(jù)點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è)終點向前方(從起點到終點的方向為前方 移動一個點, 回到第3步。第6步如果D max 大于E ,終點的前面一點, ,2

15、第7步。, 算法的效率取決于數(shù)據(jù)集合的規(guī)模。2. 2算法性能指標在滿足橫向誤差約束時, 算法的性能指標有:(1 分段數(shù)m :分段直線的總數(shù), 越少越好。(2 數(shù)據(jù)約簡率r :關(guān)鍵點數(shù)和所有數(shù)據(jù)點數(shù)n 之比, 反映數(shù)據(jù)約簡的效率, 越小越好。實際上, 該指標與分段數(shù)密切相關(guān), 因為關(guān)鍵點數(shù)等于分段數(shù)加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 為相鄰數(shù)據(jù)點間長度。(4 橫向誤差的平均值 E :所有點到相應(yīng)直線段的投影

16、距離的平均值, 越小表明算法的魯棒性越好。(5 橫向誤差的最大值E max :所有點到相應(yīng)直線段投影距離的最大值, 以檢驗算法是否滿足橫向誤差要求, 同時也間接表明算法的魯棒性, 越小越好。(6 運行時間t :反映算法的時間效率, 越小越好。由于該算法在地圖生成前離線運行, 不是用于列車實 時定位, 運行時間只要不太長就可接受。3計算結(jié)果及比較對兩個區(qū)間的數(shù)據(jù), 在不同的橫向誤差約束下, 算法性能指標的比較分別如表1和表2所示。表1區(qū)間1的算法性能指標比較性能指標數(shù)值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區(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 算法的約簡率很低, 能以較少的關(guān)鍵數(shù)據(jù)描述大量的實測GPS 數(shù)據(jù)。橫向誤差約束為1m , 約簡率不超過2%, 橫向誤差約束為2m , 約簡率約為1%。(2 縱向誤差非常小。隨著橫向誤差約束的增大, 縱向誤差有所增大。在橫向誤差約束為1m 時, 縱向誤差不超過萬分之二; 橫向誤差約束為2m , 縱向誤差不超過萬分之四

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

19、關(guān)系。這里選擇2個運行結(jié)果進行顯示。區(qū)間1的數(shù)據(jù)在橫向誤差約束為1m 的情況下, 算法的運行結(jié)果如圖3所示。區(qū)間2的數(shù)據(jù)在橫向誤差約束為2m 的情況下, 算法的運行結(jié)果如圖4所示。圖3、圖4中的圓點為分段點。可發(fā)現(xiàn)在軌道彎曲的地方圓點密度高, 在軌道平直的地方圓點密度低 。4結(jié)束語把誤差控制在允許的范圍內(nèi), 對大量實測GPS 數(shù)據(jù)進行約簡以盡可能簡單高效地表示軌道, 對列控電子地圖的自動生成和列車實時定位具有重要意義。今后在算法研究的基礎(chǔ)上, 電子地圖的數(shù)據(jù)格式、存儲方式、長度誤差的補償、快速地圖匹配算法還需做深入研究。參考文獻:1劉基余, 等. 全球定位系統(tǒng)原理及應(yīng)用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 技術(shù)的鐵路信號設(shè)備巡檢系統(tǒng)J.鐵道學(xué)報, 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唐濤, 等. 基于通信的列車運行控制技術(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.G