《实时路由与开放街道地图数据》由会员分享，可在线阅读，更多相关《实时路由与开放街道地图数据（5页珍藏版）》请在金锄头文库上搜索。
1、实时路由与开放街道地图数据摘要关于网络和手持设备的路由服务在过去几年变得无处不在，必应、谷歌地图等网站都允许用户在任何时间查找任意位置之间的路由。同样，车载导航装置属于几乎所有新车的现成的设备。开放街道地图项目的可自愿选择空间数据量已在过去五年内迅速增加。在许多领域，数据质量已符合商业地图数据，如果不是彻底超越它。我们基于与开放街道地图数据的工作演示了这两个服务器和手持设备的实现。这两个应用程序在大陆规模的网络拥有数百万街道段提供实时的和详细的最短路径计算。我们也演示出了像拖动路线和往返规划这样较先进的实时功能。1.引言路由已经成为无处不在的与流行的Web服务，如必应、谷歌地图和车载导航设备在
2、几乎每一个新的汽车上都有。我们已经解决了在早期的关于寻找最短路径的道路网络的计算的问题。不幸的是Dijkstra的开创性算法并不适合大规模的图表，并且大多数的计划项目由于它不会产生最佳路由的补偿已经被建议不采用。在过去的五到十年，算法工程社区开发的算法和数据结构为Dijkstra算法提供了大量的加速比，并保证最佳路由。尽管在技术意义上可用，但是这些高效的算法尚未被应用广泛。快速路由最重要的应用是基于服务器的网络服务和手持式导航。虽然这两种使用情况表面上看起来是不一样的，但就其技术挑战和设计可扩展的系统而言，他们大多是相同的。OSRM是一个基于服务器实现的项目，而MoNav是用于手持设备，例如像
3、平板计算机或智能电话的实现。2.相关工作有关于Dijkstra的原始算法的加速技术，该算法工程社区已经完成了大量的工作。在各路口对应节点和街道段边缘都将道路网络建模为图G =（V，E）。将Dijkstra算法利用道路网络的自然层次结构提出分层技术的时候，该算法工程社区提供了目标上的指导意义。有一个较早的复杂方法是带有地标和三角不等式（ALT）的A *算法。弧标志方法可提供最佳的结果，并且它是有大量加速比的顶尖技术之一。分层技术将会跟随长途航线在某些必要的时候及时地进入长途网络，也就是进入高速公路或国道的概念。收缩层次结构（CH）在交易预处理和查询时间方面有一个现成的非常方便的权衡方法。大陆规模
4、的路网可以在约一百个微秒的延迟下对问题进行预处理，并开始运行和查询。CH根据一些措施的重要性来排序他们，并在应用中使用这个排序来试探性更快捷地选择节点。这里，短切削是指节点从图中取出尽可能少的快捷边缘和尽可能被插入到保持最短路径的距离。由此产生的数据结构包括本来的边缘和所有产生走捷径的集合。这个迪杰斯特拉算法仅需要跟随那些导致更重要的节点的边查询就可以了。这意味着该算法工作在一个有向非循环图（DAG），而这通常限制了搜索空间在几百节点内。鲍尔等人调查了相关的目标导向技术和以层次为基础的方法。他们的CHASE算法可以在最低10微秒的延迟下寻找到道路网络的最短路径。Sanderset等人表明，有效
5、地在资源非常有限的移动设备上实施CHASE算法，可以实现大幅度提升服务器的机器运行Dijkstra算法时速度，并证明了这个做法是可行的。Kieritz等人解决了如何实现商用硬件集群上的CH预处理的技术挑战。虽然它们的描述主要是指CH的一个依赖于延迟的版本中，所有的技术也只适用于静态的道路网的工作。我们为有兴趣的读者在路线规划算法的研究进行了概述。3.实施这两种实现都已经在C +中完成，并开放了源码。因此，代码是可以提供给万维网上的任何一个用户。即使需要将开放街道地图作为主要的数据源，它也只需要很少的工作，就可以进一步增加数据源。服务器运行在Linux上，而手持的实施可用于多种运行如设备时，如W
6、indows（移动），Linux版本和Symbian操作系统。对于这两个实施方式的主要部件的算法是相同的。移动版在线上计算路线，而相比之下，许多解决方案只是连接到路由服务器，以达到可接受的查询速度。事实上移动版的实现也确实使用一个不同的图数据结构，这将在后面的段落中详细说明。预处理：我们支持两个主（压缩）打开街道地图格式，如PBF和OSM XML，并使其易于使用在不同的路由配置文件中，例如，汽车或自行车的路由。我们还对预处理进行了优化，使其可以在正常的桌面计算机上运行：我们使用了只消耗适量内存的外部存储器算法。预处理中最耗时的部分被并行化，这种做法已经充分利用目前在大多数现代计算机的多核处理器
7、中。移动数据结构：手持设备的最大的限制来自于有限的I / O带宽的闪存。特殊的数据结构已设计为手持式执行。该收缩层次结构图形成DAG，并被用来构建一个拓扑节点顺序，这大大提高了数据局部性。这些数据结构会被压缩成4千字节的块，这样做的好处是允许随机访问，同时优化了快闪存储器存取。但是因为检索有关的路由，即几何和机动注释信息，占用了大量的时间，所以我们预先计算重要快捷边缘的信息。这些预解压的过程极大地加快远了距离查询。总之，这使得路由过程高效明智的，同时使用的内存量有限。我们可以采用一种低深度空间树的结构是用来促进反向地理编码。另一方面，以正常的四叉树结构，其中每个节点具有四个下分支，我们细分空间
8、分成1024份。这样，我们可以加载整个数据块一次同时减少随机的I / O量。服务器架构：服务器实现的体系结构被选择为可伸缩的关于用户的数量和数据量。例如，组件是彼此独立的。子服务，例如服务的地图瓦片，地理编码，还有路由，被实现为插件，并且可以用几行代码被改变。服务器引擎也不会保存在会话的任何信息，也就是说，它是无状态的。该状态仅保存在客户端，这是一种基于JavaScript浏览器应用程序。这可以很容易地在多个服务器和数据中心分发的服务。到目前为止，服务器必须依靠外部资源来提供地理编码。用户输入自由形式的位置描述，并期望该服务器是纠错。虽然已经有了基本的研究，但现在仅用于出版，它尚未在生产级中实
9、现。表1：统计几个开放街道地图数据集。BerlinGermanyEuropenodes52 7814 182 09419 432 484edges139 10 141 12019 432 484Mobileprocessings203801934spaceMB65002517queryms3583128Serverprocessings345972486spaceMB1111286137queryms81227实验结果：我们在几个公开街道地图提取物里测试了两种实现的性能（参见表1）。服务器实现了测试的英特尔库尔2在2.67GHz运行，而诺基亚N900的ARMv7主频为600MHz，适用于移动版
10、。需要注意的是服务器和移动执行的时间只是勉强彼此相当的，因为每一个实施执行任务时候，另一个功能是没有。另外，路由时间也算在查询时间的一部分。很明显我们的解决方案是速度不够快，无法为用户提供没有注意到任何延迟的服务。当代的解决方案相比，值得注意的是，我们能够生产精确的结果，而被以最快的速度或更快的高档启发。此外，我们对大地图很好地开发了缩放地图大小功能。注意，服务器的数目不包括网络传输，因为这在很大程度上取决于用户是否真的连接上了。瓶颈优化：我们已经看到，实际的路由算法服务器在运行数据顺序的延迟上优于欧洲大陆现有的一百毫秒（手持式）。因此，路由不是瓶颈了，但是其它部件的优化就变得困难。例如，手持
11、式系统花费其大部分I / O操作来检索路径的几何形状和计算机动驾驶方式，而不是计算该路由本身。从另一方面来说，基于服务器的实施方式，带宽和网络延迟是现在最为关注的两个问题。大部分I / O都参与了传送路线的几何形状。因为，该客户端不具有任何映射数据，但只要有像素，该数据就必须被减少。为了应付这个问题，我们应用了两种算法，通过数量级中的命令来有效地减少这种数据。首先，几何是根据经典的道格拉斯普克算法3，可以用来实现运行的启发式变种缩放的时间。其次，一个字符串的经度和纬度坐标对是高度可压缩的。我们可以使用谷歌地图编码折线算法格式，这是简单的，但却有很大的压缩率。我们的实现方法是精心调校，并利用SI
12、MD说明可在现代的处理器上应用。如在HTTP1.1标准定义的最后，zip压缩被施加以进一步减少数据量。3 000公里的长途路由可以编码全部细节却占据不到60千字节的空间。用户通常期望从一个网站的即时答案，在互联网上的延迟是几十毫秒。回答询问低于100毫秒是网络服务通常瞄准的门槛。低算法开销意味着服务器引擎的可扩展性非常出色，即服务器的电子效率主要是受到其网络连接的影响。虚拟服务器与4GB的内存和1800（虚拟）MHz频率上的演示安装能够满足每分钟千余次查询的开销，包括网络传输。扩展功能：在加速技术，我们采用的小搜索空间不仅使我们能够快速处理请求，同时也使我们能够实现实时的新功能。最突出的特点是
13、规划的往返。这包括计算所有终点之间的距离表。以解决一个旅行商问题（TSP）实例，距离表可通过我们的算法电子邮件很快地计算出来，因为我们允许用户中途停站时，TSP实例可以通过启发式以优良的品质得到解决。4.演示说明该演示将突出这两个路由引擎的实时功能。特别重点将是对OSRM往返的过程中计算上运行的最短路径查询，可拖动的路线。此外，我们将显示MoNav的各自的能力与动手演示运行的软件的最新版本的装置。用户今后将能够使用Web服务与他们的计算机。安装在网上运行的服务器引擎的公共演示如下： http:/map.project-osrm.org手持式实现可支持用于多台设备上下载： http:/ Quick支持多种设备的，我们将切换GUI实现到QML。一个不错的到有特色的开放街道地图项目自身参数的漂移将是基于路由的数据质量工具的开发，因为质量和一致性将成为区分地图数据提供商的最重要因素之一。未来的目标方向会是生活交通数据，这将需要提供许多有趣的算法支持。
