[發明專利]一種基于聚類算法的共享單車停車區布設方法

有效

• 申請號: 202010590509.1
• 申請日: 2020-06-24
• 公開（公告）號: CN111881939B
• 公開（公告）日: 2021-03-09
• 發明（設計）人: 趙德;王煒;武麗佳;梁鳴璋;屠雨
• 申請（專利權）人: 東南大學
• 主分類號: G06K9/62
• 分類號: G06K9/62;G08G1/14
• 代理公司: 南京眾聯專利代理有限公司 32206
• 代理人: 蔣昱

1.一種基于聚類算法的共享單車停車區布設方法，其特征在于，包括如下步驟：

S1、獲取共享單車歷史位置數據；

所述步驟S1中，每隔T小時，獲取一次城市區域內所有共享單車的歷史位置數據，累計采集14天；第一個7天數據為訓練集，第二個7天數據為驗證集；共享單車的歷史位置數據包括每輛車的編號n、經度緯度λ、獲取時間t；

S2、對共享單車位置數據進行坐標轉換；

所述步驟S2中的坐標轉換為聚類數據，將S1中的經度與緯度λ數據，轉化為UTM坐標數據(E，N)，轉化后的數據為聚類數據庫；

S3、初始化DBSCAN算法聚類參數并初步聚類；

所述步驟S3具體包括如下步驟：

S31、初始化DBSCAN聚類模型的參數EPS和minPts，EPS和minPts從可選集Z中無放回的選取；可選集Z由EPS∈{x|0x60,x∈N}與minPts∈{x|0x30,x∈N}的任意兩兩組合構成；

S32、針對步驟S2的聚類數據庫中坐標數據(E，N)，采用步驟S31中的參數值進行DBSCAN聚類，根據聚類結果將每組坐標標記為一級類編號或噪聲；

S4、采用k均值聚類算法劃分過大類；

所述步驟S4具體步驟為提取步驟S32聚類后的非噪聲數據，對具有相同一級類編號的數據進行k均值聚類，k初始值設置為1；若生成的聚類中心到達該類中每個數據點的距離均小于臨界值R1，則無需對該類進行細分，二級類編號與一級類編號相同；否則，調整k值為k+1，重新進行k均值聚類，直至每個子類中聚類中心到達該子類中每個數據點的距離均小于臨界值R1，二級類編號為一級類編號+子類編號；

S5、評價指標計算與聚類參數遍歷情況檢驗；

所述步驟S5具體包括如下步驟：

S51、評價指標計算：評價指標包含三個，覆蓋率、總停車區數量和停車區平均自行車數，三個指標是關于聚類參數EPS和minPts的函數；

S52、聚類參數遍歷情況檢驗：如果當前聚類可選集Z為空集，則表明聚類參數遍歷完全，進入步驟S6；否則返回步驟S3繼續進行；

S6、提出最優共享單車停車區位置及容量；

所述步驟S6根據優化問題計算選取最優聚類結果，決策變量為EPS和minPts；最優共享單車停車區位置為最優解對應的聚類中心，停車區容量為聚類中心對應的類別中含有的自行車數量；

S7、判別停車區布設效果的穩定性；

所述步驟S7中停車區布設效果的穩定性由訓練方案與驗證方案的交叉最短鄰距離CNND確定；

所述步驟S7中的CNND計算公式如下：

其中，n_Ai為訓練方案中第i個自行車停車區的停車容量，n_Bi為驗證方案中第i個自行車停車區的停車容量，d_Ai為訓練方案中的第i個停車區到驗證方案中任一停車區的最短距離；d_Bi為驗證方案中的第i個停車區到訓練方案中任一停車區的最短距離；m_A和m_B分別為訓練方案和驗證方案中規劃的停車區個數；

當CNND小于或等于臨界值R2，則通過穩定性檢驗，輸出步驟S6中的停車區位置與停車區容量，結束所有計算步驟；當CDDN大于臨界值R2，則不通過穩定性檢驗，減少數據獲取時間間隔T，即增大數據獲取頻率，為原來的一半，返回至步驟S1重新獲取數據。

2.根據權利要求1所述的一種基于聚類算法的共享單車停車區布設方法，其特征在于，所述S51中評價指標三個，覆蓋率、總停車區數量和停車區平均自行車數，具體計算公式如下：

覆蓋率

總停車區數量NP(EPS,minPts)＝|Cluster(EPS,minPts)| (2)

停車區平均自行車數

其中，|Noise(EPS,minPts)|為DBSCAN聚類時被認定為噪聲的共享單車數量，|D|為共享單車總數，|Cluster(EPS,minPts)|為k均值聚類后形成的所有類別數。