考慮路徑長度與沖突的AGV停車場停車位分配方法

姚寶珍，張 晉，時 彬，崔賀琪，張明恒

（大連理工大學汽車工程學院，遼寧 大連 116024）

0 引言

近年來，我國汽車保有量持續增長，而城市停車位數量增長緩慢，停車難問題日益突出。同時，已有停車設施使用效率低，停車信息不通暢，駕駛者尋找車位過程中的無效巡游導致停車擁堵和大量的尾氣排放[1-2]。為解決城市停車難題，基于自動引導小車（Automated Guided Vehicles,AGV）的智能停車場應運而生。AGV 因其可實現無人化泊車、便于集中管理停車位信息等優勢在智能停車領域具有巨大的應用潛力，通過AGV 實現全自動無人泊車管理成為近年來停車領域的研究熱點。

AGV 路徑規劃作為AGV 系統的重要組成部分，直接關乎AGV系統效率優化、AGV運行安全保障、AGV 能耗降低等[3]，因此得到了廣泛研究。目前，國內外關于AGV 路徑規劃問題的研究側重于多AGV 路徑規劃及調度，如劉二輝提出一種改進的花授粉算法求解多AGV 任務調度問題[4]；王家君提出一種基于緊急程度的任務分配算法，用于解決智能停車場內泊車AGV 沖突問題[5]；Xu等提出一種兩階段的AGV 路徑規劃方法，先使用遺傳算法對AGV 進行靜態最優路徑規劃，再采取在線調度的策略以避免多AGV 的沖突碰撞[6]；Bai等將強化學習算法與改進的遺傳算法相結合，并將調度策略集成到全局靜態路徑規劃中，可根據動態環境的變化不斷調整多AGV 的調度策略，避免AGV 之間產生沖突[7]；Umar 等采用遺傳算法對多AGV 進行路徑規劃，并通過一定的約束目標設立優先級來解決任務執行過程中的沖突問題[8]；Sun 等采用時間窗算法，使每個AGV 可根據時間窗口動態調整路徑，從而實現AGV 的無沖突路徑規劃[9]。上述研究大多從改進路徑規劃算法和協同調度方法入手，大多數針對智能物流及智能制造等AGV 工作環境，從局部視角對已形成的沖突進行消解，但對AGV 間沖突的產生缺乏解決能力。對于道路狹窄、布局緊湊的停車場環境，上述研究中基于路徑規劃的方法優化空間非常有限，并不能有效避免沖突的產生。當下仍缺乏從全局層面減少AGV沖突產生的有效方法。

在AGV 智能停車場中，綜合考慮AGV 行駛距離、行駛路徑的干擾及沖突，進而為待停車輛分配合適的停車位置，可以有效地減少AGV 之間的干擾，從而改善停車場內的交通狀況，因此關于停車位分配方法的研究逐漸受到重視。關于停車位分配問題的既有研究，大多針對為人類駕駛的車輛分配最佳停車位[10-11]，如肖瑋設計了一種基于多目標點A*算法的停車場車位路徑引導系統，綜合考慮用戶需求和停車路徑長度為待停車輛分配最優停車位[12]。還有一些研究則從空間利用率、存取效率的角度出發，重點解決立體車庫場景下的停車位分配問題，如邢麗娟等采用隨機車位分配策略和就近車位分配策略，針對車輛入庫和出庫、車位利用率、堆垛機運行距離等建立仿真模型[13]；Li 等提出一種基于博弈論的停車位搜索方法，可在比啟發式謹慎策略更短的行駛距離內找到可用的停車位[14]。然而，現有針對停車位分配問題的研究與AGV 智能停車場的環境背景區別較大，若直接應用于AGV 智能停車場環境中，可能導致AGV 工作區域過于集中，造成頻繁的擁堵和沖突，但其中一些多目標優化的思路和算法仍具啟發意義。

總體上，現有關于AGV 在智能停車場領域應用的研究成果主要針對局部視角中已經產生沖突的規劃調度問題，而在全局層面的停車位分配問題研究中忽略了AGV 智能停車場環境的特殊性。因此，本文在充分考慮AGV智能停車場環境特征的基礎上，將提出一種考慮路徑長度與沖突的AGV智能停車場停車位分配模型，將停車路徑沖突概率和停車路徑長度納入模型目標函數，以期在全局層面為待停放車輛分配合理的停車位，在AGV 執行停車任務前降低多臺AGV 路徑之間產生沖突的概率，同時在局部層面，最小化停車任務的路徑長度，進而提升AGV 智能停車場運營效率。此外，設計NSGA-Ⅱ算法對所提出的模型進行求解，最后通過仿真實驗對模型和算法的有效性進行驗證。

1 停車場環境描述及地圖建模

1.1 AGV智能停車場描述

本研究主要針對由現有停車設施改建的AGV智能停車場，車輛到達停放或取車離開停車場的過程采用AGV 進行自動化搬運?？紤]到取車問題是一個端到端的最短路徑規劃問題，路徑起點及終點均已確定，因此本研究的重點為存取車高峰期的連續停車問題。停車場有多個出入口且在出入口設有交換等待區，駕駛人將待停放車輛停放在交換等待區后離開車輛。停車場控制系統將查詢當前停車場狀態，為待停放車輛分配一個空閑停車位，隨后指派1 臺空閑AGV 將待停放車輛搬運至系統分配的停車位。整個停車過程可分為以下幾個步驟。

1）車輛駛入停車場。駕駛員將車輛駛入停車場入口，并停放在指定的臨時交換等待區域。

2）車輛請求停車。當待停車輛到達停車場入口時，向停車場控制系統發送請求停車信號。

3）分配停車位?？刂葡到y接收到請求信號后，會根據當前停車場內空余車位的情況，為待停車輛分配1 個合適的停車位，通常采用隨機分配、最近可用等算法。

4）分配任務至AGV。任務系統為當前停車任務分配1 臺空閑AGV，AGV 從交換等待區載運待停車輛。

5）導航至停車位?？刂葡到y將停車位的位置信息及規劃路徑信息發送給AGV，然后AGV根據路徑信息自主將待停放車輛搬運至分配的停車位。

6）完成停車。AGV 到達停車位后，使用機械臂將車輛抬起并移動到停車位后放下車輛，完成停車任務。

7）更新AGV 停車場狀態。停車系統更新車輛停放位置、停車狀態及空閑停車位信息，等待接收下一個停車任務。

通常，大型停車場包含數百個停車位，并根據布局分為幾個區域。為了增加研究結果的可擴展性，假設停車場不同區域的布局結構及車位數量相似。在實際應用中，停車場內一般有多個出入口，不同區域間的車輛交互較少，受郝樹運[15]提出的AGV 停車場布局啟發，本文以某AGV 停車場單個停車區為基礎展開研究，如圖1 所示。該停車區包含102 個停車位、6 個交換等待區車位。停車位尺寸設計為5.5 m × 2.5 m，滿足AGV旋轉半徑的車道寬度為5.5 m。交換等待區停車位在實際應用中需考慮人員上下車操作空間，因此應比普通停車位尺寸大，但為便于研究，建模過程中假設交換等待區停車位尺寸設計與普通停車位相同。

圖1 AGV智能停車場環境布局

為簡化問題并突出關鍵環節，對停車環境做如下約束：

1）車輛通過同一交換口進出停車場；

2）AGV從入口位置開始執行停車任務；

3）停車場內部車道為雙向單車道，寬度滿足AGV的最大轉彎半徑；

4）AGV 被視為具有安全半徑的粒子且以恒定速度行駛，每次轉彎時間相同；

5）AGV 只有在進入停車位時允許跨越路徑行駛；

6）交叉口允許AGV 從4 個方向進入且可以直行、左轉、右轉，同一節點同一時刻僅允許1臺AGV進入。

1.2 停車場環境地圖建模

AGV 作業系統中，環境地圖建模方法至關重要，對作業環境準確建?？墒笰GV 系統精準地識別障礙物和危險區域，進而使路徑規劃更高效。此外，合理的環境地圖建?？墒笰GV 系統更具適應性，以應對不同的任務類型。環境地圖建模方法主要有3 種，分別為柵格法、拓撲法和可視圖法。其中，基于拓撲法構建的電子地圖主要強調空間的連通性，通過繪制節點之間的邊來表示AGV 可通行的區域，這種建模方法可有效預防AGV 與靜態障礙物的碰撞。與柵格法和可視圖法相比，在同等規模的環境條件下，基于拓撲法構建的電子地圖節點數較少，資源占有率較低，有利于提高算法尋優效率?？紤]到本研究是從全局的角度進行車位分配和路徑規劃，不考慮環境中動態障礙物的影響，故選擇拓撲地圖法用于智能停車場的環境建模。

在拓撲地圖建模中，地圖結構被抽象成一個圖，由連接頂點和頂點間的邊構成，用數學方法可以表示為G（V,E），其中G表示圖，V是圖G中的頂點集合，E是圖G中的邊集合。根據工作線路的單向和雙向行駛要求，連線分為有向和無向。拓撲法在進行計算時，需要針對現有拓撲圖，根據連線的方向屬性建立相應的鄰接矩陣，即把每個點的連接關系通過矩陣具體化。采用拓撲圖法建立的停車區域電子有向地圖如圖2所示，其中節點1～6 為交換等待區節點，節點7～108 為停車位節點，節點109～252為路徑節點。

圖2 停車區域拓撲地圖建立

為使所建停車場電子環境地圖直觀且便于理解，建模過程中忽略了停車場實際環境中的立柱區域及其他設備空間。節點間的實際距離以權值的形式表示并記錄在拓撲地圖的鄰接矩陣中。部分鄰接矩陣信息如表1 所示。其中，與停車位節點相對應的路徑節點連接而成的路徑邊，如（140,141）和（141,142）的權值均為2.5，表示AGV 搬運待停放車輛從節點142 行駛至節點141或從節點141 行駛至節點140 需要行駛2.5 m。路徑節點與停車位節點連接成的邊如（30,142），其權值為3.375，表示AGV 搬運待停放車輛從路徑節點142 行駛至停車位節點30，需要行駛3.375 m。此外，圖中的長路徑邊如（145,144），其邊權值為11，表示AGV 從節點144 行駛至節點145需要行駛11 m。表1中∞表示不可通行，例如邊（140,142）的權值為∞，表示節點142 與節點140間無可通行路徑。

表1 部分節點拓撲關系數據

2 停車位分配模型構建及算法求解

本研究針對AGV 智能停車場，從停車位分配的角度出發，為待停放車輛分配最優停車位，并對停車AGV 進行路徑規劃。最優停車位是指能降低停車高峰期間，停車場內多臺AGV 同時停放車輛時產生路徑沖突的概率，并使AGV 所行駛的總距離盡可能短，以提升AGV 停車場的停車效率。為此，需構建一個考慮停車路徑長度和路徑沖突概率的停車位分配模型。

2.1 停車位分配模型

假設有n臺車輛等待進入停車場停放，停車場空車位數為m且m≥n，停車場內有k臺AGV進行停車作業。建立待停放車輛集合W，如式（1）所示：

建立空閑停車位集合P，如式（2）所示：

建立停車AGV集合A，如式（3）所示：

建立停車位分配方案集合T，如式（4）所示：

式（1）～式（4）中：wi表示第i臺待停放車輛，i∈[1,n]；pj表示第j個空閑停車位，j∈[1,m]；aq表示編號為q的AGV，q∈[1,k]；表示AGVaq將待停放車輛wi搬運至分配的空閑停車位pj。

在停車位分配方案中，設待停放車輛wi由AGVaq搬運停放至空閑停車位pj的停車路徑為ri?；谕＼噮^域拓撲電子地圖，AGV 將待停放車輛由交換等待區搬運至分配停車位的路徑規劃問題可視為圖論問題。根據所建停車場環境地圖模型，一條路徑可表述為圖中的一些節點組合和邊組合。因此，車輛wi的停車路徑ri可表示為式（5）：

式（5）中：Vi為路徑ri所經過的節點集合；Ei為路徑ri所經過的節點所連接成的邊集合，路徑長度為路徑經過的所有節點連接成的邊的權值累加。

基于此，建立停車位分配模型，如式（6）所示：

式（6）～式（10）中：F(T)為停車位分配模型的目標函數，包括路徑長度函數f1(T)和沖突概率函數f2(T)；T為停車位分配方案集合；L(ri)為AGVaq將待停放車輛wi停放至空閑停車位pj的路徑長度；ωe為鄰接矩陣中所儲存的邊權值；C(ri)為AGVaq將待停放車輛停放至空閑停車位pj的路徑與場內同時存在的其他路徑的沖突概率，其計算參考了Zheng 等[1]在2022 年提出的停車路徑沖突概率計算方法；Eo為停車場中已在執行的任務路徑所經過的邊的集合；Ei為當前規劃路徑所經過的邊的集合；其余變量含義同前。

A*算法作為一種圖論理論中的智能尋路算法，其在AGV 路徑規劃及拓撲環境地圖中已有大量成熟的應用案例。因此，為了提高停車位分配效率和準確性，本文采用A*算法來解決停車路徑搜尋和停車路徑長度計算問題。

2.2 算法求解

考慮停車路徑長度和停車路徑沖突的停車位分配問題是一種組合優化問題，需在有限的停車場道路資源和停車效率之間做出最佳決策，以最大程度地縮短停車路徑長度并減小停車路徑沖突概率。由于搜索空間較大且優化目標間存在沖突，此類問題較難采用精確算法對真實的應用案例進行求解，因此需設計與問題結構相匹配的啟發式算法進行求解?？紤]到所提出的停車位分配問題為一個離散優化問題且具有實時性，尤其在停車場高峰期具有頻繁的停車任務需求，因此采用收斂速度快、適用性廣的非支配排序遺傳算法Ⅱ（Non-dominatedSortingGeneticAlgorithm Ⅱ,NSGA-Ⅱ）對所建停車位分配模型進行求解。

NSGA-Ⅱ是一種流行的多目標優化算法，由遺傳算法改進而來，其采用快速非支配排序、擁擠距離算法和基因型多樣性保留等技術，可有效解決多目標優化問題，準確得到多目標優化問題的Pareto 非劣解集。NSGA-Ⅱ算法流程如圖3所示。

圖3 NSGA-Ⅱ算法流程圖

針對所提出的停車位分配優化模型，對染色體進行實數編碼，每條染色體包含2n（n為待停放車輛數）個基因。染色體編碼結構如圖4所示。染色體中的每個元素都是1 個基因，這些基因組成了染色體，用于描述一個完整的停車位分配方案。在算法迭代過程中，通過對染色體進行交叉和變異操作，可以生成新的停車位分配方案。

圖4 染色體編碼結構示例

根據圖3 所示NSGA-Ⅱ算法流程，按以下步驟對不同任務背景下的停車位分配模型進行求解。

步驟1：初始化初代種群（停車位分配方案）P0，并將進化代數設置為Gen=0。

步驟2：計算種群中的個體適應度值（目標函數值），其中利用A*算法求解交換等待區節點到停車位節點的路徑節點和路徑距離。

步驟3：對所有個體進行非支配排序，并分為多個等級，其中第一等級為Pareto 前沿解集中的個體。

步驟4：計算每個等級的個體擁擠度，用于區分該等級內個體之間的密集度。

步驟5：在所有等級的個體中，選擇最優個體作為精英進入下一代種群。

步驟6：對選擇出來的個體進行變異和交叉，生成新的子代個體。

步驟7：將新的子代個體與父代個體合并，形成新的種群P1，Gen=Gen+1，重復步驟2～步驟6，直至達到最大迭代次數。

3 實驗仿真與結果分析

基于所建停車區域拓撲環境地圖，設計一個仿真實驗，驗證在不同待停車輛數和不同AGV 數的條件下，停車位分配模型的性能。此外，對本文所提停車位分配模型與常用隨機分配方法及基于最短距離分配的方法進行對比實驗。實驗程序采用Python語言編寫，在內存為24.0 GB、頻率為2.90 GHz的Inter Core i5-9400F CPU系統上運行。

3.1 實例仿真

為適應實際停車場環境中硬件設置差異和不同城市停車高峰到達率差異，分別設置50、100兩個等級的待停車輛數量以及2、3、4 共3 個等級的AGV 數量配置，以驗證算法在不同AGV 停車場環境下的適應性和穩定性。

實驗中，將NSGA-Ⅱ算法的種群數設置為100，最大迭代次數為200，交叉率為0.6，變異率為0.05。不同待停車輛數量和AGV 數量條件下的停車位分配模型求解結果如圖5 所示，其中，圖5（a）、（b）為4 臺AGV 協同作業下，分別連續停放100 輛及50 輛待停車輛的求解結果；圖5（c）、（d）為3 臺AGV 協同作業的求解結果；圖5（e）、（f）為2臺AGV 協同作業的求解結果。在不同的停車分配任務下，NSGA-Ⅱ算法均求得了多樣化的帕累托非劣解集?？紤]到非劣解集中，總停車距離值差異較小，對AGV 停車場運行效率的影響相對較小，因此，選取非劣解集中路徑沖突概率最小的解作為停車位分配模型的最優解。

圖5 不同待停車輛和AGV數量下算法求解結果

由于不同背景下多個解集包含的解數量較多，現以4 臺AGV 協同作業、停放100 輛待停車輛為例進行分析，其最優停車位分配方案和停車路徑如表2所示。

根據表2，待停車輛依次進入交換等待區節點，其中1號待停車輛由1號AGV從交換等待區節點1搬運至停車位節點8，其停車路徑r1為1-109-144-143-142-141-140-139-138-137-116-8，可表示為：

根據鄰接矩陣信息，停車路徑r1長度為28.75 m。

2號待停車輛由2號AGV 從交換等待區節點2搬運至停車位節點54，其停車路徑r2可表示為：

根據鄰接矩陣信息，停車路徑r2長度為29.75 m。

路徑r1與r2存在重疊邊（109,144），根據環境地圖鄰接矩陣，其邊權值為2.25，即路徑r2與r1的停車路徑沖突長度為2.25 m，根據式（7），對應的停車路徑沖突概率為0.04。以此類推，路徑r3與已有停車任務路徑沒有重疊的路徑邊，沖突概率為0，與路徑r4的沖突概率為0.22。在連續停放100 臺待停車輛的運行背景下，停車路徑總距離為5 005.88 m，平均路徑沖突概率為0.11。

在停車區域配備4 臺AGV、停放100 輛待停車輛的任務背景下，算法收斂過程如圖6（a）所示，總停車路徑函數f1(T)和停車路徑沖突概率函數f2(T)收斂到最優解的算法迭代次數均在120 次左右。在停車區域配備4 臺AGV、停放50 輛待停車輛的任務背景下，算法收斂過程如圖6（b）所示，算法求解連續停放100 輛車和50 輛車兩種任務背景下，總耗時均在15 s內，驗證了算法在求解維度較高的停車位分配方案時，仍具有較高的實時性。

圖6 NSGA-Ⅱ算法迭代效果圖

3.2 對比分析

為驗證所提出的停車位分配模型及其求解算法的有效性，將其與相關文獻[12-14]中采用的基于最短停車路徑長度的停車位分配方法和基于空車位隨機分配的停車位分配方法進行對比實驗。

3 組實驗均在停車區域配備4 臺AGV，即A=(a1,a2,a3,a4)，待停放車輛數量設置為100 輛，即W=(w1,w2,…,w100)。AGV 按待停放車輛編號順序依次執行停車任務，由交換等待區車位搬運待停放車輛行駛至分配的停車位后停放車輛，不考慮AGV 空載返回交換等待區車位的過程。對每種停車位分配方法，在上述相同的任務背景下各進行10 次仿真實驗。3 種停車位分配方案對比實驗結果如表3所示。

表3 3種停車位分配方法對比實驗結果

從表3 中的對比實驗結果可以看出，本文所提出的考慮路徑沖突的停車位分配方法在兩個指標上均獲得較優的表現。與基于最短停車路徑的停車位分配方法相比，考慮路徑沖突的停車位分配方法在10次實驗中的平均停車路徑長度僅高出6.76 m（在實際停車場環境中，這樣的停車路徑長度差異幾乎可以忽略），對應的平均停車路徑沖突概率僅為0.14，而最短停車路徑方法的停車路徑沖突概率則高達0.43。這是因為考慮路徑沖突的停車位分配方法模型包含了式（7）所示停車路徑長度目標函數，停車位分配過程中在降低停車路徑沖突概率的同時，兼顧了連續停車任務的總停車路徑長度。此外，最短停車路徑方法僅考慮單個停車任務的AGV 行駛路徑長度，在為待停放車輛分配停車位的過程中缺乏全局協作，導致AGV的任務路徑重疊嚴重，AGV之間的沖突和擁堵頻繁產生；而考慮路徑沖突的停車位分配方法在停車位分配過程中，受式（8）所示子目標函數的優化，在連續進行停車位分配的過程中，能選擇路徑沖突概率更小的停車位，平均路徑沖突概率相比最短停車路徑方法降低了67.44%，在不影響AGV 行駛路徑長度的同時，能有效減少多AGV執行停車任務過程中的沖突和擁堵。

隨機分配的停車位分配方法由于停車位分配過程中的隨機性，為待停放車輛分配的停車位不會同最短路徑方法一樣過度集中，停車路徑沖突概率比最短停車路徑方法低。但考慮路徑沖突的停車位分配方法相比而言仍具有明顯優勢，在10次實驗中，考慮路徑沖突的停車位分配方法的停車路徑沖突概率相比于隨機分配方法降低了44.00%，這可能是由于隨機分配方法缺乏算法對停車位分配方案進行優化，停車位分配過程中可能產生一些不合理的集中，仍存在較嚴重的AGV行駛路徑重疊。

綜上分析，本文所提考慮路徑沖突的停車位分配方法，在求解考慮到停車路徑長度和停車路徑沖突概率的雙目標優化模型后，獲得的停車位分配方案達到了理想的優化效果，可在連續停車任務中，為待停放車輛分配路徑沖突概率低且AGV行駛距離較短的停車位，提升AGV智能停車場的運行效率。

4 結束語

本文針對AGV 智能停車場中考慮停車路徑長度及停車路徑沖突的停車位分配問題進行研究，采用拓撲圖法建立了停車場環境地圖模型，提出了一種雙目標優化模型，旨在最小化停車路徑長度并降低路徑沖突概率。為求解停車位分配模型，設計了NSGA-Ⅱ算法對該模型進行求解，并在所建立的停車場環境地圖模型中進行了仿真實驗。

實驗結果表明，所提出的雙目標優化模型和算法在不同AGV 數量和停車需求下都能得到多樣化的Pareto 非劣解集，且用時較短，滿足實時性需求。與傳統方法相比，所提方法在減少停車路徑長度和路徑沖突概率方面表現更優。特別是，路徑沖突概率相對于傳統方法分別降低了67.44%和44.00%。

研究表明，考慮停車路徑沖突的停車位分配模型和NSGA-Ⅱ算法是可行且有效的，且算法用時較短，滿足實際應用環境中的實時性需求，可為不同停車需求和AGV 配置條件下提供更優的停車位分配方案。但由于缺乏實際AGV 智能停車場應用數據，研究中未考慮不同車輛停放時間對停車位分配方案的影響。未來研究中將進一步完善模型和算法，考慮更多實際因素，以滿足不同應用需求。