基于区间弱耦合度的公共自行车站点调度区域划分方法

摘要

本发明公开了一种基于区间弱耦合度的公共自行车站点调度区域划分方法。本发明首先获取空间距离数据与表示站点间关系的自行车借还数据，然后在两者结合时对rij进行归一化处理，将借还关系作为权重结合到距离矩阵中；再将代表两个站点之间借还关系的wij与表示站点间距离的dij融合，计算两个站点间的相似度sij；其次使用AP聚类算法对矩阵Sim进行求解，得到弱耦合度的区域划分；区域之间的调度取决于这两个区域之间耦合度的大小；而为了节省调度的成本，减少区域间调度的关键就是减少耦合度；因此，用耦合度目标函数R来衡量整个调度区域划分方案的合理性。本发明使得调度区域可以维持内部自行车的借还平衡，调度车区域内部调度效率提高，区域间调度工作量降低。

说明书

技术领域

本发明属于城市智能交通体系中公共自行车系统领域，涉及一种 基于区间弱耦合度的公共自行车站点调度区域划分方法，从而保证区 间弱耦合、区内强耦合的站点聚类方法。为保证分区效果达到最优， 同时考虑了站点间的距离联系与自行车租借的逻辑联系。

背景技术

城市规模的扩大与人口的增长使得城市交通压力剧增。由此产生 的废气排放、环境污染等问题越来越突出。公共自行车因具有无污染、 机动性强等优点，可以有效地缓解城市交通压力，减少二氧化碳排放， 改善城市环境，已经成为政府倡导和市民认可的交通出行方式。然而， 城市公共自行车租赁系统正处于起步阶段，目前存在的一个比较关键 性的问题是，自行车站点的分布并未根据市民的出行规律进行布局， 在站点位置的选择上缺少一定的科学分析，从而导致某些站点在某些 时间段会出现无自行车可借、无空位可还以及调度车无法及时集中地 进行自行车调度。

目前的调度区域由于面积大、站点相似性小、区域之间跨度较大、 调度路线复杂等原因，造成调度效率低下、调度成本过大等问题。因 此，需要对调度区域重新分割，划分出更合理和集中的区域进行调度， 从而提高效率，降低成本。同时，在划分区域时，应以空间距离为基 础，结合市民使用自行车的出行规律，进行科学合理的区域划分。

目前，国内外在此领域的研究较少，大部分的研究是物流领域的 单个站点布局，虽然与多个自行车站点的群体聚类有所差异，但在某 些划分方法的研究上还是有一定借鉴。在这些研究中，提出的主要方 法包括：α-cost模型，最小成本模型，最大被使用模型，带权k路 聚类算法，数值型数据与类别型数据混合聚类算法等。这些方法的研 究对象都属于个体功能比较集中，数量比较少的连锁企业或是物流仓 库，对于布局需要相对密集并且个体之间的联系比较复杂的公共自行 车站点来说，这些方法并不是很适合。

发明内容

本发明的目的是为了对城市公共自行车站点的调度区域重新划分， 提供一种基于区间弱耦合度的公共自行车站点调度区域划分方法。使 区域内部的站点相似性最大，而区域间耦合度达到最小，从而有效地 平衡区域之间的资源配置，提高公共自行车调度效率。

本发明的方法的具体步骤如下：

步骤(1).设N{N₁,N₂,N₃…N_n}为所有公共自行车租赁站点的集合； M{M₁,M₂,M₃….M_m}为要划分的调度区域集合；d_ij为任意两个不同站点i 和站点j之间的空间距离，其中i，j∈n；根据欧式距离的计算公式：

$d_{ij}=\sqrt{{(d_{ix}+d_{iy})}^2+{(d_{jx}+d_{jy})}^2}$

计算出任意两个站点之间的距离d_ij，对全部自行车站点建立空间 距离矩阵Dis:

$Dis=\left(\begin{array}{ccccc}{d}_{11}& d_{12}& d_{13}& ...& d_{1n}\\ d_{21}& d_{22}& d_{23}& ...& d_{2n}\\ d_{31}& d_{32}& d_{33}& ...& d_{3n}\\ ...& ...& ...& ...& ...\\ d_{n1}& d_{n1}& d_{n1}& ...& d_{nn}\end{array}\right)$

步骤(2).用r_ij表示站点i和站点j之间的自行车借/还量，即从 站点i租借归还至站点j的借还量和从站点j租借归还至站点i的借 还量总和，计算r_ij的值然后构建自行车借还矩阵Rel:

$\mathrm{Re}l=\left(\begin{array}{ccccc}{r}_{11}& r_{12}& r_{13}& ...& r_{1n}\\ r_{21}& r_{22}& r_{23}& ...& r_{2n}\\ r_{31}& r_{32}& r_{33}& ...& r_{3n}\\ ...& ...& ...& ...& ...\\ r_{n1}& r_{n1}& r_{n1}& ...& r_{nn}\end{array}\right)$

步骤(3).在将空间距离数据与表示站点间关系的自行车借还数据 结合时，需要对r_ij进行归一化处理，将借还关系作为权重结合到距离矩 阵中；因此根据如下公式将数据归一化；

$w_{ij}=1-\frac{r_{ij}-r_{min}}{r_{max}-r_{min}}$

其中，r_max表示借还矩阵Rel中的最大元素值，r_min表示借还矩阵Rel 中的最小元素值；

空间距离矩阵Dis中的d_ij越大表示越不相似，越小表示越相似；站 点i和站点j之间的借还量r_ij越大则权重w_ij值越小；如果w_ij越大，则 说明这两个站点之间的租还关系越不频繁，即在这两个站点间使用自 行车的市民越少；

步骤(4).将代表两个站点之间借还关系的w_ij与表示站点间距离 的d_ij融合，计算两个站点间的相似度s_ij，计算公式为：

s_ij＝w_ij×d_ij

s_ij值越大表示两个站点间越不相似；计算所有站点间的s_ij值得到 矩阵Sim：

$Sim=\left(\begin{array}{ccccc}{w}_{11}\times d_{11}& w_{12}\times d_{12}& w_{13}\times d_{13}& ...& w_{1n}\times d_{1n}\\ w_{21}\times d_{21}& w_{22}\times d_{22}& w_{23}\times d_{23}& ...& w_{2n}\times d_{2n}\\ w_{31}\times d_{31}& w_{32}\times d_{32}& w_{33}\times d_{33}& ...& w_{3n}\times d_{3n}\\ ...& ...& ...& ...& ...\\ w_{n1}\times d_{n1}& w_{n2}\times d_{n2}& w_{n3}\times d_{n3}& ...& w_{nn}\times d_{nn}\end{array}\right)$

步骤(5).使用AP聚类算法对矩阵Sim进行求解，得到弱耦合度 的区域划分；

步骤(6).得到初步的区域划分结果后，区域之间的调度取决于 这两个区域之间耦合度的大小；而为了节省调度的成本，减少区域间 调度的关键就是减少耦合度；因此，用耦合度目标函数R来衡量整个 调度区域划分方案的合理性：

$R=\frac{\underset{p=1}{\overset{m}{\Sigma }}\underset{q=1}{\overset{m}{\Sigma }}{Q}_{MpMq}}{T\times m}\times 100\%(p\ne q)$

$T=\underset{i=1}{\overset{n}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}{r}_{ij}$

其中，Q表示任意两个调度区域之间的自行车借还量之和，T表示 所有站点之间的借还量总和；m表示划分的区域总数；R值表示m个区 域之间平均耦合度的大小；结果证明使用该方法能够保证划分区域之 间耦合度最小，与其他方法得出的划分方案相比，各区域之间的借还 关系最小。

本发明有益效果如下：

本发明根据用户租车记录数据，将站点之间的空间距离，与用户 使用自行车产生的站点之间借还关系数据相结合，使用AP聚类算法对 全部城市公共自行车站点进行区域划分，保证个区域之间耦合度最低。 从而实现了以下目标：

有效避免了分区中不符合实际的现象，如某一区域跨江湖、山地 景区等。各调度区域可以维持内部自行车的借还平衡，调度车区域内 部调度效率提高，区域间调度工作量降低。

附图说明

图1站点间借还关系示意图。

图2站点间距离关系示意图。

具体的实施方式

下面结合附图和实施例对本发明作进一步说明。

基于区间弱耦合度的公共自行车站点调度区域划分方法，具体包 括如下步骤：

对公共自行车系统(publicbicyclesystem，PBS)中存储的用 户租车记录数据进行清洗，挖掘出两种主要数据，空间距离数据与借 还关系数据，如图1,2所示具体如下：

步骤(1).设N{N₁,N₂,N₃…N_n}为所有公共自行车租赁站点的集合； M{M₁,M₂,M₃….M_m}为要划分的调度区域集合；d_ij为任意两个不同站点i 和站点j之间的空间距离，其中i，j∈n。根据欧式距离的计算公式：

$d_{ij}=\sqrt{{(d_{ix}+d_{iy})}^2+{(d_{jx}+d_{jy})}^2}$

计算出任意两个站点之间的距离d_ij，对全部自行车站点建立空间距 离矩阵Dis:

$Dis=\left(\begin{array}{ccccc}{d}_{11}& d_{12}& d_{13}& ...& d_{1n}\\ d_{21}& d_{22}& d_{23}& ...& d_{2n}\\ d_{31}& d_{32}& d_{33}& ...& d_{3n}\\ ...& ...& ...& ...& ...\\ d_{n1}& d_{n1}& d_{n1}& ...& d_{nn}\end{array}\right)$

步骤(2)用r_ij表示站点i和站点j之间的自行车借/还量，即从站 点i租借归还至站点j的借还量和从站点j租借归还至站点i的借还 量总和，计算r_ij的值然后构建自行车借还矩阵Rel:

$\mathrm{Re}l=\left(\begin{array}{ccccc}{r}_{11}& r_{12}& r_{13}& ...& r_{1n}\\ r_{21}& r_{22}& r_{23}& ...& r_{2n}\\ r_{31}& r_{32}& r_{33}& ...& r_{3n}\\ ...& ...& ...& ...& ...\\ r_{n1}& r_{n1}& r_{n1}& ...& r_{nn}\end{array}\right)$

步骤(3)在将空间距离数据与表示站点间关系的自行车借还数据 结合时，需要对r_ij进行归一化处理，将借还关系作为权重结合到距离矩 阵中。因此根据如下公式将数据归一化。

$w_{ij}=1-\frac{r_{ij}-r_{min}}{r_{max}-r_{min}}$

其中，r_max表示借还矩阵Rel中的最大元素值，r_min表示借还矩阵Rel 中的最小元素值。

空间距离矩阵Dis中的d_ij越大表示越不相似，越小表示越相似。站 点i和站点j之间的借还量r_ij越大则权重w_ij值越小。如果w_ij越大，则 说明这两个站点之间的租还关系越不频繁，即在这两个站点间使用自 行车的市民越少。

步骤(4)将代表两个站点之间借还关系的w_ij与表示站点间距离的 d_ij融合，计算两个站点间的相似度s_ij，计算公式为：

s_ij＝w_ij×d_ij

s_ij值越大表示两个站点间越不相似。计算所有站点间的s_ij值得到 矩阵Sim：

$Sim=\left(\begin{array}{ccccc}{w}_{11}\times d_{11}& w_{12}\times d_{12}& w_{13}\times d_{13}& ...& w_{1n}\times d_{1n}\\ w_{21}\times d_{21}& w_{22}\times d_{22}& w_{23}\times d_{23}& ...& w_{2n}\times d_{2n}\\ w_{31}\times d_{31}& w_{32}\times d_{32}& w_{33}\times d_{33}& ...& w_{3n}\times d_{3n}\\ ...& ...& ...& ...& ...\\ w_{n1}\times d_{n1}& w_{n2}\times d_{n2}& w_{n3}\times d_{n3}& ...& w_{nn}\times d_{nn}\end{array}\right)$

步骤(5)使用AffinityPropagation(AP，吸引子传播算法)聚 类算法对矩阵Sim进行求解，得到弱耦合度的区域划分。AP算法中各个 数据点之间通过两种类型的消息进行传递：Responsibility和 Availability。res(i,k)表示从点i发送到候选聚类中心k的数值消 息，该值是评判k点是否适合作为i点的聚类中心的依据。ava(i,k) 表示从候选聚类中心k发送到i的数值消息，该值是评判i点是否选 择k点作为其聚类中心的依据。因此，res(i,k)和ava(i,k)两个值越 大，则k点作为聚类中心的可能性就越大，同时，点i也就具有较大 的可能性隶属于以k作为聚类中心的类。使用AP算法得到可以使耦合 度R值达到最小的区域划分方案，每一个划分的区域内站点数量合理， 区域面积与站点数量相对平衡，可保证调动工作基本一致，而区域之 间的站点关联也会比较低，从而保证区域间的弱耦合度。另外，每个 区域都是空间独立的，并不会出现跨河流或者山地的问题；具体工作 流程如下：

Step1:计算N个数据点之间的相似度s(i,k)，构造相似度矩阵 S,由于该相似度采用欧式距离作为计量，故数值取负，值越大即相似 度越大。

Step2:初始化参考度的值，给定迭代次数N。

Step3:计算res的值:

res(i,k)＝s(i,k)-max{ava(i,k')+s(i,k')},k≠k'

Step4:计算ava的值:

$ava(i,k)=min\{0,res(k,k)+\Sigma max\{0,res(i^{\prime },k)\left\}\right\},i^{\prime }\notin \{i,k\}$

ava(k,k)＝∑max{0,res(i',k)},i'≠k

Step5:根据res(k，k)+ava(k，k)的值决定该点是否作为聚类中 心。

Step6:当聚类中心连续N次不改变时终止计算。

步骤(6)得到初步的区域划分结果后，区域之间的调度取决于这 两个区域之间耦合度的大小。而为了节省调度的成本，减少区域间调 度的关键就是减少耦合度。因此，用耦合度目标函数R来衡量整个调 度区域划分方案的合理性：

$R=\frac{\underset{p=1}{\overset{m}{\Sigma }}\underset{q=1}{\overset{m}{\Sigma }}{Q}_{MpMq}}{T\times m}\times 100\%(p\ne q)$

$T=\underset{i=1}{\overset{n}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}{r}_{ij}$

其中，Q表示任意两个调度区域之间的自行车借还量之和，T表示 所有站点之间的借还量总和。m表示划分的区域总数。R值表示m个区 域之间平均耦合度的大小。结果证明使用该方法可以保证划分区域之 间耦合度最小，与其他方法得出的划分方案相比，各区域之间的借还 关系最小。