介绍
最近几年共享经济比较火,也出现了很多成功的共享经济企业,而共享经济中比较成功的模式大部分都围绕着共享出行展开业务,例如Uber,Lyft, 中国的滴滴,以及近两年遍地开花的共享单车公司(虽然现在部分共享单车的业务已经在停滞或萎缩)
与此同时,很多关键技术也随着共享经济的发展而被重视起来。像MM(Map Matching)[10],RP(Route Plan),Navi(Navigation)以及ETA(Estimation Time of Arrival),这些都是LBS中比较基础同时比较重要的关键技术,无论是共享单车,出租,快车,顺风车等在进行调度,收费定价的时候,都会涉及这些关键技术。
本文就向大家专门介绍其中的一个关键技术:ETA,内容包括: ETA是什么? 为什么重要? 常用ETA技术有哪些,有哪些优缺点,以及现在up-to-date的ETA技术实现细节及效果。特别会重点介绍目前滴滴已经公开发表的WDR模型在ETA上取得的成果
P.S. 本文不会透露滴滴出行内部仍在进行的项目及对应数据,涉及到的技术细节及数据均已通过论文,或者PR文对外公开发表
图:滴滴ETA(接驾ETA以及送驾ETA)
ETA是什么
从业务的角度讲,ETA就是预估一个行程中,从出发时间到到达时间的时间差,例如滴滴快车中预估到达时间,或者高德导航中规划路线行驶所花的时间

图:高德ETA(2:整体路径规划时间预估)
从技术上,我们可以将ETA的一次调用,看成是一次query,每个query的内容为:<o_i,d_i,s_i>,表示第i个请求o,d,s分别表示起点位置(original),终点位置(destination),起点时刻,ETA需要给出的就是t_i = e_i - s_i,其中e_i为行驶到终点的时刻
ETA问题看似很直接,但现实中需要准确预估ETA却非常有挑战。挑战主要来自于以下几方面:
- 时空维度上数据较为稀疏:因为需要预估的物理世界的数据,在时空维度上非常稀疏,虽然滴滴对外宣称每天有近3KW单的订单,但这些订单所产生的轨迹,也不足于充分覆盖时间+空间的路网数据。例如光北京的路网link数就有超过1Million,而从时间的维度,每2分钟发布一次路网交通状况,全天时间维度上有720的时间切片,故时空维度仅北京市共需发布约2亿个发布值,轨迹数据覆盖会非常稀疏。
- 存在较多突发局部事件:且很多时候还存在较多不确定性,例如突发性的车祸,或者交通灯损坏,修路,交通管制,等都会导致路网历史信息失效。
数量较少但影响全局的事件:而碰到节假日或者恶劣天气,整个物理世界的交通也会从系统层面恶化导致预测算法整体失效
为什么重要
但ETA又是一个很基础的关键技术,其应用场景非常广泛, 例如路径规划中用来寻找时间最短的行驶路径,分单,定价,拼单等场景都依赖于ETA。其准确性会直接影响到整个共享出行平台的效率,举几个例子:
- 体验:选定一条路线后,起终点的预估时间不准确,会直接影响用户对平台的信任,特别是很多时间敏感场景,例如赶飞机
- 计价:很多共享出行平台都会在计费的时候引入行驶时间,ETA不准会导致计价预估不准,如果是事前一口价等策略,则可能导致平台亏钱
- 调度:例如拼车场景,ETA不准则会导致拼成率大打折扣,影响用户体验,口碑及平台,司机收益
因为上述ETA的基础性&重要性,目前滴滴每天的ETA调用次数超过40 billions次(数据出处:https://outreach.didichuxing.com/tutorial/kdd2018/)
WDR模型
传统方法主要分为两类:
- route-based method: 该类方法将route 的ETA问题分解为 subroute+crossing的子eta问题。其中subroute为待预估的<o, d> route的子route, 一般地图行业叫link,为表征地图路网的最小单位,长度为数米到数百米不等,crossing为交叉路口,交叉路口因受到交通灯等的影响,故单独抽离出来。该类方法一般可以作为ETA的baseline,来评估复杂ETA算法的效果。该方法的优点就是计算比较直观,简单,而且具有很强的可解释性,出了问题后容易分析定位。缺点也很明显:时间空间上数据覆盖较低,误差容易积累,因为没有用上道路,时序,个性化等特征,故效果有提升空间。具体参见图:route-base method方法示意
- 另一类算法我们称为data-driven method,例如在预估<o, d>的ETA时,可以使使用neighborhood-based的方法找到相似的轨迹时间进行加权来计算ETA[5],类似于推荐问题(具体参见图:neighborhood-based方法),该类问题的缺点仍然是时空上的覆盖较为稀疏,比较适合车流量较大,速度相对均衡的高速或者快速路。例如,在公开的‘Shanghai Taxi Data’上, 虽然后超过3亿个点的记录,但仍然有50%的道路没有被任何轨迹覆盖,且该数据还没考虑时间维度,并且在时间维度上,高峰期和平峰期的数据分布也不一样

图:route-base method方法示意图

图:neighborhood-based方法
在解决ETA问题的同时,也会衍生出来不同分支的子问题,例如比较重要的一类问题是:我们不仅需要预估具体route的eta,同时需要预估对应eta的概率。应为有些场景我们并不需要最短的eta,但需要时间预估最准确的eta,例如赶飞机火车的场景, 一条预估50分钟的路线并不比另一条1小时的route好, 如果后者的预估置信度比前者高很多的话。该类问题可以参考[7]
而比较up-to-date的方法是使用模型来解ETA问题
问题定义
使用传统机器学习的概念, 可以将ETA问题定义为regression问题,即每条sample为给定<o,d,s>以及该sample对应的特征, 将问题建模成回归问题,使用模型来回归具体的ETA值
特征
传统的route-based方法及data-driven方法仅使用计算的路网的traffic特征来计算ETA,该处的traffic仅指具体子route(或称为link)的通行速度(或者对应的通行时间,因确定route后,route长度固定,故通行速度和时间可以相互转换)。
Traffic特征是计算ETA极其重要的特征,但在计算ETA的过程中,我们能够获取到更多更丰富的特征来提升ETA预估的准确性。route-based方法和data-driven方法的问题是很难直接使用这些特征,但复杂模型却能够使用这些特征提升模型的效果。这些特征包括:
- 空间特征spatial information:包括<o, d>路线之间经过的link序列,交叉路口序列(intersections),经过的红绿灯信息,走过的(拥堵)POI等
- 时间信息(temporal information):例如当前时间的月份,是一年中的第几天,周,小时等;以及根据历史信息计算出来是否为早晚高峰or非早晚高峰,是否节假日等;这些特征可能需要经过预处理才能得到, 甚至需要将时间信息映射到频域,找出频域特征后引入模型(参见后续博文:《LBS时空特征的提取技术》)
- 路况信息(traffic information):每两分钟发布一次全网(路网中所有link)的通行速度,该通行速度作为该2分钟时间片内全路网通行能力的重要描述。该路况信息在ETA的计算过程中比较基础也至关重要,发布路况的准确性会直接影响最终ETA的预估准确性,而且根据该路况信息,即可使用route-based方法计算出baseline的ETA。
另外路况信息发布是否准确也是一大挑战,因为在时空维度下,经过每个 link的轨迹数也比较少
- 个性化信息(personalized information) 包括driverid, 乘客id以及汽车相关的属性
- 其他特征:例如天气特征等,该类特征对大盘的影响相对较少, 但对用户体验影响非常大,例如下雨天,整体路网的拥堵程度会大幅上升,但下雨天的占比相对较少, 导致模型不一定能学出该规律,但异常天气下如果ETA不准,又会极度影响用户体验,故最后可能需要使用一些特殊逻辑进行定制处理
优化目标
模型候选的优化目标可以是MAPE,MAE,MSE等,考虑到预估偏差的大小对用户感知体验的影响,与行程本身的时长有关, 故前期在提升模型总体效果的时候,离线模型使用MAPE作为优化目标。在模型基础能力提升到一定程度后, 主要考虑用户体验影响较大的极端CASE时,会同时兼顾异常CASE率,对模型效果进行评估。
其中MAPE定义为:

模型
如,‘问题定义’部分所述,问题一旦定义成regression后, 即可使用传统回归模型进行解决。
近些年深度学习比较火,所以在有足够数据,足够计算资源,对效果又有较高要求的场景, 一般都会使用的深度学习来解决。相较之下,传统的浅模型就没有那么高端了, 但这些模型在特定的场景, 仍然会是比较好的选择。 例如我们在使用模型预估当前的路况状态(行驶道路的状态:畅通,缓行,拥堵)的情况下,使用GBDT仍然会是比较好的选择, 一则我们的Ground Truth较少,目前主要还是通过人工标注获取, 另外则是我们的应用场景需要有较强的可解释性,否则收到用户或者业务方的投诉case时,很难进行分析解释。
在ETA场景中, 浅模型和深度模型的特点如下:
浅模型
传统效果较好浅的模型有gbdt, fm, 这两个模型各有优缺点, gbdt上手比较方便,且能够直接处理连续值,能够自己进行特征选择与组合,但gbdt很难处理特征量较大的场景;fm的效果依赖于特征的表达, 表达能力有限, 对于滴滴的ETA,我们能够获取海量的训练数据,且从加强表达能力的角度考
虑, 深度学习会更胜一筹

图:Wide&Deep模型示意
深度模型
常用的深度模型很多,而且各自有适合自己的优缺点和应用场景,而现在的趋势是构建复杂网络,在复杂网络模型中, 结合浅模型和深度模型的优点,最大化提升预估效果,比较经典且在工业界落地的方法是GooglePlay App推荐场景使用的方法,参见《Wide&Deep Learning for Recommender System》,该方法使用线性模型作为Wide部分进行exploitation,而使用Deep部分进行exploration
Wide&Deep两部分的作用如下:
- Wide部分为线性模型,将特征映射到较高维度空间;一般具体的特征会先进行交叉(也相当于在线性模型中引入部分非线性特征);Wide部分主要作用是做memorization,可以充分exploit历史信息,具有较强的可解释性,并且效率较高
- Deep部分:将高维特征映射到低维的dense特征(进行embedding),之后进行concate。 Deep部分主要是进行exploration;embedding相当于从已经出现过的数据中学习feature的co-corelation,deep部分更倾向于多样性进行explore
但在滴滴ETA场景,我们引入了世界序列模型LSTM,因为传统W&D方案存在缺点:每个sample的feature必须要对齐,但对于给定<o,d>pair对应的route中,组成route的link数量不一样,一般起终点间距小则link数量会少,反之则link数量会比较多,这些link自身的属性可以作为强特征,对最终ETA的效果影响较大,但传统W&D模型在使用的时候,因为不能处理变长的link序列,故模型很难用到link的local,而只能用到这些link的统计信息,故需要引入额外的网络结构来学习这些local信息;此时时间序列模型能够处理变长输入,故是较好的选择。
所以很自然地在W&D模型基础上增加LSTM结构来adopt local的link序列信息,最终形成滴滴ETA使用的WDR模型

图:WDR模型,其中Wide部分既有dense特征也有sparse特征;而Deep部分的Sparse特征需要首先使用embedding方式转为Dense特征,之后进行Concatenation
说到这里简单岔开一下,我们在进行特征设计,或者模型网络结构设计的时候,背后都是有容易理解&解释的Philosopy的:W&D的思路是使用Wide部分进行Memorization,以便对历史信息进行exploitation,使用Deep部分寻找特征之前潜在的Co-Correlation,对特征进行exporation,而R(LSTM)部分则是为了处理W&D处理不好的link边长序列。
在具体实现过程中,线性部分一般会先做特征交叉;Deep部分会先将稀疏特征使用embedding方式转成dense特征,lstm部分则在输入link序列后,使用最终的hidden status输入值最后一层,作为最上层regression
评测方法
在评测模型的时候,我们首先对数据进行了预处理,移除了异常的trajectories, 例如travel time < 60s 或者speed>120km/h的trajectories;之后我们使用3个月的数据,并分接驾数据(pick-up)和送驾(trip)数据分别进行模型训练,并将接下来两周的数据按时间维度分为两份,分别作为验证集合(validation)和测试集(test)评估模型效果
指标
离线使用MAPE(之前提总体乘坐时间越长,偏差的容忍就越长)在线则同时使用MAPE, APE20, bad case率对模型效果进行评估,其中: APE20表示absolute error 小于 20%的case的占比,而相反地,bad case 率定位为预估偏差大于50%,或者大于180秒的case,该指标用于衡量bad case出现的概率,控制极端误差case对用户体验的影响
效果
此处仅给出送驾段MAPE衡量的模型效果,现实中送驾段MAPE能从baseline的15.01%降低到WDR的11.66%,而WDR效果可以比GBDT好2.5%.
其中WDR的R部分, 在送驾段能带来1.77%的MAPE收益,可见将local的link信息使用时间序列方法引入模型,能够带来较大的效果提升。
当然,在算法需要上线时,还需要考虑线上服务的性能,故我们还尝试了另外一种更高效的基于Attention机制的深度网络,以后再向大家介绍。
参考文献
- 《2017年滴滴出行平台就业研究报告》
- Gers, Felix A., Jürgen Schmidhuber, and Fred Cummins. "Learning to forget: Continual prediction with LSTM." (1999): 850-855.
- Cheng, Heng-Tze, et al. "Wide & deep learning for recommender systems." Proceedings of the 1st Workshop on Deep Learning for Recommender Systems. ACM, 2016.
- Wang, Zheng, Kun Fu, and Jieping Ye. "Learning to Estimate the Travel Time." Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. ACM, 2018.
- Wang, Hongjian, et al. "A simple baseline for travel time estimation using large-scale trip data." Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. ACM, 2016.
- Wang, Yilun, Yu Zheng, and Yexiang Xue. "Travel time estimation of a path using sparse trajectories." Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2014.
- Asghari, Mohammad, et al. "Probabilistic estimation of link travel times in dynamic road networks." Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems. ACM, 2015.
- https://outreach.didichuxing.com/tutorial/kdd2018/
- google官方wide&deep实现:https://github.com/tensorflow/models/tree/master/official/wide_deep
- map-matching:http://www.semocean.com/lbs%E5%9C%B0%E5%9B%BEmap-matching%E6%B5%81%E8%A1%8C%E7%AE%97%E6%B3%95%E5%8F%8A%E5%BA%94%E7%94%A8/
更多内容也可参见: http://www.semocean.com