Geohash編碼在出租車巡游路線推薦中的應用*

欒方軍 張鵬旭 曹科研

（沈陽建筑大學信息與控制工程學院 沈陽 110168）

1 引言

城市道路擁堵目前已經成為城市道路交通問題中最突出的問題。交通擁堵一方面影響著人民群眾的身心健康，另一方面造成了更大的城市交通壓力。如何提高傳統交通工具的運行效率成為了新的研究內容。由于出租車在城市居民的日常生活中發揮著重要作用，與其他公共交通工具如公交車或地鐵相比，出租車的運行路線具有隨機性和不確定性，通常不會遵循固定的路線尋找乘客。多數出租車司機在街道上漫無目的地尋找乘客，這種無目的尋找不僅浪費了出租車司機的油耗和時間，而且增加了城市出租車的空載率，降低了公共交通運行效率的同時，進一步加劇了城市交通壓力。為了加快智慧城市的發展，對空閑出租車司機推薦一個巡游路線顯得尤為重要。

基于這一研究思路，本文設計了一種新穎的出租車巡游路線推薦模型。圖1概述了本文推薦模型的整體流程：利用8位Geohash編碼覆蓋所在城市的路網，并將其寫入Neo4J圖數據庫中，GRU神經網絡根據出租車歷史數據預測出每個8位Geohash網格內每小時的乘客數量，并把該數據更新到Neo4j中對應的路段中。當該路段所有Geohash區域更新完后，得到的累加數量即是該路段預測后的總乘客數量。結合出租車當前所處的時間段及其GPS信息，每當出租車行駛到一個路段的終點之前，經過推薦系統計算出以該路段終點為起點的單位距離乘客數量更多的路段推薦給出租車司機，直至出租車接到乘客，結束推薦。

圖1 推薦模型的整體流程

2 相關工作

2.1 出租車尋客推薦

現今技術主要采用熱區域推薦和熱路線推薦，來實現出租車巡游接客效率的提高。

熱區域推薦［1～5］是指推薦一個包含很多乘客的區域，基于乘客需求量并結合司機當前位置構建，對其進行推薦可以一定程度上提高搭載成功率。存在的問題是只有目的地具有較高的接客概率，但出租車司機到達該目的地的路線是隨機的，并沒有對司機到達熱區域范圍的路線進行進一步優化，在行駛在該路線過程中很可能錯失路邊訂單。

熱路線推薦［6～10］：相對于熱區域推薦，熱路線推薦更加完整。如Lai［6］提出了城市交通庫侖定律的概念，對城市出租車和乘客之間的關系進行建模，并提出了一種路線推薦方案。出租車和乘客被視為正電荷和負電荷。Meng［7］設計了一個凈利潤目標函數，以評估行駛路線的潛在利潤，為出租車司機開發了具有成本效益的推薦系統。本文屬于熱路線推薦的范疇。

2.2 神經網絡

長短期記憶（LSTM）網絡［11］是RNN的變體，是為了解決梯度消失和梯度爆炸而產生的。LSTM和普通RNN相比多出了三個控制器（輸入控制，輸出控制，忘記控制）。GRU是Cho［12］等于2014年提出的一種優化了LSTM結構的變體。GRU神經網絡不引入額外的記憶單元，將LSTM的輸入控制和忘記控制合并為了一個更新門，具有更加精簡的特性。綜上所述本文使用GRU神經網絡進行預測。

2.3 Geohash編碼

Geohash是Gustavo Niemeyer和GM Morton于2008年發明的公共領域地理編碼系統。Geohash將地理位置編碼轉換為由字母和數字組成的短字符串。Geohash基本原理是分別將經緯度進行二等分編碼，按照其所屬區域進行連續編碼，再將兩組編碼混合進行Base32編碼，最后生成需要的Geohash編碼。其具有分層的空間數據結構，可將空間利用Z曲線填充細分為任意精度屬性的網格狀［13］。Geohash編碼在地理位置方面還有更豐富的應用，Jin用Geohash以字符串形式對商店的位置進行編碼，將其視為POI嵌入模型的上下文［18］。Wang利用Geohash編碼提出了一種數據結構的并行網格合并和過濾算法可以提取海道邊界信息［19］。Liu采用Geohash方法為分布式存儲器建立分布式空間索引［20］。但目前還沒有相關文獻把Geohash編碼應用在出租車巡游路線推薦中。

3 構建路網與神經網絡預測

3.1 圖數據庫構建路網

圖數據庫起源于歐拉理論和圖理論，也可稱為基于圖的數據庫，是NoSQL按照數據模型分類的一種。Baas［15］已經在圖數據庫和關系數據庫中使用相同的OSM數據創建了一個測試環境，證明了在最短路徑分析或連接性查詢中基于圖的數據庫是最有益的。由于城市路網的數據規模非常龐大并且多為半結構化數據，故本文將路網建模為圖2。在本文中使用的Neo4J 4.0是一種開源性的圖數據庫管理系統。其不僅支持完整的ACID規則可以清晰地表示半結構化數據，而且提供了REST API方便程序語言訪問。Neo4J的特性符合城市路網建模的要求。

在路網地圖中路線Route是一連續的路段集合，Route={s1，s2，s3···s k}在每個路線Route中路段si-1.end=si.start，每個路段si都有自己的開始路口Intersection_Begin和結束路口Intersection_End。每個路口是由經緯度和唯一的Intersection_ID所確定的，其中每個交叉路口是兩條以上路線的交點。

圖2 海口市部分路網地圖

本文使用的地圖數據來自于開放街道地圖OpenStreetMap［16］，其地形數據被存儲在后綴為OSM格式的文件中。OSM的原始數據由node，relation和key-value pairs組成。如海口市秀英區的OSM文件部分內容如下：

其中215566172是Route牡丹路的編號，由4個編號分別為2250274197，2249907634，2250360142，2250304358的路口節點組成。其中Intersectio_ID為2250274197的路口經緯度是110.2958684，20.0302589。OSM數據使用Python語言的py2neo和xml庫解析后寫入到Neo4J圖數據庫中。

當需要使用Neo4J時，使用一種叫做CQL的聲明性模式匹配語言作為查詢工具。如MATCH p=（）-［r：R_140582515］->（）RETURN p UNION ALL MATCH p=（）-［r：R_215560399］->（）RETURN p，即可查詢出編號為215560399的世貿北路和編號為140582515茉莉路的路線，路段和路口等信息。同理根據圖2的海口市部分路網地圖可以查詢出對應的Neo4J數據路網，如圖3所示。

圖3 使用Neo4j構建后的路網

3.2 Geohash網格與路網結合

為了能夠準確預測需求，將城市劃分為合適大小的區域是實現準確預測的前提。表1為不同Geohash編碼長度對經緯度誤差的影響。把Geohash的經緯度誤差映射到地圖上就是各種不同大小的網格。本文使用8位長度的Geohash編碼，其映射到地圖上面積相當于是一個361m2的網格。當出租車司機發起查詢時，根據出租車的經緯度匹配到其對應的Geohash編碼網格內。把歷史數據的每個時間步長中各個網格內的出租車載客訂單數和相關信息送入GRU神經網絡中學習。

表1 Geohash編碼長度對經緯度誤差的影響

3.3 GRU神經網絡預測

本文使用的歷史數據為滴滴向學界開放的海口市出租車訂單數據［17］，訂單數據包括訂單起止點坐標等信息。

數據范圍：［19.536300，110.130600］，［20.128100，110.130600］，［19.536300，110.694100］，［20.128100，110.694100］

日期范圍：

2017年5月1日至2017年10月31日

數據預處理：

1）清洗掉訂單時間在日期范圍外的，經緯度不在海口市的和亂碼的數據。

2）對歷史數據中出租車司機接客成功的位置其所在經緯度進行Geohash編碼。

驗證歷史數據的充分性：

本文利用信息論中的互信息概念，互信息是變量間相互依賴性的量度，兩個離散隨機變量D和Z的互信息可以定義為I(D;Z)。

其中H(D)，H(Z)是邊緣熵，H(D，Z)是D和Z的聯合熵。

其中p(d i)=v i/∑i vi這里的v i是第i個Geohash網格單元中，出租車接到乘客訂單的數量。

I(D;Z)描述的是隨機變量D和Z之間重疊的部分，但沒有描述出重疊部分占整個聯合熵的比例。Studholme等［14］提出了歸一化互信息NMI，將互信息放在［0，1］區間里。

本文的目標是找到可以基本完全描述D中大多數信息的數據量Z。圖4為歸一化互信息實驗圖，可以看出隨著Z承載著更多的以天為單位的歷史數據，歸一化互信息N MI(D，Z)的值在147天后均大于0.98，說明前147天的數據足以描述98%的歷史數據特征。

圖4 歸一化互信息實驗圖

本文將歷史出租車數據轉換為時間段是一天的數據序列，如圖5顯示了其中一個時間段一個路段的輸入數據，該數據由兩部分組成P t，i和Dt，i，其中P t，i代表t時間段內第i個路段其覆蓋的Geohash網格中出租車載客次數的合集，這里(0

圖5 一個時間段的輸入數據序列

輸出Y是預測出的該城市所有路段其覆蓋的Geohash網格中待打車乘客數量的合集。

本文使用GRU神經網絡預測。ht是隱藏層的輸出，x t是輸入，每個GRU單元通過下列式子計算得到隱藏層的輸出：

其中z t是更新門，r t是重置門，? 是候選隱藏層，它是上一隱藏層輸出結果h t-1的匯總。w是訓練參數矩陣。tanh是雙曲正切激活函數。σ使用Sigmoid作為激勵函數能夠控制重置門和更新門的取值范圍。當更新門是1時，隱藏層的輸出h t和歷史狀態等值，當更新門和重置門均是0時，隱藏層的輸出僅和輸入xt相關。當重置門為1時，候選隱藏層與歷史狀態h t-1和神經網絡的輸入x t有關當重置門是0時候，候選隱藏層與歷史狀態h t-1無關。

4 出租車巡游路線推薦

4.1 Neo4J數據庫與GRU神經網絡預測結合

每個路段si由n個8位Geohash網格包圍著，經過GRU神經網絡預測后的當前時間段該路段第j(1≤j≤n)個Geohash網格內的接單數量是geo-pi ckups j則該路段預測后的當前時間段接單總數是S i-pick u ps。

本文將GRU神經網絡預測的每個Geohash網格內的乘客數量，匹配到對應的路段上計入Si-pick u ps總數更新到Neo4J中對應路段關系的pickups標簽，如編號是R_2155661721的路段［Road：R_2155661721｛length：267，pickups：19｝］表示為該路段長度是267m，GRU神經網絡預測的編號是R_2155661721的路段該時間段內一共有19名待打車乘客。

當每個推薦路段存在n(n≥1)輛預通過的空駛出租車時，則每個空出租車當前時間段遇到待打車乘客數量Ti-pi ckups為

算法1 出租車巡游路線推薦算法

Algorithm 1 Route Recommendations for Taxi DriversInput：Longitude and latitude of taxi

Output：Recommended Si

1：whileTaxi did not receive passengersdo

2： length=［］，pickups=［］，values=［］

3： lon，lat←Update latitude and longitude of the taxi

4： Intersection←Get the nearest intersection of taxi

5： length←Returns all length of road segments starting form this intersection

6： pickups←Returns all Ti-pickups of road segments starting from this intersection

7：fori in len（pickups）do

8： values.append（pickups［i］/length［i］

9：end for

10： return Recommended Si of the best values

11：end while

4.2 巡游路線推薦

表2是出租車巡游路線推薦算法的偽代碼，當出租車司機開始使用巡游路線推薦系統時，算法會根據該出租車的GPS信息匹配到離其最近的一個路口Intersection_ID。以這個路口為起點，依次找到單位距離乘客數量最多的未行駛路段，累加推薦路段即為出租車巡游最優路線。直到出租車司機載客成功停止推薦。如圖6為出租車推薦的一條巡游路線其中的兩個路段，在出租車達到第一個路段的終點路口時如果還沒有接到訂單則繼續推薦下一個路段。在推薦過程中可以實時顯示空載出租車司機行駛過程中周邊區域待打車乘客數量。

圖6 本文方法推薦的一條巡游路線

5 實驗結果分析及討論

實驗環境為操作系統WIN10專業版，Intel Core i7-8550U CPU，8GB內存，NVIDIA MX250獨立顯卡，480G SSD硬盤。

為了驗證模型預測的準確性，本文使用均方誤差（MSE）。MSE是一種常用的回歸損失函數，是指參數估計值與參數真值之差平方的期望值；

從數學上來說，確定神經網絡的參數是一個最優化問題。由3.3節中的互信息可知前147天的數據足以描述98%的歷史數據特征，本文選擇數據集中前150天的數據作為訓練集，后30天的數據作為測試集。使用Keras中的序貫模型進行編程，構建兩層GRU神經網絡。其中，第一層GRU網絡有64個神經元，第二層GRU網絡有32個神經元，輸出層設置為1。為了增加神經網絡模型的非線性，減少梯度消失問題的同時加快訓練速度，本文使用ReLU激活函數。為避免其產生過擬合的現象，將訓練出來的模型Dropout數值設置為0.3。本文選用的損失函數是均方誤差MSE，優化器選用adam，它可以使收斂速度更快的同時波動幅度更小。模型訓練批次（batch）為64，迭代次數（epoch）為50次。如圖7所示橫坐標是迭代次數，縱坐標是loss，當迭代次數到50時，訓練集和測試集的loss都趨于穩定。

圖8是GRU神經網絡預測效果圖，橫坐標是小時數，縱坐標是隨機選取的Geohash編碼為w7w3vym8的地圖網格內的待打車乘客數量，其中圖中虛線是真實值，實線是GRU的預測值，由于預測的后30天共720 h的數據放在圖中過于緊湊，本文取了預測值和真實值的后200h生成實驗圖形。由式（11）得到訓練集的MSE=0.027，測試集的MSE=0.032，可以看到預測結果是令人滿意的。

圖7 GRU神經網絡的loss

圖8 GRU預測效果

本文模擬實驗將四個出租車于2017-6-1日上午9時以Geohash編碼是w7w3vyp2的所在位置即從海口市茉莉路與濱海路的交叉口隨機出發，三個出租車開始無目的巡游，分別用三條虛線表示，另外一個出租車按照本文的推薦方法巡游用實線表示。由圖9可知，隨著推薦巡游路線的引入，出租車遇到待打車乘客數量得到顯著提升。圖9中橫坐標是出租車的行駛距離，單位是m，縱坐標是在此行駛過程中遇到的等待打車的乘客數量。由圖可知在2km距離的巡游中，無目的巡游的出租車1在480m的地方遇到了1名乘客，出租車2共遇到了7名打車乘客，出租車3共遇到了8名乘客。使用本文方法的出租車遇到了20名乘客。由此可得使用本文的推薦巡游路線能夠大幅度增加出租車遇到打車乘客次數，減少出租車空駛，進一步提高司機的利潤。

圖9 出租車行駛距離與遇到乘客的關系

6 結語

在城市交通系統中，出租車因其快捷方便的特性而廣受乘客選擇。如何向出租車司機推薦一個更優巡游路線，成為出租司機能否提高載客效率的關鍵環節。基于上述發現本文提出了一個直接在開源數據庫系統Neo4j上使用CQL語句，實現針對大規模出租車路網與軌跡數據的高效范圍查詢，利用更長字符的Geohash編碼具有更小誤差網格的特點，實現了一種基于GeoHash編碼的空閑出租車巡游路線推薦技術，并通過實驗驗證了該方法技術上的有效性。

在接下來的工作中，將通過兩個方面著手進一步完善本文的方法：一方面獲取更加充分的城市出租車數據，通過分析這些記錄，來更好地感知乘客的出行影響因素。另一方面，充分考慮到城市道路的經常性修繕的問題，在當前工作的基礎上引入觸發器算法自動更新Neo4J上的路網屬性，以便構建更具實時性，準確性的出租車路線推薦模型。