張康帥 彭 磊

1(華南理工大學(xué) 機械與汽車工程學(xué)院 廣州 510641)

2(中國科學(xué)院深圳先進(jìn)技術(shù)研究院 深圳 518055)

1 引 言

隨著國內(nèi)小型載客汽車和私家車保有量的快速增長，現(xiàn)有的停車設(shè)施愈發(fā)難以滿足日益增長的停車需求。為了提高現(xiàn)有停車設(shè)施的利用率，北京、上海、成都、深圳等城市均已提出建設(shè)城市級停車誘導(dǎo)系統(tǒng)(City-wide Parking Guidance Systems，CPGS)的計劃。CPGS 通過向駕駛員提供其收集處理的城市各處停車場實時信息，減少駕駛員搜尋停車場的時間以提高停車設(shè)施和道路的利用率[1]。CPGS 可視為一種能夠響應(yīng)城市中駕駛員在任意位置、任意時間停車需求的信息物理(Cyber-Physical)搜索引擎[2]。由于城市中車輛、停車場眾多且停車需求頻繁，因此為 CPGS 設(shè)計良好的信息結(jié)構(gòu)從而提升其工作效率具有較大的實際意義。

傳統(tǒng) CPGS 對收集數(shù)據(jù)的處理方式通常是簡單地根據(jù)空車位率將停車場狀態(tài)分為充足、中等、短缺等狀態(tài)[3]，沒有對數(shù)據(jù)進(jìn)行深度挖掘，或根據(jù)一些其他指標(biāo)對停車場進(jìn)行定量評估[4]，故其所得的結(jié)果通常是靜態(tài)的。這些方法通常著眼于單個停車場，忽略了不同停車場之間的相互影響。受 Google 提出的網(wǎng)頁排序算法 PageRank[5]的啟發(fā)，在前期研究中，我們將城市中的所有停車場建模為以停車場為節(jié)點、連接它們的道路為邊的復(fù)雜網(wǎng)絡(luò)[6]。其中停車場的一些靜態(tài)參數(shù)(如容量和價格等)，被用于對初始服務(wù)能力進(jìn)行建模，而停車巡游行為被建模為車輛在停車場之間轉(zhuǎn)移的概率，即網(wǎng)絡(luò)的動力學(xué)特性，該模型被命名為 ParkingRank[7]。起初因為沒有考慮可用車位數(shù)的變化對網(wǎng)絡(luò)動力學(xué)的影響，此時模型是靜態(tài)的；后來通過導(dǎo)入可用車位數(shù)變化的相關(guān)數(shù)據(jù)對其進(jìn)行了改進(jìn)，使其可以根據(jù)停車場的靜態(tài)參數(shù)、實時可用車位數(shù)和停車場之間的空間關(guān)系，對停車場實時服務(wù)能力進(jìn)行定量評估并據(jù)此對停車場進(jìn)行排序[8]。

為了使 ParkingRank 算法可以與現(xiàn)有信息系統(tǒng)集成起來，本文在該主題上做了進(jìn)一步的工作。其中的關(guān)鍵在于使人們(尤其是城市管理人員)可以更直觀、高效地去理解 ParkingRank 計算結(jié)果的可視化方法，在此基礎(chǔ)上人們可以制定更合理的計劃和管理決策。由于停車場與連接它們的道路共同構(gòu)成了地理空間網(wǎng)絡(luò)，因此首選的可視化方案是覆蓋模型。其中該模型廣泛應(yīng)用于與地理空間相關(guān)的應(yīng)用。覆蓋模型通過興趣點(Point of Interest，POI)的 Voronoi 圖(或 Thiessen 多邊形)[9]無縫且不重疊的覆蓋研究范圍，以可視的方式顯示一些有用的信息，如 POI 的密度、各 POI 的服務(wù)區(qū)域等，從而可以快速清晰地傳遞信息。同時，在此基礎(chǔ)上還可以進(jìn)行更深入的研究，如新站點選址和 POI 網(wǎng)絡(luò)的健壯性評估。相較現(xiàn)有信息系統(tǒng)中，以空車位率或車位使用率為指標(biāo)的熱力圖[10]來展示大規(guī)模停車場實時信息的方式，覆蓋模型可以提供更豐富的信息。

Voronoi 圖是一種空間分割算法，可以根據(jù)給定的生成點將空間劃分為互斥的多邊形區(qū)域。它具有區(qū)域內(nèi)任意點到該區(qū)域生成點的距離比到其他區(qū)域生成點的距離都短的特點，這種距離通常采用歐式距離衡量，有時也會使用曼哈頓距離。由于這一特性，這些區(qū)域是表示 POI 服務(wù)或工作區(qū)域的理想方式，如通信基站[11]、地鐵站[12]或醫(yī)院[13]的服務(wù)區(qū)域，且在此基礎(chǔ)上可進(jìn)一步研究選址優(yōu)化，進(jìn)行健壯性分析等[14-15]。

原始的 Voronoi 圖僅根據(jù)生成點的位置坐標(biāo)來計算多邊形。但是，停車場的實際情況較為復(fù)雜，這是因為停車場的服務(wù)能力總是隨可用車位數(shù)的變化而變化，甚至受到周圍停車場的影響。因此，若要為每個停車場計算合適的多邊形，不僅要考慮停車場的位置，還要考慮影響服務(wù)能力的因素，并將其映射到距離值上。停車場的服務(wù)區(qū)域應(yīng)是動態(tài)的，代表停車場服務(wù)能力的多邊形應(yīng)根據(jù)其服務(wù)能力的變化而放大或縮小，且被約束在合適區(qū)域內(nèi)，使其符合停車場服務(wù)區(qū)域的實際情況。因此，本文提出了一種帶邊界約束的加權(quán) Voronoi 圖來滿足停車場網(wǎng)絡(luò)的要求。

加權(quán) Voronoi 圖通過使用加權(quán)歐式距離來增加與地理空間無關(guān)因素的影響。其中，加權(quán) Voronoi 圖通常使用基于柵格的方法構(gòu)建[16]。該方法首先將平面離散為點，然后根據(jù)定義直接構(gòu)建。另一種更準(zhǔn)確快速的方法是拓?fù)浏B加法，可以生成乘法加權(quán)的 Voronoi 圖[17]。拓?fù)浏B加法基于 Apollonius 圓，它是到兩個固定點的距離保持恒定比率的點的軌跡，生成點對應(yīng)的多邊形區(qū)域可以通過其與所有比其權(quán)重大的生成點形成的 Apollonius 圓的交集，減去與比其權(quán)重小的生成點形成的所有 Apollonius 圓來獲得。

本文需要解決的另一個問題是大型停車場網(wǎng)絡(luò)的高效計算。與 PageRank 一樣，ParkingRank 也是基于圖的計算，圖的大小將極大地影響計算效率。對于擁有超過 10 000 個停車場的城市(在如今的中國非常普遍)，直接使用 ParkingRank 算法計算每個停車場的服務(wù)能力是一項非常耗時的工作。在本文中，我們嘗試通過聚類分割整個城市的停車場網(wǎng)絡(luò)，從而加快計算速度，使實現(xiàn)城市級停車場的動態(tài)覆蓋變得可行。

2 城市級停車場服務(wù)能力覆蓋模型

2.1 停車場服務(wù)能力的量化

本文中，停車場服務(wù)能力的量化通過 ParkingRank 算法[7-8]實現(xiàn)，在這里僅對其關(guān)鍵步驟進(jìn)行介紹。首先，根據(jù)公式(1)計算每個停車場的初始服務(wù)能力，即當(dāng)停車場都為空且不考慮不同停車場之間的相互作用時的服務(wù)能力。

2.2 邊界約束加權(quán) Voronoi 圖

停車場的服務(wù)能力將作為可視化過程中加權(quán) Voronoi 圖的加權(quán)項。但是，根據(jù)加權(quán) Voronoi 算法，如果某點的權(quán)重遠(yuǎn)大于其相鄰點，則對應(yīng)的 Apollonius 圓會擴大到包圍其相鄰點。這種情況對于某些對象也許是合理的，但對于停車場，這將導(dǎo)致大型停車場周圍的一些小型停車場被嵌入大型停車場的服務(wù)區(qū)域中，從而失去自己的服務(wù)區(qū)域。從停車引導(dǎo)的角度看，這些小型停車場對于其附近車輛都是不可見的，即 CPGS 會引導(dǎo)所有車輛前往少數(shù)大型停車場，這與司機選擇就近停車的現(xiàn)實情況不符。

為了解決這個問題，停車場服務(wù)區(qū)域的邊界應(yīng)被限制在適當(dāng)范圍內(nèi)，以避免侵入較弱鄰居的邊界并最終將其包圍。本文在 Delaunay 三角剖分的幫助下改進(jìn)了加權(quán) Voronoi 圖。由于 Delaunay 三角剖分最大化了最小角，避免創(chuàng)建細(xì)長的三角形，使 Delaunay 三角形“形狀規(guī)則”，且具有唯一性(任意 4 點不能共圓)。

其中，a、bx、by和c由以下行列式計算：

由于 Delaunay 三角剖分的性質(zhì)確保了停車場組成的 Delaunay 三角形中不會嵌入其他停車場，因此，如果將 Apollonius 圓的變化限制在該三角形內(nèi)，那么就可以解決原始加權(quán) Voronoi 圖停車場服務(wù)區(qū)域包圍的問題。

對于任意停車場，如果假定停車場p和pi、pj組成一個 Delaunay 三角形q，那么 3 個停車場的服務(wù)能力分別為PRp、PRi和PRj。則停車場p在 Delaunay 三角形q中所占的面積Poly(p,q) 為：

圖1 使用邊界約束加權(quán) Voronoi 圖進(jìn)行覆蓋的示例Fig. 1 Example of coverage by boundary constrained weighted Voronoi diagram

2.3 將覆蓋范圍擴展至城市級停車場網(wǎng)絡(luò)

圖2 使用 MeanShift 進(jìn)行停車場聚類的示例Fig. 2 Example of clustering the parking lots by MeanShift

圖 2 為一個聚類過程的示例。其中，圖 2(a)為實際的停車場位置，每個點代表一個停車場，點的大小代表其初始服務(wù)能力的強弱。圖 2(b)為聚類過程，其中“停車場”開始移至高密度位置，總體而言，小型停車場傾向于移至較大型停車場；聚類完成后，停車場將匯聚到地圖上的不同點，如圖 2(c)所示。圖 2(d)將聚類中的停車場重新映射到其真實位置，同一聚類中的停車場采用相同的顏色表示。

至止，整個城市中的停車場組成的網(wǎng)絡(luò)已經(jīng)被劃分為許多子網(wǎng)絡(luò)，這些子網(wǎng)絡(luò)由相對較少的停車場組成。通過在每個子網(wǎng)絡(luò)上并行應(yīng)用服務(wù)能力量化和可視化算法，可以在合理時間內(nèi)實現(xiàn)整個城市范圍內(nèi)停車場的覆蓋。在這種情況下，停車場服務(wù)能力量化和可視化的時間復(fù)雜度約為 ，其中 是子網(wǎng)絡(luò)中停車場的平均數(shù)量。若 足夠小(如小于20)，則計算效率將大幅提高。

3 仿真與分析

3.1 仿真場景

深圳是中國最發(fā)達(dá)的城市之一，擁有超過 300 萬輛汽車和約 13 000 個停車場。本次仿真選擇了深圳市中心城區(qū)之一的羅湖區(qū)，共涉及超過 1 000 個停車場。如果直接對如此大量的停車場進(jìn)行服務(wù)能力量化和可視化，那么計算所需時間過長，無法反映整個城市停車場服務(wù)能力的實時變化。因此，本文嘗試使用第 2 小節(jié)提出的方法來進(jìn)行計算。此次仿真中共涉及 1 096 個停車場，表 1 是詳細(xì)的停車場數(shù)據(jù)表。其中，位置為停車場的 GPS 坐標(biāo)；價格為停車首小時收費；可用車位率是可用停車位數(shù)與總停車位數(shù)的比值，其采樣間隔為 15 min。

3.2 仿真與分析

首先，使用聚類的方法將 1 096 個停車場拆分成多個子網(wǎng)絡(luò)，以減輕后續(xù)的計算壓力?？紤]到司機通常將車停在目的地附近步行幾分鐘可達(dá)的停車場內(nèi)，因此可以將超參數(shù)dnbhd設(shè)置為與此相關(guān)的值。正常成年人 3～4 min 可以走 300 m，故在本次仿真中，dnbhd被設(shè)置為 220 m，這使得聚類中的任何停車場到其最近停車場的歐氏距離不超過 220 m，同時每個子網(wǎng)中停車場數(shù)目不會太多(如超過 50 個)。

如圖 3 所示，當(dāng)聚類完成時，1 096 個停車場被分為 141 個子網(wǎng)，每個子網(wǎng)具有 1～29 個停車場，且每個聚類的服務(wù)區(qū)域以不同顏色進(jìn)行區(qū)分。其中每個停車場聚類的服務(wù)區(qū)域，是使用初始服務(wù)能力為加權(quán)得到的聚類中各停車場服務(wù)區(qū)域的并集。圖 3 的右下部分是圖中藍(lán)色矩形包圍區(qū)域的放大，其中有 4 個小型停車場網(wǎng)絡(luò)。

因為每個小型停車場網(wǎng)絡(luò)包含的停車場數(shù)最多為 29 個，相對較少，故可以直接應(yīng)用服務(wù)能力量化和可視化算法，而不必?fù)?dān)心其計算延遲。

圖 4 是一個小型停車場網(wǎng)絡(luò)，位于圖 3 右下角放大的局部區(qū)域左側(cè)。此小型網(wǎng)絡(luò)包含 11 個停車場，具體分為 3 種類型：ID 編號為 4、5、6、9 的是住宅類停車場，ID 編號為 10、11 的是商業(yè)類停車場，ID 編號為 1、2、3、7、8 的是隸屬于辦公室的停車場。

表1 停車場數(shù)據(jù)詳表Table 1 The detailed carparks data sheet

圖3 1 096 個停車場通過 MeanShift 形成的 141 個聚類Fig. 3 1 096 carparks form 141 clusters by MeanShift

圖4 一個聚類中包含的小停車場網(wǎng)絡(luò)Fig. 4 A tiny carpark network included in a cluster

圖5 停車場網(wǎng)絡(luò)中停車場服務(wù)能力隨時間的變化Fig. 5 Time-varying service capabilities of the tiny carpark network

根據(jù)給定的信息和地理空間關(guān)系(如表 1 所示)，可以基于 ParkingRank 算法來量化該聚類中停車場的服務(wù)能力。圖 5 為圖 4 中 11 個停車場在工作日和休息日的服務(wù)能力變化情況。由于停車場的可用車位數(shù)隨時間改變，因此停車場的服務(wù)能力也隨時間改變。通常情況下，休息日去辦公的人減少，辦公室停車場(ID 編號為 1、2、3、7、8)的服務(wù)能力相較工作日有明顯的提升。

圖6 不同時刻停車場網(wǎng)絡(luò)的可視化覆蓋Fig. 6 Visualized coverage of the tiny carpark network at different moments

此外，可以根據(jù)量化出的服務(wù)能力同步可視化這個停車場網(wǎng)絡(luò)。圖 6 清楚地顯示了停車場服務(wù)區(qū)域隨服務(wù)能力的變化情況。圖 6 分別為午夜、早晨、中午和晚上 4 個典型時刻的可視化效果，相應(yīng)的服務(wù)能力在圖 5 中用紅色垂直點線突出顯示。在午夜(圖 6(a, e))，大多數(shù)人們在家中睡覺，汽車聚集在居民樓的停車場(ID 編號為 4、5、6、9)中，可用停車位的短缺使其服務(wù)能力大大降低，而公共場所停車場在此時有足夠的停車位，從而具有較強的服務(wù)能力。因此，住宅類停車場的服務(wù)區(qū)域看起來比其他區(qū)域小得多。類似地，當(dāng)人們?nèi)マk公室(圖 6(b, c, f, g))或在晚上娛樂(圖 6(d, h))時，停車場的服務(wù)區(qū)域?qū)⒏鶕?jù)他們服務(wù)能力的變化而不斷變化，同時停車場服務(wù)區(qū)域的連通性在整個過程中保持良好。此外，由于休息日上班人數(shù)減少、在家休息的人數(shù)增多，辦公室停車場(ID 編號為 1、2、3、7、8)的服務(wù)區(qū)域相較工作日明顯增大。同時，休息日外出娛樂的人數(shù)增多，商業(yè)類停車場(ID 編號為 10、11)爆滿，導(dǎo)致其服務(wù)區(qū)域銳減(對比圖 6(c, g))。顯然，這種覆蓋在停車場網(wǎng)絡(luò)的可視化是合理可行的。

3.3 與現(xiàn)有方案的對比

Wang 和 Shi[12]利用基于最短距離、最小時間等參數(shù)的 Voronoi 圖來劃分地鐵站的服務(wù)區(qū)域，由于得到的服務(wù)區(qū)域是靜態(tài)的，所以這種方法僅適用于服務(wù)能力相對穩(wěn)定且沒有顯著差異的 POI。而本文所提出方法得到的服務(wù)區(qū)域是動態(tài)的，可以表現(xiàn)停車場服務(wù)能力隨可用車位數(shù)變化而變化的性質(zhì)。曹昉等[19]提出一種變權(quán)重加權(quán) Voronoi 圖，根據(jù)變電站負(fù)載率和供電半徑動態(tài)調(diào)整權(quán)重，動態(tài)地劃分城市電網(wǎng)中變電站的供電范圍，但這種權(quán)重調(diào)整方式利用了變電站間隔較遠(yuǎn)且分布較為均勻的性質(zhì)；而本文提出的方法利用了停車場服務(wù)區(qū)域主要受相鄰?fù)＼噲鲇绊懙奶攸c，為密集且分布不均的 POI 服務(wù)區(qū)域劃分提供了方案。此外，前述提到的兩種改進(jìn) Voronoi 圖均需使用基于柵格的方法構(gòu)建，計算量較大，不適合需要實時更新的場合的應(yīng)用。

本文提出的方法與傳統(tǒng)加權(quán) Voronoi 圖[9]的比較如圖 7 所示。圖中展示的是根據(jù)停車場初始服務(wù)能力分別應(yīng)用原始加權(quán) Voronoi 圖和本文方法的覆蓋結(jié)果，在沒有邊界限制的情況下(圖 7(a))，一些服務(wù)能力較強的停車場可以任意擴大服務(wù)區(qū)域，并最終包圍臨近停車場。在這種情況下，由于許多小型停車場變成了孤立的節(jié)點，僅與較強的節(jié)點有連接，使網(wǎng)絡(luò)的連通性大大受損。相反，本文方法(圖 7(b))的結(jié)果中每個停車場的邊界都是由相鄰的停車場而不是最強大的停車場決定的，整個停車場網(wǎng)絡(luò)的連通性較好，更符合實際情況。

圖7 原始加權(quán) Voronoi 圖和邊界約束加權(quán) Voronoi 圖覆蓋效果的比較Fig. 7 Coverage comparison between original weighted and boundary constrained weighted Voronoi

此外，在本模型中，由于預(yù)先將停車場分入不同的子網(wǎng)絡(luò)，減小計算量的同時實現(xiàn)后續(xù)過程在各聚類上并行，使得用各停車場服務(wù)區(qū)域動態(tài)覆蓋整個城市成為可能。

4 總結(jié)與展望

本文提出了一個可視的城市級停車場動態(tài)覆蓋模型。首先，借助 MeanShift 算法將整個城市中的停車場分入多個聚類，形成許多小型停車場網(wǎng)絡(luò)。然后，使用 ParkingRank 算法量化了每個小型停車場網(wǎng)絡(luò)內(nèi)停車場的服務(wù)能力。最后，通過邊界約束加權(quán) Voronoi 圖將量化的停車場服務(wù)能力映射到地理空間上，形成可視服務(wù)區(qū)域，由于每個停車場的邊界都是由相鄰的停車場而不是最強大的停車場決定的，使得網(wǎng)絡(luò)連通性比原始加權(quán) Voronoi 圖更具優(yōu)勢。在仿真部分，本文建立了包含深圳市羅湖區(qū)所有停車場的動態(tài)覆蓋實例，這是首次建立包含城市中所有停車場的大規(guī)模動態(tài)覆蓋模型，仿真結(jié)果表明了本模型的合理性和可理解性。

可視的城市級停車場動態(tài)覆蓋涉及復(fù)雜網(wǎng)絡(luò)、交通流等多方面的理論、方法和技術(shù)，本文模型在以下幾個方面還存在一些限制與不足，需要做進(jìn)一步的工作。例如，在停車場網(wǎng)絡(luò)動力學(xué)中并沒有考慮實時交通狀況對司機停車巡游行為的影響。此外，本文在停車場聚類過程中直接使用了不同停車場之間的歐式距離，在未來工作中將考慮使用道路距離或改用其他聚類方法并對聚類效果進(jìn)行評估。