貨拉拉KDD2021論文詳解：MoD系統(tǒng)中信息披露的優(yōu)化方法

量子位的朋友們 2021-06-24 20:17:57 來(lái)源：量子位

近日，國(guó)際數(shù)據(jù)科學(xué)和數(shù)據(jù)挖掘領(lǐng)域的最頂級(jí)學(xué)術(shù)會(huì)議KDD入選論文正式揭曉。今年KDD吸引了全球范圍內(nèi)705篇論文投遞，僅收錄了138篇論文，收錄率不足20%。貨拉拉論文《Improving the Information Disclosure in Mobility-on-Demand Systems》（《一種MoD系統(tǒng)中信息披露的優(yōu)化方法》）從705篇論文中脫穎而出成功入選。該論文通過(guò)數(shù)據(jù)建模解決互聯(lián)網(wǎng)物流智能分單問(wèn)題，提升互聯(lián)網(wǎng)物流平臺(tái)效率，實(shí)現(xiàn)業(yè)務(wù)指標(biāo)優(yōu)化。

本文對(duì)貨拉拉論文《Improving the Information Disclosure in Mobility-on-Demand Systems》進(jìn)行詳細(xì)解讀。貨拉拉技術(shù)團(tuán)隊(duì)該論文中提出了一種優(yōu)化信息披露方式的框架，通過(guò)建模和求解，通過(guò)算法選取最合適的司機(jī)進(jìn)行履約，實(shí)現(xiàn)訂單的精準(zhǔn)推送，實(shí)現(xiàn)平臺(tái)效率、用戶體驗(yàn)和司機(jī)體驗(yàn)的整體提升。

一、研究背景

當(dāng)下貨拉拉貨運(yùn)采用的訂單分配方式為全局廣播，即在指定 時(shí)間/距離 等范圍內(nèi)，將所有訂單推送給所有司機(jī)，司機(jī)通過(guò)瀏覽訂單列表的方式，做抉擇，選取符合預(yù)期的訂單進(jìn)行響應(yīng)，對(duì)于同一訂單被多個(gè)司機(jī)響應(yīng)的場(chǎng)景，由算法綜合考慮平臺(tái)效率、用戶體驗(yàn)、司機(jī)體驗(yàn)等因素，選取最合適的司機(jī)進(jìn)行履約。

定義訂單推送給司機(jī)為一種信息披露，本論文提出的算法便是在訂單廣播環(huán)節(jié)提出的改進(jìn)。

作為司機(jī)，處于不同的狀態(tài)（時(shí)空，供需，今日累計(jì)工作時(shí)長(zhǎng)，今日累計(jì)收入等），面對(duì)不同的選擇（訂單列表），對(duì)收入的期望也會(huì)有所差異。

舉幾個(gè)例子：

1） 供給受限的情況，待匹配訂單數(shù)遠(yuǎn)遠(yuǎn)大于運(yùn)力數(shù)

司機(jī)相對(duì)主動(dòng)，傾向于接價(jià)格更高的訂單；

2）需求受限的情況，待匹配訂單數(shù)遠(yuǎn)遠(yuǎn)小于運(yùn)力數(shù)

司機(jī)相對(duì)被動(dòng)，傾向于選擇不空駛，盡量不計(jì)較價(jià)格；

3）無(wú)限制的播單場(chǎng)景，司機(jī)的訂單列表里有全城，甚至是全國(guó)的訂單

司機(jī)相對(duì)主動(dòng)，在系統(tǒng)訂單過(guò)剩時(shí)，會(huì)選擇困難；

4）強(qiáng)限制的派單場(chǎng)景，司機(jī)的訂單列表里不超過(guò)一個(gè)訂單

司機(jī)相對(duì)被動(dòng)，在系統(tǒng) 沒(méi)有派單/派單不滿意 時(shí)，會(huì)有焦慮感；

通過(guò)對(duì)司機(jī)的決策行為進(jìn)行準(zhǔn)確地估計(jì)，并通過(guò)優(yōu)化信息披露（哪些訂單給哪些司機(jī)看）的方式，我們期望實(shí)現(xiàn)司機(jī)體驗(yàn)、用戶體驗(yàn)和平臺(tái)效率的整體提升。

二、研究?jī)r(jià)值

1.區(qū)別于傳統(tǒng)的推薦系統(tǒng)，例如抖音，豆瓣，淘寶等，電商網(wǎng)站的商品，以及短視頻等內(nèi)容，相對(duì)來(lái)說(shuō)是一個(gè)不受限的資源，即一個(gè)商品可以被成百上千個(gè)用戶購(gòu)買，一條視頻可以被推薦給千千萬(wàn)萬(wàn)的用戶。

貨拉拉場(chǎng)景：訂單因時(shí)空問(wèn)題，會(huì)被推送給有限個(gè)司機(jī)；司機(jī)因屏幕問(wèn)題，只能瀏覽有限個(gè)訂單。這一類帶資源約束的問(wèn)題，目前沒(méi)有成熟有效的解決方案。

2.區(qū)別于傳統(tǒng)的派單模式，眾包業(yè)務(wù)的播單模式引入了更多的運(yùn)力保障。

a.引入了更多的復(fù)雜度

對(duì)于m個(gè)司機(jī)，n個(gè)訂單的業(yè)務(wù)場(chǎng)景

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

純暴力的搜索空間：

隨著問(wèn)題規(guī)模的不斷變大， 其對(duì)應(yīng)復(fù)雜度呈指數(shù)增長(zhǎng)。

b.引入了更多的司機(jī)競(jìng)爭(zhēng)

不管是供給過(guò)剩，還是需求過(guò)剩的場(chǎng)景，司機(jī)對(duì)某一類訂單的偏好比較一致，例如高價(jià)格、高小費(fèi)等屬性，導(dǎo)致該類訂單響應(yīng)的司機(jī)數(shù)多，而訂單最終只能由一位司機(jī)來(lái)履約，勢(shì)必產(chǎn)生很多的無(wú)效司機(jī)選擇，導(dǎo)致平臺(tái)整體效率降低。

三、算法框架

1.預(yù)測(cè)

基于業(yè)務(wù)場(chǎng)景下的條件依賴，我們拓展了Multinormal Logit Model，將司機(jī)的決策分兩步來(lái)估計(jì)：

a.司機(jī)選擇接單，或者不接單

b.司機(jī)選擇候選列表中的某一訂單進(jìn)行響應(yīng)

通過(guò)在歷史行為數(shù)據(jù)上做最大化對(duì)數(shù)似然估計(jì)，我們對(duì)模型的參數(shù)進(jìn)行擬合：

可以逐級(jí)來(lái)分析建模的合理性：

1）第一級(jí)，司機(jī)看到某個(gè)訂單列表，有一定的概率會(huì)選擇不接單，如果當(dāng)前的列表他不滿意，他會(huì)等待，直到在未來(lái)的某個(gè)時(shí)空出現(xiàn)滿意的候選訂單列表；

2）第二級(jí)，司機(jī)認(rèn)為當(dāng)前訂單列表滿意

i） 會(huì)從中選取最偏好的訂單響應(yīng)；

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

2.規(guī)劃

a.目標(biāo)函數(shù)

b.問(wèn)題求解

i. 全局的信息披露

ii. 局部的信息披露

iii. 原始的砍邊算法

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

整體算法如下：

3.實(shí)驗(yàn)

a.離線：

選取貨拉拉平臺(tái)上3個(gè)城市的歷史數(shù)據(jù)，訓(xùn)練司機(jī)決策預(yù)估模型

b.在線：

選取貨拉拉平臺(tái)上3個(gè)城市的若干時(shí)間段，按照分組輪換做AB實(shí)驗(yàn)

A：貨拉拉現(xiàn)有的全局信息披露方式

B：基于司機(jī)決策預(yù)估模型的$$MLEC$$算法框架

l 定量結(jié)果（從整體的響應(yīng)率、司機(jī)使用率來(lái)看，提出框架有較大提升）

l 定性結(jié)果（顏色越深，表示訂單響應(yīng)問(wèn)題比較嚴(yán)重，提出框架能夠緩解整體的局部供需問(wèn)題）

《Improving the Information Disclosure in Mobility-on-Demand Systems》論文提出了一種優(yōu)化信息披露方式的框架，通過(guò)建模和求解，實(shí)現(xiàn)業(yè)務(wù)指標(biāo)的優(yōu)化。這項(xiàng)研究不僅適用于貨拉拉這種互聯(lián)網(wǎng)物流平臺(tái)，同樣也可應(yīng)用于帶資源約束的推薦系統(tǒng)。

— 完 —