王長輝

（江蘇大學(xué)汽車與交通工程學(xué)院，江蘇 鎮(zhèn)江 212000）

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

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

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

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

圖1 傳統(tǒng)堆垛機運行速度示意圖

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

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

假設(shè)貨物的初始位置O為（0，0），沿直線OD的速度v采用變加速度的方法（如圖3），在保證貨叉上貨物穩(wěn)定的前提下，實現(xiàn)雙工位堆垛機出入庫復(fù)合作業(yè)一個環(huán)節(jié)運行時間的優(yōu)化。

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

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

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

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

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

圖4 加速時貨物平衡穩(wěn)定的受力圖

進一步推導(dǎo)可得：

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

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

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

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

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

2 雙工位堆垛機自動存取路徑數(shù)學(xué)模型

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

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

圖6 雙工位堆垛機復(fù)合作業(yè)中“存存取取”可能的路徑組合圖

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

3 蟻群-改進遺傳算法的設(shè)計

3.1 蟻群算法

假設(shè)t時刻，螞蟻k由一端點i轉(zhuǎn)移到另一端點j的概率為[16]：

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

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

3.2 蟻群-改進遺傳算法

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

1）編碼

采用順序編碼的方法，每一個貨位都進行編碼，且順序不允許重復(fù)。設(shè)入庫任務(wù)序列為P={1，2，3，4，5，6，7，8}，出庫任務(wù)序列為Q={3，8，1，5，7，6，2，4}，假設(shè)復(fù)合作業(yè)采取“存存取取”的方式，則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）適應(yīng)度函數(shù)確定

目標函數(shù)為時間函數(shù)，優(yōu)化的問題是求解時間函數(shù)的最小值，目標函數(shù)與適應(yīng)度函數(shù)值成反比關(guān)系，因此將適應(yīng)度函數(shù)設(shè)置為目標函數(shù)的倒數(shù)：

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

3）產(chǎn)生初始種群

利用蟻群算法產(chǎn)生較優(yōu)異的初始種群，步驟如下：

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

步驟2：設(shè)置循環(huán)次數(shù)滿足N=N+1，同時設(shè)置螞蟻禁忌表索引號為k=1；

步驟3：k=k+1；

步驟4：利用狀態(tài)轉(zhuǎn)移概率公式（9）得到螞蟻k爬到位置j的概率值；

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

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

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

步驟8：若滿足結(jié)束條件，則循環(huán)結(jié)束，并輸出計算結(jié)果；否則清空禁忌表并跳轉(zhuǎn)到步驟3。

4）改進選擇操作

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

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

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

5）改進交叉操作

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

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

6）變異操作

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

圖8 變異操作過程圖

7）算法停止準則

設(shè)置算法遺傳代數(shù)在200代后停止。

4 數(shù)值實驗結(jié)果與分析

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

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

根據(jù)路徑自動化存取原則，為了簡便分析，按照復(fù)合作業(yè)“存存取取”方式進行分析；已知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仿真優(yōu)化雙工位存取路徑

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

圖9 貨物入庫出庫任務(wù)分布圖

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

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

5 結(jié)束語

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

圖11 優(yōu)化前“存存取取”路徑組合圖

圖12 優(yōu)化后“存存取取”路徑組合圖