王小霞，歐陽露，鄭詩琪，胡三根，韓 霜

（廣東工業(yè)大學 土木與交通工程學院, 廣東 廣州 510006）

國內外已有研究主要通過提高?？奎c的規(guī)劃水平緩解共享單車潮汐現象，例如，He等[5]應用短期需求預測模型捕捉共享單車出行數據的時空特征，并在?？奎c層面預測需求量,提出了一種基于熵與理想解相似的偏好排序方法(TOPSIS)。Lin等[6]探討了共享單車系統(tǒng)戰(zhàn)略規(guī)劃，建立數學模型確定?？奎c的數量和位置、停靠點之間的路網結構以及起終點的騎行路線，為?？奎c規(guī)劃提供數據支撐。孫文霞等[7]為處理好共享單車與其他出行方式的兼容問題，通過綜合分析停靠點及其所在線路相關路網信息，調整汽車公交線路，利用?？奎c優(yōu)化配置提高交通路網利用率。靳爽等[8]基于共享單車?？奎c、公交路網的綜合調整優(yōu)化方法，在有限個可供選擇的?？奎c基礎上，建立一種雙層規(guī)劃模型。Erdogan等[9]基于靜態(tài)自行車再平衡問題，考慮到調度成本最低、各?？奎c出入流量平衡，提出一種共享單車系統(tǒng)靜態(tài)再平衡算法。劉嘉文等[10]為解決共享單車停靠點位置及車輛匹配問題，基于聯合覆蓋選址思想，提出一種共享單車停靠點選址和初始車輛的多維度優(yōu)化模型。

上述研究成果對本文的切入點有很大啟發(fā)，雖然共享單車的出現，極大地方便了人們的出行，但用戶在結束行程時“便捷性”選擇停放區(qū)域，導致城市街道共享單車?？奎c淤積占道問題。因此，提升共享單車?？奎c規(guī)劃水平，緩解?？奎c的潮汐現象不僅可以從調度[11]著手，還可以從用戶停靠點優(yōu)化選擇[12]切入。基于此，本文以城市共享單車停靠點為研究對象，通過給用戶提供?？奎c優(yōu)化選擇，從源頭上實現潮汐點位的“削峰填谷”。本文提出的?？奎c優(yōu)化選擇共包括兩個維度，第一個維度是對共享單車數據進行挖掘，確定GeoHash編碼后的有限個?？奎c空間分布，結合熱力圖對?？奎c區(qū)域進行網格劃分，量化表達共享單車?？奎c的使用情況，并使用透視表統(tǒng)計每個編碼區(qū)域在不同時間的入流量和出流量，進而計算出停靠點潮汐現象較突出的區(qū)域。第二個維度是根據第一個維度的結果，利用KNN算法選取20個距離最近的待選?？奎c，根據停靠點的潮汐程度，完成候選?？奎c的聚類分析，并在考慮?？奎c的連通性后，對候選?？奎c進行二次劃分，篩除非連通性的?？奎c，實現對用戶?？奎c的優(yōu)化選擇，最大限度地實現共享單車的合理利用。

1 算法應用

1.1 GeoHash編碼

GeoHash編碼[13]根據精度不同將區(qū)域分解成多個子塊，在一定經緯度范圍內的子塊會擁有相同編碼，而且在合適的精度下，GeoHash編碼足以解決對點位經緯度的收集和檢索問題。GeoHash編碼的方法是用二分法分別將需編碼的p點經緯度所屬區(qū)間[a，b]縮小，區(qū)間[a，b]不斷被分成左右兩部分的區(qū)間，若p點屬于左半部分區(qū)間則計為二進制0，屬右半部分區(qū)間計為1，如圖1和圖2所示，GeoHash編碼以5個位(bit)二進制為一組，根據Base32信息可將其轉化成1個可見字符，隨著可見字符數(GeoHash編碼精度)的增加，區(qū)間[a，b]范圍會愈來愈逼近p點[14]。

圖1 經緯度的二進制編碼Fig.1 The binary coding of longitude and latitude

圖2 經緯度的Base32編碼Fig.2 The Base32 encoding of longitude and latitude

結合研究對象，對共享單車訂單數據中經緯度為(118.111 688°,24.527 919°)的數據進行編碼。本次GeoHash編碼精度為6，先對經度118.111 688°進行逼近編碼。地球經度區(qū)間分為[-180°,180°]，即可將其二分為[-180°,0°)和[0°,180°]，可知118.111 688°屬于右區(qū)間[0°,180°]，給予標記為1。再將[0°,180°]分為[0°,90°)和[90°,180°]，可判斷118.111 688°為右區(qū)間[90°,180°]，給予標記為1。如此循環(huán)迭代，可以將118.111 688°所屬的[a,b]區(qū)間縮小，使其位置范圍愈來愈逼近118.111 688°。具體的迭代流程如表1所示，得到經度118.111 688°的二進制編碼為11010 01111 11110。同理，緯度24.527 919°的二進制編碼為10100 01011 10001。然后，將經緯度交替進行排序，得到二進制編碼為11100 11000 00111 01111 11101 01001。最后，對照表2的Base32編號表，將以5個位(bit)為一組的二進制編碼轉化成相應的可見字符，得到經緯度(118.111 688°,24.527 919°)的GeoHash編碼為wsk531。

表1 經度118.111 688°的GeoHash編碼計算Table 1 GeoHash coding calculation for longitude 118.111 688°

表2 Base32字符編號Table 2 Base32 character encoding

1.2 KNN聚類分析

根據GeoHash算法編碼得到共享單車?？奎c編碼區(qū)域的使用情況，對此進一步采用KNN分類識別算法[15-16]實現停靠點優(yōu)化選擇，即選擇非潮汐區(qū)域，使用情況無大幅度波動且靠近目的地的?？奎c。然而識別結果可能與上述要求不符，因此，選取區(qū)域編碼后的有限個共享單車初始?？奎c，根據歐氏距離最小原則，將聚類結果劃分納入候選?？奎c。

假設給定一個共享單車?？奎c數據集X={x1,x2,···,xN},xi(i=1,2,···,N)為二維變量、一個測試點q=(x,y)∈M((x,y))，其中數據集X表示編碼區(qū)域共享單車?？奎c位置，(x,y)表示經緯度坐標。采用歐氏距離作為判斷依據，在集合X中找到K個與q近鄰的點，即確定K個候選?？奎c，使數據點之間的絕對差異最小，歐氏距離計算公式如式(1)所示。

航空模型是整個作業(yè)過程的實施者，攝像機進行工作時，離不開航空模型的幫助。因此，航模也是其中一個特別重要的因素，尤其是航模的控制系統(tǒng)，由于航模的承載能力、控制靈敏度以及動作平滑等會對成像效果有很大的影響，如何提升航模的飛行穩(wěn)定性、運行路線的精準性以及飛行與拍攝系統(tǒng)向匹配等功能等，都是未來航模航拍控制系統(tǒng)需要提升和創(chuàng)新的內容。

式中：d(xi，xj)表示測試集與訓練集之間的距離，(xi，xj)為數據點(i，j)的坐標值。分別計算待測點q與所選取的K個候選停靠點相似度，然后，篩選出類別近鄰點并對其相似度求和，式(2)表示待測點q與類別Ci的總相似度。

式中：Tj表示待測樣本q的第j個K最近鄰，計算并比較待測樣本q與不同類別的總相似度，q待測樣本屬于與其總相似度最大的類別，最終q的類別表達式為

1.3 ?？奎c優(yōu)化選擇

采用GeoHash編碼和KNN算法進行共享單車?？奎c的優(yōu)化選擇，具體步驟如下。

步驟1：根據研究區(qū)域進行經緯度編碼，得到二進制序列。

步驟2：對二進制編碼按照奇偶位合并，進一步整合Base32編碼結果。

步驟3：使用透視表統(tǒng)計每個編碼區(qū)域在不同時間的出入流量。

步驟4：根據編碼區(qū)域內共享單車停靠點數據，輸入數據對象xi，分類中心數量K。

步驟5：選取K個共享單車候選?？奎c。

步驟6：分別計算測試集到候選?？奎c的距離，將共享單車匹配到最近的候選停靠點。

步驟7：進一步篩除潮汐現象嚴重的、需過街的?？奎c，得到最終結果。

2 共享單車數據與預處理

本文的數據時間是2020年12月21日至2020年12月25日(周一至周五)，數據范圍是廈門市湖里區(qū)與思明區(qū)，研究樣本是工作日早高峰(06:00～09:00)的58萬余條哈嘍單車訂單數據，此外，還包括共享單車停車點位(電子圍欄)數據和共享單車軌跡數據。將起點位置(即軌跡數據經緯度)可視化和廈門市矢量邊界比對后，可確認共享單車數據皆在位置范圍內，基本可以全面反映共享單車的真實使用情況。

2.1 共享單車訂單數據

訂單數據字段包括BICYCLE_ID(車輛編碼)、LATITUDE(緯度)、LONGITUDE(經度)、LOCK_STATUS(鎖車狀態(tài))、UPDATE_TIME(鎖車狀態(tài)更新時間)5個字段。為了隱私保護，車輛編碼數據結構只取了前10位。鎖車狀態(tài)中“0”代表開鎖狀態(tài)，“1”代表鎖車狀態(tài)。具體訂單數據結構如表3所示。

表3 共享單車的訂單數據結構Table 3 The data structure of shared bikes’ order

2.2 共享單車?？奎c(電子圍欄)數據

?？奎c數據包括FENCE_ID(電子圍欄唯一編號)、FENCE_LOC(電子圍欄唯一坐標)兩個字段。其中，FENCE_ID表示停車區(qū)域中每一個電子圍欄的順序編號，而FENCE_LOC表示電子圍欄所在位置的坐標串。電子圍欄數據結構如表4所示。

表4 ?？奎c數據結構Table 4 The data structure of shared bikes’ parking points

2.3 共享單車軌跡數據

軌跡數據包括BICYCLE_ID(車輛編碼)、LOCATING_TIME(定位時間)、LATITUDE(緯度)、LONGITUDE(經度)、SOURCE(數據來源)5個字段，軌跡數據結構如表5所示。其中，車輛編碼是指對應此條軌跡數據的車輛名稱，軌跡數據與訂單數據中的經緯度皆是指提取共享單車數據時的地理坐標位置。

表5 軌跡數據結構Table 5 The data structure of shared bikes’ tracks

2.4 數據的預處理

對共享單車數據進行預處理，可免除噪聲數據對結果精確度的影響。數據的預處理主要從以下幾個方面進行。

(1) 數據清洗與整理。本文選擇的是廈門市思明區(qū)與湖里區(qū)的共享單車數據，首先，以兩區(qū)經緯度范圍(北緯24.445°至24.512°，東經118.146°至118.082°)為邊界，將不在這個經緯度范圍的訂單數據剔除，其次，將重復的數據和空白的字段清理。

(2) 處理停車點位信息。計算每個停車點的面積和中心經緯度，并用GeoHash庫對停車點位經緯度進行編碼。

(3) 出入流量分析。將共享單車的訂單數據和停車數據相匹配，使用透視表統(tǒng)計每個區(qū)域在不同時間的入流量和出流量，進而計算出停靠點潮汐現象較突出的區(qū)域。

3 數據結果分析與停靠點優(yōu)化選擇

3.1 路段的出入量分析

用G e o H a s h 編碼檢索觀日路路段編碼為wsk531和wsk532的區(qū)域，分別檢索到12 319個和7 267個記錄。根據訂單信息里的鎖車數據，來判斷該共享單車在該區(qū)域是鎖車狀態(tài)還是開鎖狀態(tài)。鎖車狀態(tài)的單車屬于該區(qū)域的入流量，開鎖狀態(tài)的單車為出流量。兩個區(qū)域均在12月21日～12月25日的8時左右出現峰值，根據觀日路wsk531的區(qū)域工作日早高峰出入流量圖(見圖3)，以及wsk532的區(qū)域工作日早高峰出入流量圖(見圖4)，可以得出：(1) 在編碼為wsk531的區(qū)域，周一、周二和周四的車輛出入量最高峰值為700輛，周三為250輛；在編碼為wsk532的區(qū)域，周一、周二和周四車輛出入量最高峰值為400輛，周三為200輛。為此，周一、周二和周四的車輛出入量是周三的兩倍左右。(2) 在編碼為wsk531的區(qū)域，周一至周四早高峰的共享單車出入流量相對穩(wěn)定；而在編碼為wsk532的區(qū)域，周一至周四早高峰的共享單車入流量與出流量相差明顯，入流量是出流量的兩倍，存在車輛堆積現象。(3) 編碼為wsk531的區(qū)域，周五早高峰的共享單車出流量接近3 000輛，遠高出峰值為500輛的入流量；在編碼為wsk532的區(qū)域，周五早高峰的共享單車出流量接近1 600輛，而入流量峰值只有400輛?；谏鲜龇治隹芍斐晒蚕韱诬囃？奎c潮汐現象的原因，主要包括使用時間段、日出行時間、共享單車調度、?？奎c選擇等。

圖3 wsk531區(qū)域的工作日早高峰出入流量圖Fig.3 The morning peak flow of wsk531

圖4 wsk532區(qū)域的工作日早高峰出入流量圖Fig.4 The morning peak flow of wsk532

3.2 路段的潮汐分析

選取洪漣路、云頂中路、觀日路、呂嶺路和觀日路這5條路段的附近區(qū)域，對其進行潮汐程度計算，即用出流量減去入流量，當留存量大于區(qū)域?？奎c平均留存量時，可知該停靠點潮汐現象明顯，得到如圖5所示的各路段區(qū)域潮汐現象：(1) 在21日～24日的早高峰時間段，洪漣路、云頂中路、觀日路路段附近區(qū)域出現了明顯的潮汐現象，而呂嶺路和長樂路附近區(qū)域的曲線接近于零，其無潮汐現象。(2) 洪漣路和觀日路附近區(qū)域的車輛流量總數小于零，即入流量大于出流量，說明共享單車投入過多出現堆積現象。云頂中路附近區(qū)域的車輛流量總數大于零，說明共享單車供不應求，需要從別的地方調度車輛或者進行引導用戶在此路段?？?。(3) 周五當天，5個路段附近區(qū)域的車輛流量總數都是大于零，且觀日路＞洪漣路＞云頂中路＞呂嶺路＞長樂路。這就要求在節(jié)假日期間，適當增大共享單車的供應數量，或者從區(qū)域車流量總數小于零的地方調度車輛。

圖5 各路段區(qū)域的潮汐狀態(tài)Fig.5 The tidal state of shared bikes’ parking points of five road sections

3.3 停車區(qū)域熱度分析

通過整理共享單車訂單中同一時間點鎖車狀態(tài)為“1”的單車數據，可以計算出該區(qū)域的停車量，得到各個區(qū)域的共享單車停車熱力圖，從而能夠把共享單車的停車圍欄數據導入熱力圖中，對其進行對比分析，如圖6的某區(qū)域停車熱度圖所示，把圖中紅黃色區(qū)域定義為共享單車停放的區(qū)域，藍色區(qū)域定義為規(guī)定的停車圍欄，可見許多停車點位上沒有停放共享單車，例如，湖濱路上的某一路段，左右兩側車輛過多，停車點位不足，導致有很多車輛未停在規(guī)定位置。另外，對于潮汐現象嚴重的區(qū)域，可以通過為用戶推薦附近沒有潮汐現象的停車點位，來緩解共享單車的擁堵現象。有些?？奎c雖說距離很近，但可能是在街道的另一邊，又或者是在立交橋下，所以，應當考慮街道信息對?？奎c優(yōu)化選擇的影響。

圖6 某區(qū)域的停車熱度圖Fig.6 The parking heatmap of an area

3.4 停靠點優(yōu)化選擇

整合數據結果分析，得到共享單車的?？奎c熱度圖，其潮汐程度相差明顯，如圖7所示。因此，需要對用戶停靠點進行優(yōu)化選擇，假設圖8中的黑色圖標表示用戶要到達的目的地，藍色圖標為共享單車?？奎c，可見目的地周邊提供了較多停靠點，但其中仍存在著一些距離相對較遠的?？奎c，為此，在用戶到達目的地之前，結合其所處的時間段與位置信息，通過GeoHash編碼快速檢索出停靠點的地理編碼；根據路段潮汐統(tǒng)計，可以得出每個街道的具體潮汐情況；其次，按照密度計算(即留存量大于?？奎c平均留存量)得到潮汐情況最為嚴重的停靠點區(qū)域；利用KNN算法計算出20個最近的待選?？奎c，篩除潮汐現象嚴重的、需過街的?？奎c。圖8中用紅圈表示的20個待選停靠點，需要根據該時刻的停車熱度信息進一步篩選，從而剔除掉有潮汐狀況的?？奎c，即剔除圖9中的紅色地標停靠點。

圖7 ?？奎c熱度圖Fig.7 The heatmap of shared bikes’ parking points

圖8 20個最近鄰?？奎c熱度圖Fig.8 The heatmap of the 20 nearest neighbor shared bikes’ parking points

圖9 篩選出的潮汐狀態(tài)嚴重的?？奎cFig.9 The selected parking points with serious tidal state

即使篩除圖9中含有潮汐狀況的停靠點，仍然會存在著許多與目的地不具連通性的區(qū)域，因此，根據停靠點的連通性，對待選停靠點再一次進行篩選(例如，剔除需過街、過天橋停靠點)，從而把不具連通性的停靠點篩除，得到最終推薦給用戶的停靠點，如圖10所示。

圖10 最終推薦的?？奎c示意圖Fig.10 The final recommended parking points

4 結論

本文提出一種融合GeoHash和KNN算法，實現共享單車?？奎c優(yōu)化選擇的方法，得到以下研究結論：

(1) 共享單車?？奎c潮汐現象產生的原因主要包括使用時間段、日出行時間、共享單車調度方法、?？奎c選擇等，前兩者會影響到早高峰通勤時間、節(jié)假日出行游玩時間的?？奎c優(yōu)化選擇；后兩者會影響到共享單車?？奎c的調度分配策略。

(2) GeoHash分區(qū)編碼能夠有效地識別共享單車?？繝顟B(tài)不合理的問題，進而確定共享單車的候選停靠點及其數量，還能夠結合出行者的目的地以及共享單車?？奎c的供給，完成共享單車的時空供需平衡分析，提高共享單車的利用率。

(3) KNN分類識別算法能夠有效地識別出潮汐現象嚴重的共享單車?？奎c，進一步確定推薦給用戶的候選?？奎c及其數量，結合?？奎c的連通性以及共享單車?？奎c的供給，還可以完成共享單車的最佳?？奎c分析，減少用戶的停車決策時間。

(4) 在利用大規(guī)模共享單車訂單數據，確定共享單車?？奎c的基礎上，使用GeoHash算法對停靠點進行分區(qū)編碼，并使用KNN算法篩選出具有非潮汐現象的?？奎c，能夠達到?？奎c優(yōu)化選擇的目的，為緩解共享單車?？奎c潮汐問題提供有益借鑒。