一種基于Geohash方法和地圖路線規(guī)劃的行程匹配算法

鐘克華，游東寶，蘇炳輝

（廣州汽車集團股份有限公司汽車工程研究院，廣東 廣州 511434)

1 前言

合乘的行程匹配問題是合乘路徑選擇的基礎(chǔ)，在合乘雙方出發(fā)地和目的地明確的情況下，通過枚舉可行的出行規(guī)劃路線，計算并找出這些可行的規(guī)劃路線一定范圍內(nèi)（如路線周圍2 km）的可能行程。如何提高行程匹配效率，是行程匹配研究的難點之一。目前國內(nèi)外對合乘的研究在合乘基本理論，如合乘的發(fā)展?fàn)顩r和趨勢、組織模式等方面比較成熟，在出租客車方面有應(yīng)用方案應(yīng)用于車輛調(diào)度。李新勝［1］提出了一種基于網(wǎng)絡(luò)地圖API的拼車系統(tǒng)路線發(fā)布及匹配算法。康帆［2］提出了一種利用出發(fā)時間和歐氏PickUp距離進行匹配的方法及系統(tǒng)，可以實現(xiàn)時間滿足要求，并選擇短距離的路線。李春風(fēng)［3］先規(guī)劃車主行車路線，然后采用Geohash的方式，獲得該行車路線經(jīng)過的網(wǎng)格的標(biāo)識，再將乘客的起始點的網(wǎng)格標(biāo)識與之進行匹配。該方法可以查找匹配行程，但是其對行程方向的判斷效果不佳。以上幾種方法以能夠進行路線匹配或者以找出最優(yōu)路線為目標(biāo)進行設(shè)計，是在行程所涉及的地域面上查找可能同行的行程路線，存在因需要搜索的面太寬導(dǎo)致效率低下的問題。

為提高行程匹配效率，本文提出了一種行程匹配算法。本算法采用Geohash方法，將二維經(jīng)緯度數(shù)據(jù)表示的地圖點（latitude，longitude）線性化，轉(zhuǎn)換成一維的字符串?dāng)?shù)據(jù)，用于查找和搜索。字符串越長，表示的范圍越精確；字符串相似的表示距離相近。利用字符串的前綴匹配來查詢附近點對應(yīng)的信息，把二維查找轉(zhuǎn)換為一維查找降低了匹配計算的復(fù)雜度。本算法通過采用行程線路匹配帶的方式，縮小查找范圍，進而提高查找速度和匹配效率。在考慮時間、空間、人數(shù)、交通規(guī)定等多因素后，在給定行程路線規(guī)劃的基礎(chǔ)上查找出與該路線匹配的行程，呈現(xiàn)給合乘雙方供其選擇。

2 行程匹配算法

1）輸入 依據(jù)給出的出發(fā)地、目的地用導(dǎo)航的路徑規(guī)劃功能獲取從出發(fā)地到達目的地可行的路線，作為算法輸入。如圖1所示待匹配行程起點、終點，可行規(guī)劃路線和可能的匹配行程起點、終點的關(guān)系。

2）區(qū)域劃分 選取1）中的一條規(guī)劃路線，用Geohash方法采用編碼長度為5精度為2.4 km把線路所經(jīng)過的區(qū)域劃分為線路順路帶并進行編碼，對順路帶區(qū)域劃分方格并做出有序標(biāo)記，區(qū)域劃分如圖2所示。

3）匹配行程點查找 搜索可能匹配行程的出發(fā)地和目的地Geohash字符串，如匹配行程的出發(fā)地與目的地均落在2）中所計算出的順路帶范圍內(nèi)，則行程匹配；反之，行程不匹配。如圖3所示，圖中以C、D、E、F為出發(fā)地和目的地的行程是可匹配的，而以A、B為出發(fā)地或目的地的行程是不匹配的。

4）匹配行程方向篩選 在3）選取的可能匹配行程中，篩選出行程方向與原有行程方向一致的匹配行程。

圖1 可能的匹配行程規(guī)劃路線示意圖

圖2 行程順路帶劃分示意圖

圖3 行程匹配關(guān)系示意圖

行程方向是否一致的判定方法是：按序掃描2）中做過有序標(biāo)記的順路帶區(qū)域，如果行程起點、終點出現(xiàn)的順序與原有行程起點終點出現(xiàn)順序一致，則認(rèn)為匹配行程的方向一致；反之，則認(rèn)為匹配行程方向與原有行程方向相反。

5）匹配度計算 對4）中的匹配行程，按其與原有行程出發(fā)點距離、目的地距離和出發(fā)時間相近程度計算匹配度，并進行排序。

3 算法使用方法

3.1 步驟

1）接收外部輸入的行程參數(shù)，含出發(fā)地、目的地、出發(fā)時間、需要座位數(shù) （乘客行程）、提供座位數(shù) （車主行程）。

2）用導(dǎo)航的路徑規(guī)劃功能獲取從出發(fā)地到達目的地可行的路線。

3）對第2步所獲得的可能路徑，選取一個路線執(zhí)行第4步開始的行程匹配計算；如計算完畢，轉(zhuǎn)第13步。

4）用Geohash算法計算第3步選取的行程路線的順路帶，劃分方格并做標(biāo)記。

5）判斷行程是車主行程還是乘客行程；如是車主行程，轉(zhuǎn)向第6步，如是乘客行程，轉(zhuǎn)向第9步。

6）根據(jù)經(jīng)緯度查找出發(fā)地與目的地均在車主行程路線順路帶范圍內(nèi)乘客行程。

7）判斷第6步找到的乘客行程方向，選出與車主行程方向一致的乘客行程。

8）選出出發(fā)時間、座位數(shù)滿足需求的乘客行程；轉(zhuǎn)向第12步。

9）根據(jù)經(jīng)緯度查找出發(fā)地與目的地均在乘客行程順路帶范圍內(nèi)車主行程。

10）判斷第9步找到的車主行程方向，選出與乘客行程方向一致的車主行程。

11）選出出發(fā)時間、座位數(shù)滿足需求的車主行程。

12）根據(jù)出發(fā)地距離、目的地距離、出發(fā)時間相近程度計算匹配度，依據(jù)匹配度對滿足條件的行程進行排序；轉(zhuǎn)向第3步進入下一個迭代循環(huán)。

13）返回排好序的匹配行程列表給使用者。

3.2 流程圖

算法應(yīng)用流程圖見圖4。

4 應(yīng)用

算法應(yīng)用時，需要處理以下幾個問題。

1）路線規(guī)劃時需要選取：高速優(yōu)先、不走高速、路程最短、時間最少、費用最省等各種模式，以提供各模式下的行程線路。然后，對這些模式下的規(guī)劃路線，作為匹配算法的輸入，迭代計算路線順路帶，查找其匹配行程。

2）Geohash編碼長度：當(dāng)長度為6精度為610 m，當(dāng)長度為7時，精度在76 m。實際使用時編碼長度需要根據(jù)數(shù)據(jù)情況進行選擇，在城市城區(qū)選取編碼長度6，在郊區(qū)可以選取5。

3）在目標(biāo)點選取計算過程中，因Geohash算法的區(qū)域劃分和填充曲線，會產(chǎn)生邊界問題和突變問題。

邊界問題的解決辦法：在查詢時，除了使用定位點的Geohash編碼進行匹配外，還使用周圍8個區(qū)域的Geohash編碼。

突變問題的解決辦法：在查詢附近點的時候，首先篩選Geohash編碼相似的點，然后進行實際距離計算以確定點的選取。

5 總結(jié)

1）建立了利用字符串匹配來查找匹配行程的機制，采用Geohash方法將二維的經(jīng)緯度轉(zhuǎn)換成字符，利用字符串匹配來查找匹配行程。將二維地圖點的匹配問題簡化成一維字符串匹配問題，降低了計算復(fù)雜度。

2）設(shè)計了行程路線順路匹配帶，利用Geohash方法在行程路線一定范圍內(nèi)設(shè)計行程路線順路匹配帶。

3）提出了行程匹配度，用于標(biāo)識行程的匹配程度。匹配度計算綜合考慮了出行時間、出發(fā)地點距離、目標(biāo)地點距離等多種因素。