英语原文共 10 页，剩余内容已隐藏，支付完成后下载完整资料
基于共享自行车的轨迹规划自行车道
摘要：
世界各地的许多政府都在推行绿色交通模式。 因此，建设有效的自行车道已成为各国政府推广骑行生活方式的关键任务，因为精心策划的自行车道可以减少交通拥堵并降低骑车人和机动车驾驶员的安全风险。 遗憾的是，现有的自行车道规划轨迹挖掘方法并未考虑政府关键的实际限制：1）预算限制 2）施工便利性，以及3）自行车道利用率。
在本文中，我们提出了一种基于数据驱动的方法来开发基于大型真实世界自行车轨迹数据的自行车道施工计划。 我们执行这些约束来制定我们的问题，并引入一个灵活的目标函数来调整用户数量和轨迹长度之间的距离。 我们证明了问题的NP难度，并提出了基于贪心的启发式方法来解决这个问题。 最后，我们在Microso Azure上部署我们的系统，提供广泛的实验和案例研究来展示我们方法的有效性。
介绍：
骑自行车作为日常通勤的常用城市交通模式已被全球多个政府推广原因有以下几点：1）对用户来说这是一种环保的交通方式; 2）减少道路交通堵塞; 3）这是一种健康的生活方式。因此，建设有效的自行车道，如图所示成为政府促进自行车生活方式的重要任务。 精心策划和实施的自行车道不仅可以使骑车更容易，而且还可以降低骑车人和汽车司机的安全风险。
在城市规划自行车道的传统方法主要依赖于经验和调查。 随着GPS嵌入式设备的普及，越来越多的数据驱动的自行车道规划已经出现。但是，现有的研究只关注总结自行车轨迹数据的共性，而忽视政府面临的现实限制和要求：
- 预算限制。 其中包括实现路段上的自行车道的成本，其可以包括:1）用于创建自行车道的空间; 2）建设自行车道栏杆的价格，以及绘画标志。不幸的是，政府预算有限。
- 施工便利。为了实施自行车道，需要派出施工队到施工区，所需要的队伍数量也是一个严格的限制。 为为了便于管理，政府希望避免将队伍分散到远处的施工区（例如图中的红线突出显示自行车轨迹最多的前100个分段），并且倾向于将它们聚集在一起，即作为道路网络中有限数量的连接组件。
- 自行车道利用率。作为公共服务，从政府的角度来看，建设自行车道的目的是增加更多骑车人的可用性并覆盖更多可能的路线。
为了结合这些现实世界的限制，在本文中，我们提出了一种基于摩拜用户收集的大量轨迹来规划自行车道的数据驱动方法。 摩拜是一个完全无站点的自行车共享系统，目前部署在中国的许多大城市。 它是世界上最大的自行车运营商，最近使上海成为世界上最大的自行车共享城市。 与传统的基于台站的自行车共享系统相比，摩拜用户生成的轨迹在解决自行车道规划问题方面有两个独特的优势：
- 现实的旅行需求。 与许多现有的基于车站的自行车共享系统不同，该系统需要用户从指定车站取放自行车，摩拜提供了一个更灵活的系统，用户可以在任意位置拾取和放下自行车。因此，摩拜用户的轨迹反映了实际的城市旅行需求。
- 丰富的旅游信息。摩拜的锁定系统中嵌入了一个3G通信组件和一个GPS模块，它使用户能够用手机找到自行车。 它也保持了用户穿过的确切路线的轨迹，而传统的基于站台的自行车共享系统只能提供出入信息。
在本文中，我们在Microso Azure上设计，实施和部署了一个数据驱动的自行车道规划系统，
该系统不仅利用了成千上万摩拜用户产生的大量自行车轨迹，而且满足了政府要求的限制和
目标。 提议的系统包含两个主要部分：
- 预处理，预处理来自摩拜用户的轨迹并将其映射到道路网络上
- 自行车道规划，它采用用户的输入（即来自政府的要求）并提供自行车道建议。 主要的
贡献总结如下：
- 我们通过考虑各种建设限制来制定自行车道规划问题，并提出一个灵活的调整参数来描述覆盖用户数量与不断覆盖的自行车旅行的长度之间的设计交易。 并证明该问题是NP难的。
- 我们提出了一种贪心网络扩展算法，该算法为数据驱动的自行车道规划问题提供了可扩展的近似解决方案。 为了达到更好的有效性，我们还提出了两种不同的初始化算法，分别适用于低预算和高预算的情况。
- 我们在上海市一个月的摩拜轨迹数据（9/1/2016 - 9/30/2016）中广泛评估所提出的算法。 我们还提供广泛的数据分析并发现许多有用的见解。 此外，现场案例研究旨在评估我们的自行车道建议的有效性。
- 具有真实数据集的在线系统已部署在Microso Azure。 最后，我们收集了政府官员的反馈意见，我们的系统得到了非常积极的评价。
本文的其余部分安排如下：部分2描述问题定义和系统概述。 部分3介绍预处理模块。 自行车道规划模块在部分4中介绍。实验和案例研究在部分5，部分6介绍系统部署详情和专家评论。 相关的工作总结在部分7 部分8总结该文件。
问题定义：
给定道路网络图G=（V，E）（其中顶点集合V表示点，并且边的集合E = e表示所有相关的路段），我们的数据驱动的自行车道规划问题目标是为了发现边的子集Elsquo;isin; E遵循三个标准：1）建设预算约束；2）连接约束；3）最大化使用效益。
- 建设预算约束：连接每个路段ei的花费成本为ei.c，为了将路段转化为自行车道（例如：建造栏杆并清理空间）另一方面，政府对建设自行车道的整体预算约束B，自行车道建设的总成本不能超过总体建设预算B，在公式中表现为：
- 连通性约束：如引言部分所述，为了便于施工和管理，政府倾向于部署具有多达k个连接部件的自行车道（例如，分配给k个施工队）。这符合如下不等式：
其中表示对于边集Ersquo;联通分量的算子。
- 最大化使用效益：这里的目标是最大限度地提高部署的自行车道的总体使用率，这应该1）促进尽可能多的自行车道并且2）沿着他们的旅行路线覆盖更多的连续路段。 请注意，自行车道规划中的连续道路覆盖率至关重要，因为它提高了用户的体验质量（QoE）。 例如，一辆自行车在一条路径上行驶（即，e1 -gt;e2-gt; e3），如图中蓝色线条所示。 尽管两个计划中的自行车道覆盖相同长度的轨迹，在图三中的路线二更好因为它提供了更持久的路线，但图三中的路线一却分离成了两个不连续的子段s1和s2。
不幸的是，这两个目标（即服务更多用户vs覆盖更长和连续的旅行）通常彼此相互矛盾，因为用户旅行通常具有不同的目的地。 因此，我们提出了一个灵活的评分函数，供决策者调整他们对轨迹三的两个目标之间的偏好：
其中tri .g是轨迹tri的优先得分，si是与路径计划Ersquo;中的轨迹tri重叠的连续路段的集合，sj是在集合si中的一个连续的路段，规格化了路段连续的长度
sjisin;si(min(e,l)是在网络中最短的路段)，这样就保证了值不会小于1，并且a是调整参数，用于设置优先级对覆盖用户数量与连续长度覆盖。 使用归一化长度的指数函数来设计分数函数的原因在于，当agt; 1时，连续分段得到较高分数。 否则没有指数函数，路径规划1和路径规划2将会得到相同的分数。较小的a表明更好的性能对于大量用户覆盖来说例如，a = 1意味着我们不关心连续长度覆盖率，以及图3中的两个路径计划具有相同的专业分数），而较大的一个意味着用户旅行的较长连续长度覆盖是优选的。
然后，可以通过聚合与道路段集合Ersquo;重叠的所有轨迹Tr的得分来计算边缘集（或自行车平面图）Ersquo;.g的总体优点得分：
我们现在正式确定自行车路径规划问题为：
问题定义：给定一组轨迹Tr，一个路网G=（v,e）和花费ei.c在每段ei上，调整参数a,a的值为k，并且最大的开支限制为B，我们想找到一个Ersquo;的边集Ersquo;isin;E，这个能够最大化效益分数g,并且完全满足两个限制：1）最大开支不超过B；2）Ersquo;的联通数要小于k。正式的来说这可以表示为一个整数规划问题：
对于这样一种找到在K限制的条件下最大化效分数是一个NP-难问题并且将会在引理1中证明。
引理1（NP-难），找到K预算限制的连接路段并且得到最大效益分数是一个NP难问题。
证明：我们减少了用k最大的专业分数找出k个预算约束连通分量的问题通过0-1背包问题。我们可以将每个路段ei E视为一个项目，其中项目大小（即建设成本）和项目保护（例如，权威分数贡献）。集合Ersquo;选择路段被看作背包问题，其大小为B（总预算约束）如果我们设定a = 1，即我们不关心连续长度覆盖，并且k = E，即断开组件的最大数量是无界的。这个时候我们的问题可以转化为0-1背包问题。
因此，对于任意的决策版本的0-1背包问题，我们能找到一个决策版本来在满足K预算限制下和最大化效益通过设置k=|E|并且a=1并且他们的结果是一样的，因此0-1背包问题是我们这个问题的简化版本，因此我们的问题属于NP-难问题。
证明这个问题是NP—难问题后，我们提出了一个启发式的贪心算法来解决这个问题。
系统框架：
图4是我们系统的一个大概，里面包含了两个主要组成部分。
预处理： 这个是组件采取自行车轨迹和道路网络，并执行三项主要任务：1）轨迹数据分析，删除异常点的GPS点; 2）轨迹地图匹配，将自行车轨迹投影到相应的路段; 和3）倒置索引构建。它建立了一个索引来加速基于道路段ID检索轨迹的查找过程
自行车道规划： 这个是组件采用用户的参数，例如总预算，连接组件的数量和a值，并输出自行车道推荐结果。 如果用户对结果感到满意，可以调整参数以获得一组新的建议，我们提出了两种不同的自行车道推荐方法。
预处理
预处理是将道路网络和轨迹作为输入，并执行以下三项任务以准备数据以供进一步处理：
轨迹分析： 步骤是通过用基于启发式的异常值检测方法滤除噪声GPS点来清除摩拜用户的原始轨迹。
轨迹图匹配：在这一步中，系统将每个GPS点映射到相应的路段上。 我们使用基于交互式投票的地图匹配算法的修订版本，其中路段的速度约束未被使用，以执行地图匹配。
倒置索引结构： 在这一步中，系统为每个路段建立倒排索引，记录通过它的轨迹ID。 通过这种方式，我们可以加快基于路段的轨迹查找。索引构建过程在Microso Azure上并行完成。
自行车车道规划：
在本节中，我们首先描述计划自行车道的贪心网络扩展算法的总体框架。 艾尔，我们描述了初始化网络扩展的不同方法。
贪心网络扩展框架：
主要思想：贪心网络扩展的算法是通过个扩展K 个开始路段在路网中。灵感来源于在大地中发现的两个关键洞见，即空间热点和星状的流动空间。
空间热点：图5显示出发地点数最多的两个热点，其中上方与地铁终点站（即地铁13号线缙云路站）相反，下方说明非常受欢迎的购物中心（即，白莲中环商业广场）。 观察背后的结果是直截了当的：尽管商场非常受欢迎，但它并不靠近任何地铁站，这使得自行车成为最佳选择; 类似的终点站，从那里回家的最快和最经济的选择是骑自行车。
星状的流动空间：我们进一步调查了空间热点周围的旅行方向，我们发现自行车旅行从同一个起始位置进入不同的目的地，就像多边有一个共享端，即一个像星星一样的流动性的Paern，如箭头所示在图5（b）；
考虑到这些观察，我们基于贪心的自行车道规划算法扩展了道路网络中增量网络扩展算法。阿格慕有三个阶段：
- 阶段1：初始化：算法从选择k个起始路段开始。 通过这种方式，我们可以保证由算法生成的最终道路段推荐满足连接约束条件，即不会生成超过k个连通分量。
- 阶段2：网络扩展：在这个阶段算法迭代运行，在每次迭代中，该算法选择最佳路段（即，在经典的0-1背包中，每个成本的知识得分增益最高，这与物品保密与尺寸的比率相当）为了得到集合Ersquo;并且将没有选择的边放入候选集合中。
- 阶段3：终止。这个算法终止时满足预算限制B，并且返回结果路径集合Ersquo;作为一个推荐自行车路段规划。
算法设计：算法1给出了我们贪心网络算法的伪代码，在初始化阶段该算法首先在集合Ersquo;中选取K个起始路段，将起始路段的相邻路段放入候选集并通过减去起始路段的总成本更新预算值。
在网络扩展阶段的每一次迭代中该算法检查候选集C的每一个路段ei如果有道路段成本小于剩余的预算，则该算法已经覆盖了所有的轨迹Tr由路段ersquo;和结果路段集合E。检测到所有覆盖的路径我们再更新相应的效益分数grsquo;根据公式4。我们计算每个成分的得分增益。在这个过程众我们保存记录路段enext，通过减去选定路段enext .c的成本进行更新。 从候选集合中删除道路段enext，并且其所有
全文共5863字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[12385]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
