基于時間最短路徑的停車場車位引導算法

Parking Guidance Algorithm Based on Time-dependent Shortest Path

李　偉1　余　森1　王　偉2

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

基于時間最短路徑的停車場車位引導算法

Parking Guidance Algorithm Based on Time-dependent Shortest Path

李偉1余森1王偉2

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

摘要：針對停車場管理系統中存在的車位引導問題，在研究場內道路網絡特征的基礎上建立加權網絡模型；以停車時間最短的路徑作為最佳車位確定準則，結合Dijkstra算法改進停車引導模型，對系統進行尋優。仿真結果表明，基于時間最短路徑的引導算法所選的最優車位更符合實際，停車平均時間最短，是一種尋求最優路徑的有效算法。

關鍵詞：車位引導時間最短路徑Dijkstra算法智能交通系統停車管理靜態交通

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引言

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

1停車場車位引導系統

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

通過實地調查研究發現，提高停車場效率的關鍵，在于每一輛車都能夠以最短的時間停泊，即尋找停車時間最短的車位要比停車距離最短的車位更為重要。基于上述考慮，本文設計了一種基于時間最短路徑(time-dependent shortest paths,TSP)的停車場車位引導系統。結合Dijkstra算法進行車位誘導，系統能夠減少車輛尋泊時間，提高停車泊位利用率，促使停車設施利用平衡化。

2時間最短路徑的內涵

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

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

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

另外，某一時間段內不但有車輛駛入停車場，同時也有車輛駛離，但是大多數停車場出口和入口是分離的，雙向行駛的車輛互不干擾，且駕駛人員根據經驗很容易找到出口，所以不需要對出場車輛進行引導。

3停車場通行規則模型

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

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

(1)

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

圖2　目標停車位加權有向圖

4Dijkstra時間最短路徑算法

4.1　權重的計算

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

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

(2)

其中：

(3)

4.2　引導算法

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

算法具體步驟如下。

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

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

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

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

(4)

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

5實驗仿真結果分析

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

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

表1　停車場內空閑車位與入口的距離

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

表2　路徑長度及消耗時間測試數據

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

6結束語

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

參考文獻

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

[2] 齊悅,夏克儉,姚琳.數據結構算法與應用[M].北京:清華大學出版社,2015.

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

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

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

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

[7] 馮璐璐.基于物聯網的停車泊位誘導系統關鍵技術研究[D].長春:吉林大學,2013.

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

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

文獻標志碼：A

DOI:10.16086/j.cnki.issn1000-0380.201508006

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

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

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