陳立偉，董睿婷，王桐

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

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

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

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

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

1 停車信息預(yù)測模型

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

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

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

圖1 V2R 通信架構(gòu)

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

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

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

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

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

1.2 預(yù)測模型

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

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

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

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

即可得到停車場Pj的服務(wù)量pj：

式中p0為實時獲取的停車場當(dāng)前服務(wù)量。

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

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

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

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

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

3) 當(dāng)l＞1且uj+l＞mj時：

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

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

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

2 強化學(xué)習(xí)停車誘導(dǎo)策略

2.1 MDP 下的停車誘導(dǎo)模型

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

圖2 MDP 的基本框架

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

2.1.1 狀態(tài)空間S

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

2.1.2 動作空間A

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

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

2.1.3 狀態(tài)轉(zhuǎn)移函數(shù)

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

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

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

2.1.4 獎勵函數(shù)R

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

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

2.2 基于Q-learning 的停車誘導(dǎo)策略

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

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

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

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

采用Q-learning 的停車誘導(dǎo)算法流程如下：

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

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

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

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

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

6）s←s′，重復(fù)步驟2）。

3 實驗結(jié)果及分析

在本節(jié)中，基于One 仿真平臺進行模型搭建，在模型下應(yīng)用本文算法，完成基于強化學(xué)習(xí)的場外停車誘導(dǎo)策略（RL），并將其與基于最短步行路程（minimum distance，MD）[15]策略、基于最短排隊時間（minimum queue time，MQT）[16]策略、基于預(yù)約（reservation based，RES）[17]策略進行比較，從總路程、平均消耗時間、累積?？繑?shù)以及停車場占用率方面對算法性能進行有效的評估。

3.1 模型搭建

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

圖3 場外停車誘導(dǎo)場景

3.2 實驗評估

3.2.1 停車總路程評估

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

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

圖4 不同車輛數(shù)下的平均總路程

3.2.2 停車總時間評估

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

圖5 不同車輛數(shù)下的平均消耗時間

3.2.3 累積停靠數(shù)評估

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

圖6 累積?？繑?shù)

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

3.2.4 停車場占用率評估

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

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

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

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

4 結(jié)論

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

2）結(jié)合強化學(xué)習(xí)方法，對多目標進行處理，以智能化的方式解決停車誘導(dǎo)問題。經(jīng)與其他策略對比發(fā)現(xiàn)，改進的基于強化學(xué)習(xí)的場外停車誘導(dǎo)策略在停車總路程、平均消耗時間和累積?？繑?shù)方面都具有明顯的優(yōu)勢，并且平衡了停車場的占用率，從全局角度優(yōu)化了停車誘導(dǎo)策略。

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