基于复杂网络的公共自行车调度区域划分方法研究

卢文跃，刘彦斌

（中电海康集团有限公司，浙江 杭州 310012）

0 引言

随着城市规模的扩大，交通拥堵状况日益严重。作为解决“最后一公里”难题的公共自行车系统（Public Bicycle System，PBS）能够缓解城市道路交通的压力，减少污染物的排放。随着公共自行车系统规模不断扩大以及共享单车的出现，公共自行车系统的服务要求也越来越高，但用车高峰时段仍常会出现部分租赁点无车可借或者车辆无法归还的现象。“借车难、还车难”已经成为了公共自行车运营公司亟待解决的问题。

目前有关公共自行车运营系统的研究主要集中在租赁点选址、网点规模优化、区域划分及调度等方面。租赁点选址和网点规模研究[1~3]主要是基于周边居民人口及对应的出行需求进行相应测算。考虑到租赁点的建设成本及工程复杂度，租赁点一旦建成基本不会变动，而自行车调度灵活性较高，基本每天都需要相应的调度实现车辆的再平衡，且实现效果较为明显。

对于自行车调度，国内外学者对其进行了大量的研究。如Kadri[4]等人通过集成遗传算法、贪婪搜索算法、局部搜索算法和分支定界算法来确定自行车租赁点的调度路径。Battarra[5]等人提出了一种基于整数规划公式的以租赁点调度次序成本最低的精确算法，并成功运用到多达60个租赁点的实例中。Benjamin[6]等人使用马尔科夫决策过程方法，开发了一个决策支持工具，用以确定调度站点的优先级及相应的调度需求量。张建国[7]等人从成本最小化和租赁点满意度最大化目标出发，在平峰时段和高峰时段分别建立车辆调配的路径优化模型，并用蚁群算法求解出了不同时段对应的车辆调配路径。以上方法大都缺少对自行车调度区域划分的研究，从而导致算法的求解周期长、调度实时性较差、调度路径过长，且无法适用于大型的公共自行车系统。

目前针对公共自行车调度区域划分的相关研究并不多。申兴发[8]等人采用LDA模型和K-means聚类算法对租赁点进行聚类和功能识别，并用POI（Point of Interest）数据验证结果的有效性，但未涉及调度区域的划分。张晶等[9]人通过数据分析估算初始中心点进行第一次K-means聚类，然后引入调度需求量进行二次K-means聚类调整得到最终的区域调度划分结果，该方法主要考虑了空间距离及调度需要量等影响因素，但忽略了车辆潮汐、站点流通性等因素的影响，无法满足跨区域的调度需求；董红召等[10]人则根据公共自行车租赁点间的自流动性，采用关联规则对强相关性租赁点进行聚类划分并形成划分方案，该方法的缺点在于只考虑了部分租赁点间的流动相关性，且相关性阈值的确定较为困难。

现有方法往往在区域划分中较少考虑租赁点间的流动相关性。考虑到公共自行车在租赁点间的流通有其特定的规律，本文拟通过引入模块度运用层次聚类算法将具有流通相关性租赁点划入同一区域从而尽可能地避免跨区域的长距离调度，减少资源浪费。基于此，本文首先对调度区域进行自然小区的划分；然后，基于小区间的流动性采用基于模块度的层次聚类算法，获得一次聚类结果；最后基于属性标定合成二次聚类结果，形成公共自行车的调度区域划分方案。

1 基于复杂网络的调度区域划分模型

复杂网络（Complex Network）是指具有自组织、自相似、吸引子、小世界、无标度中部分或全部性质的网络，其具有小世界特性、无标度特性以及社团结构特性。

1.1 模块度

复杂网络中的社团发现用于发掘复杂网络中的社团结构，社团内部的连接较为紧密，而社团之间的连接较为松散[11]。为了比较各种社团结构发现算法的优劣，Newman等[12]人提出了模块度的概念，用以表征复杂网络在社区划分下与随机网络的差异。模块度为：

式中，eij表示社团i与社团j之间连接边数占网络总连接边数的比例；Tre是矩阵e的迹；‖e2‖表示矩阵e2的和范数。模块度Q表示为复杂网络中社团内部的连边所占之比例与随机连接情况下社团内部连边所占比例之期望值的差值。对于无向加权网络[10]，对应的表达式为：

顶点i和j之间边的权重值；Ci表示顶点i所在的社团，当顶点i和顶点j在同一社团中时，δ（Ci，Cj）=1，否则δ（Ci，Cj）=0。

基于模块度的优化算法主要有GN算法[14]、FN算法[14]、CNM算法、BGLL算法[15]。其中BGLL算法是一种重叠社团发现算法，算法两层迭代，外层的迭代是自下而上的凝聚法，内层的迭代是凝聚法加上交换策略，避免了单纯凝聚方法的缺点。相较于其他方法，BGLL算法复杂度更低，能在短时间消耗下处理上千万的复杂网络，同时还能保持良好的社团划分效果。因此，本文将选择拓展后的BGLL算法来优化模块度。

1.2 PBS模型定义

公共自行车系统（Public Bicycle System，PBS）是以租赁点为节点的网络拓扑结构，租赁点间自行车的流通量表示了网络节点的边的权重值，因此可用复杂网络的思想来研究公共自行车系统租赁点的社团结构。同时，公共自行车在租赁点间的流通存在潮汐现象，应用社团划分可将具有流通相关性的租赁点划分在同一社团，使得社团内部的租赁点间的流通相关性较强而社团间的流通相关性较弱。为了简化和描述算法，这里给出城市公共自行车系统相关概念[13]。

公共自行车租赁点拓扑网络可表示为G=（V，E）。u，v表示为V中的两个租赁点，三元组（u，v，T）表示租赁点u，v之间存在有向连接关系。其中T表示在指定时间内从租赁点u到租赁点v之间的自行车流通量。鉴于公共自行车在租赁点间流动是双向的，公共自行车租赁点网络是一个有向加权图，结合复杂网络中模块度的定义，得出公共自行车网络的模块度为：

式中，Q为公共自行车网络的模块度；u，v分别表示u节点和v节点；表示在时间段[t1，t2]内从节点u到节点v公共自行车流通量；表示在时间段[t1，t2]内整个PBS中的自行车的流通量；δ（Cu，Cv）为克罗内克函数，若u节点与v节点在同一集合内，则克罗内克函数的值为1，否则值为0。

BGLL算法主要应用于无向加权网络中，此处对其进行了拓展（后边统一称为层次贪婪算法），可计算出租赁点网络在节点调整时产生的相对增益：

式中，ΔQ′表示p节点转移集合后产生的模块度的相对增益；为p节点与所要转移的集合间的公共自行车流通量之和；表示所要转移的集合内所有节点的公共自行车归还量总和；kpo表示p节点的公共自行车的借出量；kpi表示p节点的公共自行车的归还量；表示所要转移的集合内所有节点的公共自行车借出量之和；W为整个公共自行车系统中的公共自行车流通量。上述各统计量均为时间段[t1，t2]内的统计量。

由层次贪婪算法划分的公共自行车租赁点区域能在区域内部达到一定的自平衡状态，可通过定义公共自行车系统的不平衡度模型来验证其自平衡特性，其关键参数包括：

（1）租赁点不平衡度[15]Hj（τ）为在时间段τ内，租赁点借出的公共自行车数量与归还的公共自行车数量的差值。

（2）区域不平衡度Hα（τ）为在时间τ内，区域α内所有租赁点不平衡度的总和。

2 模型的算法实现

如图1所示是基于复杂网络的调度区域划分流程图。将自行车租赁点划分自然小区作为基本节点，通过层次贪婪算法进行第一次聚类，结合地理位置、租赁点数量、调度需求量进行二次聚类，形成调度区域方案，具体步骤如下。

图1 基于复杂网络的调度区域划分流程图Figure 1 Division of scheduling area based on complex network

①站点OD量的计算。用户在使用公共自行车作为出行工具时，一次完整的交易包括在起始站点的刷卡借车以及终止站点的刷卡还车。在自行车交易表中记录的关键字段包括起始站点u、租车时间、归还站点v、归还时间等，站点OD量的计算即是对于所有的租赁点对（u，v），获得其三元组（u，v，T）的值。

②自然小区划分。公共自行车主要通过调度车进行调度，为使最终形成的调度区域符合道路走向，需要事先对站点进行自然小区的划分。城市道路等级分快速路、主干路、次干路、支路四级，对于公共自行车租赁点所在区域，按照道路等级从高到低分割成网格，形成最基本的网格单元即为自然小区。

③自然小区判别。基于所有公共自行车租赁点的经纬度位置进行所归属的自然小区判别，将同一自然小区内的所有公共自行车租赁点合并作为一个节点，同时将各自然小区间的公共自行车流通量作为节点间的公共自行车流通量，生成自然小区节点对（p，q）以及三元组（p，q，T）。

④第一次聚类。构造以自然小区为节点的复杂网络，以模块度为目标函数，通过层次贪婪算法进行节点的聚类划分。以每个小区作为单独节点，归入不同的集合中，遍历节点并将节点归入到相邻集合中前后的相对增益最大且大于0的集合中，计算完所有节点，再将同一集合的各节点合并为新的节点并计算新节点间的公共自行车流通量，重复以上过程直到整个公共自行车网络的模块度不发生变化。对应的具体步骤如下，可得到对应的第一次聚类划分结果。

输 入：三元组D={（p1，q1，T1），（p2，q2，T2），...，（pm，qm，Tm）}；

过程：函数FirstCluster（D）

1：计算所有节点组成网络的模块度Q

2：while模块度Q增大do

3：for每一个节点i do

4：将节点i归入到相邻节点所在集合

5：计算所有归入前后产生的相对增益（ΔQ′1，ΔQ′2LΔQ′n）

6：for每一个相对增益ΔQ′jdo

7：if相对增益ΔQ′j大于0

8：获取最大的相对增益ΔQ′j，并将节点i归入该节点所在集合

9：else

10：节点i保留在原集合中

11：end if

12：end for

13：end for

14：将同一集合的节点合并为新的节点，并计算新节点间的流通量

15：计算新节点网络的模块度Q

16：end while

输出：每个节点及节点所属集合编号{（p1，C1），（p2，C2），...，（pm，Cm）}

⑤二次聚类。对前一次聚类划分的各个区域进行属性的标定，综合各个聚合区域的地理位置、调度需求量、租赁点的数量属性进行区域合并，使得生成的最后调度区域的各属性值基本平衡，同时其数量与调度中心的数量相一致，即为最后的调度区域划分方案。

3 应用实例

本文以某地区公共自行车系统作为研究对象，其中有效租赁点的数量为457个（有交易数据的租赁点数量）。取2018年10月22日至10月28日的自行车交易数据作为样本数据，经过滤3min以内行程及其他异常数据，得到了近9000条交易记录。图2所示对该区域按照道路网进行划分得到了187个自然小区（后文主要以主城区部分为重点进行说明）。

图2 某地区自然小区划分分布图Figure 2 Distribution map of natural districts in a certain area

针对划分好的自然小区，将自行车租赁点按经纬度位置进行匹配，计算获得各自然小区间的自行车流通量。此处以自然小区作为基本节点，运用层次贪婪算法进行第一次聚类，其模块度的变化如图3所示。由图3可知，模块度由最初的0.2423经过三层的节点遍历最终达到了0.5886（横坐标表示节点成功转移的次数，面板颜色的深浅表示了不同的层，虚线表示每层结束对应的模块度的大小），前两层的模块度变化较大而第三层的模块度基本不变。图4a）表示了第一次聚类的分析结果，可以看到该地区主城区部分被分为了7个区域，对应了不同的颜色，黑色的自然小区表示该区域内无自行车租赁点。对于聚类得到的大区域的“空洞”部分，可按就近原则将其归入到对应的区域中，如3区域的方框部分的自然小区可归入到3区域中，对应的结果如图4b）所示。对于同区域内的租赁点之间流通相关性较大，而区域间的租赁点间的流通相关性较小，因此区域内部的租赁点的自行车数量能达到一定的自平衡状态。

图3 模块度的变化曲线Figure 3 Variation curve of modularity

图4 第一次聚类划分结果图Figure 4 Results of the first clustering partition

根据第一次聚类划分结果，对各个区域的属性特征进行标定，根据每个区域的地理位置、租赁点数量以及调度需求量进行二次聚类。对应7个区域的属性情况如表1所示。可以看出，区域1和区域6的租赁点数量较少，在地理位置是相邻的，且区域1对应的调度需求量为9而区域6的调度需求量为-20，可进一步实现平衡，因此可对其进行合并。同理也可以对区域2和区域3进行合并，最终将所有区域划分为5个区域，如图5所示。划分结果以区域5为中心，其他4个区域分布于东南西北四个方向。区域5的租赁点最为集中，主要对应了商业区及住宅区；区域3则以景区为主；区域4和区域1则主要以产业园区等工作区域为主；区域7则主要为郊区。表2展示了结果区域的租赁点数量以及区域不平衡度。区域不平衡度需要通过跨区域调度来进行平衡，而表中所示所有区域在一周产生的不平衡度都远小于租赁点数量，说明区域内部达到了较好的自平衡状态且无需进行短期的跨区域调度。因此，相较于传统的依据经验的区域划分以及运用K-means聚类等方法并未考虑区域间流通关系的区域划分，该方法通过研究区域的流通相关性可以尽可能地减少调度车的跨区域调度，同时较好均衡了各区域的属性特征，提高了公共自行车的调度效率。对于跨区域调度，只需以月或者年为单位对区域间自行车数量进行适当调整。

表2 二次聚类划分区域不平衡度Table 2 Regional imbalance degree by secondary clustering

图5 二次聚类结果图Figure 5 Results of the secondary clustering

表1 第一次聚类划分区域的属性标定Table 1 Attribute calibration table of the first clustering division area

4 结 语

本文通过道路网划分获得自然小区，以自然小区为节点应用层次贪婪算法进行第一次聚类，然后结合区域的地理位置、租赁点数量以及调度需求量进行二次聚类得到最终的划分结果，并结合区域不平衡度对区域的自平衡特性进行验证。该方法综合了区域内部自行车的自流动特性以及区域间的租赁点数量和调度需求量的平衡，可减少区域间的跨区域调度，实现区域内的自行车数量的动态自平衡，能够较好地满足城市公共自行车系统调度的功能需求。

本文所述方法选用道路网划分后的自然小区作为基本单元进行聚类，但在实际应用中，基本节点的确定可以更为灵活，可将不可分割的租赁点放置于同一基本单元内。同时道路网划分的精细度也会影响最后的区域划分结果，精细度越高划分效果越好。公共自行车调度区域的划分是研究租赁点车辆再平衡的基础，未来也可以在区域划分的基础上进行公共自行车调度研究。