劉彥新

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

1 概述

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

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

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

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

2 卷煙物流AGV 動態(tài)路徑規(guī)劃

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

2.1 卷煙物流系統(tǒng)路徑規(guī)劃分析

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

圖1 卷煙物流AGV 路徑規(guī)劃系統(tǒng)

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

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

圖2 柵格法示意圖

2.2 基于免疫克隆算子的AGV 動態(tài)調度算法

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

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

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

一般取：

克隆過后，種群變?yōu)椋?/p>

其中：

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

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

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

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

3 路徑規(guī)劃仿真實驗與分析

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

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

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

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

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

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

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

4 結論

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