前言
近日，阿裡本地生活智慧物流團隊的一篇論文——Order Fulfillment Cycle Time Estimation for On-Demand Food Delivery被KDD’2020 Applied Data Science Track接收為Oral presentation（ACM Knowledge Discovery and Data Mining（SIGKDD），CCF A類會議，資料挖掘領域頂級會議，2020 年的口頭報告接受率為 5.8%）。
外賣履約時間預估（OFCT：Order Fulfillment Cycle Time）問題相比一般的時間預估問題而言更為複雜，其中存在餐廳與使用者的供需關系、餐廳出餐時間的未知性以及騎手行為的不确定性等問題。在論文中我們向學術界首次詳細介紹外賣履約時間預估這一問題，并給出了有效的解決方案，最後得到了審稿人的一緻認可。
通過逐漸拆解整個外賣履約（履約：餓了麼平台保障騎手能夠将外賣準時送達給使用者）的過程，我們分析了外賣履約時間預估相比常見的其他送達時間問題（例如打車）的顯著差異，并針對影響履約時間長短的特征進行了解釋和說明。對于使用者而言可能隻是看到外賣需要多久才能吃到，而在這背後需要我們提煉出豐富的影響因素，來保證履約時間預估的準确性。我們将這些影響因素輸入深度神經網絡來推斷它們和履約時長的關系，同時我們進一步引入了餐廳、使用者位址以及騎手的隐向量來增強模型的預測性能。最後，我們提出一個新穎的後處理神經網絡算子，用于改善模型的收斂速度和準确度。我們所介紹的模型已在餓了麼實際部署，每天服務于千萬使用者。
背景介紹
履約時間預估模型預估的是從使用者下單到騎手将訂單送達使用者手上的這段時間（即預計送達時間）。餓了麼平台每天産生千萬級訂單量，時間預估作為即時配送的其中一環，既影響使用者體驗同時也涉及到騎手履約，是以其準确性對平台而言至關重要，既不能預估的太長（影響使用者體驗），也不能預估的太短（騎手無法按時完成配送）。下圖為時間預估涉及的各個環節。
主要環節包括：
- 使用者：使用者從下單到訂單送達其手中。對于每一位使用者而言，肯定是希望能夠準時拿到下單的餐品。
- 餐廳：餐廳從接受訂單到備餐完成。餐廳需要做到盡快完成備餐，這樣才能夠不影響騎手取餐及配送，如果騎手到達餐廳的時候需要等待很久的時間才能取走餐品，那麼騎手容易焦慮，一部分使用者也會在餓了麼App上催促騎手。
- 騎手：騎手從接收到訂單到完成配送。其中包括騎手到達餐廳，然後從餐廳處取走訂單對應的餐品。同時，騎手可能從餐廳處取多餐，是以需要等拿到所有訂單騎手才會離開并進行配送。
- 平台：餓了麼平台需要從中協調使用者、餐廳、騎手并兼顧配送效率。這其中包括訂單指派與路徑規劃。訂單指派是指将訂單分給附近合适的騎手，而路徑規劃是指給騎手推薦合理的取送路徑，此路徑需要同時考慮騎手配送距離和訂單逾時風險。
下圖即為大家日常在餓了麼上面點外賣的時候能夠看到的資訊，其中配送時間就是我們履約時間預估模型計算出的。
外賣履約時間與 ETA 的差異
Estimated Time of Arrival (ETA)即“預估送達時間”，一般預估的是從出發地到目的地的時間，打車場景中的預估送達時間即為一類典型的ETA問題。
本文提出的外賣履約時間預估模型，預估的是從使用者下單開始到騎手将餐品送達使用者手中所花的時間，使用者在餓了麼點了外賣以後，訂單在平台開始流轉的過程如下圖所示。
外賣履約時間預估相比預估送達時間而言更為特殊，主要展現在以下兩方面：
1 需要考慮更多影響因素
一般的預估送達時間問題僅需考慮天氣、交通狀況，時空資訊及路徑資訊等，而外賣履約時間預估問題除了考慮此類資訊外，還需考慮餐廳的地理位置，餐廳訂單備餐時間以及排程系統派單等資訊。
2 無法擷取關鍵資訊
使用者下單成功時餓了麼已經為使用者預估出預計送達時間，而此時訂單并未被騎手接單，騎手需要被系統指派才能開始取餐和配送，是以我們無法提前擷取騎手的資訊及其實際的配送路徑。
以上兩方面的差異給外賣履約時間預估問題的準确性帶來極大的挑戰。
外賣履約時間預測一般需要哪些特征
為了模組化外賣履約時間，一般需要充分利用與訂單資訊相關的資料，具體包括：
- 空間特征：包括大量id類特征，例如使用者所在區域id，餐廳id，城市id及網格id等。
- 時間特征：包括小時時刻，當天是否工作日等，如下圖（a）。
- 描述訂單大小的特征：包括訂單對應的菜品數量以及訂單價格等。
大家應該會好奇訂單價格會對外賣時間長短造成什麼影響？當使用者下單的金額較高時通常餐品對應的重量或體積較大，比如使用者預訂了蛋糕或者集體點了很多杯奶茶，這種總金額高的訂單對于騎手而言屬于難配送訂單，是以需要花費較長的履約時間。下圖（b）展示出了這種相關性，可以看到訂單價格的高低在一定程度上可以刻畫出訂單是否難配送的隐含資訊。
供需關系對履約時長的影響
從平台角度看，使用者下單量和餐廳接單量不同時刻都在發生劇烈變化，這種供需次元上的變化對實際配送時長會造成極大影響。
在介紹供需特征構造的工作前，先為大家介紹外賣配送中“波次”的概念：對于騎手身上的一組訂單，對給定的一組訂單取送順序進行分組，保證每組中所有相關訂單的取和送行為都在該組中，該分組則為騎手目前配送的波次。針對供需變化，我們構造了基于時段的供需比和完成率等特征。當供需比越高時波次的平均長度會變長，此時履約時間越長。
另一方面當完成率越高時可以推斷出騎手完成配送的訂單越多，此時騎手可以繼續承接系統接下來分派的訂單。
此外，我們通過餐廳目前待取餐單量（餐廳接單後等待騎手來取的訂單數）來刻畫餐廳的繁忙程度，當餐廳接單數變多而産能受限時會導緻訂單積壓，此時如果騎手已經到達餐廳則需要花費較長的等待時間才能取到餐品，相應的當餐廳變繁忙時，模型預估的履約時間将變長。
餐廳的出餐時間
訂單的出餐時間是外賣履約時間預估模型的一個重要影響因素，這個特征我們是通過聚合餐廳的曆史出餐時間得到的。但目前存在的難點問題對出餐時間計算的準确性帶來極大考驗，主要包括：
- 餐廳在備餐完成後缺乏人力來逐單點選出餐按鈕，導緻我們平台不能完全搜集到餐廳出餐的真實值，是以我們目前主要依靠系統采集的騎手點選出餐資料來标記餐廳的真實出餐時間。
- 餓了麼平台目前主要計算的是餐廳在餓了麼App産生的訂單，缺乏餐廳在其他管道産生的訂單或堂食訂單資料，是以較難擷取餐廳的實際供需情況。
- 餐廳的真實出餐時間具有較大的随機性。例如餐廳針對某些餐品可能會提前進行備餐，這部分提前備好的餐品可以立即出餐。而對于使用者下單時餐廳需要現做的餐品，騎手到達餐廳後可能需要等待一段時間才能取到餐，這部分現做的訂單真實出餐時間将會偏長。
- 訂單的先後順序不一定表示餐廳出餐的先後順序。由于餐廳竈台數量有限，相應的竈台隻會處理固定的菜品，是以在一批訂單中如果出現相同的菜品，後廚會選擇一起做，這種情況下部分訂單的出餐時間會明顯偏短。
在實際運用時，我們是根據商家接單時間到騎手實際點選取餐時間來計算商戶的真實出餐時間，而這其中存在一部分噪音資料：
- 騎手接單後即刻點選到達餐廳
- 騎手接單後即刻點選取餐按鈕
此外，對于一部分訓練樣本，我們認為騎手在取到餐品時實際上餐廳已經備餐完成，例如騎手晚取餐或騎手同時點選取多餐。針對這些資料我們在計算餐廳出餐時間特征時進行了一定比例的剔除。
如何合理利用騎手資訊
餓了麼從平台角度出發，将每個城市劃分成了以“網格”為最小單元的不同區域，每個蜂鳥配送站點内的騎手會服務于站點周邊範圍内固定的若幹個網格，騎手對站點輻射的網格内的商圈或者小區的熟悉程度決定了其配送效率。從下圖大家可以看到，因為騎手對餐廳所在位置、使用者所在小區都比較熟悉，是以在取餐或者配送的過程中并沒有發生繞路的情況。
而使用者下單成功時餓了麼App會立刻為使用者顯示外賣預估履約時間，此時訂單指派給具體哪位騎手來配送是未知的。為了充分利用與騎手相關的影響因素，我們根據騎手取餐距離、騎手目前接了多少訂單等特征來表征訂單可能被接單的每一位騎手，然後将可能接單的騎手序列進行特征編碼傳入外賣履約時間預估模型中，随後利用注意力機制提取騎手序列資訊，以此來增強模型的預測能力。
多元度相似訂單的配送段 ETA
配送段ETA指的是預估騎手到達目的地（使用者所在位置）附近下車後将餐品送到使用者手中所花的時間，是騎手配送的最終環節。
為了估算配送段ETA，我們理論上可以直接采用回歸模型來學習，但是常用的回歸模型通常将輸入轉化為一系列的特征，并且通過有監督學習找到這些影響因素和輸出目标之間的關系，為了友善學習和提高模型泛化能力通常基于神經網絡和內建樹模型将這些關系參數化為一個平滑的函數，但這種平滑假設的缺點是無法很好的處理長尾不規律case，可能會影響使用者體驗。例如當騎手送餐需要乘坐高層電梯時，如果遇上高峰期，可能需要等待很長的時間，而系統很難做到這種實時的預判。從下圖可以看出，騎手送餐時在樓内花了7.6分鐘。
為了部分緩解這種問題，我們借鑒了近期基于記憶的語言模型[1]的思想，将曆史訂單作為配送段時間預估的語料，通過構造多元特征來表征每個曆史訂單，當新的訂單産生時我們基于K近鄰來搜尋出與新訂單相似的若幹個曆史訂單，然後對這若幹個相似單的真實配送段時間做權重平均，以此作為新訂單的預估配送段時間。最終我們将基于K近鄰搜尋出的預估配送段時間作為特征輸入外賣履約時間預估模型中。
針對長尾資料如何解決
時間預估本質上屬于回歸問題，在訓練模型的過程中我們發現模型收斂較慢且交叉驗證的表現偏離預期，通過分析原因我們發現模型拟合的資料分布與真實履約時間的分布發生了偏移，真實的履約時間實際上是一個右偏長尾的分布，相當于有一小部分訂單真實的配送時間偏長而模型沒有學習到，針對此問題在本文中我們提出了一個新穎的後處理神經網絡算子，針對外賣履約時間預估模型的拟合結果進行縮放和變換，用于改善模型的收斂速度和準确度。此後處理算子可描述為：
其中，
經過離線訓練驗證，後處理算子可有效提升外賣履約時間預估模型收斂速度和準确度。
近期，我們又探索出一種新的後處理算子：自适應Box-Cox逆變換，相比于本文提出的後處理算子，自适應Box-Cox逆變換算子更加能夠拟合長尾資料分布，使模型效果得到了進一步改善，目前此算子已經應用于線上推斷。
實驗效果
我們提出的外賣履約時間預估模型以“編碼及預測”作為模型主體結構，具體結構如下圖所示。
其中，Nearest Courier Index這個子產品實作了前面介紹的騎手資訊編碼，這個子產品可以讓模型充分利用可能接單的騎手資訊；Postprocessing即為後處理算子，這個算子讓模型能夠更快收斂，同時也提升了模型的準确率。
在我們提出外賣履約時間預估模型前，線上時間預估模型已經穩定運作了一段時間，是以我們以線上已有模型作為baseline進行了AB實驗。下圖實驗資料顯示，外賣履約時間預估模型相比于原有模型，MAE相對降低9.8%，使用者投訴率相對降低19.3%，預測誤差和使用者投訴率均有明顯改善，對使用者體驗産生了明顯的正向效果。
總結與展望
在本文中我們為大家介紹了餓了麼目前線上實際運作并服務于使用者的外賣履約時間預估模型，通過離線評測及線上測試均證明了其有效性。
未來我們主要将着力于如下兩方面繼續研究：
- 出餐時間作為外賣履約時間預估模型的影響因素之一對其相當重要，但目前出餐時間處理相對簡單是以具有相當大的提升空間。
- 此外，我們将研發出一套通用的模型架構，即針對出餐時間和履約時間進行多任務學習。
參考文獻
[1] Urvashi Khandelwal, Omer Levy, Dan Jurafsky, Luke Zettlemoyer, and Mike Lewis. Generalization through memorization: Nearest neighbor language models. In ICLR, 2020.
深度學習課程 | 神經網絡概覽及算法詳解
人工神經網絡（Artificial Neural Networks，簡寫為 ANN）是一種模仿動物神經網絡行為特征，進行分布式并行資訊處理的算法數學模型。本課程共 36 課時，主要介紹神經網絡學習規則、感覺神經網絡、競争神經網絡及回報神經網絡等，幫助大家掌握神經網絡的相關概念和算法模型。
識别下方二維碼或點選文末“
閱讀原文”立刻學習吧：