基于蟻群-改進遺傳算法的雙工位堆垛機存取路徑優化研究

王長輝

（江蘇大學汽車與交通工程學院，江蘇 鎮江 212000）

自動化立體倉庫主要由計算機控制系統、堆垛機、貨架、出入庫站臺組成，由計算機控制系統發出指令控制堆垛機在巷道內來回運動，進行出入庫作業[1]。傳統的堆垛機主要是單工位的，一次入庫或出庫作業只能承載一個貨物單元，作業效率不高；而雙工位堆垛機一次入庫作業或出庫作業可以承載兩個貨物單元，提高倉庫周轉率[2]。如何提高貨物的出入庫作業效率是很多學者研究的重要內容，堆垛機的作業路徑是否合理對出入庫的效率有很大的影響。文獻[3]采用優化算法對建立的堆垛機進行出入庫作業的數學模型求解，得到了最短路；文獻[4]利用啟發式算法對貨物出入庫作業時間模型進行求解；文獻[5-9]采用遺傳算法對貨物出入庫路徑優化進行研究，但是考慮的因素單一，模型相對簡單；文獻[10]通過分析立體倉庫中堆垛機的工作特點與運行情況，提出了基于混合蟻群粒子群算法的路徑優化方法；文獻[11]建立了堆垛機在單周期和雙周期下作業時最短行程時間數學模型，利用遺傳蟻群算法對堆垛機的數學作業模型進行了分析和求解；文獻[12]采用了改進的遺傳算法求解堆垛機作業路徑優化問題；文獻[13-15]對堆垛機作業的路徑選擇和存儲策略分析，提出優化路徑的搜索方法。綜上所述，針對堆垛機作業路徑優化的問題，目前研究重點集中在兩個方面：路徑優化數學模型和求解方法。但是大部分路徑優化數學模型沒有考慮堆垛機啟動和制動的時間，由于貨叉上的貨物本身具有慣性，堆垛機的加速與制動不宜過大，因此堆垛機的加速與制動時間不會很小，而且在多次出入庫作業累加后，加速與制動時間總和將變得很大。因此忽略不計堆垛機的啟動與制動時間，將對模型的精確計算產生誤差，從而影響雙工位倉庫的自動化精度；目前常用的求解方法是智能尋優算法，但是大部分智能尋優算法存在容易陷入局部最優和搜索效率低的缺陷；另外大部分學者都是選擇單工位堆垛機進行研究，單工位堆垛機存取量小、存取效率也不高。

為此，該文的研究對象是雙工位堆垛機進行出入庫作業時的最優路徑，在考慮了加速與制動對貨物穩定影響的基礎上，提出了一個變加速度的雙工位堆垛機運行方法，提出自動存取路徑數學模型以及蟻群-改進遺傳算法處理多任務的存取路徑優化的問題，實現提高貨物存取效率的目的。

1 雙工位堆垛機運行方法分析與改進

傳統堆垛機運行方法如圖1所示。其水平速度vx與豎直速度vy均為固定值，但這種方法對于貨物位置較遠、存取路徑較長的作業，速度固定就顯得效率很低。

圖1 傳統堆垛機運行速度示意圖

將固定的水平與豎直速度改為水平、垂直速度隨角度θ變化；雙工位堆垛機出入庫作業運行速度改進方案如圖2所示，這里的角度θ由初始位置與目標位置決定，貨位的長度和高度分別為L和H。

圖2 雙工位堆垛機運行速度改進圖

假設貨物的初始位置O為（0，0），沿直線OD的速度v采用變加速度的方法（如圖3），在保證貨叉上貨物穩定的前提下，實現雙工位堆垛機出入庫復合作業一個環節運行時間的優化。

圖3 雙工位堆垛機運行變加速度示意圖

如圖3所示，雙工位堆垛機的速度v隨時間t變化的數學模型為：

式中，r為數學模型中的二次項系數，且r>0，tD為到達目標位置D（i，j）的時間，且 0＜t＜tD。進一步求導，可得到加速度a的數學表達式為：

但是，如何保證貨叉上的貨物在沿直線OD作變加速度運行過程中始終保持穩定平衡，是實現堆垛機出入庫運行時間優化的一個重要問題。假如堆垛機上的貨物受力平衡，如圖4所示。

則貨物由于慣性受到貨叉的水平推力應小于最大靜摩擦力fmax，直線OD與水平面的夾角θ是有方向的，其范圍為[-π/2，π/2]。則由圖4可知，貨物相對于貨叉始終保持靜止的關系可表示為：

圖4 加速時貨物平衡穩定的受力圖

進一步推導可得：

μ為摩擦系數，F2為變加速度運動的反作用力，任意F2都必須滿足上述公式，則F2的最大值也必須滿足，將F2的最大值代入不等式，化簡得到：

根據公式（6）可知，除了垂直上升之外，tD與兩個貨物之間的距離沒有關系，只與兩個貨位與水平面的角度有關。

雙工位堆垛機在多任務存取情況下，假設先不考慮θ=π/2的情況，由公式（6）求導可得：

由于-π/2≤θ＜arctan（1/μ），因此cosθ-μsinθ>0。設 g（θ）=sinθ+μcosθ，則其導數為g′（θ）=cosθμsinθ>0 ，則 g（θ）單調遞增。因此當 g（θ）>0 時，即-arctanμ＜θ＜arctan（1/μ）時 ，tD（θ）單調遞增；當g（θ）＜0 時，即 -π/2＜θ＜-arctanμ ，則 tD（θ）單調遞減，如圖5所示。在該文中，設置參數 μ=0.05，從貨位位置來看，tanθ=-0.05就相當于水平移動，即θ=0。因此當-π/2≤θ＜0時，時間函數 tD（θ）單調遞增；當 0＜θ＜arctan（1/μ）時，時間函數 tD（θ）單調遞減。由上述分析可知，雙工位堆垛機作業時間與角度的絕對值成反比。

圖5 雙工位堆垛機運行時間函數變化圖

2 雙工位堆垛機自動存取路徑數學模型

采取復合作業存取方式，雙工位堆垛機一次復合作業分別訪問2個存貨貨位和2個取貨貨位，最后回到初始位置O的方式。設出入庫初始位置為O（0，0），貨位對應的坐標為D（y，z），其中y表示貨位所在的列，z表示貨位所在的層。

為了方便構建出改進的自動存取路徑數學模型，假設出庫任務與入庫任務數量相同，且任務數量都為偶數。在雙工位堆垛機出入庫復合作業中，設入庫任務有2N個，分別表示為（P1，P2，…，P2N），對應的坐標為 （yp1，zp1），（yp2，zp2），… ，（yp2N，zp2N）；同樣，出庫任務有2N個，分別表示為（Q1，Q2，…，Q2N），對應的坐標為 （yq1，zq1），（yq2，zq2），… ，（yq2N，zq2N）。在一個出入庫行程周期中，兩個入庫任務（P2k-1，P2k）與兩個出庫任務 （Q2k-1，Q2k）進行匹配，其中 k=1，2，…，N。根據第一步先存貨、貨叉上貨物不超過兩個的原則，則有存存取取、存取存取兩種情況，以存存取取為例，如圖6所示，總共有OP2k-1P2kQ2k-1Q2kO、OP2k-1P2kQ2kQ2k-1O、OP2kP2k-1Q2k-1Q2kO、OP2kP2k-1Q2kQ2k-1O 4種組合情況。

圖6 雙工位堆垛機復合作業中“存存取取”可能的路徑組合圖

完成一次復合作業的過程中其中一個可能路徑OP2k-1P2kQ2k-1Q2kO需要的總時間為：

3 蟻群-改進遺傳算法的設計

3.1 蟻群算法

假設t時刻，螞蟻k由一端點i轉移到另一端點j的概率為[16]：

式中，τij（t）表示螞蟻經過路徑（i，j）后的信息殘留量，nij（t）為啟發信息量，α與β表示特定的影響力因素，allowedk表示定位螞蟻k下一步運動中被允許選擇的剩余貨位集合。經過n個時刻后，路徑（i，j）上的信息素調整公式為：

式中，ρ為信息量的保留度，Δτijk為一次循環中第k只螞蟻在路徑（i，j）上留下的信息量，Δτij表示螞蟻群在一次循環中留下的信息量，m表示螞蟻的數量。

3.2 蟻群-改進遺傳算法

利用蟻群算法生成優異初始種群，優化改進遺傳算法對雙工位堆垛機作業路徑進行尋優。由蟻群算法優化初始種群，由改進遺傳算法優化選擇算子、交叉算子與交叉策略，提高了優秀基因快速占據統治地位的效率，減少或避免了不合法的染色體的出現。利用蟻群-改進遺傳算法求解雙工位堆垛機作業路徑優化問題的具體步驟為：

1）編碼

采用順序編碼的方法，每一個貨位都進行編碼，且順序不允許重復。設入庫任務序列為P={1，2，3，4，5，6，7，8}，出庫任務序列為Q={3，8，1，5，7，6，2，4}，假設復合作業采取“存存取取”的方式，則2個入庫與2個出庫配對，則第一個周期為W1={P1，Q1}={（1，2），（3，8）}，第二個周期為W2={P2，Q2}={（3，4），（1，5）}，第三個周期為 W3={P3，Q3}={（5，6），（7，6）}，第四個周期為W4={P4，Q4}={（7，8），（2，4）}。

2）適應度函數確定

目標函數為時間函數，優化的問題是求解時間函數的最小值，目標函數與適應度函數值成反比關系，因此將適應度函數設置為目標函數的倒數：

式中，Ffitness為個體的適應度函數，FT為雙工位堆垛機存取過程中一個可能路徑的時間函數，具體函數詳見公式（6）與（8），tanθ＜12.5＜1/μ，因此設靜摩擦系數 μ=0.05，二次項系數r=0.25，重力常數g=10 N/kg。

3）產生初始種群

利用蟻群算法產生較優異的初始種群，步驟如下：

步驟1：初始化參數。設置初始循環次數為N=0 ，設置最大循環次數為 Nmax，路徑（i，j）的初始化信息量為τij=const，設置初始時刻的信息量為0，同時將m只螞蟻隨機放在n個位置上；

步驟2：設置循環次數滿足N=N+1，同時設置螞蟻禁忌表索引號為k=1；

步驟3：k=k+1；

步驟4：利用狀態轉移概率公式（9）得到螞蟻k爬到位置j的概率值；

步驟5：根據步驟4計算得到的狀態轉移概率值，將螞蟻移動到具有最大狀態轉移概率的位置上，同時把該位置信息存儲到禁忌表中。

步驟6：若沒有訪問完集合Wi中的所有位置，即k＜m，跳轉至步驟3；否則轉步驟7；

步驟7：根據公式（10）更新每條路徑上的信息量；

步驟8：若滿足結束條件，則循環結束，并輸出計算結果；否則清空禁忌表并跳轉到步驟3。

4）改進選擇操作

使用兩種選擇算子，以使適應度高的基因更快速占據統治地位，假設種群大小為M，個體的適應度值為Fi，若第一種算子采用比例選擇算子，采用輪盤賭模型對種群做出選擇。比例選擇算子的選擇概率為：

step1隨機抽取一個在[0，1]之間的數s，再隨機抽取一個在[0，1]區間的概率p，若 p≤0.5，則進入step2，若 p>0.5 ，則進入step3；

step2 如果 s≤p1+p2+...+pi，則選擇個體 s，否則不選擇；

5）改進交叉操作

改進交叉算子采用的是部分映射交叉算子，首先對由多個個體所組成的群體進行兩兩隨機配對。設群體的大小為M，則共有[M/2]個配對組，其中y=[x]為高斯取整函數。首先，將配對的兩個個體中的兩列基因隨機交叉，同時確定基因之間的映射關系，然后利用映射關系合法化兩個個體的后代，如圖7所示。

圖7 改進交叉算子進行基因交叉操作

6）變異操作

在個體的基因列上隨機互換兩個基因點的位置，從而進行變異操作。例如，隨機變異操作將個體的第2個基因與第6個基因位置互換，結果如圖8所示。

圖8 變異操作過程圖

7）算法停止準則

設置算法遺傳代數在200代后停止。

4 數值實驗結果與分析

采取的實驗方案：隨機選擇自動化倉庫的一排貨架，其中，這一排貨架有10層12列，一共120個貨位，每個貨位的規格為長L=2m，高H=2.5m，雙工位堆垛機的運行速度改進方法如上文所述，其中二次項系數取r=0.25。利用蟻群-改進遺傳算法求解雙工位堆垛機自動化存取路徑優化問題，同時設置算法的主要參數如下：α=1，β=5，ρ=0.5，Nmax=1 000，遺傳種群迭代次數為200代，交叉概率為0.9，變異概率為0.05，選取8個入庫任務與8個出庫任務進行仿真實驗。另外，在研究路徑優化過程中，忽略雙工位堆垛機貨叉存取貨物的時間。

1）確認實驗存取貨位坐標位置

根據路徑自動化存取原則，為了簡便分析，按照復合作業“存存取取”方式進行分析；已知8個存貨貨位的坐標為 P={P1，P2，P3，P4，P5，P6，P7，P8}={（4，8），（7，6），（5，2），（12，4），（3，5），（9，10），（10，2），（1，7）}，同時 8個取貨貨位的坐標為 Q={Q1，Q2，Q3，Q4，Q5，Q6，Q7，Q8}={（9，5），（3，6），（7，2），（1，4），（10，9），（5，7），（1，9），（12，3）}，存取貨位的位置如圖9所示。

2）Matlab仿真優化雙工位存取路徑

利用提出的算法，結合改進的自動化復合作業的“存存取取”時間模型，在給定雙工位自動化立體倉庫的相關數據信息基礎上，對雙工位堆垛機的存取路徑進行仿真優化。其中，將蟻群-改進遺傳算法進行路徑優化的結果與基本遺傳算法的優化結果進行對比，兩者的迭代曲線對比圖如圖10所示。由圖可知，在兩種算法的優化下，雙工位堆垛機路徑優化的時間目標函數值都隨著迭代次數增加而不斷減小；當遺傳算法的種群迭代到42代左右接近最優解，但是還未達到平穩狀態，在迭代至80代，達到最優解。相比于提出的算法，遺傳算法的種群在迭代到42代后的最優解只達到了局部最優解，而提出的算法則迭代到18代后就達到最優解。因此，通過仿真驗證，蟻群-改進遺傳算法相比于基本遺傳算法不僅提高了迭代效率，且提升了最優解的準確率。

圖9 貨物入庫出庫任務分布圖

圖10 遺傳算法與蟻群-改進遺傳算法的仿真結果對比圖

路徑優化前，可能采用隨機組合的方式，優化前堆垛機多任務存取路徑分布如圖11所示。有很多路徑很雜亂，導致有很多角度很小的運行路徑，需要的運行時間更長。路徑優化后的堆垛機多任務存取路徑組合圖如圖12所示，與優化前組合圖作對比，發現優化后的路徑組合圖路徑角度明顯比優化前大。根據該文改進的模型，除了角度θ=π/2時，路徑時間函數只與兩個貨物之間的角度有關，與經過的路徑大小沒有關系。優化后的路徑組合明顯比優化前的用時少，可以明顯地看出每個周期路徑縮短，相對應地完成任務所需時間也減少，進而提高倉庫運轉效率。

5 結束語

傳統雙工位堆垛機采用的固定運行速度策略，忽略了影響貨物穩定的加速與制動，且運行效率低下。針對上述問題，提出一種基于變加速度的雙工位堆垛機出入庫復合作業存取路徑的運行方法；該方法考慮了加速與制動對貨物穩定的影響問題，在保證堆垛機貨叉上貨物穩定的同時，極大地提高了雙工位堆垛機路徑的運行效率。另外，針對傳統遺傳算法對路徑優化研究的問題，提出一種基于蟻群-改進遺傳算法對雙工位復合作業路徑尋優的方法，提高了雙工位堆垛機復合作業路徑優化的效率與準確率。該方法采用蟻群算法生成遺傳算法的優異初始種群，并通過改進遺傳算法對雙工位自動存取路徑進行尋優。結果表明，相比于傳統遺傳算法，蟻群-改進遺傳算法可以更快、更準確地實現雙工位復合作業路徑的尋優。

圖11 優化前“存存取取”路徑組合圖

圖12 優化后“存存取取”路徑組合圖