滴滴 KDD 2018 論文詳解：基於強化學習技術的智能派單模型

國際數據挖掘領域的頂級會議 KDD 2018 在倫敦舉行，今年 KDD 吸引了全球範圍內共 1480 篇論文投遞，共收錄 293 篇，錄取率不足 20%。其中滴滴共有四篇論文入選 KDD 2018，涵蓋 ETA 預測 (預估到達時間) 、智能派單、大規模車流管理等多個研究領域。

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

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)

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

在這篇文章中，滴滴技術團隊在其 KDD 2017 論文《A Taxi Order Dispatch Model based On Combinatorial Optimization》的基礎上，新設計了一種基於馬爾可夫決策過程 (MDP) 的智能派單方法，通過將派單建模成為一個序列決策 (Sequential Decision Making) 問題，結合了強化學習和組合優化，能在即時完成派單決策的條件下，基於對全天供需、出行行為的預測和歸納，達到優化一天之內司機整體效率的效果，能在確保乘客出行體驗的同時明顯提升司機的收入。

這一事件在雷鋒網學術頻道 AI 科技評論旗下資料庫項目「AI 影響因子」中有相應加分。

研究背景

移動出行的本質是在乘客和司機之間建立連接。在滴滴，平台日訂單達 3000 萬，高峰期每分鐘接收超過 6 萬乘車需求，如何設計一個更高效的匹配演算法來進行司機和乘客的撮合也成為非常核心的問題。

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

然而實際上，出行場景下的司乘匹配非常複雜。一方面，高峰期出行平台每分鐘會接到大量出行需求，一方面車輛會在路上不停地移動，可能幾秒後這個司機就通過了一個路口，或是行駛上了高速路；不僅如此，每一次派單的決定也都在影響未來的司機分布。

這些都對演算法提出更高的要求: 不僅需要足夠高效，能快速地對司機和乘客進行動態、實時的匹配，秒級做出決策，同時還要能基於未來情況的預測，考慮匹配演算法的長期收益。此外還要在考慮司機收入的同時保障用戶體驗，全局優化總體交通運輸效率。

方法簡述

為了解決上述問題，滴滴技術團隊創新性地提出了一個融合強化學習和組合優化的框架。演算法的主要思路如下：

1)平台下發派單決策需要在秒級做出，同時每次決策的優化目標均為提升長期收益。由於該問題自然形成了序列決策 (Sequential Decision Making) 的定義，使用馬爾可夫決策過程 (MDP) 進行建模，並用強化學習求解;

2)針對司乘間多對多的匹配，建模成一個組合優化問題，以獲得全局最優。

通過將二者結合，即將組合優化中的司機和乘客的匹配價值，用強化學習得到的價值函數 (Value Function) 來表示，即得到了所述的演算法，其流程如下圖所示。

模型定義

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

智能體 (agent)：定義每個司機為一個智能體。雖然此定義會使問題變為一個多智能體學習 (multi-agent) 求解問題，但單司機作為智能體的方式可大大減少狀態和動作空間，使得求解變得可能；

狀態 (state)：狀態 s 定義了司機所處的周邊信息。為簡化起見，論文定義司機所處的時間和空間為其狀態，並將時空進行量化為 10 分鐘的時間段和固定大小的區域。這樣，一個完整的 episode（記為一天）由 144 個時間片組成，每個城市包含著數千至數萬的區域單位。

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

狀態轉移 (state transition) 與獎勵函數 (rewards)：完成訂單的動作會自動使司機發生時空狀態的轉移，其同時會帶來獎勵，我們定義獎勵 r 為訂單的金額。

在定義了 MDP 的基本元素之後，下一步即選定一個最優的策略，使其最大化累積期望收益。

匹配策略

在此 MDP 的定義下，平台派單的過程即針對每一次分單的輪次（2 秒），平台會取得每個待分配司機的狀態 s，並將所有待分配訂單設為司機可執行的動作之一。該問題的優化目標是 在確保用戶體驗的基礎上最大化所有司機的收益總和。論文將其建模為二分圖匹配問題，使用 KM((Kuhn-Munkres) 演算法進行求解。

在二分圖建圖的過程中，某司機和某訂單的邊權實際上表示了司機在狀態 s 下，執行完成訂單的動作 a 下的預期收益，即強化學習中的動作價值函數 (Action-State Value Function) Q(s,a)。該函數表示了司機完成某訂單後，可獲得的預期收益，其包含了兩部分：訂單的即時收益 r，以及司機完成訂單後新狀態下的預期收益期望。

價值函數

如何評估司機出現在某個特定時間/空間時的價值也成為一個核心問題。在強化學習中的價值函數表示了智能體 (Agent) 在某狀態下的預期累積收益的期望。而在滴滴這一場景中，司機處在某狀態下的價值函數，則對應了在常態狀態下司機出現在某時空位置下的預期流水收入。

通過將時間和空間進行量化，再基於滴滴平台上海量的歷史數據資源，滴滴使用動態規劃 (Dynamic Programming) 的方法求解出了每個時空狀態下司機的預期收益，即價值函數。價值函數實際上代表了滴滴出行平台上供需狀況的一種濃縮。下圖顯示了某城市晚高峰和平峰的價值函數示意。

價值函數和匹配策略相結合

將價值函數和組合優化的目標函數結合在一起，即形成了完整的派單方法。演算法流程包括：

離線部分

步驟 1.1 收集歷史數據中的訂單信息，表示為強化學習中的四元組形式；

步驟 1.2 使用動態規劃求解價值函數。將價值函數以查找表 (lookup table) 形式保存以供線上使用。

線上部分

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

步驟 2.2 計算每個司乘匹配對應的動作價值數 (State-Action Function)，並以此為權重建立二分圖;

步驟 2.3 將上述匹配權值作為權重嵌入 KM 演算法，充分考慮接駕距離、服務分等因素，求解最優匹配，進入最終派單環節。

迭代部分

步驟 3 迭代重複進行 1 和 2，即根據新積累的數據離線更新價值函數，和使用更新後的價值函數指導派單的過程。

線上使用

滴滴團隊進行了大量的離線實驗和在線 AB 測試，結果均顯示，這種基於強化學習和組合優化的派單演算法能在確保乘客出行體驗的同時明顯提升司機的收入。目前該演算法已成功部署在滴滴平台二十多個核心城市，承接廣大用戶的出行需求。

結論和下一步計劃

滴滴團隊指出，與傳統的「只考慮當下」的策略不同，這一全新的基於強化學習和組合優化的派單演算法能能考慮到每一次派單的決定會對未來的司機分布發生影響，面向長期收益。後續將在深度 Q 學習 (DQN) 演算法求解和不同城市間進行遷移學習等方面持續優化，並將持續拓展演算法在其他應用場景中的應用。

（論文地址：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）

請移步AI研習社社區下載四篇論文：

https://club.leiphone.com/page/resourceDetail/411

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！