（控制理论与控制工程专业论文）配送中心拣货系统优化.pdf

原创性声明 i ilj lli 1 1 1 j i iit l li ii 17 9 4 5 4 9 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明。本声明的法律责任由本人 承担。 论文作者签名：日期： 关于学位论文使用授权的声明 本人同意学校保留或向国家有关部门或机构送交论文的印刷件和电子 版，允许论文被查阅和借阅；本人授权山东大学可以将本学位论文的全部 或部分内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手 段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：建氆么枉导师签名 期： 一一j 山东大学博士学位论文 目录 摘要i a b s t r a c t i v 缩略词注释表v i i i 第一章绪论1 1 1 研究背景和问题的提出1 1 1 1研究背景1 1 1 2问题的提出2 1 2 国内外研究现状4 1 2 1储位分配问题的研究现状4 1 2 2自动分拣系统的研究现状1 0 1 3 本文的主要研究内容13 第二章配送中心拣货系统概述1 5 2 1 配送中心概述15 2 1 1配送中心的形成及特征1 5 2 1 2配送中心的作业环节和区域配置1 5 2 2 拣货系统的相关概念和理论1 6 2 2 1拣货系统的基本概念1 6 2 2 2拣货系统分类及拣货策略1 7 2 2 3拣货系统优化问题分类1 8 2 2 4 拣货系统优化目标1 9 2 3 储位分配问题概述2 1 2 3 1储位分配策略。2 l 2 3 2 货物特性指标2 5 2 3 3货物分类方法2 7 2 3 4储位特性及存取作业方式2 8 2 3 5出库储位的确定和出入库作业顺序3 0 2 3 6 货架模型的类型31 2 4 自动分拣系统概述3 2 2 4 1自动分拣机的种类3 2 山东大学博士学位论文 2 4 2复合式自动分拣系统3 3 2 4 3 e i q 分析3 4 2 5 小结3 6 第三章基于d o s 的储位分配方法设计及仿真3 7 3 1 基于d o s 的储位分配最优化模型3 7 3 2 基于d o s 的静态贪婪式储位分配方法3 9 3 3 基于d o s 的动态储位分配方法4 l 3 3 1 基于d o s 的动态储位分配方法设计4 2 3 3 2基于d o s 的动态储位分配方法的关键技术4 4 3 4 基于d o s 的动态储位分配方法仿真4 7 3 4 1仿真程序设计。4 8 3 4 2仓库布局和仿真参数设计5 2 3 4 3仿真方案设计5 9 3 4 4 仿真结果及分析。6 6 3 5 小结7 0 第四章单复合式自动分拣系统模型与优化7 2 4 1 单复合式自动分拣系统模型7 2 4 1 1假设条件和参数7 2 4 1 2 分拣成本分析。7 4 4 1 3优化模型7 6 4 2 模型求解7 7 4 3 应用实例7 9 4 3 1实例问题7 9 4 3 2实例求解8 0 4 4 小结8 2 第五章多复合式自动分拣系统模型与优化8 4 5 1 多复合式自动分拣系统模型8 4 5 1 1假设条件和参数8 4 5 1 2分拣成本分析。8 5 5 1 3优化模型8 7 山东大学博士学位论文 5 2 模型求解 5 2 1回溯法设计 5 2 2 求解程序设计 5 3 应用实例 5 3 1实例问题 5 3 2实例求解 5 4d 、结 第六章总结与展望 6 1 总结 6 2 展望 附录 参考文献 至| 【谢 攻读博士学位期间完成的论文及参加的科研课题 英文论文一 英文论文二 山东大学博士学位论文 c o n t e n t s c h i n e s ea b s t r a c t i e n g l i s ha b s t r a c t i v l i s to fa b b r e v i a t i o n s v i i i c h a p t e r li n t r o d u c t i o n 1 1 1 b a c k g r o u n da n dp r o b l e m 1 1 1 1b a c k g r o u n d 1 1 1 2p r o b l e ms t a t e m e n t 2 1 2l i t e r a t u r er e v i e w 。4 1 2 1l i t e r a t u r er e v i e wo ns t o r a g el o c a t i o na s s i g n m e n tp r o b l e m 4 1 2 2l i t e r a t u r er e v i e wo na u t o m a t e ds o r t i n gs y s t e m 10 1 3r e s e a r c hc o n t e n t so f t h i sp a p e r 。1 3 c h a p t e r 2o u t l i n eo f o r d e rp i c k i n gs y s t e mi nad i s t r i b u t i o nc e n t e r 。1 5 2 1o u t l i n eo fd i s t r i b u t i o nc e n t e r 。1 5 2 1 1e m e r g e n c ea n dc h a r a c t e r i s t i c so fd i s t r i b u t i o nc e n t e r 一1 5 2 1 2p r o c e s s e sa n da r e ac o n f i g u r a t i o ni nad i s t r i b u t i o nc e n t e r 15 2 2c o n c e p t sa n dt h e o r i e so f o r d e rp i c k i n g 1 6 2 2 1c o n c e p t so fo r d e rp i c k i n g 。1 6 2 2 2c l a s s i f i c a t i o na n dp o l i c i e so fo r d e rp i c k i n g 1 7 2 2 3c l a s s i f i c a t i o no fo r d e rp i c k i n gp r o b l e m 1 8 2 2 4o p t i m i z a t i o no b j e c t i v eo f o r d e rp i c k i n g 1 9 2 3o u t l i n eo fs t o r a g el o c a t i o na s s i g n m e n tp r o b l e m 。- - 2 1 2 3 1p o l i c i e so fs t o r a g el o c a t i o na s s i g n m e n t 2 1 2 3 2c h a r a c t e r i s t i c so fp r o d u c t 2 5 2 3 3m e t h o d sf o rc l a s s i f y i n gp r o d u c t s 2 7 2 3 4c h a r a c t e r i s t i c so fs t o r a g el o c a t i o na n do p e r a t i o nm o d e 。2 8 2 3 5l o c a t i o na s s i g n m e n tf o rr e t r i e v a la n do p e r a t i o ns e q u e n c e 。3 0 2 3 6r a c kt y p e s 31 2 4o u t l i n eo fa u t o m a t e ds o r t i n gs y s t e m 3 2 2 4 1t y p e so fd i s p e n s e r s 一3 2 山东大学博士学位论文 2 4 2c o m p l e xa u t o m a t e ds o r t i n gs y s t e m 3 3 2 4 3e i qa n a n l y s i s 3 4 2 5c o n c l u s i o n 3 6 c h a p t e r 3d e s i g na n ds i m u l a t i o no fd o s b a s e ds t o r a g ea s s i g n m e n tm e t h e d 3 7 3 1 o p m i z a t i o nm o d e lo fd o s - b a s e ds t o r a g ea s s i g n m e n t 3 7 3 2as t a t i cg r e e d ym e t h o df o rs t o r a g ea s s i g n m e n tb a s e do nd o s 39 3 3a d y n a m i cm e t h o df o rs t o r a g ea s s i g n m e n tb a s e do nd o s 4 1 3 3 1 d e s i g no ft h ed y n a m i cm e t h o d 4 2 3 3 2t h ek e ya r to ft h ed y n a m i cm e t h o d 4 4 3 4s i m u l a t i o n o fd o s b a s e d s t o r a g ea s s i g n m e n tm e t h o d 4 7 3 4 1d e s i g no fs i m u l a t i o np r o g r a m 4 8 3 4 2d e s i g no fw a r e h o u s el a y o u ta n ds i m u l a t i o np a r a m e t e r s 5 2 3 4 3s i m u l a t i o ns c h e m e s 5 9 3 4 4s i m u l a t i o nr e s u l t sa n da n a n l y s i s 6 6 3 5c o n c l u s i o n 7 0 c h a p t e r 4m o d e la n do p m i z a t i o no fs i n g l ec a s s 7 2 4 1m o d e lo fs i n g l ec a s s 7 2 4 1 1a s s u m p t i o n sa n ds y m b o l 7 2 4 1 2c o s ta n a n l y s i s 7 4 4 1 3 m o d e l i n g 7 6 4 2m o d e ls o l v i n g 7 7 4 3a p p l i c a t i o ne x a m p l e 7 9 4 3 1p r o b l e ms t a t e m e n t 7 9 4 3 2s o l u t i o na n da n a n l y s i s 8 0 4 4c o n c l u s i o n 8 2 c h a p t e r 5m o d e la n do p m i z a t i o no fm u l t ic a s s 8 4 5 1m o d e lo fs i n g l ec a s s 8 4 5 1 1 a s s u m p t i o n sa n ds y m b o l 8 4 5 1 2c o s ta n a n l y s i s 8 5 5 1 3 m o d e l i n g 8 7 山东大学博士学位论文 5 2m o d e ls o l v i n g 。8 8 5 2 1d e s i g no fb a c k t r a c k i n ga l g o r i t h m 8 8 5 2 2d e s i g no fs o l v i n gp r o g r a m 9 3 5 3a p p l i c a t i o ne x a m p l e 9 4 5 3 1p r o b l e ms t a t e m e n t 9 4 5 3 2s o l u t i o na n da n a n l y s i s 9 5 5 4c o n c l u s i o n 9 7 c h a p t e r 6c o n c l u s i o na n do u t l o o k 9 8 6 1c o n c l u s i o n ”9 8 6 2o u t l o o k 9 9 a p p e n d i x - - 。1 0 1 r e f e r e n c e s l1 3 a c k n o w l e d g e m e n t s 。- - 。1 2 1 p a p e r sa n dw o r kd u r i n gs t u d y i n gf o rd o c t o r sd e g r e e 。1 2 2 e n g l i s hp a p e ro n e 。1 2 3 e n g l i s hp a p e rt w o 。1 3 3 山东大学博士学位论文 摘要 我国社会物流总费用占国内生产总值的18 左右，远远高于美日等发 达国家的1 1 ，因此在我国降低物流成本具有巨大的效益和潜力。当前多 品种小批量的市场特征，使通过配送中心周转货物成为降低运输、库存、 分拣和配送成本的一项重要措施。在配送中心中，拣货成本占总成本的6 0 以上，拣货时间占作业总时间的3 5 左右。储位分配问题( s t o r a g el o c a t i o n a s s i g n m e n tp r o b l e m ，s l a p ) 是影响储存区拣货作业效率的一项重要因素， 复合式自动分拣系统( c o m p l e xa u t o m a t e ds o r t i n gs y s t e m ，c a s s ) 因具有 分拣速度快、准确率高、工人劳动强度低、性价比高等优点，使其在拣货 区的拣货作业中逐步得到广泛应用。因此将拣货系统中的储位分配问题和 复合式自动分拣系统的优化配置问题作为研究对象，对于提高配送中心作 业效率、服务水平、降低物流成本具有重要意义。 目前对储位分配问题的多数研究和应用都是以货物的存取频率 ( t u r n o v e rf r e q u e n c y ，t f ) 或单次取货存储空间指标( c u b e p e r o r d e r i n d e x ，c 0 1 ) 等平均存储特征作为储位分配的依据，没有考虑每个装载单 元的储存时间特征。基于装载单元储存时间( d u r a t i o no fs t a y ，d o s ) 的 储位分配方法以每个装载单元的储存时间为依据进行储位分配，在理论上 能够实现最优的储位分配方案，而现有方法要么为静态方法，很难应用到 生产实际中；要么为基于分类存储策略的方法，没有充分利用装载单元的 储存时间特性。本文对基于d o s 的储位分配优化模型和启发式方法进行研 究，以解决上述问题为目标提出基于d o s 的动态储位分配方法，为进一步 研究储位分配问题和配送中心改进拣货作业效率提供了新的方向和方法。 单c a s s 的综合性能依赖于分拣机的组合。当前采用e i q 分析和a b c 分类确定分拣机组合的方法，没有精确地把握分拣机组合和系统性能及成 本之间的关系。本文运用数学分析方法研究c a s s ，通过建立并求解分拣 机组合优化模型，为确定c a s s 的分拣机组合提供了定量方法。对于多 c a s s 联合作业的系统配置和任务调度问题，目前尚无有效的规划设计方 法。本文以对单c a s s 的研究为基础，建立了系统配置和任务调度优化模 山东大学博士学位论文 型，为规划和研究多c a s s 联合作业的分拣系统提供了新方法和基础。 本文的主要工作及创新点如下： ( 1 ) 对基于d o s 的储位分配最优化数学模型和静态贪婪式储位分配 方法进行分析和总结，结合储位分配问题的实际应用特点，给出基于d o s 的动态储位分配方法，并对具体的实现步骤和所涉及到的货物参数、储位 行走时间、实际d o s 列表和虚拟d o s 列表的确定及计算进行设计。首先 计算和入库装载单元在储存时间上有重叠的装载单元，得出参与储位分配 的装载单元序列，然后根据每个装载单元的存入和取出时间分配储位。该 方法符合实际应用中存取任务随时间推移逐步产生的特点，计算时间复杂 度较低，能够很容易地应用到实际生产中。 ( 2 ) 设计开发了基于d o s 的动态存储、就近存储、分类存储和定位 存储储位分配方法的仿真程序。程序为客户端服务器结构，在服务器端用 数据库保存仿真数据，用存储过程实现储位分配算法和任务的维护。在客 户端采用面向对象设计方法，实现仿真过程的计算和图形显示。仿真程序 的层次结构清晰，具有良好的可维护性和开放性。仿真动画直观、形象， 能够真实地表现仓库的作业过程。基于货物需求a b c 现象和经济订货批 量模型的仿真方案设计，使仿真方案具有很好的代表性。仿真结果表明基 于d o s 的动态储位分配方法和就近存储、分类存储及定位存储储位分配方 法相比，平均单程行走时间分别减少8 3 2 、9 2 9 和1 2 2 4 ，总体上平 均减少9 9 5 ，并且到货入库次序的改变对平均单程行走时间影响很小， 这充分验证了基于d o s 的动态储位分配方法的有效性。 ( 3 ) 针对单c a s s 的分拣机组合优化问题，分析了分拣用时、分拣成 本和分拣机组合的关系，以单位分拣成本最小化为目标，建立了分拣机组 合优化模型。并依据设备特点推导出固定成本、最小可变成本和最小分拣 用时的计算公式，从而简化了模型的求解。研究表明随着分拣系统中卧式 分拣机数量的增加，单位时间上的设备成本、场地成本呈线性增加，固定 配备人员成本不变，补货人员成本和分拣用时逐步减小，单位分拣成本呈 出先降后升的特点。该方法避免了e i q 分析和a b c 分类方法的主观性， 明确了分拣机数量和各项成本之间的关系，可有效地用于指导c a s s 分拣 i l 山东大学博士学位论文 机组合的选择。 ( 4 ) 针对多c a s s 联合作业的系统配置和任务调度问题，以单c a s s 的固定成本、最小补货成本和最小分拣用时的计算公式为基础，建立以分 拣成本最小化为目标的优化模型，设计了搜索最优解的回溯法。根据问题 特点，合理地设计了算法的分枝结构和定界函数，有效地缩小了解空间， 降低了计算复杂度，缩短了求解时间。并利用设计开发的回溯法求解程序 对应用实例进行了求解。实例结果表明分拣成本主要由固定成本决定，可 变成本的影响较小，固定成本主要取决于分拣系统的套数。因此，在分拣 系统规划中，可通过采用增加卧式分拣机数量，减少分拣系统套数的简化 做法降低分拣成本。 关键词：配送中心；拣货系统；订单分拣；储位分配；分拣系统；贪婪 算法；仿真；回溯法 i i i 山东大学博士学位论文 a bs t r a c t t h et o t a lc o s to fs o c i a ll o g i s t i c si nc h i n ai s a p p r o x i m a t e 18 o fg d p , s i g n i f i c a n t l yh i g h e rt h a nt h ec o s t so ft h eu n i t e ds t a t e s ，j a p a na n do t h e rd e v e l o p e d c o u n t r i e s ，w h i c ha r ee s t i m a t e dt ob ea b o u t1l s or e d u c i n gl o g i s t i c sc o s ti so fg r e a t b e n e f i ta n dp o t e n t i a l t h ec u r r e n tm a r k e tc h a r a c t e r i s t i c so fm u l t i - i t e m sa n d s m a l l q u a n t i t i e sm a k et u r n i n go v e rg o o d st h r o u 曲t h ed i s t r i b u t i o nc e n t e ra ni m p o r t a n t m e a s u r et or e d u c et h ec o s t so ft r a n s p o r t ，s t o r a g e ，s o r t i n ga n dd i s t r i b u t i o n i nt h e d i s t r i b u t i o nc e n t e r t h ep i c k i n gc o s t sa c c o u n tf o r6 0 o ft h et o t a lc o s tw h i l et h e p i c k i n gt i m eo c c u p i e s35 o f t h et o t a lo p e r a t i o nt i m e s t o r a g el o c a t i o na s s i g n m e n t p r o b l e m ( s l a p ) i sak e yf a c t o rt h a ta f f e c t st h ee f f i c i e n c yo fp i c k i n go p e r a t i o ni n r e s e r v ea r e aa n dc o m p l e xa u t o m a t e ds o r t i n gs y s t e m ( c a s s ) h a sb e e nw i d e l yu s e d f o rt h ep i c k i n go p e r a t i o ni np i c k i n ga r e a t h e r e f o r e ，r e s e a r c ho ns l a pa n dc a s si s o fg r e a ti m p o r t a n c ei ni n c r e a s i n gt h ew o r k i n ge f f i c i e n c y , i m p r o v i n gs e r v i c el e v e la n d r e d u c i n gl o g i s t i c sc o s t s e x i s t i n gs t o r a g el o c a t i o na s s i g n m e n tm e t h o d sf i r em a i n l yb a s e do na v e r a g e s t o r a g ef e a t u r e ss u c ha st u r n o v e rf r e q u e n c y ( t f ) o rc u b e p e r - o r d e ri n d e x ( c o i ) ，r e g a r d l e s so f t h es t o r a g et i m eo f e a c hl o a du n i t d u r a t i o no fs t a y ( d o s ) b a s e ds t o r a g el o c a t i o ns t r a t e g yc a l lc o m eu p 、析t l lo p t i m a ls o l u t i o n h o w e v e lt h e r ei s l i t t l er e s e a r c ho ni t t h i sp a p e rc o n c e n t r a t e so nm a t h e m a t i c a lm o d e la n dh e u r i s t i c a l g o r i t h mo fs t o r a g el o c a t i o na s s i g n m e n ta n dp r o v i d e sas o l i df o u n d a t i o nf o rf u t u r e s t u d yo ns t o r a g el o c a t i o na s s i g n m e n tp r o b l e ma n di m p r o v e m e n to fp i c k i n ge f f i c i e n c y t h eo v e r a l lp e r f o r m a n c eo fs i n g l ec a s sd e p e n d so nt h ec o m b i n a t i o no f d i s p e n s e r s c u r r e n tc o m b i n a t i o nm e t h o d o l o g y , w h i c hi sb a s e do ne i qa n a l y s i sa n d a b cc l a s s i f i c a t i o n , d o e sn o tt a k ei n t oa c c o u n ts y s t e mp e r f o r m a n c ea n dc o s t t h e r e f o r e ，an e wq u a n t i t a t i v em e t h o do fd e t e r m i n i n gt h eo p t i m a lc o m b i n a t i o no f d i s p e n s e r si sp r o p o s e di nt h i sp a p e r c o m b i n a t o r i a lo p t i m i z a t i o nm o d e li se s t a b l i s h e d a n dt h e ns o l v e d s i n c et h e r ei sn oe f f e c t i v ed e s i g na n dp l a n n i n gm e t h o df o rs y s t e m c o n f i g u r a t i o na n dt a s ks c h e d u l i n go fm u l t i c a s s - t a s kp r o b l e mc u r r e n t l y , t h i sp a p e r e s t a b l i s h e sac o r r e s p o n d i n go p t i m i z a t i o nm o d e lb a s e do nt hs t u d yo fs i n g l ec a s sf o r i v 山东大学博士学位论文 m u l t i - c a s sp i c k i n gs y s t e m a n dt h i sp r o v i d e sn e wm e t h o d 淞w e l la sf o u n d a t i o nf o r t h er e s e a r c ho nm u l t i c a s sp i c k i n gs y s t e m m a j o rw o r ka n di n n o v a t i o no f t h i sp a p e ra r ea sf o l l o w s ： ( 1 ) d o s - b a s e ds t o r a g el o c a t i o na s s i g n m e n to p t i m i z a t i o nm o d e la n ds t a t i c g r e e d ys t o r a g el o c a t i o na s s i g n m e n tm e t h o da r ea n a l y z e da n ds u m m a r i z e d a c c o r d i n g t ot h ep r a c t i c a la p p l i c a t i o n si ns t o r a g el o c a t i o na s s i g n m e n tp r o b l e m ，t h i sp a p e rc o m e s u p 、析t l lad o s b a s e dd y n a m i cs t o r a g el o c a t i o na s s i g n m e n tm e t h o da n dp r e s e n t s c o n c r e t ei m p l e m e n t a t i o ns t e p sa sw e l la sd e t e r m i n a t i o no ft h ei n v o l v e di t e m s p a r a m e t e r s ，s t o r a g et r a v e lt i m e ，a c t u a la n dv i r t u a ld o s l i s t i nt h ep r o p o s e dm e t h o d ， l o a du n i t st h a th a v eo v e r l a p si ns t o r a g et i m e 、 ，i t l li n b o u n dl o a du n i t sa l ef i r s t f o r e c a s t e da n dl o a du n i t ss e q u e n c e ，i n v o l v e di nt h es t o r a g ea s s i g n m e n t , i so b t a i n e d ； t h e ns t o r a g el o c a t i o ni sa l l o c a t e db a s e do nt h es t o r a g ea n dr e r i e v a lt i m eo fe a c hl o a d u n i t t h i sa p p r o a c hi sc o n s i s t e n t 、析t 1 1c h a r a c t e r i s t i c sg e n e r a t e d 、航t i la c c e s st a s ki nt h e p r a c t i c a l a p p l i c a t i o na n dc a nb ee a s i l ya p p l i e dt op r a c t i c eb e c a u s eo ft h el o w c o m p l e x i t yi nc a l c u l a t i n gt h et i m e ( 2 ) t ov e r i f yw h e t h e rt h ed o s - b a s e dd y n a m i cs t o r a g el o c a t i o na s s i g n m e n t m e t h o di se f f e c t i v e ，as i m u l a t i o np r o g r a mf o rt h es t o r a g el o c a t i o na s s i g n m e n tp r o b l e m i sd e v e l o p e db a s e do nd y n a m i cs t o r a g el o c a t i o na s s i g n m e n t , n e a r e s to p e nl o c a t i o n , c l a s s - b a s e da s s i g n m e n ta n dd e d i c a t e da s s i g n m e n t t h ep r o g r a mu s e sc l i e n t s e r v e ( c s ) a r c h i t e c t u r e t h es e r v e r - s i d eu s e sd a t a b a s et os a v et h es i m u l a t i o nd a t aa n d s e v e r a ls t o r ep r o c e d u r e st or e a l i z et h e s t o r a g ea s s i g n m e n ta l g o r i t h ma n dt a s k m a i n t e n a n c e ；t h ec l i e n t - s i d eu s e so b j e c t - o r i e n t e dd e s i g nm e t h o dt or e a l i z et h e s i m u l a t i o nc a l c u l a t i o na n dg r a p h i c a ld i s p l a y t h es i m u l a t i o np r o g r a m ，t h eh i e r a r c h i c a l s t r u c t u r eo fw h i c hi sv e r yc l e a r , h a sg o o dm a i n t a i n a b i l i t ya n do p e n n e s s s i m u l a t i o n a n i m a t i o n , w h i c hi si n t u i t i o n i s t i ca n dv i s u a l ，i sar e p r e s e n t a t i o no fr e a lw a r e h o u s e o p e r a t i o np r o c e s s d e s i g no ft h es i m u l a t i o np l a n , w h i c hi s b a s e do nt h ea b c p h e n o m e n o na n dt h ee c o n o m i co r d e rq u a n t i t ym o d e l ，m a k e st h es i m u l a t i o np r o g r a m