曹 孟,楊 健
(安徽理工大學(xué),安徽 淮南 232001)
在物流各環(huán)節(jié)中,訂單揀選成本占總成本的50%~70%,無論是“人到貨”倉庫還是“貨到人”倉庫,訂單揀選作業(yè)都需要從貨架上揀選出訂單所需要的商品[1],在這個(gè)過程中,合理的儲(chǔ)位分配方式可以減少揀選作業(yè)的揀選距離和揀選時(shí)間,降低訂單揀選成本,提高訂單的揀選效率,因此儲(chǔ)位分配問題的研究對(duì)于倉庫實(shí)際作業(yè)有著重要意義。
學(xué)者們?cè)谪浳环峙鋯栴}上作了深入的研究。何李等[2]考慮貨物重量以及出入庫頻率來進(jìn)行貨架區(qū)域劃分,建立仿真模型,以指令內(nèi)最小化單載具堆垛機(jī)運(yùn)行時(shí)間為研究目標(biāo),設(shè)計(jì)了一種兩階段狼群算法對(duì)其進(jìn)行優(yōu)化。楊瑋等[3]以最小化堆垛機(jī)行程時(shí)間為目標(biāo),提出貨位分配與作業(yè)調(diào)度集成優(yōu)化方法,設(shè)計(jì)了雙層遺傳算法對(duì)模型進(jìn)行求解。針對(duì)基于AGV的自動(dòng)化立體倉庫儲(chǔ)位分配問題,胡祥培等[4]以提高貨架商品間關(guān)聯(lián)性為目標(biāo),提出“關(guān)聯(lián)網(wǎng)絡(luò)構(gòu)建→關(guān)聯(lián)網(wǎng)絡(luò)分析→關(guān)聯(lián)網(wǎng)絡(luò)聚類”的三階段貨位分配方法,來快速高效生成儲(chǔ)位分配方案,Zhongqiang Ma[5]等以貨架上商品關(guān)聯(lián)度最大為目標(biāo),同時(shí)考慮商品的分類和商品之間的關(guān)聯(lián)性,提出了一種自適應(yīng)模擬退火變鄰域搜索算法來解決儲(chǔ)位分配的問題。
現(xiàn)有針對(duì)基于AGV的自動(dòng)化無人倉庫儲(chǔ)位分配問題的研究[6-9]大多都假設(shè)倉庫的初始狀態(tài)是空的,而現(xiàn)實(shí)中這種情況并不多見,更為實(shí)際的問題是倉庫的初始狀態(tài)非空,即倉庫處于補(bǔ)貨狀態(tài),而針對(duì)這種情況的研究并不多,因此本文將研究倉庫初始狀態(tài)非空時(shí)的儲(chǔ)位分配問題。
假設(shè)某自動(dòng)化無人倉庫中共存儲(chǔ)S種商品,倉庫中有M個(gè)貨架,每個(gè)貨架上有P個(gè)儲(chǔ)位,每個(gè)儲(chǔ)位僅存放一種商品,商品存儲(chǔ)方式為分散存儲(chǔ),即一種商品可以存放在多個(gè)貨架上,每種商品需要占用的儲(chǔ)位數(shù)已知,在某個(gè)補(bǔ)貨階段,需要將一定量的商品上架到貨架上,考慮如何合理規(guī)劃商品存放位置,減少商品的揀選成本。
由于現(xiàn)實(shí)問題較為復(fù)雜,涉及諸多方面的優(yōu)化問題,為了簡(jiǎn)化問題,作出以下假設(shè):
(1)訂單的揀選方式為按訂單揀選。
(2)歷史訂單信息是已知的,在未來一段時(shí)間內(nèi),訂單結(jié)構(gòu)幾乎不會(huì)發(fā)生改變,這個(gè)假設(shè)保證了商品之間的關(guān)聯(lián)性是穩(wěn)定的。
(3)每個(gè)儲(chǔ)位上存儲(chǔ)的商品數(shù)量滿足一個(gè)訂單中對(duì)該商品的需求。
(4)不考慮缺貨情況。
(5)每種商品可以放在多個(gè)貨架的多個(gè)儲(chǔ)位上,每個(gè)儲(chǔ)位上只能存放一種商品。
為建立上述問題的數(shù)學(xué)模型,定義如下參數(shù)符號(hào),如表1所示。
表1 參數(shù)符號(hào)
定義決策變量:
xjm表示待補(bǔ)貨商品j在貨架m上占用的儲(chǔ)伴數(shù)。
Oi表示包含商品i的訂單數(shù),Oj表示包含商品j的訂單數(shù),Oij表示同時(shí)包含商品i和j的訂單數(shù),分別統(tǒng)計(jì)一定時(shí)期內(nèi)的Oi、Oj、Oij,如式(1)和式(2)所示。
同時(shí)rij=rji,當(dāng)i=j時(shí)rij=0,則R為:
目標(biāo)函數(shù)如式(3)所示。
(3)
約束條件如式(4)~式(10)。
目標(biāo)函數(shù)式(3)表示對(duì)所有貨架上存放的商品之間的關(guān)聯(lián)度之和求最大,從第一項(xiàng)到第三項(xiàng)分別表示同一貨架上原有商品之間的關(guān)聯(lián)度之和、補(bǔ)貨商品與貨架上已有商品之間的關(guān)聯(lián)度之和、貨架上補(bǔ)貨商品之間的關(guān)聯(lián)度之和;約束條件式(4)表示存放在每個(gè)貨架上的空儲(chǔ)位數(shù)全部被待補(bǔ)貨商品所占用;約束條件式(5)確保待補(bǔ)貨商品j實(shí)際占用的總儲(chǔ)位數(shù)等于商品j需要的儲(chǔ)位數(shù);約束條件式(6)表示如果待補(bǔ)貨商品j被放到第m個(gè)貨架上,那么它占據(jù)的儲(chǔ)位數(shù)小于等于貨架m的空余儲(chǔ)位數(shù)Qm;約束條件式(7)表示如果待補(bǔ)貨商品j被放到第m個(gè)貨架上,那么商品j占用的儲(chǔ)位數(shù)量大于等于1;約束條件式(8)表示每種補(bǔ)貨商品至少需要存放到一個(gè)貨架上;約束條件式(9)和式(10)為決策變量取值約束。
對(duì)于小規(guī)模的貨位分配問題可以直接求得問題的精確解,對(duì)于大規(guī)模的問題來說,精確解很難求得,或者耗時(shí)很久,學(xué)者們大都是設(shè)計(jì)啟發(fā)式算法進(jìn)行求解,在這里結(jié)合以上模型設(shè)計(jì)基于大鄰域搜索的兩階段啟發(fā)式算法。大鄰域搜索算法(LNS)是由變鄰域搜索算法演變而來,對(duì)比變鄰域搜索算法,它具有搜索范圍廣,所得局部最優(yōu)解質(zhì)量好等特點(diǎn),但耗時(shí)也會(huì)相對(duì)較長(zhǎng)。算法共分為兩大步驟:首先在算法開始時(shí)利用設(shè)計(jì)的貪婪算法對(duì)問題求得初始解;然后基于貪婪算法所求的解,利用大鄰域搜索算法對(duì)解進(jìn)行迭代,求得本問題的最終解,即儲(chǔ)位分配方案。
算法的過程就是將待補(bǔ)貨商品不斷放置到貨架上,依次將與貨架上商品關(guān)聯(lián)度最大的商品放置到貨架上,使得總關(guān)聯(lián)度之和最大。貪婪算法的具體步驟:
(1)輸入:補(bǔ)貨前貨架上存放的商品信息矩陣和貨架上原有商品集合、待補(bǔ)貨商品集合和待補(bǔ)貨商品需要占據(jù)的儲(chǔ)位數(shù)、商品的關(guān)聯(lián)度矩陣R。
①第1步:判斷待補(bǔ)貨商品集合是否為空,若不為空繼續(xù),否則結(jié)束。
②第2步:對(duì)貨架上各個(gè)商品與待補(bǔ)貨商品之間的關(guān)聯(lián)度進(jìn)行排序,尋找關(guān)聯(lián)度最大的一對(duì)商品,這對(duì)商品包括一種貨架上的商品i,和一種待補(bǔ)貨商品j,統(tǒng)計(jì)包含商品i且有空余儲(chǔ)位的貨架數(shù)t,根據(jù)t與商品j需要的儲(chǔ)位數(shù)Dj的大小關(guān)系分為兩種情況為商品j分配儲(chǔ)位。
第一種情況若t大于等于Dj,則將商品j隨機(jī)分配到這t個(gè)貨架上,每個(gè)貨架上占據(jù)一個(gè)儲(chǔ)位。
第二種情況t小于Dj,則先在這t個(gè)貨架上各分配一個(gè)商品j,此時(shí)商品j所需的儲(chǔ)位還沒有滿足,繼續(xù)將商品j隨機(jī)分配到有空余儲(chǔ)位的貨架上,每個(gè)貨架上依然占據(jù)一個(gè)儲(chǔ)位。
③第3步:更新貨架上商品信息矩陣、貨架上商品集合、待補(bǔ)貨商品集合,轉(zhuǎn)第1步。
(2)輸出:儲(chǔ)位分配結(jié)果X0,目標(biāo)函數(shù)值Z0。
大鄰域搜索算法屬于鄰域搜索算法的一種,最早由 Shaw[10]于1998 年提出。該算法的基本框架和其他鄰域搜索算法類似,即先產(chǎn)生一個(gè)初始解,然后對(duì)解不斷進(jìn)行破壞與修復(fù)以提高解的質(zhì)量,直至得到滿意的解為止。具體而言,大鄰域搜索算法的一次迭代由兩部分構(gòu)成:第一步對(duì)當(dāng)前解進(jìn)行破壞,在本文中破壞表示將商品從貨架上移除,并對(duì)當(dāng)前解進(jìn)行拆解(如從路徑中刪除若干個(gè)點(diǎn));第二步為對(duì)破壞后的解進(jìn)行重構(gòu)生成新解,在本文中表示將商品插入到貨架上。大鄰域搜索算法的一般步驟如下:
(1)輸入初始解X。
(2)令當(dāng)前最優(yōu)解Xb=X。
(3)判斷算法終止條件是否滿足。如果是,輸出當(dāng)前最優(yōu)解Xb并結(jié)束該算法;否則繼續(xù)。
(4)對(duì)當(dāng)前解X進(jìn)行破壞,得到解Xd。
(5)對(duì)解Xd進(jìn)行修復(fù),得到解Xr。
(6)比較Xr與Xb的目標(biāo)函數(shù)值,如果Xr比Xb更優(yōu),則取當(dāng)前最優(yōu)解Xb=Xr,否則繼續(xù)。
(7)轉(zhuǎn)至步驟(3)。
本文設(shè)計(jì)三種移除算子和三種插入算子,由此共有9種組合的大鄰域搜索。
3.2.1 移除算子
(1)最差移除(Worst Removal ,WR)
最差移除是指移除貨架上貢獻(xiàn)度最小的補(bǔ)貨商品,具體過程如下:首先計(jì)算貨架上各個(gè)補(bǔ)貨商品的貢獻(xiàn)度,商品i的貢獻(xiàn)度的定義為Ci=f-f-i,其中f為貨架上原有商品關(guān)聯(lián)度之和,f-i為該貨架去掉商品i的關(guān)聯(lián)度之和,該等式等價(jià)于商品i與貨架上其他商品關(guān)聯(lián)度之和;然后計(jì)算所有貨架上補(bǔ)貨商品的貢獻(xiàn)度之后,將這些商品按照貢獻(xiàn)度大小進(jìn)行排序,引入P1≥1,生成隨機(jī)數(shù)rand,移除上述商品序列中的第(rand^P1*商品序列長(zhǎng)度)個(gè)商品。重復(fù)此步驟,直到移除商品個(gè)數(shù)滿足需要移除商品的數(shù)量。P1的大小用來控制移除商品過程中的隨機(jī)性,P1越大代表隨機(jī)性越小,反之隨機(jī)性越大。
(2)相似移除(Shaw Removal ,SR)
相似移除算子來源于Shaw,本文中移除的原則依然是相似性,只是在該算子最初被提出時(shí)是用來解決車輛路徑問題,對(duì)它進(jìn)行了改動(dòng),以適用于儲(chǔ)位分配問題,并直接用商品之間的關(guān)聯(lián)度來表示商品相似性的度量。具體過程如下:首先建立貨架上補(bǔ)貨商品的集合n1,隨機(jī)從n1中選擇一個(gè)商品放入移除商品集合中n2;然后重復(fù):從n2中隨機(jī)選擇一種商品i,按照貨架上補(bǔ)貨商品與商品i的關(guān)聯(lián)度由大到小排序,移除上述商品序列中的第(rand^P2*商品序列長(zhǎng)度)個(gè)商品。重復(fù)此步驟,直到移除商品個(gè)數(shù)滿足需要移除商品的數(shù)量。與最差移除相似的是引入P2≥1,增加選擇過程帶來一定隨機(jī)性,P2越大代表隨機(jī)性越小,反之隨機(jī)性越大。
(3)隨機(jī)移除(Random Removal ,RR)
隨機(jī)移除是指從貨架上的補(bǔ)貨商品上隨機(jī)移除n個(gè)商品,這種移除可以通過改變相似移除和最差移除中的P1、P2來實(shí)現(xiàn),當(dāng)P1或者P2的值為1時(shí)這兩種移除方式變?yōu)殡S機(jī)移除。
3.2.2 插入算子
(1)貪婪插入(Greedy Insertion ,GI)該插入算子與初始解生成的方式相似,是在插入過程中依次選擇插入貢獻(xiàn)最大的商品和位置。具體就是計(jì)算每種商品插入到有空余儲(chǔ)位的貨架上后該貨架的平均貢獻(xiàn),以此為依據(jù),選擇平均貢獻(xiàn)最大的商品與貨架,將該商品插入到該貨架上。其中商品i放置在貨架m上的平均貢獻(xiàn)Ci,m定義如式(11)所示。
(11)
其中,f為將商品i插入到貨架m上之后該貨架的相似度之和;f-i為商品i未插入貨架m上時(shí)的相似度之和;N為未插入商品i時(shí)貨架上原有商品的數(shù)量。
該表達(dá)式代表了將商品i插入貨架m后貨架m相似度增加的平均值。
(2)隨機(jī)插入(Random Insertion ,RI)
隨機(jī)插入是指在插入過程中隨機(jī)選擇被移除的商品隨機(jī)放入空余儲(chǔ)位上,該方式可以保證插入的多樣性。
(3)最大后悔插入(Regret Insertion ,ReI)
最大后悔插入是對(duì)貪婪插入算子的改進(jìn),在最大后悔插入中,選擇插入商品時(shí)同時(shí)考慮了該商品插入貢獻(xiàn)最大的貨架和插入貢獻(xiàn)第二大的貨架,以此來避免貪婪插入的短視問題。在最大后悔插入中首先計(jì)算商品i在每個(gè)有空余儲(chǔ)位的貨架上的插入貢獻(xiàn)Ci,m,其中在貨架m1上的插入貢獻(xiàn)最大為Ci,m1,在貨架m2上的插入貢獻(xiàn)Ci,m2為第二大插入貢獻(xiàn),則商品i的后悔平均插入貢獻(xiàn)值RCi如式(12)所示。
RCi=Ci,m1-Ci,m2
(12)
計(jì)算完每種商品的后悔值后取后悔值最大的商品j,將商品j插入到插入貢獻(xiàn)最大的貨架上。
通過計(jì)算機(jī)隨機(jī)生成三種規(guī)模的算例,驗(yàn)證上述組合算法表現(xiàn)的優(yōu)異性,三種規(guī)模算例的區(qū)別在于商品種類、儲(chǔ)位數(shù)、貨架數(shù)的不同,小規(guī)模算例分為五種情況:商品種類(S)/儲(chǔ)位數(shù)(P)/貨架數(shù)(M)∈{10/5/10,10/5/20,10/5/30,20/5/10,30/5/30};中等規(guī)模算例分為四種情況:商品種類(S)/儲(chǔ)位數(shù)(P)/貨架數(shù)(M)∈{30/5/25,40/5/40,50/5/50,60/5/50},大規(guī)模算例分為三種情況:商品種類(S)/儲(chǔ)位數(shù)(P)/貨架數(shù)(M)∈{200/10/80,300/10/120,500/10/180}。
算法迭代次數(shù)設(shè)置為500次,P1,P2=10,在進(jìn)行移除算子操作時(shí)移除商品的個(gè)數(shù)由移除率決定,本文設(shè)置移除率為0.8。所有實(shí)驗(yàn)均在搭載Intel(R)Core(TM)2.30GHz i5-8300H CPU 計(jì)算機(jī),MatLab R2019(a)編程環(huán)境下編程運(yùn)行。
對(duì)于小規(guī)模算例,實(shí)驗(yàn)結(jié)果如表2所示(其中括號(hào)中數(shù)字為目標(biāo)函數(shù)值的排名,1為最優(yōu),2次之,以此類推,表格只標(biāo)記出排名前五的函數(shù)值,對(duì)于中等規(guī)模算例和大規(guī)模算例結(jié)果表格類似)。從目標(biāo)函數(shù)值上來看RR-RI、RR-GI、RR-ReI、WR-GI、WR-ReI組合的大鄰域搜索算法表現(xiàn)優(yōu)于其他四種組合的鄰域搜索算法,其中WR-ReI的大鄰域搜索在五個(gè)算例中排名均位于前五,性能比較穩(wěn)定,WR-RI的大鄰域搜索表現(xiàn)最差,在五個(gè)算例中均未能排列前五。從時(shí)間上看,在五個(gè)算例中WR-RI、WR-GI 、WR-ReI、SR-GI、SR-ReI組合的大鄰域搜索算法所耗時(shí)間相差不大但都明顯大于RR-RI、RR-GI、RR-ReI、SR-RI組合的大鄰域搜索算法。
表2 小規(guī)模算例結(jié)果比較
對(duì)于中等規(guī)模算例,實(shí)驗(yàn)結(jié)果如表3所示,各組合的大鄰域搜索表現(xiàn)與小規(guī)模算例中的表現(xiàn)類似,從目標(biāo)函數(shù)值上看,RR-RI、RR-GI、RR-ReI、WR-GI、WR-ReI組合的大鄰域搜索算法表現(xiàn)優(yōu)于其他四種組合的鄰域搜索算法,這五種組合的算法在每個(gè)算例中均位于前五名,其中WR-ReI的大鄰域搜索在四個(gè)算例中有三次排名第一,一次排名第二,性能比較優(yōu)越,而其他四種組合的算法均未進(jìn)入前五名。從時(shí)間上看,在四個(gè)算例中WR-RI、WR-GI 、WR-ReI、SR-GI、SR-ReI組合的大鄰域搜索算法所耗時(shí)間相差不大但都明顯大于RR-RI、RR-GI、RR-ReI、SR-RI組合的大鄰域搜索算法。
表3 中等規(guī)模算例結(jié)果比較
對(duì)于大規(guī)模算例,實(shí)驗(yàn)結(jié)果如表4所示,WR-GI、WR-ReI、SR-GI、SR-ReI均不能在有限時(shí)間(1200s)內(nèi)完成迭代,從目標(biāo)函數(shù)值上來看RR-ReI組合算法最優(yōu),在三個(gè)算例中均排名第一,RR-GI組合算法次之,WR-RI、SR-RI組合的算法表現(xiàn)較差;從時(shí)間上看,在三個(gè)算例中所耗時(shí)間排序?yàn)镾R-RI> WR-RI> RR-GI> RR-ReI> RR-RI。
表4 大規(guī)模算例結(jié)果比較
為了分析貪婪算法求得初始解的質(zhì)量和大鄰域搜索對(duì)解優(yōu)化的效果,本節(jié)選取前文所述算例E1,E9,E12進(jìn)行模擬計(jì)算,分別計(jì)算算例隨機(jī)分配時(shí)的函數(shù)值,貪婪算法所得函數(shù)值,與大鄰域搜索算法進(jìn)行對(duì)比,實(shí)驗(yàn)結(jié)果如表5所示。
表5 RR-ReI組合算法性能分析
由表5可知貪婪分配所得初始解對(duì)比隨機(jī)分配情況的解均有所改進(jìn),最高達(dá)到了13.12%,大鄰域搜索的解相對(duì)貪婪分配所得的解也至少提升了33.10%,大鄰域搜索的解相對(duì)隨機(jī)分配所得的解至少提升了38.05%??梢姶筻徲蛩阉魉惴捎行嵘澙贩峙涑跏冀獾馁|(zhì)量,相對(duì)于隨機(jī)分配優(yōu)化效果更好。
本文研究了自動(dòng)化無人倉庫中的儲(chǔ)位分配問題,并且針對(duì)補(bǔ)貨階段的儲(chǔ)位分配問題,拓展了以往研究的深度。首先建立了一個(gè)混合整數(shù)模型,目標(biāo)是貨架上原有商品之間、補(bǔ)貨商品之間、原有商品與補(bǔ)貨商品之間的關(guān)聯(lián)度和的最大化,設(shè)計(jì)了一種兩階段算法,第一階段使用貪婪算法求得初始解,第二階段使用大鄰域搜索算法;然后設(shè)計(jì)了三種移除算子和三種插入算子,九種組合的算法;最后利用模擬算例對(duì)這九種算法進(jìn)行評(píng)估。結(jié)果表明RR-ReI組合算法在所有算法中表現(xiàn)最優(yōu),在大規(guī)模算例中目標(biāo)函數(shù)值最大,同時(shí)時(shí)間在3s以內(nèi),RR-ReI組合算法可以有效提升初始解的質(zhì)量,最低可提升33.1%,相對(duì)于隨機(jī)分配可提升38.05%,驗(yàn)證了所提算法的優(yōu)越性。
浙江交通職業(yè)技術(shù)學(xué)院學(xué)報(bào)2023年3期