基于深度強(qiáng)化學(xué)習(xí)的停車位智能動(dòng)態(tài)分配方法

馮毅彬，裴祥靜，陳柱光，黃星翔，胡文豪，陳向洋

（1.華南理工大學(xué)土木與交通學(xué)院，廣州 510641；2.廣東省外語藝術(shù)職業(yè)學(xué)院財(cái)會(huì)金融學(xué)院，廣州 510507）

停車位分配是由停車系統(tǒng)為每一個(gè)到達(dá)的車輛進(jìn)行停車位分配，以避免車輛“低效尋泊”造成的時(shí)間損耗和能源損耗，并最大化利用停車資源。Mouskos 等[1]將停車問題刻畫為有限資源的時(shí)空分配問題，利用混合整數(shù)線性規(guī)劃模型求解了在最小化用戶費(fèi)用下的最優(yōu)解。張水潮等[2]提出了基于用戶預(yù)約信息的共享停車位分配模型，實(shí)現(xiàn)了用戶端步行距離和平臺(tái)端停車費(fèi)收益的平衡。Kotb 等[3]以停車位時(shí)空利用率的最大化為目標(biāo)，將停車需求分配與動(dòng)態(tài)價(jià)格管理結(jié)合，設(shè)計(jì)了MILP 模型并用CPLEX 求解器進(jìn)行求解。Zhao 等[4]提出了一種智能體數(shù)值仿真方法，考慮了停車需求到達(dá)和離開的不確定性，設(shè)計(jì)了具有魯棒性的停車位分配策略。與傳統(tǒng)基于模型和求解算法的方法相比，深度強(qiáng)化學(xué)習(xí)在處理復(fù)雜系統(tǒng)的決策問題上更具優(yōu)勢(shì)[5]。Ke等[6]在網(wǎng)約車派單問題上提出了基于深度強(qiáng)化學(xué)習(xí)的智能延遲匹配的策略，結(jié)果表明該策略可以有效減少用戶的等待時(shí)間。Wen 等[7]提出了一種基于深度Q 學(xué)習(xí)（DQN）的共享汽車需求響應(yīng)式的調(diào)度網(wǎng)絡(luò)，該方法可有效減少車隊(duì)規(guī)模和行駛距離。趙聰?shù)萚8]提出了基于多智能體深度Q 學(xué)習(xí)的停車系統(tǒng)智能延時(shí)匹配方法，智能體自主決策延時(shí)等待時(shí)間，進(jìn)入分配池后由系統(tǒng)利用匈牙利算法進(jìn)行泊位匹配，結(jié)果表明在停車供需相對(duì)平衡的環(huán)境下，可有效減少用戶的停車時(shí)間和步行距離。基于此，本研究結(jié)合智能延時(shí)匹配策略，利用DQN 深度強(qiáng)化學(xué)習(xí)算法進(jìn)行停車位的智能分配，以其智能性和自適應(yīng)性強(qiáng)的特點(diǎn)，實(shí)現(xiàn)系統(tǒng)的“長(zhǎng)視性”收益，進(jìn)一步提升停車系統(tǒng)的周轉(zhuǎn)效率和服務(wù)水平。

1 智能停車位分配系統(tǒng)

智能停車位分配系統(tǒng)的示意圖如圖1 所示。在系統(tǒng)準(zhǔn)備階段，以目標(biāo)停車場(chǎng)的環(huán)境信息作為狀態(tài)空間，構(gòu)建基于DQN 算法的車位分配模型。通過歷史數(shù)據(jù)提取停車行為特征，并據(jù)此設(shè)置停車需求分布參數(shù)，以建立停車場(chǎng)的數(shù)值仿真系統(tǒng)。模型通過仿真系統(tǒng)訓(xùn)練，輸出智能分配策略，最后加載至停車系統(tǒng)服務(wù)器即可投入使用。在系統(tǒng)應(yīng)用階段，當(dāng)用戶到達(dá)停車場(chǎng)入口時(shí)，系統(tǒng)會(huì)根據(jù)實(shí)時(shí)狀態(tài)信息，采取智能延時(shí)的決策，延時(shí)等待時(shí)間結(jié)束后，再為用戶動(dòng)態(tài)分配最優(yōu)停車位。其中，智能延時(shí)匹配策略指車輛到達(dá)停車場(chǎng)后，通過適當(dāng)?shù)难訒r(shí)等待，以獲得更優(yōu)質(zhì)的泊位資源。

圖1 智能停車位分配系統(tǒng)示意圖

2 馬爾科夫決策過程刻畫

2.1 智能體

將停車管理者設(shè)為智能體，為每個(gè)到達(dá)的停車需求分配一個(gè)最優(yōu)停車位。

2.2 狀態(tài)

為智能體每一時(shí)刻所能觀測(cè)到的停車場(chǎng)環(huán)境信息和車輛信息。定義狀態(tài)空間

式中：Xocc為車位占有狀態(tài)，Xcha為充電樁分布信息，二者均采用One-hot 編碼；treal為實(shí)際時(shí)間；車輛為第i輛車的能源類型，0 為油車，1 為電車為第i輛車的累計(jì)延遲時(shí)間。

2.3 動(dòng)作

包含是否采取延時(shí)匹配和分配車位編號(hào)。定義動(dòng)作空間

式中：n為智能體采取的動(dòng)作值；N為停車場(chǎng)內(nèi)的車位數(shù)；當(dāng)at＜N，表示對(duì)該車輛進(jìn)行延時(shí)匹配；當(dāng)at＞N，表示直接匹配，且匹配對(duì)應(yīng)的車位編號(hào)為（at-N）。

2.4 獎(jiǎng)勵(lì)函數(shù)

定義如下

式中：Rt表示獎(jiǎng)勵(lì)函數(shù)，rpar表示停車位距離對(duì)應(yīng)獎(jiǎng)勵(lì)值，rcha表示充電需求對(duì)應(yīng)獎(jiǎng)勵(lì)值，rdelay表示延時(shí)匹配對(duì)應(yīng)獎(jiǎng)勵(lì)值。

式中：L為基準(zhǔn)距離，使其距離越小，獎(jiǎng)勵(lì)值越大；ldri為從入口到停車位的駕駛距離，lwalk為停車位到目的地的步行距離；vdri/vwalk為車輛行駛速度與人步行速度的比值；α 為用戶的步行意愿系數(shù)。

式中：β 為用戶延時(shí)等待的懲罰系數(shù)；twait為用戶延時(shí)等待的時(shí)間。

2.5 狀態(tài)轉(zhuǎn)移

由一個(gè)元組（s，a，R，s′）表示，可描述為：當(dāng)車輛進(jìn)入停車場(chǎng)時(shí)，智能體根據(jù)當(dāng)前狀態(tài)s，輸出動(dòng)作a為車位分配決策，并獲得相應(yīng)的獎(jiǎng)勵(lì)R，最后更新停車場(chǎng)環(huán)境到下一個(gè)狀態(tài)s′。

3 DQN 深度強(qiáng)化學(xué)習(xí)算法框架

本研究采用全連接神經(jīng)網(wǎng)絡(luò)（FCNN）來逼近Q值函數(shù)，以有效處理高維度的狀態(tài)和動(dòng)作空間。每一步中輸出最大Q值對(duì)應(yīng)的動(dòng)作為決策，訓(xùn)練后得到車位分配策略πθ（s，a），并以權(quán)重參數(shù)的形式儲(chǔ)存在神經(jīng)網(wǎng)絡(luò)中。目標(biāo)網(wǎng)絡(luò)是一個(gè)與估計(jì)網(wǎng)絡(luò)（主網(wǎng)絡(luò)）結(jié)構(gòu)相同的神經(jīng)網(wǎng)絡(luò)，但其參數(shù)按一定的間隔更新。估計(jì)網(wǎng)絡(luò)用于估計(jì)當(dāng)前狀態(tài)下的Q值，而目標(biāo)網(wǎng)絡(luò)用于計(jì)算目標(biāo)Q值。通過引入目標(biāo)網(wǎng)絡(luò)來生成目標(biāo)Q值，減少訓(xùn)練中的目標(biāo)值與估計(jì)值之間的相關(guān)性，以提高算法穩(wěn)定性。其中Q值的計(jì)算公式如下

式中：Q（s，a）表示在狀態(tài)s下采取動(dòng)作a的Q值；R為采取動(dòng)作獲得的即時(shí)獎(jiǎng)勵(lì)；γ 為折扣因子，maxQ（s′，a′）表示下一個(gè)狀態(tài)s′下所有可能動(dòng)作的最大Q值，且由目標(biāo)Q網(wǎng)絡(luò)估計(jì)。

在動(dòng)作選擇過程中加入了ε-greedy 探索策略，以幫助智能體避免陷入局部最優(yōu)解，更好地全面探索環(huán)境。其公式如下

式中：a為智能體選擇的動(dòng)作，argmaxQ（s，a）表示在當(dāng)前狀態(tài)s下選擇Q值最大的動(dòng)作；N為停車場(chǎng)中的車位數(shù)，randint（0，N-1）表示[0，N-1]間的一個(gè)隨機(jī)整數(shù)，即對(duì)應(yīng)車位的編號(hào)；p為選擇概率；ε 為探索率，會(huì)隨著訓(xùn)練逐漸減小。

損失函數(shù)是目標(biāo)Q值與估計(jì)Q值之間的差異程度，通過最小化損失函數(shù)，可以使估計(jì)Q值逐步接近真實(shí)的Q值函數(shù)，用于指導(dǎo)模型在訓(xùn)練過程中的參數(shù)更新。本模型采用均方誤差（MSE）來計(jì)算損失函數(shù)L（θ），其公式如下：

式中：θ 為模型參數(shù)，N為樣本數(shù)量，si為輸入狀態(tài)，ai為模型選擇的動(dòng)作，Qe（si，ai；θ）表示模型對(duì)狀態(tài)si所選擇動(dòng)作ai的估計(jì)Q值，Qti則為目標(biāo)Q值。

由于狀態(tài)和動(dòng)作的維度較大，還需采取經(jīng)驗(yàn)回放策略，將智能體所經(jīng)歷的經(jīng)驗(yàn)儲(chǔ)存在經(jīng)驗(yàn)回放池中，并在訓(xùn)練時(shí)從中隨機(jī)抽取一定數(shù)量的經(jīng)驗(yàn)進(jìn)行訓(xùn)練，從而提高數(shù)據(jù)利用率和訓(xùn)練穩(wěn)定性。本研究的算法框架設(shè)計(jì)示意圖如圖2 所示。

圖2 DQN 算法框架設(shè)計(jì)

4 停車場(chǎng)數(shù)值仿真系統(tǒng)

本研究通過提取停車場(chǎng)訂單數(shù)據(jù)中的停車行為特征，建立數(shù)值仿真系統(tǒng)作為與深度強(qiáng)化學(xué)習(xí)智能體相交互的外界環(huán)境。仿真系統(tǒng)可實(shí)現(xiàn)車輛到達(dá)、充電需求、車位匹配和狀態(tài)更新等重要環(huán)節(jié)，以模擬實(shí)際停車場(chǎng)中的環(huán)境變化與停車行為，為智能體學(xué)習(xí)提供訓(xùn)練材料。當(dāng)一個(gè)停車需求產(chǎn)生時(shí)，系統(tǒng)會(huì)為其分配最優(yōu)車位，該停車位的使用狀態(tài)隨即變?yōu)椤罢加谩保渫＼嚂r(shí)長(zhǎng)結(jié)束后則重新變回“空閑”。本仿真系統(tǒng)設(shè)定停車位數(shù)量為100 個(gè)，配有充電樁的停車位數(shù)量為50 個(gè)，到達(dá)車輛為電車的概率為50%。同時(shí)以現(xiàn)實(shí)中的1 s 作為仿真步長(zhǎng)，且不同時(shí)段的停車行為特征具有差異。其中車輛到達(dá)服從泊松分布，參數(shù)λ 表示單位時(shí)間內(nèi)平均到達(dá)的車輛數(shù)；停車時(shí)長(zhǎng)服從正態(tài)分布，參數(shù)μ 和σ分別代表均值和標(biāo)準(zhǔn)差，具體參數(shù)設(shè)定見表1。

表1 停車行為仿真參數(shù)

5 算例分析

本研究采用PyTorch 框架對(duì)神經(jīng)網(wǎng)絡(luò)進(jìn)行構(gòu)建，并將模型代入數(shù)值仿真系統(tǒng)，選用Adam 訓(xùn)練器進(jìn)行訓(xùn)練。其中DQN 算法超參數(shù)設(shè)置見表2。

表2 算法超參數(shù)設(shè)定

為了測(cè)試本研究提出的停車位智能動(dòng)態(tài)分配方法的有效性和魯棒性，本文設(shè)計(jì)了貪心算法、隨機(jī)狀態(tài)2種不同的分配策略作為對(duì)照，并將下述方法在數(shù)值仿真系統(tǒng)中進(jìn)行同步測(cè)試，對(duì)不同評(píng)價(jià)指標(biāo)進(jìn)行對(duì)比分析。其中貪心算法是一種常用的啟發(fā)式算法，以“先到先得”“用戶最優(yōu)”為原則，是最貼合人為邏輯的分配方法。貪心算法通過在每一步選擇當(dāng)前狀態(tài)下的最佳選擇，具有簡(jiǎn)單、高效的優(yōu)點(diǎn)，但不能保證獲得全局最優(yōu)解。而隨機(jī)狀態(tài)是用戶隨機(jī)選擇停車位，較符合日常生活中的停車行為特征，且反映了現(xiàn)實(shí)中普遍應(yīng)用的由車輛隨機(jī)停放的傳統(tǒng)管理模式。

5.1 平均獎(jiǎng)勵(lì)值分析

本研究將DQN 算法、貪心算法和隨機(jī)狀態(tài)3 種方法輸入到數(shù)值仿真系統(tǒng)，進(jìn)行同步訓(xùn)練測(cè)試。平均獎(jiǎng)勵(lì)對(duì)比圖如圖3 所示，可見得雖然在訓(xùn)練前期貪心算法的平均獎(jiǎng)勵(lì)值最高，但隨著迭代次數(shù)的增加，DQN 算法的系統(tǒng)平均獎(jiǎng)勵(lì)值要明顯高于貪心算法和隨機(jī)狀態(tài)。由此可見，DQN 算法對(duì)時(shí)空資源占用及變化規(guī)律的掌握，能夠有效學(xué)習(xí)到復(fù)雜狀態(tài)與動(dòng)作間的映射關(guān)系，在分配策略上更具遠(yuǎn)見性和魯棒性。

圖3 平均獎(jiǎng)勵(lì)訓(xùn)練對(duì)比圖

5.2 停車場(chǎng)周轉(zhuǎn)率分析

停車周轉(zhuǎn)率是停車場(chǎng)中每天每車位的平均使用次數(shù)，是衡量停車系統(tǒng)效率的重要參考指標(biāo)。將上述3 種方法在數(shù)值仿真系統(tǒng)中進(jìn)行100 次同步測(cè)試，得到如圖4 所示的停車場(chǎng)周轉(zhuǎn)率對(duì)比圖。由此可見在基于DQN 算法車位分配模式下的停車場(chǎng)周轉(zhuǎn)率為5.27 次/天/車位，對(duì)比貪心算法和隨機(jī)狀態(tài)，分別顯著提升了9.8%和6.7%。因此，停車位智能動(dòng)態(tài)分配策略的應(yīng)用，從系統(tǒng)層面顯著提升了停車場(chǎng)的運(yùn)行效率和停車位的利用率。

圖4 停車場(chǎng)周轉(zhuǎn)率對(duì)比圖

5.3 平均停車總時(shí)間分析

對(duì)于停車用戶來說，個(gè)人停車效率是用戶最關(guān)心、提升用戶滿意度最顯著的重點(diǎn)。平均停車總時(shí)間，包括到達(dá)目標(biāo)車位的駕駛時(shí)間和到達(dá)商場(chǎng)出入口的步行時(shí)間，是用戶停車效率最直觀、最明顯的評(píng)價(jià)指標(biāo)。本文將采取延時(shí)策略的DQN 算法、不采取延時(shí)策略的DQN 算法、貪心算法和隨機(jī)狀態(tài)共4 種策略，在數(shù)值仿真系統(tǒng)中對(duì)平均停車總時(shí)間進(jìn)行100 次測(cè)試對(duì)比，得到了如圖5 所示的平均停車總時(shí)間對(duì)比圖。由此可見，采取智能延時(shí)匹配策略的DQN 算法應(yīng)用下的平均停車總時(shí)間最短，為67.45 s，低于不采取延時(shí)匹配策略的DQN 算法2.8%，低于貪心算法6.7%，低于隨機(jī)狀態(tài)15.9%。延時(shí)匹配策略雖然增加了一定的等待時(shí)間，但由于能夠獲得更優(yōu)質(zhì)的停車位，總體停車時(shí)間得以下降。因此，可認(rèn)為DQN 算法框架下動(dòng)態(tài)車位分配與智能延時(shí)匹配策略的結(jié)合，提升了算法性能和用戶停車效率，對(duì)比其他策略更具有全局性和遠(yuǎn)視性。

圖5 平均停車總時(shí)間對(duì)比圖

6 結(jié)束語

本研究在DQN 深度強(qiáng)化學(xué)習(xí)算法框架下，實(shí)現(xiàn)停車位動(dòng)態(tài)分配和智能延時(shí)匹配策略的結(jié)合。將停車場(chǎng)管理者抽象為智能體，通過數(shù)值仿真系統(tǒng)模擬不同的環(huán)境狀態(tài)進(jìn)行學(xué)習(xí)，訓(xùn)練得到停車位智能分配策略，能夠?yàn)槊恳粋€(gè)用戶實(shí)時(shí)選擇匹配等待時(shí)間，等待后再動(dòng)態(tài)分配最優(yōu)停車位。仿真測(cè)試結(jié)果表明，停車位智能動(dòng)態(tài)分配方法能夠更有效減少用戶的平均停車總時(shí)間，提高停車系統(tǒng)的周轉(zhuǎn)率。本研究適用于諸多應(yīng)用場(chǎng)景，如各大公共場(chǎng)所的配套停車場(chǎng)和自動(dòng)化立體停車庫(kù)，還順應(yīng)了智能代客泊車技術(shù)的發(fā)展趨勢(shì)，為車輛自動(dòng)停泊過程中的車位匹配問題提供解決方案，豐富現(xiàn)有研究。