李永偉,劉樹安,郭晉秦

(1.太原工業(yè)學(xué)院,山西 太原 030008;2.東北大學(xué)信息科學(xué)與工程學(xué)院,遼寧 沈陽 110004)

引言

普通立體倉庫是由低層貨架構(gòu)成,采用單元貨格式貨位,并由人工尋址、人工揀選完成貨物出入庫操作的一種倉庫。由于其具有結(jié)構(gòu)簡(jiǎn)單、配套設(shè)備較少、維護(hù)費(fèi)用低、出入庫靈活等優(yōu)勢(shì),使其得以在信息技術(shù)高速發(fā)展的潮流中廣泛應(yīng)用于物流倉儲(chǔ)業(yè)中[1-2]。本文以某軸承倉庫為研究對(duì)象,對(duì)出庫貨位優(yōu)化問題進(jìn)行研究。

該軸承倉庫主要的倉儲(chǔ)區(qū)包括理貨區(qū)和貨架區(qū)。理貨區(qū)位于倉庫出入庫口,主要用來對(duì)出入庫貨物起緩沖作用或者存放特殊規(guī)格的貨物;貨架區(qū)并列成排,立于倉庫的中心,采用隨機(jī)存儲(chǔ)的策略存放貨物。倉庫的搬運(yùn)設(shè)備以叉車為主。出庫過程中,倉庫工作人員接到客戶的貨物需求,憑借經(jīng)驗(yàn)和記憶去相應(yīng)的貨位揀選貨物,并利用搬運(yùn)設(shè)備完成出庫操作,最后更新相應(yīng)的倉庫基本信息。

揀選基本路線為工作人員操作搬運(yùn)設(shè)備從理貨區(qū)出發(fā),并進(jìn)入貨區(qū)揀選貨物,最后回到理貨區(qū),在貨區(qū)揀選貨物過程中完全憑借經(jīng)驗(yàn)進(jìn)行,并沒有給出確定的路線,不僅耗費(fèi)體力,而且大大降低了倉庫的周轉(zhuǎn)效率。為了提高倉庫運(yùn)作效率,本文以出庫作業(yè)單的生成為切入點(diǎn),力求倉庫管理系統(tǒng)能夠生成帶有優(yōu)化的出庫作業(yè)單,即對(duì)于出庫單除了包含出庫貨物信息外,還應(yīng)包含對(duì)應(yīng)的揀選路徑和揀選批次。圍繞以上問題,建立出庫貨位優(yōu)化模型,并設(shè)計(jì)算法對(duì)模型進(jìn)行求解,最后通過仿真實(shí)驗(yàn)驗(yàn)證算法的有效性。

1 出庫貨位優(yōu)化模型的建立

為了便于對(duì)出庫過程的數(shù)學(xué)表述,給倉庫貨位進(jìn)行編號(hào)。設(shè)貨區(qū)共有N個(gè)貨位,從靠近理貨區(qū)出發(fā),自上而下、由近及遠(yuǎn)依次對(duì)每個(gè)貨位進(jìn)行編號(hào):k=1,2,…,N,并設(shè)理貨區(qū)的編號(hào)為0。在出庫過程中工作人員如何合理地從成百上千個(gè)貨位中揀選出所需的貨物,并對(duì)揀選路徑進(jìn)行合理選擇是出庫貨位優(yōu)化時(shí)需要解決的問題。由于叉車載重的限制,出庫過程中需由多個(gè)批次來完成所需貨物的揀選工作。因此可以把貨位優(yōu)化問題進(jìn)一步表述為,旨在解決如何合理地確定每件所需貨物出庫時(shí)所在的出庫貨位和出庫批次,以及如何合理地確定相應(yīng)的揀選路徑。通過解決該問題,進(jìn)而提高倉庫的出庫效率。基于以上分析,定義如下決策變量及相關(guān)參數(shù)。

1.1 單批次載重約束

制定每一批次的出庫計(jì)劃時(shí),需要考慮叉車負(fù)重能力的約束,假設(shè)單批次載重上限為W,則在出庫過程中單批次載重約束為:

(1)

其中TO—所有待出庫貨物的種類總數(shù),wi—單位i類貨物的重量(Kg),W—單批次載重的上限(Kg),j—出庫作業(yè)的批次編號(hào),q—完成出庫作業(yè)用的總批次數(shù)。上式(1)表示在任意批次的出庫作業(yè)中,叉車所載貨物的總重量不得超過單批次的載重上限。

1.2 出庫貨物種類約束

在出庫揀選過程中,對(duì)于所需的第i類貨物只能選擇從存放該類貨物的貨位中揀選,因此可以通過貨位狀態(tài)變量Sk和對(duì)應(yīng)的k貨位中貨物z是否選擇出庫共同決定決策變量yjkz的取值情況:

(2)

1.3 出庫訂單數(shù)量約束

出庫過程分多個(gè)批次完成的,其目的是把出庫單上的所有貨物從相應(yīng)的貨位中揀選齊全,所以有如下約束:

(3)

1.4 貨位出庫次數(shù)的約束

出庫過程分q個(gè)批次完成對(duì)需求貨物的揀選工作,由于單批次載重量遠(yuǎn)大于單個(gè)貨位的容量限制,為了防止在多個(gè)出庫作業(yè)批次中對(duì)某些貨位重復(fù)進(jìn)行揀選工作,規(guī)定在整個(gè)出庫過程中每個(gè)貨位只到達(dá)一次,結(jié)合前文論述,可得到貨位出庫次數(shù)限制的約束條件為:

Ka∩Kβ=?,α,β=1,2,…,p且α≠β

(4)

(5)

1.5 模型目標(biāo)

本文以工作人員在出庫過程中走過的總路程最小為優(yōu)化的目標(biāo)。由前文可知,整個(gè)出庫過程分q個(gè)批次來完成,設(shè)在第j個(gè)批次走過的貨位集合為Kj,如果求得第j個(gè)批次的揀選路徑,并求得相應(yīng)的路程,最后累加q個(gè)批次的路程即可得到出庫貨位優(yōu)化模型的目標(biāo)函數(shù),由此可得到出庫貨位優(yōu)化的目標(biāo)函數(shù):

(6)

其中zuv∈{0,1},u,v∈Kj且u≠v

duv—貨位u和貨位u之間的距離(米),d0v—理貨區(qū)和貨位v之間的距離(米),du0—貨位u和理貨區(qū)之間的距離(米)。上式(6)表示完成出庫作業(yè)時(shí)工作人員走過的總路程。

2 算法設(shè)計(jì)

出庫過程中,決定著問題優(yōu)化結(jié)果的因素可以歸結(jié)為出庫時(shí)經(jīng)過了哪些貨位,即選哪些貨位完成出庫操作;對(duì)于每個(gè)需要經(jīng)過的貨位,對(duì)應(yīng)的出庫貨物的種類和數(shù)量分別是多少;出庫時(shí),每個(gè)貨位所在批次,及批次內(nèi)經(jīng)過每個(gè)貨位的先后順序,即根據(jù)所選貨位的出庫量進(jìn)行劃分作業(yè)批次,并按一定的順序完成出庫操作。因此,出庫貨位優(yōu)化可分為兩層:首先,選擇哪些貨位進(jìn)行出庫操作,即貨位選擇優(yōu)化層;其次,對(duì)已選貨位完成出庫操作時(shí)的批次劃分及先后順序的確定,即貨位順序優(yōu)化層。

由模型和問題本身的分析可知,該問題隨著貨位數(shù)量和貨物種類的增多,模型的求解工作量會(huì)呈現(xiàn)指數(shù)式增長(zhǎng),屬于組合優(yōu)化問題[3]。對(duì)于組合優(yōu)化問題,多采用智能算法進(jìn)行求解,而遺傳算法作為經(jīng)典的智能算法,其具有魯棒性好、尋優(yōu)能力強(qiáng)的優(yōu)點(diǎn)[4-5]。因此,針對(duì)貨位優(yōu)化模型的兩層優(yōu)化,將兩個(gè)遺傳算法嵌套分別對(duì)貨位選擇層和貨位順序?qū)舆M(jìn)行求解。下面用變量X代表貨位選擇優(yōu)化層,用變量Y代表貨位順序優(yōu)化層,算法的具體流程如圖1所示。

圖1 雙層遺傳算法流程圖

遺傳算法中主要的算子包括編碼、交叉、變異和選擇策略的設(shè)計(jì)。由于本文算法方面的創(chuàng)新點(diǎn)主要在于算法結(jié)構(gòu)的設(shè)計(jì),所以對(duì)于內(nèi)部算子不作過多研究[6-7]。貨位選擇優(yōu)化層中,由于貨物種類較多,分別采用均勻交叉和互換變異,而貨位順序優(yōu)化層采用順序交叉和互換變異,選擇策略采用輪盤賭的方式。下面主要針對(duì)雙層遺傳算法的編碼、染色體修復(fù)及解碼進(jìn)行設(shè)計(jì)。

2.1 出庫貨位選擇優(yōu)化層編碼

貨位選擇層主要解決選擇哪些貨位完成出庫操作的問題。所以,在編碼時(shí)可用整數(shù)1表示出庫時(shí)選擇該貨位中的貨物出庫,整數(shù)0表示不選擇。染色體的具體結(jié)構(gòu)設(shè)計(jì)如圖2所示。

貨位的選擇:0111001101110

圖2染色體結(jié)構(gòu)

很顯然,從以上染色體還不足以得到每個(gè)可用貨位的選擇情況,所以設(shè)計(jì)輔助字符串,確定貨位的選擇情況。首先在選擇可用貨位時(shí)必須滿足條件:mki>0,?i∈I2,即所選貨位k中含有需要出庫的貨物。

另外,為了便于后續(xù)的算法設(shè)計(jì),對(duì)可用貨位按貨物種類分段,并以貨位的可出庫貨物量Yjk由小到大排序,貨位的可出庫量可由公式(7)得到。

(7)

由此,染色體的輔助字符串中還需包含每個(gè)貨位擁有貨物量的信息及對(duì)應(yīng)的貨物種類。另外,為了滿足在整個(gè)出庫過程中每個(gè)貨位只服務(wù)一次的條件,初步設(shè)定每個(gè)選中出庫貨位的實(shí)際出庫量等于該貨位可出庫的貨物量,即每到達(dá)一個(gè)貨位,把該貨位的貨物全部出庫。最后,根據(jù)貨物的計(jì)劃出庫量要求對(duì)每個(gè)貨位的實(shí)際出庫量作適當(dāng)修正。由以上分析可得出,染色體的輔助字符串的結(jié)構(gòu)設(shè)計(jì)如圖3所示。

貨物種類:貨位編號(hào):可出庫貨物量:實(shí)際出庫量:11112222333335131418921020136712192101216113611581718230101216006110817180

圖3輔助字符串

結(jié)合染色體和輔助字符串的信息,可以得到在出庫過程中從第k個(gè)貨位中揀選貨物的數(shù)量。具體在哪一個(gè)批次完成貨物的揀選,需經(jīng)過貨位順序?qū)舆M(jìn)一步確定。

2.2 染色體的修復(fù)

本文針對(duì)出庫時(shí)實(shí)際出庫量不等于計(jì)劃出庫量的情況對(duì)染色體進(jìn)行修復(fù),具體修復(fù)策略如下:

2.3 貨位順序?qū)泳幋a設(shè)計(jì)

貨位順序?qū)邮窃谪浳贿x擇優(yōu)化層的基礎(chǔ)上進(jìn)行優(yōu)化的。出庫時(shí),經(jīng)過貨位選擇層確定了選那些貨位出庫后,結(jié)合貨位選擇層染色體的輔助字符串信息,可得到如圖4所示的信息。

貨物種類:貨位編號(hào):實(shí)際出庫量:11122233331314179201671215101225111208171827

圖4選擇層結(jié)果

由此,可確定出庫過程中所要到達(dá)的貨位和每個(gè)貨位需要出庫的貨物量。另外,搬運(yùn)設(shè)備有相應(yīng)的載重約束。貨位順序優(yōu)化層需要合理確定出庫操作時(shí)走過貨位的順序,然后在解碼時(shí)劃分貨物的出庫批次,即可得到出庫方案。所以,本文采用基于整數(shù)的編碼方式,染色體的每一個(gè)基因代表一個(gè)貨位,基因順序表示完成出庫操作時(shí)所經(jīng)貨位的先后順序。染色體的結(jié)構(gòu)設(shè)計(jì)如圖5所示。

染色體:1314179201671215

圖5染色體結(jié)構(gòu)

圖5編碼表示,在出庫過程中按貨位順序13-14-17-9-20-1-6-7-12-5完成出庫作業(yè)。另外,由于受搬運(yùn)設(shè)備載重的限制,要得到完整的出庫方案,還需要結(jié)合各個(gè)貨位的出庫量,按叉車的載重約束劃分出庫批次,所以還需要設(shè)置染色體的輔助字符串,表示相應(yīng)貨位的出庫量和對(duì)應(yīng)的貨物種類,輔助字符串的設(shè)計(jì)如圖6所示。

貨物種類:實(shí)際出庫量:1112223333101225111208171827

圖6輔助字符串

2.4 解碼

解碼的過程實(shí)際上是根據(jù)搬運(yùn)設(shè)備的載重約束,結(jié)合染色體的輔助字符串信息,把染色體對(duì)應(yīng)的貨位依次劃入各個(gè)批次的出庫任務(wù)中,進(jìn)一步確定出庫路徑,然后根據(jù)貨位間的距離得到工作人員在出庫過程中經(jīng)過的總路程,以此來評(píng)價(jià)當(dāng)前染色體對(duì)應(yīng)的出庫效果,經(jīng)算法的迭代,不斷搜索到質(zhì)量更優(yōu)的解。下面以圖5所示的染色體及其輔助字符串信息為例,并假設(shè)叉車載重為50(Kg),每類貨物的單位重量為1,進(jìn)一步說明解碼過程。

按如下步驟得到出庫方案:首先將貨位13納入到第一個(gè)出庫批次,然后判斷貨位14是否可以納入到第1個(gè)批次,由于貨位13和貨位14對(duì)應(yīng)的貨物量之和滿足載重約束,即10+12<50,所以可以將貨位14納入到第1個(gè)批次。同理，可以把貨位17、貨位9納入到第1個(gè)批次。然后判斷貨位20是否可以納入到第1個(gè)批次,假設(shè)可以,則該批次對(duì)應(yīng)的貨物量之和不滿足載重約束,即10+12+25+1+11>50,所以貨位20不可納入到第1批次。由于叉車從理貨區(qū)出發(fā),最終回到理貨區(qū),所以可以得到在第1個(gè)出庫批次中,叉車所走的路徑為0—13—14—17—9—0。同理,可以得到：第2個(gè)批次路徑為0—20—1—6—0;第3個(gè)批次路徑為0—7—12—0;第4個(gè)批次路徑為0—15—0。

到此,得到了完整的出庫方案,然后根據(jù)倉庫貨位之間,以及貨位和理貨區(qū)之間的距離計(jì)算得到出庫過程中工作人員走過的總路程,即目標(biāo)函數(shù)的值,并以此評(píng)價(jià)該出庫方案的好壞。

3 仿真實(shí)驗(yàn)與結(jié)果分析

本文以軸承倉庫某次出庫過程為例,對(duì)上述貨位優(yōu)化模型和算法進(jìn)行驗(yàn)證。已知叉車載重為500 Kg,倉庫內(nèi)部貨位間的距離及貨位的存儲(chǔ)狀態(tài)已知,出庫貨物的種類、數(shù)量及庫存量如表1所示。

表1 出入庫相關(guān)信息

3.1 參數(shù)試驗(yàn)

由于所設(shè)計(jì)的雙層遺傳算法的參數(shù)較多,本文采用控制變量法進(jìn)行參數(shù)實(shí)驗(yàn),且實(shí)驗(yàn)過程中均采用10計(jì)算取均值的方法。由理論分析和實(shí)驗(yàn)結(jié)果可得,種群規(guī)模越大,迭代次數(shù)越多,結(jié)果越精確。但隨著種群規(guī)模和迭代次數(shù)的增多,算法執(zhí)行時(shí)間成指數(shù)式增加。綜合可得,貨位選擇優(yōu)化層最佳參數(shù)為交叉率0.8、變異率0.2、種群規(guī)模100、迭代次數(shù)200;貨位順序優(yōu)化層最佳參數(shù)為交叉率0.7、變異率0.1、種群規(guī)模50、迭代次數(shù)250。

3.2 優(yōu)化結(jié)果分析

利用雙層遺傳算法對(duì)算例進(jìn)行求解,然后結(jié)合模型參數(shù)對(duì)求解得到的出庫分配方案進(jìn)行詳細(xì)的分析。在建立出庫貨位優(yōu)化模時(shí),定義了決策變量yjkz,表示在第j個(gè)出庫作業(yè)批次,是否選擇貨位k中的貨物z出庫。由于每個(gè)貨位貨物的數(shù)量較多,不可能對(duì)每個(gè)貨物的選擇與否進(jìn)行表示,這里只表示出每個(gè)貨位的實(shí)際出庫量。所以,引入中間變量Yjk:表示在第j個(gè)批次貨位k的出庫量,通過實(shí)驗(yàn)得到出庫揀選方案如表2所示。

表2 出庫貨位優(yōu)化結(jié)果

由上文可知,本文對(duì)倉庫貨位采用依次編號(hào)的形式進(jìn)行表示,即相鄰編號(hào)的貨位,意味著貨位間的距離相近。通過分析表2的求解結(jié)果可以發(fā)現(xiàn),所有批次內(nèi)貨位編號(hào)沒有大的跳躍,說明算法在求解貨位優(yōu)化問題的過程中,對(duì)出庫目標(biāo)貨位的選擇是比較合理;在出庫方案中,單批次內(nèi)總有相鄰編號(hào)的貨位先后進(jìn)行出庫,說明貨位順序?qū)訉?duì)貨位選擇層選中的目標(biāo)貨位進(jìn)行了出庫順序優(yōu)化;大部分批次的載重量接近叉車載重:500 kg,說明算法在求解貨位優(yōu)化問題的過程中對(duì)批次的劃分是比較合理。對(duì)于表2中的批次5,批次載重量為278.0 kg,與叉車的載重量差距比較大,這是因?yàn)樵撆嗡?jīng)過的貨位集中在理貨區(qū)附近,單獨(dú)劃分一個(gè)批次來完成相應(yīng)的出庫操作更為合理。

由以上分析可得到,在利用雙層遺傳算法求解貨位優(yōu)化模型時(shí),在貨位選擇優(yōu)化層、貨位順序優(yōu)化層、出庫批次劃分3個(gè)關(guān)鍵點(diǎn)都取得了比較滿意的效果。

4 結(jié)論

本文以普通立體倉庫為研究對(duì)象,針對(duì)貨物出庫時(shí)揀選作業(yè)路徑進(jìn)行了優(yōu)化研究。首先建立了揀選路徑優(yōu)化模型,將這一優(yōu)化問題分為貨位選擇優(yōu)化層和貨位順序優(yōu)化層,并利用雙層遺傳算法進(jìn)行求解,通過對(duì)算例的求解,驗(yàn)證了模型及算法的可行性和合理性。但由于遺傳算法是多點(diǎn)搜索,使用雙層遺傳算法求解貨位優(yōu)化問題時(shí)效率極其低,在下一步的研究中,可就算法效率方面進(jìn)行研究。