張新陽,陳 玉,王 鵬
(安徽工程大學(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è)收益。
貨位優(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)
自動(dòng)化立體倉庫出入庫路徑優(yōu)化通過研究其出入庫任務(wù)的執(zhí)行順序,并為每一個(gè)貨物分派貨位,以提高立體倉庫的效率和利用率[5]。
遺傳算法是近幾年迅速發(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]。
通過建立模型、設(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ù)。
(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é)果
堆垛機(jī)的作業(yè)過程就是從起始點(diǎn)到目標(biāo)點(diǎn)完成取送貨后再回到起始點(diǎn)的過程。堆垛機(jī)執(zhí)行該工作的過程所走的軌跡即為堆垛機(jī)揀選路徑。立體倉庫堆垛機(jī)的路徑優(yōu)化[8]即實(shí)現(xiàn)堆垛機(jī)在揀選貨物時(shí)行走路程最短。
對(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ù)。
利用改進(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)化前后路徑
通過對(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)化立體倉庫工作效率。