基于免疫克隆算子的卷煙物流AGV 動態路徑規劃＊

劉彥新

（甘肅煙草工業有限責任公司，甘肅 蘭州 730050）

1 概述

為提高現代卷煙生產倉儲物流系統自動化管理和柔性化生產指標、降低生產成本、提高生產效率，防止物料配送差錯，眾多卷煙工業公司將自動導引小車(Automatic Guided Vehicle，AGV）作為卷煙物流輸送系統中的重要物流配送裝備，可以達到及時、快速、規模優化、成本低、易于管理的目標。

AGV 在生產現場中的行走路徑范圍并無特殊要求，只要車體能夠順利通過的場地均可作為其行走的路徑。但因現場障礙物的阻擋，或多AGV 之間的阻礙等原因，導致AGV 系統整體效率降低，通過增加AGV 數量的方式，雖然能提高AGV 系統的效率，但是多AGV 之間的沖突，又給系統增加了新的復雜性。因此，規劃出無障礙的路徑，可以有效提高AGV 系統的運行效率，節約生產過程中人工排故成本，最終達到降本增效[1]。

當前，在國內外對AGV 路徑規劃、合理避障、提高運行效率開展了廣泛的研究，牛秦玉等[2]提出通過建立作業點、生產線、工位的數據模型，設計指令優化算法，提高AGV 運行效率。李睿等[3]提出一種AGV 動態調度系統架構，對AGV 地圖進行預處理，通過Dijkstra 算法，提高AGV 運行效率。Tavares 等[4]為解決AGV 工作過程中多障礙物的避障問題，提出了利用自適應鄰域的模擬退火算法，規劃出無沖突的AGV 運行路徑。Umar 等[5]為解決多AGV 路徑沖突問題，提出設立優先級的遺傳算法，規劃出無沖突的AGV 運行路徑，成為AGV 路徑規劃研究的新趨勢。

鑒于此，文章根據實際生產車間現場環境多AGV 小車路徑情況已知，具有多邊界條件約束的情況，提出基于免疫克隆算子的算法求解最優規劃路徑，為提高AGV 系統使用效率提供一個新的方法。

2 卷煙物流AGV 動態路徑規劃

在AGV 實際使用工況中，障礙物和威脅區域經常無法固定下來，需要時刻進行規劃計算。由于局部路徑規劃（即動態路徑規劃）時間復雜度小于全局路徑規劃（即靜態路徑規劃）且效率也相對較高，因此，某卷煙廠輔料系統AGV 路徑規劃將采用局部路徑規劃進行研究和設計。

2.1 卷煙物流系統路徑規劃分析

某卷煙廠輔料輸送AGV 系統采用設計為全局路徑規劃，如圖1 所示。

圖1 卷煙物流AGV 路徑規劃系統

路徑采用有權圖法，將路徑和工作點的真實路徑抽象為點和線的問題，每一條線都表示在給定地圖下可行進的路徑，點表示AGV 路徑終點（即工作地點）。現有輔料輸送AGV 系統中路徑為單向通道，AGV 在工作過程中或前往充電樁時，只可行走在單向通道中，當運輸過程中檢測到突發障礙物或人員時，AGV 停留在原地進行等待不進行其他操作，直到障礙物消失才會繼續行進。隨著生產線生產效率的提高，對AGV 利用率較低的現有AGV 路徑規劃系統已無法滿足輔料系統供應，對產品生產影響較大。因此，需設計新的AGV 路徑規劃系統以提高生產效率。

根據分析，需要對現有AGV 系統路徑設計和路徑規劃算法兩部分進行優化，對路徑設計采用柵格法代替有權圖法。由于計算機存儲數據為離散形式，柵格法可有效降低有權圖法造成的算法計算時間長、時效性差的影響。柵格法示意圖如圖2 所示，柵格法將地圖環境利用長寬固定矩形劃分為網格圖，圖中白色區域表示AGV 可行進區域，黑色區域表示為不可行進區域即障礙物。算法將搜索AGV當前所處矩形的附近白色矩形，根據判斷條件搜索出一條或多條可行路徑方案，并最終選擇最優路徑作為解。

圖2 柵格法示意圖

2.2 基于免疫克隆算子的AGV 動態調度算法

根據上節分析，現有AGV 路徑規劃系統采用雙通道單向路徑設計，且系統采用全局路徑規劃算法進行計算，當AGV 前端感應器監測到障礙物時將會原地等待直到障礙物移除才會繼續行進。因此，針對現有AGV 路徑規劃系統設計缺陷，提出基于免疫克隆算子來求解AGV 調度路徑規劃問題。算法步驟設計如下：

（1）初始化。對地圖環境進行柵格法初始化，對每塊矩陣（即簡化坐標點）進行初始化，計算其距離矩陣；將矩陣臨近一格可移動位置存儲至距離矩陣中，用于路徑搜索使用。

（2）編碼。初始種群由解空間隨機生成。編碼采用一般數據結構編碼，編碼第一位存儲系統路徑唯一編碼用于路徑數據存儲，從第二位開始按照起始點至終點所經路徑節點進行坐標，且所有路徑點按照行進速度順序排列形成。設A 為種群中個體，則A=｛a1,a2…an｝，其中a1為唯一編碼，a2-an 為路徑點。

一般取：

克隆過后，種群變為：

其中：

為了保留父系種群的信息，變異算子并不作用到A∈A′，即：

（4）變異。對克隆子種群ai利用變異算子進行處理，隨機選擇ai種群中任意路徑點進行變異操作，并根據該變異點對后續路徑進行重新計算，以此獲得新路徑。若變異后無法計算出新路徑，則以原有路徑作為新路徑存入種群。

（5）選擇。根據個體編碼長度進行計算，由于小車行進速度固定，故個體編碼長度最短即為最優解。

（6）動態路徑規劃。當AGV 小車根據規劃路徑行進中傳感器檢測到障礙物，等待一定時間再進行檢測，連續三次檢測若障礙物未消失將重新進行路徑規劃。根據編碼第一位UUID 查詢到路徑終點，并以當前路徑點為起點，查詢路徑點為終點進行重新路徑規劃。規劃過程中將摒棄原有路徑點，以旁邊路徑作為下一路徑點進行計算，避免進入原有最優路徑。

3 路徑規劃仿真實驗與分析

根據現有廠區地圖以生產車間為例將可行進路徑分解為柵格地圖，并對地圖進行路徑矩陣設計存儲。為驗證算法適用性，分別以標準使用工況和隨機終點作為條件設計算法終點，實際終點路徑點為四條生產線投料處、輔料系統送料處和充電樁共計12 個固定終點。設置算法迭代次數為100，變異率為0.01，初始種群規模為10，免疫克隆算法計算結果如圖3 所示。

圖3 免疫克隆算法計算結果

首先起點隨機，終點分別為12 個固定路徑點進行12 次隨機路徑規劃，兩種算法路徑長度較短則統計次數加一，計算時間取12 次路徑計算平均值，得出結論見表1。

表1 遺傳算法與免疫克隆算法比較

隨機終點測試將同樣采取12 次路徑計算，路徑起點、終點均為隨機值，為保證路徑過短計算結果沒有說明性，設置12 次路徑規劃路徑點相距最少為20，同樣采用上述統計方式，得出結論見表2。

表2 遺傳算法與免疫克隆算法比較

根據上述實驗結論，免疫克隆算法計算時間兩次均少于遺傳算法，且路徑長度也少于遺傳算法，能更好地應用于工程實際。

4 結論

根據上述仿真實驗結論，在AGV 動態路徑規劃中，免疫克隆算法在路徑長度和計算時間兩個維度上均優于遺傳算法，可明顯提高企業生產效率。