基于免疫克隆算子的卷煙物流AGV 動態(tài)路徑規(guī)劃＊

劉彥新

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

1 概述

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

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

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

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

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

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

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

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

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

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

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

圖2 柵格法示意圖

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

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

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

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

一般取：

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

其中：

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

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

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

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

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

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

圖3 免疫克隆算法計算結(jié)果

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

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

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

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

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

4 結(jié)論

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