隨著城市規(guī)模的不斷擴(kuò)大和便民業(yè)務(wù)的發(fā)展，行車(chē)導(dǎo)航、共享汽車(chē)和物流派送等應(yīng)用已經(jīng)深入人們?nèi)粘Ｉ钪?。這些應(yīng)用都不可避免地需要使用GPS、北斗等定位系統(tǒng)，進(jìn)而產(chǎn)生了大量的軌跡數(shù)據(jù)。然而，普通民用GPS定位系統(tǒng)上傳的位置數(shù)據(jù)會(huì)由于許多緣故發(fā)生與物體的實(shí)際地理位置不同的現(xiàn)象，產(chǎn)生了米級(jí)別的誤差，一般在10米以?xún)?nèi)。此外，在數(shù)據(jù)傳輸、存儲(chǔ)和耗電的條件限制下，導(dǎo)致軌跡點(diǎn)采樣頻率不宜過(guò)高。因此，以上因素導(dǎo)致采集到的移動(dòng)對(duì)象位置與其實(shí)際所在道路之間有一定距離偏差。為了使接收到的位置數(shù)據(jù)可以真實(shí)反映移動(dòng)對(duì)象的運(yùn)行軌跡，需要進(jìn)行軌跡的各種預(yù)處理工作，其中地圖匹配是一項(xiàng)十分重要的工作。
一、地圖匹配
地圖匹配是將存在誤差或漂移的GPS觀測(cè)點(diǎn)匹配至路網(wǎng)上的算法，它常用于還原觀測(cè)點(diǎn)的真實(shí)位置和移動(dòng)物體的運(yùn)動(dòng)軌跡。如圖1，地圖匹配算法將采集到點(diǎn)1、2、3映射到路段上。地圖匹配可分為離線和實(shí)時(shí)兩種處理方式：離線方式接收過(guò)去一段時(shí)間觀測(cè)到的批量軌跡數(shù)據(jù)，并計(jì)算輸出全量軌跡的最優(yōu)匹配結(jié)果。其優(yōu)勢(shì)在于準(zhǔn)確度高。然而，它的處理過(guò)程十分耗時(shí)，因此，面對(duì)監(jiān)測(cè)和追蹤等需要實(shí)時(shí)返回計(jì)算結(jié)果的場(chǎng)景難免力有不逮；實(shí)時(shí)地圖匹配則可以很好地彌補(bǔ)離線處理時(shí)延大的缺陷。目前，基于HMM的實(shí)時(shí)地圖匹配算法[2]被廣泛使用于很多業(yè)務(wù)場(chǎng)景中,如公交車(chē)實(shí)時(shí)位置播報(bào)、快遞員配送位置跟蹤。以?；愤\(yùn)輸車(chē)輛的監(jiān)管為例，?；愤\(yùn)輸車(chē)若偏離原報(bào)備路線，通過(guò)實(shí)時(shí)的地圖匹配可以在第一時(shí)間獲取其異常行為及最新位置，實(shí)現(xiàn)了對(duì)?；奋?chē)輛行駛路線的實(shí)時(shí)監(jiān)測(cè)。barefoot [1]是一個(gè)開(kāi)源項(xiàng)目，它基于實(shí)時(shí)地圖匹配算法提供了實(shí)時(shí)地圖匹配服務(wù)。本文接下來(lái)主要從算法思想和實(shí)現(xiàn)思路兩方面介紹開(kāi)源項(xiàng)目barefoot中的實(shí)時(shí)地圖匹配服務(wù)。
二、算法思想
Barefoot 是一個(gè)開(kāi)源的Java項(xiàng)目，它提供了離線/實(shí)時(shí)地圖匹配及空間分析等服務(wù)，其中實(shí)時(shí)地圖匹配的實(shí)現(xiàn)思路以Goh[2] 提出的算法作為參考。如圖2所示，Barefoot提供的實(shí)時(shí)地圖匹配演示圖。
Goh[2]提出的算法基于隱馬爾可夫模型(HMM)，并采用可變滑動(dòng)窗口進(jìn)行回溯計(jì)算，實(shí)現(xiàn)了高精度低延時(shí)的實(shí)時(shí)地圖匹配。
其主要流程大體分成三步， 1）尋找候選路網(wǎng)點(diǎn)，2）計(jì)算發(fā)射和轉(zhuǎn)移概率，3）獲取計(jì)算結(jié)果。
?1）尋找候選路網(wǎng)點(diǎn)
尋找候選路網(wǎng)點(diǎn)是指，針對(duì)每一個(gè)軌跡點(diǎn)z_t，找到距離z_t指定距離(默認(rèn)為50m)的路段，計(jì)算每條路段上距離z_t最近的位置，即為候選路網(wǎng)點(diǎn)。候選路網(wǎng)點(diǎn)通常為軌跡點(diǎn)z_t在對(duì)應(yīng)路段的垂直投影點(diǎn)或路段的端點(diǎn)。
2）計(jì)算發(fā)射和轉(zhuǎn)移概率
獲取到軌跡點(diǎn)z_t對(duì)應(yīng)的候選路網(wǎng)點(diǎn)集合S_t后，以z_t到每一個(gè)候選路網(wǎng)點(diǎn)的距離和GPS定位誤差為參數(shù)，計(jì)算候選路網(wǎng)點(diǎn)的發(fā)射概率P(z_t |s_t)；再針對(duì)上一時(shí)刻的候選路網(wǎng)點(diǎn)集合S_(t-1)與本次集合S_t中的每一組候選點(diǎn)，以?xún)蓚€(gè)候選點(diǎn)之間最短路徑的長(zhǎng)度作為主要參數(shù)計(jì)算這兩點(diǎn)之間的轉(zhuǎn)移概率。
3）獲取計(jì)算結(jié)果
概率計(jì)算完成后，通過(guò)在線Viterbi算法檢驗(yàn)是否存在結(jié)果點(diǎn)，并返回到達(dá)該點(diǎn)的最優(yōu)路徑。
在HMM基礎(chǔ)之上，barefoot擴(kuò)展了兩種概率模型：過(guò)濾概率和序列概率。其中，過(guò)濾概率P(s_t |z_0…z_t)用以計(jì)算在已觀測(cè)到軌跡點(diǎn)序列z_0…z_t的條件下，最可能符合真實(shí)情況的路網(wǎng)點(diǎn)s_t；序列概率P(s_0…s_t |z_0…z_t)則在已觀測(cè)到軌跡點(diǎn)序列z_0…z_t的條件下，計(jì)算在路網(wǎng)上到達(dá)點(diǎn)s_t 最可能的路徑。
需要注意的是，在轉(zhuǎn)移概率和序列概率的計(jì)算過(guò)程中，需要使用歷史軌跡點(diǎn)對(duì)應(yīng)的候選路網(wǎng)點(diǎn)集合作為參數(shù)。因此，barefoot采用了可變滑動(dòng)窗口來(lái)保存歷史狀態(tài)?？勺兓瑒?dòng)窗口指的是窗口中可容納的路網(wǎng)點(diǎn)集合數(shù)固定，而總路網(wǎng)點(diǎn)數(shù)量取決于每個(gè)路網(wǎng)點(diǎn)集中的點(diǎn)數(shù)，是可變的值。當(dāng)接收到一個(gè)新軌跡點(diǎn)時(shí)，可變滑動(dòng)窗口向前擴(kuò)展一位，同時(shí)根據(jù)配置中的窗口上限參數(shù)來(lái)判斷是否需要清除當(dāng)前窗口中的歷史路網(wǎng)點(diǎn)集。Barefoot 提供了狀態(tài)更新TTL、路網(wǎng)點(diǎn)集合數(shù)量上限k和時(shí)間段上限τ 三個(gè)窗口配置參數(shù)用于配置路網(wǎng)點(diǎn)集合數(shù)。
三、實(shí)現(xiàn)思路
Barefoot通過(guò)啟動(dòng)tracker server接收軌跡點(diǎn)，并發(fā)布計(jì)算結(jié)果。tracker server根據(jù)配置文件中的參數(shù)初始化指定容積的線程池，并為每一個(gè)發(fā)送數(shù)據(jù)的客戶(hù)端分配一個(gè)處理線程T。T會(huì)持續(xù)接收客戶(hù)端發(fā)送的軌跡數(shù)據(jù)，并將計(jì)算結(jié)果發(fā)送回客戶(hù)端。當(dāng)客戶(hù)端長(zhǎng)時(shí)間沒(méi)有向tracker server發(fā)送消息時(shí)，對(duì)應(yīng)的連接將被中斷。在以上流程中，耗時(shí)較長(zhǎng)的計(jì)算部分由處理線程T決定是否進(jìn)行異步計(jì)算。
為實(shí)現(xiàn)以上計(jì)算步驟中的空間范圍查詢(xún)和最短路徑規(guī)劃，barefoot需要在內(nèi)存中維護(hù)路網(wǎng)結(jié)構(gòu)。它使用的方法是通過(guò)查詢(xún)讀取數(shù)據(jù)庫(kù)中的路網(wǎng)表，并根據(jù)道路線的屬性值構(gòu)建路網(wǎng)有向圖和帶有道路線空間范圍的四叉樹(shù)索引來(lái)實(shí)現(xiàn)最短路徑規(guī)劃。在空間查詢(xún)獲取候選路網(wǎng)點(diǎn)時(shí)，使用索引獲取空間范圍內(nèi)的道路線id，并在道路線上通過(guò)插值計(jì)算出與軌跡點(diǎn)距離最近的候選路網(wǎng)點(diǎn)的坐標(biāo)。
針對(duì)每個(gè)軌跡點(diǎn)，barefoot將其對(duì)應(yīng)的候選路網(wǎng)點(diǎn)集合保存至?xí)r間窗內(nèi)。時(shí)間窗使用優(yōu)先隊(duì)列(PriorityBlockingQueue)實(shí)現(xiàn)，在提供超時(shí)清理和新增入隊(duì)功能的基礎(chǔ)上，起到保證線程安全的作用。時(shí)間窗內(nèi)的候選路網(wǎng)點(diǎn)集合通過(guò)鏈表相連，方便獲取到每個(gè)路網(wǎng)點(diǎn)在上一狀態(tài)中的關(guān)聯(lián)點(diǎn)，以及本集合中最可能為真的目標(biāo)路網(wǎng)點(diǎn)(如圖4中加粗的點(diǎn))。本次候選路網(wǎng)點(diǎn)集合更新的同時(shí)，歷史點(diǎn)集合中既不是目標(biāo)點(diǎn)又與后繼路網(wǎng)點(diǎn)無(wú)關(guān)聯(lián)的點(diǎn)將被移除。
四、測(cè)試結(jié)果
Barefoot 使用合理的索引和路網(wǎng)結(jié)構(gòu)，在Goh[2] 的實(shí)時(shí)地圖匹配算法的基礎(chǔ)上擴(kuò)展了概率模型，實(shí)現(xiàn)了針對(duì)軌跡點(diǎn)實(shí)時(shí)地圖匹配的毫秒級(jí)響應(yīng)。經(jīng)測(cè)試，針對(duì)單個(gè)軌跡點(diǎn)的地圖匹配，Barefoot的計(jì)算耗時(shí)在50~200ms之間(詳見(jiàn)圖5)。
針對(duì)當(dāng)前民用GPS的普遍采樣頻率低的現(xiàn)實(shí)情況，它也可以做到地圖匹配結(jié)果的實(shí)時(shí)返回。但是，barefoot的實(shí)現(xiàn)方式也使它具有一定的局限性。
Barefoot 采用固定數(shù)量的socket連接方式提供服務(wù)。因此，當(dāng)連接的客戶(hù)端超出一定數(shù)量時(shí)，服務(wù)端的響應(yīng)速度會(huì)受到影響；同時(shí)Barefoot沒(méi)有開(kāi)放Kafka、Storm等實(shí)時(shí)平臺(tái)的接入方式，這使得其使用方式并不靈活。在地圖匹配計(jì)算方面，由于受到軌跡數(shù)據(jù)信息量不足的限制，在計(jì)算轉(zhuǎn)移概率時(shí)，對(duì)路徑cost的計(jì)算不是以軌跡點(diǎn)速度為參數(shù)，而是采用固定參數(shù)進(jìn)行模擬計(jì)算。導(dǎo)致在一些情況下可能會(huì)對(duì)計(jì)算結(jié)果產(chǎn)生影響。除此以外，目前barefoot只支持OSM路網(wǎng)數(shù)據(jù)，不支持更加靈活的路網(wǎng)模型，且每次啟動(dòng)都將路網(wǎng)數(shù)據(jù)導(dǎo)入JVM中，這種方式限制了其擴(kuò)展性和遷移性。諸如此類(lèi)問(wèn)題，都是在實(shí)現(xiàn)或者應(yīng)用時(shí)可以改進(jìn)的方向。例如，可以通過(guò)redis等分布式緩存技術(shù)優(yōu)化路網(wǎng)構(gòu)建的方法，使其更加適用于分布式場(chǎng)景；還可以針對(duì)特定路網(wǎng)數(shù)據(jù)的信息量對(duì)概率計(jì)算公式進(jìn)行改進(jìn)，通過(guò)這些方式使其更適用于特定的業(yè)務(wù)場(chǎng)景。
目前，JUST時(shí)空數(shù)據(jù)平臺(tái)[3]吸收了Barefoot優(yōu)秀的設(shè)計(jì)思路，針對(duì)Barefoot的不足，正在實(shí)現(xiàn)一套集實(shí)時(shí)數(shù)據(jù)接入、實(shí)時(shí)地圖匹配、實(shí)時(shí)地圖展示等高可擴(kuò)展的完整解決方案。
參考文獻(xiàn)
[1] https://github.com/bmwcarit/barefoot
[2] C.Y. Goh, J. Dauwels, N. Mitrovic, M.T. Asif, A. Oran, and P. Jaillet. Online map-matching based on Hidden Markov model for real-time traffic sensing applications. In International IEEE Conference on Intelligent Transportation Systems, 2012.
[3] https://just.urban-computing.cn/
