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哈哈哈，大家周末愉快~