時(shí)間:2022年04月20日 分類:推薦論文 次數(shù):
摘 要:為了減少乘客在高峰期打車難和出租車空載的情況,面對(duì)不確定的出行需求,一個(gè)無(wú)模型深度強(qiáng)化學(xué)習(xí)框架被提出來(lái)解決無(wú)人駕駛出租車調(diào)度問(wèn)題。該框架使用馬爾可夫決策模型來(lái)建模,綜合考慮了運(yùn)營(yíng)商收益與顧客等待成本,使用了基于策略的深度強(qiáng)化學(xué)習(xí)算法——雙延遲深度確定性策略梯度算法(Twin Delayed Deep Deterministic PolicyGradient TD3)對(duì)無(wú)人駕駛出租車進(jìn)行調(diào)度,達(dá)到合理分配空閑車輛資源的目的。本文基于紐約市的真實(shí)出租車出行數(shù)據(jù)來(lái)搭建環(huán)境模擬器,通過(guò)在訓(xùn)練過(guò)程中加入不確定需求來(lái)增強(qiáng)算法魯棒性。實(shí)驗(yàn)結(jié)果表明,該方法在求解不確定需求下的無(wú)人駕駛出租車調(diào)度問(wèn)題的有效性。
關(guān)鍵詞:強(qiáng)化學(xué)習(xí);無(wú)人駕駛出租車;車輛調(diào)度;策略梯度
引言
傳統(tǒng)出租車在高峰時(shí)期總會(huì)出現(xiàn)乘客“打車難”與車輛空載這兩種難以平衡的問(wèn)題1]。而且由于運(yùn)營(yíng)平臺(tái)、司機(jī)、乘客的博弈,全局最優(yōu)的調(diào)度策略往往不能被貫徹執(zhí)行。隨著物聯(lián)網(wǎng)、通信技術(shù)、人工智能技術(shù)等發(fā)展,自動(dòng)駕駛技術(shù)在不斷成熟 。目前我國(guó)不少一線城市已經(jīng)開展各類無(wú)人駕駛汽車的前期測(cè)試與探索活動(dòng),相信在不久的未來(lái),共享出租車公司如哈啰、百度等很可能搭建自動(dòng)駕駛出租車隊(duì)用于搭載乘客,以緩解當(dāng)下出租車平臺(tái)在高峰期所面臨的各類問(wèn)題。
面對(duì)城市交通中乘客出行需求的不確定性,如何有效利用無(wú)人駕駛出租車可集中調(diào)度的特點(diǎn)來(lái)調(diào)度空閑的無(wú)人駕駛出租車,從而滿足未來(lái)的出行需求,對(duì)提高無(wú)人駕駛出租車服務(wù)水平有著重要意義。車輛調(diào)度問(wèn)題是車輛路徑規(guī)劃問(wèn)題的一個(gè)子問(wèn)題 ,針對(duì)不同應(yīng)用場(chǎng)景,國(guó)內(nèi)外學(xué)者一直嘗試運(yùn)用現(xiàn)代運(yùn)籌優(yōu)化理論獲取對(duì)應(yīng)場(chǎng)景下的全局最優(yōu)解 。
目前從服務(wù)提供者角度來(lái)說(shuō),大多數(shù)運(yùn)營(yíng)商采用定價(jià)激勵(lì)的策略進(jìn)行車輛調(diào)度 。例如采用顧客加價(jià)、司機(jī)調(diào)度獎(jiǎng)勵(lì)、峰時(shí)定價(jià)等策略來(lái)引導(dǎo)司機(jī)去需求量高的地方 。但也有學(xué)者對(duì)此類實(shí)時(shí)動(dòng)態(tài)定價(jià)的有效性提出質(zhì)疑,Kooti等 根據(jù)優(yōu)步收集的真實(shí)數(shù)據(jù)分析出,峰時(shí)定價(jià)策略并沒(méi)有給車輛調(diào)度帶來(lái)較大的積極影響。研究者研究了大量基于模型的車輛調(diào)度算法。
Zhang等 根據(jù)排隊(duì)理論搭建按需系統(tǒng)(Mobility n Demand MOD)來(lái)調(diào)度出租車,他們通過(guò)求解線性規(guī)劃模型找出一種最優(yōu)的調(diào)度策略,并應(yīng)用到紐約的出租車案例中。實(shí)驗(yàn)證明該算法在滿足需求的情況下有效減少了出租車隊(duì)規(guī)模。B. Kim等[10]為了最小化出租車調(diào)度成本,將多目標(biāo)的出租車調(diào)度問(wèn)題轉(zhuǎn)化為一個(gè)網(wǎng)絡(luò)流問(wèn)題,通過(guò)最小費(fèi)用最大流算法求解。在韓國(guó)首爾地區(qū)的真實(shí)出租車數(shù)據(jù)進(jìn)行模擬研究,證明了算法的有效性。Boyacı等人[1 提出一種允許決策者權(quán)衡運(yùn)營(yíng)商和用戶利益的多目標(biāo)混合整數(shù)規(guī)劃模型來(lái)解決共享汽車調(diào)度問(wèn)題。
Ma等[1 則研究了一種無(wú)人駕駛出租車系統(tǒng),該系統(tǒng)通過(guò)提前獲取乘客需求來(lái)搭建系統(tǒng)的時(shí)空網(wǎng)絡(luò)。通過(guò)線性規(guī)劃讓系統(tǒng)在最低成本和最小計(jì)算量上做出最優(yōu)的調(diào)度決策。通過(guò)案例表明,該系統(tǒng)可以有效降低汽車擁有率。上述方法都是基于嚴(yán)格數(shù)學(xué)模型的,當(dāng)涉及變量過(guò)多或者維度過(guò)高的時(shí)候,這些數(shù)學(xué)模型不能很好地適應(yīng),且面對(duì)大規(guī)模問(wèn)題,求解效率不佳。啟發(fā)式優(yōu)化算法能夠全面有效搜尋最優(yōu)解,而且面對(duì)大規(guī)模問(wèn)題能夠保證效率,因此受到很多研究者青睞。
謝榕等[13]用人工魚群算法對(duì)出租車進(jìn)行基于全局角度的智能調(diào)度,從而實(shí)現(xiàn)對(duì)出租車的合理調(diào)度。何勝學(xué)等[14]將蟻群算法與遺傳算法結(jié)合,來(lái)求解出租車調(diào)度策略,實(shí)驗(yàn)證明了算法的有效性。上述方法都是建立在乘客的需求是靜態(tài)的假設(shè)下建模的,然而在現(xiàn)實(shí)場(chǎng)景中,若是僅根據(jù)當(dāng)前的乘客需求進(jìn)行調(diào)度則不能很好地應(yīng)對(duì)未來(lái)可能出現(xiàn)的供需不平衡的情況。在本文中我們提出了基于不確定需求的無(wú)模型強(qiáng)化學(xué)習(xí)方法來(lái)解決無(wú)人駕駛出租車調(diào)度問(wèn)題。
通過(guò)在強(qiáng)化學(xué)習(xí)訓(xùn)練中引入不確定需求,從而使訓(xùn)練出來(lái)的模型能更好適應(yīng)城市交通中乘客的不確定需求。在強(qiáng)化學(xué)習(xí)的無(wú)模型算法中,其學(xué)習(xí)代理并不依賴于模型的任何先驗(yàn)信息,無(wú)需用參數(shù)估計(jì)模型,而是直接與訓(xùn)練環(huán)境交互來(lái)更新控制策略。在實(shí)際使用中,直接調(diào)用訓(xùn)練好的模型就可以得到調(diào)度策略。因此強(qiáng)化學(xué)習(xí)算法即使面對(duì)大規(guī)模問(wèn)題也能高效地做出性能穩(wěn)定的調(diào)度方案[15]。近年來(lái)用強(qiáng)化學(xué)習(xí)算法解決調(diào)度問(wèn)題的研究有很多[16],比如陳勇 、張景玲 、黎聲益 、Chao Mao20 等。
其中Chao Mao與我們研究最為接近,該論文將車輛調(diào)度算法與強(qiáng)化學(xué)習(xí)結(jié)合,運(yùn)用深度強(qiáng)化學(xué)習(xí)方法actor cr tic21 方法來(lái)優(yōu)化車輛調(diào)度,實(shí)驗(yàn)證明該算法收斂于理論上界。然而actor cr tic算法已被證實(shí)會(huì)過(guò)高估計(jì)動(dòng)作值,即對(duì)動(dòng)作價(jià)值函數(shù)的估計(jì)會(huì)有誤差,這種誤差累積的偏差會(huì)導(dǎo)致任意的壞狀態(tài)被估計(jì)為高值,從而導(dǎo)致次優(yōu)的策略更新以致于策略網(wǎng)絡(luò)無(wú)法收斂。由于該問(wèn)題的狀態(tài)空間是連續(xù),本文采用了一種基于狀態(tài)空間連續(xù)的算法——雙延遲深度確定性策略梯度算法(Twin Delayed Deep Deterministic policy gradient algorithm,TD ) 22 ,簡(jiǎn)稱為TD3算法。該算法可以有效解決高估動(dòng)作值的問(wèn)題,從而得到最優(yōu)的調(diào)度策略。為了更有效應(yīng)對(duì)城市交通中乘客的不確定出行需求,我們將不確定需求與強(qiáng)化學(xué)習(xí)結(jié)合,在不確定需求環(huán)境下訓(xùn)練模型。
通過(guò)神經(jīng)網(wǎng)絡(luò)捕捉到需求的隨機(jī)性,模型能更好地應(yīng)對(duì)需求變化的情況。最后,我們使用紐約市真實(shí)的出租車數(shù)據(jù)來(lái)模擬乘客需求,并將數(shù)據(jù)集劃分為訓(xùn)練集和測(cè)試集來(lái)驗(yàn)證算法合理性。實(shí)驗(yàn)證明,在需求不確定情況下訓(xùn)練的模型在驗(yàn)證集和需求突變的情況下均表現(xiàn)較好,更具魯棒性。
2 無(wú)人駕駛出租車調(diào)度問(wèn)題的強(qiáng)化學(xué)習(xí)建模
為了避免維度詛咒,我們?cè)O(shè)置狀態(tài)向量和動(dòng)作向量都為連續(xù)變量。由于狀態(tài)空間和動(dòng)作空間都是連續(xù)的,我們采用了更適用于連續(xù)動(dòng)作空間的方法——雙延遲深度確定性策略梯度算法。
3 無(wú)人駕駛出租車調(diào)度問(wèn)題算法介紹
3.1 用于無(wú)人駕駛出租車調(diào)度的雙延遲深度確定性策略梯度算法雙延遲深度確定性策略梯度方法,簡(jiǎn)稱為TD 算法。TD 算法是由深度確定性策略梯度算法(Deep Deterministic Policy Gradient DDPG)[23]進(jìn)一步優(yōu)化而來(lái)。DDPG算法在處理連續(xù)動(dòng)作空間的問(wèn)題上能有很好的表現(xiàn)效果,但是它通常對(duì)于超參數(shù)十分敏感,且會(huì)在訓(xùn)練的時(shí)候會(huì)出現(xiàn)高估狀態(tài)動(dòng)作價(jià)值的問(wèn)題。而TD 算法引入了兩個(gè)目標(biāo)動(dòng)作價(jià)值網(wǎng)絡(luò)來(lái)緩解高估的問(wèn)題。
3.2 用于驗(yàn)證 TD3 算法的混合整數(shù)規(guī)劃模型描述
在這個(gè)章節(jié)中,我們假設(shè)乘客需求和系統(tǒng)動(dòng)力學(xué)的信息都是已知且確定的,以此為前提搭建混合整數(shù)規(guī)劃模型求得無(wú)人駕駛出租車調(diào)度問(wèn)題的獎(jiǎng)勵(lì)值理論上界。我們把整個(gè)調(diào)度問(wèn)題視為求解靜態(tài)的混合整數(shù)規(guī)劃問(wèn)題,該混合整數(shù)規(guī)劃模型目標(biāo)設(shè)置為成本最低來(lái)求解最優(yōu)的調(diào)度策略。在后續(xù)的實(shí)驗(yàn)中,我們將混合整數(shù)規(guī)劃的求得的理論上界與強(qiáng)化學(xué)習(xí)的結(jié)果進(jìn)行比較,進(jìn)而分析TD3網(wǎng)絡(luò)訓(xùn)練過(guò)程的收斂效果。
4 量化實(shí)驗(yàn)
4.1 實(shí)驗(yàn)設(shè)置在模型訓(xùn)練之前,我們搭建了一個(gè)環(huán)境模擬器來(lái)模擬無(wú)人駕駛出租車的運(yùn)營(yíng)及調(diào)度過(guò)程。其中用戶出行需求信息提取于真實(shí)的紐約市曼哈頓區(qū)域黃色出租車訂單數(shù)據(jù)。我們假設(shè)所有的出租車都是自動(dòng)駕駛車輛,可以集中調(diào)度。因此,我們的目標(biāo)是利用強(qiáng)化學(xué)習(xí)TD 算法和這個(gè)模擬器,來(lái)找出最優(yōu)的無(wú)人駕駛出租車調(diào)度策略。我們首先從NYC TLC(Taxi & Limousine Commission)獲得了關(guān)于紐約市曼哈頓的地理坐標(biāo)。該地圖將紐約市的曼哈頓區(qū)分為 個(gè)區(qū)域。
然后我們從NYC TLC 中獲得了 016年月黃色出租車在曼哈頓市的訂單數(shù)據(jù)集。該數(shù)據(jù)集記錄著乘客上車和下車的地點(diǎn)和時(shí)間、行駛距離、費(fèi)用、費(fèi)率類型、支付類型和司機(jī)報(bào)告的乘客數(shù)量等信息。為了減少模型驗(yàn)證的計(jì)算量同時(shí)不失其真實(shí)性,我們做了三種簡(jiǎn)化:首先我們將無(wú)人駕駛出租車行駛區(qū)域劃分為 個(gè)服務(wù)區(qū),也就是說(shuō)我們把區(qū)域聚集成更大的區(qū)域,從而形成一個(gè)小的網(wǎng)絡(luò)。
由于高峰時(shí)間段,供應(yīng)與需求有著較大的差距。我們選取早高峰的 點(diǎn)到 點(diǎn)的數(shù)據(jù),時(shí)間間隔設(shè)定為 分鐘。第三,我們假設(shè)每天每個(gè)區(qū)域的初始車輛分布是一樣的。這三個(gè)假設(shè)有助于我們減少計(jì)算時(shí)間和計(jì)算量來(lái)驗(yàn)證我們的方法。如果有足夠的計(jì)算能力,我們的方法也可以推廣到任何規(guī)模的網(wǎng)絡(luò)和時(shí)間間隔。為了不失合理性,在仿真器中,結(jié)合當(dāng)?shù)氐沫h(huán)境及相關(guān)政策,我們手動(dòng)設(shè)置了其他參數(shù),如旅行時(shí)間、等待成本、調(diào)度成本等,模擬無(wú)人駕駛出租車運(yùn)營(yíng)場(chǎng)景。
4.2 乘客需求確定
仿真環(huán)境下的TD3架構(gòu)部署與表現(xiàn)本文的策略網(wǎng)絡(luò)是由三層線性網(wǎng)絡(luò)(大小為 56)和三層激活層(前兩層為relu激活函數(shù),最后一層為tanh激活函數(shù))組成。動(dòng)作價(jià)值網(wǎng)絡(luò)由三層線性網(wǎng)絡(luò)(大小為 56)和兩層激活層(都為relu激活函數(shù))組成。其次,為了與混合整數(shù)規(guī)劃算法做對(duì)比,我們?cè)O(shè)定每天模擬器的乘客需求都是確定的,也就說(shuō)每天每個(gè)時(shí)刻每個(gè)區(qū)域到另一個(gè)區(qū)域的需求都是確定的。因此在此種情況下,混合整數(shù)規(guī)劃的目標(biāo)函數(shù)值即為獎(jiǎng)勵(lì)函數(shù)值的理論上界。
強(qiáng)化學(xué)習(xí)的訓(xùn)練過(guò)程是令獎(jiǎng)勵(lì)越大越好,此處設(shè)置的獎(jiǎng)勵(lì)值為成本的負(fù)數(shù),也就是說(shuō)訓(xùn)練過(guò)程中成本會(huì)越來(lái)越小。在實(shí)驗(yàn)中,我們將TD 算法與強(qiáng)化學(xué)習(xí)的另一種算法深度確定性策略梯度算法(Deep Deterministic Policy Gradient),簡(jiǎn)稱為DDPG算法,進(jìn)行比較。實(shí)驗(yàn)總共訓(xùn)練了300萬(wàn)次,每 000次進(jìn)行驗(yàn)證,結(jié)果如圖 所示。TD 算法實(shí)驗(yàn)最終收斂在 7.051 10 ,DDPG算法最終收斂在 7.403 10 。利用Gurobi優(yōu)化器求得混合整數(shù)規(guī)劃的最優(yōu)解為 6.905 10 。
通過(guò)對(duì)比,我們得知TD3算法與DDPG算法都收斂于整數(shù)規(guī)劃理論最優(yōu)值,但TD3算法比DDPG算法波動(dòng)性更小、收斂更快且更接近于混合整數(shù)規(guī)劃求得的理論上界。這是因?yàn)門D 算法在DDPG算法基礎(chǔ)上有三個(gè)改進(jìn),首先采用了兩個(gè)動(dòng)作價(jià)值網(wǎng)絡(luò)更新學(xué)習(xí)的方式,可以有效抑制動(dòng)作價(jià)值網(wǎng)絡(luò)高估的問(wèn)題。第二采用了策略網(wǎng)絡(luò)延遲更新的方法,讓策略網(wǎng)絡(luò)訓(xùn)練更加穩(wěn)定。第三采用了目標(biāo)網(wǎng)絡(luò)平滑化的方法,通過(guò)計(jì)算目標(biāo)動(dòng)作價(jià)值網(wǎng)絡(luò)值時(shí)動(dòng)作添加噪聲,從而讓目標(biāo)動(dòng)作價(jià)值網(wǎng)絡(luò)更新更準(zhǔn)確和魯棒。
4.3 乘客需求不確定
仿真環(huán)境下的TD3架構(gòu)部署與表現(xiàn)為了進(jìn)一步測(cè)試TD3算法的實(shí)驗(yàn)表現(xiàn),我們進(jìn)一步允許乘客需求的隨機(jī)性。用一個(gè)月的每個(gè)時(shí)刻每個(gè)區(qū)域的平均值作為乘客需求確定的情況,設(shè)為D0,也就是3.2中乘客需求確定下的仿真環(huán)境設(shè)置。接下來(lái)進(jìn)一步給需求添加不確定性,把需求變?yōu)楦咚狗植迹禐橐粋(gè)月每個(gè)區(qū)域的需求均值,標(biāo)準(zhǔn)差設(shè)為 的均值和 均值兩種情況,表示為D25和50的情況。通過(guò)這樣的設(shè)置,我們得到三種需求環(huán)境分別是10 、 25、 50。
通過(guò)實(shí)驗(yàn)我們可以看出TD 算法在D25、D50兩種不確定需求的情況下均可達(dá)到收斂。盡管需求隨機(jī)性為 50的時(shí)候,獎(jiǎng)勵(lì)值波動(dòng)比較大,但仍然在150萬(wàn)輪之后趨于平穩(wěn)。對(duì)比在D0、 25、D50三種環(huán)境的訓(xùn)練曲線,我們可以發(fā)現(xiàn)顧客需求不確定性越大,獎(jiǎng)勵(lì)值波動(dòng)越大。這是符合規(guī)律的,因?yàn)轭櫩托枨笫枪?3)獎(jiǎng)勵(lì)值的其中一個(gè)因變量。當(dāng)顧客需求不確定性越大時(shí),獎(jiǎng)勵(lì)值波動(dòng)也就越大。
但更關(guān)鍵的是,我們可以看到在三種情況下訓(xùn)練的算法都可以達(dá)到收斂。因此可以得出結(jié)論:TD 算法可以有效應(yīng)對(duì)需求不確定環(huán)境下的無(wú)人駕駛出租車調(diào)度。圖 給出了不同需求環(huán)境下訓(xùn)練出來(lái)的最優(yōu)模型(即通過(guò)上述不同仿真環(huán)境訓(xùn)練得到的D0 TD3、D25TD3、D50 TD3模型)分別在不同需求環(huán)境下的測(cè)試獎(jiǎng)勵(lì)值。
結(jié)束語(yǔ)
在本文中,我們提出了一種用深度強(qiáng)化學(xué)習(xí)方法解決自動(dòng)駕駛出租車調(diào)度問(wèn)題。該方法基于雙延遲深度確定性策略梯度算法(TD3)框架,該框架由兩個(gè)深度神經(jīng)網(wǎng)絡(luò)搭建。在實(shí)驗(yàn)中,我們首先對(duì)紐約市曼哈頓區(qū)域黃色出租車數(shù)據(jù)進(jìn)行整理分析,然后我們假設(shè)系統(tǒng)動(dòng)力學(xué)都是已知且確定的,所以我們可以通過(guò)混合整數(shù)規(guī)劃得到了獎(jiǎng)勵(lì)(總成本的負(fù)數(shù))的理論上界。
我們將雙延遲深度確定性策略梯度算法應(yīng)用在紐約市曼哈頓區(qū)域的黃色出租車的交通網(wǎng)絡(luò)中。通過(guò)實(shí)驗(yàn)對(duì)比,我們?cè)跍y(cè)試集上證實(shí)了TD3算法在需求不確定的情況下訓(xùn)練出來(lái)的模型的收斂性及有效性。同時(shí)我們通過(guò)不確定交通需求和需求突變的情況來(lái)測(cè)試算法的魯棒性,實(shí)驗(yàn)證明TD3算法能夠有效應(yīng)對(duì)需求不確定的情況。本文還留下了很多有意思的值得拓展的研究。
首先,我們的實(shí)驗(yàn)是建立在一個(gè)簡(jiǎn)化的交通網(wǎng)絡(luò)上進(jìn)行的。由于不斷增長(zhǎng)的動(dòng)作空間和狀態(tài)空間,進(jìn)行大規(guī)模的集中策略調(diào)度一直是一個(gè)挑戰(zhàn)。也許可以嘗試一下采用多智能體強(qiáng)化學(xué)習(xí)的方法,如Boyali 將每個(gè)司機(jī)作為一個(gè)智能體,多個(gè)司機(jī)協(xié)同調(diào)度,從而可以有效提高調(diào)度系統(tǒng)運(yùn)行的效率,Seow 采用多智能體模型,分布式調(diào)度出租車。其次我們的實(shí)驗(yàn)中只考慮了單一模式的車輛,而在未來(lái)運(yùn)營(yíng)商可能由人類駕駛的車輛和無(wú)人駕駛出租車結(jié)合的車隊(duì)組成 ,算法可以進(jìn)一步結(jié)合兩者的特點(diǎn)。除此之外,我們還可以進(jìn)一步考慮拼車對(duì)調(diào)度策略的影響[27]。
目前我們的研究中是沒(méi)有考慮拼車系統(tǒng)的,如果能進(jìn)一步考慮拼車系統(tǒng)的話,運(yùn)營(yíng)商就可以用更少的車輛滿足更多的需求,進(jìn)一步提高效率,節(jié)約能源,緩解交通擁堵。最后,我們目前只結(jié)合顧客的需求與現(xiàn)有的車輛進(jìn)行調(diào)度,但我們可以參考更多的信息比如交通情況等來(lái)參與決策,從而能利用更多的信息來(lái)進(jìn)行優(yōu)化調(diào)度。
參考文獻(xiàn):
[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)
陳晟愷 方水良 唐任仲 基于需求預(yù)測(cè)的云制造服務(wù)租賃配置優(yōu)化 J].計(jì)算機(jī)集成制造系統(tǒng),2020,26(11):2944 2954.
作者:周曉婷1,吳祿彬1,章 宇2,姜善成1+