东南亚的超级APP是如何用Go打造Grab的路径规划和ETA引擎

胡泊：Grab/地图团队资深架构师。

入行10年，前端、后端、大数据均有涉猎。现就职于Grab，从零开始搭建了Grab路径规划服务，经过三年努力，在多项指标上击败国际地图服务商和东南亚本地地图服务商，成为Grab业务的主要支撑力之一。

大家好，我是来自Grab的胡泊。非常荣幸有机会跟大家分享我们是如何用 Go 搭建Grab路径规划和EAT的引擎。本次演讲我分以下几个部分：

一、Who’s Grab

二、团队角色

三、路径规划和ETA引擎的构建和演进

四、Go in Grab

Who’s Grab

首先什么是Grab？去年 Gopher  China大会上，我们自我介绍我们是东南亚最大的出行平台，但是不想做送餐的出行不是好支付，我们在收购了Uber东南亚的业务后，开始在出行、送餐和支付等各个领域发力，希望成为东南亚的Super APP，简单说就是滴滴加美团加蚂蚁金服。

团队角色

什么是路径规划呢？就是给定起点和终点，规划一条合理的路径。什么是ETA呢？它是Estimated Time of Arrival的缩写，在我们业务场景中的意思就是给定一个路线，预计一个行驶的时间。这个词在英语里面还有一个含义就是"什么时候能做完"，所以当我在公司内部交流 工具 里把ETA加为关键词，一出现就发提醒后，全公司无论哪里出了问题，我都会被提醒，不幸成了全公司的oncall。

业务场景

派单

下面介绍一下路径规划和ETA在我们场景中起什么作用。大家对于出行和送餐业务场景非常熟悉，用户下单第一步就是要找到一个合适的司机或者找到一个合适的骑手，而准确计算司机到达时间和合理的骑手路线是派单中不可缺少的环节，小而言之它会影响每一次消费者和用户的体验，大而言之它会影响平台的效果。平台之间的竞争最核心的就是用户的体验和整体的效率，所以这是支撑我们平台最核心的引擎之一。

计价

计价同样离不开准确的距离和时间计算。我们计价特点和国内不一样，我们是一口价，当乘客决定起点和终点，就要给出固定价格。生活中，我们会遇到很多在异国或是一些地方打车时，明明是直线，在没有Grab时，打出租车，上车后司机就开始绕行，乘客在这情况下往往没有安全感。为了给用户带来安全体验，让他们安心，我们决定一口价。当然这也就给我们带来压力，乘客安心了，但是如果把钱算少了，司机肯定就不干了。

司乘体验

下面谈谈司乘体验。当我们叫到一辆车，不仅显示司机什么时间到，而且会展示路线和路况，这样乘客会知道司机堵在哪儿，缓解未知的焦虑。还有ERP，这是新加坡的收费站，他们收费站跟我们收费不一样，他们在道路埋了磁感线圈，车辆经过时就会收费。这个乘客在车上很难感受到，而我们知道行使路线和状态，所以会主动给乘客发推送，让乘客清楚知道价格为什么发生变化。

另外我们非常重视安全，因为我们知道预计行使轨迹，还知道司机的位置、速度等一些实际状态，这样我们就能检测异常。司机是否在超速，是否逆行，或者明明这段路很顺畅，但是检测到司机发生异常停留，那可能就是发生了这两种情况: 要么司机出了车祸，要么发生一些不安全事件，我们安全组会迅速采取行动降低这种事件的发生。

综上所述，我们路径规划和ETA是公司出行和送餐非常底层的技术引擎，支撑公司和用户体验和效率。

路径规划和ETA引擎的构建和演进

下面详细介绍一下我们搭建ETA系统的历史和心路历程。在Grab北京研发中心刚成立时，有一天 CTO 把我们叫到一个会议室，在白板密密麻麻画了一个线团，然后点了两个点，说我们有东南亚最丰富轨迹的数据，我们能不能从中计算出 A 点到 B 点的时间。大家面面相觑，然后他又接着问了我们一个直击灵魂的问题，ETA是什么？(什么时候能做完？)。领导发话了，我们就要找到解决方案。领导说的直接根据轨迹计算ETA ，其实还是探索领域，暂时没有很好的工程落地实践。我们还探索了一种方案: 把地图打成一个个格子，把两点间的时间计算转移成格子间概率转移的计算。但缺点是格子的大小很难定义，太大准确性无法保障，太小复杂度很难控制，最终我们还是决定把路网抽象成图，把问题转换成图搜索问题。

地图

开源地图OSM

既然我们决定了大的技术方向是要用循路算法，那第一个问题就是：地图在哪儿？这一幅图是达芬奇的《救世主》，表达了我第一次见到OSM时的内心感受。相信大家都从开源软件收益很多，有很多伟大的软件让我们使用，这是我第一次发现还有开源数据这样方便实用的东西。

OSM发展历程

简单回顾下OSM 的发展历程: 它在2004年最开始是众包的形式，鼓励地图爱好者通过骑车和驾驶收集GPS数据，然后编辑后上传。很快，互联网巨头敏锐嗅到了其中的商业价值，纷纷加入了贡献数据的行列。最早他们用测绘车采集数据，但是这个成本非常高，效率非常低。像今天 Facebook 更多采用 AI 的手段，通过卫星图像识别，自动化把地图补上，这个大大降低成本，提高效率。

虽然这些巨头在补充这个数据，但是我们面临的问题是这些巨头们的商业范畴主要以欧美为主，以及OSM在欧美比较活跃，在亚洲的参与者比较少。我们刚接触这个项目，探索地图质量，发现以北京为例就是五环以内的主要道路有，五环以外很可能是一片空白，而且里面缺少了很多的毛细血管的道路，所以我们首先要做的就是补充数据。不但要补充整个路网信息，还有补充路的属性，比如确认这条路是不是单向路，是不是有禁止左转，这都是为了图的连通性完整。补充数据来源也是刚才CTO提到的: 我们有东南亚最丰富的轨迹数据，同时我们还采集街景图像。

路网学习

下面介绍我们经过迭代非常行之有效的方法。我们最后采取的是图形学的方法，最左边是一个GPS轨迹点的图片，准确说是map matching失败的点。随着不断有司机经过，GPS累积，我们就能找到这一块路的轮廓，这一块就是疑似缺失的道路。我们把这个转换成图形学问题，通过一系列灰度化，找轮廓，找中心线的操作，我们就比较准确找到缺失道路的位置。我们会把这些数据给我们离线团队进行审核编辑，帮助我们补充路网。

这是经过我们这些努力，使雅加达2016年基本空白到现在基本上把“毛细血管”补充非常完整。整个Grab团队在这几年和离线团队配合，总共给东南亚补充了超过10万公里的道路。这些大概相当于绕赤道两周。而且这些数据我们都回馈给了开源社区，如果大家想到东南亚创业，也可以使用这些数据。

司机定位

有了地图，其实还是不够，刚才提到了，我们最核心的问题是要根据两个点来计算一个路径或者是一个时间，这两个点的准确性实际也是非常重要的。这个图有一点点夸张了，很多年前一个顺风车的截图，看到这张图司机还在朝鲜半岛，隔海相望，不太顺路。

GPS误差

刚才那个例子有些夸张，我们实际遇到的主要问题是GPS的会受到天气或者高楼被干扰信号。如图，判断司机到底行驶在绿色点的路还是蓝色点的路，这是我们要解决的问题。  

刚才也提到了一个词：可能性，所以我们把这个定位问题转化成概率问题，通过概率模型解决，我们选择的是隐马尔可夫模型，这里其实是经典的解码问题。这里稍微介绍一下HMM，它的核心是有一条隐藏状态链，一条观测状态链，还有状态间概率转换的模型。

我们这里观测状态就是GPS点，隐藏状态就是司机到底真实的位置是什么？下面我们通过建立这个模型解决这个问题。

这张图就是红色点是GPS点，就是我们观测状态，我们第一步要找到的就是所有可能的隐藏状态，我们适用一个RTree进行搜索，把GPS点投射到附近道路，这样就有了备选的点，在四个备选点找出哪两两相对可能性最大。这里给大家介绍一下，发射概率就是隐藏概率和观测概率转移的概率。我们的场景中就是GPS点到这个路的投射点的一个垂直距离，这个大家非常好理解，如果这个距离比较近可能性就比较大。

还有转移的概率，就是两个隐藏状态间的转移概率，这里就是候选点间导航距离和直线距离的比例。这个也很好理解，因为这是一个时序的序列，如果这两个投射点导航距离绕很大的圈这个概率就非常低。有了算法，下一步就是要解决和面对工程的问题，首先我们做了一些过滤，去掉了低速的状况和路口的状况，下一步最核心的问题是管理海量数据，我们有数百万在线司机，会上传海量数据，而且这些数据要在各个微服务之间进行传播，这么海量的数据需要一些手段进行处理。

第一个方法就是剪枝，在这个距离导航过程中，如果探索需要很长时间，我们要快速丢弃掉。

第二个方法是用谷歌的方法，坐标点大家非常熟悉，就是两个经度纬度两个浮点数，谷歌怎么做呢？它把浮点数转换成整数，然后不用再存每一个坐标的具体值，而是只需要增量可以了，也就是第二个坐标和第一个坐标的差，这样就只需要存一个几百或者几千这样的小整数，这样就能很好的节省空间。

我们还用到了Golang的gob。大家对protobuf都很熟悉，而Golang提供的gob不需要额外的schema，只要复用struct结构就可以，效率也非常好。这也是我们对于Golang很深的感受。就是他在保障性能的基础上，让代码写起来很简单舒服。 

我们花这么长时间定位这些点，也不只是为了定位起终点，一个个点定位准之后，再通过聚集实际就形成了路况数据，这是导航中不可缺少的因素。这张图是雅加达日常“宁静“的夜晚，我第一次去雅加达出差晚上12点飞机，7点我还在办公室，领导说你怎么还不走?我想我怎么也是在北京堵过的人，但是雅加达3000万多的人口，跟北京一样多的车，或许还有同样多的摩托车，再再减去大家遵守的规则，就形成了非常混乱的路况。东南亚的城市大家可能旅游过，泰国、马尼拉各个城市都是这样，路况对我们非常非常重要。我们面临最核心的问题，想分享一下还是海量的数据。

路况

路况支持了多个业务产品，比如说我们要去更新这个权重，我们要把路况渲染铺到APP界面上，其中还有一个情况给我们造成非常大的压力，就是给机器学习提供路况特征，这个特征是这样的，每一次计算我们要把这个结果拆成每一个路段，每一个路段获取这个路段的路况信息，这相当于我们这个路况的量相当巨大的ETA的QPS乘以平均路段分解的数量，这个达到几千万的量级，非常可怕。最早我们很天真，直接上Redis，一个节点不够就上六十个，万万没想到依然无法撑住海量的读操作。

我们最开始的优化就是加内存缓存层，我们实现了RingBuffer的结构，维护的值是这个路段的过去数个时间窗口不同的值，这样我们就把读 Redis 做了平滑，压力大大缓解了，可以支撑我们的业务，但是这个带来新的问题，每一个Client不得不在内存维护这样数据，带来了内存和CPU的消耗。我们继续演进，下一步的想法就是用Spark Streaming来做增量化让客户端读取数据。这也很方便定制聚集化，路况是有不同的时间段，有的需要5分钟为窗口聚集，也的需要1分钟，这样可以通过订阅不同的流来解决。这里一些详细的信息不方便透露，在申请专利。

有了地图、有了定位，有了路况，数据已经备齐，我们开始面对算法问题。这个图大家看起来非常亲切和怀念，Dijkstra，一下把我们带回大学课堂。这是大家最熟悉最经典的一个算法，但非常遗憾，我们业务量非常大，它无法支撑住我们业务量。我们就寻找和研究新的寻路算法，最核心的思想是用预处理换一个快速处理时间，通过预处理提高查询速度。我们最终选择了CH，这个算法做到了预处理时间和查询时间非常平衡。他有一个核心的思想，他希望当距离比较远的时候，在搜索时只探索相对重要的道路。比如说搜索中关村到国贸，我们肯定不希望在图搜索过程当中过多搜寻回龙观小区的路，而希望直接引向四环。

举一个例子详细介绍预处理的过程。顾名思义，CH的意思就是压缩和分层。举一个极端的例子做一个简单的解释。这个图在现实不太可能出现。我们想选寻找1到15的路径，在传统算法中就是一个一个节点探。CH怎么做的呢？首先分层，大家可以看到每一个节点落到了相应不同的高度，这个是层级。这个层怎么用呢？预处理之后，跑的是双向Dijkstra，他要求找1到15，首先从1和15两个方向照，1正向找，15反向找，都只找更高层次的节点，大家看原来4到8，5到11节点，这样明明存在通路被打断了，他的处理方式是增加了快捷边，通俗地说，当出现4、5、6这样的波谷，就会建立4到6的快捷边，快捷边基础上会不断创建新的快捷边，建完了这些快捷边之后，一是这个论文论证了一定会确保结果的准确性。二是看到大大提升了这个查询的效率。原来1到15这么多路的查询，变成双向快速几步可以做到，这就是CH大概的中心思想。 

有了CH算法，我们解决算法层的问题。下面也遇到了很多性能的问题。我们也是通过调优过程中找到一些小的点，跟大家分享一下。第一是一定重用map/slice。第二是图的结构，经典的图结构是临接链表等，我们的经验是flatten成一个长的数组，这样可以减少内存的开销。下面有一点反直觉，坐标是一个经度、一个纬度，这是WGS84坐标，实际上还有其他的坐标，比如墨卡托投影坐标。当 程序员 发现不同类型的坐标，第一反应就是抽象一个接口。但是当发现程序里面有数亿的坐标，这个接口本身的开销就不能忽视，所以接口的使用也需要谨慎。我们首先还是要考虑性能问题。

下面分享图权重调优。这个图很有意思。权重并不一定是距离和时间，我们不一定找最短的路和最快的路。我们希望找到的路是什么样的路？最快也未必是最好，最短也未必是最好的，可能司机最愿意走的路才是最合理的，我们就通过运筹学方法找到权重。这个优化的过程刚才提到了，这个指标的差值越来越小，我们也是不断训练，希望让这个权重不断合理化，让我们能够找到的路径变得越来越合理。

可能有了以上的这些数据，能支撑大业务量的算法，对于传统的导航公司已经基本够用了。我们为什么还要继续用机器学习的方法调优呢？因为我们面对两个非常现实的问题，第一个我们在初期地图的质量还是没有保障，所以需要机器学习弥补这个措施。还有很重要的场景刚才提到了，叫到一个司机显示司机到达时间，这个时间并不长，就是两三分钟。但是在东南亚大家很难想象，他们几乎不会用导航软件看路的，尤其东南亚很多都是摩托车、蹦蹦车。司机都是老乡问路，不认识路就下车问，所以不得不把行为因素考虑进去。能想到的方法就是用机器学习方法进行调优。我们想到一些特征，比如说红绿灯数、转弯数还有司机画像，不断演进过程。

从这个图可以看出，我们使用的XgBoost模型有成千上万棵树，在树里通过不同的特征得到调整值，最后最后汇总，这听起来就非常适合Go语言。Go语言就是性能保证情况下，写起来非常顺畅。但是我们这里也踩了小小的坑跟大家分享一下。离线训练模型还是主要用Python，在dump它训练出模型给线上Go使用时，发现小数定五位之后精度无法保证，出现一些随机性，导致线上和线下不一致。可以通过数字整形化，避免跨语言出现这样一些问题。

下面分享下线下海量数据训练和模拟。由于Spark对Go支持不好，我们自己写了一个简单的分布式的系统进行任务的分发和管理，好处是复用了线上核心代码。我们Grab分实际环境和测试环境，在测试环境复用这些环境，在这个时间跑这些任务。有了这个系统之后发现大大提高了我们自己训练和模拟的效率。

同时Grab是非常注重数据驱动的公司。我们想上任何一个新模型和版本，可能经过测试，在Grab内部也有一个实验平台，可以非常方便帮助配置化使用，你可以定义一个时间周期、一个车型，只要配置好，就会自动帮助你组织试验，同时又完善的数据通道，这样可以通过数据决策，到底你的模型是否合理。

Go in Grab

下面大概给大家介绍了流程，再就是介绍Go  in  Geo。我们为什么用Go做系统？

第一是Grab系统中Go性能非常好。同时我们发现Go语言对于地图环境非常多好用的工具。简单介绍几个：第一是支持核心的地理几何计算，这个非常方便；第二是处理OSM地图的工具，第三是很有意思是MapBox实现的开源地图渲染引擎，非常方便自己搭建一个地图。后面不一一介绍了，都非常方便。

Grab内部也是有成百上千的微服务。我们在过程中有非常方便的工具，就是GrabKit，你注册之后自动生成非业务的相关代码，这样可以专注在业务层面，大大提升了开发的效率。

第二个是Gandalf，是自动测试的平台，可以方便帮助我们进行各种API的测试。

第三是Golangcamp，新兵训练营，任何一个人加入Grab，会在这个训练营实践训练代码。同时Grab非常推崇Gopher ，我们也在新加坡、越南支持了Gopher 新加坡、越南。还有我们Grab内部的Gopher大神写的Go DI的书。

我们还在持续的招聘。Grab总部在新加坡，在全球各地也是有多个研发中心，其中北京是最大的一个海外的研发中心，主要负责的业务包括刚才提到的送餐，这也是我们在全力发展的新业务，第二是地图，通过我的分享，如果大家觉得地图也比较有意思，欢迎加入我们。

Grab崇尚奋斗，但觉得奋斗不等于996，在955名单我写PPT的时候排在第9位，我们不在加班的互联网公司行业内，以上是全部分享，谢谢大家。

GO 中国征稿啦！

自“Go中国  ” 公众号上线以来，因为扎实的干货（害羞）、前沿的解读（娇羞）、满满的福利一直深受 Gopher 们的喜爱，为了给大家带来更具实力的干货以及 Go 语项目开发经验，我们将开始对外征稿！

现在我们开始对外征稿啦！如果你有优秀的 Go 语言技术文章想要分享，热点的行业资讯需要报道等，欢迎联系在菜单栏回复“投稿”“合作”联系我们的小编进行投稿。