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

在審

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

本發明屬于公共交通調度領域，提出了一種基于k?means算法的公共自行車智能調度系統區域劃分方法，應用于城市公共自行車智能調度系統的區域劃分，得到需求量絕對值總和最小的區域劃分方案。該方法具體步驟包括：步驟1.使用k?means算法對公共自行車站點進行區域劃分；步驟2.統計各個站點的調度需求量；步驟3.對調度需求量絕對值超過20的區域的邊緣性站點進行二次區域劃分；步驟4.生成最終的區域劃分方案。本發明充分利用了站點的地理位置和站點的調度需求量，考慮了自行車系統的自流動性，對公共自行車調度區域合理劃分，確保更多的區域在區域內不就能滿足調度，減少跨區域調度任務的產生，能提高調度的時效性。

技術領域

本發明屬于公共交通調度領域，具體設計一種基于k-means算法的公共自行車智能調度系統區域劃分方法，涉及二次k-means區域劃分算法的應用與改進，生成合理的調度區域，以使公共自行車調度路徑最短。

背景技術

公共自行車智能調度系統(PBDS)作為公共自行車租賃系統的組成部分，是實現公共自行車各個站點之間正常調度、對自行車系統運行實行集中控制的現代化信息系統，為確保自行車租、還順暢、提高調度效率、實行透明指揮提供了有力的保障。然而現有的公共自行車調度系統調度效率低下，調度路線的規劃不完善，只注重調度任務的完成，沒有考慮到調度的時效性和調度成本的浪費，在一定程度上會制約公共自行車租賃系統的服務質量，諸如：

1、調度時沒有考慮區域劃分的概念，導致調度的路線過長；

2、沒有考慮公共自行車系統具有的自流動性，容易產生過度調度；

3、調度的自行車數量太大，調度車的容量限制沒有考慮進去，導致所需的調度車輛過多。

針對公共自行車調度系統規劃的調度路線可能存在問題，本發明提出一種基于k-means算法的公共自行車智能調度系統區域劃分方法，以使調度的效率提高，縮短調度路徑、降低調度車需求數量減少調度成本。本發明基于2016年重慶市科研創新項目-城市公共自行車智能調度算法的研究(項目編號CYS16171).

發明內容

(一)要解決的技術問題

本發明所要解決的技術問題是提供一種基于k-means算法的公共自行車智能調度系統區域劃分方法，該方法能夠解決目前公共自行車調度系統規劃的調度路線過長，調度需求量過大，造成過度調度，且對調度車需求量過大等問題。從而使自行車系統能順暢無障礙的運行，不會產生租車難還車難問題，是市民提供方便。

(二)技術方案

本發明提供了一種基于k-means算法的公共自行車智能調度系統區域劃分方法，包括以下步驟：

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

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

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

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

優選地，所述步驟S1具體為：

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

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

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