基于GeoHash與聚類的共享單車動態(tài)回收點設(shè)置方法研究

張志清，李亞偉，董 靜 ZHANG Zhiqing,LI Yawei,DONG Jing

（1.武漢科技大學(xué) 恒大管理學(xué)院，湖北 武漢 430065；2.武漢科技大學(xué) 服務(wù)科學(xué)與工程研究中心，湖北 武漢 430065）

近年來，隨著共享單車投入數(shù)量的逐年增多，也產(chǎn)生了大量損壞車輛，如果不能及時處理，在造成資源浪費的同時也會導(dǎo)致一定的經(jīng)濟損失，因此，如何獲取損壞車輛的相關(guān)信息并進行及時處理，是相關(guān)企業(yè)良好運營的關(guān)鍵所在。對共享單車而言，由于其創(chuàng)新型無樁停放特性導(dǎo)致車輛停放位置是無序和分散的，因此，共享單車的故障車輛更難回收處理。有學(xué)者從多個視角對共享單車的運營進行了研究，主要集中在單車投放站點的選址[1]、單車系統(tǒng)的調(diào)度與優(yōu)化策略[2-4]、停車點最佳投放量決策模型[5]等，但對如何高效處理故障單車方面的研究相對較少，因此本文提出動態(tài)回收點概念，在對騎行數(shù)據(jù)進行分析處理的基礎(chǔ)上，采用GeoHash與聚類方法對共享單車動態(tài)回收點設(shè)置方法，為共享單車的管理提供了新的思路，具有一定的理論和實際意義。

1 共享單車騎行數(shù)據(jù)處理分析

1.1 原始數(shù)據(jù)處理

本研究中的樣本數(shù)據(jù)取自2017摩拜杯算法挑戰(zhàn)賽，共包含3 214 096條出行記錄。由于原始數(shù)據(jù)經(jīng)過GeoHash算法編碼，所以需要對數(shù)據(jù)進行解碼處理。根據(jù)GeoHash算法的編碼規(guī)則，設(shè)計解碼算法流程如圖1所示。

用Java語言編寫程序?qū)崿F(xiàn)GeoHash解碼算法，經(jīng)檢驗，算法運行效果良好，可以實現(xiàn)上述GeoHash解碼算法，解碼后的部分?jǐn)?shù)據(jù)如表1所示。

表1 解碼后部分?jǐn)?shù)據(jù)表

圖1 GeoHash編碼的解碼算法流程圖

1.2 空間分布特征分析

根據(jù)GeoHash解碼算法得到的經(jīng)緯度數(shù)據(jù)，生成各個共享單車的空間分布數(shù)據(jù)，利用ArcGIS軟件形成.shp格式的點文件；然后通過ArcGIS漁網(wǎng)生成工具箱，生成北京市200*200米的網(wǎng)格數(shù)據(jù)形成.shp格式的面文件，將共享單車的O（Origin） 點、D（Destination）點空間位置數(shù)據(jù)聚合到網(wǎng)格中，將網(wǎng)格上的O點、D點數(shù)據(jù)通過核密度熱力圖的形式進行展示，圖2為北京市摩拜單車2017年5月10日至2017年5月24日騎行數(shù)據(jù)的O、D點熱力圖。

圖2 摩拜單車騎行熱力圖

圖中熱力強度等級由無色、綠色系、黃色系、橙色、深紅、黑色表示并依次增強。為了更加直觀、細致的了解各地區(qū)、站點共享單車的使用強度，在熱力圖分析的基礎(chǔ)上，通過對騎行區(qū)域進行網(wǎng)格劃分來量化顯示單車使用強度，其中每個網(wǎng)格設(shè)定為800*800米。以D點騎行數(shù)據(jù)為例，在ArcGIS軟件中計算每個網(wǎng)格區(qū)域的日平均騎行量，如圖3所示。

圖3 摩拜單車D點日均騎行量圖示

圖4 北京局部地區(qū)摩拜單車日均騎行量顯示圖

在有單車使用數(shù)據(jù)的區(qū)域，最低日平均騎行量為0.66667次，最高日平均騎行量為1 376.333374次，據(jù)此劃分了5種顏色所代表的日平均騎行量等級，圓圈內(nèi)數(shù)字表示該區(qū)域的日均騎行量。其中綠色圓點表示該區(qū)域單車日均使用200次以內(nèi)；藍色表示該區(qū)域單車日均使用200～400次；黃色表示該區(qū)域單車日均使用400～600次；粉色表示該區(qū)域單車日均使用600～800次；紅色表示該區(qū)域單車日均使用800～1 376.333374次。取局部區(qū)域進行共享單車空間分布點更加細致的分析。局部日均騎行量如圖4所示。

圖4中三個紅色圓點所在區(qū)域為北京大紅門服裝商貿(mào)城到百榮世貿(mào)商城的一片商貿(mào)區(qū)域和東鐵營村這一集中住宅區(qū)，并且這三處均離地鐵站點較近；并且由圖4可知，圖中紅、粉、黃三色所代表的最高強度單車使用區(qū)域有其共同特征，這些區(qū)域多在地鐵站點周邊，且所在區(qū)域多為辦公樓、商場、娛樂場所、住宅區(qū)，這些區(qū)域均有較多且穩(wěn)定的騎行需求。

綜上所述，通過對騎行終點數(shù)據(jù)的空間分布分析，可以基本了解到北京摩拜單車的使用情況，包括單車使用的熱點區(qū)域分布特征以及各地區(qū)日均使用量數(shù)據(jù)，可為后續(xù)的逆向物流網(wǎng)絡(luò)規(guī)劃提供參考依據(jù)。

1.3 單車回收點聚類分析

本文利用北京摩拜的騎行終點數(shù)據(jù)，通過K-means聚類分析形成一定范圍的騎行終點區(qū)域作為回收需求區(qū)域，并將回收需求區(qū)域中的聚類中心點作為回收點，便于后續(xù)逆向物流網(wǎng)絡(luò)構(gòu)建。K-means算法是基于無監(jiān)督學(xué)習(xí)提出的聚類算法，算法描述如下：

輸入：訓(xùn)練樣本V=｛v1,v2,v3,…,vn｝；k：聚類個數(shù)；

輸出：C=｛c1,c2,c3,…,ck｝。

步驟1：在數(shù)據(jù)集中隨機挑選k個對象作為初始聚類中心c1,c2,c3,…,ck。

步驟2：計算數(shù)據(jù)集中每個對象到聚類中心的位置，選取最小距離分配到聚類中，其中V=｛v1,v2,v3,…,vn｝；j=1,2,3,…,k。

步驟3：將每個聚類中的所有對象的均值作為新的聚類中心，如式（1）所示：

nj為第j類中對象的個數(shù)，j=1,2,3,…,k。

步驟4：當(dāng)各個簇的聚類中心不在發(fā)生變化，聚類準(zhǔn)則函數(shù)如式（2）所示：

收斂，則算法結(jié)束，到步驟5；否則返回步驟2繼續(xù)迭代。

步驟5：輸出聚類結(jié)果。

K-means算法優(yōu)點是可以處理大數(shù)據(jù)集，并且聚類速度較快，有較好的拓展性，K-means算法是相對可伸縮的和高效率的，因為它的計算復(fù)雜度為O（nkt），其中n為對象個數(shù)，k為聚類個數(shù)，t為迭代次數(shù)，通常有t≤n，k≤n，因此它的復(fù)雜度通常也用O（n）表示。

本文取經(jīng)緯度坐標(biāo)點（116.345771,39.981975）和（116.400532,39.955543）作為該矩形區(qū)域?qū)蔷€上兩點，在樣本騎行數(shù)據(jù)中截取出D點在此范圍內(nèi)的數(shù)據(jù)，共獲得70 480條騎行數(shù)據(jù)，該區(qū)域面積約為4.5km*2km。在此區(qū)域根據(jù)騎行數(shù)據(jù)建立D點熱力圖，如圖5所示。

利用Matlab進行編程實現(xiàn)K-means聚類算法，并在Intel Core i5-5600U CPU@2.50GHz處理器PC上運行，設(shè)置算法參數(shù)，利用基本的K-means算法進行求解，運行4min得到聚類結(jié)果。經(jīng)檢驗，該聚類算法具有很強的可操作性，結(jié)果可用于后續(xù)規(guī)劃模型。計算過程中，基本的K-means算法的誤差平方和的收斂圖如圖6所示。

圖5 聚類區(qū)域D點熱力圖

圖6 K-means算法誤差平方和的收斂圖

可以看到：聚類的誤差平方和在12個聚類點之后趨于穩(wěn)定，說明算法收斂。并且在選擇算法k值時也可參考聚類區(qū)域熱力圖輔助分析，結(jié)合聚類區(qū)域熱力強度高的區(qū)域個數(shù)作為現(xiàn)實參考因素合理配置k值。本文結(jié)合熱力圖分析和上述收斂圖結(jié)果，選取12個聚類點。算法得到的聚類中心的經(jīng)緯度坐標(biāo)如表2所示。

在ArcGIS軟件中將上述聚類點顯示于聚類區(qū)域熱力圖上，如圖7所示。

表2 K-means算法聚類點坐標(biāo)

圖7 聚類點結(jié)合熱力圖綜合顯示圖

圖中黑色棋子即為聚類中心點所在位置，可以看出，聚類中心整體分布情況與共享單車騎行熱力圖中的熱點區(qū)域吻合度較高，比較符合共享單車運營的實際情況，證明該方法的有效性。

2 結(jié)論

在考慮騎行分布特征和現(xiàn)實回收狀況的前提下，對共享單車回收處理的逆向物流網(wǎng)絡(luò)規(guī)劃方法進行了研究， 基于GeoHash算法對原始數(shù)據(jù)進行解碼處理， 在此基礎(chǔ)上，對騎行大數(shù)據(jù)進行空間分布特征分析， 然后通過聚類分析方法，對所取研究范圍內(nèi)的騎行數(shù)據(jù)進行聚類分析，得到回收服務(wù)區(qū)的回收點分布及每個回收點的位置信息。在分析共享單車騎行空間分布特征的基礎(chǔ)上，提出了利用K-means聚類對共享單車回收點進行聚類分析的方法。該方法可以有效地計算騎行需求區(qū)域，即為單車回收需求區(qū)域，并將聚類點作為單車回收點。這一關(guān)鍵步驟為后續(xù)的共享單車回收逆向物流路徑規(guī)劃研究奠定了堅實的基礎(chǔ)。