基于Spark Streaming的海量GPS數(shù)據(jù)實(shí)時(shí)地圖匹配算法

陳艷艷 李四洋 張?jiān)瞥?/p>

摘 要：浮動(dòng)車(chē)GPS數(shù)據(jù)作為交通信息處理的基礎(chǔ)，隨著被監(jiān)控車(chē)輛數(shù)量的高速增長(zhǎng)，產(chǎn)生了海量GPS數(shù)據(jù)，對(duì)地圖匹配提出了挑戰(zhàn)。為了解決傳統(tǒng)匹配方法難以滿足匹配效率和精度的不足，提出一種針對(duì)海量GPS數(shù)據(jù)的實(shí)時(shí)并行地圖匹配算法，能夠同時(shí)保證較高匹配精度和運(yùn)算效率。為構(gòu)建一種面向?qū)崟r(shí)數(shù)據(jù)流的高效、準(zhǔn)確實(shí)時(shí)地圖匹配算法，首先通過(guò)引入速度、方向綜合權(quán)重因子對(duì)依賴(lài)歷史軌跡的離線地圖匹配算法進(jìn)行重構(gòu)，進(jìn)而引入Spark Streaming分布式計(jì)算框架，實(shí)現(xiàn)地圖匹配算法的實(shí)時(shí)、并行運(yùn)算，大幅提升實(shí)時(shí)地圖匹配效率。實(shí)驗(yàn)結(jié)果表明，該算法在復(fù)雜路段的匹配準(zhǔn)確率較常規(guī)拓?fù)淦ヅ渌惴ㄌ岣?0%以上，整體匹配準(zhǔn)確率達(dá)到95%以上；在匹配效率方面，較同等數(shù)量的單機(jī)服務(wù)器效率可提高4倍左右。實(shí)驗(yàn)結(jié)果表明，該算法在由11臺(tái)機(jī)器組成的計(jì)算集群上實(shí)現(xiàn)8 000萬(wàn)個(gè)GPS數(shù)據(jù)點(diǎn)的實(shí)時(shí)地圖匹配，證明了該算法可以完成城市地區(qū)的實(shí)時(shí)車(chē)輛匹配。

關(guān)鍵詞：海量； GPS； 并行計(jì)算； 地圖匹配； 實(shí)時(shí)計(jì)算； Spark

中圖分類(lèi)號(hào)：TP391 文獻(xiàn)標(biāo)志碼：A?文章編號(hào)：1001-3695（2024）05-008-1338-05

doi：10.19734/j.issn.1001-3695.2023.08.0424

Massive GPS data real-time map matching algorithm based on Spark Streaming

Abstract：Floating car GPS data serves as the foundation for processing traffic information， with the rapid increase in the number of monitored vehicles， a massive amount of GPS data is generated， posing great challenges to map matching. To address the shortcomings of traditional matching methods in terms of matching efficiency and accuracy， this paper proposed a real time parallel map matching algorithm for massive GPS data that ensured both high matching accuracy and computational efficiency. This paper firstly reconstructed an efficient and accurate real-time map matching algorithm for streaming data by introducing a comprehensive weight factor that considered velocity and direction to enhance the offline map matching algorithm that relied on historical trajectories. Then，it introduced the Spark Streaming distributed computing framework to achieve real-time and parallel computation of the map matching algorithm， significantly improving the efficiency of real-time map matching. Experimental results demonstrate that the proposed algorithm achieves more than a 10% increase in matching accuracy compared to conventional topological matching algorithms on complex road sections， with an overall matching accuracy of over 95%. In terms of matching efficiency， it achieves approximately a fourfold improvement compared to an equivalent number of standalone servers. The experimental results show that the proposed algorithm achieves real-time map matching of 80 million GPS data points on a computing cluster composed of 11 machines， proving that the proposed algorithm can achieve real-time vehicle matching in urban areas.

Key words：massive; GPS; parallel calculation; map matching; real-time computing; Spark

0 引言

道路上行駛的車(chē)輛裝備GPS，實(shí)時(shí)采集其運(yùn)行的位置數(shù)據(jù)，是道路實(shí)時(shí)路況計(jì)算、交通事件檢測(cè)、交通趨勢(shì)預(yù)測(cè)等交通監(jiān)管應(yīng)用數(shù)據(jù)的基礎(chǔ)。由于GPS數(shù)據(jù)存在一定的偏移［1］，地圖匹配處理將車(chē)輛GPS軌跡數(shù)據(jù)糾正到其行駛的路段上，為眾多智能交通應(yīng)用提供必需的車(chē)輛行駛路徑信息，因此成為智能交通關(guān)鍵支撐算法。當(dāng)前城市中對(duì)車(chē)輛實(shí)時(shí)監(jiān)測(cè)的規(guī)模越來(lái)越大，例如在首都北京，實(shí)時(shí)監(jiān)測(cè)的車(chē)輛數(shù)量已經(jīng)接近100萬(wàn)輛，同時(shí)在線的車(chē)輛數(shù)量峰值也達(dá)到60萬(wàn)輛。意味著在1～5 s的高采樣頻率下，每秒會(huì)產(chǎn)生超過(guò)40萬(wàn)條等待處理的車(chē)輛GPS數(shù)據(jù)。爆發(fā)增長(zhǎng)的GPS數(shù)據(jù)對(duì)地圖匹配處理提出了嚴(yán)峻的挑戰(zhàn)。當(dāng)前地圖匹配算法多數(shù)為串行匹配，運(yùn)行于單機(jī)系統(tǒng)中，其中優(yōu)秀的算法如Hmm地圖匹配算法［2］、PIF地圖匹配算法［3］等，匹配效率只能達(dá)到2萬(wàn)條/s，遠(yuǎn)不能滿足城市范圍大規(guī)模GPS數(shù)據(jù)實(shí)時(shí)匹配的要求。而將海量數(shù)據(jù)分散到多個(gè)單機(jī)系統(tǒng)中進(jìn)行同步匹配的方法，則遇到計(jì)算任務(wù)分配困難、缺少負(fù)載均衡機(jī)制、出錯(cuò)后難以自動(dòng)恢復(fù)等弊端，難以工程化實(shí)施。伴隨著浮動(dòng)車(chē)軌跡數(shù)據(jù)的增長(zhǎng)和智能交通應(yīng)用的多樣化和智能化，地圖匹配的效率和實(shí)時(shí)性需求越來(lái)越高。目前針對(duì)實(shí)時(shí)地圖匹配的研究，如文獻(xiàn)［4］提出了WI map-matching algorithm，首先使用基于權(quán)值的匹配算法將軌跡匹配在路鏈中，然后使用插值法對(duì)匹配路徑進(jìn)行修正，對(duì)比實(shí)驗(yàn)表明，WIMM效率相對(duì)于IVMM與STMM有極大提高。文獻(xiàn)［5］將浮動(dòng)車(chē)行駛距離與GPS點(diǎn)偏移映射為狀態(tài)轉(zhuǎn)移概率與狀態(tài)顯示概率，提出基于隱馬爾可夫模型的地圖匹配算法。文獻(xiàn)［6］設(shè)計(jì)了基于Hmm的改進(jìn)實(shí)時(shí)地圖匹配算法，并在新加坡路網(wǎng)的測(cè)試中表現(xiàn)較好。以上算法在提高準(zhǔn)確率的同時(shí)難以兼顧效率，或?yàn)闈M足效率需求而犧牲部分準(zhǔn)確率，但在特殊應(yīng)用場(chǎng)景下，人們希望能夠同時(shí)提升效率與準(zhǔn)確率。

通過(guò)以上兩方面的分析，考慮到城市路網(wǎng)及路況的復(fù)雜性，針對(duì)海量GPS數(shù)據(jù)的實(shí)時(shí)匹配問(wèn)題，本文通過(guò)引入速度權(quán)重因子，重構(gòu)了一種新的地圖匹配算法以應(yīng)對(duì)實(shí)時(shí)計(jì)算的需求，并針對(duì)匹配效率不足的問(wèn)題，基于Spark Streaming計(jì)算框架實(shí)現(xiàn)了并行實(shí)時(shí)匹配計(jì)算。

1 實(shí)時(shí)地圖匹配算法

1.1 浮動(dòng)車(chē)地圖匹配算法難點(diǎn)分析

浮動(dòng)車(chē)數(shù)據(jù)是一段由時(shí)空關(guān)聯(lián)的車(chē)輛位置狀態(tài)信息組成的數(shù)據(jù)流，代表浮動(dòng)車(chē)從開(kāi)始到當(dāng)前時(shí)刻的行駛軌跡。對(duì)于一輛浮動(dòng)車(chē)，時(shí)間段

（t1，t2，…，tk）產(chǎn)生的k個(gè)點(diǎn)組成軌跡P，每個(gè)點(diǎn)pi由（ID，lat，lng，timestamp，speed，angle）等字段構(gòu)成，ID代表這輛浮動(dòng)車(chē)的唯一標(biāo)識(shí)，timestamp表示定時(shí)數(shù)據(jù)采集時(shí)刻標(biāo)識(shí)，lat和lng分別表示緯度和經(jīng)度，speed表示車(chē)輛當(dāng)前速度，angle表示車(chē)輛當(dāng)前航向角。地圖匹配將浮動(dòng)車(chē)GPS定位數(shù)據(jù)與數(shù)字地圖進(jìn)行匹配，使目標(biāo)點(diǎn)精確定位到路網(wǎng)中。在保證匹配精準(zhǔn)度和強(qiáng)實(shí)時(shí)性的要求下，浮動(dòng)車(chē)行駛環(huán)境、數(shù)據(jù)質(zhì)量參差不齊，及存在海量數(shù)據(jù)等問(wèn)題，給實(shí)時(shí)地圖匹配帶來(lái)了挑戰(zhàn)，具體難點(diǎn)如下：

a）車(chē)輛行駛環(huán)境及數(shù)據(jù)質(zhì)量。近年來(lái)隨著定位技術(shù)的突破和浮動(dòng)車(chē)采集設(shè)備性能的提升，采集到的定位數(shù)據(jù)精準(zhǔn)度大大提升，但是車(chē)輛行駛環(huán)境受到建筑物、信號(hào)干擾、駕駛行為以及采集設(shè)備的采樣頻率等情況的影響，要求匹配算法具有精準(zhǔn)度的同時(shí)具備較強(qiáng)的魯棒性，能夠應(yīng)對(duì)各類(lèi)異常數(shù)據(jù)。

b）海量數(shù)據(jù)處理及復(fù)雜路網(wǎng)。截止到2022年年底，北京市公路里程已達(dá)到2.2萬(wàn)km，主要道路達(dá)到7 000 km以上，汽車(chē)保有量超過(guò)600萬(wàn)輛，形成了較為復(fù)雜的城市路網(wǎng)和交通運(yùn)行態(tài)勢(shì)，給地圖匹配的準(zhǔn)確度和效率增加了難度。

1.2 實(shí)時(shí)地圖匹配算法選型

目前，地圖匹配算法可以分為幾何地圖匹配算法、拓?fù)涞貓D匹配算法及高級(jí)地圖匹配算法三大類(lèi)。幾何分析法只考慮了浮動(dòng)車(chē)軌跡與道路形狀的幾何關(guān)系，計(jì)算簡(jiǎn)單，匹配效率較高，但是在實(shí)際應(yīng)用中準(zhǔn)確率較低，不適合在大部分路網(wǎng)中使用。高級(jí)地圖匹配算法［7，8］，如模糊邏輯、隱馬爾可夫模型地圖匹配算法，將地圖匹配問(wèn)題轉(zhuǎn)換為復(fù)雜數(shù)學(xué)模型，雖然匹配準(zhǔn)確率較高，但是計(jì)算復(fù)雜度高、匹配效率低下，不適合海量浮動(dòng)車(chē)數(shù)據(jù)的地圖匹配。而拓?fù)涞貓D匹配算法在大數(shù)據(jù)地圖匹配場(chǎng)景中應(yīng)用最為廣泛，如文獻(xiàn)［9］所述，拓?fù)涞貓D匹配方法充分考慮了路段之間的拓?fù)潢P(guān)系，以及車(chē)輛定位位置與道路距離、車(chē)輛與道路方向夾角等參數(shù)對(duì)匹配結(jié)果的影響。相比于高級(jí)地圖匹配算法，拓?fù)涞貓D匹配算法能夠在保證較高匹配準(zhǔn)確率的情況下盡可能地提高匹配效率［4，10］。文獻(xiàn)［11］提出一種LeapFrog拓?fù)涞貓D匹配算法，即在匹配過(guò)程中，當(dāng)GPS點(diǎn)附近只有一條候選路鏈時(shí)，跳過(guò)該點(diǎn)與后續(xù)只對(duì)應(yīng)一條候選路鏈的連續(xù)的GPS點(diǎn)。但是，LeapFrog拓?fù)涞貓D匹配算法使用了后續(xù)時(shí)刻的GPS點(diǎn)信息輔助判斷當(dāng)前GPS點(diǎn)匹配路鏈（link），而在實(shí)時(shí)地圖匹配過(guò)程中，后續(xù)時(shí)刻GPS點(diǎn)信息是無(wú)法獲取的，該算法在離線GPS數(shù)據(jù)地圖匹配中表現(xiàn)良好，但在車(chē)輛實(shí)時(shí)監(jiān)管、車(chē)輛導(dǎo)航等需要實(shí)時(shí)地圖匹配的應(yīng)用中難以勝任。

通過(guò)對(duì)上述各類(lèi)地圖匹配算法的分析，各匹配算法在提高準(zhǔn)確率的同時(shí)難以兼顧效率，或?yàn)闈M足效率需求而犧牲部分場(chǎng)景的準(zhǔn)確率?？紤]到實(shí)時(shí)地圖匹配算法對(duì)匹配效率的要求較高，本文下一步將以匹配效率較高的拓?fù)涞貓D匹配算法為基礎(chǔ)，結(jié)合浮動(dòng)車(chē)在城市公路上的行駛特征，構(gòu)建新的地圖匹配算法，兼顧匹配效率的同時(shí)提高算法準(zhǔn)確率，使其滿足交通信息服務(wù)準(zhǔn)確、實(shí)時(shí)、快速發(fā)布的需求。

1.3 實(shí)時(shí)地圖匹配算法構(gòu)建

拓?fù)涞貓D匹配方法（topological map matching）如文獻(xiàn)［5］所述，充分考慮了路段之間的拓?fù)潢P(guān)系，以及車(chē)輛定位位置與道路距離、車(chē)輛與道路方向夾角等參數(shù)對(duì)匹配結(jié)果的影響。與效率較低的高級(jí)地圖匹配算法和準(zhǔn)確率較差的幾何地圖匹配算法相比，拓?fù)涞貓D匹配算法在大部分場(chǎng)景下的計(jì)算準(zhǔn)確率和效率均可達(dá)到較高水平［8］，適合海量浮動(dòng)車(chē)數(shù)據(jù)的實(shí)時(shí)匹配。

1.3.1 拓?fù)涞貓D匹配算法計(jì)算步驟

拓?fù)涞貓D匹配算法核心處理由候選路鏈計(jì)算、拓?fù)潢P(guān)系計(jì)算及路徑推測(cè)三個(gè)步驟組成，具體如下：

a）候選路鏈計(jì)算。在完成對(duì)車(chē)輛歷史軌跡{pi-1，pi-2，…}中各點(diǎn)的匹配之后，對(duì)于當(dāng)前時(shí)刻GPS點(diǎn)pi ，根據(jù)pi的坐標(biāo)以及地圖數(shù)據(jù)中路鏈的位置，計(jì)算出與點(diǎn)pi相距小于GPS點(diǎn)的最大偏移距離（通常為40 m）的所有候選路鏈Li，1，Li，2，…，Li，mi，并根據(jù)車(chē)輛GPS點(diǎn)偏移距離、車(chē)輛方向偏移角度計(jì)算各候選路鏈的距離權(quán)重和方向權(quán)重，其中距離權(quán)重WD（Lij） 和方向權(quán)重WH（Lij）的計(jì)算公式如下：

其中：di-1是前一GPS點(diǎn)與候選路鏈間的距離；di是當(dāng)前GPS點(diǎn)與其候選路鏈間的距離；σ是可調(diào)整的權(quán)重系數(shù)；D是最大定位誤差半徑，本文設(shè)定為40 m。

其中：gi-1是前一GPS點(diǎn)的行進(jìn)方向與候選路鏈方向之間的差值；gi是當(dāng)前GPS點(diǎn)行進(jìn)方向與候選路鏈方向之間的差值；μ是權(quán)重系數(shù)；G是候選路徑最大允許夾角，本文設(shè)為60°。

b）拓?fù)潢P(guān)系計(jì)算。根據(jù)路網(wǎng)拓?fù)浣Y(jié)構(gòu)，計(jì)算點(diǎn)pi-1、pi對(duì)應(yīng)的候選路鏈Li-1，1，Li-1，2，…，Li-1，mi-1和 Li，1，Li，2，…，Li，mi之間所有可達(dá)路徑，作為浮動(dòng)車(chē)，由點(diǎn)pi-1移動(dòng)至pi時(shí)所有可能的路徑；并通過(guò)以下公式計(jì)算pi點(diǎn)對(duì)應(yīng)候選路鏈的總權(quán)重值WS（Li，1），WS（Li，2），…，WS（Li，mi）。

其中：WD（Li，j）和WH（Li，j）分別為L(zhǎng)i，j的距離權(quán)重和方向權(quán)重;WTR（Li-1，k，Li，j）和WLC（Li-1，k，Li，j）為候選路鏈Li-1，k與Li，j的轉(zhuǎn)向權(quán)重和拓?fù)錂?quán)重。當(dāng)兩條候選路鏈之間無(wú)可達(dá)路徑時(shí)，對(duì)應(yīng)WTR與WLC設(shè)為0；當(dāng)存在可達(dá)路徑時(shí)，WLC設(shè)為1，WTR將根據(jù)兩條路鏈的幾何屬性計(jì)算得到［12］。

c）路徑推測(cè)。比較各候選路徑的總權(quán)重，根據(jù)浮動(dòng)車(chē)數(shù)據(jù)與路鏈屬性，推測(cè)出當(dāng)前時(shí)刻浮動(dòng)車(chē)最可能經(jīng)過(guò)的路鏈，并保留點(diǎn)pi的所有權(quán)重值不為0的候選路鏈，用于支持下一時(shí)刻對(duì)車(chē)輛GPS點(diǎn)pi+1的權(quán)重計(jì)算。

1.3.2 實(shí)時(shí)地圖匹配算法構(gòu)建

本文研究的實(shí)時(shí)地圖匹配場(chǎng)景的主要困難在于無(wú)法利用后續(xù)時(shí)刻GPS點(diǎn)的信息來(lái)推測(cè)候選路徑［6］，在道路交叉點(diǎn)附近的GPS點(diǎn)對(duì)應(yīng)的兩條候選路鏈（如圖1、2所示）距離相距較近、方向相似，對(duì)應(yīng)的距離權(quán)重以及航向權(quán)重差別較小，難以分辨浮動(dòng)車(chē)正確的行駛路鏈。但是對(duì)于低速運(yùn)行的軌跡數(shù)據(jù)，由于在相同距離上采樣點(diǎn)的密集度較高，通過(guò)多定位點(diǎn)距離權(quán)重和方向權(quán)重綜合驗(yàn)證，可以很好地進(jìn)行候選路徑的推測(cè)。但是對(duì)中高速軌跡匹配（尤其是采樣點(diǎn)距離超過(guò)10 m），由于采樣點(diǎn)間隔較大，通過(guò)定位點(diǎn)距離權(quán)重和方向權(quán)重得出的候選路鏈有多條，如圖1所示，對(duì)于待匹配點(diǎn)P1的候選路鏈L1和L2，依據(jù)距離權(quán)重和方向權(quán)重，很難得出正確的判斷，P2、P3定位點(diǎn)亦是如此。因此，本文引入速度權(quán)重以輔助分辨交叉路口附近的浮動(dòng)車(chē)的正確行駛線路。

城市道路主輔路、立交橋、環(huán)形路等區(qū)域中分叉拓?fù)浣Y(jié)構(gòu)多為一條主干道分叉為一條主干道與一條連接路，如圖2所示。其中主干道限速較高，連接路限速較低［13］，通往連接路的浮動(dòng)車(chē)在分叉口處選擇減速行駛，引入速度權(quán)重將有助于區(qū)分限速不同的分叉路鏈。

本文引入速度權(quán)重的權(quán)值對(duì)拓?fù)涞貓D匹配算法中的候選路鏈的總權(quán)重值WS進(jìn)行調(diào)整，調(diào)整后的總權(quán)重WVS計(jì)算公式為

2 分布式實(shí)時(shí)地圖匹配算法計(jì)算實(shí)現(xiàn)

2.1 分布式計(jì)算框架選擇

實(shí)時(shí)地圖匹配的數(shù)據(jù)處理有以下幾個(gè)特點(diǎn)：a）能夠記錄數(shù)據(jù)流狀態(tài)，以便下一批次數(shù)據(jù)的處理需要上一次處理后的結(jié)果；b）對(duì)數(shù)據(jù)處理的效率與吞吐量要求較高；c）需要較高的容錯(cuò)性，但是需保證每批數(shù)據(jù)僅被處理一次。

目前常用的流式實(shí)時(shí)分布式計(jì)算框架有Spark Strea-ming［14，15］和Storm［16］，都能夠較好地記錄數(shù)據(jù)流狀態(tài)。Spark Streaming主要對(duì)某段時(shí)間的數(shù)據(jù)進(jìn)行批量處理，具有較高的吞吐量，處理延時(shí)在秒級(jí)左右［17，18］；在容錯(cuò)性方面，Spark Streaming僅在處理級(jí)別上進(jìn)行操作跟蹤，可以保證每個(gè)批量的記錄都被精確地處理一次，更適合處理事務(wù)性較高的場(chǎng)景。因此，相對(duì)于吞吐量較低，容錯(cuò)開(kāi)銷(xiāo)較大的Storm平臺(tái)，Spark Streaming框架更加適合用于并行的實(shí)時(shí)地圖匹配處理。

2.2 地圖匹配算法的并行實(shí)現(xiàn)

本文設(shè)計(jì)了一個(gè)基于Spark Streaming的分布式實(shí)時(shí)地圖匹配計(jì)算流程。在該流程中，首先將地圖劃分為多個(gè)網(wǎng)格，每個(gè)網(wǎng)格在經(jīng)緯度直角坐標(biāo)系中為等長(zhǎng)寬的矩形；然后將不同網(wǎng)格分配至不同的計(jì)算單元，每個(gè)計(jì)算單元只計(jì)算指定網(wǎng)格內(nèi)的浮動(dòng)車(chē)數(shù)據(jù)。這樣，每個(gè)計(jì)算單元只讀取一次對(duì)應(yīng)網(wǎng)格中的路鏈數(shù)據(jù)就可以完成網(wǎng)格內(nèi)所有點(diǎn)候選路鏈的計(jì)算，減少了地圖數(shù)據(jù)加載次數(shù)，在理論上能夠較大地提升匹配效率。另一方面，將候選路鏈計(jì)算的時(shí)間復(fù)雜度O（mn）作為每個(gè)計(jì)算單元計(jì)算時(shí)消耗的估計(jì)量，可以作為每個(gè)節(jié)點(diǎn)分配計(jì)算單元時(shí)負(fù)載均衡優(yōu)化的參考，其中m為網(wǎng)格中路鏈密度，n為網(wǎng)格中浮動(dòng)車(chē)的密度。

在分布式實(shí)時(shí)地圖匹配算法設(shè)計(jì)過(guò)程中，本文基于上述方法進(jìn)行地圖空間劃分，設(shè)計(jì)了一個(gè)基于Spark Streaming的并行地圖匹配計(jì)算流程，如圖4所示。圖中的步驟雖然與串行的實(shí)時(shí)地圖匹配流程較為相似，但是其輸入數(shù)據(jù)方式不同，使得兩者之間的計(jì)算效率產(chǎn)生本質(zhì)的差異。

該計(jì)算流程將實(shí)時(shí)的流式數(shù)據(jù)作為輸入數(shù)據(jù)，基于Spark Streaming框架，按固定時(shí)間間隔（為保證實(shí)時(shí)性，在這里設(shè)置間隔為5 s）將數(shù)據(jù)流劃分為多個(gè)Streaming batch data［19，20］。接下來(lái)的流程中將對(duì)每個(gè)Streaming batch data分三步處理：

a）分片數(shù)據(jù)預(yù)處理。首先計(jì)算出每個(gè)GPS點(diǎn)所屬網(wǎng)格的編號(hào)（GridID），然后篩選并標(biāo)記可跳點(diǎn)車(chē)輛對(duì)應(yīng)的GPS點(diǎn)所匹配的路鏈。

b）候選路鏈計(jì)算。首先以預(yù)處理計(jì)算得到的GridID為key進(jìn)行分組操作；其次獲取對(duì)應(yīng)grid中的路鏈；然后驗(yàn)證跳點(diǎn)標(biāo)記的GPS點(diǎn)是否到達(dá)路鏈終點(diǎn)，取消到達(dá)終點(diǎn)的GPS點(diǎn)的標(biāo)記；最后計(jì)算無(wú)跳點(diǎn)標(biāo)記的GPS點(diǎn)的候選路鏈與權(quán)重。

c）路徑推測(cè)。首先使用updateStateby-Key操作獲取上一時(shí)間分片內(nèi)各車(chē)輛的匹配結(jié)果，然后對(duì)于每一車(chē)輛，計(jì)算前后兩點(diǎn)第一個(gè)候選路鏈之間的拓?fù)潢P(guān)系，連接為候選路徑；最后根據(jù)拓?fù)潢P(guān)系計(jì)算出每個(gè)候選路徑的權(quán)重值，并比較選擇出權(quán)重最大的候選路徑作為匹配結(jié)果；對(duì)于之后一條候選路徑的車(chē)輛，將該候選路徑作為該車(chē)輛的可跳點(diǎn)標(biāo)記。

在該流程中，浮動(dòng)車(chē)歷史定位信息的獲取效率優(yōu)化是依靠Spark的RDD機(jī)制，當(dāng)前時(shí)間段的Streaming batch data相應(yīng)的計(jì)算結(jié)果將存儲(chǔ)至內(nèi)存存儲(chǔ)單元RDD中，以便供下一時(shí)間段Streaming batch data計(jì)算流程中相應(yīng)模塊通過(guò)updateStateByKey算子獲取。另外，Spark的流式數(shù)據(jù)處理框架中，DAG圖機(jī)制以及內(nèi)存計(jì)算等技術(shù)充分利用CPU與內(nèi)存資源，實(shí)現(xiàn)多臺(tái)機(jī)器內(nèi)存共享管理，并將其抽象為一個(gè)整體進(jìn)行讀取、寫(xiě)入、計(jì)算等多種操作，其效率遠(yuǎn)遠(yuǎn)優(yōu)于串行算法中多次對(duì)單車(chē)數(shù)據(jù)的查找、操作、寫(xiě)入流程，實(shí)現(xiàn)了匹配算法在優(yōu)化計(jì)算效率的同時(shí)保障計(jì)算魯棒性的目的，使得計(jì)算性能進(jìn)一步提升。

3 實(shí)驗(yàn)

3.1 實(shí)驗(yàn)環(huán)境和數(shù)據(jù)集

為了更準(zhǔn)確地測(cè)試本文算法的計(jì)算效率和準(zhǔn)確性，采用11個(gè)虛擬機(jī)，每個(gè)虛機(jī)配置包括8核CPU、36 GB內(nèi)存、500 GB存儲(chǔ)，本文的實(shí)驗(yàn)環(huán)境不包括大數(shù)據(jù)平臺(tái)管理服務(wù)和數(shù)據(jù)接口前置服務(wù)器，僅為地圖匹配算法處理部分。本文的實(shí)驗(yàn)數(shù)據(jù)為北京市2018年9～11月份采集的部分公交車(chē)、出租車(chē)運(yùn)行過(guò)程中的軌跡數(shù)據(jù)，數(shù)據(jù)采集頻率為1 s，數(shù)據(jù)量1億條左右。通過(guò)數(shù)據(jù)預(yù)處理，去掉部分無(wú)效數(shù)據(jù)和軌跡點(diǎn)缺失較嚴(yán)重的數(shù)據(jù)，有效數(shù)據(jù)有8千萬(wàn)條以上，數(shù)據(jù)容量40 GB，采集數(shù)據(jù)包含的關(guān)鍵信息如表1、2所示，地圖數(shù)據(jù)為2019年北京市四維地圖。為了更好地驗(yàn)證上述基于Spark Streaming構(gòu)造的分布式實(shí)時(shí)地圖匹配算法的計(jì)算效率，本文依托已有的數(shù)據(jù)進(jìn)行效率測(cè)試，驗(yàn)證不同數(shù)據(jù)規(guī)模下并行匹配效率與單機(jī)串行的計(jì)算效率差異。

為了更精準(zhǔn)地分析本文算法的匹配效果，在本次實(shí)驗(yàn)的數(shù)據(jù)集中，選取54輛采樣頻率為1 s且具有固定行駛路線的公交車(chē)一周的軌跡數(shù)據(jù)，以及采樣頻率為1 s的100輛出租車(chē)一周的行駛軌跡數(shù)據(jù)，用于對(duì)算法準(zhǔn)確率進(jìn)行分析、驗(yàn)證。

3.2 匹配準(zhǔn)確率分析

本文從兩個(gè)角度進(jìn)行匹配算法準(zhǔn)確度的分析：a）從算法匹配總體準(zhǔn)確度角度，本文構(gòu)造匹配算法與經(jīng)典拓?fù)淦ヅ渌惴?、高?jí)匹配算法中的隱馬爾可夫模型進(jìn)行對(duì)比分析；b）按照道路等級(jí)分析本文算法在各道路結(jié)構(gòu)下的適應(yīng)性。

3.2.1 匹配精度計(jì)算方法

本文將測(cè)試城市道路匹配算法準(zhǔn)確率，將使用匹配正確的車(chē)輛定位點(diǎn)數(shù)量與軌跡中總點(diǎn)數(shù)數(shù)量的比值作為匹配的準(zhǔn)確率，用于評(píng)價(jià)地圖匹配算法的效果。本文構(gòu)造的實(shí)時(shí)地圖匹配算法準(zhǔn)確率（accuracy）將使用AN（accuracy by number）度量，這種度量方法被用在文獻(xiàn)［11］的實(shí)驗(yàn)中。

其中：pi=（p1，p2，…，pn）為采集到的軌跡點(diǎn)；p*j=（p*1，p*2，…，p*n）為匹配正確的軌跡點(diǎn)。

3.2.2 匹配算法準(zhǔn)確率對(duì)比分析

首先本文從總體地圖匹配效果方面對(duì)比并分析本文算法與經(jīng)典拓?fù)渌惴?、隱馬爾可夫模型的匹配準(zhǔn)確度。由圖5可見(jiàn)，本文算法的準(zhǔn)確度明顯優(yōu)于經(jīng)典拓?fù)淦ヅ渌惴?，整體匹配精度提高了10%以上，相對(duì)于隱馬爾可夫模型也有明顯的優(yōu)勢(shì)。根據(jù)前文分析，隱馬爾可夫模型計(jì)算復(fù)雜度較高，不適合應(yīng)用于實(shí)時(shí)度較高的處理。

同時(shí)，本文隨機(jī)抽樣24組車(chē)輛軌跡數(shù)據(jù)進(jìn)行驗(yàn)證，為了減少隨機(jī)因素對(duì)結(jié)果的影響，每組數(shù)據(jù)的連續(xù)軌跡均超過(guò)10 km。驗(yàn)證數(shù)據(jù)包括3輛公交車(chē)和3輛出租車(chē)的軌跡數(shù)據(jù)，通過(guò)各算法的處理，為了減少單車(chē)影響，對(duì)每輛車(chē)進(jìn)行準(zhǔn)確率計(jì)算。如表3所示，各算法的準(zhǔn)確率與圖5的準(zhǔn)確度基本一致，再次驗(yàn)證了本文算法可以較好地完成實(shí)時(shí)地圖匹配的處理。

針對(duì)表3中的car_3軌跡數(shù)據(jù)，通過(guò)本文算法處理，并借助MapInfo軟件進(jìn)行展示，得到了匹配效果如圖6所示。在圖6中，綠色線代表成功匹配到的道路，而紅色虛線則表示車(chē)輛實(shí)際行駛道路，但算法未能正確匹配的部分（參見(jiàn)電子版）。除了在圖中圈出的路口由于軌跡點(diǎn)的偏移過(guò)大且數(shù)據(jù)過(guò)于稀疏而導(dǎo)致稍有偏差外，其他部分均能夠正確匹配，準(zhǔn)確率與表3中所述一致，達(dá)到了95%以上。

3.2.3 匹配算法在各道路類(lèi)型上的準(zhǔn)確率分析

接下來(lái)，本文按照北京市幾類(lèi)道路類(lèi)型進(jìn)行匹配，以進(jìn)一步分析本文算法的匹配準(zhǔn)確度，如圖7所示。

本文按照四維地圖道路等級(jí)提取北京市五環(huán)內(nèi)主路、輔路、快速路各10條，每條長(zhǎng)度在2 km以上，以及5座立交橋進(jìn)行準(zhǔn)確度分析。本文算法在各道路類(lèi)型上的平均準(zhǔn)確率均在93%以上，尤其是在快速路和主路上準(zhǔn)確度達(dá)到了98%以上，在立交橋上的準(zhǔn)確度達(dá)到95%，完全滿足智能交通應(yīng)用的要求。

3.3 匹配算法效率分析

本文在Spark Streaming計(jì)算框架與單機(jī)串行計(jì)算效率對(duì)比實(shí)驗(yàn)中，準(zhǔn)備了11臺(tái)相同配置的設(shè)備，并把數(shù)據(jù)隨機(jī)分成11份，實(shí)驗(yàn)結(jié)果如圖8所示。Spark cluster的運(yùn)行效率遠(yuǎn)遠(yuǎn)高于相同數(shù)量的單機(jī)服務(wù)器，數(shù)據(jù)量越大，這種趨勢(shì)愈明顯。基于本文8 000萬(wàn)條數(shù)據(jù)集的測(cè)試可以看出，3 min內(nèi)Spark cluster可以處理完所有數(shù)據(jù)（相當(dāng)于10萬(wàn)數(shù)量級(jí)車(chē)輛實(shí)時(shí)產(chǎn)生的軌跡數(shù)據(jù)），并且隨著數(shù)據(jù)量的增加，Spark cluster處理效率更高，當(dāng)數(shù)據(jù)增長(zhǎng)至8 000萬(wàn)條時(shí)，Spark cluster的處理能力是相同數(shù)量的單機(jī)服務(wù)器的4倍左右。

4 結(jié)束語(yǔ)

隨著智慧交通發(fā)展和車(chē)輛軌跡數(shù)據(jù)的爆發(fā)式增長(zhǎng)，精準(zhǔn)、實(shí)時(shí)、快速的地圖匹配處理成為道路運(yùn)行監(jiān)測(cè)、智慧公路建設(shè)的迫切需求。為解決傳統(tǒng)拓?fù)涞貓D匹配算法在實(shí)時(shí)性和計(jì)算效率方面的問(wèn)題，依托Spark Streaming分布式計(jì)算框架，本文提出一種針對(duì)于海量GPS數(shù)據(jù)的實(shí)時(shí)并行地圖匹配算法，突破離線地圖匹配算法對(duì)歷史軌跡數(shù)據(jù)的依賴(lài)。其主要貢獻(xiàn)如下：首先，通過(guò)引入速度和方向權(quán)重因子，實(shí)現(xiàn)只依靠當(dāng)前位置點(diǎn)和后續(xù)位置點(diǎn)的地圖匹配算法，為分布式實(shí)時(shí)地圖匹配處理提供算法支撐；其次，以浮動(dòng)車(chē)軌跡數(shù)據(jù)流作為實(shí)時(shí)數(shù)據(jù)輸入，依托Spark Streaming分布式計(jì)算框架的RDD數(shù)據(jù)塊和DAG圖機(jī)制以及內(nèi)存計(jì)算策略，充分利用服務(wù)器CPU與內(nèi)存資源實(shí)現(xiàn)實(shí)時(shí)地圖處理；最后，本文通過(guò)實(shí)時(shí)軌跡數(shù)據(jù)進(jìn)行了算法和計(jì)算框架的對(duì)比實(shí)驗(yàn)，可為后續(xù)實(shí)時(shí)地圖匹配算法的改進(jìn)、優(yōu)化提供參考。同時(shí)，本文在測(cè)試范圍上存在一定的局限性，主要以北京營(yíng)運(yùn)車(chē)輛的軌跡數(shù)據(jù)進(jìn)行測(cè)試，未能對(duì)其他城市進(jìn)行對(duì)比分析，后續(xù)研究工作將在算法復(fù)用性上進(jìn)行更為充分的測(cè)試和優(yōu)化。

參考文獻(xiàn)：

［1］Manikandan R， Latha R， Ambethraj C. An analysis of map matching algorithm for recent intelligent transport system［J］.Asian Journal of Applied Sciences， 2017，5（1）：179-183.

［2］Fu Xiao， Zhang Jiaxu， Zhang Yue. An online map matching algorithm based on second-order hidden Markov model［J］. Journal of Advanced Transportation， 2021，2021：1-12.

［3］Hunter T， Abbeel P， Bayen A M. The path inference filter： model-based low-latency map matching of probe vehicle data［M］//Algorithmic Foundations of Robotics X. Berlin： Springer， 2013： 591-607.

［4］盛彩英，席唱白，錢(qián)天陸. 浮動(dòng)車(chē)軌跡點(diǎn)地圖匹配及插值算法［J］. 測(cè)繪科學(xué)， 2019，44（8）：106-112. （Sheng Caiying， Xi Changbai， Qian Tianlu， et al. Study of map-matching and interpolation algorithm of floating car data［J］. Science of Surveying and Mapping， 2019，44（8）：106-112.）

［5］Karamete B K， Adhami L， Glaser E. An adaptive Markov chain algorithm applied over map-matching of vehicle trip GPS data［J］. Geo-spatial Information Science， 2021，24（3）： 484-497.

［6］Luo Linbo， Hou Xiangting， Cai Wentong， et al. Incremental route inference from low-sampling GPS data： an opportunistic approach to online map matching［J］. Information Sciences， 2010，512： 1407-1423.

［7］Jin Zhixion， Kim J， Yeo H ， et al. Transformer-based map matching model with limited ground-truth data using transfer-learning approach［EB/OL］.（2021-10-07）. https：//doinory/10.1016/j.trc.2022.103668.

［8］Zhang Xiaoyao， Li Xuejing. Map-matching approach based on link factor and hidden Markov model［J］. Journal of Intelligent & Fuzzy Systems： Applications in Engineering and Technology， 2021，40（3）： 5455-5471.

［9］Velaga N R， Quddus M A， Bristow A L. Developing an enhanced weight-based topological map-matching algorithm for intelligent transport systems［J］. Transportation Research， Part C： Emerging Technologies， 2009，17（6）： 672-683.

［10］Hsueh Y L， Chen H C， Huang Weijie. A hidden Markov model-based map-matching approach for low-sampling-rate GPS trajectories［C］//Proc of the 7th IEEE International Symposium on Cloud and Service Computing. Piscataway， NJ： IEEE Press， 2017：178235-178245.

［11］Huang Jian， Qie Jinhui， Liu Chunwei， et al. Cloud computing-based map-matching for transportation data center［J］. Electronic Commerce Research & Applications， 2015， 14（6）： 431-443.

［12］He Mujun， Zheng Linjiang， Cao Wei， et al. An enhanced weight-based real-time map matching algorithm for complex urban networks［J］. Physica A： Statistical Mechanics and Its Applications， 2019， 534： 122318.

［13］Pan Yuyan， Guo Jifu， Chen Yanyan， et al. Incorporating traffic flow model into a deep learning method for traffic state estimation： a hybrid stepwise modeling framework［J］. Journal of Advanced Transportation， 2022， 2022（1）： article ID 5926663.

［14］Apache Spark. The Apache software foundation［DB/OL］. https：//spark.apache.org/.

［15］Wang Suzhen， Jia Zhiting， Cao Ning. Research on optimization and application of Spark decision tree algorithm under cloud-edge collaboration［J］. International Journal of Intelligent Systems， 2022，37（11）： 8833-8854.

［16］Muhammad A， Aleem M， Islam M A. TOP-Storm： a topology-based resource-aware scheduler for stream processing engine［J］. Cluster Computing， 2021，24： 417-431.

［17］Ghesmoune M， Lebbah M， Azzag H. Micro-batching growing neural gas for clustering data streams using spark streaming［J］. Procedia Computer Science， 2015，53（1）： 158-166.

［18］Liu Guipeng， Zhu Xiaomin， Wang Ji， et al. SP-Partitioner： a novel partition method to handle intermediate data skew in spark streaming［J］. Future Generation Computer Systems， 2018，86： 1054-1063.

［19］Livaja I， Pripui K， Sovilj S， et al. A distributed geospatial publish/subscribe system on Apache Spark［J］. Future Generation Computer Systems， 2022，132： 282-298.

［20］Hu Fei， Yang Chaowei， Jiang Yongyao， et al. A hierarchical indexing strategy for optimizing Apache Spark with HDFS to efficiently query big geospatial raster data［J］. International Journal of Digital Earth， 2020，13（3）： 410-428.