劉 暢，張承瑞，孫玉璽

(山東大學 機械工程學院，濟南 250061)

(山東大學 高效清潔機械制造教育部重點實驗室，濟南 250061)

1 引 言

隨著工業(yè)4.0時代的智能工廠的引入，工廠規(guī)模越來越大，對自動導引運輸車(Automated Guided Vehicle，AGV)的需求量變大，調(diào)度復雜性增加，AGV調(diào)度機制應該更加高效、魯棒.

現(xiàn)在已經(jīng)有很多學者對多AGV調(diào)度進行研究.Valerio Digani，M.Ani Hsieh等[1]提出一種優(yōu)化策略，來最大化AGV的吞吐量；Bai Li，Hong Liu，Duo Xiao等人[2]提出一種集中式多AGV運動規(guī)劃方法，計算效率更高.但是，國內(nèi)外研究的多AGV路徑規(guī)劃問題大多數(shù)是基于單負載，對多負載AGV的研究較少.

Azimi等[3]較早的研究了多載AGV調(diào)度需要解決的問題.Ho Y-C，Chien S-H研究多負載AGV的相關問題[4]，并且重點研究了多負載AGV的提取分配原則[5].霍凱歌等[6]，已經(jīng)對自動化集裝箱碼頭中的多載AGV調(diào)度問題進行研究，他們發(fā)現(xiàn)，多載AGV比單載AGV效率更高.Li-xiang Zhang等[7]研究了在自動化汽車裝配線環(huán)境下，多載AGV高效運輸物料的問題，并使用遺傳算法進行求解.Li-zhen Du等[8]研究了在紡織車間環(huán)境下，多載AGV運輸物料的問題，并且使用混合遺傳算法和粒子群算法進行求解.

隨著任務的維數(shù)增加，傳統(tǒng)算法求解的時間復雜度大.所以，國內(nèi)外很多學者使用智能算法(如頭腦風暴算法[9]、粒子群優(yōu)化算法[10])來對多AGV調(diào)度問題進行求解.

上述論文中，大多只是簡單的假設多載AGV運輸1個或2個負載，只考慮負載重量的約束，卻沒有考慮負載的體積約束.

本文第2節(jié)描述多載AGV調(diào)度問題的環(huán)境，第3節(jié)對路徑規(guī)劃問題進行建模，第4節(jié)對初始數(shù)據(jù)進行預處理之后，使用改進的自適應遺傳算法進行求解，第5節(jié)將改進的自適應與標準遺傳算法和自適應遺傳算法進行比較.

2 問題描述

對于工廠的物料運輸問題，在傳統(tǒng)的單載AGV模型中，不需要考慮體積、重量約束，只是將一種物料運輸?shù)侥康牡?，一次只?zhí)行一個任務.這極大的浪費了AGV的負載能力.

如圖1所示，AGV沒有任務時，會?？吭诔潆妳^(qū)域(charge area)，進行充電或者待機.任務集合發(fā)布時，AGV從充電區(qū)域(charge area)來到倉庫(warehouse).在不超過AGV體積、重量約束的條件下，根據(jù)調(diào)度算法求解得結(jié)果進行加載貨物，然后正式開始運輸貨物.在圖1的多載AGV運輸物料示意圖中，AGV可以根據(jù)任務需求自由地到達任意一點.當AGV負載為空時，會返回倉庫(warehouse)進行下一個任務的運載.周而復始，直到所有任務完成后，AGV會回到充電區(qū)域進行充電或者待機，直到下一個任務集合的到來.

圖1 多載AGV運輸物料示意圖

3 建立模型

本文主要解決的是工廠環(huán)境下如何高效調(diào)度多載AGV的問題.

3.1 符號說明與模型假設

符號說明

M：表示路徑規(guī)劃的路徑數(shù)目；

Ni：表示在規(guī)劃的第i路徑中，執(zhí)行任務點的數(shù)目；

cij：表示在規(guī)劃的第i條路徑中，從倉庫出發(fā)到第j個任務點所產(chǎn)生的成本；

Gij：表示在規(guī)劃的第i條路徑中，第j個任務點所需要的物料的重量；

G：表示多載AGV可承受的最大重量；

Vij：表示在規(guī)劃的第i條路徑中，第j個任務點所需要的物料的體積；

V：表示多載AGV可承受的最大體積；

Aijk：表示第k個任務是否在第i條路徑的第j個任務點被執(zhí)行；

K：表示任務總數(shù)目；

d_list：表示只能被單個運輸?shù)娜蝿拯c形成的路徑；

dd_list：表示被最短路徑模型求解后得到的路徑集合；

p_list：表示d_list和dd_list兩個集合的并集.

模型假設

1)單個任務的負載不會超過多載AGV的最大載重約束和體積約束；

2)AGV行駛單位長度，成本相同；

3)AGV勻速行駛.

3.2 調(diào)度模型

目標函數(shù)：

(1)

約束函數(shù)：

(2)

(3)

(4)

(5)

公式(1)為模型的目標函數(shù)，為距離函數(shù)矩陣，表示路徑的成本；公式(2)為多載AGV的重量約束；公式(3)為多載AGV的體積約束；公式(4)、公式(5)，約束任務能且只能被一輛多載AGV完成.

4 改進的自適應遺傳算法

遺傳算法[11]實現(xiàn)簡單，通用性強，易于和其它算法結(jié)合，具有并行性和魯棒性.但是，它也存在過早收斂、局部搜索能力弱等問題.

針對標準遺傳算法的上述不足，本文在自適應遺傳算法的基礎上，加入災變操作與逆變操作，提出一種改進的自適應遺傳算法(Improved Adaptive Genetic Algorithm，IAGA)，如圖2所示，其為改進自適應遺傳算法的流程圖.

圖2 IAGA流程圖

在初始化種群后，算法進入迭代部分，進行選擇、交叉、變異操作.

然后進入災變操作，根據(jù)適應度值，求解災變算子，判斷是否執(zhí)行災變操作，災變算子隨著陷入局部極值迭代次數(shù)的增加，不斷的增加種群的交叉概率和變異概率，使算法更容易跳出局部極值.

之后，進入逆轉(zhuǎn)操作，即局部搜索部分.當滿足逆轉(zhuǎn)條件后，進入逆轉(zhuǎn)操作.在逆轉(zhuǎn)操作中，添加了倒序操作與插入操作.選取種群的部分染色體，根據(jù)倒序概率和插入概率，判斷是否進行倒序操作或者插入操作，執(zhí)行完畢后，將操作后的染色體的適應度值，與操作前的適應度進行比較.適應度值變大時，才會接受新解.算法將沿著適應度變高的方向進行進化.

最后根據(jù)迭代終止條件(迭代次數(shù)或者收斂)，判斷是否終止迭代.

4.1 適應度函數(shù)

目標函數(shù)為最小路徑.為了方便編程和簡化智能算法的迭代過程，本文使用懲罰函數(shù)的方式，將重量的約束與體積約束，加入到成本函數(shù)中.適應度值為成本的倒數(shù)，成本越大，適應度越小.適當調(diào)整α，β的值，滿足各個AGV的載重約束和體積約束.

(6)

(7)

4.2 自適應策略

自適應交叉算子、變異算子

本文采取文獻[11]中，正弦自適應遺傳算法的遺傳算子的求解公式.

(8)

(9)

其中，pc為交叉概率；pm為變異概率；pc1為種群的最大交叉概率；pc2為種群最小交叉概率；pm1為種群的最大變異概率；pm2為種群最小變異概率；fm為種群的最大適應度；fa為種群平均適應度；f′為染色體個體適應度；

自適應遺傳算子隨著適應度的變化而不斷變化，可以很好地提高遺傳算法的收斂速度和性能.

自適應災變算子

傳統(tǒng)的災變算子是固定值，導致對每個算例的適應性不強，需要不斷調(diào)整.

本文提出一種自適應災變算子，它隨著陷入局部極值的代數(shù)的增加，不斷增加交叉概率與變異概率，使整個種群跳出局部最優(yōu)解.

(10)

(11)

(12)

(13)

災變算子的自適應調(diào)整，如圖3所示，在算法迭代初期，種群適應度急劇變化階段，不會發(fā)生作用.在種群陷入局部極值后，隨著陷入極值的時間越長，災變算子使得交叉概率和變異概率不斷增大.

圖3 災變階段交叉概率、變異概率變化量

自適應逆轉(zhuǎn)算子

本文提出一種自適應逆轉(zhuǎn)算子，隨著總迭代次數(shù)的增加，逆轉(zhuǎn)算子不斷改變，使得種群進行逆轉(zhuǎn)操作的概率增大.

(14)

其中，Pi為執(zhí)行逆轉(zhuǎn)操作概率；Pim為最大逆轉(zhuǎn)概率；T為迭代周期；ite為迭代次數(shù).

如圖4所示，在算法的迭代初期，種群的多樣性大，不需要過多的進行逆轉(zhuǎn)操作.在算法的后期或者迭代陷入局部最優(yōu)值時，適當?shù)倪M行逆轉(zhuǎn)操作，既可以增加種群的多樣性，也有利于跳出局部極值.而且，逆轉(zhuǎn)操作使得種群向著更加有利的方向進行進化，容易跳出局部極值.

圖4 逆轉(zhuǎn)操作概率的自適應調(diào)整

4.3 算法基本流程

4.3.1 數(shù)據(jù)預處理

1)剔除重量大或者體積大的任務

分析所有任務點需要的物料的重量與體積，刪除重量很大或者體積很大、無法與其他物料進行一起運輸?shù)奈锪嫌唵?這樣的物料只能單載運輸.形成單載AGV路徑集d_list.之后，智能算法求解多載AGV路徑集合dd_list.

剔除重量大或者體積大的任務，將其組合成單獨的任務隊列，可以減少調(diào)度系統(tǒng)的搜索的維度，使得算法求解的效率更高，速度更快.

2)根據(jù)數(shù)據(jù)提供的x坐標與y坐標，計算直線距離，提前生成距離矩陣，避免在程序計算中重復計算，降低程序的計算量.

4.3.2 調(diào)度模型求解

編碼與解碼

采用實數(shù)編碼的策略.常見的二進制編碼雖然簡單易行，不適合高維、高精度優(yōu)化問題.這里采用實數(shù)編碼.

倉庫的編碼：0，分割各個字符串.例如：任務點1-4為一組，6-9為一組，11-14為一組，編碼后的染色體的編碼字符串，1-2-3-4-0-6-7-8-9-0-11-12-13-14，這就是編碼過程.解碼過程則相反.

選擇

本文采用輪盤賭選擇方式.根據(jù)每個個體的適應度，按照比例進行概率選擇.適應度越大的染色體被選中的概率越大，反之，適應度越小的染色體被選中的個體越小.

交叉、變異

采用兩點交叉方式.隨機選中小于染色體編碼長度的兩個數(shù)，將它與臨近的染色體相同位置進行交換.但是由于采用的是實數(shù)編碼.所以，交叉操作完成之后，相應的染色體內(nèi)部，需要進行調(diào)整.

采用單點變異的方式.因本文采用的是實數(shù)編碼，所以單點變異后，需要進行調(diào)整.

逆轉(zhuǎn)

選出部分種群，根據(jù)設定好的概率(倒序概率，插入概率)，使用逆序排列，插入排列的方式，保留適應度值增大的染色體，否則恢復大原基因排列.這樣做的目的，一是增加種群的多樣性，二是可以向著種群適應度值高的方向進化.

調(diào)整

因采用實數(shù)編碼，除0外的其他實數(shù)應保持數(shù)字的唯一性，當進行交叉變異等操作后，需要進行調(diào)整，來滿足染色體數(shù)字的唯一性.

5 仿真驗證

本文的實驗環(huán)境為：Windows 10+MATLAB 2014b.本文的算例由Solomon[12]提出的算例調(diào)整修改而來，任務數(shù)據(jù)包括位置，重量約束，體積約束初始任務數(shù)據(jù)包括位置，重量約束，體積約束.搭建了一個倉庫點，(N-1)個工作站，在共N個點的環(huán)境.多載AGV能承受負載的最大重量為4，多載AGV能承受負載的最大體積為4.

分別在N為30，60，90 3個規(guī)模下，各做10組實驗，取得3種規(guī)模下，改進的自適應遺傳(IAGA)，標準遺傳算法(Standard Genetic Algorithm，SGA)，自適應遺傳算法(Adaptive Genetic Algorithm，AGA)算法，3種算法收斂的迭代次數(shù)、迭代時間、迭代精度.

分析圖5可知，在相同的迭代次數(shù)下，改進的自適應遺傳算法比標準遺傳算法、自適應遺傳算法收斂速度更快、更加接近最優(yōu)值.

圖5 N=30，各個算法迭代變化趨勢

由表1-表3，比較3種算法在N=30，60，90維度下的的迭代次數(shù)、迭代時間、收斂解，可知，改進的自適應遺傳算法迭代次數(shù)更少、達到收斂的時間更短，收斂解更加接近最優(yōu)解.

表1 N=30，各個算法比較

表2 N=60，各個算法比較

表3 N=90，各個算法比較

6 結(jié) 論

本文中，多載AGV調(diào)度問題是一個添加了物料體積、重量雙重約束的VRP(Vehicle Routing Problem，車輛路徑規(guī)劃問題)問題.本文首先對數(shù)據(jù)進行預處理，降低求解變量的維度，然后使用改進的自適應遺傳算法(IAGA)進行求解，最后，分別在數(shù)據(jù)維度N=30，60，90時，進行多組實驗取平均值.與標準遺傳算法(SGA)、自適應遺傳算法(AGA)相比，改進的自適應遺傳算法收斂快，優(yōu)化效果明顯，收斂精度高.

在求解過程中也發(fā)現(xiàn)一些不足：1)在任務合并尋優(yōu)過程中，迭代時間長，可以進一步改進算法或者調(diào)整參數(shù)來進行加快收斂；2)本文沒有考慮時間約束，在后續(xù)工作中可以加入時間窗約束.