基于改進型蟻群算法自適應停車引導系統的設計

晏 勇，雷 航，梁 潘

（1. 阿壩師范學院 電子信息與自動化學院，四川 阿壩 623002；2. 電子科技大學信息與軟件工程學院，四川 成都 610054；3. 成都航空職業技術學院 士官管理學院，四川 成都 610100）

目前，停車難已經成為阻礙城市發展的重要因素，特別是在城市中心繁華地段這一矛盾更加突出。停車場信息化建設滯后與汽車產業的發展不相稱，停車缺乏有效引導設備，車輛不能及時高效找到停車位，同時停車場本身通行能力有限，容易造成擁堵，停車更難。本文采用改進蟻群算法[1]，設計了一種自適應停車引導系統，車輛進入停車場后，系統按目的地最優路徑原則引導車輛就近停放，縮短了停車路徑，減少了停車時間，提高了停車效率與停車場的使用效率，具有很高的實用價值。

最優路徑規劃是自適應停車引導系統的核心，預停車輛進入停車場后迅速找到目標停車位，完成停車。蟻群算法是一種典型的最優路徑規劃算法，有并行性、魯棒性強等優點，同時也存在局部最優與收斂性差的缺點[2]。文[3]研究了基于人工勢場的群蟻算法，采用隨機參數轉移策略，增強算法魯棒性；文[4]重構啟發函數，加快算法收斂速度，但容易出現局部最優；文[5]將基本蟻群算法與遺傳算法相融合，引入交叉算子，避免局部最優。本文針對標準蟻群算法缺點，結合先前研究成果提出了基于狀態轉移策略的改進型自適應蟻群算法，加快算法收斂速度，實現停車最優路徑規劃。

1 任務描述

典型地下停車場有一個出口與一個入口，受建筑物實際條件影響，停車場內部存在斷頭路，內部道路為雙向兩車道行駛，考慮安全因素需減少步行時間，目的地設置為大樓電梯口，車輛進入停車場后，引導系統按目的地最近原則分配車位，盡量遠離停車場出口且轉彎少，按路徑最優原則規劃一條停車路徑，在入口大屏幕顯示，并通過藍牙模塊發送至車主手機，所有車主按照停車場引導路徑與引導車

位有序停車。基于以上特征，采用拓撲法對典型的停車場進行描述，拓撲結構如圖1。

圖1 停車場拓撲結構

停車引導系統中有n輛待停車輛，有n個車位，車輛停車最優路徑優化模型用有向圖表示，其中G=(V,A)，V= 0∪D，入口0 表示車輛起始位置；D為車輛與空閑車位集合，D=B∪C= ｛1,2, … , 2n｝；B為車輛集合，B= {1,2,… ,n}；C為空閑車位集合，C={n+ 1,n+ 2,… , 2n}；A= {(i,∈V,i≠j,i,j= 0,1,… ,n}，每條路徑(i,j)都包含非負權屬值，dij和tij分別代表停車路徑的距離和時間。汽車從入口0 出發，到達指定停車位[6]。根據停車場現場條件與任務描述，停車引導系統最優停車路徑與時間成本的目標函數如式（1）：

2 改進型自適應蟻群算法

2.1 算法描述

改進型蟻群自適應算法以原有信息素更新為基礎，計算下一節點移動轉移策略，求解最優停車規劃路徑，同時保證收斂速度與質量，提高算法魯棒性[7]。最優規劃路徑搜索中的螞蟻k在時刻t處于節點i，由改進型自適應蟻群算法狀態轉移策略計算下一移動節點j，通過規劃最優路徑到達停車地點[8]。

式（2）和（3）中，k表示螞蟻數量，allowedk表示螞蟻可訪問下一節點的集合，表示節點i的第k只螞蟻在下一節點轉移到節點j的概率，α表示信息素的重要程度，β表示啟發因子的重要程度[9]。q∈ [ 0,1]為平均分布隨機數，q0為閥值決定先驗知識與新路徑之間重要程度。q＜q0則螞蟻采用確定性搜索方式移動；q≥q0則螞蟻采用隨機搜索方式移動，通過計算下一點概率確定下一步移動節點[10]。由于地下車庫停車過程中可能受到停車場擁擠等因素干擾，進一步進行濾波與最佳路徑自適應調整，濾波系統函數為

停車擁堵檢測采用激光器檢測停車路徑是否擁堵，雙向擁堵時Madapt= 0，單向擁堵時Madapt= 0.5，雙向暢通時Madapt= 1。

2.2 算法流程

算法設計基于下一步潛在節點移動的狀態轉移策略，設定螞蟻的自適應度，求解螞蟻最優路徑，改進型自適應蟻群算法流程圖2。

圖2 改進型自適應蟻群算法流程

初始化蟻群參數包括蟻群數量、迭代次數等參數，令初始循環次數為0；將m只螞蟻放置于停車場入口處作為初始節點[12-13]，初始化信息素nij=，將初始節點作為出發點搜索下一步移動節點；初始化禁忌表以螞蟻當前位置為中心搜索下一步移動節點，按照式（2）和（3）計算路徑概率，將下一移動節點添加至遺傳禁忌表，搜索螞蟻移動路徑；通過設置Madapt，更新信息素遍歷螞蟻路徑，求解螞蟻移動最優解，即停車最優路徑[14-15]。

3 系統實現

改進型蟻群算法的自適應停車引導系統由4 個部分構成，即停車場主控平臺、擁堵檢測終端、車位檢測終端、智能手持終端。停車場主控平臺為系統核心，完成改進型蟻群算法的停車系統的自適應算法并選擇最優停車路徑、待停車輛與停車路徑綁定、待停車輛路徑與智能手持終端綁定，無線傳感器網絡（wireless sensor networks, WSN）協調器組網與網絡管理[16]。停車場主控平臺采用德州儀器C6000 系列66AK2E0x 多核DSP 處理器，主頻1.4 GHz，內嵌ARM 內核；WSN協調器與終端節點控制器采用基于TI 公司Zigbee 協議處理器CC2530[17]。

4 結果與分析

改進型蟻群算法自適應停車系統仿真測試包括最優停車位選擇與最優停車路徑選擇，以某地下停車場為例，采用MATLAB2018a 軟件進行仿真與數據對比測試，數值仿真環境為Intel Core i7-8700 處理器、8 GB內存、Windows10 操作系統[18]。

4.1 最優停車位仿真測試

改進型蟻群算法自適應停車系統最優車位為靠近電梯入口且遠離停車場出口的位置，每一個車位都作為WSN 終端節點，有唯一物理地址，計算電梯入口與車位距離LEe、停車場出口與車位距離LPe。對于1和 2 號停車位，LEe1＞LEe2則選擇 2 號停車位，LEe1＜LEe2則選擇1 號停車位，即選擇靠近電梯入口的停車位；當LEe1=LEe2時，LPe1≥LPe2則選擇1 號停車位，LPe1＜LPe2則選擇2 號停車位，即選擇遠高停車場出口的停車位。

停車場平面圖如圖1 所示，當前實際空余車位A11、C5、G5、I7、H10，通過仿真計算得到 LEeA11＞LEeC5＞LEeG5＞ LEeI7= LEeH10和 LPeI7＞LPeH10，選擇I7車位，實際大屏幕顯示車位與仿真測試結果一致，下一步完成最優停車路徑仿真測試。

4.2 最優停車路徑仿真測試

停車場平面圖如圖1，仿真測試蟻群算法參數為螞蟻數量M= 50，迭代次數I=100，α= 1，β= 1，τ0= 1，學習速率η=0.8，根據不同擁堵情況設定Madapt，每個實驗樣本均為隨機生成，起點為停車場入口，終點為停車位I7，汽車進入停車場限速5 km/h，車位尺寸3 m ×6 m，停車場路面雙向車道路寬8 m。Madapt= 1時基本蟻群算法與改進型自適應蟻群算法結果對比見表 1；Madapt= 0.5時結果對比見表 2；Madapt= 0時結果對比見表3。

表2 基本蟻群算法與改進型自適應蟻群算法結果對比（Madapt=0.5）

表3 基本蟻群算法與改進型自適應蟻群算法結果對比（Madapt=0）

對比分析表1、2、3 結果知，停車路徑雙向暢通時，相比基本算法，改進型蟻群自適應算法時間與距離短且彎道少；通道AB 單向擁堵時，原最優路徑“入口—AB—I—I7”經自適應調整后變為“入口—F—CD—I—I7”，停車時間減少39 s；通道AB 雙向擁堵時，基本蟻群算法停車路徑“入口—AB—I—I7”不變，停車時間待定（等待交通恢復），經自適應調整后最優路徑為“入口—F—CD—I—I7”，停車時間45 s。經測試，改進型蟻群自適應算法在交通暢通、單向擁堵或雙向擁堵情況下均能自動檢測擁堵并識別最優停車路徑，汽車可按最優路徑停入車位。

5 結語

本文針對地下停車場最優路徑規劃問題，建立了基于狀態轉移策略改進型蟻群自適應算法模型，完成停車場內部道路的擁堵檢測并調整規劃路徑，實現動態最優停車路徑。測試結果表明，采用該算法模型優化了停車路徑，縮短了停車時間，具有較好的實用價值。