0
| 本文作者： 奕欣 | 2018-08-23 16:56 | 專題：KDD 2018 |
國際數據挖掘領域的頂級會議 KDD 2018 在倫敦舉行，今年 KDD 吸引了全球范圍內共 1480 篇論文投遞，共收錄 293 篇，錄取率不足 20%。其中滴滴共有四篇論文入選 KDD 2018，涵蓋 ETA 預測 (預估到達時間) 、智能派單、大規(guī)模車流管理等多個研究領域。
四篇論文分別是（文末附論文打包下載地址）
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) 問題，結合了強化學習和組合優(yōu)化，能在即時完成派單決策的條件下，基于對全天供需、出行行為的預測和歸納，達到優(yōu)化一天之內司機整體效率的效果，能在確保乘客出行體驗的同時明顯提升司機的收入。
這一事件在雷鋒網學術頻道 AI 科技評論旗下數據庫項目「AI 影響因子」中有相應加分。
移動出行的本質是在乘客和司機之間建立連接。在滴滴，平臺日訂單達 3000 萬，高峰期每分鐘接收超過 6 萬乘車需求，如何設計一個更高效的匹配算法來進行司機和乘客的撮合也成為非常核心的問題。
當下滴滴的專車、快車等業(yè)務線已經在普遍使用智能派單模式，即從全局視角出發(fā)，由算法綜合考慮接駕距離、服務分、擁堵情況等因素，自動將訂單匹配給最合適的司機接單。論文所述的算法也是在這一派單模式下的改進。
然而實際上，出行場景下的司乘匹配非常復雜。一方面，高峰期出行平臺每分鐘會接到大量出行需求，一方面車輛會在路上不停地移動，可能幾秒后這個司機就通過了一個路口，或是行駛上了高速路；不僅如此，每一次派單的決定也都在影響未來的司機分布。
這些都對算法提出更高的要求: 不僅需要足夠高效，能快速地對司機和乘客進行動態(tài)、實時的匹配，秒級做出決策，同時還要能基于未來情況的預測，考慮匹配算法的長期收益。此外還要在考慮司機收入的同時保障用戶體驗，全局優(yōu)化總體交通運輸效率。
為了解決上述問題，滴滴技術團隊創(chuàng)新性地提出了一個融合強化學習和組合優(yōu)化的框架。算法的主要思路如下：
1) 平臺下發(fā)派單決策需要在秒級做出，同時每次決策的優(yōu)化目標均為提升長期收益。由于該問題自然形成了序列決策 (Sequential Decision Making) 的定義，使用馬爾可夫決策過程 (MDP) 進行建模，并用強化學習求解;
2) 針對司乘間多對多的匹配，建模成一個組合優(yōu)化問題，以獲得全局最優(yōu)。
通過將二者結合，即將組合優(yōu)化中的司機和乘客的匹配價值，用強化學習得到的價值函數 (Value Function) 來表示，即得到了所述的算法，其流程如下圖所示。
這一定義的馬爾可夫決策過程由以下模塊組成：
智能體 (agent)：定義每個司機為一個智能體。雖然此定義會使問題變?yōu)橐粋€多智能體學習 (multi-agent) 求解問題，但單司機作為智能體的方式可大大減少狀態(tài)和動作空間，使得求解變得可能；
狀態(tài) (state)：狀態(tài) s 定義了司機所處的周邊信息。為簡化起見，論文定義司機所處的時間和空間為其狀態(tài)，并將時空進行量化為 10 分鐘的時間段和固定大小的區(qū)域。這樣，一個完整的 episode（記為一天）由 144 個時間片組成，每個城市包含著數千至數萬的區(qū)域單位。
動作 (action)：動作 a 定義了司機的完成訂單或空閑操作。對完成訂單而言，司機會經過前往接乘客、等待乘客和送乘客到目的地等過程。
狀態(tài)轉移 (state transition) 與獎勵函數 (rewards)：完成訂單的動作會自動使司機發(fā)生時空狀態(tài)的轉移，其同時會帶來獎勵，我們定義獎勵 r 為訂單的金額。
在定義了 MDP 的基本元素之后，下一步即選定一個最優(yōu)的策略，使其最大化累積期望收益。
在此 MDP 的定義下，平臺派單的過程即針對每一次分單的輪次（2 秒），平臺會取得每個待分配司機的狀態(tài) s，并將所有待分配訂單設為司機可執(zhí)行的動作之一。該問題的優(yōu)化目標是 在確保用戶體驗的基礎上最大化所有司機的收益總和。論文將其建模為二分圖匹配問題，使用 KM((Kuhn-Munkres) 算法進行求解。
在二分圖建圖的過程中，某司機和某訂單的邊權實際上表示了司機在狀態(tài) s 下，執(zhí)行完成訂單的動作 a 下的預期收益，即強化學習中的動作價值函數 (Action-State Value Function) Q(s,a)。該函數表示了司機完成某訂單后，可獲得的預期收益，其包含了兩部分：訂單的即時收益 r，以及司機完成訂單后新狀態(tài)下的預期收益期望
。
如何評估司機出現在某個特定時間/空間時的價值也成為一個核心問題。在強化學習中的價值函數表示了智能體 (Agent) 在某狀態(tài)下的預期累積收益的期望。而在滴滴這一場景中，司機處在某狀態(tài)下的價值函數，則對應了在常態(tài)狀態(tài)下司機出現在某時空位置下的預期流水收入。
通過將時間和空間進行量化，再基于滴滴平臺上海量的歷史數據資源，滴滴使用動態(tài)規(guī)劃 (Dynamic Programming) 的方法求解出了每個時空狀態(tài)下司機的預期收益，即價值函數。價值函數實際上代表了滴滴出行平臺上供需狀況的一種濃縮。下圖顯示了某城市晚高峰和平峰的價值函數示意。
將價值函數和組合優(yōu)化的目標函數結合在一起，即形成了完整的派單方法。算法流程包括：
離線部分
步驟 1.1 收集歷史數據中的訂單信息，表示為強化學習中的四元組形式；
步驟 1.2 使用動態(tài)規(guī)劃求解價值函數。將價值函數以查找表 (lookup table) 形式保存以供線上使用。
線上部分
步驟 2.1 收集待分配的司機和訂單列表;
步驟 2.2 計算每個司乘匹配對應的動作價值數 (State-Action Function)，并以此為權重建立二分圖;
步驟 2.3 將上述匹配權值作為權重嵌入 KM 算法，充分考慮接駕距離、服務分等因素，求解最優(yōu)匹配，進入最終派單環(huán)節(jié)。
迭代部分
步驟 3 迭代重復進行 1 和 2，即根據新積累的數據離線更新價值函數，和使用更新后的價值函數指導派單的過程。
滴滴團隊進行了大量的離線實驗和在線 AB 測試，結果均顯示，這種基于強化學習和組合優(yōu)化的派單算法能在確保乘客出行體驗的同時明顯提升司機的收入。目前該算法已成功部署在滴滴平臺二十多個核心城市，承接廣大用戶的出行需求。
滴滴團隊指出，與傳統的「只考慮當下」的策略不同，這一全新的基于強化學習和組合優(yōu)化的派單算法能能考慮到每一次派單的決定會對未來的司機分布發(fā)生影響，面向長期收益。后續(xù)將在深度 Q 學習 (DQN) 算法求解和不同城市間進行遷移學習等方面持續(xù)優(yōu)化，并將持續(xù)拓展算法在其他應用場景中的應用。
（論文地址：Large?Scale Order Dispatch in On?Demand Ride?Hailing Platforms: A Learning and Planning Approach
或點擊本鏈接移步AI研習社社區(qū)下載四篇論文。
雷峰網原創(chuàng)文章，未經授權禁止轉載。詳情見轉載須知。
專題
