基于分布式架構(gòu)的停車位分配算法*

龐華健， 陳觀林,， 徐 煌

(1.常州大學(xué) 信息科學(xué)與工程學(xué)院，江蘇 常州 213164；2.浙江大學(xué)城市學(xué)院 計算機(jī)與計算科學(xué)學(xué)院，浙江 杭州 310015)

0 引 言

當(dāng)前，泊車位難尋已成為大型城市通病[1～3],設(shè)計切實可行且有效的停車機(jī)制可以在很大程度上緩解國內(nèi)城市交通壓力。文獻(xiàn)[4]介紹了智能車輛的發(fā)展與技術(shù)研究現(xiàn)狀，而優(yōu)化公共停車資源也是智能交通建設(shè)不可或缺的一環(huán)。文獻(xiàn)[5]中基于GPS的車速傳感器開發(fā)，為智能交通系統(tǒng)引入民用GPS技術(shù)提供了有效嘗試。文獻(xiàn)[6]設(shè)計了一種基于智能手機(jī)的尋泊軟件，系統(tǒng)功能上基本滿足用戶需求，但使用貪心算法來實現(xiàn)泊車位的分配，無法規(guī)避多個用戶目標(biāo)點重復(fù)的問題。文獻(xiàn)[7]設(shè)計了一種城市道路車輛智能尋泊與計費系統(tǒng)，采用地磁感應(yīng)設(shè)備實時收集路邊停車位信息，但不具備優(yōu)化泊車資源的算法體系。文獻(xiàn)[8]提出了一種可用于停車場誘導(dǎo)系統(tǒng)的基于ARM傳感器的車輛檢測算法。文獻(xiàn)[9]中闡述了一種基于最小-最大社會公平性的半分布式車位分配方法，利用了雙重分解技術(shù)和子梯度方法，完成了算法的半分布式實現(xiàn)。上述已有的研究與算法設(shè)計都對分布式技術(shù)與智能交通進(jìn)行了可行性嘗試，但仍然存在一些不足，不能良好適用于中國目前的交通大環(huán)境中。

本文基于線上的分布式平臺，提出了一種基于分布式的停車位分配算法，經(jīng)仿真驗證，對于高供需比環(huán)境下的峰值泊車請求能夠快速求得占優(yōu)解集。

1 停車位分配的系統(tǒng)模型與算法原理

1.1 系統(tǒng)總體設(shè)計

停車分配系統(tǒng)在時隙單位內(nèi)采集停車需求，通過路徑規(guī)劃生成用戶距目標(biāo)點附近復(fù)數(shù)停車位的距離，將停車需求匯總成距離矩陣。通過線上分配算法對匯總的矩陣進(jìn)行求解，得到Pareto占優(yōu)解集，選取當(dāng)前最優(yōu)的匹配矩陣并將結(jié)果分發(fā)給用戶終端，智能終端根據(jù)收到的匹配結(jié)果對用戶進(jìn)行導(dǎo)航，停車分配系統(tǒng)結(jié)構(gòu)如圖1所示。

圖1 停車分配系統(tǒng)結(jié)構(gòu)圖

基于圖1中的系統(tǒng)，提出一種基于Spark Streaming的分布式停車位分配算法。根據(jù)時隙內(nèi)用戶當(dāng)前位置與目標(biāo)位置，與可達(dá)停車位的當(dāng)前狀態(tài)等信息，對所以用戶的停車請求進(jìn)行統(tǒng)計、處理和匹配。

1.2 數(shù)據(jù)預(yù)處理

服務(wù)器根據(jù)用戶的當(dāng)前位置與目標(biāo)位置以及可用車位生成車輛Nt={1,2,3,…,Nt}與停車位Mt={1,2,3,…,Mt}之間的映射距離矩陣Dij，dij表示車輛i∈Nt的目的地到停車位j∈Mt的距離。并將所有用戶按停車位編號的順序組成代價矩陣Dij舉例如下

式中i為當(dāng)前的用戶編號，j為停車位編號，∞為對應(yīng)的用戶i與停車位j不可達(dá)。

1.3 算法目標(biāo)

引入二進(jìn)制決策變量xij,i∈Nt,j∈Mt，用來表示停車位的占用狀況，量化表示為

(1)

由決策變量組成的決策矩陣Xij，其特征為每行每列最多只有一個1的滿秩矩陣，在得到距離矩陣Dij后，此最優(yōu)分配問題即可轉(zhuǎn)化為根據(jù)對角線法則求得的滿秩矩陣最小值，即矩陣最小值的問題，即

(2)

1.4 系統(tǒng)模型設(shè)計

假設(shè)有時隙歸一化整數(shù)值t={1,2,3,…}，在每個時間段t的開始，已知有停車位集合Mt={1,2,3,…,Mt}。在時隙t開始時，對一組車輛Nt={1,2,3,…,Nt}進(jìn)行停車位分配，其中，Nt≤Mt。其次，定義了式(1)中的二進(jìn)制決策變量，上述定義中的dij和xij構(gòu)成了距離矩陣Dij和匹配矩陣Xij，二者矩陣相乘即為當(dāng)前匹配下的路徑代價總和，問題可以表示為

(3)

上述約束條件的含義是：每個停車位最多分配一輛車，每輛車都會被分配到一個停車位。

1.5 算法設(shè)計

1.5.1 遺傳算法編碼

遺傳算法基因編碼常用的類型為十進(jìn)制與二進(jìn)制，二進(jìn)制編碼運算快，符合最小字符集原則，但也有漢明距離大，容易陷入局部最優(yōu)的缺點；十進(jìn)制編碼又稱實數(shù)編碼，是遺傳算法中解決連續(xù)參數(shù)優(yōu)化問題時普遍使用的編碼方式，但也存在變異不穩(wěn)定等缺點。本文采用二進(jìn)制矩陣編碼的形式，即滿足約束條件(3)的匹配矩陣，舉例如下此編碼方法易于計算適應(yīng)度以及后續(xù)的交叉遺傳與變異算子的運算，且便于解碼。

1.5.2 個體生成

當(dāng)系統(tǒng)在時隙內(nèi)收集到了一定用戶請求后，通過數(shù)據(jù)預(yù)處理操作操作生成代價數(shù)組，即Dij，根據(jù)Dij的維數(shù)，隨機(jī)生成不同的匹配矩陣，這些匹配矩陣即為個體，舉例如下

1.5.3 適應(yīng)度計算

常見的適應(yīng)度計算包括線性標(biāo)定、動態(tài)線性標(biāo)定、冪律標(biāo)定、對數(shù)標(biāo)定和指數(shù)標(biāo)定等，各種計算方式對應(yīng)的數(shù)據(jù)特征也不同，本算法數(shù)據(jù)特征具有個體數(shù)值大，且個體之間差距較大，更適用于動態(tài)線性標(biāo)定。

產(chǎn)生個體后，每個個體即為一組儲存了車輛與車位的匹配信息的分配矩陣，將個體的分配矩陣與代價矩陣進(jìn)行矩陣乘算操作舉例如下

即可得到對應(yīng)的個體代價矩陣

通過遍歷個體代價矩陣，求得代價總和des(i)，通過動態(tài)線型規(guī)劃的方法，將種群中的最大個體代價值減去當(dāng)前個體代價值，然后加上一個極小數(shù)ξ的k次冪，k代表迭代次數(shù)，以此結(jié)果記作該個體的適應(yīng)度，即

f′=fmax-f+ξk

(4)

1.5.4 交叉算子與變異算子

生成個體后按照隨機(jī)輪賭博的方式進(jìn)行父代選擇，即劃分每個個體到不同的取值范圍，然后生成隨機(jī)數(shù)，將隨機(jī)數(shù)所在范圍的個體選作一個父代個體，重復(fù)操作直至父代個體數(shù)達(dá)到總?cè)萘浚e例見表1。

表1 個體代價及其適應(yīng)度

如表1中所示，個體適應(yīng)度總和為112，則在1～112之間取隨機(jī)整數(shù)，若取得整數(shù)在[1,30]則添加一個1號個體到父代群體中，若取得整數(shù)在[31,45]則添加一個3號個體到父代群體中，以此類推。

在選出父代個體后，進(jìn)行交叉算子運算。交叉運算時，選自同一個體的父代不進(jìn)行交叉運算。父代個體的每行遺傳信息以五成的概率作為子代的遺傳信息，生成子代個體直到子代個體數(shù)目達(dá)到父代個體數(shù)目。

當(dāng)子代個體產(chǎn)生后，如果個體內(nèi)有不符合分配矩陣約束條件的匹配信息行，則尋找其他可行的匹配信息進(jìn)行替代，舉例如下

隨機(jī)變異算子：在產(chǎn)生新個體的每一行匹配信息時，采取1 %的概率的隨機(jī)變異，將該行改為滿足約束條件的其他匹配信息。

學(xué)生成績的好壞，跟他的聽課效率是密不可分的。而聽課也要講究方法。教師要引導(dǎo)學(xué)生明確聽課的重要性，聽課要專心致志，邊聽邊思考，前后聯(lián)系，不懂就問。同時還要將自己所聽到的信息加以分析、歸納、整理、記錄，這樣才能更好地記憶與復(fù)習(xí)。

1.5.5 輸出條件

通過貪心算法求得無約束條件下的最小代價和Des(min)，若當(dāng)前種群內(nèi)最優(yōu)個體達(dá)到最小代價Des(min)的水平，則輸出最優(yōu)個體作為最優(yōu)解。當(dāng)個體的適應(yīng)度達(dá)到預(yù)期或無變化時，輸出個體為Pareto占優(yōu)解集。

2 算法實現(xiàn)

2.1 算法流程

1)收集時隙內(nèi)用戶的停車請求并編號，將用戶編號與對應(yīng)的距離信息存儲至服務(wù)器數(shù)據(jù)庫中。

2)按照用戶和停車位編號生成代價數(shù)組Dij，記不可達(dá)停車位為∞。

3)隨機(jī)生成滿足約束條件的個體，若匹配信息不滿足約束條件則重新生成。

4)通過式(4)計算當(dāng)前種群內(nèi)個體的適應(yīng)度，并通過輪盤賭博選出父代個體，選出的父代個體數(shù)量與當(dāng)前種群容量一致。

5)執(zhí)行交叉與變異操作生成新的子代個體，直到生成的子代個體數(shù)量達(dá)到父代個體數(shù)量。

2.2 算法的分布式實現(xiàn)

遺傳算法并行運行框架中的Map與Reduce階段具體流程如下：

Map階段：將個體矩陣信息輸入到線程，通過輪盤賭博選出父代并將父代進(jìn)行Shuffling混洗操作。此階段輸入為分配到該節(jié)點的若干個個體信息，輸出為〈id,(i,des(i),d(i))〉，其中作為key值的id為個體的百位與十位數(shù)值，value值由個體編號，個體適應(yīng)度以及個體的矩陣信息組成。

Reduce階段：輸入為具有同一id節(jié)點編號的鍵值對〈id,(i,des(i),d(i))〉。通過判斷節(jié)點上是否有滿足輸出條件的個體或種群，若滿足則合并輸出，不滿足則進(jìn)行交叉遺傳和變異操作，生成新的個體，新的個體id與編號繼承自父代，將子代個體保存進(jìn)新的個體匹配矩陣中，作為Map階段迭代的輸入值。并行運行框架如圖2所示。

圖2 遺傳算法并行運行框架

3 算法仿真

3.1 實驗數(shù)據(jù)獲取

實驗數(shù)據(jù)采用2017年6月14日至20日的杭州市下城區(qū)的某商業(yè)中心停車場記錄，數(shù)據(jù)存儲量共2.2 G，數(shù)目總計1 萬余條。

3.2 仿真結(jié)果分析

鑒于停車需求與車位供給的不穩(wěn)定性，對采集的停車數(shù)據(jù)進(jìn)行了統(tǒng)計與分析，得到了需求數(shù)量與時間的關(guān)系，節(jié)假日與工作日的泊車需求相比較，差異在于節(jié)假日的泊車需求在時間段上分布更為均勻，而工作日則更集中在早晚高峰時段，共同點是需求數(shù)量在凌晨至6時許達(dá)到谷值，而在9時與18時左右達(dá)到峰值。

需求數(shù)量對于算法的運算量也有一定的影響，總的來說，需求量越大，生成的矩陣維度越高，個體的代價值也隨之增加。影響個體代價均值的因素除了需求數(shù)量，還包括供需比，當(dāng)供需比越大，則滿足停車請求的車位越少，以10個請求為例，供需比與個體代價之間的關(guān)系如圖3(a)所示。由圖可知，供需比與生成個體的代價均值之間呈指數(shù)型上升，并在供需比大于0.5時上升速度顯著加快。

在仿真時可以通過控制輸入的代價矩陣維度來模擬供需比和需求數(shù)量的改變。取供需比0.25，需求數(shù)量為100生成代價矩陣并代入算法。在每一代計算適應(yīng)度時，計算個體代價均值，輸出變化曲線如圖3(b)所示。

這100個需求在無約束條件下的最小值為186，與仿真算法得到的Pareto占優(yōu)解集相近。在需求數(shù)不變的情況下調(diào)整供需比，運行仿真算法與有約束條件的貪心算法進(jìn)行比較，得到對比曲線如圖3(c)所示。

圖3 仿真結(jié)果

由上述曲線可知，在低供需比條件下，貪心算法具有明顯優(yōu)勢，但當(dāng)處于高峰時段時，需求量增加、供需比升高則會導(dǎo)致貪心算法的運算時間呈指數(shù)型上升，遠(yuǎn)超遺傳算法的運算量，甚至可能無法求得占優(yōu)解集。

3.3 算法的分布式實現(xiàn)

按照圖2中設(shè)計的分布式流程框架，進(jìn)行算法的分布式實現(xiàn)，參數(shù)設(shè)置為100個請求，供需比0.75。將遺傳算法進(jìn)行分布式運算后，各線程的變化趨勢基本一致，但迭代次數(shù)增加了約50 %，且部分線程在收斂之后出現(xiàn)了代價回升的現(xiàn)象，這些不足主要是由于各個線程的Reduce階段相對獨立，無法在種群之間進(jìn)行基因交流，因此,需要引進(jìn)精英策略。精英策略是指在Map階段通過計算適應(yīng)度，選出優(yōu)秀個體，將其鍵值對中的key改為其他線程的key，以此達(dá)到種群間優(yōu)秀個體及其基因的交流。通過運行改進(jìn)之后的分布式NSGA-II算法，得到了每一代種群的代價均值與迭代次數(shù)曲線如圖4所示。

圖4 分布式NSGA-II代價變化曲線

其算法收斂代數(shù)基本能達(dá)到預(yù)期。本文所述的貪心算法、NSGA算法與分布式運行NSGA算法、NSGA-II算法的時間分別為31.2，18.6，5.47，3.58。

4 結(jié) 論

NSGA算法能在較高的供需比條件下更快提供可靠的匹配結(jié)果。在分布式環(huán)境下，NSGA算法在運算時間上取得了相當(dāng)?shù)奶岣撸⑶乙刖⒉呗灾蟮腘SGA-II基本達(dá)到了預(yù)期收斂速度。