[發明專利]一種基于圖論的公共自行車調度區域智能劃分方法

有效

• 申請號: 201410162000.1
• 申請日: 2014-04-21
• 公開（公告）號: CN103956042A
• 公開（公告）日: 2014-07-30
• 發明（設計）人: 竇萬峰;成先鏡
• 申請（專利權）人: 南京師范大學
• 主分類號: G08G1/00
• 分類號: G08G1/00;G06F19/00
• 代理公司: 南京知識律師事務所 32207
• 代理人: 李媛媛

技術領域

本方法屬于公共交通調度領域，可應用于公共自行車調度區域智能劃分，得到最佳的公共自行車調度區域，提出了一種基于圖論的租賃點聚類和區域劃分方法。

背景技術

優先發展城市公共汽車交通是解決城市交通擁堵問題最有效的方法。但是由于公交的覆蓋率低，公交站點間距離長，發車頻率不確定，換乘不方便等問題給人們的出行帶來了不便，降低了公共出行方式對廣大市民的吸引力。為解決公交車存在的上述問題，延伸公交服務（最后一里路），推行公共自行車與公共交通換乘的模式，吸引更多的小汽車出行者改變出行方式，倡導市民“綠色出行”，并且緩解城市交通擁堵、減少環境污染、節約道路資源。結合城市公共交通的其他手段，公共自行車系統作為城市公交的組成部分承擔著重要的交通任務，其提供的綠色、低碳出行方式有效地彌補了公交、地鐵等的缺陷，極大地方便了市民出行。

然而，隨著公共自行車系統規模逐漸增大、使用頻率逐漸增加，給公共自行車系統的管理和服務也帶來了一系列問題，主要表現在：高峰期時段，某些租賃點的鎖樁呈空位狀態時間過長，用戶借不到車；某些租賃點的鎖樁呈滿位狀態時間過長，用戶還不了車；居民區、辦公區及部分商業區都存在明顯的早晚高峰和方向不均衡現象，導致了車輛調度難度的增加及車輛周轉率的降低。其中，公共自行車“借車難、還車難”問題成為市民使用公共自行車綠色出行過程中的突出問題。

因此，為緩解這種“借車難，還車難”的現狀，提高公共自行車系統的服務水平，有必要對其位置和區域進行分析并采用合理的調度方法對公共自行車進行綜合調度。對現有區域進行合理優化劃分，減少公共自行車系統的調度成本，更好地為出行者提供服務，及時平衡公共自行車在時間和空間上的分布，提高公共自行車的利用率。

發明內容

本發明針對上述出現的“借車難，還車難”現象，提出了一種基于圖論的公共自行車調度區域智能劃分方法，對現有區域進行合理優化劃分，減少公共自行車系統的調度成本，能更好地為出行者提供服務，及時平衡公共自行車在時間和空間上的分布，提高公共自行車的利用率。

圖論算法介紹：

一般幾何上將圖定義為空間一些點和連接這些點的線的集合。圖論中將圖定義為一個偶對G=(V,E)，其中V={x|x∈某個數據對象}，它是頂點的有窮非空集合；E={(x,y)|x,y∈V}，它是頂點之間關系的有窮集合，稱為邊集。若圖中代表邊的頂點對是有序的，則稱該圖為有向圖，反之則稱為無向圖。本文討論的圖是有向有限圖，即頂點數和邊數都是有限的。

圖的關聯矩陣表示的基本思想就是引入兩個數組，一個記錄圖中的各個頂點信息的一維數組，稱為頂點表；另一個是表示圖中各個頂點之間關系的二維數組，稱為關聯矩陣。

V=(V₀,V₁,V₂,…,V_n)，E_ij=(V_i,V_j)(0<=i<=n,0<=j<=n)

在有向帶權圖中，每條邊都具有一個與之相關的具有某種實際意義的數，成為邊的權值。令C_ij是邊E_ij上的權值，該權值的計算基于路況難度、距離、關聯度三個因素，三者加權求和，得到邊的權值。考慮到道路單行限制和租賃點在道路的左右邊布局不同，一般C_ij不同于C_ji，即C_ij≠C_ji。

本發明采用的技術方案如下：

一種基于圖論的公共自行車調度區域智能劃分方法，具體包括如下步驟：

步驟1：根據路況信息和租賃點之間的關聯關系，對租賃點的實際距離進行加權調整得到租賃點之間的道路廣義距離值C_ij；

步驟2：構建廣義距離矩陣C

根據計算的租賃點之間的道路廣義距離值C_ij，構建一個租賃點廣義距離矩陣C，廣義距離矩陣C表示租賃點之間的連接距離，其中每一個分量C_ij為租賃點i和租賃點j之間的道路廣義距離；

步驟3：剪枝處理

給定一個閾值r，對廣義距離矩陣C進行處理，得到由道路廣義距離值C_ij在閾值r以內的值組成的關聯矩陣；

步驟4：繪制區域連通圖

根據剪枝處理之后的結果，繪制關聯矩陣的區域連通圖；

步驟5：重復步驟3-4，直到得到需要的互不關聯的區域；

步驟6：租賃點分級