摘 要：為了減少乘客在高峰期打車難和出租車空載的情況，面對不確定的出行需求，一個無模型深度強化學習框架被提出來解決無人駕駛出租車調度問題。該框架使用馬爾可夫決策模型來建模，綜合考慮了運營商收益與顧客等待成本，使用了基于策略的深度強化學習算法——雙延遲深度確定性策略梯度算法(Twin Delayed Deep Deterministic PolicyGradient TD3)對無人駕駛出租車進行調度，達到合理分配空閑車輛資源的目的。本文基于紐約市的真實出租車出行數據來搭建環境模擬器，通過在訓練過程中加入不確定需求來增強算法魯棒性。實驗結果表明，該方法在求解不確定需求下的無人駕駛出租車調度問題的有效性。

　　關鍵詞：強化學習;無人駕駛出租車;車輛調度;策略梯度

　　引言

　　傳統出租車在高峰時期總會出現乘客“打車難”與車輛空載這兩種難以平衡的問題1]。而且由于運營平臺、司機、乘客的博弈，全局最優的調度策略往往不能被貫徹執行。隨著物聯網、通信技術、人工智能技術等發展，自動駕駛技術在不斷成熟 。目前我國不少一線城市已經開展各類無人駕駛汽車的前期測試與探索活動，相信在不久的未來，共享出租車公司如哈啰、百度等很可能搭建自動駕駛出租車隊用于搭載乘客，以緩解當下出租車平臺在高峰期所面臨的各類問題。

　　面對城市交通中乘客出行需求的不確定性，如何有效利用無人駕駛出租車可集中調度的特點來調度空閑的無人駕駛出租車，從而滿足未來的出行需求，對提高無人駕駛出租車服務水平有著重要意義。車輛調度問題是車輛路徑規劃問題的一個子問題 ，針對不同應用場景，國內外學者一直嘗試運用現代運籌優化理論獲取對應場景下的全局最優解 。

　　目前從服務提供者角度來說，大多數運營商采用定價激勵的策略進行車輛調度 。例如采用顧客加價、司機調度獎勵、峰時定價等策略來引導司機去需求量高的地方 。但也有學者對此類實時動態定價的有效性提出質疑，Kooti等 根據優步收集的真實數據分析出，峰時定價策略并沒有給車輛調度帶來較大的積極影響。研究者研究了大量基于模型的車輛調度算法。

　　Zhang等 根據排隊理論搭建按需系統(Mobility n Demand MOD)來調度出租車，他們通過求解線性規劃模型找出一種最優的調度策略，并應用到紐約的出租車案例中。實驗證明該算法在滿足需求的情況下有效減少了出租車隊規模。B. Kim等[10]為了最小化出租車調度成本，將多目標的出租車調度問題轉化為一個網絡流問題，通過最小費用最大流算法求解。在韓國首爾地區的真實出租車數據進行模擬研究，證明了算法的有效性。Boyacı等人[1 提出一種允許決策者權衡運營商和用戶利益的多目標混合整數規劃模型來解決共享汽車調度問題。

　　Ma等[1 則研究了一種無人駕駛出租車系統，該系統通過提前獲取乘客需求來搭建系統的時空網絡。通過線性規劃讓系統在最低成本和最小計算量上做出最優的調度決策。通過案例表明，該系統可以有效降低汽車擁有率。上述方法都是基于嚴格數學模型的，當涉及變量過多或者維度過高的時候，這些數學模型不能很好地適應，且面對大規模問題，求解效率不佳。啟發式優化算法能夠全面有效搜尋最優解，而且面對大規模問題能夠保證效率，因此受到很多研究者青睞。

　　謝榕等[13]用人工魚群算法對出租車進行基于全局角度的智能調度，從而實現對出租車的合理調度。何勝學等[14]將蟻群算法與遺傳算法結合，來求解出租車調度策略，實驗證明了算法的有效性。上述方法都是建立在乘客的需求是靜態的假設下建模的，然而在現實場景中，若是僅根據當前的乘客需求進行調度則不能很好地應對未來可能出現的供需不平衡的情況。在本文中我們提出了基于不確定需求的無模型強化學習方法來解決無人駕駛出租車調度問題。

　　通過在強化學習訓練中引入不確定需求，從而使訓練出來的模型能更好適應城市交通中乘客的不確定需求。在強化學習的無模型算法中，其學習代理并不依賴于模型的任何先驗信息，無需用參數估計模型，而是直接與訓練環境交互來更新控制策略。在實際使用中，直接調用訓練好的模型就可以得到調度策略。因此強化學習算法即使面對大規模問題也能高效地做出性能穩定的調度方案[15]。近年來用強化學習算法解決調度問題的研究有很多[16]，比如陳勇 、張景玲 、黎聲益 、Chao Mao20 等。

　　其中Chao Mao與我們研究最為接近，該論文將車輛調度算法與強化學習結合，運用深度強化學習方法actor cr tic21 方法來優化車輛調度，實驗證明該算法收斂于理論上界。然而actor cr tic算法已被證實會過高估計動作值，即對動作價值函數的估計會有誤差，這種誤差累積的偏差會導致任意的壞狀態被估計為高值，從而導致次優的策略更新以致于策略網絡無法收斂。由于該問題的狀態空間是連續，本文采用了一種基于狀態空間連續的算法——雙延遲深度確定性策略梯度算法(Twin Delayed Deep Deterministic policy gradient algorithm，TD ) 22 ，簡稱為TD3算法。該算法可以有效解決高估動作值的問題，從而得到最優的調度策略。為了更有效應對城市交通中乘客的不確定出行需求，我們將不確定需求與強化學習結合，在不確定需求環境下訓練模型。

　　通過神經網絡捕捉到需求的隨機性，模型能更好地應對需求變化的情況。最后，我們使用紐約市真實的出租車數據來模擬乘客需求，并將數據集劃分為訓練集和測試集來驗證算法合理性。實驗證明，在需求不確定情況下訓練的模型在驗證集和需求突變的情況下均表現較好，更具魯棒性。

　　2 無人駕駛出租車調度問題的強化學習建模

　　為了避免維度詛咒，我們設置狀態向量和動作向量都為連續變量。由于狀態空間和動作空間都是連續的，我們采用了更適用于連續動作空間的方法——雙延遲深度確定性策略梯度算法。

　　3 無人駕駛出租車調度問題算法介紹

　　3.1 用于無人駕駛出租車調度的雙延遲深度確定性策略梯度算法雙延遲深度確定性策略梯度方法，簡稱為TD 算法。TD 算法是由深度確定性策略梯度算法(Deep Deterministic Policy Gradient DDPG)[23]進一步優化而來。DDPG算法在處理連續動作空間的問題上能有很好的表現效果，但是它通常對于超參數十分敏感，且會在訓練的時候會出現高估狀態動作價值的問題。而TD 算法引入了兩個目標動作價值網絡來緩解高估的問題。

　　3.2 用于驗證 TD3 算法的混合整數規劃模型描述

　　在這個章節中，我們假設乘客需求和系統動力學的信息都是已知且確定的，以此為前提搭建混合整數規劃模型求得無人駕駛出租車調度問題的獎勵值理論上界。我們把整個調度問題視為求解靜態的混合整數規劃問題，該混合整數規劃模型目標設置為成本最低來求解最優的調度策略。在后續的實驗中，我們將混合整數規劃的求得的理論上界與強化學習的結果進行比較，進而分析TD3網絡訓練過程的收斂效果。

　　4 量化實驗

　　4.1 實驗設置在模型訓練之前，我們搭建了一個環境模擬器來模擬無人駕駛出租車的運營及調度過程。其中用戶出行需求信息提取于真實的紐約市曼哈頓區域黃色出租車訂單數據。我們假設所有的出租車都是自動駕駛車輛，可以集中調度。因此，我們的目標是利用強化學習TD 算法和這個模擬器，來找出最優的無人駕駛出租車調度策略。我們首先從NYC TLC(Taxi & Limousine Commission)獲得了關于紐約市曼哈頓的地理坐標。該地圖將紐約市的曼哈頓區分為 個區域。

　　然后我們從NYC TLC 中獲得了 016年月黃色出租車在曼哈頓市的訂單數據集。該數據集記錄著乘客上車和下車的地點和時間、行駛距離、費用、費率類型、支付類型和司機報告的乘客數量等信息。為了減少模型驗證的計算量同時不失其真實性，我們做了三種簡化：首先我們將無人駕駛出租車行駛區域劃分為 個服務區，也就是說我們把區域聚集成更大的區域，從而形成一個小的網絡。

　　由于高峰時間段，供應與需求有著較大的差距。我們選取早高峰的 點到 點的數據，時間間隔設定為 分鐘。第三，我們假設每天每個區域的初始車輛分布是一樣的。這三個假設有助于我們減少計算時間和計算量來驗證我們的方法。如果有足夠的計算能力，我們的方法也可以推廣到任何規模的網絡和時間間隔。為了不失合理性，在仿真器中，結合當地的環境及相關政策，我們手動設置了其他參數，如旅行時間、等待成本、調度成本等，模擬無人駕駛出租車運營場景。

　　4.2 乘客需求確定

　　仿真環境下的TD3架構部署與表現本文的策略網絡是由三層線性網絡(大小為 56)和三層激活層(前兩層為relu激活函數，最后一層為tanh激活函數)組成。動作價值網絡由三層線性網絡(大小為 56)和兩層激活層(都為relu激活函數)組成。其次，為了與混合整數規劃算法做對比，我們設定每天模擬器的乘客需求都是確定的，也就說每天每個時刻每個區域到另一個區域的需求都是確定的。因此在此種情況下，混合整數規劃的目標函數值即為獎勵函數值的理論上界。

　　強化學習的訓練過程是令獎勵越大越好，此處設置的獎勵值為成本的負數，也就是說訓練過程中成本會越來越小。在實驗中，我們將TD 算法與強化學習的另一種算法深度確定性策略梯度算法(Deep Deterministic Policy Gradient)，簡稱為DDPG算法，進行比較。實驗總共訓練了300萬次，每 000次進行驗證，結果如圖 所示。TD 算法實驗最終收斂在  7.051 10 ，DDPG算法最終收斂在  7.403 10 。利用Gurobi優化器求得混合整數規劃的最優解為  6.905 10 。

　　通過對比，我們得知TD3算法與DDPG算法都收斂于整數規劃理論最優值，但TD3算法比DDPG算法波動性更小、收斂更快且更接近于混合整數規劃求得的理論上界。這是因為TD 算法在DDPG算法基礎上有三個改進，首先采用了兩個動作價值網絡更新學習的方式，可以有效抑制動作價值網絡高估的問題。第二采用了策略網絡延遲更新的方法，讓策略網絡訓練更加穩定。第三采用了目標網絡平滑化的方法，通過計算目標動作價值網絡值時動作添加噪聲，從而讓目標動作價值網絡更新更準確和魯棒。

　　4.3 乘客需求不確定

　　仿真環境下的TD3架構部署與表現為了進一步測試TD3算法的實驗表現，我們進一步允許乘客需求的隨機性。用一個月的每個時刻每個區域的平均值作為乘客需求確定的情況，設為D0，也就是3.2中乘客需求確定下的仿真環境設置。接下來進一步給需求添加不確定性，把需求變為高斯分布，均值為一個月每個區域的需求均值，標準差設為 的均值和 均值兩種情況，表示為D25和50的情況。通過這樣的設置，我們得到三種需求環境分別是10 、 25、 50。

　　通過實驗我們可以看出TD 算法在D25、D50兩種不確定需求的情況下均可達到收斂。盡管需求隨機性為 50的時候，獎勵值波動比較大，但仍然在150萬輪之后趨于平穩。對比在D0、 25、D50三種環境的訓練曲線，我們可以發現顧客需求不確定性越大，獎勵值波動越大。這是符合規律的，因為顧客需求是公式 3)獎勵值的其中一個因變量。當顧客需求不確定性越大時，獎勵值波動也就越大。

　　但更關鍵的是，我們可以看到在三種情況下訓練的算法都可以達到收斂。因此可以得出結論：TD 算法可以有效應對需求不確定環境下的無人駕駛出租車調度。圖 給出了不同需求環境下訓練出來的最優模型(即通過上述不同仿真環境訓練得到的D0 TD3、D25TD3、D50 TD3模型)分別在不同需求環境下的測試獎勵值。

　　結束語

　　在本文中，我們提出了一種用深度強化學習方法解決自動駕駛出租車調度問題。該方法基于雙延遲深度確定性策略梯度算法(TD3)框架，該框架由兩個深度神經網絡搭建。在實驗中，我們首先對紐約市曼哈頓區域黃色出租車數據進行整理分析，然后我們假設系統動力學都是已知且確定的，所以我們可以通過混合整數規劃得到了獎勵(總成本的負數)的理論上界。

　　我們將雙延遲深度確定性策略梯度算法應用在紐約市曼哈頓區域的黃色出租車的交通網絡中。通過實驗對比，我們在測試集上證實了TD3算法在需求不確定的情況下訓練出來的模型的收斂性及有效性。同時我們通過不確定交通需求和需求突變的情況來測試算法的魯棒性，實驗證明TD3算法能夠有效應對需求不確定的情況。本文還留下了很多有意思的值得拓展的研究。

　　首先，我們的實驗是建立在一個簡化的交通網絡上進行的。由于不斷增長的動作空間和狀態空間，進行大規模的集中策略調度一直是一個挑戰。也許可以嘗試一下采用多智能體強化學習的方法，如Boyali 將每個司機作為一個智能體，多個司機協同調度，從而可以有效提高調度系統運行的效率，Seow 采用多智能體模型，分布式調度出租車。其次我們的實驗中只考慮了單一模式的車輛，而在未來運營商可能由人類駕駛的車輛和無人駕駛出租車結合的車隊組成 ，算法可以進一步結合兩者的特點。除此之外，我們還可以進一步考慮拼車對調度策略的影響[27]。

　　目前我們的研究中是沒有考慮拼車系統的，如果能進一步考慮拼車系統的話，運營商就可以用更少的車輛滿足更多的需求，進一步提高效率，節約能源，緩解交通擁堵。最后，我們目前只結合顧客的需求與現有的車輛進行調度，但我們可以參考更多的信息比如交通情況等來參與決策，從而能利用更多的信息來進行優化調度。

　　參考文獻：

　　[1] Maciejewski M, Bischoff J. Congestion effects of autonomous taxi fleets[J]. Transport, 2018,33(4): 971 980.

　　[2] Sakhare K V, Tewari T, Vyas V. Review of vehicle detection systems in advanced driver assistantsystems[J]. Archives of Computational Methods in Engineering, 2020, 27(2): 591 610

　　.[3] Kuutti S, Bowden R, Jin Y, et al. A survey of deep learning applications to autonomous vehiclecontrol[J]. IEEE Transactions on Intelligent Transportation Systems, 2020, 22(2): 712 733.

　　[4] Javanshour F, Dia H, Duncan G. Exploring the performance of autonomous mobility on demandsystems under demand uncertainty[J]. Transportmetrica A: transport science, 2019, 15(2): 698721.

　　[5] CHEN Shengkai,Fang Shuiliang,Tang Renzhogn. Demand forecasting based optimization ofservice configuration for cloud manufacturing[J]. Computer Integrated Manufacturing Systems,2020,26(11):2944 2954(in Chinese)

　　陳晟愷 方水良 唐任仲 基于需求預測的云制造服務租賃配置優化 J].計算機集成制造系統,2020,26(11):2944 2954.

　　作者：周曉婷1，吳祿彬1，章 宇2，姜善成1+