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

欒方軍 張鵬旭 曹科研

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

1 引言

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

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

圖1 推薦模型的整體流程

2 相關工作

2.1 出租車尋客推薦

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

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

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

2.2 神經(jīng)網(wǎng)絡

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

2.3 Geohash編碼

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

3 構建路網(wǎng)與神經(jīng)網(wǎng)絡預測

3.1 圖數(shù)據(jù)庫構建路網(wǎng)

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

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

圖2 ?？谑胁糠致肪W(wǎng)地圖

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

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

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

圖3 使用Neo4j構建后的路網(wǎng)

3.2 Geohash網(wǎng)格與路網(wǎng)結合

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

表1 Geohash編碼長度對經(jīng)緯度誤差的影響

3.3 GRU神經(jīng)網(wǎng)絡預測

本文使用的歷史數(shù)據(jù)為滴滴向學界開放的?？谑谐鲎廛囉唵螖?shù)據(jù)［17］，訂單數(shù)據(jù)包括訂單起止點坐標等信息。

數(shù)據(jù)范圍：［19.536300，110.130600］，［20.128100，110.130600］，［19.536300，110.694100］，［20.128100，110.694100］

日期范圍：

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

數(shù)據(jù)預處理：

1）清洗掉訂單時間在日期范圍外的，經(jīng)緯度不在?？谑械暮蛠y碼的數(shù)據(jù)。

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

驗證歷史數(shù)據(jù)的充分性：

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

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

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

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

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

圖4 歸一化互信息實驗圖

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

圖5 一個時間段的輸入數(shù)據(jù)序列

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

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

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

4 出租車巡游路線推薦

4.1 Neo4J數(shù)據(jù)庫與GRU神經(jīng)網(wǎng)絡預測結合

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

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

當每個推薦路段存在n(n≥1)輛預通過的空駛出租車時，則每個空出租車當前時間段遇到待打車乘客數(shù)量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是出租車巡游路線推薦算法的偽代碼，當出租車司機開始使用巡游路線推薦系統(tǒng)時，算法會根據(jù)該出租車的GPS信息匹配到離其最近的一個路口Intersection_ID。以這個路口為起點，依次找到單位距離乘客數(shù)量最多的未行駛路段，累加推薦路段即為出租車巡游最優(yōu)路線。直到出租車司機載客成功停止推薦。如圖6為出租車推薦的一條巡游路線其中的兩個路段，在出租車達到第一個路段的終點路口時如果還沒有接到訂單則繼續(xù)推薦下一個路段。在推薦過程中可以實時顯示空載出租車司機行駛過程中周邊區(qū)域待打車乘客數(shù)量。

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

5 實驗結果分析及討論

實驗環(huán)境為操作系統(tǒng)WIN10專業(yè)版，Intel Core i7-8550U CPU，8GB內存，NVIDIA MX250獨立顯卡，480G SSD硬盤。

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

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

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

圖7 GRU神經(jīng)網(wǎng)絡的loss

圖8 GRU預測效果

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

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

6 結語

在城市交通系統(tǒng)中，出租車因其快捷方便的特性而廣受乘客選擇。如何向出租車司機推薦一個更優(yōu)巡游路線，成為出租司機能否提高載客效率的關鍵環(huán)節(jié)?；谏鲜霭l(fā)現(xiàn)本文提出了一個直接在開源數(shù)據(jù)庫系統(tǒng)Neo4j上使用CQL語句，實現(xiàn)針對大規(guī)模出租車路網(wǎng)與軌跡數(shù)據(jù)的高效范圍查詢，利用更長字符的Geohash編碼具有更小誤差網(wǎng)格的特點，實現(xiàn)了一種基于GeoHash編碼的空閑出租車巡游路線推薦技術，并通過實驗驗證了該方法技術上的有效性。

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