貨拉拉KDD2021論文詳解：MoD系統中信息披露的優化方法

近日，國際數據科學和數據挖掘領域的最頂級學術會議KDD入選論文正式揭曉。今年KDD吸引了全球范圍內705篇論文投遞，僅收錄了138篇論文，收錄率不足20%。貨拉拉論文《Improving the Information Disclosure in Mobility-on-Demand Systems》（《一種MoD系統中信息披露的優化方法》）從705篇論文中脫穎而出成功入選。該論文通過數據建模解決互聯網物流智能分單問題，提升互聯網物流平臺效率，實現業務指標優化。

本文對貨拉拉論文《Improving the Information Disclosure in Mobility-on-Demand Systems》進行詳細解讀。貨拉拉技術團隊該論文中提出了一種優化信息披露方式的框架，通過建模和求解，通過算法選取最合適的司機進行履約，實現訂單的精準推送，實現平臺效率、用戶體驗和司機體驗的整體提升。

一、研究背景

當下貨拉拉貨運采用的訂單分配方式為全局廣播，即在指定 時間/距離 等范圍內，將所有訂單推送給所有司機，司機通過瀏覽訂單列表的方式，做抉擇，選取符合預期的訂單進行響應，對于同一訂單被多個司機響應的場景，由算法綜合考慮平臺效率、用戶體驗、司機體驗等因素，選取最合適的司機進行履約。

定義訂單推送給司機為一種信息披露，本論文提出的算法便是在訂單廣播環節提出的改進。

作為司機，處于不同的狀態（時空，供需，今日累計工作時長，今日累計收入等），面對不同的選擇（訂單列表），對收入的期望也會有所差異。

舉幾個例子：

1） 供給受限的情況，待匹配訂單數遠遠大于運力數

司機相對主動，傾向于接價格更高的訂單；

2）需求受限的情況，待匹配訂單數遠遠小于運力數

司機相對被動，傾向于選擇不空駛，盡量不計較價格；

3）無限制的播單場景，司機的訂單列表里有全城，甚至是全國的訂單

司機相對主動，在系統訂單過剩時，會選擇困難；

4）強限制的派單場景，司機的訂單列表里不超過一個訂單

司機相對被動，在系統 沒有派單/派單不滿意 時，會有焦慮感；

通過對司機的決策行為進行準確地估計，并通過優化信息披露（哪些訂單給哪些司機看）的方式，我們期望實現司機體驗、用戶體驗和平臺效率的整體提升。

二、研究價值

1、區別于傳統的推薦系統，例如抖音，豆瓣，淘寶等，電商網站的商品，以及短視頻等內容，相對來說是一個不受限的資源，即一個商品可以被成百上千個用戶購買，一條視頻可以被推薦給千千萬萬的用戶。

貨拉拉場景：訂單因時空問題，會被推送給有限個司機；司機因屏幕問題，只能瀏覽有限個訂單。這一類帶資源約束的問題，目前沒有成熟有效的解決方案。

2、區別于傳統的派單模式，眾包業務的播單模式引入了更多的運力保障。 

a、引入了更多的復雜度

對于m個司機，n個訂單的業務場景

派單解決的是1vs1的匹配問題，播單解決的問題是n vs m的信息披露問題

純暴力的搜索空間：

 

隨著問題規模的不斷變大， 其對應復雜度呈指數增長。

b、引入了更多的司機競爭

不管是供給過剩，還是需求過剩的場景，司機對某一類訂單的偏好比較一致，例如高價格、高小費等屬性，導致該類訂單響應的司機數多，而訂單最終只能由一位司機來履約，勢必產生很多的無效司機選擇，導致平臺整體效率降低。

三、算法框架

1、預測

基于業務場景下的條件依賴，我們拓展了Multinormal Logit Model，將司機的決策分兩步來估計：

a、司機選擇接單，或者不接單

b、司機選擇候選列表中的某一訂單進行響應

 

通過在歷史行為數據上做最大化對數似然估計，我們對模型的參數進行擬合：

可以逐級來分析建模的合理性：

1）第一級，司機看到某個訂單列表，有一定的概率會選擇不接單，如果當前的列表他不滿意，他會等待，直到在未來的某個時空出現滿意的候選訂單列表；

2）第二級，司機認為當前訂單列表滿意

i） 會從中選取最偏好的訂單響應；

ii）基于此候選訂單列表，如果減少訂單o的信息披露，則司機對于其他訂單 o'的接單意愿會提升，而司機對于第一級的 不接單的概率也會提升（第一級的滿意度降低）

2、規劃

a、目標函數

 

b、問題求解

i、全局的信息披露

ii、局部的信息披露

iii、原始的砍邊算法

iv、最小化損失的砍邊算法（Minimal Loss Edge Cutting）

整體算法如下：

 

3、實驗

a、離線：

選取貨拉拉平臺上3個城市的歷史數據，訓練司機決策預估模型

b、在線：

選取貨拉拉平臺上3個城市的若干時間段，按照分組輪換做AB實驗

A：貨拉拉現有的全局信息披露方式

B：基于司機決策預估模型的$$MLEC$$算法框架

• 定量結果（從整體的響應率、司機使用率來看，提出框架有較大提升）

 

解整體的局部供需問題

• 定性結果（顏色越深，表示訂單響應問題比較嚴重，提出框架能夠緩）

《Improving the Information Disclosure in Mobility-on-Demand Systems》論文提出了一種優化信息披露方式的框架，通過建模和求解，實現業務指標的優化。這項研究不僅適用于貨拉拉這種互聯網物流平臺，同樣也可應用于帶資源約束的推薦系統。

雷鋒網雷鋒網