陳立偉，董睿婷，王桐

1.哈爾濱工程大學 信息與通信工程學院，黑龍江 哈爾濱 150001

2.哈爾濱工程大學 先進船舶通信與信息技術工業(yè)和信息化部重點實驗室，黑龍江 哈爾濱 150001

隨著車輛保有量急劇增加，城市中停車難問題日益加劇。尤其對于城市中心，停車資源與停車需求的極度不匹配導致道路擁堵嚴重，停車資源分配不合理造成停車場服務效率不平衡。因此停車場外停車誘導方法亟需著重研究，互聯(lián)網的快速發(fā)展也使得智能場外停車誘導[1]成為可能。

針對場外停車誘導問題，Rajabioun等[2]和Xiao等[3]基于模型分析停車信息的季節(jié)性和時空相關性，對未來的停車可用信息[4]進行預測，得到未來去往各停車場成功停車的概率作為誘導依據。Badii等[5]和Yang等[6]等分別采用統(tǒng)計以及機器學習的方法對成功找到停車位的概率進行預測。這些依賴預測概率的方法在停車需求大時并不可靠，且容易受到運營模式和特殊事件[7]的影響。王韓麒[8]考慮雙目標函數的約束，基于灰熵理論，構建場外停車誘導模型，以提高區(qū)域范圍內的停車率。Boyles等[9]模擬單個駕駛員的停車搜索過程，根據駕駛員過去訪問停車場的記錄設置先驗值，完善馬爾科夫模型狀態(tài)空間。Liu等[10]利用瓶頸模型分析停車場收費標準和管理模式對停車時間等造成的影響。常玉林等[11]采用排隊模型研究路徑流量與停車場可用性的關系，提出隨機用戶均衡模型。陳群等[12]考慮總行程時間以及停車場的周轉率，對停車位分配進行優(yōu)化。然而這些方法都只考慮單一用戶的利益最大化，而沒有考慮到所有發(fā)起停車請求的用戶之間競爭合作的博弈關系，所以會出現對某一用戶車輛最優(yōu)的停車誘導策略，對整個系統(tǒng)卻遠遠不是最優(yōu)的。

本文在多車停車需求的情況下，考慮全局利益，引入強化學習（reinforcement learning，RL）方法提出一種基于強化學習的智能場外停車誘導策略，使停車效率最大化，平衡所有停車場的停車占用率，以減少停車搜索對城市擁堵帶來的影響。

1 停車信息預測模型

停車信息包括用戶停車時間及目的地、停車場所的位置及車位占用率等，停車信息的獲取是進行場外停車誘導的前提，通常由車載聯(lián)網系統(tǒng)以及傳感器設備等可以實現實時獲取停車信息。本文采用預訂機制完成未來停車信息預測模型。

1.1 車路協(xié)同通信架構

在智能交通背景下，通過部署路側單元（road side unit，RSU）形成車路協(xié)同（vehicle to road side unit，V2R）通信架構，將停車誘導系統(tǒng)的計算負荷分布到云端進行，將結果發(fā)送至車載模塊，實現車路協(xié)同[13]。建立城市環(huán)境下場外停車誘導系統(tǒng)的V2R 通信模型，如圖1 所示。具體通信步驟如下：

圖1 V2R 通信架構

1）在每個更新周期T內，每個停車場節(jié)點將自身停車信息（停車位占用情況、排隊信息等）、位置等發(fā)送給RSU，實現信息的實時傳遞與更新。

2）當車輛有停車需求時，向RSU 發(fā)送自己的預訂停車時長與行駛目的地，由RSU 進行存儲和計算。

3）RSU 執(zhí)行停車誘導策略算法，對時間步內有停車需求的車輛進行統(tǒng)一調度，并將調度結果返回給車輛。

4）各車輛分別前往由RSU 提供的停車場，完成停車誘導。

5）RSU 將誘導結果發(fā)送給停車場P，P根據誘導信息更新自身狀態(tài)。再重新執(zhí)行步驟1）。

1.2 預測模型

假定在某道路交通系統(tǒng)中，在時刻t行駛著N輛汽車，這些汽車構成了交通系統(tǒng)中的車輛集合V={V1,V2,···,VN}，區(qū)域內包含M個停車場，構成停車場集合P={P1,P2,···,PM}，對應于每一個停車場Pj假定有mj個停車位。

某時刻車輛Vi發(fā)起停車預訂請求，包含停車時長Ti，以及行駛目的地Di，構成一個預訂信息表G=〈T,D〉。該車輛需要尋找合適的停車場進行停車，對于 ?i=1,2,···,N：

將狀態(tài)改變1 次的時長設為1 個時間步，根據車輛所在位置 (xi,yi)，停車場所在位置 (xj,yj)，考慮停車場的車位占用情況，?j=1,2,···,M，為車輛選擇停車場制定一個策略F=Fi j：

在車輛發(fā)起停車預訂請求以及成功停車時對Vi和Fij的值進行更新。并且，對它們施加一個約束：

即可得到停車場Pj的服務量pj：

式中p0為實時獲取的停車場當前服務量。

由于車輛到達各個停車場的距離不同，即車輛在路途中消耗的時間各不相同，這會導致車輛到達停車場進行排隊的順序不同。設車輛Vi到達停車場Pj的路程為di,j，行駛的平均速度為vi，則路途耗時為

對于場外停車誘導策略來說，車輛的排隊時間很大程度上由排隊長度決定。假設停車場Pj的當前排隊車輛數目為L，車輛的排隊位置為

式中：lP為正在停車場處排隊的車輛長度，lT為在去往停車場過程中所用時間較小的排隊車輛長度。對于l∈{1,2,···,L}，停車場Pj的當前排隊隊列中第l輛車表示為Vl,j，uj表示在停車場Pj中當前被占用的停車位數量，tinit為車輛發(fā)起停車需求的起始時間，βl,j為Vl,j停車結束時間。車輛停車消耗的總時間T包括路程時間和排隊等待時間，設車輛在停車場預訂的停留時間=Ti，分3 種情況對停車結束時間 βl,j進行討論：

1) 當uj+l≤mj時，即停車位充足，沒有車輛進行排隊時：

2) 當l=1且uj+l＞mj時，即當前車輛位于排隊位置的第一個時：

3) 當l＞1且uj+l＞mj時：

式中：τj為當前占用停車位的車輛的結束停車時間集合，為時間集合中第l個停車結束的車輛離開的時間。

所以車輛Vi去往停車場Pj停車消耗的總時間為

則系統(tǒng)內車輛完成停車所消耗的平均停車總時間為

2 強化學習停車誘導策略

2.1 MDP 下的停車誘導模型

本文采用馬爾科夫決策過程（Markov decision processes，MDP），基本框架如圖2 所示。設置停車誘導系統(tǒng)為一個智能體，在執(zhí)行停車誘導策略時，系統(tǒng)與環(huán)境進行交互，環(huán)境通過一組狀態(tài)和動作進行建模，在動作和環(huán)境的作用下，系統(tǒng)會產生新的狀態(tài)，同時環(huán)境會給出一個獎勵。系統(tǒng)以這樣的方式不斷循環(huán)，智能體與環(huán)境不斷交互，則會產生許多數據。

圖2 MDP 的基本框架

強化學習方法是根據系統(tǒng)反饋的獎勵修改自身動作，再通過環(huán)境交互獲得新的數據，從而進一步改善自身的行為，最終智能體在不斷的學習過程中逐步完成最優(yōu)策略的制定。

2.1.1 狀態(tài)空間S

對于一個狀態(tài)空間S，有st∈S。在本文中，設st=Kt，Kt為在時間步t時M個停車場的空閑位置，。場外停車誘導系統(tǒng)在每個狀態(tài)st下采取不同的動作，則誘導情況會處于不同的狀態(tài)。將用戶車輛調度到不同的停車場的到達時間是多種多樣的，并且當有一輛新的車輛到達指定停車場，或者有已完成停車任務的車輛離開時，都可能發(fā)生狀態(tài)轉換。所以在不同的調度動作下會產生不同的下一狀態(tài)。

2.1.2 動作空間A

動作at∈A，是場外停車誘導決策。在狀態(tài)st下，各車輛選擇一個在距目的地的里程約束下可以到達的停車場進行停車，即為誘導決策動作。每個發(fā)起的停車需求會造成系統(tǒng)狀態(tài)的改變，而各車輛在最優(yōu)決策下做出的動作也會改變系統(tǒng)的狀態(tài)。設置動作空間為每個車輛Vi(i∈[1,N])做出的對于停車場的選擇ai={Vi,P1,P2,···,PM}，其中：

為該策略添加約束，以保證策略的完備性以及唯一性，即保證系統(tǒng)內車輛總數限制為N：

2.1.3 狀態(tài)轉移函數

在停車誘導系統(tǒng)中，每一個狀態(tài)下做出的實時動作決策都會對當前狀態(tài)產生定向的改變，但在未來的停車誘導中，當前的最優(yōu)決策可能不會產生未來的最優(yōu)決策。所以系統(tǒng)需要估計未來的回報，以獲得對當前決策的評價。

在本文中，存在2 類主要的動態(tài)因素，即完成停車任務所消耗的總時間以及到達目的地的總路程。消耗的總時間較短且總路程較小的車輛所做出的動作被認為是更優(yōu)的，系統(tǒng)則會為這些動作分配更高的執(zhí)行概率，以使決策向著更優(yōu)的方向發(fā)展。因此設計一個狀態(tài)轉移函數T(s,a,s′)[14]，在MDP 條件下的下一狀態(tài)不受歷史動作和狀態(tài)影響，只受當前狀態(tài)的影響，即

在狀態(tài)s下執(zhí)行動作a，系統(tǒng)會以均勻分布的形式提供狀態(tài)轉移概率，將停車場的當前占有率轉移到下一狀態(tài)s′。并且，對于每個動作a，以及每個狀態(tài)s，都需要滿足 0 ≤T(s,a,s′)≤1。

2.1.4 獎勵函數R

車輛執(zhí)行動作an∈A，然后前往指定的停車場進行停車，學習器將從該車輛的策略中獲得獎勵。系統(tǒng)通過獎勵函數對決策結果進行反饋，以實現學習和更新?？紤]車輛停車過程所消耗的總時間，以及從發(fā)起停車請求的起始點到目的地的路程，目標是在滿足約束條件的同時，將車輛消耗的總時間降至最低，并最大程度地縮短行駛路程。所以本文中，設置獎勵函數為

式中：T(st,at)為車輛在狀態(tài)st下做出動作at所消耗的停車總時間；為初始行駛里程；為與初始里程相比減少的距離；α 和 β分別代表消耗時間和距離所占的權重，若 α較大則策略更傾向于選擇所用時間較短的停車場進行停車，反之則更傾向于選擇行駛路程較短的停車場進行停車。

2.2 基于Q-learning 的停車誘導策略

基于Q-learning 的場外停車誘導策略需要確定一個策略 π，定義為在時間步t對所有發(fā)出停車請求的車輛所作出的一系列停車調度動作at，所以π=(a1,a2,···,at)。我們的目標是得到一個策略π*能最大化總獎勵：

式中Qπ(st,at)為長期回報狀態(tài)-動作值函數：

式中：τ為根據停車誘導策略和狀態(tài)轉移通過采樣所獲得的序列，γ ∈(0,1]為折扣因子。

當狀態(tài)st下做出最佳動作動作at，則能夠得到最優(yōu)狀態(tài)-動作值函數Q*(st,at)為最大期望回報。

采用Q-learning 的停車誘導算法流程如下：

1）初始化參數，對于 ?s∈S，?a∈A，價值函數Q(s,a)=0。

2）更新系統(tǒng)環(huán)境狀態(tài)s，當受到來自車輛的預訂信息時，執(zhí)行停車誘導策略。

3）基于Q值，選擇并執(zhí)行動作a∈A。

4）觀測新的狀態(tài)s′，并得到獎勵函數R(s,a)，更新Q值為

5）執(zhí)行策略最優(yōu)策略 π*為

6）s←s′，重復步驟2）。

3 實驗結果及分析

在本節(jié)中，基于One 仿真平臺進行模型搭建，在模型下應用本文算法，完成基于強化學習的場外停車誘導策略（RL），并將其與基于最短步行路程（minimum distance，MD）[15]策略、基于最短排隊時間（minimum queue time，MQT）[16]策略、基于預約（reservation based，RES）[17]策略進行比較，從總路程、平均消耗時間、累積?？繑狄约巴＼噲稣加寐史矫鎸λ惴ㄐ阅苓M行有效的評估。

3.1 模型搭建

如圖3 所示，本文在One 仿真平臺上將哈爾濱市部分地圖作為仿真背景，部署了150～400 輛車、7 個停車場和6 個RSU。設置仿真時間為12 h，停車場車位數量選取為30～60 個，場景內車輛移動速度為30～50 km/h，車輛在距離目的地小于2 km時會發(fā)起停車請求，并且參數 α 和 β的設置考慮了實際生活中用戶的偏好。

圖3 場外停車誘導場景

3.2 實驗評估

3.2.1 停車總路程評估

使用Dijkstra[18]算法計算開放街道地圖（open street map，OSM）道路網絡中的最短導航距離，包括發(fā)起停車需求的位置到停車場的行駛距離，以及2 段停車場到預訂目的地間的步行距離。

由于MD 策略是選擇距離目的地最近的停車場進行停車，故不考慮對MD 策略下的停車總路程進行評估。由圖4 可知，隨著車輛的增加，車輛的平均總行駛里程略有增加。MQT 策略只考慮排隊等待時間，所以當車輛越來越多時，會選擇距目的地較遠的停車場進行停車。而RES 策略下，車輛對停車場進行預約，則可以避免某些車輛停車過遠，但由于受用戶主觀動作影響，所以無法達到最優(yōu)決策。而RL 策略下的車輛考慮路程因素，智能選擇停車場，所以性能表現最好。

圖4 不同車輛數下的平均總路程

3.2.2 停車總時間評估

如圖5 所示，當場景內車輛數較少時，空閑車位數量可以滿足停車需求，所以排隊等待時間對停車總時間的影響較小，而車輛行駛路程消耗的時間則占了更大的權重，此時MD 策略下車輛選擇距離自己最近的停車場進行停車，所以所消耗的總時間也就最短。但當車輛數不斷增大，停車規(guī)模超過停車場所能承擔的負荷時，MD 策略下就近選擇的方式會使車輛集中涌入某幾個停車場而造成停車負載不均衡，產生停車排隊等待時間，停車消耗的總時間也就明顯增加。MQT 策略考慮了車輛排隊等待時間而忽視了路程時間，所以性能略有提升。RES 策略由于對車位進行了提前預約，所以車輛越多時該策略優(yōu)勢越明顯。而本文采用的RL 策略考慮路程時間的同時，平衡各停車場的占用率，極大地減少停車需求規(guī)模對策略性能的影響，所以隨著車輛的增加，該策略性能優(yōu)勢逐漸增大。

圖5 不同車輛數下的平均消耗時間

3.2.3 累積?？繑翟u估

本次實驗部署了400 輛汽車，由圖6 可知，在12 h 內，停車場完成的累積?？繑抵饾u增加，并最終趨于平穩(wěn)。由于車輛規(guī)模較大，所以空閑車位數量無法滿足停車需求，這時各停車場的停車占用率是否平衡對性能影響較大。

圖6 累積?？繑?/p>

MD 策略只考慮了路程因素，選擇距離目的地最近的停車場進行停車，會導致城市中心停車場負載過大，停車效率低，所以性能表現最差。MQT策略考慮排隊等待時間，在一定程度上能夠解決車輛分配的問題，但隨著時間的增加，在距目的地距離的約束下，仍會有停車場車輛趨于飽和，所以最終停靠數沒有明顯提高。而采用預訂機制的RES 和RL 策略能夠明顯地緩解單一停車場過飽和的趨勢，在強化學習的作用下，RL 策略則能更好提高系統(tǒng)停車效率。

3.2.4 停車場占用率評估

由于MD 策略采取就近原則，只選取距離目的地最近的停車場進行停車，并不能起到平衡停車場占用率的作用，所以在本次實驗中不作考慮。而MQT、RES 和RL 策略都能在一定程度上平衡停車場的停車占用率，所以按距離目的地由近到遠的順序依次選取3 個停車場，在場景內有400 輛汽車時，對MQT 策略、RES 策略和RL 策略的性能進行進一步比較。

圖7 顯示的是12 h 仿真結束后3 個停車場的停車占用率情況。

圖7 12 h 后的停車場占用率

可以看到，在MQT 策略中，較近的停車場1 和停車場2 的占用率已達到100%，而停車場3 的占用率只有52%，所以該策略平衡占用率的效果較差。在RES 策略下，3 個停車場的占用率分別為100%、98%和62%，停車場1 和停車場2幾乎已滿，而停車場3 僅使用了2/3 的停車位，這說明采用用戶主導的預約方式仍不能很好地平衡停車場的占用率，用戶更傾向于選擇距離目的地較近的停車場進行停車。但在RL 策略下，3 個停車場的占用率在83%～93%，達到了很好的平衡效果。

4 結論

1）本文在構建停車信息預測模型時，摒棄對停車可用性概率的預測，采用停車預訂的方式對停車時長及旅行目的地進行預設，能夠在一定程度上解決未來停車信息的不確定性，是實現停車誘導策略的前提。

2）結合強化學習方法，對多目標進行處理，以智能化的方式解決停車誘導問題。經與其他策略對比發(fā)現，改進的基于強化學習的場外停車誘導策略在停車總路程、平均消耗時間和累積?？繑捣矫娑季哂忻黠@的優(yōu)勢，并且平衡了停車場的占用率，從全局角度優(yōu)化了停車誘導策略。

3）采用的停車預訂機制雖然能夠很好地解決對未來停車信息預測的問題，但在特殊事件的影響下依然會有所偏差，所以如何能夠更準確地對未來的空閑停車位數量進行預測，是需要解決的重要問題。