遺傳算法在堆垛機(jī)路徑優(yōu)化上的應(yīng)用研究

張新陽，陳 玉，王 鵬

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

隨著自動(dòng)化生產(chǎn)技術(shù)的發(fā)展，企業(yè)在生產(chǎn)制造方面的競(jìng)爭(zhēng)加大，產(chǎn)品的運(yùn)輸、檢查及存儲(chǔ)方面所占的比重越來越高。在產(chǎn)品的存儲(chǔ)方面，自動(dòng)化立體倉庫的存儲(chǔ)效率主要取決于堆垛機(jī)的運(yùn)行速度、貨位的優(yōu)化存取[1]。有效解決貨物在存取中效率低的問題，可以大大提高自動(dòng)化立體倉庫的工作效率。貨架作為自動(dòng)化立體倉庫的存儲(chǔ)部分，是倉儲(chǔ)物流中一個(gè)重要環(huán)節(jié)[2]，合理安排貨位的出入庫分配原則和分配策略，能有效降低搬運(yùn)過程中的損耗，降低物流業(yè)務(wù)成本，提高物流行業(yè)收益。

1 自動(dòng)化立體倉庫模型設(shè)計(jì)

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

圖1 自動(dòng)化立體倉庫結(jié)構(gòu)平面圖

立體倉庫由計(jì)算機(jī)控制，先將立體的程序通過PLC輸入計(jì)算機(jī)中，按照操作執(zhí)行出庫、入庫等動(dòng)作。當(dāng)一批生產(chǎn)任務(wù)到達(dá)時(shí)，計(jì)算機(jī)按照指令順序依次來執(zhí)行出入庫任務(wù)。由于出入庫動(dòng)作執(zhí)行的順序不一樣[4]，堆垛機(jī)路徑也不同，因而堆垛機(jī)每次執(zhí)行任務(wù)的時(shí)間也不同。

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

圖2 堆垛機(jī)存取路徑

(1)對(duì)于貨物復(fù)合作業(yè)，根據(jù)自動(dòng)化立體倉庫的出入效率原則，建立數(shù)學(xué)模型：

(1)

(2)

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

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

(3)

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

(3)堆垛機(jī)存取貨物是多目標(biāo)優(yōu)化求解問題，通過對(duì)兩個(gè)目標(biāo)函數(shù)賦予權(quán)重參數(shù)，使得多目標(biāo)函數(shù)變成單目標(biāo)函數(shù)進(jìn)行求解。為了方便計(jì)算求解，兩個(gè)目標(biāo)函數(shù)權(quán)重參數(shù)均為0.5。將上述目標(biāo)函數(shù)進(jìn)行變換可得到函數(shù)：

f3=0.5·(f1+f2),

(4)

在賦予權(quán)重參數(shù)后，可得到堆垛機(jī)最終的目標(biāo)函數(shù)：

(5)

2 立體倉庫貨位優(yōu)化模型算法設(shè)計(jì)

自動(dòng)化立體倉庫出入庫路徑優(yōu)化通過研究其出入庫任務(wù)的執(zhí)行順序，并為每一個(gè)貨物分派貨位，以提高立體倉庫的效率和利用率[5]。

2.1 遺傳算法介紹

遺傳算法是近幾年迅速發(fā)展的一種高效的優(yōu)化算法。算法對(duì)目標(biāo)函數(shù)的形狀、連續(xù)性等無特殊要求，條件要求不嚴(yán)格，且具有很好的全局搜索能力、良好的容錯(cuò)能力以及適應(yīng)性。遺傳算法不只限于局部搜索僅僅記錄一個(gè)解，而是記錄一個(gè)群體，它可以同時(shí)記錄多個(gè)解?？紤]到遺傳算法在小規(guī)模的多目標(biāo)優(yōu)化項(xiàng)目中具有運(yùn)算速度和精度上的優(yōu)勢(shì),采用遺傳算法對(duì)立體倉庫的貨位進(jìn)行優(yōu)化[6]。

2.2 遺傳算法設(shè)計(jì)

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

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

表1 貨位對(duì)應(yīng)編碼

貨物編碼對(duì)應(yīng)數(shù)字編碼1(1,1)2(2,3)

貨物編碼對(duì)應(yīng)數(shù)字編碼3(3,2)4(4,1)

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

(2)種群初始化。種群的數(shù)目設(shè)定為隨機(jī)，種群數(shù)目越大，遺傳算法得到最優(yōu)解的機(jī)會(huì)就越小?？紤]執(zhí)行效率和結(jié)果，將種群的數(shù)目設(shè)定為100。

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

(6)

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

由于要求的目標(biāo)函數(shù)綱量不同，對(duì)于目標(biāo)函數(shù)直接進(jìn)行加權(quán)求和顯然沒有意義。因此解決綱量不同帶來的影響，需要對(duì)目標(biāo)函數(shù)進(jìn)行去綱量處理。

對(duì)目標(biāo)函數(shù)進(jìn)行如下的線性變換法轉(zhuǎn)換：

fk=αfk+b

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

(7)

由式(7)得到去綱量后的適應(yīng)度函數(shù)：

(8)

式中，k表示第幾個(gè)目標(biāo)函數(shù)。

對(duì)式(8)取倒數(shù)，得到適應(yīng)度函數(shù)：

(9)

為了使得上述函數(shù)能夠在區(qū)間(0,1)中，對(duì)于遺傳算法通常采用正規(guī)標(biāo)定的方法：

(10)

γ∈(0,1)在此區(qū)間內(nèi)，避免分母為0；將選擇方式調(diào)整為隨機(jī)選擇。通過去綱量和正規(guī)標(biāo)定處理后，目標(biāo)函數(shù)均為無綱量和映射在(0,1)區(qū)間的函數(shù)。

將多目標(biāo)函數(shù)取權(quán)重wk且權(quán)重之和為1，最終將兩個(gè)適應(yīng)度函數(shù)化為一個(gè)適應(yīng)度函數(shù)：

(11)

式中,wk為目標(biāo)函數(shù)綱量；Fk為一個(gè)適應(yīng)度函數(shù)。

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

(12)

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

交叉算子：采用較多的單點(diǎn)交叉法對(duì)染色體進(jìn)行交叉運(yùn)算，交叉原理如圖3所示。

圖3 遺傳算法交叉原理

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

2.3 貨位優(yōu)化仿真及求解

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

表2 貨物參數(shù)

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

圖4 優(yōu)化前貨位求解結(jié)果 圖5 優(yōu)化后貨位求解結(jié)果

3 立體倉庫堆垛機(jī)路徑優(yōu)化

堆垛機(jī)的作業(yè)過程就是從起始點(diǎn)到目標(biāo)點(diǎn)完成取送貨后再回到起始點(diǎn)的過程。堆垛機(jī)執(zhí)行該工作的過程所走的軌跡即為堆垛機(jī)揀選路徑。立體倉庫堆垛機(jī)的路徑優(yōu)化[8]即實(shí)現(xiàn)堆垛機(jī)在揀選貨物時(shí)行走路程最短。

3.1 立體倉庫揀選貨物作業(yè)建模

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

(13)

式中,Si為城市號(hào)；d為城市之間距離。

堆垛機(jī)在揀選作業(yè)時(shí)，程序給予作業(yè)任務(wù)，堆垛機(jī)根據(jù)作業(yè)任務(wù)從起始點(diǎn)處出發(fā)，依次將作業(yè)清單上的任務(wù)揀選完成后回到揀選作業(yè)區(qū)，以便執(zhí)行下次任務(wù)。

3.2 揀選路徑優(yōu)化計(jì)算仿真

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

表3 揀選貨物坐標(biāo)參數(shù)

圖6 優(yōu)化前后路徑

4 結(jié)論

通過對(duì)立體倉庫的分析，解決自動(dòng)化立體倉庫的貨位優(yōu)化問題和堆垛機(jī)路徑優(yōu)化問題[9]。通過算法選擇，確定優(yōu)化目標(biāo)和約束條件，建立相應(yīng)的數(shù)學(xué)模型，結(jié)合遺傳算法思想，并對(duì)遺傳算法進(jìn)行一定的優(yōu)化，利用Matlab求解。最后，通過對(duì)比優(yōu)化前后的結(jié)果，實(shí)現(xiàn)了自動(dòng)化立體倉庫的貨位優(yōu)化和堆垛機(jī)路徑優(yōu)化[10]，提高了自動(dòng)化立體倉庫工作效率。