实时路由与开放街道地图数据

《实时路由与开放街道地图数据》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、实时路由与开放街道地图数据摘要关于网络和手持设备的路由服务在过去几年变得无处不在，必应、谷歌地图等网站都允许用户在任何时间查找任意位置之间的路由。同样，车载导航装置属于几乎所有新车的现成的设备。开放街道地图项目的可自愿选择空间数据量已在过去五年内迅速增加。在许多领域，数据质量已符合商业地图数据，如果不是彻底超越它。我们基于与开放街道地图数据的工作演示了这两个服务器和手持设备的实现。这两个应用程序在大陆规模的网络拥有数百万街道段提供实时的和详细的最短路径计算。我们也演示出了像拖动路线和往返规划这样

2、较先进的实时功能。1.引言路由已经成为无处不在的与流行的Web服务，如必应、谷歌地图和车载导航设备在几乎每一个新的汽车上都有。我们已经解决了在早期的关于寻找最短路径的道路网络的计算的问题。不幸的是Dijkstra的开创性算法并不适合大规模的图表，并且大多数的计划项目由于它不会产生最佳路由的补偿已经被建议不采用。在过去的五到十年，算法工程社区开发的算法和数据结构为Dijkstra算法提供了大量的加速比，并保证最佳路由。尽管在技术意义上可用，但是这些高效的算法尚未被应用广泛。快速路由最重要的应用是基

3、于服务器的网络服务和手持式导航。虽然这两种使用情况表面上看起来是不一样的，但就其技术挑战和设计可扩展的系统而言，他们大多是相同的。OSRM是一个基于服务器实现的项目，而MoNav是用于手持设备，例如像平板计算机或智能电话的实现。2.相关工作有关于Dijkstra的原始算法的加速技术，该算法工程社区已经完成了大量的工作。在各路口对应节点和街道段边缘都将道路网络建模为图G=（V，E）。将Dijkstra算法利用道路网络的自然层次结构提出分层技术的时候，该算法工程社区提供了目标上的指导意义。有一个较早

4、的复杂方法是带有地标和三角不等式（ALT）的A*算法。弧标志方法可提供最佳的结果，并且它是有大量加速比的顶尖技术之一。分层技术将会跟随长途航线在某些必要的时候及时地进入长途网络，也就是进入高速公路或国道的概念。收缩层次结构（CH）在交易预处理和查询时间方面有一个现成的非常方便的权衡方法。大陆规模的路网可以在约一百个微秒的延迟下对问题进行预处理，并开始运行和查询。CH根据一些措施的重要性来排序他们，并在应用中使用这个排序来试探性更快捷地选择节点。这里，短切削是指节点从图中取出尽可能少的快捷边缘和尽

5、可能被插入到保持最短路径的距离。由此产生的数据结构包括本来的边缘和所有产生走捷径的集合。这个迪杰斯特拉算法仅需要跟随那些导致更重要的节点的边查询就可以了。这意味着该算法工作在一个有向非循环图（DAG），而这通常限制了搜索空间在几百节点内。鲍尔等人调查了相关的目标导向技术和以层次为基础的方法。他们的CHASE算法可以在最低10微秒的延迟下寻找到道路网络的最短路径。Sanderset等人表明，有效地在资源非常有限的移动设备上实施CHASE算法，可以实现大幅度提升服务器的机器运行Dijkstra算法时

6、速度，并证明了这个做法是可行的。Kieritz等人解决了如何实现商用硬件集群上的CH预处理的技术挑战。虽然它们的描述主要是指CH的一个依赖于延迟的版本中，所有的技术也只适用于静态的道路网的工作。我们为有兴趣的读者在路线规划算法的研究进行了概述。3.实施这两种实现都已经在C++中完成，并开放了源码。因此，代码是可以提供给万维网上的任何一个用户。即使需要将开放街道地图作为主要的数据源，它也只需要很少的工作，就可以进一步增加数据源。服务器运行在Linux上，而手持的实施可用于多种运行如设备时，如Win

7、dows（移动），Linux版本和Symbian操作系统。对于这两个实施方式的主要部件的算法是相同的。移动版在线上计算路线，而相比之下，许多解决方案只是连接到路由服务器，以达到可接受的查询速度。事实上移动版的实现也确实使用一个不同的图数据结构，这将在后面的段落中详细说明。预处理：我们支持两个主（压缩）打开街道地图格式，如PBF和OSMXML，并使其易于使用在不同的路由配置文件中，例如，汽车或自行车的路由。我们还对预处理进行了优化，使其可以在正常的桌面计算机上运行：我们使用了只消耗适量内存的外部存

8、储器算法。预处理中最耗时的部分被并行化，这种做法已经充分利用目前在大多数现代计算机的多核处理器中。移动数据结构：手持设备的最大的限制来自于有限的I/O带宽的闪存。特殊的数据结构已设计为手持式执行。该收缩层次结构图形成DAG，并被用来构建一个拓扑节点顺序，这大大提高了数据局部性。这些数据结构会被压缩成4千字节的块，这样做的好处是允许随机访问，同时优化了快闪存储器存取。但是因为检索有关的路由，即几何和机动注释信息，占用了大量的时间，所以我们预先计算重要快捷边缘的信息。这些预解压的过程极大地加快远了距