黎飛　程登　黃祖朋　張亮　張送　趙小羽　李淑英

摘 要：車輛的高頻活動(dòng)區(qū)域?qū)τ谲囕v的服務(wù)應(yīng)用有較大的參考意義，而汽車高頻活動(dòng)區(qū)域的計(jì)算中會(huì)基于其采集模塊提供的經(jīng)緯度數(shù)據(jù)進(jìn)行運(yùn)算，而該采集模塊的經(jīng)緯度數(shù)據(jù)誤差通常為10米左右，較大誤差的引入會(huì)影響高頻區(qū)域計(jì)算的復(fù)雜度，準(zhǔn)確性，及時(shí)性。若要降低該誤差通?？山柚岣卟杉K的采集精度，或第三方差分定位服務(wù)，但同時(shí)導(dǎo)致成本上升。本文將基于當(dāng)前車輛采集模塊的經(jīng)緯度數(shù)據(jù)精度，采用地圖網(wǎng)格化分塊索引的方式改進(jìn)了車輛高頻活動(dòng)區(qū)域的算法，提高了車輛高頻活動(dòng)區(qū)域的計(jì)算的速度和準(zhǔn)確性。

關(guān)鍵詞：網(wǎng)格 索引 高頻 區(qū)域算法

Algorithm of Vehicle High Frequency Activity Region Based on Grid Block Index

Li Fei Cheng Deng Huang Zupeng Zhang Liang Zhang Song Zhao Xiaoyu Li Shuying

Abstract：The high-frequency activity area of the vehicle has a great reference significance for the service application of the vehicle， and the calculation of the high-frequency activity area of the vehicle will be based on the longitude and latitude data provided by the collection module， and the longitude and latitude data error of the collection module is usually about 10 meters， and the introduction of large errors will affect the complexity， accuracy and timeliness of calculation in the high-frequency region. To reduce this error， it is usually possible to improve the acquisition accuracy of the acquisition module or a third-party differential positioning service， but at the same time it leads to an increase in cost. Based on the accuracy of the latitude and longitude data of the current vehicle acquisition module， this paper uses map gridding and block indexing to improve the algorithm of the vehicle high-frequency activity area， and improve the speed and accuracy of the calculation of the vehicle high-frequency activity area.

Key words：grid， index， high frequency， area algorithm

1 引言

隨著社會(huì)的發(fā)展和科技的進(jìn)步，大數(shù)據(jù)，機(jī)器學(xué)習(xí)，人工智能等高新尖技術(shù)的飛速發(fā)展促使汽車向著智能化方向發(fā)展，基于車輛位置或活動(dòng)區(qū)域的智能化服務(wù)作為其中重要的一環(huán)成為當(dāng)下研究熱點(diǎn)。智能化服務(wù)的開(kāi)展更多依賴車輛定位的精準(zhǔn)度，運(yùn)算速度，便于優(yōu)化用戶畫(huà)像，給車輛的營(yíng)銷，服務(wù)推薦等提供決策和改善方向。

當(dāng)前大部分車輛位置所采集的經(jīng)緯度誤差較大（通常為10～15米），要降低該誤差提高計(jì)算的準(zhǔn)確度有兩種方案，一則提高采集設(shè)備的精度或引入第三方的差分定位服務(wù)，但此方案會(huì)導(dǎo)致車輛成本上升;二則通過(guò)引入其他特征數(shù)據(jù)，設(shè)計(jì)更復(fù)雜的運(yùn)算模型，但此方案導(dǎo)致設(shè)計(jì)復(fù)雜性較高，運(yùn)算實(shí)效和計(jì)算的硬件成本上升。綜上兩種方案均存在一些弊端。本文將介紹一種基于當(dāng)前車輛經(jīng)緯度誤差條件下，不增加硬件成本，降低運(yùn)算的復(fù)雜性，提高運(yùn)算時(shí)效性和定位精準(zhǔn)度的優(yōu)化算法方案。

2 算法思路

整體算法分為劃分區(qū)域網(wǎng)格，建立空間索引，處理車輛位置信息，車輛位置地圖映射，計(jì)算車輛所屬網(wǎng)格，確定高頻停車區(qū)域共6個(gè)步驟，如圖1。

2.1 劃分區(qū)域網(wǎng)格

將待分析區(qū)域的地圖按照經(jīng)緯度坐標(biāo)根據(jù)一定的間隔在縱橫方向上分成M 行和N列，即MxN個(gè)網(wǎng)格，如圖2。將網(wǎng)格上每個(gè)節(jié)點(diǎn)的經(jīng)緯度作為該點(diǎn)的坐標(biāo)Pi（xi，yi），其中x表示經(jīng)度，y表示緯度，i表示網(wǎng)格節(jié)點(diǎn)編號(hào)索引，從0開(kāi)始計(jì)。同時(shí)將每個(gè)網(wǎng)格建立編號(hào)索引。

2.2 建立空間索引

這是一種分割空間對(duì)象的索引方法。即為每個(gè)網(wǎng)格分配一個(gè)動(dòng)態(tài)存儲(chǔ)區(qū)，并將該網(wǎng)格所框選的空間對(duì)象，如道路，建筑物等信息存入該網(wǎng)格對(duì)應(yīng)的存儲(chǔ)空間中。

2.3 處理車輛位置數(shù)據(jù)

依據(jù)需求提取某個(gè)群體范圍里車輛經(jīng)緯度數(shù)據(jù)并針對(duì)無(wú)效數(shù)據(jù)進(jìn)行清洗，如空值，異常漂移值等。

2.4 車輛位置在地圖映射

將清洗好的車輛經(jīng)緯度數(shù)據(jù)映射到地圖上，此時(shí)車輛每個(gè)位置將以點(diǎn)狀分布在地圖上，如圖3。

2.5 計(jì)算車輛位置所屬網(wǎng)格

假設(shè)每個(gè)網(wǎng)格的長(zhǎng)度和寬度分別為dl，dw。dw為橫向兩相鄰節(jié)點(diǎn)橫坐標(biāo)之差即經(jīng)度之差，dl為縱向相鄰兩節(jié)點(diǎn)縱坐標(biāo)之差即緯度之差（圖4）。

用車輛某個(gè)位置坐標(biāo)xi和yi分別除以dw，dl，即可獲得改位置點(diǎn)所在的行和列編號(hào)，進(jìn)而獲得網(wǎng)格編號(hào)。如公式1

行k=[yi/dl]+1

列j=[xi/dw]+1? ? ? ? ? ? ? ? 公式1

通過(guò)以上公式遍歷所有車輛位置數(shù)據(jù)，即可獲得每個(gè)位置點(diǎn)所屬的網(wǎng)格編號(hào)。

2.6 確定車輛高頻停車區(qū)域

計(jì)算各網(wǎng)格所包含的位置點(diǎn)的總數(shù)并按降序排列，選取數(shù)量最多的幾個(gè)（通常不超過(guò)3個(gè)）網(wǎng)格所在的區(qū)域即為該車輛的高頻活動(dòng)區(qū)域。結(jié)合區(qū)域內(nèi)存儲(chǔ)的空間對(duì)象，即可很好的判斷車輛的活動(dòng)喜好。如圖5

3 算法總結(jié)

該算法的有兩個(gè)關(guān)鍵點(diǎn)。其一在于合理的定義網(wǎng)格的大小。網(wǎng)格劃分越小，確認(rèn)的高頻活動(dòng)區(qū)域越精準(zhǔn)，但同時(shí)會(huì)增消耗較多計(jì)算資源和存儲(chǔ)資源，增加了計(jì)算時(shí)長(zhǎng)。其二在于計(jì)算車輛位置所屬的網(wǎng)格編號(hào)。通常的算法會(huì)用車輛經(jīng)緯度位置數(shù)據(jù)分別與每個(gè)網(wǎng)格的4個(gè)節(jié)點(diǎn)的經(jīng)緯度數(shù)據(jù)進(jìn)行比較運(yùn)算來(lái)判斷所屬網(wǎng)格，但該算法需要遍歷每個(gè)網(wǎng)格的節(jié)點(diǎn)，運(yùn)算效率不高，消耗的計(jì)算資源較多。本文算法采用車輛經(jīng)緯度位置數(shù)據(jù)除以網(wǎng)格的長(zhǎng)度和寬度的方法，僅計(jì)算一次變可以得到結(jié)果，效率較高。

4 結(jié)語(yǔ)

本文提出的算法無(wú)需引入高精采集設(shè)備或第三方差分定位服務(wù)或復(fù)雜計(jì)算模型，是一種低成本，高效率，高準(zhǔn)確率的計(jì)算車輛高頻活動(dòng)區(qū)域的算法，尤其面對(duì)在海量大數(shù)據(jù)及實(shí)時(shí)性要求較高的條件下，計(jì)算效能十分明顯。

基金項(xiàng)目：廣西創(chuàng)新驅(qū)動(dòng)發(fā)展專項(xiàng)資金資助項(xiàng)目（桂科AA18242039）;柳州市科學(xué)研究與技術(shù)開(kāi)發(fā)計(jì)劃資助項(xiàng)目（2019AG10202）

參考文獻(xiàn)：

[1]陶曉麗，張志華， 張麗等. 基于格網(wǎng)索引的點(diǎn)目標(biāo)捕捉算法[J]. 測(cè)繪與空間地理信息，2015，38（10）：200.

[2]徐松杰，陳紫強(qiáng).基于網(wǎng)格分塊的快速地圖匹配算法[J]. 桂林電子科技大學(xué)學(xué)報(bào)，2014，34（01）：33-36.

[3]張麗芬，王曉華，胡景松，宋維佳，龍斌. 基于網(wǎng)格劃分的幾種空間索引[J]. 北京理工大學(xué)學(xué)報(bào)，2004，24（02）：140-144.

[4]張順，尹洪權(quán)，吉敏. 基于網(wǎng)格索引的地圖匹配算法[J].齊魯工業(yè)大學(xué)學(xué)報(bào)[J]，2015，29（04）：77-80.