基于AHP與Bellman—Ford算法的停車規劃方法

王超+高武奇

摘要：為解決現代城市停車車位信息不透明、缺乏誘導信息等原因導致的停車難等問題，提出了一種車位引導算法。該算法根據各停車場、路段的靜態信息和采集來的實時信息，建立相應的指標體系，采用層次分析法，計算各指標權值系數，得出區位排序，并給出基于改進Bellman-Ford算法的最短車位引導路徑。

關鍵詞：車位引導；層次分析法；指標體系；Bellman-Ford算法

中圖分類號：U495 文獻標識碼：A 文章編號：1007-9416（2017）07-0142-02

近年來，隨著國家經濟的高速發展和人民生活水平的快速提高，城市化進程伴隨著汽車的廣泛普及。由于機動車的增長，車輛使用強度增加，對停車產業而言，是一種最好的機遇，多種停車場設備相繼出現[1]。為了停車管理更加方便快捷，智能停車系統中已經開始采用停車誘導手段。這樣，不僅可以使駕駛者能更加快捷地找到車位，提高停車場車位利用率，而且可以提高停車場的管理效率，大大緩解城市交通壓力，為城市交通建設帶來更多效益[2]。因而，在考慮實現怎樣的停車誘導時，如何選擇合理的車位和最便捷的路徑，保證駕駛者順利找到車位并停入已經成為現今停車誘導研究領域所要解決的重要問題。

1 問題分析

目前國內外公認的較好最短路徑算法是Dijkstra算法[3]，其本質是基于靜態網絡的最短路徑搜索算法[4]。由于交通路網的復雜性和不確定性，與靜態環境下的最短路徑相比，動態條件下最短路徑的選擇更有現實意義[5]。路徑最短不一定時間最短，而且不同類型的停車場對應不同的停車環境，不同的駕駛者有不同的停車意愿，所以車位的選擇也不能一概而論。目前停車場管理系統所能提供的信息主要還是靜態的路徑誘導，缺乏對交通情況變化的掌握，很容易造成擁堵現象[6]。對于停車場或者是車位的選擇，已有的方法大多是基于最短路徑得出的，忽視了駕駛者的特殊要求。

因而，在本文中提出一種普遍適用的區位選擇方法，無論是對于停車場外引導還是停車場內引導[7]，該方法都可以在在保證及時獲取車位信息的前提下，可以根據層次分析法以及該時段的實時車位信息給出合適的停車區位排序，并考慮實時路況信息給出最佳停車路徑，有效提高停車效率。

2 基本原理

2.1 指標體系的建立

停車場的類型有很多，有地下停車場、露天室外停車場、路內停車場以及住宿小區/校園傳統停車場等，其停車設施、周圍環境、車輛進出情況、收費情況等不盡相同。 在經過多個停車場的問卷調查及數據采集后，綜合得出費用、可達性、流量、環境、空余車位數量等多個影響駕駛者選擇停車區位的指標，這里選取影響最為重要的4個指標（費用、可達性、流量、環境），綜合分析這些指標要素，建立評價各停車區位的指標體系及衡量尺度。

2.2 最佳車位的選擇

2.2.1 AHP基本原理

層次分析法（AHP）可以將定性和定量的方法結合起來，處理許多用傳統的最優化技術無法著手的實際問題，在最大程度克服主觀因素的條件下，盡可能全面地考慮所有的影響因素，得出比較準確、科學的結論。同時，層次分析法比較簡單易行，成本也比較低，不會造成過重的財務負擔。

首先將復雜問題分成若干層次，以同一層次的各要素按照上一層要素為準則進行兩兩判斷，比較其重要性，以此計算各層要素的權重，最后根據組合權重并按最大權重原則確定最優方案。

2.2.2 AHP選最佳車位

（1）選擇評價指標，建立層次結構模型。將決策的目標——確定最佳車位、考慮的因素——選取的指標要素和決策對象——各個停車區位按它們之間的相互關系分為目標層、準則層和方案層，繪制層次結構圖。

（2）構造指標判斷矩陣并比較。在確定各層次各因素之間的權重時，如果只是定性的結果，則常常不容易被別人接受，因而提出：一致矩陣法，即：不把所有因素放在一起比較，而是兩兩相互比較。對比時采用相對尺度，以盡可能減少性質不同因素相互比較的困難，以提高準確度。層次分析法中通常采用9級標度法來給判斷矩陣的元素賦值[8][9]，這里需要根據依據經驗值及專家打分法，將各準則要素的相對權重定量化，并運用加權平均，利用上一步的結果計算每個方案下每個指標的相對權數。

（3）一致性檢驗。為了確保判斷矩陣能科學地評價各個指標的相對重要性以及評價結果的有效性[10]，AHP提供了一致性程度要求來檢驗成對比較的一致性，若該一致性檢驗符合要求，則繼續下面的運算；否則重新審核并做出相應修改。

（4）確定最佳車位。通過層次總排序確定準則層所有因素對于總目標相對重要性的排序權值。將不同方案各準則要素的權重矩陣與準則要素的相對權重矩陣相乘，得到各區位的層次排序，進而選出最佳區位。

2.2.3 路徑選擇

本文將Bellman-Ford算法改進，提出了靜態/動態最優路徑算法。動態最優路徑算法是在已有路徑權值的基礎上，通過在路段增加附加權值來映射路況等因素對路徑的影響，根據實際路況選擇相應的附加權值[5]，最后由Bellman-Ford算法得出實時的動態最優路徑。無附加權值或附加權值均為零時的情況為靜態最優路徑算法。

附加權值的選取需要綜合各種環境因素（能見度、路面濕滑度、交通密集度等）對路徑的影響并根據其影響程度匹配不同等級的權值。這里的附加權值不是單一的，可以有多個。如果在車輛行駛途中有停車需求，則根據one-step-look-ahead的策略，將所處位置作為動態最優路徑算法的源點，同時對交通網絡的附加權重進行匹配賦值[11]，從而實現了最優路徑的實時動態選擇。當路況突然發生變化時，只需要及時更新各路徑的權值即可[12]，不會影響算法的運行。

通過采用限制搜索范圍、分解搜索目標等策略減少迭代次數，以降低算法的時間復雜度。endprint

3 結語

應用層次分析法確定最佳停車區位，可以將定性的區位分析根據民意調查轉化為定量的權值大小，進而將停車區位選擇變為停車區位的單一指標/綜合排序問題。在一定程度上，將現有的停車資源充分整合[13]，為有停車意愿的駕駛者提供了最佳停車區位，滿足了駕駛員的特殊要求。在Bellman-Ford算法中引入附加權值計算得出的最佳路徑綜合考慮了靜/動態交通和環境變化等因素，具有全局優化性、實時性和應變性。

參考文獻

[1]楊曉光，薛昆，白玉.城市停車誘導信息系統設計[J].交通運輸系統工程與信息，2004，（1）：93-96.

[2]劉姣，葛召炎，謝靜，吳軒.停車場泊車問題的研究與仿真[J].計算機仿真，2011，（7）：340-344.

[3]王防修，周康.基于回溯法的Dijkstra算法改進及仿真[J].計算機仿真，2013，（11）：352-355.

[4]何建國，張文勝，趙根莊.智能泊車引導方法的研究與實現[J].地理空間信息，2007，（2）：3-5.

[5]宮恩超，李魯群.基于Bellman-Ford算法的動態最優路徑算法設計[J].測繪通報，2011，（8）：26-28+41.

[6]李坤.智能停車場車位檢測與泊位誘導系統研究與設計[D].中國科學院大學（工程管理與信息技術學院），2013.

[7]劉媛媛.大型停車場內車位誘導系統研究[D].長安大學，2010.

[8]劉江.基于層次分析法的企業運輸方式的選擇[D].對外經濟貿易大學，2006.

[9]汪少勇，李建忠，郭秋麟，李登華.層次分析法在致密油有利區優選中的應用——以川中侏羅系大安寨段為例[J].地球科學進展，2015，（6）：715-723.

[10]魏曉玲.在Matlab平臺上用AHP對高職院校畢業生綜合素質的評價[J].計算機與數字工程，2016，（11）：2288-2292.

[11]董芳.彎道駕駛行為研究及無人駕駛車輛智能行為評價[D].北京理工大學，2016.

[12]張沖，朱凡.基于Bellman-Ford算法的無人機路徑規劃研究[J].彈箭與制導學，2007，（5）：249-251.

[13]周智勇，陳峻，王煒.城市停車誘導信息系統發展應用綜述[J].交通運輸系統工程與信息，2006，（2）：27-30.endprint