ETA：Estimated Time of Arrival，地图服务中一个十分重要核心的基础能力。高德百度的导航，美团的配送，滴滴的接送驾等等，可以说有地图的地方就有ETA。
我了解到的，美团配送的ETA是树模型（应该是xgb那一套），高德百度正在基于路况预测做，滴滴在KDD2018有两篇ETA的论文（论文地址：https://www.kdd.org/kdd2018/accepted-papers/view/learning-to-estimate-the-travel-time），其中一篇我看过的是WDR模型——算是业内比较先进的模型了吧，所以深度模型应该算是刚刚起步吧。
PS：我其实是ETA的门外汉，没有调研也没有实践经验，也是偶然机会开始初步的思考这个问题。想到这个模型大概也有几周了时间了，一直没有写出来，一方面是因为感觉不成熟，另一方面也有私心，想着说不定我自己有机会尝试。由于，目前focus on强化学习的任务，所以就把这个想法写出来，如果业内人士觉得不靠谱直接忽略我，觉得靠点谱可以尝试，对于学生读者来说如果感兴趣并感觉靠谱的话，说不定做的效果好，一篇KDD也是有可能的哈哈。
路况预测
一个路网一般可以抽象为一个Graph，这个graph具有现实地理意义，每个边表示一个link，路况指的是任意一个link的旅行时间。路况预测就是基于历史路况信息，预测接下来一段时间的路况。
关于路况预测，高速路网相对于城市路网简单一些，没有潮汐现象、红绿灯以及重度拥堵这种情况，所以预测起来相对更加容易一些。对于路况预测，现在比较好的模型有基于图卷积的DCRNNs，这是一个基于encoder-decoder的模型，encoder和decoder里的基本元件是DCGRU，是使用扩散卷积改造的GRU。论文如下： Diffusion Convolutional Recurrent NeuralNetwork: Data-Driven Traffic Forecasting。也有基于graph attention networks的网络，具体可以看我之前写的Graph Neural Network Review的最后一节。
城市路网的路况预测相对复杂很多，上述的模型也有效，但是跟准确率相对于高速路网会低很多（我自己尝试过）。我们姑且认为，当前路网预测的SOAT方法就是基于图网络的吧。
ETA
在路径规划的基础上，ETA的任务就是预测多个link组成的一条路径规划的旅行时间。很明显这是要基于当前路况的，但是当前路况是信息是不够的，我们还需要对未来的路况进行预测。比如一个路径规划有n个link，link_1的旅行时间是5min，那么link_2的旅行时间就需要使用5min以后的路况信息。
对于使用encoder-decoder架构的路况预测模型来说，ecoder向量包含了我们预测未来路况需要的所有信息，所以感觉上，这个encoder向量对于ETA来说至关重要。
Two-task ETA
所以，我觉得一种可能的基础网络架构可能长这样：
左边是路况预测网络，使用encoder-decoder架构，Encoder和Decoder可以选择Graph RNN的模型，例如DCRNNs或GAT-LSTM等；右边是ETA Model，可以是任意的模型，例如xgb，RNN，它的输入信息是路况预测的Encoder向量。
所以这是一个典型的two-task的任务，loss函数需要考虑两个，一个路况预测，一个是ETA。当然路况预测也可以是提前训练好的一个模型。
几个重要的问题- 当前城市路网路况预测效果不是特别理想 。主要是城市路网路况天然方差就比较大，有潮汐现象、红绿灯等复杂的影响因素。不过，聊胜于无应该也会有一定的效果，这方面需要更好预测的可以自己改进了，这就是另一个问题了。
- 基于RNN的ETA Model。 如果ETA Model使用xgb就没什么好说的，直接搞就行了。如果使用类似RNN的序列建模，大概长这样：
对于每个link，都输入路况预测的encoder向量，输出该link的eta，并将该预测的eta作为下一个link的输入。
一个路径规划，其包含的link数目肯定是不同的，可以参照NLP中的解决办法，划分一些桶，比如5，10，15等，对于link数目在0~5的都放在5这个桶内，对于link是4的，就在末尾加两个padding mask，使其link数目是5。具体的可以去稍微看一下NLP怎么处理句子长度对不齐的。
- 你可能需要Attention。 一个城市路网是非常非常大的，如果作为一个Graph训练的话，那么其Encoder信息就是包含整个Graph的，当我们对于某一个具体的路径规划计算eta时，这些Encoder向量似乎包含的信息太杂了，我想到两个办法：一种是可以借助Attention，对于每一个路径的Eta动态计算其需要的Encoder，也就是在路况预测的时候加入Attention，我们的目的是对于一个具体ETA包含的link及其相关的link路况预测的更准，其他的可以不那么准，这样就使得我们的Encoder向量专注于某个具体的ETA；第二种方法是对城市就行划分，一个城市可以包含多个Graph，对每一个相对较小的Graph就不太需要attention了。
PS：以上纯属YY哈哈哈，大家周末愉快~