作者 | 滴滴AI Labs
編輯 | 陳大鑫
某個周末晚上，小陳約好了和女朋友去商場吃飯看電影。
小陳平時喜愛打遊戲，此時正在專心打農藥。
「啊！ZZ隊友送人頭，白瞎我最強亞索！傷心～」
而小陳的女朋友這個時候打來了電話:
你收拾好了嗎？我已經到口紅啦……
小陳內心：「這次竟然這麼快？我還以為剛到眉毛呢，可是我還想再開一局逆風翻盤拿五殺呢！但是又不能遲到啊……
小陳想到先點開打車軟體計算一下雙方的時間吧：
首先設置好出發地為女朋友家，目的地為要去的商場，呼叫快車，顯示要30分鐘。
再來設置一下自己的出發地，呼叫快車，哇！只要15分鐘。
小陳於是決定再開一局，一套「行雲流水」的操作下來之後，成功「助力」自己一方被五殺，望著被推倒的水晶塔，小陳內心「開心無比」，心想這局勝利的關鍵果然在自己身上啊！
後來小陳準時趕到女朋友之前赴約……
小陳心想這軟體預估到達的時間真是準啊，多虧了它，農藥也打了，約會也沒遲到。
相信以上類似場景大家多少都有遇到過，大家近些年逐漸習慣用網約車，而以滴滴為代表的網約車軟體背後必須要提供各方面精準的服務。
這其中就涉及到一個至關重要的基礎問題：預估到達時間（Estimated Time of Arrival, ETA）。
在滴滴、Uber、Lyft等共享出行平臺，時間預測的精度會直接關係到路徑選擇的合理性、訂單分配的精確性和交通系統的整體效率，從而影響乘客的出行體驗，以及司機的效率和收入；而且，海量的日均調用量也會對ETA模型的線上推理速度提出非常高的要求。
ETA的複雜性和挑戰性，使其成為頗具學術研究價值的問題。它要考慮交通要素的空間關係和交通系統的時間特性，也要引入個性化特徵和外部特徵的建模。這些特點使得機器學習成為很好的ETA解決方案，能夠利用海量交通數據來建模行程時間分布。
在今年的KDD2020大會上，滴滴發表了一篇題為《CompactETA: A Fast Inference System for Travel Time Prediction》的論文，詳細介紹了如何在線上部署中實現微秒級的ETA機器學習解決方案。
這種名為CompactETA的新算法是滴滴在此前論文《Learning to Estimate the Travel Time》（KDD2018）的算法框架的基礎上提出的，它能基於圖注意力網絡（Graph Attention Network）將高階的時空依賴關係編碼到特徵表示中，並進一步使用了位置編碼技術（Positional Encoding）來保留行駛路徑的序列信息。相比前一代方案，CompactETA實現了超過100倍的線上加速，平均響應時間低於50us。
1
ETA可建模成機器學習問題
直觀來看，ETA系統要預測從地圖上一點移動到另外一點所花費的時間。這是一個廣泛存在的概念，航班、火車、汽車以及單車騎行都有對應的ETA預測任務。
下面是一個示意圖，假設用戶從左上方的起點出發，想要前往右下角的終點，ETA系統將結合路網狀態和用戶信息對這段行程花費的時間做一個預估（圖中示例的25分鐘）。
ETA的應用在滴滴平臺上無處不在。
例如以下場景：
1、選定目的地之後，乘客首先看到就是預估接駕時間和預計到達終點的時間。前者告訴乘客大約多久之後司機可以到達他指定的出發點，後者給了乘客關於旅途時長的一個預測。如果這兩個時間足夠準確，乘客便會對行程有合理的心理預期，便於高效安排自己的事務。
2、除了顯示時間之外，其實還有一個數字隱藏了ETA的貢獻，那就是預估價格。滴滴平臺綜合了行程距離和ETA等信息，按照計價規則提前估計一個金額供乘客參考。這些都是用戶直觀可感受的。
3、在用戶看不到的後臺，ETA當然也是滴滴的派單引擎和調度引擎的重要決策信息之一。在滴滴，ETA服務的日均調用量已經達到百億級別，想要提升網約車雙邊交易的效率，精準的ETA是重要基礎之一。
當人們想要預估一次行程時間時，至少有三個信息是必要的：誰、何時出發，以及走哪條路。放在網約車平臺，這三個信息對應著：司機ID、出發時刻和行駛路徑。這三個必要信息構成了ETA的query，即：
其中司機ID和出發時刻都是標量，而行駛路徑是一個向量，由一系列的路段ID組成。把路段稱作Link。那麼路徑可以表示為：
其中的各個L代表了Link的ID。根據query中的三項輸入，可以在特徵庫中查詢並構造出豐富的特徵，車型、車齡、駕齡等畫像信息，這些都可能對行車速度有影響。利用出發時刻，可以得到當前的天氣信息、道路限行信息、交通管制信息等。
出發時刻本身輸入到模型中也幫助了對周期性交通規律的建模。利用行駛路徑就可以查詢到該行程經過了哪些路，這些路的靜態物理屬性是怎樣的（封閉快速路/鄉鎮村道，車道數，限速，紅綠燈情況等）；同時還能知道這些路的動態屬性，通常指的是路況，描述了路網當前的通行擁堵情況。
所有特徵會分為兩類：
第一類是全局特徵，描述了行程級別的基本信息。對於每個樣本來說，它記錄成一個向量。
第二類是道路特徵，描述了行程的link序列細節，對於每個樣本來說，它記錄成一個矩陣。每一列描述了一個link的特徵向量。例如，在下圖中，左邊的天氣類型構成了全局特徵的一維；而右邊的link特徵，每個link都有對應維度記錄自己的長度和通行速度值。
在輸入模型之前，不同類型的特徵會進行變換。離散特徵先通過各自對應的embedding層，然後與連續特徵拼接起來。全局特徵和道路特徵都採用這種做法。
基於query構造完特徵之後，就可以設計模型學習出從特徵到行程時間預估的一個映射，這是一個典型的回歸問題：
。
2
ETA機器學習方案的一些探索性
在滴滴團隊於2018年發表的《Learning to Estimate the Travel Time》一文中，首次提出了系統性的ETA機器學習解決方案。
其中，Wide-Deep-Recurrent（WDR）深度神經網絡模型取得了很好的精度。WDR的細節可參考之前的解讀文章，接下來簡要介紹一下團隊在WDR之後的一些思考和探索。
首先是數據稀疏性問題。儘管滴滴有著龐大的軌跡數據，但在時間、空間和人這三個維度的組合面前，卻還沒有達到充足。在WDR（以及大部分深度學習模型）中，link ID都以embedding的方式處理。
一旦某個link的歷史數據太少，那麼它的embedding vector就容易處於欠擬合狀態，影響了整體ETA預測的準確性，我們把這稱之為空間稀疏性問題。
為了解決這個問題，團隊做了一個工作：基於路況分布來度量不同link的相似性，並利用metric learning來對link的embedding vector加強訓練。這個思路類似於遷移學習，把熱門link的知識遷移到缺少數據但是通行模式相似的冷門link上。
除了空間稀疏性問題，對應的還有時間稀疏性和司機稀疏性的問題，它們是數據在不同時段和司機上的分布不均導致的。我們同樣用了metric learning的方法來處理司機稀疏性，用他們的駕駛習慣來度量相似性。
而對於時間稀疏性，我們嘗試了給相鄰時段的embedding vector設置共享參數，使得相鄰時段的embedding vector更加相似。
除了稀疏性問題，我們也關心當規劃路線不存在的場景下如何進行ETA預測。本質上看，這需要把起終點之間多種可能的路線都學習到模型中。
團隊針對性地提出用圖相關的算法來隱式地對路線進行建模，同時採用了multi-task learning的框架，不光預測行程時間，也預測行程距離，通過多任務的相互協同來加強ETA的準確性。這個工作已經發表在KDD 2018上（Multi-task Representation Learning for Travel Time Prediction）。
此外，考慮到路網天然是一個拓撲圖，我們也關注把圖卷積方法應用在ETA和路況預測任務上。這方面可以關注同樣在KDD 2020上的《HerETA: Heterogeneous Information Network Embedding for Estimating Time of Arrival》。
當然，作為工業級應用，WDR最大的瓶頸還是在於線上推理速度。
模型中recurrent結構消耗了相當大的計算資源。一次典型的ETA計算耗時長達幾毫秒，如果伺服器負載較高，響應時間甚至會到幾十毫秒。這樣的服務效率，在傳統網際網路應用中算是非常高的，但在共享出行領域，卻還是重要的系統瓶頸之一，也產生了較大的機器成本。
因此，在提出了ETA的機器學習解決方案後團隊就把主要精力放在提升ETA推理速度上。同時，也希望精度不要有所降低。這就是本文要介紹的CompactETA的產生背景。
3
既快又準的ETA對出行平臺降本提效有重要意義
ETA在網約車後臺服務中發揮著重要作用，比如分單引擎、拼車引擎和運力調度等。為了實現整體交通系統的最優調度，分單引擎需要計算每個司機去接每個乘客的ETA，由此來綜合統籌片區內的情況，盡最大可能保證司機和乘客的有效分配。
再比如，既要提升交通效率，又要滿足個性化出行需求，拼車是很有潛力的解決方案。以路徑規劃、ETA為代表的地圖算法在拼車中扮演著重要的角色。拼車的順路程度不僅由距離決定，時間也是重要參考。過長的繞行時間同樣會給乘客體驗和司機效率帶來嚴重傷害。
作為一項重要的工業級應用，ETA僅僅是精度高還遠遠不夠。以拼車ETA調用量為例，如下圖所示，假設僅考慮10名司機和20名乘客，引擎想要計算出最佳的雙拼方案，那麼就需要知道每一種組合的預估接駕時間。這裡，總共有10x20x19=3800種司機和乘客的組合。
假如有一天，乘客願意接受短距離調度，比如走幾十米到更佳的上車點（乘客走幾十米，比如過天橋或出園區，有可能讓司機少繞路幾百米甚至幾公裡），那麼我們要為每個乘客考慮附近的多個上車點，並且尋找最優的整體路線。假如候選上車點為5個，接駕路徑的組合數迅速爆炸為3800x5x5=95000。為了求解10名司機和20名乘客的最佳拼車接駕方案（哪個司機接哪兩個乘客，順序如何），我們可能面臨至少95000次ETA調用。在全國範圍內，類似的計算還要重複成千上萬遍。
我們當然可以採用各種組合優化的近似算法來降低ETA的調用量，甚至調用更快但相對不準的降級ETA服務，但這都會損害解的最優性。在共享出行平臺，為了支持龐大的業務，ETA計算佔據的伺服器資源非常大。一個既準又快的ETA服務方案不僅能支持更複雜的業務策略，而且還能明顯降低成本。
4
CompactETA設計思路
提到神經網絡加速，首先讓人想到的是近年來流行的模型壓縮方法，又或者是採用GPU的整型計算來降低浮點數精度進行推理。如果優化得當，這些手段確實能取得幾倍的性能提升，但這還遠遠不夠。我們希望實現更可觀的加速，因此分析了業務和模型更深層次的特點，嘗試站在一個更全面的角度來設計快速推理的ETA。
經典的線上機器學習系統，比如圖像分類，處理各個query的流程是解耦的。一張圖片的推理計算與其它圖片無關。但是ETA的query分布有自身的特點，具有明顯的聚集現象，總的來說可以分為兩個方面：
1、空間聚集性
派單場景的ETA query來源於鄰近區域內的司機乘客產生的接送組合。這一批路線雖然起終點各不相同，但其中重疊的link非常多。比如下圖，我們想知道某個乘客被周圍各個司機接駕的ETA，最後那一段路線很大概率是重複的。
2、時間聚集性
ETA query不僅在空間上聚集，時間上也呈現聚集現象。大部分乘客在呼叫車輛時，都可能在短時間內經過好幾輪的派單嘗試，由此產生的ETA query在時間上非常接近。比如下圖，第二輪派單時相比第一輪派單，司機又移動了幾十米，兩條路線有很多重複的地方。但與多個司機同時產生路線的情形不同，這是一個司機在多個時間產生的路線，我們要確保這段時間內道路特徵沒有發生變化，才能認為這兩次計算有冗餘的地方。
事實上，道路特徵確實不是實時變化的，而是有一定的更新周期。更新最快的是路況信息，工業界更新頻率較高的平臺一般採用2分鐘發布一版路況的做法。對於其它特徵，比如車道等屬性來說，更新周期為地圖測繪的間隔，通常是天級別的。因此，在兩次間隔不長的ETA query中，重合路線的特徵是完全不變的（只要不橫跨多個路況更新周期）。
對於WDR來說，只要起終點不同，那麼link序列就不同，整個recurrent部分都要重新計算。有沒有辦法讓這些聚集的query共享計算結果呢？我們首先嘗試了一個思路：把端到端整體預測的方式改為對每個link單獨預測時間然後求和的方式。但在滴滴的實踐中發現，大量link過短過碎導致時間誤差較大，求和之後誤差可能進一步積累放大。另外，link時間求和的方式也阻礙了個性化信息在模型中的充分表達，影響了整體的準確性。
最終，我們決定對每個link抽取高層級的表示（high level representation），然後對表示向量求和而不是直接對時間求和。在最後階段，保留了一個精簡的MLP模型，將個性化信息和link表示之和進行融合。各個link的表示向量可以獨立於query定期更新。當兩個query的路線有大量重複時，它們可以充分復用這些重合link的表示向量。在這樣的思路指導下，我們設計了CompactETA模型，相比WDR它有幾個根本性的改進：
1、Graph Attention Network取代了LSTM的位置。在WDR中，鄰近link的依賴關係通過LSTM的序列學習能力來建立；而在CompactETA中，link之間的依賴關係通過學習路網的拓撲結構來建立。
2、移除了wide和deep部分。為了把query到達之後的計算量壓縮到極致，我們選擇了直接把全局特徵輸入到最終的MLP中，而不再經過wide和deep部分，這在一些情況下會對精度有少許影響。
3、增加了位置編碼。這一操作是為了儘可能地保留link的序列信息。在求和操作中，link的順序完全不影響結果，這與我們的直覺相違背——先走哪條路再走哪條路對整體行程時間是有影響的。這個問題同樣存在於NLP任務中，當模型從RNN演化為Attention結構時，單詞的順序信息也被丟失了。我們借鑑了Transformer的解決方案，用三角函數生成了一系列關於位置的編碼。但與Transformer不同的是，直接把PE加到表示向量上對於求和操作依然沒有任何作用，所以我們採用了更加激進的乘法方式來使用位置編碼。
最終，CompactETA的設計結構如下圖所示。在線上部署中，Graph Attention Network構成了updater模塊，每當感知到新版路況時，就為地圖中每一個link計算它的表示向量。這些表示向量被存在一個內存表中，並及時推送到predictor模塊。真正的實時計算發生在predictor中。當一個ETA query到來時，服務僅僅執行了查表、求和等簡單操作，加上一個128維隱層的MLP計算。這些計算是非常快的，即便CPU機器也能在若干微秒內完成。
CompactETA的優勢有兩方面。
第一，它響應速度非常快。只有發生在predictor上的計算會影響query響應時間，而updater的計算與此是完全隔離的。
第二，它節約了非常多的計算量。如前所述，空間聚集和時間聚集的query大量共享了同一批link表示向量，整體計算量有了大幅下降。
5
實驗表明CompactETA推理速度大幅提升
模型的準確性經過了離線和在線評估，而服務性能指標由實際壓測給出。結果可以總結為：CompactETA推理速度比SOTA模型快了超過100倍，同時準確性非常接近。以下詳述。
在北京、蘇州和瀋陽的離線評測中，相比於WDR模型，CompactETA的MAPE指標最多變差了0.21%（北京接駕場景）。對於大多數業務來說，這個精度差異已經很難被感知了。比如，20分鐘的行程，平均預測誤差僅變大了2.52秒（0.21%）。
在線上實驗中，考慮到網約車雙邊市場不適宜做簡單的隨機分配流量，實驗分別進行了A/A階段和A/B階段。在A/A階段中，對照組（WDR）和實驗組（WDR）天然有2%左右的噪聲波動。而在A/B階段中，我們觀察到對照組（WDR）和實驗組（CompactETA）的差異水平也在2%左右。
此結果說明CompactETA和SOTA模型的線上差異在噪聲範圍內，應用於實際業務時，效果基本沒有差異。服務指標方面，測試伺服器配備了Intel Xeon E5-2670 2.3GHz的48核CPU，機器內存是128GB。
不同並發量下的壓力測試表明，CompactETA的單機峰值QPS高達93.4萬，平均響應時間在中低負載下可以穩定控制到50us以內。作為對比，WDR模型的單機峰值QPS僅為0.7萬，且無論何種負載水平下，平均響應時間都超過了CompactETA的100倍。
6
總結
ETA服務是共享出行的基礎設施之一,本文介紹了CompactETA這種能夠高速進行線上推理的模型，也梳理了本團隊在ETA方向上的系統性工作以及相關思考。
高效率的ETA服務一方面可以突破新業務形態的計算瓶頸，另一方面也能顯著降低現有業務的成本。低成本且高精度的ETA，是出行企業進行運力智能調度和精細化運營的基礎。除了出行之外，它也有潛力服務於電子地圖、外賣、物流以及無人車調度等領域。ETA還有不少有價值的問題值得探討，期待感興趣的同行和我們交流,一同進步！