自動(dòng)化立體倉庫中的儲(chǔ)位分配及存取路徑優(yōu)化.doc

自動(dòng)化立體倉庫中的儲(chǔ)位分配及存取路徑優(yōu)化Vo1.26.No.1管理工程學(xué)報(bào)JournalofIndustrialEngineering/EngineeringManagement20l2年第1期自動(dòng)化立體倉庫中的儲(chǔ)位分配及存取路徑優(yōu)化陳璐,陸志強(qiáng)(上海交通大學(xué)機(jī)械與動(dòng)力工程學(xué)院工業(yè)工程與物流工程系,上海200240)摘要:儲(chǔ)位分配和存取作業(yè)路徑優(yōu)化是倉儲(chǔ)管理中的兩個(gè)重要決策問題.本文研究如何在自動(dòng)化立體倉庫中對(duì)這兩個(gè)問題進(jìn)行同時(shí)決策.提出了一個(gè)混合整數(shù)規(guī)劃模型對(duì)該問題進(jìn)行優(yōu)化建模,設(shè)計(jì)開發(fā)了一個(gè)基于有向連接圖的兩階段優(yōu)化算法對(duì)問題求初始解,并利用禁忌搜索算法對(duì)所求得的解進(jìn)行改進(jìn).算法第一階段解決儲(chǔ)位分配問題,在此基礎(chǔ)上第二階段利用Hungarian算法對(duì)堆垛機(jī)的存取作業(yè)路徑優(yōu)化問題進(jìn)行求解.最后利用實(shí)例對(duì)算法效率和精度進(jìn)行分析評(píng)價(jià),計(jì)算結(jié)果驗(yàn)證了算法的有效性.關(guān)鍵詞:自動(dòng)化立體倉庫;儲(chǔ)位分配;交叉存取;禁忌搜索算法中圖分類號(hào):F224.3文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):1004?6062(2012)叭一0042-06O引言儲(chǔ)位分配和存取作業(yè)路徑優(yōu)化是自動(dòng)化立體倉庫(AutomatedSt0rage/RetrievalSystem,AS/RS)中兩個(gè)值得關(guān)注的問題.良好的儲(chǔ)位分配策略可以充分利用存儲(chǔ)空間,降低倉儲(chǔ)成本.對(duì)存取作業(yè)路徑進(jìn)行優(yōu)化可以減少堆垛機(jī)的行駛距離,縮短作業(yè)時(shí)間,提高存儲(chǔ)效率.對(duì)于AS/RS中的儲(chǔ)位分配問題,常用的存儲(chǔ)策略分為四類:定位存儲(chǔ),隨機(jī)存儲(chǔ),分類存儲(chǔ),以及共同存儲(chǔ).最早有關(guān)儲(chǔ)位分配策略的研究是Heskett0提出的單位訂單體積索引原則COl(cubeperorderindex).Malmborg和Krishnakumar研究了應(yīng)用定位存儲(chǔ)策略的倉儲(chǔ)系統(tǒng)的最優(yōu)化儲(chǔ)位分配方法.Hsieh和Tsai提出基于物料BOM的分類存儲(chǔ)方法.Muppani和Adil應(yīng)用模擬退火算法解決物料分類問題和儲(chǔ)位分配問題.李曉林等以汽車企業(yè)配送中心為例,研究了儲(chǔ)位動(dòng)態(tài)管理模型.胡列格綜合公平份額分配準(zhǔn)則和ABC分類方法,并考慮關(guān)鍵因素進(jìn)行儲(chǔ)位分配.對(duì)于AS/RS中的堆垛機(jī)存取作業(yè)路徑優(yōu)化問題,Han等的研究結(jié)果表明,當(dāng)堆垛機(jī)的空駛時(shí)間降低50%時(shí),系統(tǒng)效率可以提高1015%.Lee和Sehaer研究了當(dāng)貨物存儲(chǔ)位置確定時(shí)對(duì)存取操作的排序方法.VandenBerg和Gademann”研究了應(yīng)用定位存儲(chǔ)方法的存取路徑優(yōu)化問題.Lerher等研究了采用不同排序方法時(shí)堆垛機(jī)的運(yùn)輸時(shí)間模型.Malmborg和A1一Tassan研究了采用隨機(jī)存儲(chǔ)策略時(shí)不同系統(tǒng)參數(shù)對(duì)系統(tǒng)效率的影響,這些參數(shù)包括:存取路徑設(shè)計(jì),庫存水平,訂貨頻率等.鄭歡”對(duì)自動(dòng)化立體倉庫的存取路徑優(yōu)化問題進(jìn)行研究,并應(yīng)用遺傳算法和蟻群算法進(jìn)行求解.物料的儲(chǔ)位分配將對(duì)存取作業(yè)路徑優(yōu)化產(chǎn)生直接影響,然而現(xiàn)有文獻(xiàn)中對(duì)這兩個(gè)問題之間相互關(guān)系的研究卻很少見.本文研究自動(dòng)化立體倉庫中對(duì)儲(chǔ)位分配及存取作業(yè)路徑同時(shí)進(jìn)行優(yōu)化的問題.設(shè)計(jì)了一個(gè)基于有向連接網(wǎng)的兩階段決策算法對(duì)該問題求初始解,基本思想是:第一階段利用基于有向連接圖的算法對(duì)儲(chǔ)位分配進(jìn)行決策,在此基礎(chǔ)上,第二階段利用指派問題(AssignmentProblem)的最優(yōu)算法進(jìn)行存取作業(yè)的路徑優(yōu)化.在此基礎(chǔ)上,開發(fā)了禁忌搜索算法對(duì)所求得的解進(jìn)行改進(jìn).1儲(chǔ)位分配及存取路徑優(yōu)化模型1.1問題定義基于物料停留期(DurationofStay,DOS)進(jìn)行存儲(chǔ)是?種共同存儲(chǔ)方法”,即在進(jìn)行儲(chǔ)位分配時(shí)考慮不同物料倉庫內(nèi)的停留時(shí)問,盡可能多的利用較好的存儲(chǔ)位置.此外,堆垛機(jī)采用交叉存取方式,以減少總的行駛時(shí)間,提高仔儲(chǔ)效率.交叉存取指堆垛機(jī)在一個(gè)來回程中執(zhí)行一個(gè)存操作和一個(gè)取操作.本節(jié)提一個(gè)混合整數(shù)規(guī)劃模型(MixedIntegerProgramming,MIP)對(duì)自動(dòng)化立體倉庫內(nèi)的儲(chǔ)位分配和存取路徑進(jìn)行同時(shí)優(yōu)化.MIP模型基于如下假設(shè):1)堆垛機(jī)每次操作對(duì)單位物料進(jìn)行存/取;2)堆垛機(jī)從/入庫臺(tái)至每個(gè)儲(chǔ)位的單程行駛時(shí)間已知;3)各物料的DOS已知.1.2模型參數(shù)及決策變量MIP模型包含以下參數(shù):為計(jì)劃周期內(nèi)需要進(jìn)行存/取操作的物料的總數(shù);K為所有儲(chǔ)位數(shù)量;o為物料的到達(dá)時(shí)間;d為物料i的離開時(shí)間;c為從m/入庫臺(tái)至儲(chǔ)位k的收稿日期:2010.0115修回日期:2010-11-06基金項(xiàng)目:國家自然科學(xué)基金資助項(xiàng)目(70802040)作者簡(jiǎn)介:陳璐(1975一),女,安徽合肥人,上海交通大學(xué)講師,博士,主要研究領(lǐng)域?yàn)樯a(chǎn)及物流系統(tǒng)建模與優(yōu)化.Vo1.26.NO.1管理工程學(xué)報(bào)2012年第1期行駛時(shí)間;c為儲(chǔ)位k至儲(chǔ)位的行駛時(shí)間.此外模型中還需定義下列矩陣和集合:定義1.定義一個(gè)矩陣,W=Wli,=1,2,表示任意兩個(gè)物料是否可以在同一位置進(jìn)行存儲(chǔ).W的定義如下:r1,adtoratd,i,=1,i0-oth.rwi.則當(dāng)W.:1時(shí),物料i和在倉庫內(nèi)的停留時(shí)間沒有相互重合,因此i和可以存放在同一儲(chǔ)位.定義2.定義物料集合R,使得集合R中物料的取操作可以和物料i的存操作在一個(gè)交叉存取作業(yè)中完成,即:R.=mIa=d,m=1,2,N,i=1,2,.定義3.定義物料集合s,使得集合s中物料的存操作可以和物料m的取操作在一個(gè)交叉存取作業(yè)中完成,即S:il.=d,i=1,2,m=1,2,.需要做出的決策為:各物料的存儲(chǔ)位置,以及堆垛機(jī)進(jìn)行交叉存取作業(yè)的行駛路徑.因此定義決策變量為:如果物料i存放于儲(chǔ)位k,則=1,否則=0;如果堆垛機(jī)對(duì)物料i和物料m進(jìn)行交叉存取,并且i存放于儲(chǔ)位k,m存放于儲(chǔ)位k,貝Uy=1,否貝0ykk=0.1.3MIP模型定義MIP模型的目標(biāo)函數(shù)為:最小化堆垛機(jī)對(duì)計(jì)劃期內(nèi)所有物料完成存/取操作的總行駛時(shí)間z.(1)MIP模型的約束條件包括:1,i=l,(2)k=l+xtk1+W,i,J=1,i<,k=1,K(3)ykk1,1,(4)mERik.=1Ky1,m=1,(5)iSmk?=1y(+,),i=1,mER,k,k=1,(6),kk0,1(7)式(1)右方第一部分表示堆垛機(jī)對(duì)計(jì)劃周期內(nèi)所有物料進(jìn)行單獨(dú)存和取的行駛時(shí)間總和,第二部分表示采用交叉存取方式所節(jié)省的行駛時(shí)間.因此,式(1)最小化堆垛機(jī)的總行駛時(shí)間.式(2)確保每個(gè)物料只分配給一個(gè)儲(chǔ)位.式(3)確保當(dāng)W=0時(shí),i和不能存放在同一儲(chǔ)位;而當(dāng)W=1時(shí),i和可以存放在同一儲(chǔ)位.式(4)確保一個(gè)交叉存取作業(yè)中僅包含一個(gè)存操作.式(5)保證一個(gè)交叉存取作業(yè)中只包含一個(gè)取操作.式(6)定義y,即當(dāng)且僅當(dāng)=1且=1時(shí),=1.式(7)定義了決策變量的0,1屬性.Goetschalckx和Ratliff指出基于DOS的儲(chǔ)位分配問題是一個(gè)NP難度問題,而本文對(duì)儲(chǔ)位分配和存取路徑進(jìn)行同時(shí)優(yōu)化則具有更大的難度.因此本文首先采用一個(gè)基于有向連接圖的兩階段優(yōu)化算法對(duì)問題進(jìn)行求解.在此基礎(chǔ)上,利用禁忌搜索算法對(duì)所求得的初始解進(jìn)行改善.2優(yōu)化算法設(shè)計(jì)本節(jié)提出一個(gè)基于有向連接圖的兩階段優(yōu)化算法(GraphBasedHeuristics,GBH)進(jìn)行求解,算法第一階段對(duì)物料進(jìn)行儲(chǔ)位分配,并將問題轉(zhuǎn)化為一個(gè)指派問題(AssignmentProblem).第二階段利用指派問題的最優(yōu)化算法對(duì)交叉存取的路徑優(yōu)化問題進(jìn)行求解.2.1儲(chǔ)位分配算法儲(chǔ)位分配算法的設(shè)計(jì)基于以下的最優(yōu)化定理”:定理:對(duì)于采用共同存儲(chǔ)策略的AS/RS,當(dāng)堆垛機(jī)行駛時(shí)間與作業(yè)序列無關(guān)時(shí),當(dāng)且僅當(dāng)以下條件滿足時(shí),一個(gè)存儲(chǔ)策略為最優(yōu)策略:倉庫中第一個(gè)最近儲(chǔ)位中存儲(chǔ)的物料數(shù)量,前兩個(gè)最近儲(chǔ)位中存儲(chǔ)的物料數(shù)量,前個(gè)最近儲(chǔ)位中存儲(chǔ)的物料數(shù)量同時(shí)最大化.要完全滿足定理中的最優(yōu)化條件非常困難,本節(jié)提出了存儲(chǔ)圖的概念,以盡量達(dá)到最優(yōu)化條件的要求.存儲(chǔ)圖是一個(gè)有向連接圖,一個(gè)計(jì)劃周期為的存儲(chǔ)圖G=(V,C,A)定義為:一為時(shí)間節(jié)點(diǎn)集合,V=1,2,+1.節(jié)點(diǎn)1為源節(jié)點(diǎn),節(jié)點(diǎn)+1為匯節(jié)點(diǎn).一c為有向連接弧集合,任意一對(duì)相鄰節(jié)點(diǎn)之間都由一個(gè)有向連接弧連接.一A為有向存儲(chǔ)弧集合.一個(gè)存儲(chǔ)弧表示一個(gè)物料在倉庫內(nèi)的停留時(shí)間,弧尾表示物料到達(dá)倉庫的時(shí)間,弧頭表示物料離開倉庫的時(shí)間.表1物料的停留時(shí)間圖1示例問題的存儲(chǔ)圖存儲(chǔ)圖不僅可以反映出計(jì)劃周期內(nèi)所有物料的DOS信息,而且一條從源點(diǎn)至匯點(diǎn)的路徑中所包含的物料在倉庫內(nèi)的停留時(shí)間不會(huì)相互重合,因此這些物料可以存儲(chǔ)在同一儲(chǔ)位.例如,4種物料的出/入庫時(shí)間如表1所示,計(jì)劃周期為4天.圖1表示的就是這4個(gè)物料的存儲(chǔ)圖.為了定義儲(chǔ)位分配算法,將存儲(chǔ)圖中每條存儲(chǔ)弧賦權(quán)重C一:Z陳璐等:自動(dòng)化立體倉庫中的儲(chǔ)位分配及存取路徑優(yōu)化B+DOS,其中口為一個(gè)遠(yuǎn)大于7T的常數(shù),DOS為物料i在倉庫內(nèi)停留時(shí)間.顯然,包含存儲(chǔ)弧數(shù)量最多的路徑為最長路徑.圖1中存儲(chǔ)圖的最長路徑為125,該路徑長度為2B+4.GBH算法包含以下步驟:(1)找出存儲(chǔ)圖G中從源點(diǎn)至匯點(diǎn)的最長路徑P;(2)將P中包含的物料存儲(chǔ)在當(dāng)前最近的位置;(3)將P中包含的存儲(chǔ)弧從G中刪除;(4)如果A為空,算法終止;否則轉(zhuǎn)到(1).算法每一步都將當(dāng)前存儲(chǔ)圖中最長路徑上的所有物料存放于最近的儲(chǔ)位,這樣可以充分利用距離最近的儲(chǔ)位,最大限度的滿足定理中的最優(yōu)化條件.2.2交叉存取路徑優(yōu)化算法在解決了物料的儲(chǔ)位分配問題之后,第二步需要解決堆垛機(jī)存取作業(yè)的路徑優(yōu)化問題.當(dāng)各物料的儲(chǔ)位確定,即變量集確定之后,對(duì)原MIP模型進(jìn)行如下簡(jiǎn)化.假設(shè)物料i的儲(chǔ)位為,則:f,(8)L0otherwise.定義新的決策變量業(yè)中有且僅有一個(gè)存操作和一個(gè)取操作.式(13)定義了決策變量的0,1屬性.通過上述對(duì)MIP模型的簡(jiǎn)化,將存取路徑優(yōu)化問題轉(zhuǎn)化為一個(gè)標(biāo)準(zhǔn)的指派問題,可以采用Hungarian或Simplex方法求得最優(yōu)解.此類算法的求解效率非常高.3禁忌搜索算法禁忌搜索的思想最早由Glover16提出,它是對(duì)局部鄰域搜索的一種擴(kuò)展,是一種全局逐步尋優(yōu)算法,是對(duì)人類智力過程的一種模擬.通過引入一個(gè)靈活的鄰域結(jié)構(gòu)和相應(yīng)的禁忌準(zhǔn)則來避免迂回搜索,最終實(shí)現(xiàn)全局優(yōu)化.本文使用禁忌搜索算法的目的是通過對(duì)鄰居解的搜索,改善優(yōu)化算法對(duì)大規(guī)模問題的求解精度.3.1解的向量表示物料的儲(chǔ)位分配計(jì)劃可以用一個(gè)向量集合丌表示,丌=仃l,仃2,7rl,其中K為AS/RS內(nèi)所有儲(chǔ)位數(shù)量,仃表示在整個(gè)計(jì)劃周期內(nèi)存放在儲(chǔ)位k的所有物料序列,k=一441,2,K.用n表示序列丌所包含的物料數(shù)量,即n:I7r1,則向量丌可以表示為:7r=(7r(1),?-,7r(n),丌()為序列r中第k個(gè)物料,即向量中第個(gè)位置的元素.3.2鄰域結(jié)構(gòu)定義鄰域結(jié)構(gòu)是通過對(duì)任意兩個(gè)儲(chǔ)位的存儲(chǔ)物料進(jìn)行交換(swap)操作來實(shí)現(xiàn)的.假設(shè)k和k為任意兩個(gè)儲(chǔ)位,k,=1,2,K,則當(dāng)前可行解的一個(gè)鄰居解可以通過將向量中的物料序列與向量.中的物料序列進(jìn)行交換而獲得.當(dāng)或后為空時(shí),其中一個(gè)儲(chǔ)位的所有物料被移動(dòng)到另外?個(gè)儲(chǔ)位.用SW(k,k)來表示在儲(chǔ)位k與之問的交換操作,則對(duì)當(dāng)前解的所有交換操作可以表示為:KOP()=Usw(k,k).xK當(dāng)前解的鄰域可以表示為:(7r)=丌ISW(k,k)EOP(丌)3.3鄰居解的快速評(píng)價(jià)應(yīng)用Hungarian算法對(duì)向量7r的鄰居解進(jìn)行求解,可以獲得堆垛機(jī)的存取作業(yè)路徑,并計(jì)算出堆垛機(jī)完成計(jì)劃周期內(nèi)所有物料存/取作業(yè)的總行駛時(shí)間z.但是如果采_II該法對(duì)鄰居解進(jìn)行評(píng)價(jià)需要在搜索過程中多次調(diào)用Hungalian算法,將花費(fèi)大量計(jì)算時(shí)間.本節(jié)采用最近移動(dòng)距離算法來求解堆垛機(jī)的存取作業(yè)路徑優(yōu)化問題,以獲得總行駛時(shí)間z的下界z,并利用Z來對(duì)鄰居解進(jìn)行快速評(píng)價(jià).最近移動(dòng)距離算法具體步驟如下所述:(1)對(duì)所有i,i=l,在集合R中選擇距離i最近的物料rn.(2)對(duì)物料i和物料m進(jìn)行交叉存取.(3)R.一R.一rn.3.4禁忌表及搜索策略為了避免循環(huán)搜索的發(fā)生,需要定義禁忌表(tabulist)在本文的搜索算法中,一旦在k和k之間發(fā)生了一個(gè)交換操作,就在禁忌表中增加這兩個(gè)儲(chǔ)位及它們所存儲(chǔ)的物料序列丌和在后續(xù)若干步驟的搜索中,禁止將仃和7r,r1所包含的物料重新交換給儲(chǔ)位和k.禁忌表的長度有限,處理該表時(shí)采取的是先進(jìn)先出(FIFO)策略.算法采用best-fit搜索策略.對(duì)當(dāng)前解7r的鄰域中所仃未被禁忌的鄰居解進(jìn)行快速評(píng)價(jià),也就是計(jì)算每個(gè)鄰居斛的目標(biāo)函數(shù)值低界z,然后移動(dòng)到具有最小z的解.3.5搜索算法描述(1)算法初始化:7r:仃,Z=Z(仃),T=0,her=Niter=0.(2)賦值her:=her+1,Nher:=Niter+l.任仃的鄰域中找到最好的非禁忌鄰居解7r,并且修改禁忌表T.賦值仃:=仃.(3)如果z()<Z,則賦值7r:仃,Z=Z(仃),Niter=0,并且返回步驟(2).(4)如果(terMaxher)并且(NlterNonlmpher),則返Vo1.26.No.1管理工程學(xué)報(bào)2012年第1期回步驟(2);否則終止搜索算法.當(dāng)算法在規(guī)定次數(shù)(Nonlmpher)的迭代之后,對(duì)當(dāng)前得到的最好解不再能夠改進(jìn),或者迭代的總次數(shù)達(dá)到了一個(gè)預(yù)先設(shè)定的最大迭代次數(shù)Maxlter時(shí),算法終止.4數(shù)據(jù)實(shí)驗(yàn)為了對(duì)所提出的算法進(jìn)行評(píng)價(jià),本節(jié)設(shè)計(jì)了一系列具有不同參數(shù)的問題進(jìn)行了大量實(shí)例計(jì)算.算法在一臺(tái)個(gè)人計(jì)算機(jī)上由VisualC+編程實(shí)現(xiàn),計(jì)算機(jī)配置為:CentrinoDuoCPU2.0GHz,2.0GBRAM.OPLCPLEX用于對(duì)MIP模型求最優(yōu)解.4.1問題參數(shù)定義假設(shè)AS/RS的每個(gè)貨架長為,高為,堆垛機(jī)水平方向速度為y,垂直方向速度為.則堆垛機(jī)水平及垂直方向的最大行駛時(shí)間為t=Vh,以及t=H/Vh.設(shè)Y=maxt,t,b=mintJY,tJY,則y表示堆垛機(jī)最大行駛時(shí)間.b表示貨架比例.對(duì)貨架比例進(jìn)行歸一化,即設(shè)定Y=1.實(shí)例問題的具體參數(shù)定義如下:計(jì)劃周期取值分別為:8,15,30;貨架比例b取值分別為:1,0.8,0.6,0.4;物料數(shù)量取值為10200;物料在倉庫內(nèi)的停留期在一致性分布區(qū)間U(1,T)內(nèi)隨機(jī)產(chǎn)生;每個(gè)儲(chǔ)位的水平及垂直行駛時(shí)間(h,)分別在一致性分布區(qū)間(0,1)和U(0,b)內(nèi)隨機(jī)產(chǎn)生.儲(chǔ)位k的行駛時(shí)間c為:C=max(h,).任意兩個(gè)儲(chǔ)位k及k之間的行駛時(shí)間c為:c=max(1h一h,I,I一1),當(dāng)k=時(shí),c,=.4.2單一存取和交叉存取為了比較堆垛機(jī)單一存取方式和交叉存取方式對(duì)系統(tǒng)效率的影響.將本文的GBH算法與Montulet等提出的針對(duì)單一存取方式的儲(chǔ)位分配算法進(jìn)行比較,如圖2所示._.一b=l,0卜_b=0,8一斗一b=0,6-b=0,4(1O,lO)(2O,20)(40,40)(60,60)(80,SO)(100,100)(200,2oo)Problemsize(N,K)圖2單一存取方式和交叉存取方式的比較(T=8)從圖2可以得出如下結(jié)論:(1)較之于單一存取方式,采用交叉存取方式可以大大降低堆垛機(jī)的平均行駛時(shí)間,并且隨著問題規(guī)模的增大,這種改進(jìn)變得更加明顯.(2)實(shí)例中的物料數(shù)量和儲(chǔ)位數(shù)量分別從10個(gè)到200個(gè)不等,實(shí)驗(yàn)結(jié)果顯示GBH算法的性能與問題規(guī)模無關(guān),表明了算法較好的魯棒性.(3)GBH算法性能與系統(tǒng)參數(shù)無關(guān),當(dāng)b=1.0時(shí),t的平均改進(jìn)為12.61%,當(dāng)b=0.8時(shí),t的平均改進(jìn)為12.75%,當(dāng)b=0.6時(shí),t的平均改進(jìn)為14.O1%,當(dāng)b=0.4時(shí),t的平均改進(jìn)為13.53%.4.3算法性能分析本節(jié)在大量算例的基礎(chǔ)上對(duì)文中提出的GBH算法和禁忌搜索算法的求解精度和效率進(jìn)行分析.表2比較了在不同問題參數(shù)(,K和b)下,應(yīng)用GBH算法和禁忌搜索算法求得解的堆垛機(jī)平均行駛時(shí)間和CPU計(jì)算時(shí)間.對(duì)每一類問題參數(shù),實(shí)驗(yàn)隨機(jī)產(chǎn)生10組數(shù)據(jù),并記錄了禁忌搜索算法相對(duì)于GBH算法的改進(jìn)比例.表2的數(shù)據(jù)顯示,禁忌搜索算法相對(duì)與GBH算法具有較大的改進(jìn),在1.20%至6.48%之間.禁忌搜索算法的計(jì)算時(shí)間隨問題規(guī)模增大而增加,最大計(jì)算時(shí)間均在15分鐘之內(nèi),這表明了算法具有較好的求解效率.5結(jié)論倉儲(chǔ)作業(yè)是一連串的”存”和”取”的動(dòng)作組合.如何使“存”和”取”的動(dòng)作快速而有效,從而提高倉儲(chǔ)作業(yè)的運(yùn)作效率,對(duì)儲(chǔ)位及存取路徑進(jìn)行有效的管理非常必要.本文研究了自動(dòng)化立體倉庫中的物料儲(chǔ)位分配及存取作業(yè)路徑進(jìn)行同時(shí)優(yōu)化的問題,目標(biāo)是最小化堆垛機(jī)完成計(jì)劃周期內(nèi)所有物料存取作業(yè)的總行駛時(shí)間.提出了基于圖形的兩階段決策算法對(duì)問題進(jìn)行求解,并利用禁忌搜索算法對(duì)所求得的解進(jìn)行改進(jìn),實(shí)例計(jì)算證明了算法的有效性,以及交叉存取方式對(duì)提高系統(tǒng)效率的重要性.本文為自動(dòng)化立體倉庫中運(yùn)作優(yōu)化及決策提供了新的思路和途徑,為進(jìn)一步研究倉儲(chǔ)作業(yè)系統(tǒng)總體優(yōu)化,并將研究成果應(yīng)用于倉儲(chǔ)管理的實(shí)際工作,提高企業(yè)的經(jīng)濟(jì)效益提供了參考.允許物料在倉庫停留期內(nèi)存儲(chǔ)位置發(fā)生變化,實(shí)現(xiàn)動(dòng)態(tài)儲(chǔ)位管理,以最大限度的利用倉庫現(xiàn)有資源,進(jìn)一步提高存取作業(yè)效率將是今后的研究目標(biāo).?-45?-Sf】肇bug一重Qg陳璐等:自動(dòng)化立體倉庫中的儲(chǔ)位分配及存取路徑優(yōu)化23參考文獻(xiàn)FrancisRL,McGinnisLF,WhiteJA.Facilitylayoutandlocation:ananalyticalapproachM.PrenticeHall:EnglewoodCliffs,N.J.1992.HeskettJL.Cubeperorderindex-AkeytowarehousestocklocationJ.TransportandDistributionManagement,1963,3:2731.Heskett兒.Puttingthecube-per-orderindextoworkinwarehouselayoutJ.TransportandDistributionManagement,1964,4:23304MalmborgCJ,KrishnakumarB.OptimalstorageassignmentpoliciesformultiaddresswarehousesystemsJ.IEEETransactiononSystems,Man,andCybernetics,1989,19(1):197204.5HsiehS,TsaiKC.ABOMorientedclassbasedstorageassignmentinanautomatedstorage/retrievalsystemJ.InternationalJournalofAdvancedManufacturingTechnology,2001,17:683691.6MuppaniVR,GendraKumar,AdilGK.Efficientformationof.46.789101213storageclassesforwarehousestoragelocationassignment:AsimulatedannealingapproachJ.Omega,2008,38:609618.李曉林,劉波濤.配送中心儲(chǔ)位動(dòng)態(tài)管理模型研究J.軟件導(dǎo)刊,2007(1):5153.胡列格,胡建國.配送中心儲(chǔ)位分配決策方法的動(dòng)態(tài)研究J.長沙交通學(xué)院學(xué)報(bào),2004,20(2):6872HanMH,McGinnisLF,ShiehJS,WhiteJA.0nsequemringretrievalsinanautomatedstorage/retrievalsystemJ11ETransaction,1987,3:5666.LeeHF,SchaeferSK.Sequencingmethodsforaatomate(1S|OIageandretrievalsystemswithdedicatedstorageJ1.(omputcrs&IndustrialEngineering,1997,32(2),351362VandenBergJP,GademannAJ.R.M.Optimalroutinginallautomatedstorage/retrievalsystemwithdedicatedstorageJj.1ieTransactions,1997,31:4074I5.LerherT,TraveltimemodelsforautomatedwarehouseswithaisletransferringstorageandretrievalmachineJ.EuropeanJournalofOperationalResearch,2010,205:571583.MalmborgCJ,AITassanK.AnintegratedperformanceumdelforVo1.26,No.1管理工程學(xué)報(bào)2012年第1期1415orderpickingsystemswithrandomizedstorageJ.AppliedMathematicalModelling,2000,24:95111.鄭歡.自動(dòng)化立體倉庫路徑優(yōu)化問題研究D.碩士學(xué)位論文.吉林大學(xué),2006.GoetsehalckxM,RatliffHD.SharedstoragepoliciesbasedonthedurationstayofunitloadsJ.ManagementScience,1990,36(9):11201132.16GloverF.FuturepathsartificialintelligenceJ1986,13(5):533549.forintegerprogrammingandlinkstoComputersandOperationsResearch,17MontuletP,LangevinA,RiopelD.Leproblmedeloptimisationde1entreposagepartag6:m6thodesexacteetheufistiqueJ.INFOR,1997,35(2):138153.OptimizationforStorageLocationAssignmentsandInterleavingProblemsinanAutomatedStorage/RetrievalSystemCHENLu,LUZhiqiang(SchoolofMechanicalEngineering,ShanghaiJiaoTongUniversity,Shanghai200240,China)Abstract:AutomatedStorage/RetrievalSystems(AS/RS)arewidelyusedinwarehousesanddistributioncenterseverywherearoundtheworld.Storagelocationassignmentandinterleavesequencingaretwoimportantdecision-makingproblemsinAS/RSmanagement.Althoughthesetwoproblemsarelogicallyinterrelated,mostpreviousresearchhasfocusedonjustoneproblematatime.Studyingasinglepolicyinisolationwouldbeacceptableifitdoesnotinteractwithotherfunctions.However,doingsoisapparentlynotthecaseinmanyreallifesituations.MaximumthroughputofAS/RSsystemmayonlybeobtainedfromanoptimalcombinationofstorageassignmentandinterleavingpolicy.ThispaperaddresseslocationassignmentandinterleavingproblemsinAR/RSatthesametime.Anincomingunitloadisassignedtoastoragelocationaccordingtoitsdurationofstay(DOS).Storage/Retrieval(S/R)machinesperformstoragesandretrievalsinthedualcommand(DC)mode.DCmodemeansthatanS/RmachinepicksupanitemfromanI/0station,stoanotherlocationtoretrieveanitem,andthenreturnstotheI/Ostationtodeliverit.Theproposedmethodmustprovidenotonlystoragelocationsbutalsostorage/retrievalinterleavingsequencesofS/Rmachines.TheobjectiveistominimizetheaveragetraveltimeofS/Rmachinestoprocessstorageorretrievaloperations,thereforemaximizingtheoperationalefficiencyoftheAS/RS.Anintegratedprogrammingmodelisprovidedtoreachanoptimalsolutiontol