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

劉彥新

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

1 概述

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

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

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

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

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

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

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

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

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

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

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

圖2 柵格法示意圖

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

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

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

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

一般取：

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

其中：

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

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

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

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

3 路徑規(guī)劃仿真實(shí)驗(yàn)與分析

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

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

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

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

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

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

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

4 結(jié)論

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