共享单车搬迁策略研究

谢青成

摘要：为满足单车用户的用车需求，对共享单车搬迁策略进行研究，提出两阶段共享单车搬迁策略.离线阶段构建单车停放区域提取模型，采用改进的DBSCAN聚类方法（DistrictPick up Technology，DPT）获取各时段热门用车区域、用车频率与行程结束后的放车区域、放车频率;在线阶段提出搬迁优化模型（RelocationOptimi-zationPlan，OMP），根据当前时段的用车区域，搜索距离其最近的前一时段K近邻放车区域，并结合实时路况为其推荐前K条路况良好的单车搬迁路径。相较于传统的共享单车搬迁策略，在拥堵比例为48%时，OBJ值至少缩小52.4%，AT值至少缩小52.6%。

关键词：共享单车;搬迁策略;DPT算法;搬迁优化模型DOI：10.11907/ejdk.191910开放科学（资源服务）标识码（OSID）：

中图分类号：TP319文献标识码：A 文章编号：1672-7800（2019）010-0147-05

0引言

共享单车属于新型城市公共自行车，传统城市公共自行车系统开始采用固定的租赁站点，以投币为凭证供人们匿名使用。近几年，随着摩拜、OFO等共享单车的广泛使用，在方便人们出行的同时，也引发了诸多问题，如大量共享车随意停放影响了正常交通秩序，且高峰时段用户依然面临无车可用的情况。目前共享单车数量已趋于饱和，基于有限数量的单车资源，要确保满足各时段的用车需求，亟需设计出动态的单车搬迁策略、推荐有效的搬迁路径，这涉及两个问题：①预测各时段的用车需求;②结合实际路况的有效搬迁路径推荐。

针对目前共享单车搬迁所面临的问题，本文构建并实施一个两阶段的共享单车搬迁策略。在离线阶段，提出DPT算法，采用改进的DBSCAN聚类方法（DPT）对各时段的用车点（放车点）聚类，找到各时段用车区域及其用车频率（放车区域及放车频率）;在线阶段，提出搬迁优化模型（OMP）。根据用车区域的位置，搜索K近邻放车区域，并结合实时路况推荐前K条路况良好的单车搬迁路径，从根本上满足实时用车需求，推进绿色智能城市建设。本文主要作如下研究：提出DPT算法，采用改进的DBSCAN聚类DPT算法，提取区别各时段的用车区域和放车区域;提出结合实时交通状况的搬迁优化模型（OMP），以较小路径长度和较短搬迁耗时的方式完成单车搬迁，确保各时段内的单车使用需求得到满足。1

相关工作

1.1用车需求预测

现有用车需求预测大多数聚焦于使用单车历史数据即取车（放车）记录对用车区域需求进行预测，许多学者对此作了研究。米文勇采用非集计模型预测用车需求，并提出了自行车停车位置规划方法;Eoin等研究高峰时段使用情况，通过分析共享单车系统数据，以发现单车的用车需求位置，但该方法仅考虑了高峰时段的用车需求，且工作日和节假日高峰时段未分开考虑;Dimitrios等通过识别单车使用影响因素及共享单车流动模式，进而预测单车用车需求。

1.2放車区域预测

放车区域预测相关研究大多根据历史数据对放车区域进行提取，也有考虑时间、天气等因素，比如Liu等采用区分工作日、节假日的高斯混合模型对固定车站的放车频率进行预测。但目前共享单车的很多站点不固定，其虽然能很好地预测出放车区域的放车次数，但是缺乏各时段放车区域位置预测。对放车点区分工作日、节假日各时段的聚类DPT算法，可以发现各时段的放车区域和放车频率。

1.3搬迁路径推荐

对搬迁路径的研究大部分是通过对用车区域和放车区域的分析进行数学建模。如Liu等运用带约束的K中心聚类（AdaCCKC）算法对用车比例和放车比例进行聚类，将大型多车辆路径问题简化为内部站点集群间的路径选择问题，缺乏实时路况的考虑;FObio等提出一个基于迭代的局部搜索的启发式算法，通过一条最优路径完成所有站点之间的搬迁，但是一天仅搬迁一次，不能满足各时段用车需求;Christian等提出了一个混合整数线性规划方法，但未考虑实时路况，因此搬迁效率较低。

2总体框架

本文构建一个两阶段的共享单车搬迁策略，总体框架如图1所示，整体框架分为离线阶段和在线阶段。在离线阶段，首先对历史轨迹使用地图匹配技术并结合路网数据将有序路段的交点序列映射到真实路段上;然后对轨迹数据进行预处理，包括去除噪声数据，将用车点和放车点的数据分别提取出来，再分别对用车点数据和放车点数据进行分时段基于最小阈值支持的聚类，从而实现各时段用车区域和行程结束放车区域的提取。基于最小阈值支持的聚类，是指用车需求频次和放车频率必须达到一定阈值α才能被视为用车区域和放车区域，聚类技术采用基于密度聚类的DBSCAN聚类，该聚类适于任意形状的轨迹数据聚类且能进一步去噪。在区域提取过程中，使用实时轨迹对其进行增量更新，确保用车区域和放车区域提取的精准性。在线阶段，首先获取当前用车区域的位置信息和所属时段，搜索用车区域的top-K近邻放车区域，同时结合当前时段共享单车轨迹流完成对各路段交通拥塞情况的评测，根据各路径拥堵比例对用车区域与初始提取的top-K近邻放车区域之间的路径进行评测排序，实现top-K单车搬迁路径推荐。

2.1离线阶段

本文使用单车历史轨迹数据提取用车及放车区域，基于DPT算法对提取出的用车点和放车点分别进行聚类，通过使用两个参数r_time和r_spatio分别作为时间维度、空间维度的半径，给定点在E领域内成为核心对象的最小领域点数MinPts，将簇视为一系列由低密度区域（噪声）分割开的高密度连通区域。由于在聚类过程中考虑了空间和时间相似性，使得聚类结果为在某一时段内数据点密度较大的簇，即位于同一簇中的用车点在地理位置和时间纬度上邻近，最终达到某一连续时段内较大的聚类目标。伪代码如算法1所示。

对当前用车区域的K近邻放车区域推荐，即用车区域到放车区域路径长度最短的top-K放车区域推荐，对于一个给定位置P_current、当前时间戳T_current的用车区域而言，搜索与其时空邻近的放车区域，考虑将用车区域当前位置P_current，的簇心S_cen与放车区域之间的最短路径作为用车区域到放车区域的路径，并对每条路径进行评测排序，完成用车区域的K近邻放车区域推荐。

采用Dijkstra算法作为寻路策略，完成对基于起始位置P_start、P_termination的最短路径计算。Dijkstra算法可以找到从一个顶点s到任何其它顶点的最低权重路径，本文采用Dijkstra算法找到离用车区域路径最短的top-K个放车区域，该算法通过距离权值SP找到最短距离路径。

算法1中步骤7-10对每个在列表D中的点搜索离其在时间维度和空间维度上相邻的点，如果相邻点的数量小于MinPts，就把它视为噪声点;步骤11-15是对所有未被访问的相邻点再次搜索时空邻近点，如果相邻的点数量超过MinPts就把这些点归为同一个簇;步骤16-21是重复操作步骤11-15直至每个相邻点都被访问完。

2.2在线阶段

获取区分工作日、节假日中各时段的用车和放车区域集，该部分工作以离线方式处理。在线阶段中，提出了搬迁优化模型（OMP），包括用车区域的K近邻放车区域推荐、实时路况评测和搬迁路径推荐3部分。

2.2.1K近邻放车区域推荐

对当前用车区域的K近邻放车区域推荐，即用车区域到放车区域路径长度最短的top-K放车区域推荐，对于一个给定位置P_current、当前时间戳T_current的用车区域而言，搜索与其时空邻近的放车区域，考虑将用车区域当前位置P_current的簇心S_sen与放车区域之间的最短路径作为用车区域到放车区域的路径，并对每条路径进行评测排序，完成用车区域的K近邻放车区域推荐。

采用Dijkstra算法作为寻路策略，完成对基于起始位置P_start、P_termination的最短路径计算。Dijkstra算法可以找到从一个顶点s到任何其它顶点的最低权重路径，本文采用Dijkstra算法找到离用车区域路径最短的top-K个放车区域，该算法通过距离权值SP找到最短距离路径。

2.2.2买时路况

本文通过基于滑动窗口的轨迹流聚类方法获得各路段基于时间T_current的实时速度，需要对用车区域到搬迁源区域的每条路径进行实时路况评测。将道路交通状况分为3种：速度低于30km/h的将其视为交通拥塞（以红色标记），速度在[30km/h，60km/h]范围内定义为交通缓慢（以黄色标记），速度超过60km/h的定义为交通畅通（以绿色标记）。

2.2.3搬迁路径推荐

每个放车区域到用车区域有众多路径，需要找到交通状况良好的前K条路径。根据拥堵比例评测交通状况，首先需要计算出各路段的速度，采用基于滑动窗口模型的轨迹流聚类关注最近时段到达的车辆行驶轨迹，将其划分成簇以实时提取各簇的移动行为模式，继而实现对各簇所在路段的实时交通状况评测，将交通拥堵和交通缓慢的路段长度和总路径长度进行比例分析，并对所有路径按拥堵比例排序，从而完成到用车区域各K邻近放车区域的搬迁路径推荐。拥堵比例计算如下：

3实验

3.1实验环境及数据集

本文實验采用上海2015年4月共30天的共享单车轨迹数据集，该数据集包含近30000辆共享单车的近5万条GPS轨迹数据。离线阶段首先采用共享单车历史轨迹数据C₁提取用车区域和放车区域，在线阶段采用出租车轨迹数据C₂模拟实时到达轨迹，通过各时段内实时到达的出租车轨迹分析路网交通情况，利用C₁提取各时段内的用车区域和放车区域，并利用C₂对实时交通路况进行评测。实验使用Java语言实现算法编写，并在Windows 7操作系统、机器配置为2.50GHz Intel Core i5处理器和12GB物理内存的PC机上运行。

3.2对比方法

本文提出的DPT算法，是对用车点和放车点进行时空聚类，预测用车和放车频率的方法。采用的对比方法如下：

Multi-Similarity-based Inference（MSI）法考虑天气、温度、风速和时间相似性预测用车需求。其相似性函数是这3个相似性的乘法，而这几个因素的权重没有被研究。

Historical Mean（HM）法是将自行车需求的历史记录作为预测值而不考虑其它因素的需求预测方法。

Muhi-Similarity-Equally-Weighted KNN（MSEWK）方法是对影响需求预测的不同因素采取相同的权值，运用混合高斯算法预测需求。

采用的性能衡量标准是对每个时段用车频率和放车频率预测的平均绝对误差。评测标准表示为MAE，如下：

3.3实验结果

3.3.1用车频率及放车频率预测

本文提出的预测用车频率的DPT算法性能如图2所示。可以看出，多源因素模型（MSI和MSEWK）虽然优于传统单因素统计预测模型（IPPI，HM），但是对用车频率时空聚类的DPT法的错误率低于其它方法。

在放车频率预测上，本文方法优于其它结合多因素预测方法，如图3所示，这充分证明了本文方法的有效性。

3.3.2搬迁优化

搬迁优化模型（OMP）的有效性和高效性如图4所示。在相同路径长度下，交通拥堵比例较小的路段可以明显减少CPU运行时间，总路径越长CPU运行时间越长;用OMP法则随着总搬迁路径长度增加，拥堵比例也越低，但是总路径过长，CPU运行时间也会变长。因此，需要找到总路径长度较小，拥堵比例也较小的搬迁路径。

表1展示了优化后总的搬迁路径长度（Optimal Objec-tives，OBJ）和CPU运行时间（CPU Running All Times，AT）。将本文优化模型与同样是对搬迁优化的NearestNeighbor Insertion Alzorithm（NNIA）和Genetic Algorithm（GA）进行比较可知，本文车辆路径优化策略最优。本文搬迁优化模型（OMP）比NNIA和GA的搬迁总路径长度更小，完成搬迁的CPU运行时间更短。

4结语

为满足不同时段共享单车用车需求并解决单车搬迁效率问题，本文提出了一个两阶段的共享单车搬迁策略框架，该框架能准确预测各时段的用车需求及放车区域，并结合实时路况推荐单车搬迁路径。基于共享单车数据集的实验结果表明，DPT算法能精确预测用车需求、发现放车区域，所提出的搬迁优化模型能有效提升共享单车搬迁效率。在未来工作中，拟结合包括天气、日期、POI数据等提取多源外部特征，对轨迹数据与外部特征进行统一建模，进一步提升单车搬迁策略的有效性。