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

有效

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

1.一種基于圖論的公共自行車調度區域智能劃分方法，其特征在于，此方法包括如下步驟：

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

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

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

步驟3：剪枝處理

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

步驟4：繪制區域連通圖

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

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

步驟6：租賃點分級

根據租賃點之間的關聯關系計算它們之間的連接度，再根據租賃點之間的車輛流動信息計算日均車輛流量，依此得到租賃點的總度，按照租賃點的總度值大小確定租賃點的等級。

2.根據權利要求1所述的一種基于圖論的公共自行車調度區域智能劃分方法，其特征在于，所述步驟1中，根據租賃點的實際距離，將道路路況難度系數和租賃點的關聯度作為調整因子，得到租賃點之間的道路廣義距離C_ij如下：

C_ij=L_ij×K_ij×R_ij???????（1）

其中，L_ij代表道路實際距離；

K_ij代表租車點i到租車點j的路況難度，是指調度車輛行走的難易程度，可以對道路實際距離的修正；

R_ij代表租車點i到租車點j之間的關聯度，是指節點之間的關聯關系，也可以對道路實際距離進行修正：

其中，n_ij記為從租車點i借出且歸還到j的車輛數，n_i出記為從i點借出的總車輛數，n_i入記為從i點歸還的總車輛數。

3.根據權利要求1所述的一種基于圖論的公共自行車調度區域智能劃分方法，其特征在于，所述步驟3的具體處理過程為：將廣義距離矩陣C中每個分量的值大于或等于閾值r的租車點間之間的廣義距離值C_ij設為無窮大，表示這兩個租車點沒有關聯；分量值小于閾值r的保持不變，表示租車點存在關聯，即

當某個C_ij≥r,則C_ij=∞，即表示這兩個租車點之間道路不通。

4.根據權利要求1至3之一所述的一種基于圖論的公共自行車調度區域智能劃分方法，其特征在于，所述步驟6租賃點分級具體方法包括：

a)計算租賃點的關聯度d：租賃點與其它租賃點有直接的車輛流的，則認為它們之間存在關聯，一個租賃點與其它租賃點有關聯關系的總數稱為租賃點的關聯度d；

b)計算租賃點日均車輛流量t：計算每個租賃點每天借出和還入的車輛流量的平均值，根據運營數據統計每天的借出的車輛數和還入的車輛數，計算出租賃點多天的車輛流量的平均值：

這里n_i入為租賃點每天還入的車輛數，n_i入為租賃點每天借出的車輛數，N為統計的天數；

c)計算租賃點的總度D：租賃點的總度為租賃點的連接度與其日車輛流動均值的乘積D=d×t；

d)確定租賃點的等級：

將同一區域中的租賃點按照它們的總度值排序，按照u%、v%、w%的原則劃分為三個區間，u+v+w=100；設區域的租賃點總數為P，則區間的租賃點為該區域的一級租賃點，區間的租賃點為該區域的二級租賃點，區間的租賃點為該區域的普通租賃點。