引言

ETA（Estimated time of Arrival，預計送達時間）是外賣配送場景中最重要的變量之一（如圖1）。 我們對ETA預估的準確度和合理度會對上億外賣用戶的訂單體驗造成深遠影響，這關系到用戶的后續(xù)行為和留存，是用戶后續(xù)下單意愿的壓艙石。ETA在配送業(yè)務架構中也具有重要地位，是配送運單實時調度系統(tǒng)的關鍵參數(shù)。對ETA的準確預估可以提升調度系統(tǒng)的效率，在有限的運力中做到對運單的合理分配。在保障用戶體驗的同時，對ETA的準確預估也可以幫助線下運營構建有效可行的配送考核指標，保障騎手的體驗和收益。

圖1. ETA的業(yè)務價值

最近幾年，ETA在互聯(lián)網(wǎng)行業(yè)中的運用取得了令人矚目的進展，其中以外賣行業(yè)和打車行業(yè)最令人關注。但與打車行業(yè)相比，ETA在外賣行業(yè)中的業(yè)務場景更為復雜。如圖2所示，從業(yè)務要素來看，打車涉及到兩方——乘客和司機，而外賣行業(yè)則涉及了三方——騎手、商家、用戶，這使得問題的處理難度提升了一個量級。從業(yè)務的環(huán)節(jié)來看，打車分為派單、接人、送達三個環(huán)節(jié)，是一個司機接單到達指定地點接送乘客到達目的地的過程；而外賣則主要分為接單、到店、取餐、送達四個環(huán)節(jié)，是一個用戶、騎手、商家來回交錯的場景。業(yè)務環(huán)節(jié)的增加帶來了更多的復雜性和不確定性，如騎手操作在各個環(huán)節(jié)中存在較多的不可控因素，商家可能出餐較慢，此外還有運力規(guī)劃和天氣因素的不確定性等，這就直接導致了外賣ETA采取了端到端（下單到接單）的預估方式，相比于拆分成四個環(huán)節(jié)單獨預估具有更強的容錯性。無論從業(yè)務所涉及的要素還是從業(yè)務環(huán)節(jié)來看，外賣業(yè)務的復雜程度遠遠高于打車業(yè)務，對ETA預估的難度更大。

圖2. ETA架構圖

ETA中比較常用的模型是以GBDT（Gradient Boost Decision Tree，梯度提升決策樹）、RF（RandomForest，隨機森林）和線性回歸為主的回歸預測模型。GBDT是利用DT Boosting的思路，通過梯度求解的方式追蹤殘差，最終達到利用弱分類器（回歸器）構造強分類器（回歸器）的目的。RF在DT Bagging的基礎之上通過加入樣本隨機和特征隨機的方式引入更多的隨機性，解決了決策樹泛化能力弱的問題。而線性回歸作為線性模型，很容易并行化，處理上億條訓練樣本不是問題。但線性模型學習能力有限，需要大量特征工程預先分析出有效的特征、特征組合，從而去間接增強線性回歸的線性學習能力。

在回歸模型中，特征組合非常重要，但只依靠業(yè)務理解和人工經(jīng)驗不一定能帶來效果提升，這導致在實際應用中存在特征匱乏的問題。所以如何發(fā)現(xiàn)、構造、組合有效特征，并彌補人工經(jīng)驗的不足，成了ETA中重要的一環(huán)。

GBDT構造特征現(xiàn)狀

Facebook 2014年的文章介紹了通過GBDT解決LR的特征組合問題。[1]GBDT思想對于發(fā)現(xiàn)多種有區(qū)分性的特征和組合特征具有天然優(yōu)勢，可以用來構造新的組合特征。在Facebook的文章中，會基于樣本在GBDT中的輸出節(jié)點索引位置構造0-1特征，實現(xiàn)特征的豐富化。新構造的0-1特征中，每一個特征對應樣本在每棵樹中可能的輸出位置，它們代表著某些特征的某種邏輯組合。例如一棵樹有n個葉子節(jié)點，當樣本在第k個葉子節(jié)點輸出時，則第k個特征輸出1，其余n-1個特征輸出0，如圖3所示。

圖3. GBDT(Gradient Boost Decision Tree)特征構造方法

至于構造新特征的規(guī)模，需要由具體業(yè)務規(guī)模而決定。當GBDT中樹的數(shù)量較多或樹深較深時，構造的特征規(guī)模也會大幅增加；當業(yè)務中所用的數(shù)據(jù)規(guī)模較小時，大規(guī)模的構造新特征會導致后續(xù)訓練模型存在過擬合的可能。所以構造特征的規(guī)模需要足夠合理。

GBDT構造特征在ETA場景的中的應用方案

在ETA場景中，由于業(yè)務場景復雜，所以特征的豐富性決定了ETA最終效果的上限。在目前所擁有的特征中，在特征工程的基礎階段，我們依靠業(yè)務理解、人工分析和經(jīng)驗總結來構造特征。但從特征層面來看仍然存在欠缺，需要讓特征更加豐富化，深度挖掘特征之間的潛在價值。

基礎特征構建

圖4. 基礎特征構成

特征作為ETA中的重要部分，決定了ETA的上限。我們基于人工經(jīng)驗和業(yè)務理解構建了不同的離線特征和在線特征。

(1) 離線特征

a. 商戶畫像：商戶平均送達時長、到店時長、取餐時長、出餐狀況、單量、種類偏好、客單價、平均配送距離。

b. 配送區(qū)域畫像：區(qū)域運力平均水平、騎手規(guī)模、單量規(guī)模、平均配送距離。

(2) 在線特征

a. 商家實時特征：商家訂單擠壓狀況、過去N分鐘出單量、過去N分鐘進單量。

b. 區(qū)域實時特征：在崗騎手實時規(guī)模、區(qū)域擠壓（未取餐）單量、運力負載狀況。

c. 訂單特征：配送距離、價格、種類、時段。

d. 天氣數(shù)據(jù)：溫度、氣壓、降水量。

其中區(qū)域實時特征和商家實時特征與配送運力息息相關，運力是決定配送時長和用戶體驗的重要因素。

GBDT模型訓練和特征構造

利用基礎特征，訓練用于構造新特征的GBDT模型。在GBDT中，我們每次訓練一個CART（Classification And Regression Trees）回歸樹，基于當前輪次CART樹的損失函數(shù)的逆向梯度，擬合下一個CART樹，直到滿足要求為止。

(1) 超參數(shù)選擇

a. 首先為了節(jié)點分裂時質量和隨機性，分裂時所使用的***特征數(shù)目為√n。

b. GBDT迭代次數(shù)（樹的數(shù)量）。

樹的數(shù)量決定了后續(xù)構造特征的規(guī)模，與學習速率相互對應。通常學習速率設置較小，但如果過小，會導致迭代次數(shù)大幅增加，使得新構造的特征規(guī)模過大。

通過GridSearch+CrossValidation可以尋找到最合適的迭代次數(shù)+學習速率的超參組合。

c. GBDT樹深度需要足夠合理，通常在4~6較為合適。

雖然增加樹的數(shù)量和深度都可以增加新構造的特征規(guī)模。但樹深度過大，會造成模型過擬合以及導致新構造特征過于稀疏。

(2) 訓練方案

將訓練數(shù)據(jù)隨機抽樣50%，一分為二。前50%用于訓練GBDT模型，后50%的數(shù)據(jù)在通過GBDT輸出樣本在每棵樹中輸出的葉子節(jié)點索引位置，并記錄存儲，用于后續(xù)的新特征的構造和編碼，以及后續(xù)模型的訓練。如樣本x通過GBDT輸出后得到的形式如下：x → [25,20,22,....,30,28] ，列表中表示樣本在GBDT每個樹中輸出的葉子節(jié)點索引位置。

OneHotEncoder（新特征熱編碼）

圖5. OneHotEncoder(新特征熱編碼)使用方法

由于樣本經(jīng)過GBDT輸出后得到的x → [25,20,22,....,30,28] 是一組新特征，但由于這組新特征是葉子節(jié)點的ID，其值不能直接表達任何信息，故不能直接用于ETA場景的預估。為了解決上述的問題，避免訓練過程中無用信息對模型產(chǎn)生的負面影響，需要通過獨熱碼（OneHotEncoder）的編碼方式對新特征進行處理，將新特征轉化為可用的0-1的特征。

以圖5中的***棵樹和第二棵樹為例，***棵樹共有三個葉子節(jié)點，樣本會在三個葉子節(jié)點的其中之一輸出。所以樣本在該棵樹有會有可能輸出三個不同分類的值，需要由3個bit值來表達樣本在該樹中輸出的含義。圖中樣本在***棵樹的***個葉子節(jié)點輸出，獨熱碼表示為{100}；而第二棵樹有四個葉子節(jié)點，且樣本在第三個葉子節(jié)點輸出，則表示為{0010}。將樣本在每棵樹的獨熱碼拼接起來，表示為{1000010}，即通過兩棵CART樹構造了7個特征，構造特征的規(guī)模與GBDT中CART樹的葉子節(jié)點規(guī)模直接相關。

基于獨熱碼編碼新特征完成后，加上原來的基礎特征，特征規(guī)模達到1000+以上，實現(xiàn)特征豐富化。

評估指標與實踐效果

評估指標

與傳統(tǒng)的回歸問題不同，ETA與實際業(yè)務深度耦合，所以需要基于業(yè)務因素考慮更多的評估指標，以滿足各端（C端、R端）用戶利益。

① N分鐘準確率：訂單實際送達時長與預估時長的絕對誤差在N分鐘內的概率。

1.業(yè)務含義:

• 在N分鐘準確率中，N的判定方法來源于絕對誤差與用戶滿意度的關系曲線。通常絕對誤差在一定范圍內，用戶滿意度不會有明顯波動。如果發(fā)現(xiàn)當誤差大于K分鐘時，用戶滿意度出現(xiàn)明顯下滑，則可以將K做為N分鐘準確率中N的取值依據(jù)。
• 預估時長等同于平臺提供給C端用戶對送餐快慢的心理預期，如果N分鐘準確率越高，證明預估時長愈發(fā)接近用戶的心理預期，表示C端用戶體驗越好。

2.計算方法:

• Xi：樣本i的絕對誤差=abs(實際送達時長-預估時長)。
• 計算每個樣本的誤差的是否在N分鐘內，并統(tǒng)計概率P(Xi <= N)，如圖6、圖7所示。

圖6

圖6.判定訂單預估是否準確的計算方法

圖7

圖7.N分鐘準確率計算方法

② N分鐘業(yè)務準時率：實際送達時長與預估時長的差值在N分鐘內的概率。

1.業(yè)務含義：

• N分鐘業(yè)務準時率中N的判定方法與N分鐘準確率類似。
• N分鐘業(yè)務準時率是一種合理考核騎手以及保障騎手績效收益的指標。ETA場景與其它回歸場景相比，在預估準確的同時，預估合理性同樣很重要。N分鐘準確率雖然有效地量化C端用戶體驗指標，但無法衡量R端騎手體驗。所以N分鐘業(yè)務準時率是一個很好的補充指標。

2.計算方法：

• Xi，樣本i的有偏差值=(實際送達時長-預估時長)。
• 若Xi < 0 ，表示騎手提前送達，等同于業(yè)務準時。
• 若0 < Xi <= N ， 表示騎手在超時N分鐘內送達，等同于業(yè)務準時；但如果Xi > N ，表示騎手超時N分鐘以上送達，從指標層面看，該訂單騎手配送業(yè)務超時。
• 統(tǒng)計訂單配送不超時的概率P(Xi <= N)，計算方法與N分鐘準確率(圖7)類似。

實踐效果對比

我們在此之前已經(jīng)做了很多特征工程和優(yōu)化方面的工作，本次我們在不增加任何額外特征的情況下，僅通過模型架構的變化進行優(yōu)化。在對全量訂單進行評估對比的同時，我們對一些高價值和午高峰期間的訂單進行重點評估。

① 高價值訂單：高價值訂單僅占全量訂單的5%。這部分訂單用戶滿意度較低、配送體驗較差，屬于長尾訂單范疇，優(yōu)化難度高于其它類型訂單。

② 午高峰訂單：午高峰運單業(yè)務占比高達40%。午高峰期間，商家存在堂食和外賣資源爭搶問題，造成出餐時間不穩(wěn)定，導致業(yè)務中存在更多不確定性，預估難度明顯大于非高峰期。

將GBDT構造特征+Ridge與老版本base model（GBDT）進行對比。從結果上來看，構造新特征后，可以對ETA預估帶來更好的效果，其中在高價值訂單中，騎手的N分鐘業(yè)務準時率提升顯著。具體結論如下：

① 全量訂單

平均偏差(MAE)減少了3.4%，誤差率減少1.7個百分點，N分鐘準確率提升2.2個百分點，N分鐘業(yè)務準時率持平。

② 高價值訂單

平均偏差(MAE)減少了2.56%，誤差率減少1個百分點，N分鐘準確率提升1.6個百分點，N分鐘業(yè)務準時率提升3.46個百分點。

③ 午高峰訂單

平均偏差(MAE)減少了3.1%，誤差率減少1.4個百分點，N分鐘準確率提升1.7個百分點，N分鐘業(yè)務準時率持平。

從上述效果來看，GBDT構造特征可以給ETA場景帶來更多的提升，在線上使用時，也需要在性能和構造特征的規(guī)模上做出取舍。考慮到騎手的主觀能動性等因素，通常上線后，線上效果比線下試驗效果要更加樂觀。

總結

ETA 作為是外賣配送場景中最重要變量之一，是一個復雜程度較高的機器學習問題，其特征的豐富性決定了ETA的上限。在業(yè)務特征相對匱乏的情況下，GBDT+OneHotEncoder可以實現(xiàn)特征的豐富化，深度挖掘出特征的潛在價值。實驗結果顯示，在特征豐富化的情況下，ETA的準確度明顯提高。

與此同時，我們也在嘗試進行更多的探索。我們認為時序關系也是ETA場景的重要特征，并嘗試將該關系特征化加入到目前的模型和策略中，改善特征質量，提高ETA的預估能力上限。同時引入深度學習和增強學習，在提高上限的同時，用更好的模型去接近這個新的預估上限，為ETA的場景提升打下堅實的基礎。

【本文為51CTO專欄機構“美團點評技術團隊”的原創(chuàng)稿件，轉載請通過微信公眾號聯(lián)系機構獲取授權】

戳這里，看該作者更多好文