AI的浪潮势不可挡，在无数大众最熟悉的生活场景中，其实蕴含着许多未被发现的秘密。这些“深藏功与名”的AI技术，在最基础的功能背后，却演绎着数据和算法最动人的一面。百度地图将通过揭秘黑科技一系列专题，讲讲地图日常功能背后的技术。

本期内容将为你展示地图导航中，算法与千变万化的道路信息之间的“斗智斗勇”，如何对地图中常规的路线规划进行改造，让“未来出行”成为可能。

所谓路线规划就是“两点之间直线最短”的简单明了吗？——天真。

要知地图产品在为用户规划路线时，那可是一场人类与复杂算法、道路信息之间的斗智斗勇。百度地图的算法工程师们，不仅要面对瞬息万变的路况信息，还要应对各种各样“意料之外情理之中”的干扰。所以如何综合利用好各类信息，快速提供准确有效的出行方案，就成了“路线规划”要解决的切实问题。

小王是一个在北京西二旗工作的资深“码农”，虽是地道的北京人但因为多年摇不上号只好暂时上了外地牌照。由于五环在工作日早晚高峰期禁止外地牌照车辆行驶，小王上下班通常会绕开五环或者早早出发躲避限行。周一早上，公司组织集体去西五环附近的北京园博园参加活动。早上8点40多，大家都准备从公司出发了，因为此时五环还是限行状态，不少人凭着习惯绕路上了六环。小王打开百度地图查路线，导航却提醒他：再等5分钟后出发，就可以避开限行时间直接走五环。既能节省时间和油费，还不会违章。最终小王虽然多等了5分钟，却比其他人早到20分钟，还少走了一半路程。

百度地图路线规划示意图

“多等5分钟少走半程路”的背后是一整套路线规划的复杂流程，算法为用户规划路线时，通常要经过路线规划、特征提取、路线筛选和路线排序四个步骤。如今用户的要求越来越高，仅仅是“当前时刻”的路线规划已经很难满足实际需求，但目前大部分地图导航还无法结合实际情况推荐出发时间和路线，导致用户常常白费了大量时间。百度地图这种通过预估未来交通状况并提供躲避拥堵、限行路线的方式，成了受欢迎的新趋势。换句话说，有了百度地图，人们出门前临时查找路线，却发现一路飙红“无路可走”的年代很快就要翻篇儿了。

那么，百度地图是如何改造路线规划的四个步骤，满足用户智能化出行需求的呢？

第一步 针对时间规划路线

为了实现根据时间推演进行路线规划，常用做法是将连续的时间点分散成多个时刻，在每一个时刻都生成一套权值，并在路线搜索过程中恰当切换不同权值，从而实现针对时间进行路线规划。在算法选择上，一般要考虑预处理时间、在线计算性能、路线效果等要素。A*算法和CRP算法（基于剖分的路线规划算法）由于预处理时间较短、数据较小，天然具有快速编译及生效的优点，是面对此类问题的主流选择。

第二步 基于海量数据合理预测

有了完整的路线数据后，可以获得更加精确的预计到达时间，这也是算法进行后续决策的基础。由于预计到达时间与路况息息相关，二者都有着丰富的历史数据作为参考，在进行未来时间预估时，算法可以根据历史数据和当前道路状态合理预测，从而保障路线规划的准确和智能。

第三步 借助通行规范筛选路线

路线筛选主要结合预计到达时间和用户车牌号，通过限行、交规、封路等通行规范，筛选出符合车辆需求的合理路线。百度地图在路线筛选环节已经做到了秒级生效，而利用精准的预计到达时间，则能为用户提供更多选择，例如是否立即出发，还是等一段时间避开限行再出发。

第四步 “为用户着想”的路线排序

在向用户推荐3条最优路线时，需要引入对未来路线状态的判断，但随之也带来了新的难题，例如上文中提到的“外地牌照如何走五环”和各种突发情况。

面对“即刻出发但要绕行的六环”和“等几分钟再出发的五环”该如何选择？百度地图一方面通过“常规路线”，即大部分用户选择的路线或用户自身曾走过的路线，过滤掉没有意义的绕行。另一方面，通过衡量不同路线的代价综合筛选。因为每个人对时间代价、距离代价的感受不同，意味着每条路线背后的算法模型，都在逐渐被“主人”养成个性化推荐，通过用户以往的驾驶行为和操作偏好，推荐更适合路线。

当路上遇到突发情况导致预计到达时间不准，可能引起用户违章时，算法往往会做“最坏的假设”。举个例子，早上六点半一辆外地牌照的汽车行驶在北京的五环上时，一场交通事故导致了大面积堵车。这时路线规划将考虑到这一点，对于那些不能帮用户在规定时间内驶离五环的路线慎重考虑，排序中可能会放到更靠后的位置。并在导航过程中，不断检测前方通行状况判断用户是否有违规风险，并通过语音、图像提醒指引更合理的路线。

在这场算法跟道路信息之间的斗智斗勇中，百度地图不仅能处理好纷繁复杂的各类信息，还能让它们“为我所用”，以这些信息为指标提供最优的出行选择。当“未来时刻”成为用户越来越重视的核心要素之一，更智能化的导航规划也将成为未来趋势。

以下为整理的百度地图ETA算法推荐：

一个路线规划的请求，一般要经过几个步骤

1、路线规划，根据用户的起终点、偏好、车牌等信息，进行路线规划

2、特征提取，获取当前路线的所有特征，为后续的路线筛选、排序做准备，这里的特征主要是指通行时间、道路拥堵情况等路线信息

3、路线筛选，根据当前时刻所生效的限行、交规、封路等信息，将不符合通行规范的路线进行剔除

4、路线排序，针对所有合理的路线，根据模型进行智能排序，挑出当前最优的3条路

随着用户对智能化出行的要求越来越高，以上步骤中的“当前时刻”已经很难满足用户对于智能化出行的要求，“未来时刻”成了用户越来越重视的核心要素之一，这正是导航智能化最集中的体现。

所谓“未来时刻”，是要把用户这次导航过程中可能遇到的事情都尽量考虑到，因为很多信息是动态变化的，例如道路的拥堵程度，其实是会随着时间的变化有一定变化规律的，再例如现实世界中的各种限行规则，是有着明确的限制区域和限制时间的，如何综合利用这些信息去为用户提供最优的出行选择，是路线规划服务最核心的内容，那么我们看下如何对以上步骤进行改造来完成用户智能化出行的需求。

对于路线规划的要求是，可以根据时间的推演进行路线规划，不再是仅仅考虑当前时刻。由于路线规划的原理是在一张带权有向图上搜索最优（或次优）路线，常用的做法是将连续的时间点离散成多个时刻，从而在每一个时刻都生成一套权值，并在路线搜索过程中恰当的切换不同的权值，从而实现针对时间进行路线规划。

针对路线规划算法的选择，一般要考虑的有要素有预处理时间、在线计算性能、路线效果等，CH路线规划算法，由于预处理时间过长，面对多套权值同时编译，难以胜任此类需求；A*算法和CRP算法具有较短的预处理时间和较小的预处理数据，天然具有快速编译及生效的优点，是面对此类问题的主流选择。

此时由于已经有了完整的路线数据，可以获得更加精确的ETA（Estimated Time of Arrival，即预计到达时间）信息，ETA信息是进行后续决策的基础，估时的准确性直接影响了用户对产品的体验。ETA信息与路况信息息息相关，二者都有着丰富的历史数据，从而可以根据不同时刻的统计数据和当前的路网状态进行合理预测，从而进一步提升路线规划的智能化体验。

对于路线筛选的要求是，需要结合实时ETA数据与用户的个人信息（主要是车牌信息），对路线上的限行、交规、封路等与时间相关的要素进行精确判断，从而筛选出符合用户所设置车辆的合理路线。那么这里有一个问题是，既然路线规划环节已经对即将发生的限制类通行信息进行了应用，路线筛选的意义何在？主要是由于以下两个原因：

（1）时效性方面，路线筛选环节可以做到秒级的生效，时效性上路线规划，能够更加严格的控制产出路线的合理性；

（2）可以利用精准的ETA数据，为用户提供更多的选择，例如是否立即出发，还是进行一定时间的等待再出发。

此步骤的主要目的是将用户最有可能选择的3条路选出，区别于传统的路线排序方法，这里需要引入对未来路线状态的判断，而这个变动又会带来新的难题，例如：

（1）面对一条等待一段时间出发的路线和另一条即刻出发但是需要额外绕行的路线如何选择

①如果选择了绕行路线，怎么保证这条路线是合理绕行而不是在限行区域之外无意义的兜圈

②如果选择了等待路线，这个等待时间是否过长从而导致用户无法接受

这类问题的主要解决思路是：

①通过定义“常规路线”的方式来过滤掉无意义的绕行，常规路线主要包括：

a. 一对起终点之间大部分用户选择的一条或多条路线

b. 此用户在这对起终点之间曾经走过的个人熟悉路线

②通过衡量不同的出行方式引入的时间代价、距离代价、出行体验（例如拥堵状况）来进行综合筛选，这里往往会借助大量的用户点选数据进行训练从而做出更加趋于合理的选择

（2）如何解决由于突发情况引入的ETA不准从而导致的用户违章，解决思路主要分2部分：

①往往做最坏的假设，这个假设就是，道路通行状况逐渐恶化，所以针对这类用户可能难以逃出限行区域的路线，排序环节往往会给予更慎重的考虑

②在用户导航过程中，不断检测前方的通行状况从而判断用户是否有违规风险，通过不同的产品形态（例如语音、图像、交互等）来指引用户进行更加合理的选择。

　　欢迎关注“创事记”的微信订阅号：sinachuangshiji

　　百度外卖终于卖了。再次印证了中国互联网江湖的一条铁律：老大和老二打，打没的是老三。

　　无论以后百度外卖以何姿态示人，一个事实是，它错过了一条不止百亿美金的赛道。看看美团和饿了么的估值，就会知道这个教训有多大。

　　更重要的是，这也宣告了百度O2O战略的彻底终结。百度O2O战略始于地图，终于外卖。而所有的故事，都从2013年的两场收购未遂开始。

　　那年初春，我去采访俞永福。当时的UC正在风口浪尖上，一会腾讯收购、一会百度收购，甚至周鸿祎也偶尔进来敲一竹杠。UC就像苏州街上一位抢手的大姑娘，不停被媒体卖身。

　　‘卖艺不卖身，这是UC的底线。’俞永福底气十足。春节前，雷军刚刚送他一辆Model S。采访结束，俞永福还不忘提及那句日后被各路媒体反复提及的话：‘雷军说，永福做什么都支持。’

　　2012年，小米手机第一年就卖了100亿，那个时候的雷军应该给兄弟们发红包、买豪车。京东GMV做到100亿用了6年，百度则用了整整10年。所以，2013年春节前，李彦宏急了，开始呼唤百度的狼性。

　　为什么急？因为狼来了。到2013年，移动端开始取代PC端成为互联网的主要流量入口，微信眼看就要成为腾讯新的獠牙，阿里IPO在即，李彦宏一回头，发现死对头周鸿祎提着刀过来了。

　　周鸿祎的刀是360手机助手。用了不到一年时间，这个依靠PC端强力导流的应用分发渠道就在2013年年初跻身第一阵营，除它之外，还有网龙的91助手+安卓市场，以及如日中天的豌豆荚。应用宝、百度手机助手这些富二代，还只是准一线。

　　李彦宏跟当时百度‘太子’李明远说，时间不等人，想不明白也要试（买），我们摸着石头过河吧。李彦宏不可能摸360手机助手，周鸿祎也不会让他摸。

　　时任百度副总裁、负责投资并购业务的老大汤和松说过一段话，大致可以还原李厂长和百度的过河逻辑。‘从PC到手机，其实就是跨过一条河，怎么过河？两种方式：一是架桥，一是坐船。买手机浏览器是架桥，买应用商店是坐船。’

　　2013年的中国，UC就是手机浏览器，手机浏览器就是UC。2012年年底，UC全球用户突破4亿，而手机百度达到这个数字比UC整整晚了一年。换句话说，在2013年春节前后，百度没有一款产品的用户数超过UC。所以，摸UC成了李彦宏的首选。

　　百度对UC的报价就发生在春节前后。一位投资人后来跟我说，报价一路涨达到12亿美金，全部用现金。说白了，就是创始团队套现走人，百度生吃一个4亿用户的大金蛋。要知道，微信在2013年年初才刚刚突破3亿用户，手机淘宝过了当年夏天才突破3亿用户；如果买下UC，李彦宏至少能睡个安稳觉了。

　　但是UC团队不从。这笔账划不划算，在一年后阿里巴巴的上市招股书得到验证：2013年3月，阿里曾对UC战略投资31.3亿人民币，12月，又支付了11亿现金进一步增持，总计获得UC 66%的股份。没错，控股了，但重点不是这里。

　　2014年6月，阿里收购了UC Web全部剩余股权，对价为4.79亿美元现金+1230万股限制性股票。1230万限制性股票意味着什么？如果阿里巴巴上市市值达到2000亿美金，这部分股票的价值就是10亿美金，加上之前三次注资，UC的估值也就是后来大家所熟知的近50亿美金。

　　‘通过这种方式，能够让UC的同事享受到阿里的IPO增值和业务成长带来的增值。’俞永福说的很直白了。

　　12亿美金和50亿美金哪个大？问题是在2013年，谁也看不出来，当时的阿里估值在800亿美金左右，远远高于百度的市值，百度如果给股票，增值空间是不是更大？但百度不给。

　　几个月之后，百度拿下了91助手，同样全部是现金，19亿美金，创造了中国互联网历收购史的记录。这个价格比给UC的最终报价多出整整7亿，而7亿美金正好是百度最早对UC的报价。

　　后来雷军在饭局上遇到汤和松，开玩笑说一开始觉得这么高的价格买91怪怪的，没想到这个交易带动百度市值涨了90亿美金。但雷军同样没想到的是，阿里会涨到4000亿美金。今天来看，特斯拉送对了。

　　雷军送别人特斯拉，李彦宏自己造无人驾驶；雷老板广结善缘，李厂长尽在掌握。表面上看，是百度错过了UC，实际上是李厂长错过了UC团队。

　　除了UC，另一家公司也曾被百度摸过，这就是高德。我在《AT巨兽诞生记：掀桌、爆买、血洗赛道》一文中说过这么一个故事：

　　当年百度内部对‘是推地图产品，还是买一家现成的公司’，有过纠结。后来买下高德成为主流声音，并且很快与高德团队谈的差不多了，但最终高德团队发现，他们与百度收来的小公司没啥差别，因为李彦宏根本没有打算见一见他们。

　　几乎与此同时，阿里出手。马云亲自接见高德团队，晓之以理动之以情，演说家一举从百度手里抢下高德。据一位投资人说，阿里第一次投资之前，高德在C端用户的市场份额，要比百度地图差很多。但时至今日，二者的市场格局早已变天。

　　而阿里买高德的路数与UC一样：先投资控股，转年全部拿下。2013年3月阿里对UC那次注资，实现了控股，转年6月份正式买入剩余股份；2013年5月，阿里注资高德，成为其第一大股东，转年2月从纳斯达克将其私有化。节奏几乎一致。

　　据说2013年，百度还接洽过大众点评，路数与报价UC、高德一样，控股拿下，无奈最后被实力更强大的腾讯截胡。

　　UC是纯互联网产品公司，to C基因强大；高德则是to B业务起家，当时在车载市场具有统治力，但在C端与百度差距巨大。就在阿里彻底控股这两家公司的2014年8月，俞永福出任了高德互联网业务负责人，并于转年正式出任高德集团总裁。让具有to C经验的产品团队接手高德，这是阿里的一招险棋。

　　先说一组数字。2013年8月份，百度地图突破2亿用户；高德手机地图达到这个数字，是在当年年底，晚了小半年。也就是在最初的竞争阶段，两家体量都差不多，百度地图还稍稍占据优势。那此前百度为什么还想生吃高德呢？因为O2O。

　　从2013年到今天，中国互联网创业最大的风口就是O2O，无论是团购、外卖，还是共享经济，都是这个风口之下的产物。线上流量越来越依赖线下流量，巨头疯狂布局。

　　风口面前，百度地图先行先试。2012年10月，百度正式把之前的地图业务升级为LBS事业部，与当时李明远负责的移动云事业部成为百度在移动互联网时代的两大护卫。从县级市，一跃成为省部级，与太子执掌的部委双子闪耀，在百度还从来没有一个产品部门享受过这样的待遇。

　　LBS其实就是O2O概念的前身。地图在LBS事业部的角色，其实就是百度O2O战略的支点。2013年，百度的河就这样变成了O2O，当时在百度地图上，可以看到百度自己的团购、以及后来买来的糯米团购、还有百度外卖。

　　战略决定路径。当百度围绕O2O不断做加法的时候，百度地图一度承载了所有O2O业务。而此时的高德地图却选择了做减法，从2014年开始，就逐步去掉了一切跟O2O相关的业务。直到2016年，在日活这个关键数据上，高德地图首次赶上百度地图。

　　应该说在2013年前后，阿里对O2O的核心期待，不是地图，而是美团、快的等超级风口之上的的赛道。这在某种程度上减轻了高德地图的‘负荷’。而百度不是。

　　全资收购糯米之后，又自己做了外卖，再加上之前的地图，这成了百度应对O2O的三大法宝，每一块都很重要，彼此被需要，当O2O是公司最核心战略的时候，合力大于3，但当这个战略的价值日益萎缩的时候，单块业务随时可能成为弃子。这次外卖转手给饿了么，就是最好的例子。

　　其实早在2014年9月份，百度地图+O2O的战略就已经出现疲态。先是LBS负责人沈丽离职，加盟百度O2O业务的最大友商美团。接着是2015年年初，LBS事业部干脆销售，旗下核心业务并于李明远的移动云事业部，再到2016年，李明远再次从百度离职。人事变动的背后是公司战略的变动。到了2017年，百度的河又变成了人工智能。

　　除了战略摇摆不定，战略的落地能力也是百度错失O2O的一大原因。李彦宏曾说拿出200亿人民币补贴外卖，但当美团、饿了么在2016年春节疯狂加班的时候，百度外卖选择了非常人性化地放假。钱没到位，还唤起了竞争对手的狼性。

　　据说，通过大力推广自有产品和并购，百度在2013年这一年共计获得14款用户过亿的产品，这在当年的BAT中，绝对是第一，但到了今天，还有几款能够停留在各大APP排行榜的Top 20？

　　从UC到高德，俞永福走了4年；从O2O到人工智能，李彦宏也走了四年。四年后的今天，UC还在、高德还在，但是91助手、糯米、百度外卖去哪了？

（声明：本文仅代表作者观点，不代表新浪网立场。）