[發明專利]公共自行車調度區域劃分方法

在審

• 申請號: 201410362468.5
• 申請日: 2014-07-28
• 公開（公告）號: CN104166895A
• 公開（公告）日: 2014-11-26
• 發明（設計）人: 董紅召;吳滿金;史彩霞;劉冬旭;陳寧
• 申請（專利權）人: 浙江工業大學
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06Q30/06
• 代理公司: 杭州天正專利事務所有限公司 33201
• 代理人: 王兵;黃美娟

1.一種城市公共自行車調度區域劃分方法，具體包括：

步驟1.公共自行車系統調度區域聚類劃分

11確定租賃點間的租還關系；

抽取公共自行車OD數據樣本，設D表示由公共自行車系統交易記錄所組成的數據庫，每一條自行車交易記錄由唯一的交易標識和兩個租賃點的項目數據組成；I_i(i＝1,2,…,n)表示第I輛公共自行車在編號為i的租賃點所產生的交易記錄，當I_i∩I_j≠φ時，即表示租賃點i和租賃點j存在租還關系；

12生成關聯集合；

121)計算最小相關性閾值σ_min

對于公共自行車系統租賃點，最小相關性閾值σ_min與數據庫中的總記錄條數n_total、流動自行車總數目n_bike以及小范圍內租賃點數目q_site有關，公式歸納如下：

σmin=ntotal*ρt*nbike*qsite]]>

其中，t為采集的數據的天數，ρ為正常租還交易記錄系數；小范圍內租賃點數量q_site：指生活區、商業區、學校等區域周邊的租賃點數量，設定小范圍內租賃點具有相同屬性；

122)判斷租賃點的關聯度大小；

當I_i∩I_j>σ_min時，即認為具有租還關系的兩租賃點相關性較大，分別劃到同一個集合中，生成關聯集合A_P；合理設定最小相關性閾值σ_min至關重要，過大或過小都會對劃分結果將產生較大的誤差；

123)將關聯集合中的相關租賃點進行聚類劃分；

1231選取K個初始聚類中心；以當前各調度指揮中心實際所在的地理位置為初始聚類中心；

1232計算相關租賃點到聚類中心的最短距離；遍歷所有租賃點，分別計算關聯集合中每個租賃點到K個初始聚類中心的距離；選取K個距離中的最近距離minL_i(i＝1,2,…,n，表示相關租賃點編號)，即為租賃點i到調度中心的最短距離；

1233計算距離閾值；對關聯集合中的租賃點，根據距離屬性進行聚類；其中為所有minL_i之和的平均值，表示距離閾值；當l<l_max時，集合中的元素在地理位置上具有可達性，歸于同一調度區域，同時可避免邊緣點對整體最優性的干擾；

1234重新計算各聚類區域的聚類中心，得到K個聚類調度區域；

步驟2.公共自行車系統調度區域劃分調整

21以整個步驟1聚類劃分的調度區域為基礎，綜合調度區域中的租賃點需求類型、地理位置及調度區域數量等屬性特征，進行調度區域劃分調整；

211租賃點需求類型；一個調度區域中，接受公共自行車調入的租賃點的數量與接受調出的租賃點的數量應大致平衡；

212)地理位置；因河流、鐵路及障礙物等因素影響，距離租賃點最近的調度中心K_i無法對租賃點進行調度服務；因此可將這部分租賃點劃分到除調度中心K_i以外的最近的調度中心K_j中(K_i，K_j表示步驟1中劃分好的不同調度區域)；

213調度區域的數量；調度區域劃分調整后，最終得到的調度區域個數應與原有調度指揮中心個數K相同；

22對于某些無法作其他劃分的租賃點，根據地理上的比鄰原則，即租賃點到聚類區域中心的距離，分別劃入到最近的聚類區域中，構成最終的聚類劃分的結果；

步驟3.生成最終的調度區域劃分方案。