[發明專利]一種基于k-means算法的公共自行車智能調度系統區域劃分方法

在審

• 申請號: 201611103426.5
• 申請日: 2016-12-02
• 公開（公告）號: CN108154250A
• 公開（公告）日: 2018-06-12
• 發明（設計）人: 張晶;梁燕;馮宇;魏文俊;王謀;鄭嘉欣;王珂栩
• 申請（專利權）人: 重慶郵電大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/06;G06Q50/26
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種基于k-means算法的公共自行車智能調度系統區域劃分方法，其具體包括如下步驟：

S1、采用k-means算法對公共自行車系統內的所有站點根據經緯度分為K個區域；

S2、計算每一區域的所有站點的調度需求量總和；

S3、將調度需求量總和絕對值大于20的區域的邊緣站點放置一個集合，引進調度需求量這一新的參數，用k-means算法再次對這個集合內的站點劃分進新的區域；

S4、生成最終區域劃分方案。

2.根據權利要求1所述的基于k-means算法的公共自行車智能調度系統區域劃分方法，其特征在于：S1、采用k-means算法對公共自行車系統內的所有站點根據經緯度分為K個區域具體為：

S101：獲取歷史數據，從自行車租賃系統中導入歷史租還車數據，統計每個站點的租還車總量，選取租還車總量占全年總租還車總量0.25%以上的所有站點作為A類站點；

S102：分別計算S101中每個A類站點到其他A類站點的距離總和，選取K個距離總和最大的站點作為區域劃分算法的初始中心點；

S103：將剩下的非A類站點按照與中心點的距離最小的原則分為K類，即生成初始的K個區域；

S104：重新計算K個區域的聚類中心點，并重復S103操作，將其余站點重新區域分類；

S105：重復S104直至聚類中心點不再發生改變或是劃分的區域內的站點不再發生改變或是各個區域內各站點與中心站點距離的誤差平方和局部最小為止；

S106：生成穩定的K個區域，每個區域內的站點不再改變。

3.根據權利要求1所述的基于k-means算法的公共自行車智能調度系統區域劃分方法，其特征在于S2、計算每一區域的所有站點的調度需求量總和，具體為：

S201：根據自行車系統實時的滿車率和每個站點的租車總數與還車總數的差值計算每個站點的當前調度需求量；

S202：將已經得到的各個站點的調度需求量導入自行車租賃系統，分別統計每個區域的調度需求量之和。

4.根據權利要求1所述的基于k-means算法的公共自行車智能調度系統區域劃分方法，其特征在于S3、將調度需求量總和絕對值大于20的區域的邊緣站點放置一個集合，引進調度需求量這一新的參數，用k-means算法再次對這個集合內的站點劃分進新的區域，具體為：

S301：找出需要修正劃分的區域，即找出S202中調度需求量總和大于20（每輛調度車所能裝載的最大自行車數）的區域，若滿足條件的區域個數為0或者1，則完成了區域劃分，若滿足條件的區域個數大于1，則需要修正區域劃分；

S302：將調度需求量最大的區域作為起始修正區域，將其邊緣站點以及相鄰區域的邊緣站點放置一個集合中，通過計算這些邊緣站點與所有區域中心點的距離以及調度需求量的修正值的和，將這些邊緣站點重新分配至不同的區域內；

S303：計算新生成的該初始修正區域內所有站點的調度需求量之后，若需求量小于20，則修正成功，生成穩定的區域；

S304：重復S302、S303所述步驟，調整其余需要修正的區域，直至所有區域的調度需求量都小于20為止；

S305：若有區域無法通過邊緣站點的調整達到調度需求量小于20的條件，則盡可能多的滿足其余站點的調度需求量趨向于0。

5.生成最終區域劃分方案。