入职新公司以来的第一项任务就是参与原有导航系统的重构。原有的导航系统基本上就是在高德地图API的基础上做了一次封装,现在希望能慢慢建立自己的导航系统。
一般来说,导航系统可分为以下部分:
1、地理基础数据。包括地图、天气数据、交通数据、行政规划数据等。国外来看的话,地图数据较为开放。国内的话,地图数据的保密性比较高。一般具有测绘资质的公司才有资格进行地图测绘,拥有地图数据。获取地理基础数据的通道就是通过这些公司,例如高德、百度等。或者有些有钱的直接购买地图数据,但是这样一来地图更新的难度就比较大了。另外一方面,可以通过开源地图的方式获取地理数据,通过OSM(Open Street Map)等平台可以下载数据,但是这些数据在精度的和实时性上是没有办法保证的。(数据下载地址: http://download.geofabrik.de/);
2、底层算法实现。当我们拥有地图数据的时候,就要考虑如何通过相关的算法实现例如:最短时间、最短距离、最低成本等功能。这些都可看做为导航系统的基础功能。说道最短理解算法,不得不提到的是迪杰斯特拉算法,可以算法最短路径算法鼻祖一般的存在。但是由于其本身的效率问题,在工业应该中往往不会直接使用迪杰斯特拉算法,而是对算法进行改进。目前应用比较多的有:A*算法,CH(Contraction Hierarchies)算法,以及由微软硅谷研究院三名工程师提出的Crp(customizable route planning) 算法,这个算法目前被应用在Bing地图中。
3、业务系统实现。有了地理基础数据,并且实现了算法之后,你就可以结合实际的业务需求,真正开始导航系统的开发。
分析完导航系统的组成部门之后,我们来探讨以下具体的实现方案。我将实现方案分为三种:
1、完全借助第三方API来实现,借由第三方的地图数据和算法接口实现,例如上面提到高德以及百度API。优点:开发难度低,地图数据更新效率高,算法应用较为成熟,精度度高;缺点:财力成本大,核心技术难以掌握,对第三方依赖大,难以加入具有本身特色的导航系统,因为是通过远程web服务调用实现的,请求响应速度无法保证;
2、借助第三方提供的地图数据,自己完成算法和业务逻辑实现。优点:开发财力成本低,核心算法实现自己掌握,可加入自身已有运营数据,本地部署服务,响应速度快;缺点:开发技术难度较大,人力成本高,算法实现效率可能需要稳步提升;
3、借助开发数据和自身已有运营数据整合为地理基础数据,自己实现算法。优点:导航系统架构自己控制,无需额外购买第三方资源,缺点:地图数据准确性无法保证,开发技术难度大。
在具体的实现中,可以根据自己公司的特色进行导航系统的开发。个人比较倾向于第二种方案。此外,这里推荐一些开源的地图导航算法库:
/wiki/Routing,对基于OSM数据的导航实现库进行了一个总结,开源在这里找到很多有用的资源;
推荐两个不错的开源库:
OSRM(Open Source Routing Machine),/Project-OSRM/osrm-backend
C++编写的导航路径计算库。给定两个地理坐标,通过OSRM可以计算其间的路径、距离、交通时间,并提供 HTTP 和 C++ 的接口,提供的服务:
Nearest :根据坐标查找最近的匹配目标;
Route:查找坐标间最快的路径
Table :计算路径上坐标之间的时间和距离
Match:捕捉GPS噪点
Trip:旅行商问题(Travelling SalesMan problem),寻求单一旅行者由起点出发,通过所有给定的需求点之后,最后再回到原点的最小路径成本。
Tile :生成Mapbox矢量切片
优点:
导航文本支持中文,支持汽车、自行车、步行模式,也可以通过profile定义进行定制化
GraphHopper(/graphhopper/graphhopper/):GraphHopper是一种快速且内存有效的Java导航引擎,默认使用OSM和GTFS数据,也可导入其他的数据源。支持CH(Contraction Hierarchies)、A*、Dijkstra算法。
分为两个版本:开源和商业版本,
具体情况参照另一篇博客:/haochajin/article/details/99851216