基于深度強化學習的停車位智能動態(tài)分配方法

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

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

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

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

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

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

2 馬爾科夫決策過程刻畫

2.1 智能體

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

2.2 狀態(tài)

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

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

2.3 動作

包含是否采取延時匹配和分配車位編號。定義動作空間

式中：n為智能體采取的動作值；N為停車場內的車位數(shù)；當at＜N，表示對該車輛進行延時匹配；當at＞N，表示直接匹配，且匹配對應的車位編號為（at-N）。

2.4 獎勵函數(shù)

定義如下

式中：Rt表示獎勵函數(shù)，rpar表示停車位距離對應獎勵值，rcha表示充電需求對應獎勵值，rdelay表示延時匹配對應獎勵值。

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

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

2.5 狀態(tài)轉移

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

3 DQN 深度強化學習算法框架

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

式中：Q（s，a）表示在狀態(tài)s下采取動作a的Q值；R為采取動作獲得的即時獎勵；γ 為折扣因子，maxQ（s′，a′）表示下一個狀態(tài)s′下所有可能動作的最大Q值，且由目標Q網絡估計。

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

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

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

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

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

圖2 DQN 算法框架設計

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

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

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

5 算例分析

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

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

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

5.1 平均獎勵值分析

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

圖3 平均獎勵訓練對比圖

5.2 停車場周轉率分析

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

圖4 停車場周轉率對比圖

5.3 平均停車總時間分析

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

圖5 平均停車總時間對比圖

6 結束語

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