走近高德駕車ETA（預估到達時間）
1. 什麼是駕車ETA
臨近節假，長途自駕返鄉的你是否曾為無法預知路上到底有多堵而糾結？通勤上班，作為有車一族的你是否在為路況變幻莫測的早晚高峰而煩惱？外出旅行，趕火車、趕飛機的你是否還在為擔心錯過班次而焦慮？不要慌，高德的駕車ETA幫你預知未來路況，讓每個使用者輕鬆成為「時間管理大師」！
**ETA（Estimated Time of Arrival），即預估到達時間，指的是使用者在當前時刻出發按照給定路線前往目的地預計需要的時長。**如圖1展示了駕車ETA在導航軟體的前端頁面上呈現的形態，使用者在使用過程中會主要參考這一資料安排行程時間、進行出行相關決策；對於打車的場景，平臺呈現給使用者的預估價也基於這一資料進行計算。因此，如何準確地預估ETA對於高德地圖的諸多業務板塊都起到至關重要的作用。
圖1 ETA在高德地圖上的前端展示
為方便後文表述，這裡先簡單介紹一下ETA相關的技術概念：
link：路段，是分叉口之間基本的道路組成單元。
trace：軌跡，對應的是一個由一連串link組成的序列。
SP(Speed Profile)：同一特徵日相同時間區間的歷史平均速度，按10min聚合。例如每週一早上9:00-9:10，某個link上所有軌跡，可以將過去幾周聚合求一個平均速度，這個平均速度可以代表對這個link在未來週一早上9:00-9:10這個時間區間內通行速度的靜態預測。
AutoLR(Autonavi Location Reference)：實時路況，道路當前通行耗時，每分鐘都會發布新的值。
link通行耗時真值：在一個5min的時間視窗內進入某一link的所有軌跡，在完成去噪後求取平均值，即得到該link在該5min視窗內的通行耗時真值。
2. 業務板塊
圖2展示了ETA業務的各個板塊。
圖2 ETA整體框架
基礎資料層面，link場景分層根據歷史實走真值將link歸為不同類別。每類link預測的難度不同，例如有些link的通行時間每天鮮有擁堵，則可直接利用靜態SP預測，因此呼叫的預測模組也不盡相同。真值生產及推演系統首先將各個link上5min視窗的實走軌跡聚合求平均通行時間，得到link通行耗時真值；同時利用真值推演工具可推算給定trace的通行耗時真值。link級、trace級的通行耗時真值是模型訓練、模型評估、線上問題調查等一系列工作的資料基石。
預測模組層面，有三大預測模組可用於link級預測。
一是靜態SP：該方法通過歷史均值進行預測，不利用實時資訊。
二是線性模型，該模組在ETA服務中被呼叫，通過實時資訊AutoLR和歷史資訊SP來擬合link級真值。
三是精準預測，該模組作為演演算法服務提供link級預測結果，通過深度學習模型利用實時通行速度、流量等資訊對較為複雜的突發路況進行預測。
預測功能層面，除link級預測外，ETA服務還提供trace級預測功能，對使用者規劃的整條路線進行ETA預測；以及準點率預測功能，對給定trace級預測結果的可信度做出判斷。
應用場景層面，自駕、打車業務都需使用ETA，但兩者樣本分佈以及重點關注的場景不盡相同。ETA的演演算法能力在前端頁面還涉及到一些其他形式的透出，例如擁堵段預計通過耗時、擁堵未來趨勢說明，以及準點率等等。
效果評測層面，涉及到自身link級、trace級基礎指標評測，對真值推演結果的評測、各個場景的效果評估。監控干預層面，涉及到實時撈取頭部問題case、對問題link的ETA進行自動干預、人工干預等。
3. ETA的預測流程
線上的ETA服務為其他服務提供ETA預測計算介面。精準預測模型部署在另外的演演算法服務中，該服務每分鐘將link級多時間跨度預測值寫入快取，ETA服務按需查取相應值。對某個link進行預測時，有精準預測值的情況下將優先使用精準預測結果。ETA服務中的線性模型提供link級多時間跨度預測能力。在精準預測沒有被觸發的情況下，檢視是否有實時路況以及待預測時刻與發起預測時刻時間差是否在1小時以內，滿足上述條件則使用線性模型預測的結果。SP資料載入在ETA服務記憶體中，由於是靜態歷史均值，預測時間跨度可達未來一週。link級預測中，最低優先順序的是利用SP進行靜態預測。
link級預測結果可按照上述方案獲取，那麼整條路線的ETA要如何計算呢？這裡就要用到link序列ETA推演的功能。假如使用者規劃的路線如圖3所示，則在進行預測時，link1應選取對應距離當前[0min, 5min)時間跨度的通行時間預測值，例如該預測值為11min；則使用者預計進入link2的時刻為11min之後，在link2上的通行時間應該選取link2對應[10min, 15min)時間跨度的通行時間預測值……依此邏輯推演到最後一根link（若推演到的某根link累積時間已超出1h，則用SP作為預測值），從而得到對整條路線ETA的預測。
圖3 link序列ETA推演
4. ETA預測的難點及解決方案
在一些出行量大且擁堵規律複雜多變的場景，準確預估ETA的挑戰性極大。例如工作日的早晚高峰，路況非常複雜，而且學校寒暑假後的開學、以往疫情期的反覆、一些特殊日期（例如七夕、聖誕等）出行需求的劇增，都會使得歷史規律無法直接複用。
為了能讓深度模型提前感知擁堵的到來，我們在預測中引入了「未來流量」。想象這樣的場景：來自北京的使用者A由於家到公司較遠，每天早上6點就要開車途徑北五環去公司。9月1日，他像往常一樣早上6點開車出門。走到北五環，使用者A發現今天格外堵。直到在北五環上堵得快要遲到，才突然醒悟，原來今天是開學第一天，早高峰車流量大幅增加，後悔自己沒有出發前沒早點開啟高德看看ETA。
我們注意到，由於使用者A出發很早，出發時刻全程路況仍非常暢通，此時各個link流量也基本和8月無區別。這樣，想要讓模型能預判未來會出現比往常嚴重很多的擁堵，就必須引入能在使用者出發時刻就與8月相同時間有明顯區分度的特徵。使用者A的例子中，在他剛剛出發時，北五環上車流很小，但已經有很多像他一樣早起且需要走北五環的使用者開著導航從家裡出發了，這些人雖然還沒有上五環，但只要他們不偏航且完全按照ETA預估的時間行進，那麼未來任意時刻這些使用者的位置我們都可以推算得到，這意味著我們可以統計「未來的交通流量」。也就是說，這些已經在導航中的使用者，未來各個時間片上會在北五環的各個link上分別形成多大的交通流量，都可以統計到（注：這裡統計到的流量是匿名的聚合總量）。如圖4所示，我們把這個統計量稱作「未來的交通流量」特徵。上面的例子中，早上6點，有很多需要上北五環的使用者已經出發了，因此此時五環上的link已經顯著高於8月份。
圖4 計劃中的交通流量
模型層面，我們提出了一種新的用於通行時間預測的深度學習框架：混合時空圖折積網路（H-STGCN），該框架利用上述計劃中交通流量提升模型效果。
在該模型中，我們設計了域轉換器，以此整合異質模態的交通流量特徵。同時，我們設計了複合鄰接矩陣使得圖折積層能夠更好地捕捉路段間的接近性。實驗發現，在真實場景資料集上，H-STGCN和較先進的其他時空預測模型相比取得了顯著更優的效果，在突發擁堵的預測上優勢尤為明顯。這項研究成果在為使用者帶來更優出行體驗的同時，相應論文也被AI領域國際頂級會議KDD2020接收。
5. ETA的效果評估
對應link級預測與trace級預測，ETA效果的評估也有link級評測與trace級評測。
5.1. link級評測
trace計算參與的角色眾多，涉及到方方面面（實時資訊、歷史統計資訊、道路推演等）都會給trace級別的ETA帶來影響，我們為了更好的衡量在單獨link上ETA的計算質量，我們提出了link eta的評估方法。
bad link率
bad link率計算方法為，bad link批次總數同總link批次數的比值。bad link率越低，link級預測效果越好。bad link批次的定義如公式：
i表示批次id，滿足這個條件即為bad link。
MSE
這裡的n指的是link數量，k指的是評估批次數量。MSE越低，link級預測效果越好。
5.2. trace級評測
通過對比使用者實走時長和ETA行前預測的結果，可以對使用者全行程軌跡的ETA質量進行評估。使用trace級評測，可以監控trace的MSE、MAE、MAPE、優良率、惡劣率等指標。
6. 總結
本文對高德駕車ETA整體的業務板塊進行了簡要的介紹。