文摘

乘坐自行车分享系统已经成为不可或缺的交通工具在我们的日常生活中,因为绿色交通逐渐成为一种共识和有意识的行动。然而,问题的“难以出租或返回一个自行车”已逐渐成为一个问题在操作自行车分享系统。此外,科学和系统的方案,可以有效地完成任务再平衡自行车分享系统的缺乏。本研究旨在介绍的基本概念k分裂的层次聚类算法。再平衡战略模型的基础上,结合遗传算法的详细程度。数据收集从自行车分享系统在宁波。结果表明,该算法可以缓解这个问题的不均匀分布对租房的需求或返回自行车和有效改善服务从自行车分享系统。与传统方法相比,该算法有助于重新平衡自行车分享系统的有效时间减少28.3%。因此,它是一种有效的调整方案。

1。介绍

交通堵塞的问题越来越严重,城市机动车数量增加(1]。这种情况已成为现代城市发展的一个主要问题。在中国的许多大城市,汽车的运行速度高峰时期主干道小于20公里/小时。持续的交通拥堵和一系列的社会问题,如环境污染、能源浪费和废气排放,严重阻碍了经济的发展。然而,人们越来越关注环境保护,节能,减排,因为增加的运输问题和生态环境恶化。绿色交通的概念也吸引了越来越多的关注,而蓬勃发展的城市公共交通系统已经成为社会共识。乘坐自行车分享系统被认为是绿色和低碳的交通方式2]。这种运输方式可以缓解道路交通压力和解决“最后一英里”问题在公共交通3]。因此,旅行自行车分享系统已成为越来越受欢迎,得到世界各国政府的关注4- - - - - -7]。

然而,自行车不能自发形成一个相对平衡的分布由于交通流量的不对称,从用户需求的不确定性。政府利用相当比例的人力和财政资源平衡自行车。然而,情况如“没有自行车租”或“不”桩返回一个自行车仍然存在在许多车站由于滞后和nonscientificity的平衡8,9]。因此,许多市民放弃自行车分享系统,当他们出去,从而大大降低人们使用自行车分享系统的概率(10- - - - - -12)和限制自行车分享系统在一定程度上的发展。

简单地增加公共自行车系统的设施来改善服务和提高满意度从公众不能从根本上解决问题。如何有效平衡自行车在电台,以确保站用更少的自行车可以快速转移,而那些自行车可以转移,已成为越来越多的研究人员共同关心的话题(13,14]。

本研究基于模型的开发调整方案的详细程度和认知过程的层次结构。这个方法执行重整计划从粗到细粒度在整个实验区域。通过宁波市的自行车分享系统作为一个例子,本研究通过比较实验,验证提出调整方案可以改善公共自行车系统的运作效率,降低了管理成本。执行这样一个事业支持有关部门制定合理的调整方案,自行车分享系统。

2。文献综述

2.1。调整方案

近年来,公共自行车系统推进相关研究,这些研究提供了大量的想法再平衡自行车分享系统。平衡的主要选择自行车分享系统包括基于用户和运营商策略(15]。前者是dockless自行车分享系统中更受欢迎,而后者表现更好的在站自行车分享系统。对于后者,目前的趋势显示了混合解决方案结合不同的平衡模式。

阴et al。16)开发了一种logit模型来估计社会人口的影响,土地使用,公共交通特征调整自行车分享系统,得到了很好的结果。但logit模型太简单处理复杂的模式在调整自行车分享系统。路[17)治疗的问题尽可能多的用户提供服务,一双bike-dock分配问题。他们进一步开发了一个算法与当地比率来解决这个问题。结果表明,该算法可以节省旅行时间和帮助更多的用户使用公共自行车系统。但是如果用户不愿意走很长的路去车站,该算法将不会工作。施(18)设计了一种改进的粒子群优化算法和制定相应的平衡自行车模型。然而,卡车通常有一个低比率的平均负载据统计。所以,算法需要进一步优化。刘和任19)提出了一个动态平衡策略和一种改进的遗传算法。该算法旨在提高整体效率降低线路的数量。但是一些理想化的模型中设置造成很多错误和减少的效果。毛(20.)提出了公共自行车系统和一个动态平衡模型计算出每个区域的自行车数量与时空图分析移动模式。结果表明,该方法有很高的精度。但仍有被忽视的因素在模型中,将影响精度。最近,一些学者[21)提出了一种自底向上的基于集群模型重新平衡自行车分享系统结合spatiotemperal特点的自行车旅行。然而,这纯粹是一个静态的再平衡战略方法,及其效果和性能需要改进。

2.2。模型的详细级别

模型细节层次(LoD)起源于计算机视觉领域。电脑决定了资源配置呈现对象根据环境中的位置和重要性,以减少nonimportant对象的水平的细节和获得更高的渲染效率。近年来,的详细级别的模型已广泛应用于许多领域。

风扇等。22)提出了一个战略培训层次分类的图像。网络将会更加稳定和健壮的通过等级培训。实验表明,该网络的训练,这种策略将会得到更好的结果。王(23)提出了一个面向可靠性分级控制策略。采用这种策略,进一步提高微型电网的效率。结果表明,该分层控制结构具有更好的性能对可靠性的提高。图像金字塔模型的另一个应用程序的层次细节模型在图像的存储和管理24]。图像金字塔建立一系列层具有不同分辨率和建立相应的空间索引机制。这将提高缩放或浏览图像的渲染速度。胡(25]进一步介绍了路由策略层次模型和计算最佳的旅游路线与分层的方式。Nakano [26转位因子)分类分级分类问题,提出了战略的层次分类新数据集。实验结果表明,该方法提出了一个更有竞争力的结果相比其他策略。

简而言之,数据结构模型的水平的细节是很容易的和明确的。它已经被应用在很多学术领域。同时,模型的实现很简单,所以它更适合调整自行车分享系统在城市地区。

2.3。建模自行车分享系统的平衡

2.3.1。概述

学习平衡自行车分享系统是确定车站需要重新平衡,自行车的数量必须传输的每一站,以及计算最优路径调整卡车(27]。

本研究假设的总数量的自行车和每个车站的股权仅限于简化再平衡问题。一辆自行车锁在一个电台或被用户使用。三个州发生在每个车站,即没有自行车,没有空闲成堆,可用自行车和闲置成堆。我们假设一定数量的平衡中心设置。这些中心是负责调整自行车的车站。每个中心配备有卡车。这些卡车的承载能力保持不变。平衡系统总是监视公共自行车系统的状态。成堆的锁比车站时低于或超过一定范围时,系统将自动提醒员工在管理中心重新平衡自行车。

2.3.2。模型建设

因此,如何设计一个合理的和有效的平衡方案基于站点的需求一直是一个关键问题。通过这个方案,卡车可以通过电台以有序的方式,最后返回到中心。在这种情况下,公共自行车系统可以尽可能满足用户的需求和提高公共自行车服务系统(28,29日]。此外,平衡自行车分享系统必须的成本考虑进去,因此卡车的运行距离最短的或所花费的总时间最少。这是一个迫切需要解决的问题在当前的公共自行车系统,这也是本研究倾向于解决的问题。

因此,调整方案提出了工作需要的运输成本和满足自行车分享系统作为目标函数。

(1)运输成本。卡车旅行必须短运输成本降到最低。被一辆卡车的距离进行调整访问下列公式所示: 在哪里是一个决策变量。 意味着卡车从站到车站在一个特定的旅行, 意味着卡车不从站到车站 。 距离车站吗到车站 ,和每公里的运输成本。N指的是需要重新平衡的站总数在一定的旅行。

(2)满意。满意度可以翻译成惩罚成本不满足时间窗口。具体来说,调度卡车应该预期的时间内完成分派任务尽快确保用户可以利用在车站的服务。我们使用软时间窗限制卡车的到达时间。违约成本高时前后到达时间的预期时间是早/晚。的惩罚成本时间如下公式所示: 在哪里是一个决策变量指示是否站需要重新平衡。卡车到达车站的时候吗 ; 是网站的时间窗口 ,和代表最早的时候所期望的网站 ; 是最新的时间预计网站吗 ; 是早到的违约成本的时候窗口是不满意;和迟到的惩罚成本。图1显示了图的罚函数软时间窗。

总之,平衡模型的目标函数如下所示: 在哪里α运输成本的重量值,β的权重值是违约成本的时间窗口,是运输成本,是惩罚成本的时间窗口。因此,优化的目标函数如下所示:

上述公式的约束如下:(1)决策变量是一个0 - 1变量,定义如下: (2)在每个旅行,每一站由卡车只能服务一次。因此, 在哪里V代表所有车站的集合,包括平衡中心由{0}表示。再平衡中心可以多次访问每个旅行。(3)卡车将访问自行车站。 (4)每个车的装载必须是一个非负整数,不超过其最大容量。 在哪里代表的自行车数量的卡车运输我到车站j,是自行车的最大数量,卡车可以携带。(5)自行车的数量平衡前后站重新平衡。 在哪里车站前的初始数量自行车重新平衡,然后呢是后来数。(6)的到达时间卡车在车站j下列公式所示: 在哪里装载或卸载的时候是一辆自行车,然后呢卡车从站的运行时间吗我到车站j。(7)卡车将访问车站一个接一个,见公式(12),米是一个数字,趋向于无穷。

总之,公共自行车系统的模型的平衡算法提出了研究显示如下:

2.4。k - means

聚类是一种无监督学习方法在机器学习。这种方法使用对象之间的相似性将整个数据集划分为几个不同的集群。这样的步骤进行,以确保数据在同一集群有很大程度的相似性,在不同的集群和数据之间的相似性很低。通过这种方式,集群通常用于揭示数据间的内在本质。站的拓扑关系是一个重要的空间特性,因为自行车的分布站被认为是一种网络拓扑结构。合理的分工方案很容易设计分地区站定位是否考虑网络拓扑结构的特点。在这项研究中,我们使用集群车站的k - means聚类算法的基础上的空间特征。

k - means算法是一种常用的聚类算法,在研究领域一个重要的分析工具。该算法的目标是随机选择k点的数据集作为初始聚类中心,然后计算每个中心和其余的对象之间的距离。剩下的数据然后分为接近这些集群k中心。最后,每个集群的中心是根据对象的重新计算集群,集群是改变。重复这个过程直到每个部门的结果保持不变或平方误差的总和在每个集群达到最低时,算法结束。

在k - means,的选择k值直接影响最终的聚类结果。在文献中很多策略可以用来确定k价值。在这项工作中,我们将使用肘部规则。肘部规则的核心指标是平方误差的总和(SSE)。这个指数表示聚类结果的质量。集群的聚合度会增加,上交所的价值自然会变得更小的价值k增加(30.]。具体来说,如果该值k小于集群的实数,上交所的下降会增加以来的大k将增加每个集群的聚集。然而,如果k变得更接近集群的实数,奖励在增加聚合将大幅减少30.]。因此,上交所的衰落将大幅减少。的价值k继续增加,它往往成为被夷为平地。这表明上交所和之间的关系k看起来像手肘的形状。的价值k对应于肘部的部分是最佳的聚类数,如图2。

曲线在图2类似于一个弯头,k值对应于肘适当的值。

2.5。遗传算法

遗传算法(GA)用于“通过模拟自然进化过程搜索最优解过程”(31日,32]。的一些核心业务将简要介绍了遗传算法的部分。

2.5.1。编码

一个数字序列用于编码克服搜索空间大等缺点,长代码生成的二进制编码。在本文中,0是用来表示数量平衡中心和{1、2、3、……n}代表自行车站需要重新平衡。例如,如果一个染色体是[0、2、3、4、0,1,5 0],这意味着平衡卡车离开中心,调整站2、3和4,并返回到中心。然后离开中心重新平衡站1和5,再返回到中心。具体路线如下:

再平衡中心⟶站2⟶站3⟶站4⟶平衡中心⟶站1⟶站5⟶平衡中心

2.5.2。初始种群

首先,所有车站的数量需要重新平衡是随机排序,然后k−1 0是随机插入到染色体k是再平衡卡车的数量。然后插入一个0,分别在开始和结束的序列,代表的再平衡卡车离开中心,最后回到中心。之后,判断当前是否调整计划满足卡车的容量约束和是否有连续0在当前调整方案。如果约束满足的负载要求,没有连续0再平衡路径,它将被选择作为一个初始染色体或将被丢弃,重新生成一个新的染色体。重复上面的过程来生成N染色体形成了初始种群。

2.5.3。适应度函数

健身可以用来简单地评估质量的染色体。适应度函数值越大,相应的染色体就越好。因此,在这项研究中,上面的成本函数的值的倒数作为适应度函数;也就是说,

2.5.4。选择

精英保留和轮盘赌选择结合本文不仅确保最好的个体存活到下一代,也使个体适应度函数值大进入下一代。假定的染色体数量在当前人口NP,和具体操作步骤如下:(1)最优个体适应度函数的最大价值在当前人口记录精英。这个人不执行成对交叉和变异,但直接复制到下一代。(2)轮盘赌选择上执行其余的人。换句话说,NP−1染色体交叉选择。

2.5.5。交叉

交叉操作进行NP−1染色体在前一步骤中选择。生成新个体不断通过交叉,扩大算法的搜索空间。(1)当平衡卡车的数量K> 1,本研究采用一种改进的交叉算子。具体步骤如图所示3。步骤1:基因片段与0开始和结束时都随机选择父母的染色体1和家长2,分别。第二步:预先考虑基因除了最后一个0两个基因片段的父染色体。步骤3:基于基因片段1和基因片段2,后代1和后代2构造。步骤4:扩大后代1:遍历父2的基因从左向右,并添加没有出现在基因的基因段1(1)后代的后代,最后添加代码0年底后代1。填写后代2对称以同样的方式。第五步:对后代1,K−2 0是随机插入后段1,确保有K平衡路径。之后,判断当前的染色体是否满足平衡卡车的容量约束,确保没有连续的0。如果约束条件没有得到满足,K−2 0插入。后代2是相同的方式处理。(2)当平衡卡车的数量K= 1,循环使用交叉算子和具体步骤如图所示4。第一步:首先,0年代开始和结束时的父母1和家长2删除,然后父母1的位置是随机选择的。第二步:找到父母的相应位置上的基因数量2;然后回到父1找到相同数量的基因的位置。重复这个过程,直到形成一个环。父母的基因和相应的位置1的戒指保存。步骤3:父母的基因选择1选产生的后代的位置顺序并不是打扰。步骤4:其余的基因在父2投入后代1。

最后,添加0到染色体的两端得到最终结果的染色体后代1。同样,染色体后代2可以获得。

2.5.6。突变

在这项研究中,选择交换变异对染色体进行变异;即两个非零的基因是随机选择在父染色体和交换。如果路线可以交换后满足卡车容量的约束,它将更新。

总之,遗传算法的完整算法流程如图5。

3所示。再平衡战略基于模型的详细级别

3.1。K-Divisive层次聚类算法

分裂的层次聚类算法(33,34也被称为自上而下的聚类方法。在该算法中,集合中的所有对象被当作一个集群。这然后分成小的集群,每个集群作为一种新的细分。总体而言,分裂的层次聚类方法的实现也是一个过程,构造一个树从上到下,如图6,线和不同的颜色指的是不同的集群。在上述递归分割过程中,所有对象首先被当作一个树的根节点。然后递归分割成多个小的集群。这个过程是迭代执行,直到只有一个对象存在于每个集群或一个预定义的终止条件满足。

在许多分裂的层次聚类算法中,分裂的层次聚类和k - means,称为K-divisive层次聚类,是使用最广泛的算法之一。这个算法的目的是将数据通过分裂的层次聚类算法通过迭代应用k - means直到每个对象成为集群或满足终止条件。

K-divisive层次聚类方法结合了传统的k - means算法和分裂的层次聚类,从而不仅使集群现实,也极大地提高聚类效率(35]。

3.2。平衡算法基于K-Divisive层次聚类

公共自行车系统的相应的再平衡战略设计的基础上,在本节中K-divisive层次聚类算法。前面的分析表明,K-divisive层次聚类算法的过程实际上是一个分裂的集群从粗到细的粒度。平衡算法的本质是一个再平衡战略,粒度由大变小和一个持续改进的过程。

得到相应的分裂地区后,覆盖区域集群,从原始数据集划分,被视为平衡单元顶部水平。租/返回然后计算每个集群的自行车数量。根据统计结果,制定相应的调整方案,这也是顶级的再平衡战略。然后,自行车的subclusters站在下一个水平获得了每个调整单元。这个层次的集群比以往更加细化。相应的调整单元形成根据每个集群的范围。这些单位被视为平衡细胞在第二个层次。此后,所有集群等不同层次遍历是根据一个规则。计算相应的调整计划根据租/返回需求在不同的集群在同一水平。通过这种方式,每一层的再平衡战略集成在一起,形成一个树状方案,即基于模型的平衡算法的详细级别。 The complete process is shown in Figure7。

总之,该算法实际上是一个从粗到细的再平衡过程。这一概念也充分体现了人类的认知过程从宏观到微观。当决策者进行再平衡计划,他们总是执行计划从宏观的角度来看,然后逐渐完善小公司,而不是集中在一个或两个站的需求开始。因此,这项工作的平衡算法也符合认知和思维的过程和特点。

4所示。结果与讨论

实验使用Python,程序测试和运行Windows操作系统下的10。此外,与传统方案进行对比实验。结果表明,平衡算法提出了工作与传统相比有明显的优势。

4.1。实验K-Divisive层次聚类

宁波城市的市区公共自行车系统作为实验区选择在这工作。统计数据显示,169个自行车站定位。这些站的地方位于分为多个级别的细节,如图8站,一个点代表一辆自行车。具体来说,收集所有的电台被认为是一个集群,也是作为开始的层次划分。这些电台被用来画一个手肘图。一个合适的k价值被发现将集群组成的所有电台形成小subclusters。上面这些subclusters被认为是细胞水平,作为区域1、2和3所示图8。

整个区域所有自行车站定位分为三个subclusters。这些集群通常覆盖一个大空间。自行车的数量站包括相对较大。这些电台有一个低密度分布,和车站之间的安排相对稀疏。此后,肘部图是画再找到合适的k在每个subcluster价值。k - means聚类算法应用于进一步划分subcluster获得二级部门计划(例如,地区11、12和13在图8)。

通过持续的分裂subcluster范围会逐渐减少。自行车的数量站在每个subcluster也将减少。分裂过程不断根据这些规则执行,直到每个集群包含少量或只有一个车站。层次划分方案站在自行车分享系统与粒度从大到小终于由叠加在一起形成多层集群不同的扩展。

4.2。实验基于LoD模型的平衡算法

减少的数量计算,车站在底部形成的集群分工方案的LoD被视为平衡单位最后一个级别。换句话说,站在这些细胞不再分裂。结合租/返回每个细胞的需求,计算每一层的调整方案。然后再平衡方案在每一层叠加在一起,形成一个完整的方案,从粗到细的粒度。

记录在早上高峰时间6月30日,2019年,被选为表现在实验研究中的样本数据。自行车的数量在每个站在上午7点作为初始状态。在每个车站的使用自行车模拟通过阅读租赁/返回记录在数据库中。报警阈值在车站被设置为[0.4,0.6]。具体地说,车站会报警,当其饱和度超过阈值区间。此后,一个固定的时间窗口从惊人的生成时间。自行车在每个区域的总需求及其相应的时间窗口分别测定,如表所示1。

遗传算法应用于计算平衡单元之间的最优路径。次卡车回到平衡中心应该尽可能最小化。当前水平的平衡任务完成后,调整单位的低水平进一步执行。我们的遗传算法假设如下:人口规模是100,迭代的数量是1000,变异率为0.1,卡车的运行速度是30公里/小时,最大承载能力的卡车是400的初始负载250。最后,调整方案在不同层次上解决,如表所示2。

4.3。比较实验和分析

我们也将该算法与传统的一个。在传统的算法中,我们没有把车站区域定位的LoD模型。相反,遗传算法直接称为平衡地区最低层的LoD模型的集群。

在这个实验中,我们只分配一个卡车重新平衡自行车分享系统明确结果。据推测卡车的运行速度是30公里/小时。实验结果如图所示9。图9(一个)表明,卡车将直接从中心运行对所有调整单位与传统的平衡算法。图9 (b)显示了调整方案基于LoD模型提出了这项工作。

如果采用传统平衡方法,卡车将直接从平衡运行所有车站中心。每个站的调整方案由遗传算法计算,如表所示3。卡车覆盖的总长度是65318.75米,有效时间是130.7分钟,如表所示4。然而,平衡方案的基础上提出了工作,我们收集的统计数据在不同水平的总长度,发现路径使用本文中的方法是46845.62米,有效时间是93.73分钟,如表所示4。得出结论,该算法可以减少28.3%的再平衡公共自行车系统的有效时间与传统相比。

再平衡的方法提出了工作可以有效地缩短总距离,从而减少的有效时间。这种机制可以帮助来满足用户的需求尽可能多使用自行车和完善城市公共自行车系统的整体服务。因此,这个平衡自行车分享系统方案是可行的。

平衡算法的关键是解决自行车需求的不平衡分布的空间和时间。实验证明了平衡方法提出了工作可以提高响应速度,提高服务的公共自行车系统,减少维护成本。如果这项工作的方法是应用于主要城市公共自行车系统的操作和管理,那么它将不仅有助于提高系统的服务,增加公民的满意度也有效地引导人们使用自行车分享系统,而不是汽车。因此,路上交通拥堵的现状是增强。

5。结论

我们研究了自行车分享系统调整方案的详细级别的模型的基础上结合K-divisive层次聚类算法。算法需要综合考虑最大化满足需求租用或返回自行车和平衡成本最小化作为优化目标。

算法最初将收集所有电台作为集群的集群,然后使用k - means算法。获得的subclusters然后使用k - means reclustered形成小subclusters。集群不断执行根据这样的规则,形成分层的层。自行车的地方站定位划分不同的粒度。每一层的层次结构,由集群被认为是一种平衡。最后,遗传算法来计算单位每一层之间的最优平衡路线。再平衡方案从粗到细的形成从宏观的角度来看。

与此同时,我们在宁波市区的公共自行车系统作为一个例子来验证算法的可行性和实用性。比较实验证明了平衡方案可以有效地缓解的问题“很难租/返回一个自行车”的自行车分享系统。与传统方法相比,提出的算法可以减少调整自行车分享系统的有效时间28.3%。因此,这项工作可以提供一个有效的理论依据平衡公共自行车系统在城市地区和管理部门的重要指导。

虽然这项工作取得了相当大的成果,还指出一些缺点。(1)在建立模型中,时间窗的长度设置为固定值。我们没有详细讨论这个值的设置。在未来的研究中,租赁需求的特点/返回自行车车站将综合考虑分析的影响设置不同的值的时间窗算法。这个任务是必要的,以确定最优值的时间窗口。(2)实验参与这项研究仅仅是用于验证该算法的有效性。在未来的研究中,我们将结合租或返回需求的时空分布特征与神经网络预测租自行车/返回要求。通过这样做,提出的算法可以更准确。

研究的贡献将灵感或指导人员从事这一领域。我们将进一步研究动态和智能城市公共自行车系统平衡策略。

数据可用性

样本数据和代码支持本研究的发现是可用的https://figshare.com/s/b1f7067d0e6ce05bb003。

的利益冲突

作者宣称没有利益冲突。

确认

这项研究是由浙江省自然科学基金(没有。宁波LQ18D010008),自然科学基金(没有。2018 a610132),一个项目由浙江省教育科学研究基金支持部门(Y201736984)。