基于雙層遺傳算法的倉庫揀選路徑優(yōu)化問題研究

李永偉,劉樹安,郭晉秦

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

引言

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

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

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

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

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

1.1 單批次載重約束

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

(1)

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

1.2 出庫貨物種類約束

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

(2)

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

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

(3)

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

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

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

(4)

(5)

1.5 模型目標

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

(6)

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

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

2 算法設計

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

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

圖1 雙層遺傳算法流程圖

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

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

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

貨位的選擇:0111001101110

圖2染色體結構

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

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

(7)

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

貨物種類:貨位編號:可出庫貨物量:實際出庫量:11112222333335131418921020136712192101216113611581718230101216006110817180

圖3輔助字符串

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

2.2 染色體的修復

本文針對出庫時實際出庫量不等于計劃出庫量的情況對染色體進行修復,具體修復策略如下:

2.3 貨位順序層編碼設計

貨位順序層是在貨位選擇優(yōu)化層的基礎上進行優(yōu)化的。出庫時,經(jīng)過貨位選擇層確定了選那些貨位出庫后,結合貨位選擇層染色體的輔助字符串信息,可得到如圖4所示的信息。

貨物種類:貨位編號:實際出庫量:11122233331314179201671215101225111208171827

圖4選擇層結果

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

染色體:1314179201671215

圖5染色體結構

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

貨物種類:實際出庫量:1112223333101225111208171827

圖6輔助字符串

2.4 解碼

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

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

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

3 仿真實驗與結果分析

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

表1 出入庫相關信息

3.1 參數(shù)試驗

由于所設計的雙層遺傳算法的參數(shù)較多,本文采用控制變量法進行參數(shù)實驗,且實驗過程中均采用10計算取均值的方法。由理論分析和實驗結果可得,種群規(guī)模越大,迭代次數(shù)越多,結果越精確。但隨著種群規(guī)模和迭代次數(shù)的增多,算法執(zhí)行時間成指數(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)化結果分析

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

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

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

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

4 結論

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