引言

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

圖1. ETA的業(yè)務(wù)價(jià)值

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

圖2. ETA架構(gòu)圖

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

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

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

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

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

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

GBDT構(gòu)造特征在ETA場景的中的應(yīng)用方案

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

基礎(chǔ)特征構(gòu)建

圖4. 基礎(chǔ)特征構(gòu)成

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

(1) 離線特征

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

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

(2) 在線特征

a. 商家實(shí)時特征：商家訂單擠壓狀況、過去N分鐘出單量、過去N分鐘進(jìn)單量。

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

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

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

其中區(qū)域?qū)崟r特征和商家實(shí)時特征與配送運(yùn)力息息相關(guān)，運(yùn)力是決定配送時長和用戶體驗(yàn)的重要因素。

GBDT模型訓(xùn)練和特征構(gòu)造

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

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

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

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

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

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

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

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

(2) 訓(xùn)練方案

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

OneHotEncoder（新特征熱編碼）

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

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

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

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

評估指標(biāo)與實(shí)踐效果

評估指標(biāo)

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

① N分鐘準(zhǔn)確率：訂單實(shí)際送達(dá)時長與預(yù)估時長的絕對誤差在N分鐘內(nèi)的概率。

1.業(yè)務(wù)含義:

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

2.計(jì)算方法:

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

圖6

圖6.判定訂單預(yù)估是否準(zhǔn)確的計(jì)算方法

圖7

圖7.N分鐘準(zhǔn)確率計(jì)算方法

② N分鐘業(yè)務(wù)準(zhǔn)時率：實(shí)際送達(dá)時長與預(yù)估時長的差值在N分鐘內(nèi)的概率。

1.業(yè)務(wù)含義：

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

2.計(jì)算方法：

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

實(shí)踐效果對比

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

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

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

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

① 全量訂單

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

② 高價(jià)值訂單

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

③ 午高峰訂單

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

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

總結(jié)

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

與此同時，我們也在嘗試進(jìn)行更多的探索。我們認(rèn)為時序關(guān)系也是ETA場景的重要特征，并嘗試將該關(guān)系特征化加入到目前的模型和策略中，改善特征質(zhì)量，提高ETA的預(yù)估能力上限。同時引入深度學(xué)習(xí)和增強(qiáng)學(xué)習(xí)，在提高上限的同時，用更好的模型去接近這個新的預(yù)估上限，為ETA的場景提升打下堅(jiān)實(shí)的基礎(chǔ)。

【本文為51CTO專欄機(jī)構(gòu)“美團(tuán)點(diǎn)評技術(shù)團(tuán)隊(duì)”的原創(chuàng)稿件，轉(zhuǎn)載請通過微信公眾號聯(lián)系機(jī)構(gòu)獲取授權(quán)】

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