基于路網(wǎng)層次收縮的快速分布式地圖匹配算法

李瑞遠 朱浩文 王如斌 陳 超 鄭 宇

1(重慶大學(xué)計算機學(xué)院 重慶 400044) 2(京東城市(北京)數(shù)字科技有限公司 北京 100176) 3(北京京東智能城市大數(shù)據(jù)研究院 北京 100176)

Fig. 1 Illustrationof Map-Matching圖1 軌跡地圖匹配示例

作為軌跡數(shù)據(jù)挖掘最基本的操作之一，地圖匹配在許多空間數(shù)據(jù)智能場景中都非常有用.例如，在軌跡壓縮應(yīng)用中，先將GPS點軌跡轉(zhuǎn)化成由路段ID組成的匹配軌跡，然后利用整數(shù)編碼或者最短路徑的方法對軌跡進行壓縮，減少存儲空間.文獻[3]通過比較匹配軌跡和原始GPS點距離評估城市區(qū)域的GPS環(huán)境友好性，即哪些地方的GPS誤差高，哪些位置的GPS誤差低，從而指導(dǎo)部署輔助定位設(shè)備.文獻[4]通過地圖匹配操作實現(xiàn)對移動機器人的定位.文獻[5]通過查詢經(jīng)過某一點的匹配軌跡，找到從該點出發(fā)一段時間內(nèi)能夠抵達的區(qū)域范圍.在軌跡異常檢測中，通過比較匹配軌跡與預(yù)設(shè)路徑的差異判斷車輛是否偏離了給定路線.文獻[8-9]查詢經(jīng)過給定路徑的所有匹配后的軌跡，可以分析每條道路的交通流量，或者更好地為車輛導(dǎo)航.

軌跡地圖匹配非常困難，特別是在并行道路或者高架橋等路網(wǎng)密集的區(qū)域.目前應(yīng)用最廣泛的方法是基于隱馬爾可夫模型(hidden Markov model, HMM)的地圖匹配方法，因為其不僅考慮了路網(wǎng)的連接性，還考慮了GPS點之間的相互關(guān)系，因此具有較高的準確率.然而，基于HMM的地圖匹配算法的運行效率很低，難以滿足實時性很高的場景需求，在大規(guī)模軌跡數(shù)據(jù)的場景下，單臺計算機的資源有限，這個問題顯得尤為突出.例如，在實時可達區(qū)域分析文獻[5]中，需要實時匹配全城范圍內(nèi)的車輛，才能捕捉每條道路的交通情況，最終響應(yīng)用戶實時可達區(qū)域查詢的需求；在?；繁O(jiān)管項目中，需要實時監(jiān)控?；奋囕v是否偏離了既定的路線，因為一旦發(fā)現(xiàn)異常，需要實時地對其進行攔截，防止其駛?cè)刖用駞^(qū)域，造成安全隱患.即使對于離線匹配的場景，也需要盡可能地加快地圖匹配的效率，減少資源的消耗.

有大量的工作用來加速基于HMM的地圖匹配效率.例如，通過構(gòu)建空間索引加速查找每個GPS點的候選路段，但僅采用這種方法對整體提速并不明顯，因為基于HMM的地圖匹配的瓶頸在于大量的最短路徑計算.為此，一部分研究工作簡化了最短路徑計算，包括減少待匹配的GPS點個數(shù)、略過較低概率匹配點之間的最短路徑計算、用近似值替代最短路徑等.然而，簡化計算的方法通常需要一些額外的信息，包括GPS點方向、路網(wǎng)等級等，其通用性受限，還會降低地圖匹配的準確率.因此，另一部分工作直接加速最短路徑的計算，但它們?nèi)杂休^大的提升空間.還有一部分工作利用并行計算或分布式計算技術(shù)，充分利用更多機器資源來提高計算效率，但是它們沒有考慮到路網(wǎng)和軌跡之間的大小差異，按照采樣軌跡對數(shù)據(jù)進行分區(qū)，容易造成數(shù)據(jù)不均衡，或者軌跡切分過細破壞軌跡完整性從而導(dǎo)致匹配準確率降低等問題.

針對已有工作的不足，面向大規(guī)模軌跡數(shù)據(jù)的場景，本文提出了一個基于層次收縮的分布式地圖匹配處理框架(contraction hierarchy-based map-matching, CHMM).首先，在大多數(shù)實際項目中，涉及到的路網(wǎng)數(shù)據(jù)非常小，因此，我們將路網(wǎng)數(shù)據(jù)廣播到整個集群，對軌跡進行隨機分區(qū)，保證了數(shù)據(jù)平衡和軌跡完整性.其次，針對基于HMM的地圖匹配算法效率較低問題，我們提出了使用基于層次收縮的多對多最短路徑查詢算法，在保證匹配準確率不變的情況下，大大加速了圖匹配過程.層次收縮算法最初被用來加速計算兩點之間的最短路徑，其思想是，先對路網(wǎng)進行預(yù)處理，增加一些捷徑，并對每個道路頂點進行編號；然后采用雙向搜索算法，利用編號限制搜索方向，利用捷徑跳過一些節(jié)點的遍歷，從而顯著提升最短路徑的計算效率.本文對基于層次收縮的最短路徑算法加以改造，實現(xiàn)多對多(即多個出發(fā)點，多個目標點)的最短路徑查詢，從而減少重復(fù)計算，提升地圖匹配效率.注意，本文提出的優(yōu)化方案與其他加速方案是正交的，即可以與其他加速方案同時使用.本文的貢獻主要包含4個方面：

1) 提出了一個分布式地圖匹配框架.采用了一種新的分區(qū)策略，即將路網(wǎng)廣播、軌跡分段后再隨機分區(qū)，從而實現(xiàn)負載均衡，保持軌跡完整性.

2) 提出了基于層次收縮的多對多最短路徑搜索算法，從而加速地圖匹配算法的效率;

3) 采用了4個真實的數(shù)據(jù)集進行實驗，實驗結(jié)果表明，本文提出的分布式算法能夠大大提升地圖匹配的效率，同時具有很強的可擴展性；

4) 本文提出的CHMM算法已經(jīng)落回到了產(chǎn)品JUST中，并支持了多個真實的項目落地.我們開源了CHMM算法的核心代碼，并提供了一個在線演示環(huán)境供讀者體驗.

1 先驗知識

本節(jié)先給出一些形式化的定義，然后介紹Apache Spark的必要知識.

1.1 問題定義

定義1.

路網(wǎng)(road network).路網(wǎng)是一個有向圖

G

=(

V

,

E

)，其中，

V

={

v

,

v

,…,

v

}是節(jié)點集合，表示交叉路口；

E

={

e

,

e

,…,

e

}是有向邊集，表示路段集合

.

每條路段

e

∈

E

是一個三元組

e

=(

v

,

v

,

l

)，

v

,

v

∈

V

表示

e

的通行方向為從

v

到

v

，路段長度為

l

，稱

v

和

v

分別是

e

的起始節(jié)點和終止節(jié)點

.

為方便起見，令

e

=(

v

,

v

)，

l

=

len

(

v

,

v

)

.

對于雙向路段，可以用2條有向邊來表示

.

1.2 Apache Spark

Apache Spark(簡稱Spark)是一個基于內(nèi)存的分布式處理框架，它能夠處理大規(guī)模的數(shù)據(jù)，并保證了容錯性.Spark提供了一種數(shù)據(jù)抽象，稱為RDD(resilient distributed dataset)，每個RDD包含多個分區(qū)(partition)，不同的分區(qū)可能分布在集群的不同機器中，每臺機器可以有多個executor，每個executor可以并行處理多個分區(qū)，每個分區(qū)即為一個并行處理單元.RDD可以通過一些并行的操作(例如map,filter,reduce等)進行構(gòu)建和轉(zhuǎn)換.我們應(yīng)當盡可能保證每個RDD分區(qū)內(nèi)的數(shù)據(jù)量差不多，從而實現(xiàn)負載均衡，加快整體的效率.RDD可以緩存在內(nèi)存中，或者持久化在磁盤中，以便重復(fù)使用，減少數(shù)據(jù)計算，這在循環(huán)迭代的場景中非常有用.在Spark中，可以將變量廣播(broadcast)到所有executor中，或者通過zipPartitions操作將2個RDD合并成一個RDD，這樣能夠?qū)崿F(xiàn)2個RDD之間的信息交換.Shuffle操作能夠?qū)?shù)據(jù)在不同的分區(qū)中重新組織和分配，但是shuffle操作代價非常昂貴，因為它會造成不同分區(qū)甚至不同機器之間的數(shù)據(jù)轉(zhuǎn)移，因此我們應(yīng)該盡可能地減少shuffle的次數(shù).

盡管CHMM算法是基于Spark實現(xiàn)的，但是我們可以很方便地將它移植到其他的分布式計算框架中，例如Apache Hadoop或者Apache Flink.

2 基本框架

圖2給出了基于層次收縮的分布式地圖匹配算法CHMM的基本框架，共包含3個部分：軌跡數(shù)據(jù)預(yù)處理、路網(wǎng)數(shù)據(jù)預(yù)處理、軌跡地圖匹配.

1) 軌跡數(shù)據(jù)預(yù)處理.如圖2左上部分所示，我們首先讀取軌跡數(shù)據(jù)，然后對軌跡進行分段，即將一條長的軌跡分段成多條短的子軌跡，一方面能夠更好地組織軌跡數(shù)據(jù)，另一方面也能夠加快后續(xù)地圖匹配的效率(詳見第3.1節(jié)).

2) 路網(wǎng)數(shù)據(jù)預(yù)處理.如圖2左下部分所示，我們首先讀入路網(wǎng)數(shù)據(jù)，然后利用層次收縮算法進行收縮，最終得到收縮后的路網(wǎng)，用來加快后續(xù)地圖匹配過程中的最短路徑計算(詳見第3.2節(jié)).

3) 軌跡地圖匹配.如圖2右半部分所示，這個過程接收層次收縮的路網(wǎng)和分段后的軌跡作為輸入，基于這2個數(shù)據(jù)集，首先對軌跡數(shù)據(jù)進行分區(qū)，使得每個分區(qū)中的數(shù)據(jù)量盡可能相等，從而達到負載均衡.然后在每個分區(qū)里面并行執(zhí)行地圖匹配算法，得到最終的匹配軌跡(詳見第3.3節(jié)).我們還將CHMM算法落回到了JUST中，并提供了一個用戶界面，用戶可以通過該系統(tǒng)觸發(fā)地圖匹配過程，并查看匹配結(jié)果(詳見第4節(jié)).

Fig. 2 Framework of CHMM圖2 CHMM算法的基本框架

3 分布式地圖匹配算法CHMM

在本節(jié)中我們將詳細介紹CHMM的各個步驟，最后對算法性能進行分析.

3.1 軌跡數(shù)據(jù)預(yù)處理

為解決上述問題，本文在地圖匹配之前，先對軌跡進行分段.軌跡分段是指將一條長的軌跡分解成多條短的子軌跡.有多種軌跡分段的方法，例如：根據(jù)出租車的一次載客過程或者共享自行車一次借車過程對軌跡進行分段，根據(jù)快遞員一次送貨過程對軌跡進行分段等.上述的分段方法都需要具體的業(yè)務(wù)知識，并不適用于所有軌跡數(shù)據(jù).因此，本文采用基于駐留點和時間跨度的方法對軌跡進行分段，只利用軌跡的時空信息，適用范圍更廣(任何其他的軌跡分段方法都可用于CHMM算法).具體分成2步：駐留點檢測和軌跡切分.

1) 駐留點檢測

.

駐留點是移動對象在一段時間

t

內(nèi)產(chǎn)生在一個區(qū)域范圍

d

中的GPS點.我們采用文獻[42]的駐留點檢測方法，依次將每個GPS點作為錨點，檢查其后繼節(jié)點是否滿足時間和空間條件

.

如圖3所示，假設(shè)

p

是當前的錨點，其后繼節(jié)點

p

,

p

,

p

到

p

的距離都小于

d

，

p

到

p

的距離大于

d.

接著我們檢查

p

與

p

的時間間隔是否大于

t.

若大于

t

，那么

p

,

p

,

p

,

p

都是駐留點

.

接著，我們以

p

作為錨點重復(fù)前面的過程，直到所有的GPS點都檢查完畢

.

在本文中，我們令

d

=100 m，

t

=100 s.該取值不但能夠排除十字路口等紅綠燈的情況(通常紅綠燈的等待時間在100 s以內(nèi))，也能夠避免GPS的定位誤差而帶來的影響(GPS的定位誤差通常不超過100 m)，還能夠較好地捕捉長時間停留在某處的情形.

Fig. 3 Illustration of trajectory segmentation圖3 軌跡分段示例

2) 軌跡切分.獲得所有的駐留點后，我們以駐留點作為其中一類分割點.另一類分割點考慮相鄰2個GPS點的時間間隔，若間隔大于

t

′，那么這2個GPS點之間也會形成一個分割點，如圖3的

p

,

p

所示

.

軌跡分段利用這些分割點，將長軌跡分割成多段短的子軌跡

.

圖3中將一條長軌跡分成了3段子軌跡

.

注意，

t

′不能設(shè)置得過低，因為如果設(shè)置得過低，將會產(chǎn)生過多的子軌跡，每條子軌跡的起

/

止節(jié)點無法充分利用前

/

后GPS點的信息，影響匹配結(jié)果的準確性

.

在本文中，我們令

t

′=60 min，因為如果2個連續(xù)GPS點超過了這個時間，它們之間的距離通常會相距非常遠，它們相互之間參考價值不大，其間的地圖匹配結(jié)果的正確性也難以保證

.

Fig. 4 Distributed trajectory processing based on Spark圖4 基于Spark的分布式軌跡預(yù)處理

分布式實現(xiàn).利用Spark，可以很容易實現(xiàn)軌跡數(shù)據(jù)預(yù)處理.如圖4所示，我們首先利用textFile操作從外部存儲中讀取軌跡數(shù)據(jù)，形成軌跡RDD.然后調(diào)用Spark的map操作識別出軌跡的駐留點，得到新的軌跡RDD，最后繼續(xù)調(diào)用flatMap操作對軌跡切分(因為一條長軌跡將會切分成多條子軌跡)，得到分段后的子軌跡RDD.注意，整個軌跡預(yù)處理過程不涉及到數(shù)據(jù)的shuffle，利用Spark的并行處理能力，能夠高效地預(yù)處理海量的軌跡數(shù)據(jù).

3.2 路網(wǎng)數(shù)據(jù)預(yù)處理

為了加快基于HMM的地圖匹配算法效率，一種最有效的方式是提升最短路徑的查詢效率.基于層次收縮的最短路徑查詢權(quán)衡了預(yù)處理時間、存儲空間、查詢效率3方面的因素，能夠以較少的預(yù)處理時間、較少的存儲空間、高效地支持兩點之間的最短路徑.為此，在本節(jié)，我們對路網(wǎng)數(shù)據(jù)進行層次收縮，得到收縮后的路網(wǎng)；同時討論當路網(wǎng)非常大時，我們應(yīng)當如何處理.在3.3節(jié)，我們闡述如何利用層次收縮后的路網(wǎng)加速地圖匹配.

3.2.1 路網(wǎng)層次收縮

接下來用一個實際例子來闡述層次收縮過程.給定如圖5(a)所示的路網(wǎng)，圖中每條邊都是雙向邊，邊上的數(shù)字表示路段長度，節(jié)點旁邊的數(shù)字表示該節(jié)點的邊差.例如，節(jié)點

v

的邊差是1-3=-2，因為假設(shè)刪除

v

，我們會刪除

v

的3條相鄰邊(

v

,

v

),(

v

,

v

),(

v

,

v

)，但是為保持所有節(jié)點對的最短路徑長度不變，我們需要增加1條長度為6的捷徑(

v

,

v

)，否則節(jié)點

v

到

v

的最短路徑長度無法得以保留

.

我們隨機選擇最小邊差的一個節(jié)點

v

進行收縮，并對

v

進行層數(shù)編號，得到如圖5(b)所示的路網(wǎng)，虛線表示已經(jīng)刪除的邊和節(jié)點，邊(

v

,

v

)表示增加的捷徑，節(jié)點內(nèi)的數(shù)字表示層數(shù)編號

.

同時，我們更新剩余節(jié)點的邊差

.

接著，我們收縮節(jié)點

v

，得到如圖5(c)所示的路網(wǎng).以上過程不斷迭代重復(fù)，直到所有的節(jié)點都收縮完畢，最后得到如圖5(d)所示的收縮路網(wǎng)

.

Fig. 5 Example of contraction hierarchy圖5 層次收縮的例子

算法1.

路網(wǎng)層次收縮算法

.

輸出：收縮后的路網(wǎng)

G.

① 初始化一個優(yōu)先隊列

q

,并將所有的

v

∈

V

入隊，按照給定的度量標準排序;

level

=1;② while

q

≠null do③

v

←

q.pop

();④

v

的層次編號設(shè)為

level

;

level

++;⑤ for each(

u

,

v

)∈

E

并且

u

尚未編號do⑥ for each(

v

,

w

)∈

E

并且

w

尚未編號do⑦ if

u

→

v

→

w

是

u

到

w

的最短路徑then⑧

l

←

len

(

u

,

v

)+

len

(

v

,

w

);⑨ if(

u

,

w

)已經(jīng)存在

E

中then⑩ 更新(

u

,

w

)的長度為

l

;

3

.

2

.

2 超大路網(wǎng)處理方案一般而言，城市中的路網(wǎng)數(shù)據(jù)更新周期較長，例如按月或者按季度更新，因此，上述路網(wǎng)收縮過程可以周期性執(zhí)行，并將收縮結(jié)果存儲起來，再次使用時直接加載收縮后的路網(wǎng)即可

.

此外，在實際落地項目中，通常是以城市甚至區(qū)域作為交付的基本單元，而一個城市中的路網(wǎng)通常不會很大，例如，作為中國大都市的北京，其路網(wǎng)占用的磁盤大小約為100 MB，任何一臺標準的服務(wù)器均可以進行處理

.

對于無法完全加載到單臺機器內(nèi)的情形，我們可以先對路網(wǎng)切割，例如按照行政區(qū)域進行切割或者采用圖分割算法，將一張大的路網(wǎng)切割成多個小的子路網(wǎng)，然后對每個子路網(wǎng)單獨進行層次收縮，最后對落在每個子路網(wǎng)內(nèi)的軌跡數(shù)據(jù)，依次采用本文提出的分布式地圖匹配算法(見第3

.

3節(jié))

.

Fig. 6 Handling trajectories and road networks at boundaries圖6 處理邊界的軌跡和路網(wǎng)

Fig. 7 Distributed road network preprocessing based on Spark圖7 基于Spark的分布式路網(wǎng)預(yù)處理

3.2.3 分布式實現(xiàn)

圖7展示了利用Spark實現(xiàn)路網(wǎng)預(yù)處理的過程.首先，通過textFile操作從外部文件中讀取路網(wǎng)數(shù)據(jù)，形成路網(wǎng)RDD.注意這里的路網(wǎng)圖是以路段的形式存儲的，在不同的分區(qū)之間以點分割的形式進行分割.接著，我們通過partitionBy操作對路網(wǎng)重新分區(qū).我們實現(xiàn)了一種按照城市范圍的自定義分區(qū)方法，使得落在同一個城市擴張范圍內(nèi)的路段重新分配到同一個分區(qū)中.若路段與多個城市擴張范圍相交，則會分配到多個分區(qū)中.在每個新的分區(qū)中，我們可以得到一個子路網(wǎng)，通過mapPartitions操作實現(xiàn)對子路網(wǎng)的層次收縮，采用mapPartitions的原因是單個分區(qū)內(nèi)的所有路段都會參與整體的收縮運算.最后，同樣通過調(diào)用mapPartitions操作，將每個分區(qū)內(nèi)的層次收縮子路網(wǎng)存儲為單個文件，同時記錄了每個文件的路網(wǎng)空間范圍，方便后續(xù)地圖匹配過程使用.

3.3 軌跡地圖匹配

(1)

Fig. 8 Steps of Map-Matching based on HMM圖8 基于HMM的地圖匹配步驟

(2)

(3)

(4)

確定每個GPS點的候選點后，通過計算相鄰2個候選點的最短路徑，即可獲得最終匹配結(jié)果.

算法2.

基于層次收縮的最短路徑搜索算法

.

輸入：層次收縮路網(wǎng)

G

=(

V

,

E

),起始點

s

，終止點

t

;輸出：從

s

到

t

的最短路徑長度

d

.

① if

s

和

t

在同一條路段上then② return

s

到

t

的路段距離;

③ end if

④ 初始化優(yōu)先隊列

q

和

q

，用來存儲待檢查的節(jié)點，其鍵為對應(yīng)節(jié)點到

s

或

t

的最短路徑距離;⑤ 初始化哈希表

h

和

h

，其鍵為已檢查的節(jié)點，值為對應(yīng)節(jié)點到

s

或

t

的最短路徑距離;⑥ 將

s

的所有出口節(jié)點加入

q

，將

t

的所有入口節(jié)點加入

q

；

d

←∞;⑦ while

q

≠null或者

q

≠null do⑧ if

q

≠null do

/

*正向走一步*

/

⑨ (

d

,

v

)←

q

.pop

();⑩ if

d

>

d

do

/

*正向擴張結(jié)束*

/

/

*表示在中間相遇*

/

v

.level

do

/

*表示在中間相遇*

/

v

.level

do

在第3

.

2節(jié)，我們已經(jīng)對路網(wǎng)進行了層次壓縮

.

給定壓縮后的路網(wǎng)

G

，起始點

s

，終止點

t

，基于層次收縮的最短路徑搜索過程類似于雙向Dijkstra搜索算法

.

如算法2所示，若

s

和

t

(可能不是路網(wǎng)節(jié)點)在同一個路段，則直接計算

s

到

t

的路段距離并返回(行①～③)

.

否則，我們通過3個步驟獲得最終結(jié)果：1) 初始化(行④～⑥)

.

我們借助于2個優(yōu)先隊列來分別控制正向和反向的搜索順序，借助于2個哈希表來分別記錄某個節(jié)點是否已經(jīng)被訪問過以及它們到

s

或

t

的最短距離，并將

s

的出口節(jié)點(即從

s

出發(fā)能夠抵達的第1個道路節(jié)點)和

t

的入口節(jié)點(即能夠抵達

t

的最后一個道路節(jié)點)分別加入到2個優(yōu)先隊列中

.d

表示當前解，初始化為正無窮大

.

例如，要找到圖5(d)中

v

到

v

的最短路徑長度，其過程如表1所示，每一步執(zhí)行完畢后，各變量的取值在相應(yīng)位置給出

.

例如，在第4輪擴張時，正向擴張從優(yōu)先隊列

q

中取出

v

，它到

s

的距離為6，小于

d

，因此不會手動清空

q

.

此外，它尚未被正向擴張訪問過，因此將

v

加入

h

中

.

由于它已被反向擴張訪問過，說明此時已經(jīng)找到了一條經(jīng)由

v

的路徑，更新

d

.

然后檢查

v

的鄰居，發(fā)現(xiàn)不存在層級比

v

大并且未訪問過的節(jié)點

.

此時，2個優(yōu)先隊列均為空，搜索完畢

.

最后得到

v

到

v

的最短距離為7

.

注意，整個過程中，我們都沒有訪問節(jié)點

v

.

相對于雙向Dijkstra算法，基于層次收縮的最短路徑算法主要有2點優(yōu)化：1)利用捷徑，能夠繞過一些中間節(jié)點，從而減少迭代次數(shù)；2)限制了搜索方向，即正向搜索沿著層次增加的方向，反向搜索沿著層次減少的方向.因此，基于層次收縮的最短路徑搜索算法更快.注意，基于層次收縮的最短路徑算法雖然與A算法有相似之處，即通過啟發(fā)式方法控制了搜索方向，但兩者的啟發(fā)式方法不能直接結(jié)合在一起，因為對于層次收縮算法而言，每條邊的層級數(shù)都不一樣，也就無法先按照層級數(shù)擴張，再按照A算法的啟發(fā)函數(shù)來擴張；在路網(wǎng)收縮前，我們也無法事先得知起止點，也就無法利用A的啟發(fā)函數(shù)來對路網(wǎng)進行收縮.

Table 1 Example of Shortest Path Search Based on CH表1 基于層次收縮的最短路徑搜索示例

然而，針對地圖匹配的情形，算法2仍有較大的優(yōu)化空間

.

如圖8(b)所示，假設(shè)GPS點

p

有

m

個候選點，

p

+1有

n

個候選點，在轉(zhuǎn)移圖中，

p

到

p

+1共有

m

×

n

條有向邊，因此需要觸發(fā)

m

×

n

次最短路徑的計算

.

一種最直觀的方式，是調(diào)用

m

×

n

次算法2，每次計算一組候選點對的最短路徑

.

然而，這樣會帶來很多冗余的計算

.

給定如圖9(a)所示的路網(wǎng)，節(jié)點從左往右層級逐漸升高

.

要計算

A

到

D

和

F

的最短路徑，采用一對一的最短路徑計算方法，其搜索過程如圖9(b)所示，路徑中的節(jié)點表示訪問的先后順序.可見，圖9(b)中虛線部分的搜索過程是冗余的.

Fig. 9 Redundant computing for one-to-one shortest path圖9 單對單最短路徑冗余計算

為了盡可能地減少冗余計算，本文提出了基于層次收縮的多對多最短路徑搜索方法

.

其大體思想是，給定一個層次收縮路網(wǎng)

G

=(

V

,

E

)，出發(fā)節(jié)點集合

S

={

s

,

s

,…,

s

}和目標節(jié)點集合

T

={

t

,

t

,…,

t

}，我們依次從每個出發(fā)節(jié)點

s

和目標節(jié)點

t

往外擴張一步

.

其中，對于每個出發(fā)節(jié)點，我們沿著有向邊且層級增加的方向擴張；對于每個目標節(jié)點我們沿著有向邊的反方向且層級增加的方向擴張

.

若某個出發(fā)節(jié)點(或目標節(jié)點)與所有目標節(jié)點(或出發(fā)節(jié)點)確定了最短路徑距離，那么該出發(fā)節(jié)點(目標節(jié)點)便停止擴張

.

算法3.

基于層次收縮的多對多最短路徑搜索算法

.

① 初始化2個優(yōu)先隊列集合

QS

={

q

,

q

,…,

q

}和

QT

={

q

,

q

,…,

q

}，

q

∈

QS

，

q

∈

QT

的排序鍵分別為對應(yīng)節(jié)點到

s

和

t

的最短路徑距離;② 初始化2個哈希表集合

HS

={

h

,

h

,…,

h

}和

HT

={

h

,

h

,…,

h

}，

h

∈

HS

，

h

∈

HT

的鍵為已檢查的節(jié)點，值為該節(jié)點到

s

或

t

的最短路徑;

⑤ 將

s

∈

S

的所有出口節(jié)點加入

q

，將

t

∈

T

的所有入口節(jié)點加入

q

；⑥ while

QS

≠?或者

QT

≠? do⑦ for each

q

∈

QS

do

/

*所有起始點正向走一步*

/

⑧ (

d

,

v

)←

q

.pop

();

/

*

s

正向擴張結(jié)束*

/

⑩ 從QS中移除

q

;

do

v

.level

do

/

*所有終止點反向走一步*

/

/

*

t

反向擴張結(jié)束*

/

do

v

.level

do

圖10展示了利用Spark進行地圖匹配的處理過程.在第3.1節(jié)，我們獲得了分段后的軌跡RDD

.

在第3

.

2節(jié)，我們獲得了多份收縮后的子路網(wǎng)，并存儲在了外部磁盤中

.

在地圖匹配過程中，我們首先計算分段軌跡的空間范圍

range

，然后在Spark的Driver進程中依次讀取與

range

相交的每個子路網(wǎng)文件，匹配完某個子路網(wǎng)內(nèi)的軌跡后，銷毀該路網(wǎng)變量，再讀取下一個路網(wǎng)

.

由于每個子路網(wǎng)不會很大，因此可以在Driver進程的內(nèi)存中存儲起來.對于每個子路網(wǎng)，我們首先向集群中廣播其空間范圍.分段后的軌跡RDD調(diào)用filter方法，過濾掉路網(wǎng)空間范圍外的軌跡數(shù)據(jù).由于經(jīng)歷了軌跡分段和過濾，分區(qū)間的軌跡數(shù)目可能會相差比較大，因此，需調(diào)用repartition方法，一方面調(diào)整分區(qū)的數(shù)目，使得耗時的地圖匹配能夠充分利用集群資源，另一方面能緩解數(shù)據(jù)不平衡的問題.最后通過調(diào)用map方法結(jié)合廣播的子路網(wǎng)對每條軌跡進行地圖匹配.

Fig. 10 Distributed trajectory map matching based on Spark圖10 基于Spark的軌跡地圖匹配

3.4 性能分析

盡管從時間復(fù)雜度上看CHMM算法與相對于傳統(tǒng)基于HMM的地圖匹配算法相同，但是通過以下3個優(yōu)化，大大提升了地圖匹配效率：1)分布式計算充分利用了多臺機器資源；2)通過層次收縮路網(wǎng)限制了最短路徑的搜索方向，跳過了大量中間節(jié)點的訪問；3)多對多最短路徑搜索減少了大量冗余計算.

4 系統(tǒng)展示

本文提出的基于層次收縮的地圖匹配算法已經(jīng)落回了JUST系統(tǒng)中，用戶通過如下的SQL語句，就能夠?qū)崿F(xiàn)快速地圖匹配功能.

SELECT

st_trajMapMatchToCompletePath(

t

1

.traj

,

t

2

.rn

)

(SELECT

st_makeRoadNetwork(collect_list(

r

))AS

rn

圖11展現(xiàn)了JUST系統(tǒng)的用戶界面，用戶在SQL面板中輸入上述地圖匹配SQL語句，就能在地圖面板中查看地圖匹配的結(jié)果，如圖中綠色線所示.本文提出的算法已經(jīng)支持了?；奋囕v行為分析、地圖路網(wǎng)修復(fù)等多個項目的落地.

Fig. 11 UI of JUST for Map-Matching based on CH[38]圖11 JUST實現(xiàn)基于層次收縮的地圖匹配界面[38]

5 實驗及分析

本節(jié)先介紹實驗相關(guān)設(shè)置，然后分析實驗結(jié)果.

5.1 實驗設(shè)置

5.1.1 數(shù)據(jù)集

我們采用4個真實的數(shù)據(jù)集來驗證本文提出的地圖匹配方法的性能.

1) 西安軌跡數(shù)據(jù)集.采用滴滴蓋亞數(shù)據(jù)開放計劃提供的軌跡數(shù)據(jù)，原始數(shù)據(jù)共包含中國西安市從2018-10-01—2018-11-30這2個月的出租車軌跡數(shù)據(jù)，其空間范圍為經(jīng)緯度坐標(108.92,34.20)到(109.01,34.28)，包含了2 846 251 982條GPS點，未分段的軌跡有3 960 100條，磁盤占用為217 GB，相鄰2個GPS點的采樣時間間隔約為3 s.分段后平均每條軌跡包含42個GPS點.我們隨機采樣一些GPS點，數(shù)據(jù)分布如圖12(a)所示，由圖12可知，軌跡在空間上分布非常不均勻.

2) 西安路網(wǎng)數(shù)據(jù).從OSM(open street map)網(wǎng)站中下載了西安軌跡空間范圍向外擴了5 km的路網(wǎng)數(shù)據(jù)，這樣確保邊界處的軌跡匹配結(jié)果正確.截取的路網(wǎng)共包含了71 906條邊，33 370個頂點，磁盤占用8.47 MB.

3) 北京軌跡數(shù)據(jù)集.T-Drive數(shù)據(jù)集包含中國北京市從2008-02-02—2008-02-08一周內(nèi)10 366輛出租車的軌跡數(shù)據(jù)，原始數(shù)據(jù)共有17 662 984個GPS點，平均采樣時間間隔為177 s，磁盤占用為752 MB，去除明顯噪聲(坐標為(0,0)的GPS點)后，其空間范圍為經(jīng)緯度坐標(116.24,39.83)到(116.48,40.02)，分段后的軌跡數(shù)目為314 086條.圖12(b)展示了T-Drive采樣數(shù)據(jù)的分布.

4) 北京路網(wǎng)數(shù)據(jù).從OSM中下載北京軌跡數(shù)據(jù)集對應(yīng)空間向外擴張5 km范圍內(nèi)的路網(wǎng)數(shù)據(jù)，共有43 856條邊，19 665個頂點，磁盤占用3.89 MB.

前2個數(shù)據(jù)集統(tǒng)稱為西安數(shù)據(jù)集，后2個數(shù)據(jù)集統(tǒng)稱為北京數(shù)據(jù)集.默認情況下，我們采用西安數(shù)據(jù)集，因為其軌跡數(shù)據(jù)量更大、采樣時間間隔更小、數(shù)據(jù)質(zhì)量更好.

Fig. 12 Data distribution圖12 數(shù)據(jù)分布

5.1.2 衡量標準

本文在保證與基于HMM的地圖匹配算法準確率不變的情況下，主要聚焦在地圖匹配效率的提升上.因此，我們主要比較不同方法的預(yù)處理時間、地圖匹配的時間.

5.1.3 對比方法

我們比較以下方法的地圖匹配效率.注意對于不同方法，使用的都是分段后的軌跡.所有對比方法的代碼均隨著我們的方法一起開源.

1) CHMM.本文提出的方法，即采用廣播路網(wǎng)的方式、軌跡隨機分區(qū)的方法、多對多的層次壓縮最短路徑算法來加速地圖匹配過程.

2) FMM.FMM方法首先計算每條路段到一段范圍內(nèi)所有其他路段的最短路徑，然后通過查表的方式來計算最短路徑，從而加快地圖匹配的效率.我們實現(xiàn)了其分布式版本.在預(yù)計算過程中，采用單源Dijkstra算法計算

δ

范圍內(nèi)的最短路徑并存儲在一個二維哈希表中.在地圖匹配階段，若在二維哈希表中存在2條路段的最短距離，則直接返回，若不存在，則使用Dijkstra算法計算最短距離.

3) PartitionSpace.文獻[44]首先對軌跡數(shù)據(jù)進行采樣，在Spark Driver中采用四叉樹的方式對空間進行劃分，使得每個子空間的軌跡樣本數(shù)目相近.接著對全量軌跡數(shù)據(jù)集按照此空間進行劃分，使得每個分區(qū)內(nèi)的軌跡數(shù)目盡可能相同.它還考慮了邊界路網(wǎng)的問題，對于每個分區(qū)，往外擴張500 m路網(wǎng).文獻[15]采用的是一對一Dijkstra計算最短路徑，但為了公平起見，我們在每個分區(qū)內(nèi)采用了CHMM算法，即這個方法與我們的方法不同之處在于數(shù)據(jù)分區(qū)方式的不同.

4) Dijkstra.采用傳統(tǒng)的采用單向Dijkstra算法計算最短路徑距離，例如文獻[13,51].

5) Bi-Dijkstra.文獻[23]采用雙向單對單Dijkstra算法計算最短路徑距離，用來加速地圖匹配.

6)

m

-

n

-Dijkstra.文獻[24-25]采用雙向多對多Dijkstra算法計算最短路徑距離，用來加速地圖匹配.

7) A.文獻[39]采用A算法計算最短路徑距離.

8) CH.采用單對單CH算法計算最短路徑距離.

注意，實驗結(jié)果中未展示雙向A算法，因為文獻[52]指出，雙向A算法在雙向搜索相遇時，得到的只是近似結(jié)果.為得到準確結(jié)果，仍會繼續(xù)搜索很長的時間，導(dǎo)致算法極慢.實際上，我們也實現(xiàn)并開源了雙向A搜索算法，終止條件為：任何一個雙向搜索開放隊列為空，或者可能的最短路徑大于當前已經(jīng)找到的最優(yōu)值.在我們的實驗環(huán)境中，即使匹配一條只有14個GPS點、采樣間隔為24 s的軌跡，雙向A算法花費的時間也超過了130 min.我們不比較多對多A算法以及雙向多對多A算法，因為A算法的啟發(fā)式函數(shù)是針對單個起止點的，當涉及到多個起止點時，難以設(shè)計啟發(fā)式函數(shù)，這將是一個有趣的研究點.

5.1.4 參數(shù)設(shè)置

表2顯示了實驗過程中的各參數(shù)變量取值，其中若無特殊說明，默認的參數(shù)用粗體表示.我們通過查看機器數(shù)目和軌跡集大小的變化驗證我們方法的

Table 2 Parameter Settings表2 參數(shù)設(shè)置

高可擴展性；通過不同采樣率和GPS點個數(shù)的軌跡驗證我們方法的廣泛適用性.對于所有方法，在尋找候選點時，我們先對路網(wǎng)構(gòu)建R-tree索引.

5.1.5 實驗環(huán)境

集群由5臺物理機器組成，每臺機器有24個物理CPU核、128 GB內(nèi)存，操作系統(tǒng)為CentOS 7.4.我們部署了Hadoop 2.7.3和Spark 2.3.3，編程語言使用Java和Scala，JDK的版本為1.8.在實驗過程中，我們分配了5核和5 GB內(nèi)存給了Spark Driver進程，為每個機器啟動了30個executor，每個executor分配了5核和16 GB內(nèi)存.

5.2 實驗結(jié)果

Fig. 13 Preprocessing performance of FMM (Xi’an)圖13 FMM預(yù)處理性能 (西安)

5.2.1 路網(wǎng)數(shù)據(jù)預(yù)處理性能對比

我們首先比較不同方法的路網(wǎng)數(shù)據(jù)預(yù)處理性能.注意我們沒有比較軌跡的預(yù)處理性能，因為所有方法都是基于分段后的軌跡進行地圖匹配的，他們的軌跡預(yù)處理過程相同.在這些方法中，只有CHMM,CH和FMM需要進行路網(wǎng)數(shù)據(jù)預(yù)處理，而CHMM和CH方法都是對路網(wǎng)進行同樣的層次壓縮，因此我們只比較CHMM與FMM的路網(wǎng)預(yù)處理性能.路網(wǎng)數(shù)據(jù)預(yù)處理都是在Spark Driver程序中進行的.圖13展示了FMM算法對西安路網(wǎng)數(shù)據(jù)的每一條路段，采用Dijkstra算法預(yù)計算其到

δ

空間范圍內(nèi)所有路段間的最短路徑所需的時間和結(jié)果占用空間.由圖13可知，F(xiàn)MM算法的預(yù)處理時間和預(yù)處理結(jié)果大小都隨著

δ

增大呈指數(shù)增長，當

δ

=3 km時，預(yù)處理結(jié)果大小達到了1.67 GB，當加載到內(nèi)存時，占用空間會更大，不適合分布式場景下廣播.而CHMM的路網(wǎng)預(yù)處理時間，需要的時間僅為13 s，壓縮后序列化的路網(wǎng)大小僅為19 MB，因此適合廣播.綜上，CHMM方法僅需要少量的預(yù)處理開銷，非常適合分布式的場景.

5.2.2 地圖匹配性能隨采樣間隔變化

由于地圖匹配非常耗時，在這一組實驗中，我們選取了西安數(shù)據(jù)集預(yù)處理后前10 000條軌跡進行分布式匹配，用來比較不同方法的匹配時間隨著采樣時間間隔的變化.原始軌跡的采樣時間間隔為3 s一個點，9 s表示每3個點保留一個GPS點，以此類推.

表3展示了實驗結(jié)果，其中括號中的數(shù)字表示對應(yīng)采樣時間間隔下軌跡的平均GPS點個數(shù).從表3中我們可以得出以下7個結(jié)論：

1) 隨著采樣時間間隔從3 s增加到60 s，幾乎所有方法的地圖匹配時間先減少，然后緩慢增加.因為采樣時間間隔越大，一條軌跡中包含的GPS點越少，需要計算的最短路徑點對的數(shù)目越少，因此地圖匹配時間越少.但是隨著采樣間隔越大，2個相鄰的GPS點距離也就越大，計算最短路徑的時間也越長，導(dǎo)致采樣時間間隔從24 s增加到60 s時，地圖匹配時間有所增加.

2) 對于FMM算法，隨著

δ

的增加，從緩存中能夠查到的最短路徑記錄命中率也就越大，因此，

δ

=1 000 m時的地圖匹配效率比

δ

=500 m時更快.但是在我們的實驗環(huán)境中，當

δ

=2 000 m時，路網(wǎng)預(yù)計算結(jié)果在內(nèi)存中的空間大于2 GB，Spark無法廣播大于2 GB的變量，因此我們未比較

δ

≥2 000 m的情形.3) 當采樣間隔較低時，F(xiàn)MM算法比Dijkstra更快，因為我們可以在預(yù)計算結(jié)果中，直接查詢到某些最短路徑，從而避免耗時的Dijkstra計算.例如，當

δ

=1 000 m、采樣時間間隔為3 s時，命中率約為60%，避免了大部分的計算開銷.隨著采樣時間間隔增加，F(xiàn)MM的用時與Dijkstra的差距越小，因為命中率會變小.4) Bi-Dijkstra算法、

m

-

n

-Dijkstra算法、A算法、CH算法、CHMM算法都比原始的Dijkstra更快，而本文提出的CHMM最快，因為通過壓縮路網(wǎng)，CHMM算法能夠限定搜索的方向，通過捷徑能夠跳過一些中間節(jié)點，而且通過多對多搜索，減少了重復(fù)計算.

5) Bi-Dijkstra算法比A算法快，甚至是Dijkstra算法性能的20倍左右，因為Bi-Dijkstra算法減少了許多無效的路網(wǎng)擴張；此外，在實現(xiàn)中，我們采用了文獻[53]的方法，一旦雙向擴張相遇后，只擴張隊列內(nèi)的路段，進一步限定了搜索范圍.

6)

m

-

n

-Dijkstra與CHMM類似，共享了部分中間結(jié)果，減少了大量的重復(fù)計算過程，這非常適合基于HMM的地圖匹配算法，因此A算法不如

m

-

n

-Dijkstra算法.

7) PartitionSpace方法內(nèi)部也采用了CHMM算法，但是采用四叉樹根據(jù)軌跡分布對軌跡進行分區(qū)(在我們的實驗中，最大分區(qū)數(shù)目為150，因為集群的總核數(shù)為150).由于軌跡的空間分區(qū)非常不均衡，通過采樣對空間進行分區(qū)，仍會造成分區(qū)不均衡的問題，而本文提出的CHMM能夠保證分區(qū)均衡，因此比PartitionSpace方法更快.

Table 3 Map-Matching Time VS Sampling Interval on Xi’an Datasets

5.2.3 地圖匹配性能隨GPS點個數(shù)變化

在這組實驗中，我們展示了采用北京數(shù)據(jù)集的實驗結(jié)果.西安數(shù)據(jù)集的實驗結(jié)果類似，因此結(jié)果未展出.我們選取了北京數(shù)據(jù)集中GPS點個數(shù)大于30的10 000條軌跡，每條軌跡的采樣時間間隔大約是24 s.對于每條軌跡，分別截取前5,10,15,20,25,30個GPS點，形成新的軌跡，用來驗證不同方法隨著GPS點個數(shù)增加的耗時變化情況.

由表4可知，隨著GPS個數(shù)的增加，所有方法所需要的耗時都增加，因為我們需要匹配更多的點，計算更多的最短路徑.所有方法中，CHMM算法效率最高.

m

-

n

-Dijkstra算法表現(xiàn)也很不錯，因為它共享了部分中間結(jié)果，減少了重復(fù)計算.在不需要多次執(zhí)行地圖匹配算法或者路網(wǎng)更新較頻繁的場景，可以使用

m

-

n

-Dijkstra算法，因為它無需對路網(wǎng)數(shù)據(jù)預(yù)處理.有趣的是，F(xiàn)MM(500 m)比FMM(1 000 m)效率更快，這與常識以及表3的結(jié)果相反.經(jīng)分析，本組實驗中FMM算法的耗時都不高，因此其廣播變量的時間不可以忽略.當

δ

=500 m時，預(yù)計算的最短路徑結(jié)果的磁盤占用為14 MB；而當

δ

=1 000 m時，預(yù)計算的最短路徑結(jié)果的磁盤占用為48 MB，所需的廣播耗時更大.

Table 4 Map-Matching Time VS Number of GPS Points on Beijing Datasets

結(jié)合表3和表4來看，匹配北京數(shù)據(jù)集所需的時間比匹配西安數(shù)據(jù)集所需的時間小很多，因為北京數(shù)據(jù)集的路網(wǎng)更稀疏，每個GPS點的候選點更少，需要計算的最短路徑更少.

各步驟的耗時占比.表5和表6分別統(tǒng)計了各個算法在地圖匹配過程中，每個步驟的時間占比以及耗時情況.這里選用了西安數(shù)據(jù)集預(yù)處理后GPS點個數(shù)在30～50的1 731條軌跡，軌跡采樣時間間隔為24 s.由于本組實驗主要查看各部分耗時占比，我們采用單機版單線程環(huán)境運行了實驗，各步驟的耗時是匹配這1 731條軌跡的時間之和.注意，PartitionSpace算法與CHMM算法只是分布式分區(qū)方法不同，在單機版單線程環(huán)境中，與CHMM算法一致，因此其結(jié)果未列出.所有的方法中，構(gòu)建候選圖的耗時最大，因為里面涉及到耗時的最短路徑查詢操作；確定匹配路徑耗時最少(接近于0%)，這得益于Viterbi算法的使用.例如，對于傳統(tǒng)的Dijkstra算法，其構(gòu)建候選圖的耗時高達99.19%，即使作了一些優(yōu)化，最佳對比方法(即

m

-

n

-Dijkstra)構(gòu)建候選圖的耗時也需要占用92.65%.而CHMM是所有方法中構(gòu)建候選圖耗時唯一少于90%的方法，但也占用89.87%.將表3和表5結(jié)合起來看，構(gòu)建候選圖占比越小的方法整體運行得更快.因此，加快最短路徑的計算對于基于HMM的地圖匹配至關(guān)重要.另一個需要說明的現(xiàn)象是，表3與表6中各算法的性能之比是不同的，因為它們所使用的數(shù)據(jù)集不一樣，而且執(zhí)行環(huán)境不同，但他們之間的相對性能是一致的.

Table 5 Time Ratio of Different Steps in Map-Matching on Xi’an Datasets表5 西安數(shù)據(jù)集地圖匹配各步驟時間占比 %

Table 6 Time Cost of Different Steps in Map-Matching on Xi’an Datasets表6 西安數(shù)據(jù)集地圖匹配各步驟時間 s

5.2.4 擴展性比較

為了驗證CHMM方法的擴展性，我們做了2組實驗.在第1組實驗中，我們對西安數(shù)據(jù)集中100萬條軌跡進行地圖匹配，分析在不同集群節(jié)點數(shù)目情況下，所需要的匹配時間.我們從表3中選取了較快的4個算法CHMM,CH,

m

-

n

-Dijkstra,PartitionSpace進行對比，因為其他的算法效率太低，匹配100萬條軌跡數(shù)據(jù)，即使使用5臺節(jié)點的集群，運行一整晚均未出結(jié)果.由圖14(a)可知，隨著節(jié)點數(shù)目的增加，所有的方法所需的時間逐漸減少，然后趨于平穩(wěn).因為節(jié)點數(shù)目越多，計算資源越多，因此會更快，但當節(jié)點更多時，瓶頸將會由計算開銷轉(zhuǎn)化成通信開銷，因此會趨于平穩(wěn).CHMM算法的運算效率比其他的方法更高，而且可以更快地穩(wěn)定下來.

Fig. 14 Scalability of different methods (Xi’an)圖14 不同方法的擴展能力(西安)

圖14(b)展示的是不同方法的執(zhí)行時間隨著數(shù)據(jù)集大小的變化情況.其中，100%的數(shù)據(jù)表示西安數(shù)據(jù)集中約為500萬條軌跡.由圖14可知，隨著數(shù)據(jù)集的增大，所有方法所需的時間開銷呈線性增長，但CHMM方法所需的時間少得多，而且增長率更低，CHMM優(yōu)勢更明顯.整體而言，CHMM算法所需的時間是PartitionSpace算法的1/3.因此，CHMM的可擴展性更強，效率更高.

6 相關(guān)工作

對軌跡地圖匹配問題的研究由來已久，其中基于HMM的軌跡地圖匹配應(yīng)用最為廣泛，因為其具有較高的準確率，能夠處理噪聲和低采樣率軌跡的情形.但它也面臨著效率較低的問題，因此，有大量加速軌跡地圖匹配的研究工作.這些工作大體可分成4類：構(gòu)建索引、簡化計算、加速最短路徑計算、并行計算或者分布式計算.

1) 構(gòu)建索引.基于HMM的軌跡地圖匹配的第一步是尋找每個GPS點周圍一定范圍內(nèi)的路段，用于確定候選點.大多數(shù)地圖匹配工作都對路網(wǎng)構(gòu)建空間索引，以加快對周圍路段的查詢.許多空間索引可供選擇，例如：R-trees,Quad-trees,

k

-

d

trees、網(wǎng)格索引或者它們的變種.盡管構(gòu)建空間索引能夠一定程度上加快地圖匹配效率，然而，候選點的確定并不是基于HMM的軌跡地圖匹配的最大瓶頸，僅僅通過空間索引對全局軌跡地圖匹配的提速是非常有限的.2) 簡化計算.研究發(fā)現(xiàn)，基于HMM的軌跡地圖匹配的瓶頸在于確定匹配路徑，其效率跟軌跡點的個數(shù)、路網(wǎng)的稠密度、最短路徑的計算有關(guān).為提升地圖匹配的效率，直觀方法是減少匹配GPS點的個數(shù)、減少候選路段的條數(shù)、簡化最短路徑的計算.①減少匹配GPS點的個數(shù).當軌跡采樣率非常高時，可以通過對軌跡進行降采樣或者軌跡化簡的方式，減少待匹配的GPS點從而加快地圖匹配.文獻[19]設(shè)計了一種考慮空間信息(例如路段長度和回轉(zhuǎn)方向)的加權(quán)函數(shù)用來進行軌跡化簡，并提出了3種軌跡化簡方法來減少軌跡中的GPS點的個數(shù).文獻[20]首先考慮GPS點的移動方向?qū)壽E進行聚類，然后將同一個聚類內(nèi)的GPS點匹配到同一條路段中，因為聚類的個數(shù)比GPS點的個數(shù)少很多，因此能夠顯著提升匹配效率，同時這種方法還能夠緩解噪聲點帶來的影響.實時地圖匹配通常只考慮最近一段時間的GPS點數(shù)據(jù)，因此通常比離線地圖匹配更快.②減少候選路段的條數(shù).ST-Matching算法只保留當前為止得分最多的

l

個候選點.SD-Matching算法首先對每個候選點計算一個綜合概率，它同時考慮了空間概率和角度概率的.然后只選擇

k

個綜合概率最大的點作為最終候選點，從而加快地圖匹配效率.③簡化最短路徑的計算.SD-Matching算法通過運動方向找到一個搜索區(qū)域，然后只考慮在搜索區(qū)域內(nèi)的路徑，大大簡化了最短路徑的計算.文獻[17]針對手機基站數(shù)據(jù)，改造了HMM算法，提出了一個快速實時的維特比解碼器，具有線性的空間復(fù)雜度和時間復(fù)雜度，其大體思路是消除了乘以0的路徑組合.針對高頻軌跡，文獻[21]直接用GPS點的歐氏距離替代路網(wǎng)距離.簡化計算的方法通常需要額外的信息，例如GPS點的方向，其通用性受限.此外，這類方法在一定程度上會降低匹配精度.

3) 加速最短路徑計算.與簡化計算不同，這類方法能保持匹配結(jié)果與原生HMM類的地圖匹配算法一致.針對Dijkstra算法計算2個候選點的最短路徑非常耗時的問題，文獻[39]采用A算法或ALT算法加速最短路徑的計算.文獻[23]采用雙向Dijkstra算法來加速，而文獻[24-25]采用多對多Dijkstra算法進行加速.前面這些提速方法需要在原始的路網(wǎng)上進行搜索，其加速效果仍然有較大提升的空間.文獻[22]預(yù)計算并緩存了一定空間范圍內(nèi)任何一對路段之間的最短距離，當進行匹配時，通過查表的方式求得2個候選點之間的最短距離.這種方法非常消耗內(nèi)存，在路網(wǎng)稠密的地方，常常容易內(nèi)存溢出.

4) 并行計算或者分布式.另外一種方式通過使用更多的CPU來加速地圖匹配過程.文獻[51]采用多線程的方式并行化構(gòu)建路網(wǎng)索引，同時并行化地圖匹配過程，大大提升了匹配效率.文獻[27]使用Hadoop實現(xiàn)大規(guī)模GPS軌跡的分布式地圖匹配.針對Hadoop執(zhí)行效率較低的問題，涌現(xiàn)了很多基于Spark的分布式地圖匹配工作.例如，文獻[21]根據(jù)軌跡點采用了Quad-tree進行分區(qū)，同時，對于分區(qū)邊界的路網(wǎng)，進行擴張和拷貝，從而提升邊界點的匹配準確率.它還提出了一種分批處理的方法，防止數(shù)據(jù)過大時內(nèi)存開銷太大.但是根據(jù)軌跡進行分區(qū)的方法，在空間范圍不大并且軌跡數(shù)目較多時，可能會面臨著路網(wǎng)拷貝過多、單個分區(qū)內(nèi)軌跡數(shù)目較多的問題，當劃分空間非常小，軌跡也會被切分成很小，極端情況下，一個分區(qū)內(nèi)的軌跡點數(shù)目只有1～2個，嚴重影響了地圖匹配準確率.因此它的擴展性受限，效率不高，準確率可能會受影響.

本文提出的CHMM方法利用了空間索引加速候選點的查找，基于層次收縮的路網(wǎng)采用多對多的方式加速最短路徑計算，同時提出了一個分布式處理框架，在保持高匹配率的同時，具有更高的效率和更強的可擴展性.

7 總結(jié)與展望

本文提出了一個基于層次收縮的分布式地圖匹配算法框架，能夠?qū)崿F(xiàn)海量軌跡數(shù)據(jù)的快速匹配.具體來說，提出了一個簡單但非常有效的數(shù)據(jù)分區(qū)策略，能夠保證分布式環(huán)境下任務(wù)的負載均衡；提出了利用層次收縮的方法加速地圖匹配效率，并在此基礎(chǔ)上提出了基于層次收縮的多對多最短路徑查詢算法.實驗結(jié)果表明我們提出的方法具有較高的效率和可擴展性.例如，在我們的實驗環(huán)境中，對于500萬條軌跡進行地圖匹配，CHMM算法的耗時僅為PartitionSpace算法的1/3.所提的方法已經(jīng)支持了多個真實空間數(shù)據(jù)智能項目的落地.我們還提供了一個在線演示系統(tǒng)，開源了核心代碼，期待能夠推動相關(guān)技術(shù)在更多的空間數(shù)據(jù)智能場景中落地.未來工作中，我們期待增加更多過濾條件在層次路網(wǎng)搜索中，同時考慮將本文提出的方法與其他優(yōu)化方法例如文獻[57]相結(jié)合，更進一步地提升地圖匹配效率.

作者貢獻聲明

：李瑞遠負責想法的提出、文章的撰寫以及rebuttal等事宜；朱浩文、王如斌負責執(zhí)行實驗、將算法落回產(chǎn)品；陳超負責論文算法討論和整體質(zhì)量把控；鄭宇給我們提供了工作、實驗環(huán)境，提出問題及大體方向，確定論文框架.