（光学工程专业论文）单元货格式立体仓库出入库优化调度研究.pdf

山东大学硕士学位论文 摘要 自动化立体仓库是一种集信息、储存、管理于一体的高技术密集型机电 一体化产品，涉及的领域很广自动化立体仓库的管理和控制，涉及诸多因 素和方面，其中执行货物出库和入库作业时，运输机具的调度即仓库的出入 库调度关系着仓库经济效益和社会效益的高低，因而一直是产学界关注和研 究的重点本文在前人研究的基础上对该问题展开了进一步的研究，主要工 作在于： 首次提出了与现代化立体仓库经济技术要求相协调的效率提高原则，改 进了传统研究一味追求效率最高而把效率、技术可行性及现有装备设施的合 理利用割裂开来的做法 在深入研究影响仓库作业效率主要因素的基础上，提出了为取而存，为 存而取，存取互为目标的合理化要求，进而提出了堆垛机动作最少的调度设 计原则，建立了出入库调度问题的数学模型，并根据调度原则提出了约束条 件。 考虑到仓库管理的复杂性和特殊性，纯粹地数学分析难免以偏概全而导 致实用性的丧失，本文在比较研究的基础上，采用有条件的最优点搜索法，该 法是解决动态规划问题较为成熟的方法作者在应用于本课题时进行了合理改进 编写了计算机程序模块，使设计的算法在计算机上得以实现，并结合社 会和企业大多数物流中转仓库的功能和类型，构造了物流仓库模型，对设计 的算法进行了模拟验证验证结果显示，设计的算法简单高效，实用性较强。 最后，总结了课题研究成果，指出了存在的不足和有待后续研究的问题 及方向根据作者的观察，本课题提出的观点、原则和方法还未见公开发表， 因此，该研究具有一定意义上的创新价值。 关键词：立体仓库；仓库管理；出入库调度；调度原则；调度算法 山东大学硕士学位论文 a b s t r a c t t h ea s r si sm e c h a n i c a l & e l e c t r i c a li n t e g r a t i o np r o d u c t i o nw i t hh i g l l t e c h n o l o g ya n dd e n s i t yw h i c hi n v o l v e si n f o r m a t i o n ，s t o r a g ea n dm a n a g e m e n t t h e a s 瓜sm a n a g e m e n ta n dc o n t r o li n v o l v em a n yf a c t o r sa n da s p e c t s ，a m o n gw h i c h ， b o t ht h ea s r se c o n o m i cp e r f o r m a n c ea n ds o c i a lp e r f o r m a n c ea r er e l a t e dt ot h e d i s p a t c ho fs t o r a g em a c h i n e sw h e nt h e y a r ei nt h eo p e r a t i o no fs t o r a g ea n d r e t r i e v a l s ot h ed i s p a t c ho fs t o r a g em a c h i n e sh a sb e e nt h ep o i n tp r o b l e mw h i c hi s r e s e a r c h e db ye n t e r p r i s e r sa n ds c h o l a r s o nt h eb a s eo ff o r m e rr e s e a r c hw h i c hp r e s c h o l a r sh a v ed o n e ，w em a n a g e dt oi m p r o v et h ea r i t h m e t i ci nac r e a t i v ew a y t h e m a i nw o r ki n c l u d e s ： t h ep r i n c i p l ea b o u tt h ei n c r e a s i n go fa s 瓜sw o r k i n ge f f i c i e n c yw h i c hi s a d a p t i v et oe c o n o m i ca n dt e c h n i c a ld e m a n dh a sb e e nb r o u g h tf o r w a r df o rt h ef i r s t t i m e ，t h et r a d i t i o n a lr e s e a r c ha i mi st op u r s u et h eh i g h e s te f f i c i e n c yo n l ya n d n e g l e c t st h ep o s s i b i l i t yo ft h ei m p l e m e n to fw o r k i n ge f f i c i e n c y ，t e c h n i q u ea n d r a t i o n a lu s i n go fm a c h i n e w eh a v ec h a n g e dt h et r a d i t i o n a lr e s e a r c hw a yi n t oa n e w o n e t h i sr e s e a r c hi se s t a b l i s h e do nt h eb a s eo ft h ea n a l y s i sa b o u tt h em o s t i m p o r t a n tf a c t o rt h a ti n f l u e n c e sw o r k i n ge f f i c i e n c yo f w a r e h o u s e w ep r o p o s et h e i d e aw h i c hs t o r a g ea n dr e t r i e v a la r ed e t e r m i n e db ye a c ho t h e r t h e nw ep u t f o r w a r dt h ed i s p a t c hp r i n c i p l et h a tn e e d st h el e a s tm o t i o n so ft h ec r a n e a n dt h e m a t hm o d e lh a sb e e nf o u n d e d ，b u tt h er e s t r i c t i o ni sa l s op u tf o r w a r da c c o r d i n gt o t h ed i s p a t c hp r i n c i p l e c o n s i d e r i n gt h ec o m p l e x i t ya n dp a r t i c u l a r i t yo fw a r e h o u s em a n a g e m e n t ，i ti s h a r df o ru st oa v o i dt h ep a r t i a lc o n c l u s i o ni fw ea n a l y z et h ep r o b l e mi np u r e m a t h e m a t i cw a y t h e r e f o r e ，w ea d o p tt h ec o n d i t i o n a ls e a r c hw a y t or e a l i z eo u r a r i t h m e t i c t h i sw a yi sam o r ep o p u l a ro n et od e a lw i t ht h ed y i l a m i cp l a n n i n g p r o b l e m s ，a n dr e a s o n a b l ei m p r o v e m e n t h a sb e e nc o m p l e t e db e f o r ei ti su s e di no u r r e s e a r c h i l lt h er e s e a r c h t h ec o m p u t e rp r o g r a mi sc o m p i l e d ，w h i c hm a k e st h ed e s i g n e d a r i t h m e t i ct r u ei nc o m p u t e r a n dt h ew a r e h o u s em o d e li sc o n s t r u c t e da c c o r d i n gt o i l 山东大学硕士学位论文 t h ef u n c t i o na n dt y p eo ft h emo s tso c i e t ya n dt h eb u s i n e s se n t e r p r i s e 。s1o g i s t i c s w a r e h o u s e w eh a v ec o m p l e t e dt h es i m u l a t i v et e s tt ov e i l f yt h ea r i t h m e t i c ，a n dt h e t e s tr e s u l t ss h o wt h a tt h ea r i t h m e t i ci sab r i e f , e f f i c i e n ta n dp r a c t i c a lo n e a tt h ee n do ft h ep a p e r t h er e s e a r c ha c h i e v e m e n ti sc o n c l u d e d ，a n db o t ho f t h ee x i s t e ds h o r t a g ea n dt h en e x tq u e s t i o na b o u tt h er e s e a r c ha l ep o i n t e do u t a c c o r d i n g t ot h ea u t h o r si n v e s t i g a t i o n , t h ev i e w s ，p r i n c i p l e sa n dw a y sp o i n t e do u t i nt h i sp a p e ra r e n tp u b l i s h e di np u b l i c t h e r e f o r e ，t os o m ed e g r e e ，t h er e s e a r c hi s p r o v i d e dw i t hv a l u eo ni n n o v a t i o no b v i o u s l y k e yw o r d s ：s t e r e o s c o p i cw a r e h o u s e ；w a r e h o u s ed i s p a t c h ；d i s p a t c hp r i n c i p l e ； d i s p a t c ha r i t h m e t i c i l l 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明。本声明的法律责任由本人 承担。 论文作者签名：童豆至萱耋e l 期论文作者签名：3 里l 丝三f 墨 期 o ij 移s ，仍 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保 留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅；本人授权山东大学可以将本学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或其他复制手段保存论文和汇编本 学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：鲢导师签名：俎日 期：圣堕丛鲨 山东大学硕士学位论文 1 1 课题提出的背景 第1 章绪论 近年来随着我国经济的快速发展和对外联系的日益紧密，物流研究受到 了产学界的高度重视。先进的生产制造模式、市场的多元化的需求，产品生 命周期的缩短以及供应链的快速反应、生产制造的全球化等特点使得物流活 动在时间和空间上更加广泛和频繁同时，物流服务业务也在蓬勃发展之中， 各地专业化的物流中心、物流企业大量诞生电子商务对传统物流业务产生 了巨大的冲击和影响，在此环境下，要求包括货物中转和配送在内的物流活 动反应速度越来越快，前置时间越来越短，周转次数越来越多【l l 。 自动化立体仓库是社会物流系统的重要组成部分，是一个复杂的综合自 动化系统【2 1 仓储作为物流的主要功能之一，它将实现货物在时间上的转移， 创造时间效益p l ，自动化立体仓库在此方面较传统仓库有着无可比拟的优势。 自动化立体仓库自诞生以来就受到了极大关注，其相关技术和管理的研究从 未停止过。在现代社会，随着生产方式和技术革命性的变革，自动化立体仓 库已经成长为支持企业和社会经济活动的重要因素，其经济和社会效益逐渐 被人接受，自动化立体仓库也成为了企业和社会资金及技术投向的重点【4 】 自动化立体仓库又称高层货架仓库、自动存取系统自动化立体仓库系 统( a s r s ，a u t o m a t e ds t o r a g ea n dr e t r i e v a ls y s t e m ) 是在不进行人工处理的 情况下自动存储和取出物料的系统这个概念覆盖了不同复杂程度及规格的 极为广泛多样的系统。系统a s r s 是指这样一个系统，它使用了几层、十几层 甚至几十层的高层货架，能在巷道内的任何货位存储和取出货物的搬运车以 及计算机控制的通信系统，系统还可以直接与其他生产系统相联，衔接产需【蜘 自动化立体仓库的出现和发展是第二次世界大战后生产和技术发展的结 果。上世纪5 0 年代初，美国出现了采用桥式堆垛起重机的仓库，5 0 年代末 6 0 年代初出现了司机操作的巷道式堆垛起重机1 9 6 3 年美国首先在仓库业务 中采用计算机控制，建立了第一座计算机控制的立体仓库在我国，上世纪 山东大学硕士学位论文 的7 0 年代开始研究采用巷道式堆垛机的立体仓库，1 9 7 4 年在郑州纺织机械 厂建成了第一个自动化立体仓库，1 9 8 0 年，由北京机械工业自动化研究所等 。单位研制建成的自动化立体仓库在北京汽车制造厂投产，至此我国已建成和 正在施工中的自动化立体仓库达到2 1 座【6 】截至目前，我国已建成的自动化 立体仓库3 0 0 多座，完全自动化的有3 0 多座我国的自动化仓库技术现已实 现了与其他信息决策系统的集成，正在做智能控制和模糊控制的研究工作【_ ” 随着现代工业生产的发展，敏捷制造系统( a g i l em a n u f a c t u r i n gs y s t e m ) 、 柔性制造系统( f l e x i b l em a n u f a c t u r i n gs y s t e m ) 、计算机集成制造系统( c i m s ， c o m p u t e ri n t e g r a t e dm a n u f a c t u r i n gs y s t e m ) 和工厂自动化( f a c t o r y a u t o m a t i o n ) 对自动化仓库提出了更高的要求，搬运和储存要求更可靠、更实时的信息， 生产和仓储中的物流要求必须伴随着并行的信息流。扫描、射频数据通信等 快速通信交换技术，准确定位技术、数据采集技术等在仓储机械上的应用越 来越普遍，物品的存取和发放更为快速、实时、可靠和准确。实现系统的柔 性化，采用灵活的传输设备和物流线路成为实现物流和仓储自动化的趋势。 自动化立体仓库调度问题是综合优化领域一个非常重要的方面，其研究 成果多应用在邮件、零备件等轻小型仓库的自动分拣系统。对于大型的物流 中转仓库，研究的重点多集中在装置和设备或者宏观物流系统的优化上，特别 是在国内，自动化仓库绝大多数是中低层小型分离式仓库，真正实现全部自动 化的立体仓库还极少，绝大多数是半自动化的水平，存储原则也未与自动化要 求相衔接，调度问题的研究相对滞后嘲本课题正是在此背景下提出来的。 1 2 课题研究的意义和价值 自动化立体仓库出入库调度问题是在车辆路线问题的基础上发展而来 的，其与车辆问题的主要区别在于；1 ) 距离与时间或费用不成定量的比例关 系，甚至不成确定的定性对应关系。在车辆路线问题中，时间( 或费用) 消耗 与距离有确定的比例关系，距离越远消耗越多；而在出入库调度问题中，由 于不同方向输送机具运行速度不同，因而使得这种关系不再一直成立。2 ) 出 入库调度问题的优化关注的不仅是效率，其牵涉的问题和因素比车辆路线问 题多。车辆路线的合理性衡量标准是效率是否最高，即或路线最短，或时间 最少，或费用最低；而出入库调度问题则还必须兼顾在库货物的均衡存放、 山东大学硕士学位论文 储存时间、货架受力、输送机具协调运行等多种因素3 ) 影响作业效率的主 要因素不同仓库作业效率最大的制约因素是堆垛机的运作效率，堆垛机在 执行存、取、运等任务时，为实现精确定位，特别是高层作业时的精确定位， 必须加大减速超调量，即加大减速距离，延长减速时间；同时为了确保作业 的安全性，存取作业后加速时间和距离相对也较长从实践的角度看，用于 定位的时间约占总运行时间的2 5 3 5 蜊m l ，与车辆路线问题相比较，该因 素对效率的影响显得尤其重要。车辆路线问题最早由d a n t z i g 9 】在上世纪5 0 年代末提出来，经过近5 0 年众多学者的研究，取得了丰硕成果，形成了相对 完整的理论体系，并取得了较为丰富的实践经验，特别是算法研究上，产生 了以时窗限制车辆路线问题( v r p t w ， v e h i c l er o u t i n gp r o b l e m sw i t ht i m e w i n d o w s ) 【、多车种车辆路线问题( f s v r p ，f l e e ts i z ea n dm i xv e h i c l e r o u t i n gp r o b l e m s ) 1 2 - 1 3 】、周期性车辆路线问题( p v r p ，p e r i o d i cv e h i c l e r o u t i n gp r o b l e m s ) 、车辆多次使用的车辆路线问题( v r p m ，v e h i c l er o u t i n g p r o b l e m sw i t hm u l t i p l eu s eo fv e h i c l e ) 1 4 - 1 5 1 等一大批针对不同路线情况、 作业情况及各种特殊要求的数学模型及算法相比之下，仓库出入库调度问 题的研究显得较为薄弱，尤其是在我国，部分的原因是由于已经建成的立体 仓库自动化水平还相对较低，机械故障率居高不下，出入库调度问题还未进 入迫切需要解决问题的日程，更主要的原因是仓库出入库调度问题与车辆路 线问题的区别很大，优化研究涉及多种原则并非提高效率这单一原则，理论 和实践上都处于相对不成熟时期，这就使得该问题的研究具备了一定程度的 创新意义和价值。 本研究采用了统筹效率，技术可行性、设备使用合理性和现阶段管理水 平等于一体的思想，针对不同作业情况优化的内容有不同方向的侧重，在单 一作业情况下，主要考虑货物储存状况的改善；在复合作业情况下则主要着 眼于效率的提高同时兼顾储存状况的改善，因此这就改变了传统研究一味追 求高效率，置其他因素于不顾的做法显然，在强调社会协调进步和平衡发 展的今天，该研究方法对于社会和企业物流所广泛涉及的设施合理布局、路 径合理设置、资源合理开发等都有一定的借鉴意义。 本课题研究的目的在于结合现实经济和技术背景，深入研究出入库调度 问题合理化的目标；限制条件极其松弛情况；发展简便实用的智能算法和个 山东大学硕士学位论文 案问题的一般化方法，等等。通过该课题的研究，可以向各类( 包括传统的 和现代的) 仓库的管理者们在制定在库货物的管理和控制措施时提供有益的 决策依据。 1 3 研究的内容和方法 1 3 1 研究内容 出入库调度问题的优化目标是：在兼顾仓库般经济技术原则的前提下， 使作业效率最高。由于该课题的提出有着明确的现实背景，其研究成果必须 具有理论上的先进性，实践上的可操作性和可检验性的特点，因此，本论文 的研究将集中在以下几个问题上，即本论文研究的主要内容是： ( 1 ) 单元货格式立体仓库概述及其出入库调度现阶段研究现状将重点 介绍与出入库调度相关的单元货格式立体仓库的基本知识和基本数学计算； 现阶段出入库调度问题研究的进展情况及主要成果；针对现阶段我国仓库企 业的管理和技术水平，明确本课题的研究方法该内容主要见于第2 章。 ( 2 ) 出入库调度问题及其数学建模介绍出入库调度问题的内容实质、 主要研究形态和制约条件；从现实研究能力和条件出发，对出入库问题进行 概念和任务界定；在对出入库调度问题的类型、特点、约束条件充分分析的 基础上明确具体的研究原则和目标；抽象出出入库调度问题的数学模型，见 第3 章。 ( 3 ) 模型求解的算法设计该内容是本论文研究的重点和核心以及创新 点的体现部分。主要包括：设计求解的基本思路、基本原则：介绍并选择基 本的实现算法；针对不同的作业方式实现其算法。算法主要由流程图形式表 现，见第4 章 ( 4 ) 模拟验证模拟验证主要用于检验优化算法的可行性和有效性，通 过构造仓库模型以及仓储现状，模拟演练优化的过程并对模拟结果进行分析， 得出适当结论。模拟验证见第5 章 山东大学硕士学位论文 1 3 2 研究方法 ( 1 ) 定性分析方法与定量分析方法相结合为使研究结果具有指导性和 实用性，结论应尽可能具体，分析过程尽可能精确。但考虑现实中仓库作业 的情况千差万别，纯粹定量分析难免以偏盖全，而完全定性分析则会空泛乏 力。所以，宣采用定性分析与定量分析相结合的方法进行研究 ( 2 ) 实证分析方法与规范分析方法相结合实践是推动理论发展的内在动 力，是检验理论的唯一标准。在国内外众多的仓库企业中，有许多成功组织 物流的经验和成熟做法，这些都是深入研究的宝贵资料。非常有必要对现有 的方法和理论进行实证分析，总结优点，找出不足，并采用规范分析的方法， 提炼出系统全面的理论和方法 ( 3 ) 实例分析方法与归纳总结方法相结合实例分析方法是通过对具体 案例的深入剖析，找出产生问题的原因和规律。这种方法在社会科学和管理 科学的研究中应用广泛本文将在现实基础上构造一案例，实际应用文中提 出的理论和方法，使本文的结论有较坚实的实践基础 山东大学硕士学位论文 第2 章单元货格立体库及问题研究现状 2 1 单元货格式立体仓库概述 单元货格式仓库是立体仓库的一种，其特点是货架沿仓库的宽度方向分 成若干排，每两排为一组，其间有一巷道供堆垛起重机作业，每排货架又分 为数列和数层，从而形成大量的货格用以储存货物( 如果将货架合并在一起， 使同一层、同一列的货格相互贯通，形成能依次存放多货物单元的通道，在 通道的一端装入货物单元，在通道的另一端取出货物单元，这就形成了贯通 式仓库) l i “ 2 1 1 设计原则 自动化立体仓库是土建、机械和电气等多专业的综合工程，这些专业技术 及其设备在立体仓库的设计过程中相互交叉，相互制约自动化仓库系统作 为机械电气及电器控制相结合的产品，其设计原则是根据实际经验和一般设 计要求提出的，属于一般指导的范畴，文献 1 8 ，1 1 5 - 1 1 7 给出了2 0 几项，与 本文关系密切的有： 1 ) 安全性原则。设计的系统应能保护人、库存货物和设备不受损伤，设 计中必须考虑防撞击、防坠落和防火灾等措施。 2 ) 高利用率原则即尽量减少设备的空闲时间和追求最少的设备故障时 间：有效利用存储空间 3 ) 容量富裕原则增加一个超负荷系统的容量是一件非常困难的事情， 因此必须考虑到发展的需要，设计成一个能满足现在和不久的将来需要的容 量。 4 ) 复合作业操作原则。即尽量把几种操作合并在一起进行，例如出库和 入库穿插进行等。 5 ) 简化流程原则。这是基于每种操作都需要一些点时间及费用，因此应 山东大学硕士学位论文 尽量减少操作 6 ) 物料和设备最短移动距离原则即以货物和设备最短的移动距离达到 目的地 7 ) 标准化原则。标准的设计、产品、设备和货物单元能给使用和管理带 来极大的方便，这也是国内外的发展趋势。 2 1 2 通过能力计算 一段时间内( 通常是1 个月) 进出库作业量通常用来仓库的通过能力衡 量，这是仓库宏观设计必须考虑的重要因素，其值与仓库总面积有关。立体 仓库的总面积由以下几个部分组成：货物的有效存放面积，入库验货场面积， 出库发货场面积，通道( 人行道、车行道等) 面积等立体仓库总面积可由 下式计算 彳：鱼( 2 1 ) 幻 式中4 立体仓库需总面积( m 2 ) 卜立体仓库面积利用率，即，存货面积与总面积之比 肌d 一立体仓库货物的库存量( t ) 口立体仓库单位面积上的库存量( t m 2 ) 其中，立体仓库的货物存储量可由下式计算 m o = 等r 协2 ， 式中卜立体仓库的月最大货物存取量( t ) 卜设计最大入库百分数 卜货物在库中的平均储存期( 天) ，该数据根据统计的各种货物 历年平均库存周期分析确定 3 卜每月以3 0 天计算 单位面积上的库存量计算公式为 q = r m ( 2 3 ) 式中胁货架的层数 r 每层货物堆存量( t ，i n 2 ) 山东大学硕士学位论文 仓库面积确定之后，立体仓库的通过能力即可计算 口：3 0 a q a( 2 6 ) ，6 式中口一仓库面积有效利用率 卜库存货物的月不平衡系数。 系数b 与货运量、货源、运输工具的衔接、水文气象及生产管理有关其 值应参照同类仓库正常情况下不少于连续3 年的统计资料来分析确定，一般 情况下，运量( 货物出入库量) 越大，不平衡系数越小【例 2 1 3 平面及立体布置 平面布置主要是解决仓库整体几何形状的问题，立体布置主要解决仓储及 运输设施的布局问题 关于平面布置，在上节中我们已经解决了总面积问题，面积确定后，还必 须解决仓库的长度和宽度这两个数据由需要存储的物品数量、存储空间、 货架的排数和列数以及高度决定。a s k i n 和s t a n d r i d g e l 2 0 】在1 9 9 3 年提出了求解 问题的方法，该方法由货架信息来确定仓库的长度和宽度假设要存储一个 货物单元，只要知道了通道参数，就可以获得仓库的长度和宽度。 如果我们分别用x ，y 表示货架的列和行，c 、d 表示通道系数( 通道长度 占货架长度的比例) 则仓库的长为“+ c ，宽度为咖+ 巩为了使货物平均单次 移动距离最小，须有 x ( c + 1 ) + v ( d + 1 ) 皿n 1 。一 ( 2 5 ) 满足x y z 行( 工，y ，z 是整数，z ：层数) 上述模型可以采用如下方法求解，即放松对工和y 的限制，同时令叼，= = h ( 最优化条件) 由此可以用y 表示x ，对y 求导并令其导数等于0 ，可求得y 。 利用这个值和方程x y z - - n ，可以得到其他变量的值 x y z 2 辟 z ：三 弦 因此，无约束的目标值为 山东大学硕士学位论文 苎堕坐+ 灭d + 1 ) 丝 2 ( 2 6 ) 式( 2 6 ) 对y 进行微分，令其结果等于0 ，可得； 二氅掣+ 盟：0 2 y z 2 与x y z = 以重组，可得： 弘臁 ( 2 - 7 ) 弘、丽 旺 y ；。峰尝 ( 2 - 8 ) y 2 、丽i 忆诺 式( 2 7 ) 和式( 2 8 ) 反映了通道系数对仓库的影响，不同的d 、c 会改 变x 和y 的值，即相应地改变仓库的长度和宽度，比如，当c = d 时，x = y ，即 仓库是方形的【2 ” 立体布置方案的确定取决于很多因素，包括：1 ) 货架结构：2 ) 堆垛机类 型；3 ) 待处理货物的数量和种类；4 ) 按货物种类和用途划分的货架段和组 台货架的专用化程度；5 ) 货物验收区、储存区、配套区和发货区的相互布局。 仓库里的布置方案，通常是指货架的布局方案，对于单元货格式自动化仓库， 布局有通道式、死巷道式( 也叫回流式) 、转移式和旁流式4 种布局形式，其 中以通道式和死巷道式为主 1 ) 通道式货架布局。通道式货架如图2 - 1 所示当收、发货区( 即入库 收货区目i 厨发货区 山东大学硕士学位论文 站台和出库站台) 在库房两端时这样布局最方便，同时可以保证货物连续流 动，而且还可将库内物流分开该种布局占地面积相对较大，输送机械使用 数量较多 2 ) 死巷道式货架布局死巷道式货架布局如图2 2 所示这种布局适合 于收、发货区位于存储区的一侧情况。这种布局仓库占地面积相对较小，输 送设备较少且使用率较高。但库内物流不易分开 收货区亘j 1 一货区 2 1 4 货架及货位管理 货架作为一种承重结构，必须具有足够的强度和稳定性，具有一定的精度 和在工作载荷下的有限的弹性变形，一般由钢材( g b 7 0 0 中的q 2 3 5 钢或 g b l 5 9 1 中的1 6 m 。) 或混凝土【2 2 】建成。 2 1 4 1 货架尺寸 货架尺寸的确定有静态法和动态法两种口引，通常是用动态法。所谓动态法 确定货架尺寸就是根据所需要的出入库频率和所选堆垛机的速度参数来确定 货架的总体尺寸，步骤如下 已知条件：库容量q ，出入库频率p d ，货架的高度日，货格尺寸和堆垛机 速度参( y 萱，矿童，g x ) 。 当q 和日确定后，最佳布置就是能满足出入库频率要求的最少的巷道数。 此时配备的堆垛机最少。具体的算法步骤为 1 ) 假定巷道数n b ( 先令其值为1 ) ，货架层数h ，则货架列数 n m 2 赢( 2 - 9 ) 山东大学硕士学位论文 2 ) 根据层数和列数肌以及堆垛机的速度参数，计算每台堆垛机的平 均作业周期乃或。 3 ) 计算整个仓库的出入库能力 p ：3 6 0 ，0 ( 2 1 0 ) i 4 ) 比较p 和p d 。如果p 小于凡，说明设计货架达不到出入库频率要求， 再计算胁- 2 的情况，重复以上四步计算，直到p 大于或等于p 口为止，此时 的巷道数为最佳巷道数 2 1 4 2 货架最佳高度 货架高度是仓库的主要参数，其影响因素有：借以确定储存量( 容量) 等 级的货物流量、货物周转率( 储存期) 、订货发送时的配套方式( 此方式取决于 每一批货物的品种数目和单位数量) 从综合费用的角度看，德国专家认为， 最佳高度在2 0 - - - 2 1 m 范围内，或在1 5 2 0 m 之间【2 5 1 1 2 6 1 。据美国克拉克( c l a r c ) 公司的数据，货架高度在2 0 m 左右费用最低最新研究成果表明，折算费用 随货架高度h 的变化如表2 1 表2 1 货架高度与折算费用对应关系 lh ( m )68 4l o 81 2 6 1 4 4 1 6 2 i 折算费用( ) l o o9 69 27 36 45 8 实践证实最佳高度日与容量有一定的关系：当容量为1 0 0 0 4 0 0 0 t ，高度 为1 2 6 m ：当容量为6 0 0 0 t 或以上时，高度为1 6 2 m ，这主要因为高度再继续 增加会明显降低堆垛机作业效率需要指出的是，随着仓储机械技术的进步， 专家一致认为，一台堆垛机运行的巷道最佳长度应在8 0 - - 1 2 0 m 之间，一般 要求保持h l = k 圪，推荐采用货架高和货架长的比值 日l = l “一1 6( 2 1 1 ) 2 1 4 3 货位管理 货位管理又称货位规划或货位分配是“将货物合理纳入仓库设施，以 实现物料调度最优化和提高空间利用率的目标”传统仓库的物料搬运作业 中，装卸、储运和分拣作业占总作业时间的4 0 左右，其余6 0 的作业时间 是人员或搬运设备的走行消耗【2 7 1 货位管理的主要目标就是：处理任意调度 货物时，最大限度地缩短行走时间。 山东大学硕士学位论文 对于自动化立体仓库，货位管理主要有两层含义，一是为待入库的货物分 配最佳货位，即入库货位分配；二是选择待出库货物的货位，即出库货位的 确定但与传统仓库管理中的货位管理不同的是，自动化立体仓库在货位分 配原则时考虑的因素则要比传统仓库多得多其中，主要的原则有； 1 ) 货架受力情况良好。包括：下重上轻的原则，即重的货物存放在低层 货位，轻的货物存放在高层货位；分散存放原则，即物料分散存放在仓库的 不同位置，避免因集中存放造成货格受力不均匀。 2 ) 先入先出，加快周转。即同种货物出库时，先入库者，先提取出库， 避免货物因长期积压造成锈蚀、变质、变形及其他损坏 3 ) 分巷道储存即同种货物分散在不同巷道，这样可以防止因某巷道发 生堵塞而影响该种货物的出库。 对于单元货格式立体库，提高存取效率的货位分配主要有以下两种方法： 1 ) 物料按出入库频度分类，分区存放通过把出入库频繁的物料存放在 便于出库的区域，可以缩短堆垛机执行实时性要求高的出库作业的行走路线， 从而缩短作业完成的时间 2 ) 联合货位编号进行货位分区一般先要进行货位编号货位编号应该 能够反映出货位与出库台的距离，总的衡量，随着货位序号的上升，货位离 出库台的距离增加图2 3 为单排货架的货位编号的示意图。当仓库有多个货 架时，为平衡各巷道各排货架的物料存储及堆垛机的运行，通常采用联合货 位编号的方法，图2 - 4 为多排货架的货位编号示意图 图2 - 3 单排货架货位编号示意图 图2 4 多捧货架货位编号示意图 山东大学硕士学位论文 2 2 出入库调度问题的研究现状 国外自动化立体仓库出入库调度问题的研究主要集中在宏观物流系统的 优化上威果主要是不同存储原则下的货位布置模型。有代表的存储原则包括： 1 ) 随机存储原则，即将入库的货物单元放在任何可存的货位上在实践 中，货物往往放在最近的货位上f r a n c i c 、m c g i n n i s ，w h i t e ( 1 9 9 2 ) 和t o m p k i n s ( 1 9 9 6 ) 【2 s 1 等经过长期试验，发现操作人员总是倾向于优先使用最近的空间， 确立了该原则。 2 ) 分类存储原则。货物由于分类不同，会存放到预先指定的货位。显然， 在相同的存储( s r ，s t o r a g e r e t r i e v a l ) 数量和频率下，随机存储原则占用的 空间更小，这是因为分类存储原则要求必须给每种货物不少于最大存储量的 空间 3 ) c o i 原则，该原则最早由h e s k e t t ( 1 9 6 4 ) 【2 9 1 提出来的某种货物的c o l 是该种货物的存取( s 瓜) 数量和其存储空间的比值。按照这个理论，仓库管 理者应将各种货物的c o i 算出，然后按递减顺序排列。最后，管理者按照排 列顺序安排货位，c o i 值越高的货物，其货伊越靠近仓库出入口( i ，o ，i n o u t ) 这样，c o l 原则将单次s r 量大、存储空间要求少的货物放在i o 口附近的货 位上 4 ) 分级存储原则。这个原则源自p a r e t o 3 0 】的观察，p a r e t o 发现一个国家 或者说整个世界上一小部分人占有大量财富，而大多数人只占有很少部分的 财富，这种情况叫做p a r e t o 效应( l 行e d o p a r e t o 是1 9 世纪著名经济学家) 。 p a r e t o 经过长期观察，在一个仓库中，8 0 的s 瓜活动是关于2 0 的货物的， 1 5 的s 瓜活动是关于3 0 的货物的，剩余的5 的s r 活动和5 0 的货物有 关研究人员据此将货物分级为a 、b 和c 级，上述三种货物分别为a 、b 、 c 类。显然，为了缩短作业时间，a 类货物应放在离i o 口最近的地方，b 类 其次，以此类推 在上述原则下，形成了仓库布置( 含货位分配) 模型，以下这些模型只 是定性地描述了货物单元货位的确定方案 ( 1 ) 分类原则布置模型假设：a 仓库有户个i o 口，可供 个货物单元 存取。仓库可以容纳1 7 个货物单元对于j 个货物单元。需要s 个货位。最 山东大学硕士学位论文 理想的情况是 s f = ( 2 - 1 2 ) i - l 当等式左边稍小于右侧时，可假设第n 1 个货物单元占据剩余的 ( 月一s ，) 个货位 i l 设： 再广货物单元f 从编号为k 的i i o 口进出的频率 c ，f 一从k 号i o 口将一个货物单元移动单位距离的时间( 费用) 如一第，号货位到k 号f o 1 ：3 的距离 。厂一布尔变量，用来表示货物单元f 是否在货位_ ，上 这样就可以建立仓储货位分配模型，来降低总体作业时间( 费用) 假设每个f o 口与不同货物单元组合的作业时间( 费用) 不同，则模型为： 满足 m i n l - lj - i且f s 卜 i u 工盯= s ， j - i ( 2 1 3 ) ( 2 1 4 ) x u = 1 ( 2 - 1 5 ) 石u2 1 或0 i = l ，2 ，m ；j = 1 ，2 ，n ( 2 - 1 6 ) 艺c 业厶白 令： 坳2 午 q 。1 7 目标函数则可写成： r a i n 峋 ( 2 1 8 ) 扣lj - l 该模型可以通过运输算法求解 ( 2 ) 特定条件下的0 0 i 原则布置模型此类模型非常复杂，有必要为其 山东大学硕士学位论文 限定特殊条件：每种货物以同样的比例进出i o 口，而且移动货物的单位距离 的时间( 费用) 与i o 口无关。定义r 为通过第k 个i o 口进出仓库的比例， k = - i ，2 ，p ( 对任何一种货物都适合，因为所有的货物都以相同的比例使 用i o 口) 这样由于该模型中的附加约束。因此没有必要使用办及e l k ，将丘和c 矗 分别以z 和c 。代替，模型( 2 1 3 ) 变为如下形式： m i n ，l j 主c jf jp 。d “ 丝1 广卜s ，l ” ( 2 1 9 ) 同样要求满足( 2 1 4 ) 一( 2 1 6 ) 式 令： m = 见如 目标函数则可写为： 量季。等wiraine卜 沼2 0 ) l 孚h ( 2 - ，- l ，- ll， j 由( 2 2 0 ) 和约束( 2 z 4 ) 一( 2 1 6 ) 构成的布置模型比前面的模型要简 单，而且不需要采取运输算法求解 求解的方法是对每个货物单元f 的成本项( 时间、费用c , f , s ) 进行排序， 然后使成本项最大的货物单元存储在距离i o 口最近的货位上 ( 3 ) 随机存储原则布置模型入库的货物单元被随机存储在一个货位， 该货位要求为空且是有效的每个空的货位在被选择为待存货位时机会都是 相同的假设需要打个存储货位，求这一个货位的布置以使每个货位和p 个 i o 口之间的总期望距离最小显然，每个i o 口到每个货位的距离之和为； 杰白 k - i ( 2 2 1 ) 在不减少这些距离的情况下安排存储货位，选择一个最近的存储货位 理论上，以上模型一定程度上适合与出入库的货位管理，但主要还是适 合于仓库宏观物流系统的优化。 近些年来，随着车辆路线问题研究方法的成熟和发展，出入库调度问题 山东大学硕士学位论文 的研究出现了新的理论和方法，其中基因算法的发展较为突出 基因算法又叫遗传算法，最早由b a g l e yj d 在1 9 6 7 年提出，而其理论和 方法的系统性研究是在1 9 7 5 年由m i c h i g a n 大学的j h h o l l a n d 3 u 所实行该 方法是从进化论得到灵感和启迪，借鉴了自然选择和自然进化的原理。其机 理是：把问题的解构成满足约束条件的“染色体”，即通过编码把解适当地表 示成“串”随机产生初始群体，即给出一群“串”，作为假设解。然后把这 些假设解置于问题的“环境”中，并按适者生存的原则，从中选出较适应环 境的染色体进行复制，再通过交叉、变异产生更适应环境的“新一代”染色 体群。这样，一代一代地进化，最终收敛到最适应环境的染色体上，它就是 问题的最优解标准步骤： 1 ) 初始化随机选择一个群体，即选择一个串的集合b i ( i - - 1 ，2 ，n ) 。 这个初始的群体就是假设解的集合( 一般n = 3 0 - - 1 6 0 ) 2 ) 选择根据适者生存的原则选择下一代的主体在选择时，以适应度 为选择原则，适应度准则体现了适者生存，不适应者淘汰的自然法则。 给出目标函数f ，则f ( b ) 称为个体b ，的适应度 p 雠中龟) = 掣甩 ( 2 2 2 ) 厂( 6 ) j - l 表示选中b 。作为下代个体的次数显然，从( 2 2 2 ) 可知，适应度较高的 个体繁殖的下一代数目较多。这样就产生了对环境适应能力更强的后代，即 向最优解接近了一步 3 ) 交叉对于选中用于繁殖下一代的个体，随机地选择两个个体的相同 位置，按交叉概率b ( 一般取值0 2 5 - - 0 7 5 ) 在选中位置实行交换。这个过程 反映了随机信息交换，目的在于产生新的基因组合，亦即产生新的个体，交 叉时可实行单点交叉或多点交叉 4 ) 变异根据生物遗传中基因变