文摘

汽车共享是一种汽车租赁服务,由消费者租车时间短,通常收取的小时。城市交通的分析大数据的重要性和意义为汽车共享系统确定仓库的位置。出租车OD(叫做)是一个城市交通的典型数据集。的数据量非常大,传统的数据处理应用程序不工作。本文的优化方法确定仓库位置聚类出租车OD点与美联社(亲和力传播)聚类算法已被提出。通过分析AP聚类算法的特点,AP聚类进行了优化基于行政区划分等级。考虑稀疏相似矩阵的出租车OD点,美联社集群已经适应的输入参数。在案例研究中,我们选择OD对来自北京的出租车GPS轨迹数据的信息。仓库的数量和位置取决于集群OD点基于优化AP聚类。我们描述我们的方法的实验结果并与标准进行比较K方法则使用定量和平稳性指标。真实数据集的实验表明,该方法用于确定汽车共享仓库性能优越。

1。介绍

大数据到处存在,提供海量数据集,可以让人们的生活更方便和实现可持续发展1]。大数据通常需要一组与新形式的集成技术,揭示从不同的数据集,复杂的,大规模的2]。在过去的几年中,城市交通数据爆炸,我们已经真正进入了大数据时代交通(3]。这种情况下激励我们做出一些新尝试在城市交通大数据。在本文中,我们提出一种新的尝试,城市交通大数据来确定汽车共享仓库的位置。

汽车共享系统打算提供一个替代模型的汽车租赁,用户被允许使用的车辆收取的时间(4]。这些方面是用来评估汽车共享系统,即城市交通环境、仓库的布局,和租赁模式。对于城市交通环境,直观的大城市是一个不错的选择,因为他们有很高的对公共交通的需求。关于仓库的位置,汽车共享是一个最重要的长期决策由于这样的事实,它已经直接影响质量,效率,服务和成本影响利润和市场竞争力。汽车共享仓库部署基于需求一直是一个巨大的挑战由于缺乏现实的车辆操作数据。因此,确定仓库位置精确的详细研究是必要的。

实现利润最大化的合理分配仓库,应考虑以下三个方面。消费者方面:理想的步行距离是0 - 3公里。如果距离太长,用户愿意租车辆将显著减少。投资回报方面:好仓库的位置将大大提高整体收益。从现有的汽车共享系统,我们知道,汽车共享是绝大多数集中在都市核心;大约95%的成员被发现在这些设置5]。例如,Autolib项目”是一个完整的电动汽车共享服务在巴黎。2016年7月,它提供了超过1000个仓库,可以发现在巴黎步行5分钟内。仓库建设的可行性方面:一般来说,汽车共享仓库应该位于热点,如购物中心、写字楼停车场,交通枢纽。这些网站通常有足够可用的停车位,建筑成本相对较低。总的来说,消费者希望他们可以租车辆尽可能的方便。然而,汽车共享服务提供商希望挣更多的钱,花更少的同时构建仓库。考虑这些因素以一种集成的方式,经常访问地区的出租车是一个不错的选择,也就是说,出租车的热点地区。广泛的流量传感器,城市交通数据容易获得,成为大型规模。有许多方法来发现出租车从出租车GPS轨迹数据热点。然而,并非所有的出租车热点非常适合汽车共享仓库。有可用的停车位建设汽车共享仓库是必要的。起点和终点(OD点)用户的旅行可以从出租车GPS轨迹数据,提取反映交通热点和指示汽车共享的潜在需求。 Based on the above theory, we propose a method to discover the traffic hotpots by clustering taxi OD points and determine the locations of car-sharing depots.

许多聚类算法,不同的聚类算法给出了不同的集群。重要的是要选择一个合适的聚类算法时间成本和性能之间的平衡。最流行的一种聚类算法K则。然而,K则是有效的只有在之前已经知道集群的集群的数量。令人兴奋的是另一个流行的聚类算法,美联社(亲和力传播)聚类算法,可以确定集群自发的数量。不过,美联社的复杂性是不可接受的,特别是在大规模的数据集。改善美联社的计算复杂性,本文提出了一种基于行政区分割的优化方法和相似矩阵的稀疏表示。这项研究的结果表明大规模数据的好处来确定汽车共享仓库的位置。结果可以提供一些指导和建议政府和汽车租赁服务提供商的早期汽车共享系统建设。虽然该研究只使用一个特定的城市为例,该方法和框架也适用于其他城市。

本文主要的贡献在于以下两个方面:(我)我们提出一种新颖的优化方法确定仓库位置聚类大规模OD点与AP算法基于行政区分割。我们提出一种基于密度的方法来优化美联社的参数以及简要介绍AP聚类方法的原理和应用范围为稀疏的相似性矩阵。(2)我们实现大规模数据集实验大约包含九万OD点提取出租车GPS轨迹生成大约12000北京的出租车。我们的方法会产生大约50点适合汽车共享仓库。然后我们评估我们的模型与网络优化的美联社和相似性K则。结果表明,AP有优势K则。所有的实验表明,我们的方法是可行的和有效的在决定汽车共享仓库由集群。

本文的其余部分组织如下。部分2介绍了一些相关的工作地点的仓库和出租车GPS数据。部分3介绍了我们的方法的细节来判断汽车共享仓库的位置。部分4讨论了实验结果和分析结果。结论和未来的工作进行了讨论5。

2。相关的工作

大多数的研究确定汽车的位置处理城市交通大数据仓库。在本节中,我们回顾一些现有的作品。

2.1。确定仓库的位置

城市大数据使高度颗粒和纵向系统,它可以帮助我们更好地理解城市系统和服务(6- - - - - -10]。它可以用于很多领域,如规划和管理城市,和商业。例如,[3)大数据应用于交通流预测。文献[11]提供了一个模型来评估培训时间表从乘客的角度的数据轨道交通线路。文献[12)提出的一项研究对公共电动汽车充电站使用交通大数据。

各种各样的城市交通大数据用于仓库位置的问题。文献[13)提出了一种方法来优化仓库的位置在单向汽车共享系统中车辆库存失衡问题是由三个旅行选择解决方案。文献[14)提出了一种方法来优化自行车分享站的位置和舰队维度和措施所需的自行车搬迁活动在一个常规操作。文献[15开发一个仿真模型,考虑需求可变性和一辆汽车搬迁政策和测试提供的解决方案之前MIP模型。文献[16]分析了汽车共享服务的性能在所有站,估计需求的关键因素,并使用这些驱动程序识别未来仓库的位置。文献[17)确定仓库的位置根据预测汽车的需求。确定候选仓库的基础和前提。然而,它仍然是很难确定候选仓库,以便详细研究是非常必要的。

2.2。分析出租车GPS轨迹数据

出租车GPS轨迹数据是一个重要的和有效的城市交通大数据分析一些关于交通的某些问题。越来越多的研究开始关注近年来出租车GPS数据。有许多工作在分析出租车GPS数据。文献[18)使用出租车GPS数据来分析交通拥堵的变化在北京奥运会。文献[19)提出了一种方法来构造landmarks-nodes图。地标被定义为经常穿越道路段的出租车。他们呈现的是一个方法一天自适应分割成不同的时间部分基于熵之间的旅行时间和方差地标。这引出了一个被估计的分布之间的旅行时间的地标。文献[20.)提出了一种方法来构造一个模型基于大规模的交通密度的出租车旅行,可以用来预测交通条件和估计排放对城市空气质量的影响。文献[21)发展一种方法来识别交通热点出租车GPS数据的基础上,基于集群出租车GPS数据的方法K则算法。然而,最明显的问题K——是,它需要一个输入参数 ,这意味着你必须提前知道有多少交通热点。最重要的是,对仓库的位置问题,更多地关注出租车GPS数据分析是必要的。

3所示。方法

本节重点介绍我们的方法,旨在寻找合适的地点和汽车租赁仓库的数量,同时满足消费者需求和最大限度地减少总成本。假设汽车共享仓库的总需求是未知的,但积极与出租车流动,我们的方法是集群出租车OD点,然后找到热点从连续出租车GPS轨迹,这可能被视为汽车共享仓库的位置。本文的体系结构如图1。该框架包括三个主要组件:过滤的原始数据,聚类OD点,和最后的原型滤波器。详细的过程将在下面几节中介绍。

3.1。过滤的原始数据

过滤效率点从出租车GPS轨迹数据是必要的准备,因为不是所有的旅行都有效。例如,一些错误数据崩溃造成的gps或一些无效的数据不能反映交通流有效的字符。汽车共享仓库的位置是由旅游者的旅游需求。我们只是过滤乘客的旅行的起点和终点在某种程度上反映了旅游需求。和OD点可以从连续GPS轨迹中提取根据触发事件。

每个出租车GPS点是由一组描述六元素:出租车id,触发事件,操作状态、时间、经度和纬度的GPS。“出租车id”车的执照,这是一个为每个出租车惟一标识符。“触发事件”是表示出租车事件的触发状态。当触发器事件= 0,这意味着出租车变成别人的“空载”状态。和1意味着转向“负载”,2表示“强化”,3表示“撤回驻军。”“运行状态”是出租车的运行状态。0表示“空载”,1表示“负载”,2表示“停车”,3表示“打完电话。”“时间”是出租车的当前时间(SGT),格式是“mm-dd-hh-mm-ss”。“经”是出租车的GPS坐标(北纬东经和)。例如,一个数据记录 ,这意味着1143年出租车转向“空载”和当前时间是11月6日12:38:43,北京时间,出租车是位于116.556101°E和39.963646°N。来满足我们的需求,我们需要过滤点触发事件突然跳从1到0或0到1,也就是说,OD点。值得一提的是,所有的OD点是按出生时间。

3.2。集群OD点

为了确定汽车共享仓库的位置,我们做聚类分析在OD点基于AP聚类算法。

3.2.1之上。新偏好在AP聚类

首先,我们回顾标准AP模型(22]。为数据点,成对的输入是一组相似之处 ,在哪里的相似点对点 ,和一组范例的偏好 ,在哪里是选择的偏好作为一个范例。一般来说,偏好设置为相似吗和影响的最终数量确定原型。目标是选择一个子集的数据点作为原型,并将每nonexemplar点分配给相应的范例,以最大化的整体和相似点和他们的范本。有两种类型的数据点之间的消息交换,即责任 和可用性 。首先,可用性值 设置为0和责任的价值观是什么 将输入点之间的相似之处吗和 。美联社的消息的更新计算如下: 在哪里 代表多好点的证据作为的范例 。 反映了如何适当的证据选择作为范例。方程(1)表明,更新 降低了相似 通过删除相应的候选人竞争的范本。方程(2)代表的更新过程 从数据和收集证据是否每个候选人范例将会成为一个很好的范例。

上面的更新规则只需要简单,当地的计算很容易实现,只需要将消息之间交换对点与已知的相似之处。在任何时候在亲和传播,可用性和责任可以组合来识别原型。为点 ,的价值最大化 要么标识点作为一个范例,如果 或标识数据点是点的范例 。

美联社认为所有数据点作为潜在的范本。作为输入一组相似 ,而 由输入的偏好。在这篇文章中,相似度将是负的欧几里得距离:点和 , 。注意偏好的数量可以用来控制最后的范本,偏好较低导致少量的原型和高偏好导致大量的范本。一般来说,所有数据点的偏好将输入的值相似,这样所有的数据点也同样适合作为范本。声明没有之前倾向于特定的数据点作为范本。

然而,它会导致一些异常值生成相应的集群包含只在传统AP算法相对较小的数据点。例如,图2(一个)显示AP聚类过程中的异常值,数据点右上角的会形成一个集群与其他集群。不过考虑到本文的场景中,异常值的点,出租车很少经过。从经济角度看,离群值并不适合个人候选人汽车共享仓库。因此,我们更愿意将异常值合并到最近的高密度集群。目的的基础上,我们提出一个新的输入偏好的配方如下: 新偏好 将相似点的平均值和其他人。这个值在点密度有关。密度越高,价值越大;同时重点是更喜欢被选为范例。图2(一个)介绍了集群结果偏好将所有输入的值相似之处。我们可以看到离群值变成一个集群包含只有本身。图2 (b)介绍了集群导致偏好设置紧随其后的是(3)。很明显,属于最近的相对高密度集群。

3.2.2。美联社基于行政区分割聚类

从直观上看,美联社的运行时每个迭代。然而,正如[23]礼物,分享计算使我们有效地计算消息可以减少运行时中每个迭代。图3介绍了曲线运行时的总数量从5000年到30000年到5000年每一步。我们可以发现运行时急剧增加上升。实验结果证实了结论。而是三万,运行时大约是15个小时。如果变得更大,它是不可接受的。例如,OD点在24小时内的数量大约是十万,它可能花费数百小时。

为了解决上述问题,我们提出一个优化的美联社基于行政区划分的聚类方法。假设OD点分布均匀行政区域。下面有四个主要步骤的方法:(1)分配所有OD点不同的行政区域。每个地区的组OD点命名为 , 。每个地区都有近OD点。(2)实现标准的美联社 ,然后我们得到一组原型命名为每一个 。此步骤的时间复杂度 ,在那里是迭代的数量。(3)每天都重复上述两个步骤的OD点。然后我们每天每个地区的范本: , , 。(4)对于每个区域,把所有的原型一组, 。分别实现美联社在这些设置。然后我们有最终的每个地区的典范。

为简单起见,我们纪念的一步来第一阶段和步骤第二阶段。

虽然美联社基于行政区分割适用,它仍然需要太多时间由于质量数据。例如,在北京海淀区的迭代需要12个小时,这显然是不可接受的。改进之一是稀疏的相似矩阵,美联社。美联社每个点之间的交流信息。如果两个点之间的相似性是太低了,它们之间的信息太少,我们可以将它设置为零。换句话说,我们可以设置一个最小的和可接受的相似度阈值 ,相似度的计算公式如下:

然后,我们相似变换矩阵 稀疏矩阵。这意味着我们只需要计算出非空的元素。我们可以用三元组存储稀疏矩阵并计算基于一些技术来降低复杂性。为OD点, 有元素。通过以上方法,它变成了元素。很明显, 。步骤的时间复杂度可以减少 从 。当数据集的规模非常大,广泛分布的数据集,这种方法显然是有效的。

尽管稀疏方法可以缩短时间,它也带来了一些问题。两个点之间的相似性参与稀疏阈值的计算是有限的 。找到原型的过程一定距离有限范本的数量将会增加。

以上优化程序后,美联社基于行政区分割聚类方法现在可以得到一组原型实现。这些原型选择从实际数据点,通常叫做“中心。“这可以被视为代表点的所有点的一个子集。所以我们把这些范本交通热点。这些交通火锅仓库可以被视为潜在的候选人。

图4显示从三万年北京OD点集群原型。我们发现82%的原型是位于第五。我们都知道,第五环城公路密集区域的边界。在宏观层面,这些集群现实原型的结果符合得很好。

3.3。原型滤波器

基于前面的步骤,我们有一组原型。然而,我们不能简单地认为所有的原型汽车共享仓库。在某些情况下,一些原型是如此之近,几乎重叠(图4)。更重要的是,在每个集群的数量是不同的。一些范本可以代表许多点,而其他人表示只有几个。因此,我们计算每个集群的点数量和等级从最大的到最小的。如图5,的索引是设在范本,设在是点的数量,是集群的典范。我们发现在图的一个转折点5100年,它是关于(24日)。这意味着只有24范本有100或更多的附加分。这个有趣的结果是由美联社的原则。美联社为每个点渴望找到一个范例,它不能自发地删除离群值。考虑本文的目标是找到高密度地区,我们只能把第一批24原型做出简要分析和评价。

图6显示部分的点在北京首都国际机场三号航站楼建筑之前过滤。图7显示过滤后的点。相比之下,图6指出,在图7不再是重叠的。图8显示第一批24原型的位置。我们可以发现我们生活最典范的热点。是特别敏感的火车站,大型商业和住宅小区。

4所示。实验和结果

为了防止噪音干扰和确定合适的汽车共享仓库的位置,我们把一个星期的出租车GPS数据组成的七十万分在北京。因此,本节的目标是“行政区分割”模型应用于大规模数据集。

在下面几节中,我们描述了数据集用于实验部分4.1。部分4.2介绍了基于大规模数据集的实验细节,最后我们在几个方面分析结果。

4.1。案例研究的数据集

确定汽车共享仓库的位置,我们需要获取两种类型的数据,也就是说,OD点从出租车GPS轨迹数据获得和行政区域的边界。

(1)出租车GPS轨迹数据。GPS轨迹数据获取GPS车辆代表全市人类的移动模式,从中我们可以得到每个出租车旅行的起点和终点。OD点可以从连续GPS轨迹数据触发事件。

在本文中,我们利用GPS轨迹数据集生成的12000北京的出租车从5到2012年11月11日。GPS轨迹数据集包含大约七十万个GPS点。我们提取895139 OD点从GPS轨迹数据集。我们定义为简单起见以下符号:(我) :出租车GPS轨迹数据集(2) :设置的OD点过滤掉(3) :汽车租赁仓库的位置

(2)行政区域的边界。行政区域的边界是用来把OD点,由多边形的顶点。我们获得它从百度地图API (https://api.map.baidu.com/library/CityList/1.4/docs/symbols/BMapLib.CityList.html)。

4.2。结果

摘要OD点是大型和密集和张成的空间很大。它完全满足稀疏美联社的规范和要求。因此,我们使用阶段中的稀疏美联社的第1部分3.2。以下小节中的步骤3,不同的输入的结果的偏好和划分两个阶段是总结表1。首先,我们关注不同的输入参数之间的比较。“偏好”意味着输入偏好意味着在第一阶段的相似之处。“新偏好”意味着第一阶段的输入偏好相似性计算的预期值(4)。我们发现数量的偏好大于聚类原型基于意味着基于新的偏好,因为新的偏好导致异常值分配到相应的高密度区域和减少总数 。其次,相比之下,稀疏的美联社的结果和标准美联社的第二阶段,我们发现稀疏美联社的总数大于标准的美联社。平均2.59集群稀疏的AP元素,而标准的平均元素集群美联社26.83。前看起来那么糟糕,因为不正确的使用稀疏的美联社。我们已经提到,我们使用稀疏美联社在阶段1中,导致输入数据的任意两个点之间的相似性在阶段2和稀疏的阈值是有限的。因此,在第二阶段中,很难找到原型在稀疏的阈值有效。当我们采用标准美联社在阶段2中,集群的结果变得更好。因此,重要的是要检查数据是否适合使用稀疏的美联社。总之,第一阶段的新偏好和第二阶段标准美联社是最好的选择。

要了解更多信息,我们比较结果和美联社之间K——净相似,定义如下:

净相似措施适当程度的原型如何解释数据。这是美联社的目标函数K——试图最大化。我们可以用网络相似性评价聚类方法的性能。我们可以看到在图9美联社基于行政区相似,网络是一个小比K——在每一个地区,特别是在海淀区等大区域。这是由于稀疏美联社第1阶段中使用更适合大面积区域。同时在较小的区域,比如西城区,我们的方法不显示一个突出的优势。

结果现在,有1379个范本替代汽车共享仓库。然而,正如我们所知,不是所有的原型都是合适的,我们需要手动过滤这些范本。在方法部分3.3我们分析点的数量,应该集中1379原型,分别如图10。同样地,我们发现一个转折点和它的坐标是(1500)。因此,我们把第一批50原型做出简要分析和评价。如图11礼物,我们可以发现,我们的方法是敏感的大多数交通火锅,特别是车站、机场、购物中心、和医院。从最直接的意义上说,这个结果在预料之中。

美联社和成本评估时间K方法,则与5000年到30000年OD点我们做另一个实验基于上面的步骤。时间成本总结在表的结果2。显然,美联社远远超过的时间成本K则。值得注意的是,结果显示,在3号线时间的成本K——只执行了一次,我们集合的地方由于美联社。也就是说,我们组最终集群AP作为输入的数量的K则。事实上如果没有美联社的结果,我们必须确定近似通过不同的尝试和实验值迭代。很难预测的范围在大量数据的前提下。然而,结果不说服的时间复杂度K——执行比美联社。如果我们执行K——迭代确定近似 ,在最坏的情况下,时间的复杂性K则会 同时据美联社的时间复杂度 ,这是不到K则。因此,美联社和K——未来的方向是本文降低时间复杂度K则。

5。结论

在本文中,我们做一个新的审判在城市交通大数据关于汽车共享仓库的决心。实验上实现北京的出租车GPS轨迹数据组成的大规模出租车OD点为汽车共享仓库研究部署策略。解决高度复杂的问题造成的大规模数据集,我们提出一种优化美联社基于行政区分割聚类方法。我们定义一个新的偏好公式解决异常值问题在聚类的过程。此外,我们运用稀疏美联社方法来降低时间成本。结合理论和实践,我们提出我们的方法的适用范围。与此同时我们而美联社和目标函数K——共同之处,即净相似。美联社不仅可以克服的最大弱点K则,K则不能确定(集群)的数量本身,但在网络相似性也表现得更好。尽管一些措施减少美联社的运行时,它仍然需要太长时间。因此,在实际应用中,我们可以结合美联社K——为了达到更好的性能。虽然该研究只需要北京为例,本文的结果表明,该方法具有较好的通用性,因为该方法并不局限于数据集本身。方法论的框架适用于任何一个城市只有可用的数据集。

由于这样的事实,我们的方法是基于集群使用出租车OD点,我们还没有考虑太多关于火锅是否有能力成为汽车共享仓库。与此同时,区域划分数据集是不严格的。它可能打破一些相关性尤其是在高密度地区。在这种情况下,美联社集群基于网格划分更为合理。网格细分意味着出租车OD点划分到多个不重叠的庞大的数据点的网格简化表示成更小的子集。我们计划在这些方面做进一步的研究。

的利益冲突

作者宣称没有利益冲突有关的出版。

确认

这项工作是由国家科技重大项目支持(2016 zx03001025 - 003)和北京共同建设专项资金项目。