國(guó)際數(shù)據(jù)挖掘領(lǐng)域的頂級(jí)會(huì)議 KDD 2018 在倫敦舉行，今年 KDD 吸引了全球范圍內(nèi)共 1480 篇論文投遞，共收錄 293 篇，錄取率不足 20%。其中滴滴共有四篇論文入選 KDD 2018，涵蓋 ETA 預(yù)測(cè) (預(yù)估到達(dá)時(shí)間) 、智能派單、大規(guī)模車流管理等多個(gè)研究領(lǐng)域。

四篇論文分別是（文末附論文打包下載地址）

• Efficient Large-Scale Fleet Management via Multi-Agent Deep Reinforcement Learning

Kaixiang Lin (Michigan State University); Renyu Zhao (AI Labs, Didi Chuxing); Zhe Xu (AI Labs, Didi Chuxing); Jiayu Zhou (Michigan State University)

• Multi-task Representation Learning for Travel Time Estimation

Yaguang Li (University of Southern California); Kun Fu (DiDi AI Labs); Zheng Wang (DiDi AI Labs); Cyrus Shahabi (University of Southern California); Jieping Ye (DiDi AI Labs); Yan Liu (University of Southern California)

• Large-Scale Order Dispatch in On-Demand Ride-Sharing Platforms: A Learning and Planning Approach

Zhe Xu (AI Labs, Didi Chuxing); Zhixin Li (AI Labs, Didi Chuxing); Qingwen Guan (AI Labs, Didi Chuxing); Dingshui Zhang (AI Labs, Didi Chuxing); Qiang Li (AI Labs, Didi Chuxing); Junxiao Nan (AI Labs, Didi Chuxing); Chunyang Liu (AI Labs, Didi Chuxing); Wei Bian (AI Labs, Didi Chuxing); Jieping Ye (AI Labs, Didi Chuxing)

• Learning to Estimate the Travel Time

Zheng Wang (Didi Chuxing); Kun Fu (Didi Chuxing); Jieping Ye (Didi Chuxing)

昨天，我們重點(diǎn)對(duì)滴滴 KDD 2018 Poster 論文《Learning to Estimate the Travel Time》進(jìn)行了介紹，本文則是對(duì)滴滴 KDD 2018 Oral 論文《Large?Scale Order Dispatch in On?Demand Ride?Hailing Platforms: A Learning and Planning Approach》的詳細(xì)解讀。

在這篇文章中，滴滴技術(shù)團(tuán)隊(duì)在其 KDD 2017 論文《A Taxi Order Dispatch Model based On Combinatorial Optimization》的基礎(chǔ)上，新設(shè)計(jì)了一種基于馬爾可夫決策過(guò)程 (MDP) 的智能派單方法，通過(guò)將派單建模成為一個(gè)序列決策 (Sequential Decision Making) 問(wèn)題，結(jié)合了強(qiáng)化學(xué)習(xí)和組合優(yōu)化，能在即時(shí)完成派單決策的條件下，基于對(duì)全天供需、出行行為的預(yù)測(cè)和歸納，達(dá)到優(yōu)化一天之內(nèi)司機(jī)整體效率的效果，能在確保乘客出行體驗(yàn)的同時(shí)明顯提升司機(jī)的收入。

這一事件在雷鋒網(wǎng)學(xué)術(shù)頻道 AI 科技評(píng)論旗下數(shù)據(jù)庫(kù)項(xiàng)目「AI 影響因子」中有相應(yīng)加分。

研究背景

移動(dòng)出行的本質(zhì)是在乘客和司機(jī)之間建立連接。在滴滴，平臺(tái)日訂單達(dá) 3000 萬(wàn)，高峰期每分鐘接收超過(guò) 6 萬(wàn)乘車需求，如何設(shè)計(jì)一個(gè)更高效的匹配算法來(lái)進(jìn)行司機(jī)和乘客的撮合也成為非常核心的問(wèn)題。

當(dāng)下滴滴的專車、快車等業(yè)務(wù)線已經(jīng)在普遍使用智能派單模式，即從全局視角出發(fā)，由算法綜合考慮接駕距離、服務(wù)分、擁堵情況等因素，自動(dòng)將訂單匹配給最合適的司機(jī)接單。論文所述的算法也是在這一派單模式下的改進(jìn)。

然而實(shí)際上，出行場(chǎng)景下的司乘匹配非常復(fù)雜。一方面，高峰期出行平臺(tái)每分鐘會(huì)接到大量出行需求，一方面車輛會(huì)在路上不停地移動(dòng)，可能幾秒后這個(gè)司機(jī)就通過(guò)了一個(gè)路口，或是行駛上了高速路；不僅如此，每一次派單的決定也都在影響未來(lái)的司機(jī)分布。

這些都對(duì)算法提出更高的要求: 不僅需要足夠高效，能快速地對(duì)司機(jī)和乘客進(jìn)行動(dòng)態(tài)、實(shí)時(shí)的匹配，秒級(jí)做出決策，同時(shí)還要能基于未來(lái)情況的預(yù)測(cè)，考慮匹配算法的長(zhǎng)期收益。此外還要在考慮司機(jī)收入的同時(shí)保障用戶體驗(yàn)，全局優(yōu)化總體交通運(yùn)輸效率。

方法簡(jiǎn)述

為了解決上述問(wèn)題，滴滴技術(shù)團(tuán)隊(duì)創(chuàng)新性地提出了一個(gè)融合強(qiáng)化學(xué)習(xí)和組合優(yōu)化的框架。算法的主要思路如下：

1) 平臺(tái)下發(fā)派單決策需要在秒級(jí)做出，同時(shí)每次決策的優(yōu)化目標(biāo)均為提升長(zhǎng)期收益。由于該問(wèn)題自然形成了序列決策 (Sequential Decision Making) 的定義，使用馬爾可夫決策過(guò)程 (MDP) 進(jìn)行建模，并用強(qiáng)化學(xué)習(xí)求解;

2) 針對(duì)司乘間多對(duì)多的匹配，建模成一個(gè)組合優(yōu)化問(wèn)題，以獲得全局最優(yōu)。

通過(guò)將二者結(jié)合，即將組合優(yōu)化中的司機(jī)和乘客的匹配價(jià)值，用強(qiáng)化學(xué)習(xí)得到的價(jià)值函數(shù) (Value Function) 來(lái)表示，即得到了所述的算法，其流程如下圖所示。

模型定義

這一定義的馬爾可夫決策過(guò)程由以下模塊組成：

• 智能體 (agent)：定義每個(gè)司機(jī)為一個(gè)智能體。雖然此定義會(huì)使問(wèn)題變?yōu)橐粋€(gè)多智能體學(xué)習(xí) (multi-agent) 求解問(wèn)題，但單司機(jī)作為智能體的方式可大大減少狀態(tài)和動(dòng)作空間，使得求解變得可能；

• 狀態(tài) (state)：狀態(tài) s 定義了司機(jī)所處的周邊信息。為簡(jiǎn)化起見(jiàn)，論文定義司機(jī)所處的時(shí)間和空間為其狀態(tài)，并將時(shí)空進(jìn)行量化為 10 分鐘的時(shí)間段和固定大小的區(qū)域。這樣，一個(gè)完整的 episode（記為一天）由 144 個(gè)時(shí)間片組成，每個(gè)城市包含著數(shù)千至數(shù)萬(wàn)的區(qū)域單位。

• 動(dòng)作 (action)：動(dòng)作 a 定義了司機(jī)的完成訂單或空閑操作。對(duì)完成訂單而言，司機(jī)會(huì)經(jīng)過(guò)前往接乘客、等待乘客和送乘客到目的地等過(guò)程。

• 狀態(tài)轉(zhuǎn)移 (state transition) 與獎(jiǎng)勵(lì)函數(shù) (rewards)：完成訂單的動(dòng)作會(huì)自動(dòng)使司機(jī)發(fā)生時(shí)空狀態(tài)的轉(zhuǎn)移，其同時(shí)會(huì)帶來(lái)獎(jiǎng)勵(lì)，我們定義獎(jiǎng)勵(lì) r 為訂單的金額。

在定義了 MDP 的基本元素之后，下一步即選定一個(gè)最優(yōu)的策略，使其最大化累積期望收益。

匹配策略

在此 MDP 的定義下，平臺(tái)派單的過(guò)程即針對(duì)每一次分單的輪次（2 秒），平臺(tái)會(huì)取得每個(gè)待分配司機(jī)的狀態(tài) s，并將所有待分配訂單設(shè)為司機(jī)可執(zhí)行的動(dòng)作之一。該問(wèn)題的優(yōu)化目標(biāo)是 在確保用戶體驗(yàn)的基礎(chǔ)上最大化所有司機(jī)的收益總和。論文將其建模為二分圖匹配問(wèn)題，使用 KM((Kuhn-Munkres) 算法進(jìn)行求解。

在二分圖建圖的過(guò)程中，某司機(jī)和某訂單的邊權(quán)實(shí)際上表示了司機(jī)在狀態(tài) s 下，執(zhí)行完成訂單的動(dòng)作 a 下的預(yù)期收益，即強(qiáng)化學(xué)習(xí)中的動(dòng)作價(jià)值函數(shù) (Action-State Value Function) Q(s,a)。該函數(shù)表示了司機(jī)完成某訂單后，可獲得的預(yù)期收益，其包含了兩部分：訂單的即時(shí)收益 r，以及司機(jī)完成訂單后新?tīng)顟B(tài)下的預(yù)期收益期望。

價(jià)值函數(shù)

如何評(píng)估司機(jī)出現(xiàn)在某個(gè)特定時(shí)間/空間時(shí)的價(jià)值也成為一個(gè)核心問(wèn)題。在強(qiáng)化學(xué)習(xí)中的價(jià)值函數(shù)表示了智能體 (Agent) 在某狀態(tài)下的預(yù)期累積收益的期望。而在滴滴這一場(chǎng)景中，司機(jī)處在某狀態(tài)下的價(jià)值函數(shù)，則對(duì)應(yīng)了在常態(tài)狀態(tài)下司機(jī)出現(xiàn)在某時(shí)空位置下的預(yù)期流水收入。

通過(guò)將時(shí)間和空間進(jìn)行量化，再基于滴滴平臺(tái)上海量的歷史數(shù)據(jù)資源，滴滴使用動(dòng)態(tài)規(guī)劃 (Dynamic Programming) 的方法求解出了每個(gè)時(shí)空狀態(tài)下司機(jī)的預(yù)期收益，即價(jià)值函數(shù)。價(jià)值函數(shù)實(shí)際上代表了滴滴出行平臺(tái)上供需狀況的一種濃縮。下圖顯示了某城市晚高峰和平峰的價(jià)值函數(shù)示意。

價(jià)值函數(shù)和匹配策略相結(jié)合

將價(jià)值函數(shù)和組合優(yōu)化的目標(biāo)函數(shù)結(jié)合在一起，即形成了完整的派單方法。算法流程包括：

離線部分

步驟 1.1 收集歷史數(shù)據(jù)中的訂單信息，表示為強(qiáng)化學(xué)習(xí)中的四元組形式；

步驟 1.2 使用動(dòng)態(tài)規(guī)劃求解價(jià)值函數(shù)。將價(jià)值函數(shù)以查找表 (lookup table) 形式保存以供線上使用。

線上部分

步驟 2.1 收集待分配的司機(jī)和訂單列表;

步驟 2.2 計(jì)算每個(gè)司乘匹配對(duì)應(yīng)的動(dòng)作價(jià)值數(shù) (State-Action Function)，并以此為權(quán)重建立二分圖;

步驟 2.3 將上述匹配權(quán)值作為權(quán)重嵌入 KM 算法，充分考慮接駕距離、服務(wù)分等因素，求解最優(yōu)匹配，進(jìn)入最終派單環(huán)節(jié)。

迭代部分

步驟 3 迭代重復(fù)進(jìn)行 1 和 2，即根據(jù)新積累的數(shù)據(jù)離線更新價(jià)值函數(shù)，和使用更新后的價(jià)值函數(shù)指導(dǎo)派單的過(guò)程。

線上使用

滴滴團(tuán)隊(duì)進(jìn)行了大量的離線實(shí)驗(yàn)和在線 AB 測(cè)試，結(jié)果均顯示，這種基于強(qiáng)化學(xué)習(xí)和組合優(yōu)化的派單算法能在確保乘客出行體驗(yàn)的同時(shí)明顯提升司機(jī)的收入。目前該算法已成功部署在滴滴平臺(tái)二十多個(gè)核心城市，承接廣大用戶的出行需求。

結(jié)論和下一步計(jì)劃

滴滴團(tuán)隊(duì)指出，與傳統(tǒng)的「只考慮當(dāng)下」的策略不同，這一全新的基于強(qiáng)化學(xué)習(xí)和組合優(yōu)化的派單算法能能考慮到每一次派單的決定會(huì)對(duì)未來(lái)的司機(jī)分布發(fā)生影響，面向長(zhǎng)期收益。后續(xù)將在深度 Q 學(xué)習(xí) (DQN) 算法求解和不同城市間進(jìn)行遷移學(xué)習(xí)等方面持續(xù)優(yōu)化，并將持續(xù)拓展算法在其他應(yīng)用場(chǎng)景中的應(yīng)用。

（論文地址：Large?Scale Order Dispatch in On?Demand Ride?Hailing Platforms: A Learning and Planning Approach

http://delivery.acm.org/10.1145/3220000/3219824/p905-xu.pdf?ip=183.240.196.144&id=3219824&acc=OPENTOC&key=4D4702B0C3E38B35%2E4D4702B0C3E38B35%2E4D4702B0C3E38B35%2E054E54E275136550&__acm__=1534949330_cd114e6e3a392b6b3eeabeafae021d77）

或點(diǎn)擊本鏈接移步AI研習(xí)社社區(qū)下載四篇論文。

雷峰網(wǎng)原創(chuàng)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見(jiàn)轉(zhuǎn)載須知。