自动化立体仓库中的储位分配及存取路径优化.doc

自动化立体仓库中的储位分配及存取路径优化Vo1.26.No.1管理工程学报JournalofIndustrialEngineering/EngineeringManagement20l2年第1期自动化立体仓库中的储位分配及存取路径优化陈璐,陆志强(上海交通大学机械与动力工程学院工业工程与物流工程系,上海200240)摘要:储位分配和存取作业路径优化是仓储管理中的两个重要决策问题.本文研究如何在自动化立体仓库中对这两个问题进行同时决策.提出了一个混合整数规划模型对该问题进行优化建模,设计开发了一个基于有向连接图的两阶段优化算法对问题求初始解,并利用禁忌搜索算法对所求得的解进行改进.算法第一阶段解决储位分配问题,在此基础上第二阶段利用Hungarian算法对堆垛机的存取作业路径优化问题进行求解.最后利用实例对算法效率和精度进行分析评价,计算结果验证了算法的有效性.关键词:自动化立体仓库;储位分配;交叉存取;禁忌搜索算法中图分类号:F224.3文献标识码:A文章编号:1004?6062(2012)叭一0042-06O引言储位分配和存取作业路径优化是自动化立体仓库(AutomatedSt0rage/RetrievalSystem,AS/RS)中两个值得关注的问题.良好的储位分配策略可以充分利用存储空间,降低仓储成本.对存取作业路径进行优化可以减少堆垛机的行驶距离,缩短作业时间,提高存储效率.对于AS/RS中的储位分配问题,常用的存储策略分为四类:定位存储,随机存储,分类存储,以及共同存储.最早有关储位分配策略的研究是Heskett0提出的单位订单体积索引原则COl(cubeperorderindex).Malmborg和Krishnakumar研究了应用定位存储策略的仓储系统的最优化储位分配方法.Hsieh和Tsai提出基于物料BOM的分类存储方法.Muppani和Adil应用模拟退火算法解决物料分类问题和储位分配问题.李晓林等以汽车企业配送中心为例,研究了储位动态管理模型.胡列格综合公平份额分配准则和ABC分类方法,并考虑关键因素进行储位分配.对于AS/RS中的堆垛机存取作业路径优化问题,Han等的研究结果表明,当堆垛机的空驶时间降低50%时,系统效率可以提高1015%.Lee和Sehaer研究了当货物存储位置确定时对存取操作的排序方法.VandenBerg和Gademann”研究了应用定位存储方法的存取路径优化问题.Lerher等研究了采用不同排序方法时堆垛机的运输时间模型.Malmborg和A1一Tassan研究了采用随机存储策略时不同系统参数对系统效率的影响,这些参数包括:存取路径设计,库存水平,订货频率等.郑欢”对自动化立体仓库的存取路径优化问题进行研究,并应用遗传算法和蚁群算法进行求解.物料的储位分配将对存取作业路径优化产生直接影响,然而现有文献中对这两个问题之间相互关系的研究却很少见.本文研究自动化立体仓库中对储位分配及存取作业路径同时进行优化的问题.设计了一个基于有向连接网的两阶段决策算法对该问题求初始解,基本思想是:第一阶段利用基于有向连接图的算法对储位分配进行决策,在此基础上,第二阶段利用指派问题(AssignmentProblem)的最优算法进行存取作业的路径优化.在此基础上,开发了禁忌搜索算法对所求得的解进行改进.1储位分配及存取路径优化模型1.1问题定义基于物料停留期(DurationofStay,DOS)进行存储是?种共同存储方法”,即在进行储位分配时考虑不同物料仓库内的停留时问,尽可能多的利用较好的存储位置.此外,堆垛机采用交叉存取方式,以减少总的行驶时间,提高仔储效率.交叉存取指堆垛机在一个来回程中执行一个存操作和一个取操作.本节提一个混合整数规划模型(MixedIntegerProgramming,MIP)对自动化立体仓库内的储位分配和存取路径进行同时优化.MIP模型基于如下假设:1)堆垛机每次操作对单位物料进行存/取;2)堆垛机从/入库台至每个储位的单程行驶时间已知;3)各物料的DOS已知.1.2模型参数及决策变量MIP模型包含以下参数:为计划周期内需要进行存/取操作的物料的总数;K为所有储位数量;o为物料的到达时间;d为物料i的离开时间;c为从m/入库台至储位k的收稿日期:2010.0115修回日期:2010-11-06基金项目:国家自然科学基金资助项目(70802040)作者简介:陈璐(1975一),女,安徽合肥人,上海交通大学讲师,博士,主要研究领域为生产及物流系统建模与优化.Vo1.26.NO.1管理工程学报2012年第1期行驶时间;c为储位k至储位的行驶时间.此外模型中还需定义下列矩阵和集合:定义1.定义一个矩阵,W=Wli,=1,2,表示任意两个物料是否可以在同一位置进行存储.W的定义如下:r1,adtoratd,i,=1,i0-oth.rwi.则当W.:1时,物料i和在仓库内的停留时间没有相互重合,因此i和可以存放在同一储位.定义2.定义物料集合R,使得集合R中物料的取操作可以和物料i的存操作在一个交叉存取作业中完成,即:R.=mIa=d,m=1,2,N,i=1,2,.定义3.定义物料集合s,使得集合s中物料的存操作可以和物料m的取操作在一个交叉存取作业中完成,即S:il.=d,i=1,2,m=1,2,.需要做出的决策为:各物料的存储位置,以及堆垛机进行交叉存取作业的行驶路径.因此定义决策变量为:如果物料i存放于储位k,则=1,否则=0;如果堆垛机对物料i和物料m进行交叉存取,并且i存放于储位k,m存放于储位k,贝Uy=1,否贝0ykk=0.1.3MIP模型定义MIP模型的目标函数为:最小化堆垛机对计划期内所有物料完成存/取操作的总行驶时间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)右方第一部分表示堆垛机对计划周期内所有物料进行单独存和取的行驶时间总和,第二部分表示采用交叉存取方式所节省的行驶时间.因此,式(1)最小化堆垛机的总行驶时间.式(2)确保每个物料只分配给一个储位.式(3)确保当W=0时,i和不能存放在同一储位;而当W=1时,i和可以存放在同一储位.式(4)确保一个交叉存取作业中仅包含一个存操作.式(5)保证一个交叉存取作业中只包含一个取操作.式(6)定义y,即当且仅当=1且=1时,=1.式(7)定义了决策变量的0,1属性.Goetschalckx和Ratliff指出基于DOS的储位分配问题是一个NP难度问题,而本文对储位分配和存取路径进行同时优化则具有更大的难度.因此本文首先采用一个基于有向连接图的两阶段优化算法对问题进行求解.在此基础上,利用禁忌搜索算法对所求得的初始解进行改善.2优化算法设计本节提出一个基于有向连接图的两阶段优化算法(GraphBasedHeuristics,GBH)进行求解,算法第一阶段对物料进行储位分配,并将问题转化为一个指派问题(AssignmentProblem).第二阶段利用指派问题的最优化算法对交叉存取的路径优化问题进行求解.2.1储位分配算法储位分配算法的设计基于以下的最优化定理”:定理:对于采用共同存储策略的AS/RS,当堆垛机行驶时间与作业序列无关时,当且仅当以下条件满足时,一个存储策略为最优策略:仓库中第一个最近储位中存储的物料数量,前两个最近储位中存储的物料数量,前个最近储位中存储的物料数量同时最大化.要完全满足定理中的最优化条件非常困难,本节提出了存储图的概念,以尽量达到最优化条件的要求.存储图是一个有向连接图,一个计划周期为的存储图G=(V,C,A)定义为:一为时间节点集合,V=1,2,+1.节点1为源节点,节点+1为汇节点.一c为有向连接弧集合,任意一对相邻节点之间都由一个有向连接弧连接.一A为有向存储弧集合.一个存储弧表示一个物料在仓库内的停留时间,弧尾表示物料到达仓库的时间,弧头表示物料离开仓库的时间.表1物料的停留时间图1示例问题的存储图存储图不仅可以反映出计划周期内所有物料的DOS信息,而且一条从源点至汇点的路径中所包含的物料在仓库内的停留时间不会相互重合,因此这些物料可以存储在同一储位.例如,4种物料的出/入库时间如表1所示,计划周期为4天.图1表示的就是这4个物料的存储图.为了定义储位分配算法,将存储图中每条存储弧赋权重C一:Z陈璐等:自动化立体仓库中的储位分配及存取路径优化B+DOS,其中口为一个远大于7T的常数,DOS为物料i在仓库内停留时间.显然,包含存储弧数量最多的路径为最长路径.图1中存储图的最长路径为125,该路径长度为2B+4.GBH算法包含以下步骤:(1)找出存储图G中从源点至汇点的最长路径P;(2)将P中包含的物料存储在当前最近的位置;(3)将P中包含的存储弧从G中删除;(4)如果A为空,算法终止;否则转到(1).算法每一步都将当前存储图中最长路径上的所有物料存放于最近的储位,这样可以充分利用距离最近的储位,最大限度的满足定理中的最优化条件.2.2交叉存取路径优化算法在解决了物料的储位分配问题之后,第二步需要解决堆垛机存取作业的路径优化问题.当各物料的储位确定,即变量集确定之后,对原MIP模型进行如下简化.假设物料i的储位为,则:f,(8)L0otherwise.定义新的决策变量业中有且仅有一个存操作和一个取操作.式(13)定义了决策变量的0,1属性.通过上述对MIP模型的简化,将存取路径优化问题转化为一个标准的指派问题,可以采用Hungarian或Simplex方法求得最优解.此类算法的求解效率非常高.3禁忌搜索算法禁忌搜索的思想最早由Glover16提出,它是对局部邻域搜索的一种扩展,是一种全局逐步寻优算法,是对人类智力过程的一种模拟.通过引入一个灵活的邻域结构和相应的禁忌准则来避免迂回搜索,最终实现全局优化.本文使用禁忌搜索算法的目的是通过对邻居解的搜索,改善优化算法对大规模问题的求解精度.3.1解的向量表示物料的储位分配计划可以用一个向量集合丌表示,丌=仃l,仃2,7rl,其中K为AS/RS内所有储位数量,仃表示在整个计划周期内存放在储位k的所有物料序列,k=一441,2,K.用n表示序列丌所包含的物料数量,即n:I7r1,则向量丌可以表示为:7r=(7r(1),?-,7r(n),丌()为序列r中第k个物料,即向量中第个位置的元素.3.2邻域结构定义邻域结构是通过对任意两个储位的存储物料进行交换(swap)操作来实现的.假设k和k为任意两个储位,k,=1,2,K,则当前可行解的一个邻居解可以通过将向量中的物料序列与向量.中的物料序列进行交换而获得.当或后为空时,其中一个储位的所有物料被移动到另外?个储位.用SW(k,k)来表示在储位k与之问的交换操作,则对当前解的所有交换操作可以表示为:KOP()=Usw(k,k).xK当前解的邻域可以表示为:(7r)=丌ISW(k,k)EOP(丌)3.3邻居解的快速评价应用Hungarian算法对向量7r的邻居解进行求解,可以获得堆垛机的存取作业路径,并计算出堆垛机完成计划周期内所有物料存/取作业的总行驶时间z.但是如果采_II该法对邻居解进行评价需要在搜索过程中多次调用Hungalian算法,将花费大量计算时间.本节采用最近移动距离算法来求解堆垛机的存取作业路径优化问题,以获得总行驶时间z的下界z,并利用Z来对邻居解进行快速评价.最近移动距离算法具体步骤如下所述:(1)对所有i,i=l,在集合R中选择距离i最近的物料rn.(2)对物料i和物料m进行交叉存取.(3)R.一R.一rn.3.4禁忌表及搜索策略为了避免循环搜索的发生,需要定义禁忌表(tabulist)在本文的搜索算法中,一旦在k和k之间发生了一个交换操作,就在禁忌表中增加这两个储位及它们所存储的物料序列丌和在后续若干步骤的搜索中,禁止将仃和7r,r1所包含的物料重新交换给储位和k.禁忌表的长度有限,处理该表时采取的是先进先出(FIFO)策略.算法采用best-fit搜索策略.对当前解7r的邻域中所仃未被禁忌的邻居解进行快速评价,也就是计算每个邻居斛的目标函数值低界z,然后移动到具有最小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管理工程学报2012年第1期回步骤(2);否则终止搜索算法.当算法在规定次数(Nonlmpher)的迭代之后,对当前得到的最好解不再能够改进,或者迭代的总次数达到了一个预先设定的最大迭代次数Maxlter时,算法终止.4数据实验为了对所提出的算法进行评价,本节设计了一系列具有不同参数的问题进行了大量实例计算.算法在一台个人计算机上由VisualC+编程实现,计算机配置为:CentrinoDuoCPU2.0GHz,2.0GBRAM.OPLCPLEX用于对MIP模型求最优解.4.1问题参数定义假设AS/RS的每个货架长为,高为,堆垛机水平方向速度为y,垂直方向速度为.则堆垛机水平及垂直方向的最大行驶时间为t=Vh,以及t=H/Vh.设Y=maxt,t,b=mintJY,tJY,则y表示堆垛机最大行驶时间.b表示货架比例.对货架比例进行归一化,即设定Y=1.实例问题的具体参数定义如下:计划周期取值分别为:8,15,30;货架比例b取值分别为:1,0.8,0.6,0.4;物料数量取值为10200;物料在仓库内的停留期在一致性分布区间U(1,T)内随机产生;每个储位的水平及垂直行驶时间(h,)分别在一致性分布区间(0,1)和U(0,b)内随机产生.储位k的行驶时间c为:C=max(h,).任意两个储位k及k之间的行驶时间c为:c=max(1h一h,I,I一1),当k=时,c,=.4.2单一存取和交叉存取为了比较堆垛机单一存取方式和交叉存取方式对系统效率的影响.将本文的GBH算法与Montulet等提出的针对单一存取方式的储位分配算法进行比较,如图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可以得出如下结论:(1)较之于单一存取方式,采用交叉存取方式可以大大降低堆垛机的平均行驶时间,并且随着问题规模的增大,这种改进变得更加明显.(2)实例中的物料数量和储位数量分别从10个到200个不等,实验结果显示GBH算法的性能与问题规模无关,表明了算法较好的鲁棒性.(3)GBH算法性能与系统参数无关,当b=1.0时,t的平均改进为12.61%,当b=0.8时,t的平均改进为12.75%,当b=0.6时,t的平均改进为14.O1%,当b=0.4时,t的平均改进为13.53%.4.3算法性能分析本节在大量算例的基础上对文中提出的GBH算法和禁忌搜索算法的求解精度和效率进行分析.表2比较了在不同问题参数(,K和b)下,应用GBH算法和禁忌搜索算法求得解的堆垛机平均行驶时间和CPU计算时间.对每一类问题参数,实验随机产生10组数据,并记录了禁忌搜索算法相对于GBH算法的改进比例.表2的数据显示,禁忌搜索算法相对与GBH算法具有较大的改进,在1.20%至6.48%之间.禁忌搜索算法的计算时间随问题规模增大而增加,最大计算时间均在15分钟之内,这表明了算法具有较好的求解效率.5结论仓储作业是一连串的”存”和”取”的动作组合.如何使“存”和”取”的动作快速而有效,从而提高仓储作业的运作效率,对储位及存取路径进行有效的管理非常必要.本文研究了自动化立体仓库中的物料储位分配及存取作业路径进行同时优化的问题,目标是最小化堆垛机完成计划周期内所有物料存取作业的总行驶时间.提出了基于图形的两阶段决策算法对问题进行求解,并利用禁忌搜索算法对所求得的解进行改进,实例计算证明了算法的有效性,以及交叉存取方式对提高系统效率的重要性.本文为自动化立体仓库中运作优化及决策提供了新的思路和途径,为进一步研究仓储作业系统总体优化,并将研究成果应用于仓储管理的实际工作,提高企业的经济效益提供了参考.允许物料在仓库停留期内存储位置发生变化,实现动态储位管理,以最大限度的利用仓库现有资源,进一步提高存取作业效率将是今后的研究目标.?-45?-Sf】肇bug一重Qg陈璐等:自动化立体仓库中的储位分配及存取路径优化23参考文献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.李晓林,刘波涛.配送中心储位动态管理模型研究J.软件导刊,2007(1):5153.胡列格,胡建国.配送中心储位分配决策方法的动态研究J.长沙交通学院学报,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管理工程学报2012年第1期1415orderpickingsystemswithrandomizedstorageJ.AppliedMathematicalModelling,2000,24:95111.郑欢.自动化立体仓库路径优化问题研究D.硕士学位论文.吉林大学,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