Parking Guidance Algorithm Based on Time-dependent Shortest Path

李　偉1　余　森1　王　偉2

(河南工業(yè)職業(yè)技術(shù)學(xué)院計算機工程系1，河南 南陽　473000；西安電子科技大學(xué)通信工程學(xué)院2，陜西 西安　710071)

基于時間最短路徑的停車場車位引導(dǎo)算法

Parking Guidance Algorithm Based on Time-dependent Shortest Path

李偉1余森1王偉2

(河南工業(yè)職業(yè)技術(shù)學(xué)院計算機工程系1，河南 南陽473000；西安電子科技大學(xué)通信工程學(xué)院2，陜西 西安710071)

摘要：針對停車場管理系統(tǒng)中存在的車位引導(dǎo)問題，在研究場內(nèi)道路網(wǎng)絡(luò)特征的基礎(chǔ)上建立加權(quán)網(wǎng)絡(luò)模型；以停車時間最短的路徑作為最佳車位確定準則，結(jié)合Dijkstra算法改進停車引導(dǎo)模型，對系統(tǒng)進行尋優(yōu)。仿真結(jié)果表明，基于時間最短路徑的引導(dǎo)算法所選的最優(yōu)車位更符合實際，停車平均時間最短，是一種尋求最優(yōu)路徑的有效算法。

關(guān)鍵詞：車位引導(dǎo)時間最短路徑Dijkstra算法智能交通系統(tǒng)停車管理靜態(tài)交通

Abstract：Aiming at the parking guidance issue existing in parking lot management system, on the basis of the network features of the site road of parking lot, the weighted network model is established. With the time-dependent shortest path as the determine criterion for the best parking space, the parking guidance model is improved by combining Dijkstra algorithm, the system is optimized. The simulation results indicate that the best parking space selected by the guidance algorithm based on time-dependent shortest path is more realistic, the average parking time is shortest; this is an effective algorithm for finding the optimal path.

Keywords：Parking guidanceTime-dependent shortest pathDijkstra algorithmIntelligent transportation systemParking managementStatic traffic

0引言

近年來,隨著機動車數(shù)量的井噴式增長，交通情況急劇惡化，停車位日益緊缺的問題在大中城市尤為嚴重。交通管理部門紛紛采取措施，新建地下停車場、立體式車庫，開辟道路兩側(cè)夜間停車位，意圖構(gòu)造全方位停車設(shè)施，減緩部分停車難的問題。然而據(jù)統(tǒng)計,在已經(jīng)投入使用的停車設(shè)施中，還存在效率低下的現(xiàn)象[1]。如何運用科技手段對停車場加以改進,使其充分發(fā)揮停車潛力，已成為交通管理部門和科研工作者關(guān)心的問題。車位引導(dǎo)系統(tǒng)就是其中重要的一項技術(shù)，它通過向駕駛員提供到達目標車位的最優(yōu)路徑來引導(dǎo)車輛行駛，縮短車輛在停車場內(nèi)的尋泊時間，減少交通擁堵，提高停車效率。

1停車場車位引導(dǎo)系統(tǒng)

停車場車位引導(dǎo)系統(tǒng)本質(zhì)上是圖論中的求解最優(yōu)路徑問題。目前對最優(yōu)路徑問題的研究有很多，Dijkstra算法[2]是其中的經(jīng)典方法，國內(nèi)外學(xué)者對此進行了很多的研究和改進。張渭軍[3]提出了從起點和終點分別用二叉樹按其方向性進行搜索的雙向Dijkstra算法，以此節(jié)省計算時間。文獻[4]對Dijkstra算法的存儲結(jié)構(gòu)進行改進，采用多重鄰接表來構(gòu)建無向圖，優(yōu)化構(gòu)建無向圖和求解最短路徑問題的時間復(fù)雜度。彭紅星[5]根據(jù)停車場路網(wǎng)的實際情況，將車位節(jié)點和路口節(jié)點區(qū)分開,采用雙層搜索方法，減少搜索點個數(shù)。

通過實地調(diào)查研究發(fā)現(xiàn)，提高停車場效率的關(guān)鍵，在于每一輛車都能夠以最短的時間停泊，即尋找停車時間最短的車位要比停車距離最短的車位更為重要?；谏鲜隹紤]，本文設(shè)計了一種基于時間最短路徑(time-dependent shortest paths,TSP)的停車場車位引導(dǎo)系統(tǒng)。結(jié)合Dijkstra算法進行車位誘導(dǎo)，系統(tǒng)能夠減少車輛尋泊時間，提高停車泊位利用率，促使停車設(shè)施利用平衡化。

2時間最短路徑的內(nèi)涵

停車最短路徑，最直觀的是從停車場入口位置到目標車位距離最短的路徑，一旦停車場建好，這種路徑就是靜態(tài)不可變的。然而現(xiàn)實生活中，由于停車場內(nèi)道路交通強度是時變的，不同時間段行駛在道路上的車輛數(shù)目可變，兩點間距離最短并不代表行駛時間最短。當最短路徑車輛較多、出現(xiàn)擁堵時，路程長的路徑反而可能耗時較短，因此最優(yōu)路徑必須考慮到實時的交通信息[6]。綜合上述兩個方面的因素選擇的時間最短路徑，才是滿足實際需要的最佳路徑。所以設(shè)計停車引導(dǎo)系統(tǒng)時還要考慮到車輛分流問題，在進出停車場的車流高峰時期對車輛進行分流，能夠極大地提高停車場效率。

圖1為某停車場車位分布圖，其中，點P0、E分別為停車場入口和出口，C1~C8為交叉路口節(jié)點，P1~P12為空閑車位。

當某一較短時間段內(nèi)駛?cè)胪＼噲龅能囕v較多時，車位引導(dǎo)算法如果僅考慮選擇距離入口最近的車位，車輛將會在圖中C5-C1、C5-C6區(qū)間形成排隊現(xiàn)象，而其他區(qū)域出現(xiàn)無車的狀況。這種場內(nèi)相關(guān)道路局部擁堵的情況是停車場要極力避免的，因此需要根據(jù)停車場內(nèi)部交通組織布局，合理分散交通流。以圖1為例，某時刻同時駛?cè)氲能囕v可以分別按照C5-C1-C2-C3-C4、C5-C6-C2-C3-C4、C5-C6-C7-C3-C4、C5-C6-C7-C8-C4四條路徑行駛，充分利用停車場的所有停車位，避免車輛刮蹭等交通事故的出現(xiàn)。

另外，某一時間段內(nèi)不但有車輛駛?cè)胪＼噲?，同時也有車輛駛離，但是大多數(shù)停車場出口和入口是分離的，雙向行駛的車輛互不干擾，且駕駛?cè)藛T根據(jù)經(jīng)驗很容易找到出口，所以不需要對出場車輛進行引導(dǎo)。

3停車場通行規(guī)則模型

交通網(wǎng)絡(luò)分析往往要建立抽象的計算機圖論模型，該模型中最短路徑的查找就是在兩個指定網(wǎng)絡(luò)節(jié)點間找到一個權(quán)重最小的路徑。這里的權(quán)重不僅可以是距離，還可以是時間、費用、容量等其他因素[7]。

停車場路網(wǎng)相對較為簡單，主要由環(huán)路、交叉路口及停車位等節(jié)點組成，可以抽象為一個加權(quán)有向圖G(P,C,T)，如圖2所示。在G(P,C,T)中，P表示停車場路網(wǎng)中的節(jié)點，C表示場內(nèi)有向路段，T是權(quán)重，其值為車輛在道路節(jié)點i和j之間的行駛時間：

(1)

式中：c(i,j)和v(i,j)分別為節(jié)點i到j(luò)之間的距離和行駛速度。

圖2　目標停車位加權(quán)有向圖

4Dijkstra時間最短路徑算法

4.1　權(quán)重的計算

由式(1)可知，圖2中兩個相鄰節(jié)點之間的權(quán)重即車輛在該路段行駛所需要的時間。一般情況下，道路的行駛速度v(i,j)比較穩(wěn)定，且與道路上的機動車數(shù)成反比。車輛數(shù)量越多，道路越擁擠，行駛速度越慢。

設(shè)定車輛在場內(nèi)道路上行駛單位長度需要的時間為Δt，考慮到同一路徑上多個車輛之間的相互影響，定義延遲系數(shù)K。經(jīng)現(xiàn)場實地統(tǒng)計，當一條路徑上有2輛車時，單位長度行駛時間延長至1.9Δt；當一條路徑上有3輛車時，單位長度行駛時間延長至2.7Δt；當一條路徑上的車輛大于4輛時，單位長度行駛時間延長至3.1Δt。即：

(2)

其中：

(3)

4.2　引導(dǎo)算法

基于時間最短路徑的停車場車位引導(dǎo)算法，輸入一個以空閑停車位為節(jié)點的鄰接矩陣AMcost，在鄰接矩陣中以停車場入口P0作為源頂點。用P表示所有空閑停車位節(jié)點集合，鄰接矩陣AMcost中的每一個元素AMcost[i][j]表示有序節(jié)點對(Pi,Pj)之間的權(quán)重。本算法以兩點之間的車輛行駛時間作為權(quán)重，不同于經(jīng)典Dijkstra算法，該權(quán)重是隨著同一時間場內(nèi)環(huán)路上車輛的數(shù)目而時變的[8]，具體變化關(guān)系如式(2)、式(3)所示。若Pi、Pj不相鄰，則將元素AMcost[i][j]置為∞。設(shè)S為已經(jīng)查找到的從P0出發(fā)的最短路徑的節(jié)點集合，任意兩節(jié)點之間的總開銷就是最短路徑經(jīng)過的所有邊的權(quán)重總和。用T表示這些最短路徑的花費值，T[i]表示從源節(jié)點P0出發(fā)到終點Pi的最短路徑的開銷。

算法具體步驟如下。

① 初始化最短路徑集合S及其開銷T，即T[j]=AMcost[0][j]，S={P0}。

② 比較集合S外部各節(jié)點Pi∈P-S，選取其中T[j]最小的節(jié)點Pk，則Pk就是目前求得的一條從P0出發(fā)的最短路徑的終點，并將節(jié)點Pk加入集合S。

③ 更新從P0到Pk最短路徑的開銷值，令：

T[k]=min(T[k],AMcost[j][k])

(4)

④ 重復(fù)步驟②、③，直到有向圖中各節(jié)點均加入集合S，即得出從P0到其余各節(jié)點的時間最短路徑。

5實驗仿真結(jié)果分析

為驗證算法的正確性和有效性，在MicrosoftVisualC++ 6.0環(huán)境下，使用C語言開發(fā)仿真程序進行測試。以圖1所示的停車場車位分布圖為背景，在某一時刻，停車場內(nèi)剩余12個空閑車位，其余車位均已被占用。車輛到達停車場的時間服從泊松分布，道路車流穩(wěn)定，短時間內(nèi)共有6輛機動車順序進入停車場待分配車位。

停車場入口到每個空閑車位的行駛距離如表1所示。表1中，s表示單位長度。

表1　停車場內(nèi)空閑車位與入口的距離

分別編程實現(xiàn)距離最短路徑引導(dǎo)算法(distance-dependent shortest paths,DSP)和時間最短路徑引導(dǎo)算法，這兩種算法中車輛在停車場內(nèi)的行駛距離和消耗時間統(tǒng)計如表2所示。表2中，s也表單位長度。

表2　路徑長度及消耗時間測試數(shù)據(jù)

由表2可知，時間最短路徑引導(dǎo)算法求出車輛行駛路徑長度為64s，所需行駛時間合計為69.6Δt，而傳統(tǒng)的距離最短路徑引導(dǎo)算法求出的車輛行駛路徑長度為53s，所需行駛時間合計為93.0Δt。實驗數(shù)據(jù)表明，改進算法求得的總路徑長度較傳統(tǒng)算法稍遠，但由于車輛分布較為合理，相互之間的延誤時間少，導(dǎo)致路況良好，車流比較順暢，所以所需行駛時間減少了許多。這種方案更能滿足用戶的實際需要，而且引導(dǎo)駕駛者避免擁擠的區(qū)域，選擇車流相對順暢的路段，更能解決停車場內(nèi)交通擁堵問題。

6結(jié)束語

本文利用基于時間最短路徑的Dijkstra算法對停車場車位分布加權(quán)有向圖進行最短路徑尋優(yōu)，找到時間意義上的最優(yōu)車位。該算法減少了駕駛員停車時間，降低了道路車流量，有利于停車場的內(nèi)部管理，對于現(xiàn)代多車位、路線復(fù)雜的大型停車場具有實際意義。通過實驗證明，其結(jié)果更符合實際需要。

參考文獻

[1] 張玉杰,田碩.地下停車場智能化照明與停車引導(dǎo)系統(tǒng)設(shè)計[J].自動化儀表,2014,35(4):64-67.

[2] 齊悅,夏克儉,姚琳.數(shù)據(jù)結(jié)構(gòu)算法與應(yīng)用[M].北京:清華大學(xué)出版社,2015.

[3] 張渭軍,王華.城市道路最短路徑的Dijkstra算法優(yōu)化[J].長安大學(xué)學(xué)報:自然科學(xué)版,2005,25(6):62-65.

[4] 黃震,薛文科,李鵬,等.Dijkstra算法在停車誘導(dǎo)系統(tǒng)中的應(yīng)用[J].計算機時代,2013(12):38-41.

[5] 彭紅星,解鳳玲.改進Dijkstra算法在停車誘導(dǎo)系統(tǒng)中的應(yīng)用與仿真[J].計算機應(yīng)用,2011,31(S2):63-66.

[6] 李曉東,王東,曾凡智,等.城市交通時間最短路徑計算模型及應(yīng)用仿真[J].計算機仿真,2014,31(1):172-176.

[7] 馮璐璐.基于物聯(lián)網(wǎng)的停車泊位誘導(dǎo)系統(tǒng)關(guān)鍵技術(shù)研究[D].長春:吉林大學(xué),2013.

[8] 張玉杰,田碩.Dijkstra優(yōu)化算法在停車場車位引導(dǎo)系統(tǒng)中的應(yīng)用[J].計算機測量與控制,2014,22(1):191-193.

中圖分類號：TH7;TP301+.6

文獻標志碼：A

DOI:10.16086/j.cnki.issn1000-0380.201508006

河南省科技攻關(guān)計劃基金資助項目(編號：142102310225)。

修改稿收到日期：2015-05-07。

第一作者李偉(1982-)，男，2008年畢業(yè)于西安電子科技大學(xué)交通信息工程及控制專業(yè)，獲碩士學(xué)位，助教；主要從事嵌入式及物聯(lián)網(wǎng)技術(shù)、智能交通系統(tǒng)的研究。