算法花园

严重申明：本篇文章所有信息从论文、网络等公开渠道中获得，不会透露滴滴地图 ETA 任何实现方法。

这篇论文是滴滴时空数据组 2018 年在 KDD 上发表的关于在 ETA 领域应用深度学习的文章，里面提到模型和技巧大家都应该耳熟能详，最大亮点是工业界的创新。

简单介绍一下背景：ETA 是 Estimate Travel Time 的缩写，中文大概能翻译成到达时间估计。这个问题描述是：在某一个时刻，估计从 A 点到 B 点需要的时间。对于滴滴，关注的是司机开车把乘客从起点送到终点需要的时间。抽象出来 ETA 就是一个时间空间信息相关的回归问题。CTR 中常用的方法都可以在这里面尝试。

对于这个问题：文章首先提到一个最通用的方法 Route ETA：即在获得 A 点到 B 点路线的情况下，计算路线中每一段路的行驶时间，并且预估路口的等待时间。最终 ETA 由全部时间相加得到。这种方法实现起来很简单，也能拿到一些收益。但是仔细思考一下，没有考虑未来道路的通行状态变化情况以及路线的拓扑关系。针对这些问题，文章中提到滴滴内部也有利用 GBDT 或 FM 的方法解决 ETA 问题，不过没有仔细写实现的方法，我也不好继续分析下去。

评价指标

对于 ETA 问题来说，工业界和学术界常用的指标是 MAPE(mean absolute percentage error)，${y_i}$ 是司机实际从 A 点到 B 点花费的时间，${f(x_i)}$ 是 ETA 模型估计出来的时间。得到计算公式如下：

$${min_f \sum_{i=1}^{N}\frac{|y_i - f(x_i)|}{y_i}}$$

多说一句，如果使用 GBDT 模型实现 ETA 时，这个损失函数的推导有点困难，全网也没有看见几个人推导过。

这个公式主要考虑预估时间偏差大小对用户感知体验的影响，目前我们更加关心极端 badcase 对用户的影响。

特征

• 特征：
  • 空间特征：路线序列、道路等级、POI等
  • 时间特征：月份、星期、时间片等
  • 路况特征：道路的通行速度、拥堵程度
  • 个性化信息：司机特征、乘客特征（有「杀熟」风险）、车辆特征
  • 附近特征：天气、交通管制

模型

模型包含 3 个部分：

• Wide Learning Models：Wide & Deep 这一部分使用的是 LR + 特征工程，希望模型能记忆一部分的模型。这篇论文中直接利用交叉积学习，减少手动特征工程。
• Deep Neural Networks：对 sparse feature 做一次 Embedding，使用 3 层 MLP 和 ReLU 的网络。
• Long-Short Term Memory：前两部分模块没用使用路线序列特征，所以这部分采用 LSTM 抽取路线特征。由于路线序列是不定长的，论文中的模型是使用最后一个隐藏状态，我们也可以把全部的隐藏状态 reduce_sum 输入到最后的模块。
• Regressor： 将 3 个模型的输出综合起来，作为最后的 ETA 预估。MAPE 作为损失函数，利用 BP 训练模型。

上面模型中使用的特征分类：

• Dense feature：行程级别的实数特征，比如起终点球面距离、起终点 GPS 坐标等。
• Sparse feature：行程级别的离散特征，比如时间片编号、星期几、天气类型等。
• Sequential feature：link 级别的特征，实数特征直接输入模型，而离散特征先做 embedding 再输入模型。注意，这里不再是每个行程一个特征向量，而是行程中每条 link 都有一个特征向量。比如，link 的长度、车道数、功能等级、实时通行速度等。

评估

包括两部分：离线评估和在线评估。

离线评估中取滴滴 2017 年北京前6个月的订单数据，分成两类 pickup （平台给司机分单后，司机开车去接乘客的过程）和 trip （司机接到乘客并前往目的地的过程）。具体数据集划分如下。

离线使用 MAPE 来评价模型。在线评估时，为了更好的与用户体验挂钩，采用多个指标来衡量 ETA 的效果。包括：

• APE20: absolute percentage error 小于 20% 的订单占比。（越大越好）
• Badcase率：APE 大于 50% 或者 AE 大于 180s 的订单占比，定义为对用户造成巨大影响的情况。（越小越好）
• 低估率：低估订单的比例。（越小越好）

离线结果如下图所示，说来汗颜 PTTE 和 TEMP 是什么算法我都不知道…… WD-MLP 指的是将 WDR 中的 R 部分换成 MLP 。最终 WDR 较 route-ETA 有巨大提升，而且 LSTM 引入的序列信息也在 pikcup 上提升了 0.75%。文章的最后还提出来，LSTM 也可以换成是 Attention，这样替换有什么优点和缺点留给大家思考。

在线实验结果如下图所示，滴滴 ETA MAPE 明显小于 com1、com2、com3 ，这三家地图公司具体是哪三家，大家也能猜到吧。

ETA 服务工程架构

从上面的图中可以看出 ETA 服务工程架构主要包括三个部分：

• Data Aggregation：包括利用 Map Matching 将司机上传到平台的 GPS 对应到滴滴的 Map Info 中得到司机真实行驶过的路线信息，Order Context 指的是订单相关的信息，augmented Data 额外数据比如上文说的交通情况相关信息。
• Offline Training：利用上一步得到的历史数据训练模型。这里可以值得一提的是，ETA 模型是和时间强相关的（节假日和工作日的数据分布明显不同），所以在文章中作者指出将拿出最新的一部分数据用来 fine-tune 训练出来的 WDR 模型。
• Online Service：这里需要一个完整的模型服务系统，其他公司也有很多分享，所以原文没有多提。

FMA-ETA: Estimating Travel Time Entirely Based on FFN With Attention

• WDR 模型中 RNN 耗时长，探索基于 Attention 机制的模型
• 对特征分组（multi-factor）去做 Attention 效果比多头要好
• 实验结果分析这部分没有看懂

  The deep modules with attention achieve better results than WDR on MAE and RMSE metrics, which means attention mechanism can help to extract features and sole the long-range dependencies in long sequence.

• 遗憾之处
  • 新模型预测时延减少，但是没有线上实验结果。
  • 暂时没有公开代码和数据集。

总结

从上面简单的介绍来看，ETA 可以使用 CTR 和 NLP 领域的很多技术，大有可为。最后，滴滴 ETA 团队持续招人中（社招、校招、日常实习等），感兴趣者快快和我联系。

说点题外话 你为什么从滴滴出行离职？ - 知乎 中提到一点：

8.同年大跃进，在滴滴中高层的眼里，没有BAT。滴滴单量超淘宝指日可待，GAFA才是滴滴要赶超的对象。百度系，LinkedIn系，学院派，uber帮，联想系，MBB就算了，据说连藤校都混成了一个小圈子。。一个项目A team ，B team。一个ETA，投入了多少人力自相残杀？MAPE做到0%又如何？用户体验就爆表了吗？长期留存就高枕无忧了吗？风流总被雨打风吹去，滴滴是二龙山，三虫聚首？是不是正确的事情不知道，反正跟着公司大势所趋，升D10保平安。

参考

• KDD 2018：滴滴提出WDR模型显著提升ETA预测精度 | 雷锋网
• LBS工业界ETA应用及滴滴WDR技术 – Semocean