[發明專利]基于聚類中心修正的定制公交合乘站點生成方法

有效

• 申請號: 201810348137.4
• 申請日: 2018-04-18
• 公開（公告）號: CN108734337B
• 公開（公告）日: 2022-03-18
• 發明（設計）人: 閆學東;李云偉;邵雯;劉鳳
• 申請（專利權）人: 北京交通大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q50/30;G06V10/762;G06K9/62
• 代理公司: 北京市商泰律師事務所 11255
• 代理人: 黃曉軍

1.一種基于聚類中心修正的定制公交合乘站點生成方法，其特征在于，包括：

步驟1：利用層次聚類法對乘客預約需求點進行分類，確定定制公交最佳站點的個數；

步驟2：根據所述最佳站點個數及需求點的空間坐標，構造乘客需求集合和樣本特征向量集合，并獲取初始聚類合乘站點集；

步驟3：對所述初始聚類合乘站點集中不與備選合乘站點重合的初始聚類中心，進行修正及聚類操作，使聚類中心落在路網上，得到聚類合乘站點；

步驟4：通過更新的價值函數值，對所述聚類合乘站點的生成結果進行判斷；

所述的根據最佳站點個數及需求點的空間坐標，構造乘客需求集合和樣本特征向量集合，并獲取初始聚類合乘站點集，包括：

步驟2.1：構造乘客需求集合X為：

X＝{x₁,x₂,...,x_n}， (1)

其中，n為需求個數；

所述乘客需求集合中的每一個需求x_i的樣本特征向量為：

(x_i1,x_i2,...,x_im)^T， (2)

其中，m為分類研究的指標個數，在需求點空間上進行聚集，取m＝2；

步驟2.2：利用模糊c均值聚類法，獲取初始聚類合乘站點集；

所述的利用模糊c均值聚類法，獲取初始聚類合乘站點集，包括：

步驟2.2.1：定義模糊c空間，得到c×n的矩陣U，用值在[0,1]間的隨機數初始化隸屬矩陣U，使其滿足下式：

步驟2.2.2：構造聚類合乘站點坐標集合Y：

Y＝{(x,y)|(x,y)∈S}， (4)

其中，S表示路網中的備選合乘站點集，S為路網節點及路段中能夠作為站點的中間點的總和；

初始化Y，令

步驟2.2.3：將所述矩陣U代入下式：

其中，p為一個加權指數，且p∈(1,∞)；

得出c個合乘站點的初始聚類中心，同時構造臨時聚類合乘站點為：

C_L＝{c_i|i＝1,...,c}，Card(C_L)＝c， (6)

其中，C_L即所述初始聚類合乘站點集；

所述的對初始聚類合乘站點集中不與備選合乘站點重合的初始聚類中心，進行修正及聚類操作，使聚類中心落在路網上，得到聚類合乘站點，包括：

步驟3.1：重復判斷操作，直至

步驟3.2：所述判斷操作為：

若c_i∈Y，則重新獲取所述初始聚類合乘站點集，若不成立，則判斷聚類中心c_i的位置，生成對應的備選聚類站點集合C_i；

步驟3.3：令C_L＝C_L\{c_i}，并對所述備選聚類站點集合C_i進行判斷，若C_i為空集，將c_i存入Y中，返回步驟3.1進行所述重復判斷操作；若返回步驟2.2，利用模糊c均值聚類法獲取所述初始聚類合乘站點；否則，將C_i中的元素依次取出并記作a，則當前聚類合乘站點集Y'為：

Y'＝{Y,a,C_L}， (7)

計算價值函數值的公式如下：

其中，d_ij表示聚類中心i與需求點j的歐式距離；

若選擇所述C_i中使價值函數值最小的點作為聚類站點存入Y，否則，令C_i'＝C_i-C_i∩Y，選擇C_i'中使價值函數值最小的點作為聚類站點存入Y，并記對應的價值函數值為F；

步驟3.4：按照式(10)、(11)更新U矩陣的i+1至c行，返回步驟3.1；

所述的生成對應的備選聚類站點集合C_i，包括：

設UNIT為路網節點能構成的最小封閉多邊形，為最小路網單元；

步驟3.2.1：若生成的聚類中心c_i位于路網單元UNIT內，則C_i為該單元各邊所覆蓋的所有S中的點構成的集合，所有S中的點包括頂點；

步驟3.2.2：若生成的聚類中心c_i位于路網上，則分別選擇該路網上兩側距離c_i最近的S中的點作為c_i點的備選聚類站點，此時C_i為所選擇的兩個站點構成集合；

步驟3.2.3：若生成的聚類中心c_i與路網單元UNIT各邊所覆蓋的S中的點重合，則S中的點包括頂點。