文章轉自滴滴科技合作（ID: didioutreach），
原文鏈接：NeurIPS 2019論文解讀 | 北郵X滴滴：基於最小車隊的動態車輛調度
張文琦（北京郵電大學博士研究生）
李晶晶（北京郵電大學碩士研究生）
王強（北京郵電大學副教授，博導），研究方向：移動網絡、信息理論、機器學習和智能決策系統
石東海，滴滴惠普產品技術負責人、高級技術總監
眾所周知，交通供需存在時間和空間上的不匹配的現象，某一時刻城市內一部分地區車輛供過於求的同時，另一部分地區可能存在車輛空駛的狀況。隨著近年來全球定位系統（GPS）、無線通訊工具以及人工智能技術的發展，我們是否可以進行更好的規劃，在維持車隊規模一定的情況下，對這些空駛車輛進行有效指引以減少空閒率、提高司機收入並改善用戶體驗呢？滴滴出行惠普產品的石東海團隊以及北極郵電大學王強團隊對此合作探討，結合強化學習算法進行調度優化，仿真驗證顯示效果顯著。
由於交通供需之間的不匹配，大城市的車輛共享平臺效率有很大提升空間。隨著全球定位系統（GPS）和無線通信工具的發展，車輛共享平臺可以充分利用空閒車輛來緩解供需之間的差距。
針對如何對空駛車輛有效指引以減少空閒率，同時研究城市承運中不同車隊規模時的效率，滴滴出行普惠產品技術部負責人石東海團隊和北京郵電大學王強副教授合作探討，聯合提出了一種基於最小車隊的動態車輛調度方法，模擬實驗得到了AI Labs的環境支持。
首先，在已知車輛共享網絡情況下，採用二部圖匹配算法獲得所需的最小車輛數。然後，為了平衡實時交通中交通供需之間的失配，提出了深度強化學習算法DDQN（Dueling Deep Q-Network ），以有效地使用有限的車輛。DDQN能夠估算供需之間複雜的動態關係，因此可以根據DDQN的調度政策將可用車輛調度到需求量大的地方，從而緩解供需之間的差距。最後，我們設計了一個模擬器來訓練和測試決鬥的深度強化學習算法。仿真結果證明算法在訂單響應率和司機計費時長佔比方面有顯著改進，可以提升司機收入、改善用戶體驗。
1研究背景
在線乘車共享服務由於其便利性和靈活性而受到了許多研究者的追捧。隨著全球定位系統（GPS）和無線通信工具的發展，車輛共享平臺能夠充分利用道路上的車輛，這不僅能提高交通資源的利用率，還能夠有效緩解交通擁堵和交通供需之間的差距。因此如何最好的規劃和管理共享平臺中的車輛就變得尤為重要。在已知車輛共享網絡的情況下，採用二部圖匹配算法最小化所需車輛數，並提出DDQN算法來將可用車輛分配到實時交通需求較大的地點已達到緩解供需之間差距的目的。
2問題挑戰
在當前的研究背景下，本論文提出了一種深度強化學習算法DDQN。在算法設計的過程中，我們面臨的挑戰主要是如何有效地分配有限的車輛，以滿足更多需求。由於在車隊管理過程中，調度政策的變化將很大程度上影響到未來的供需情況，我們需要保證調度的有效性。
3解決方案
本論文基於滴滴平臺中真實的數據，包括道路信息、時間估計以及訂單數據，設計基於 DDQN的強化學習算法對車輛進行動態的調度策略。
本論文主要解決兩個方面的問題，1）最小車隊問題，在訂單信息已知的情況下最大程度地減少所需車輛的數量；2）可用車輛調度問題，根據深度強化學習的策略，將可用車輛派往需求量大的地點來最大程度地提高響應率。
1最小車隊問題
根據訂單數據，構建一個車輛共享網絡，由於時間的方向性，它是一個有向無環圖。圖中的每個節點代表一個行程，圖中的邊表示兩行程之間的可連接。由於是個有向無環圖，我們可以將圖分解為一個二部圖，此時最小車隊問題就轉化為二部圖最大匹配問題。通過二部圖匹配算法就可以得到車輛共享網絡的最小車隊數量，圖1展示了執行算法後得到的最小車隊數和真實情況的對比，可以看到所需的車隊數量有了明顯的減少。
圖1 每小時完成所有訂單所需的最少車輛數量
圖2 乘客忍耐時間與所需最小車輛的關係
2可用車輛調度問題
在一個調度的時間線裡，首先根據歷史信息生成訂單，其次更新可調度車輛分佈，再次根據決策策略進行空閒司機調度，最後進行派單。調度的時間線流程如圖3所示。
圖3 調度時間線
我們使用DDQN模型來對共享網絡中的可用車輛進行合理的調度和管理。在DDQN模型中， DDQN由狀態、動作、獎勵和狀態-動作值（Q值）組成，空閒駕駛員（可用車輛）作為代理人。DDQN的目標是從初始狀態開始獲得最大化長期累積報酬的最優策略。在每次調度的過程中，每個空閒駕駛員都從狀態空間觀察一個狀態，然後根據策略，每個空閒駕駛員都從動作空間選擇一個動作執行。具體動態過程如圖4所示。在DDQN中，我們採用Dueling結構對各個狀態進行動作選擇，這樣可以提高算法的穩定性。
圖4 調度/管理可用車輛的動態過程
4實驗與結果
在該實驗中，本論文的數據集來源於滴滴出行的脫敏數據，可用車輛調度的實驗數據包括北京核心區連續三週的車輛和訂單數據。訂單數據集包含上/落客時間和上/落客位置（經緯度）。車輛數據包含每幾秒鐘更新的位置（經緯度）和狀態（在線和離線）信息。通過對比模擬器方法、隨機方法和Q-Learning的方法，證明了我們提出的方法在訂單響應率和司機計費持續時間佔空比方面有顯著改進，如表1所示。
表1 模型的實驗結果對比
論文核心貢獻者
張文琦
北京郵電大學博士研究生
王強
北京郵電大學副教授/博導
研究方向包括移動網絡、信息理論、機器學習和智能決策系統
李晶晶
北京郵電大學碩士研究生
石東海
滴滴普惠產品技術負責人、高級技術總監
閱讀更多 運籌OR帷幄 的文章
