自動化立體倉庫堆垛機路徑優化方法研究

楊增鋼，閆 明，雷 蕾 YANG Zenggang, YAN Ming, LEI Lei

（沈陽工業大學 機械工程學院，遼寧 沈陽 110870）

目前在使用遺傳算法解決路徑優化問題方面，主要分為兩個維度。一是橫向維度：多算法結合；二是縱向維度：將遺傳算法升級。本文從橫向、縱向兩個維度同時對現有算法進行改進。在縱向維度，將現有自適應遺傳算法中交叉、變異公式進行改進，形成IAGA 算法，以解決AGA 在進化早期出現“停滯”的問題。在橫向維度，將IAGA 與SA 結合形成ASAGA 算法，以提高算法的精確度和收斂速度。

1 堆垛機調度建模

1.1 復合作業模式

復合作業方式工作過程為：從出入庫站臺O 點出發運行到第一個貨位點進行入庫操作，然后直接運行到第二個貨位點，進行出貨操作回到出入庫站臺，如此便完成了一組出入庫作業。如圖1 所示。

1.2 建立數學模型

考慮復合作業的實際工作情況，為使研究更方便，提出假設：

（1） 忽略堆垛機起速、降速時間；

（2） 堆垛機運動分解成兩個正交方向的運動；

（3） 堆垛機收到一組指令，其中入庫與出庫指令數量均為k。堆垛機一次出入庫作業時間為：

其中：tOA為入庫運行時間，tAB空載運行時間，tOB出庫運行時間。

由圖1 可知，任意一組出入庫組合任務中，無論其處于哪一個順序位置上，OA 與OB 的距離是固定的，即tOA、tOB固定，而tAB（即空載時間） 卻會因為相鄰的入庫與出庫貨位點的不同選擇而發生變化，所以選擇合適的出入庫順序使空載運行時間最短才是問題的關鍵。

采用單向配對的方式進行出入庫任務處理，設A= ｛A1,A2,…,Ak｝，B= ｛B1,B2,…,Bk｝兩個有序序列，Ak表示第k 個入庫貨位，Bk表示第k 個出庫貨位，則復合作業運行路徑為：O→A1→B1→O→A2→B2→O→…→Ak→Bk。作業簡化成如下方式：入庫貨位點集合A 按照訂單自然順序排列，作為待配對位置點，對出庫貨位點進行排序，使得總運行時間最小。

設A 中第i 個入庫貨位點的坐標為（xi, yi），重新排序后的B 中的第i 個出庫貨位點坐標為）。數學模型為：

式中：Vx、Vy為堆垛機水平、豎直方向運行速度，L 為貨格的寬度。

2 自適應模擬退火遺傳算法

2.1 自適應遺傳算法設計步驟

（1） 編 碼

采用順序編碼，整數的不同排列順序即表示基因在染色體上的不同排列。

（2） 選擇算子

本文采用輪盤賭法。基本思想：將個體適應度值占全部個體適應度總值的比例作為進入下一代的概率，概率公式為：

式中：f （xi）為個體i 的適應度值，為當代所有個體適應度值總和。

（3） 交叉、變異算子

a.交叉、變異方式：

采用兩點交叉方式：隨機選擇兩個交叉點的位置，兩個交叉點之間的染色體片段即為交叉片段，兩個父代交換交叉片段，其他位置上的基因按原來順序且不重復原則排列在染色體上。

例如：

父代A （1,3,5,2,6,4 ）→子代A （3,5,2,1,6,4）

父代B （4,5,2,1,6,3 ）→子代B （4,3,5,2,1,6）

變異方式：隨機選取兩個基因位置進行交換。

例如： （1,3,5,2,6,4 ）→（1,6,5,2,3,4）

b.交叉、變異概率：

在Srinivasa[1]提出的自適應交叉、變異概率公式基礎上做出改進，改進后公式如下：

由改進后的公式，避免了出現交叉、變異概率為0 的現象，進化早期保證當前最優個體能夠繼續進化，保證了全局收斂性。式中，fi表示要進行交叉運算的兩個較大個體的適應度，K1、K2、K3、K4為常數，fmax為當代最大適應度值，favg為適應度平均值。

2.2 模擬退火算法

模擬退火算法具有跳突性，在于其Metropolis 準則：當個體A 為當前最優解時，算法不會將其直接輸出為最終解，而是在其鄰域隨機擾動產生一新個體B。若B 適應度大于等于當前最大適應度fi，則直接接受該個體，并將B賦予A；若B 的適應度小于fi，則將根據Metropolis 準則：隨機產生一個數Z∈（0,1 ），若Z≤exp （Δf/KT ）則接受B；反之，則不接受。其中，K為物理學常量，T 為當前溫度。

2.3 自適應模擬退火遺傳算法

為了徹底克服遺傳算法過早收斂的問題，將改進后的自適應遺傳算法（IAGA） 與SA 結合。結合方式如圖2 所示：

圖2 ASAGA 流程圖

結合方式：將遺傳算法經交叉變異后，將新種群中每一個體均進行模擬退火操作，然后求解出每一個體的適應度Fi，并將這些個體組成新的組合F=max （F1,F2,…,Fn），當作本代一組最優解，作為下一代的初始種群。

3 仿真分析

3.1 參數設置

參數：貨架：長100m，高30m，單元貨格高度1m，寬度1m，共3 000 個貨位；堆垛機：水平速度Vx=1.5m/s，豎直速度Vy=0.5m/s；隨機生成40 條貨單，30 條入庫貨單，30 條出庫貨單。

入庫貨單坐標： （2,1 8 ）（5,3 ）（20,16 ）（28,23 ）（35,12 ）（36 ,9 ）（42,28 ）（50,26 ）（58,24 ）（63,10 ）（64,15 ）（9,2 0 ）（12,20 ）（18,16）（29,13 ）（44 ,2 ）（59,17 ）（70,23 ）（72,15 ）（75 ,7 ）（79 ,1 ）（82 ,8 ）（84,30 ）（84 ,8 ）（89 ,2 ）（92,30 ）（98,21 ）（93 ,3 ）（99 ,8 ）（100,28 ）；

出庫貨單坐標： （3,5 ）（12,14 ）（17,21 ）（24,29 ）（29 ,7 ）（35,28 ）（43 ,6 ）（53,13 ）（60 ,2 ）（64,30 ）（66 ,2 ）（6,1 9 ）（14,25 ）（14,14）（26,30 ）（37,28 ）（38 ,2 ）（44,10 ）（47 ,9 ）（54,29 ）（65,18 ）（71,17 ）（76,13 ）（79,20 ）（80 ,5 ）（81,21 ）（88,10 ）（90 ,1 ）（93,30 ）（95 ,9 ）。

將出庫貨單依次編號1~30。種群規模N=100，初始溫度T0=100，最終溫度Tf=0.01，降溫速率k=0.98，內部循環次數取50。

3.2 結果分析

使用Matlab 軟件分別對各種算法運行20 次，分別取四種算法中最能代表結果平均值的一組數據，如圖3 所示。

圖3 四種算法最大適應度迭代曲線

由圖3 看出，ASAGA 求解結果最接近理論最優值，適應度為0.000 92，即堆垛機最短作業時間為1 117s，貨位出庫順序為12→1→2→4→18→7→16→6→20→19→8→3→13→14→5→17→21→24→22→23→9→25→15→27→11→10→26→28→30→29。

從縱向角度分析。IAGA 能夠在算法進化初期避免出現陷入局部最優的現象，收斂速度有明顯的提升，精確度也有一定幅度的提高。從橫向角度分析。ASAGA 吸取了IAGA 全局搜索性強和SA 局部最優跳脫性的優點，在精確度和收斂速度上均有所提高。

4 結束語

本文研究自動化立體倉庫堆垛機復合作業路徑優化問題，建立數學模型，并使用SA、AGA、IAGA、ASAGA 四種算法求解，得到了最佳路徑優化方案。并通過結果分析，證實了IAGA 能夠解決AGA 在進化早期陷入局部最優的問題，ASAGA 能夠在算法精確度、收斂速度兩方面較SA、IAGA 均有一定提高，進而提高了倉庫效率，降低了成本。