遺傳算法在堆垛機路徑優化上的應用研究

張新陽，陳 玉，王 鵬

(安徽工程大學 機械與汽車工程學院，安徽 蕪湖 241000)

隨著自動化生產技術的發展，企業在生產制造方面的競爭加大，產品的運輸、檢查及存儲方面所占的比重越來越高。在產品的存儲方面，自動化立體倉庫的存儲效率主要取決于堆垛機的運行速度、貨位的優化存取[1]。有效解決貨物在存取中效率低的問題，可以大大提高自動化立體倉庫的工作效率。貨架作為自動化立體倉庫的存儲部分，是倉儲物流中一個重要環節[2]，合理安排貨位的出入庫分配原則和分配策略，能有效降低搬運過程中的損耗，降低物流業務成本，提高物流行業收益。

1 自動化立體倉庫模型設計

貨位優化的目的是根據某一種貨位分配原則，使得每一個貨位能夠合理且高效率地放入到合理的位置中。在自動化立體倉庫中，貨位的分配控制對象主要有3個，即堆垛機、貨架和貨架貨位。通常自動化立體倉庫主要由貨架、堆垛機、運送工具以及控制臺4個部分組成[3]。貨架是貨物存儲的單元格整體；堆垛機是貨物存儲過程中的執行器；AGV小車或其他運送工具是貨物輸送橋梁；控制臺是立體倉庫的操作平臺和觀察平臺。自動化立體倉庫結構平面圖如圖1所示。

圖1 自動化立體倉庫結構平面圖

立體倉庫由計算機控制，先將立體的程序通過PLC輸入計算機中，按照操作執行出庫、入庫等動作。當一批生產任務到達時，計算機按照指令順序依次來執行出入庫任務。由于出入庫動作執行的順序不一樣[4]，堆垛機路徑也不同，因而堆垛機每次執行任務的時間也不同。

目前的自動化立體倉庫存取的貨物量較大，同時存在入庫和出庫同時進行的復合作業。復合作業要比單一作業的效率高很多。堆垛機存取路徑如圖2所示。對于復合作業，O為堆垛機周轉平臺，A點為儲存貨物點，B點為取出貨物點，堆垛機所走的路徑為O→A→B→O。假設自動化立體倉庫每排共有m層n列，離地面最近的一層為第一層，離出入口最近的列為第一列。設O、A、B的坐標分別為O(0,0)、A(a,b)、B(c,d)。

圖2 堆垛機存取路徑

(1)對于貨物復合作業，根據自動化立體倉庫的出入效率原則，建立數學模型：

(1)

(2)

式中，f1(x,y)為每個托盤上貨物的質量與其所在層的乘積之和；tij(x,y)為貨物從O點出發執行相應任務后回到O點所需要的時間；vx為堆垛機水平運行速度；vy為堆垛機垂直運行速度；l為貨格長；h為貨格高；pij∈(0,1)為第i行j列的貨物周轉效率。

(2)根據貨物上輕下重原則，由此可建立數學模型：

(3)

式中,Gij為貨架第i行j列的商品重量；m、n表示立體倉庫每排共m層n列。

(3)堆垛機存取貨物是多目標優化求解問題，通過對兩個目標函數賦予權重參數，使得多目標函數變成單目標函數進行求解。為了方便計算求解，兩個目標函數權重參數均為0.5。將上述目標函數進行變換可得到函數：

f3=0.5·(f1+f2),

(4)

在賦予權重參數后，可得到堆垛機最終的目標函數：

(5)

2 立體倉庫貨位優化模型算法設計

自動化立體倉庫出入庫路徑優化通過研究其出入庫任務的執行順序，并為每一個貨物分派貨位，以提高立體倉庫的效率和利用率[5]。

2.1 遺傳算法介紹

遺傳算法是近幾年迅速發展的一種高效的優化算法。算法對目標函數的形狀、連續性等無特殊要求，條件要求不嚴格，且具有很好的全局搜索能力、良好的容錯能力以及適應性。遺傳算法不只限于局部搜索僅僅記錄一個解，而是記錄一個群體，它可以同時記錄多個解。考慮到遺傳算法在小規模的多目標優化項目中具有運算速度和精度上的優勢,采用遺傳算法對立體倉庫的貨位進行優化[6]。

2.2 遺傳算法設計

通過建立模型、設計編碼、確定適應度、遺傳操作以及仿真進行立體倉庫貨物分配算法設計。在整個貨位優化過程中，堆垛機在貨品和貨位之間起著紐帶作用，即每一個貨品都是通過巷道堆垛機被運送到優化后的貨位上。入庫貨位優化的研究對象就是貨品、貨位和巷道堆垛機。模型的建立需要將研究對象的客觀屬性抽象化，從而全面考慮貨品、貨位和巷道堆垛機三者之間的關系，找出各個實體之間的相關屬性。為了求解方便，不考慮貨物的大小以及形狀。

(1)確定編碼。遺傳算法編碼就是其中的轉化方法，編碼的好壞將極大地影響立體倉庫的響應速度、貨位優化的復雜程度以及貨位優化的效果等。由于立體倉庫屬于多目標組合優化問題，通過對比發現整數編碼更加有效，因而選用整數編碼。具體方式如下：①一組貨位的優化由一條染色體代替；②染色體上的每個基因數與立體倉庫優化的貨位區間中貨位數相對應，每條基因可由多個數字組合而成；③染色體上的每個基因代表著一個貨位，該基因所在染色體的位置代表貨位在該處的編碼。研究的貨位為單獨的一個貨架，因此采用兩個整數x、y表示行和列。假設目前有4個貨物需要存放在優化區間內，相應的編號如表1所示。由表1可知，(1,1)表示將編號為1的貨物存放在坐標為(1,1)的貨位中。(1,1)(2,3)(3,2)(4,1)表示一條染色體上的基因，把該基因放在一起表示一條染色體，即一組貨位的最優解。

表1 貨位對應編碼

貨物編碼對應數字編碼1(1,1)2(2,3)

貨物編碼對應數字編碼3(3,2)4(4,1)

12345…貨物(1,1)(2,3)(3,2)(4,1)(5,2)...貨位

(2)種群初始化。種群的數目設定為隨機，種群數目越大，遺傳算法得到最優解的機會就越小。考慮執行效率和結果，將種群的數目設定為100。

(3)適應度確定。遺傳算法中對適應度函數的要求為非負，且適應度要求越大越好。通常會將目標函數作為適應度函數，但由于選擇策略的影響，需要適應度函數非負遞增。本節所研究的貨位優化目標為兩個，并且都要求取最小值，且函數值非負。對于求最小值的函數問題，目標函數和適應度函數可以通過以下變化：

(6)

對于Cmax為一個較大的數，?f(x),Cmax≥f(x)。Cmax取值可以由以下方法取得：①預先設定較大固定值；②當代所得的最大適應值；③當前或幾代中最大適應值。

由于要求的目標函數綱量不同，對于目標函數直接進行加權求和顯然沒有意義。因此解決綱量不同帶來的影響，需要對目標函數進行去綱量處理。

對目標函數進行如下的線性變換法轉換：

fk=αfk+b

其中a,b的線性比例如下：

(7)

由式(7)得到去綱量后的適應度函數：

(8)

式中，k表示第幾個目標函數。

對式(8)取倒數，得到適應度函數：

(9)

為了使得上述函數能夠在區間(0,1)中，對于遺傳算法通常采用正規標定的方法：

(10)

γ∈(0,1)在此區間內，避免分母為0；將選擇方式調整為隨機選擇。通過去綱量和正規標定處理后，目標函數均為無綱量和映射在(0,1)區間的函數。

將多目標函數取權重wk且權重之和為1，最終將兩個適應度函數化為一個適應度函數：

(11)

式中,wk為目標函數綱量；Fk為一個適應度函數。

(4)選擇策略。選擇算子：遺傳算法的選擇影響著種群的發展，遺傳算法中較常用的方法主要有輪盤賭選擇法、隨機遍歷抽樣法等。由于輪盤賭選擇法具備操作簡單，不同的選擇算子會使算法表現不同的性能的特點，采用輪盤賭選擇算子。假設種群規模為N，個體的適應度為Fk，那么該個體可能被選中的概率為P。

(12)

由式(12)可以看出，采用輪盤賭的方法與該個體的適應度有關，適應度越大，則越容易遺傳到下一代中。

交叉算子：采用較多的單點交叉法對染色體進行交叉運算，交叉原理如圖3所示。

圖3 遺傳算法交叉原理

變異算子：遺傳算法通過交叉操作后得到大量相同的染色體，很容易收斂到局部最優解。所以在遺傳算法得到的最優解中隨機選擇兩個基因進行位置交換；計算換位后的染色體適應度是否減少或者增加，如若發生減少則取用換位后的個體取代原個體。重復上述兩個步驟，達到事先規定的交換次數。

2.3 貨位優化仿真及求解

(1)貨位優化模型建立[7]。建立的立體倉庫貨架貨位10排10列共計100個貨位，每個貨物托盤所占貨位均為1，同時有5種貨物需要入庫，相關參數如表2所示。

表2 貨物參數

(2)仿真結果對比分析。用Matlab遺傳算法求解，所得優化前后結果分別如圖4、圖5所示。由圖4、圖5可知，通過不斷迭代，優化后的曲線較未優化的曲線下降更為平緩。優化后的貨位在240代以后目標函數基本沒有變化，迭代完成時的值為4.45×105，迭代時間為104.562 s。優化前的貨位目標函數在275代之后基本沒有變化，迭代完成時的值為4.68×105，迭代時間為204.529 s。

圖4 優化前貨位求解結果 圖5 優化后貨位求解結果

3 立體倉庫堆垛機路徑優化

堆垛機的作業過程就是從起始點到目標點完成取送貨后再回到起始點的過程。堆垛機執行該工作的過程所走的軌跡即為堆垛機揀選路徑。立體倉庫堆垛機的路徑優化[8]即實現堆垛機在揀選貨物時行走路程最短。

3.1 立體倉庫揀選貨物作業建模

對于堆垛機揀選問題的研究，通常將其假設為商旅問題進行描述：有N個城市，一個旅行商從起始城市出發，到另一個城市買貨，之后到其余未曾到過的城市買貨，最終N個城市全部買完回到起始城市，要求旅行商所走路徑最短。用數學模型可表達為：

(13)

式中,Si為城市號；d為城市之間距離。

堆垛機在揀選作業時，程序給予作業任務，堆垛機根據作業任務從起始點處出發，依次將作業清單上的任務揀選完成后回到揀選作業區，以便執行下次任務。

3.2 揀選路徑優化計算仿真

利用改進后的遺傳算法針對企業要求進行算法求解。揀選貨物坐標參數如表3所示。根據表3中的參數，利用Matlab進行求解計算，最終得到優化結果如圖6所示。通過Matlab計算得到結論：優化前一批貨物從開始揀選到揀選結束所用時間為385.71 s，改進后所用時間為235.69 s。堆垛機的作業時間明顯縮短，提高了堆垛機的工作效率。

表3 揀選貨物坐標參數

圖6 優化前后路徑

4 結論

通過對立體倉庫的分析，解決自動化立體倉庫的貨位優化問題和堆垛機路徑優化問題[9]。通過算法選擇，確定優化目標和約束條件，建立相應的數學模型，結合遺傳算法思想，并對遺傳算法進行一定的優化，利用Matlab求解。最后，通過對比優化前后的結果，實現了自動化立體倉庫的貨位優化和堆垛機路徑優化[10]，提高了自動化立體倉庫工作效率。