（计算机软件与理论专业论文）基于遗传算法的自动化立体仓库的货位优化研究.pdf

中文摘要 传统的仓库作业管理由于沿袭了多年的习惯，依靠经验来放置物品，通常将货 物放置在可能到达的最近货位，通常并不考虑货物的动态变化以及客户需求，故造 成流程速度慢、仓库利用率低以及空间利用不足等问题。为此，货位优化应用而生， 货位优化管理是针对每一类货品的特性，为它确定一个恰当的存储方式，依据该存 储方式为货物分配存储空间。从而使得仓库作业能利用同等的劳动力或成本去做更 多的工作，提供更快捷、更周到的服务。 本论文在此背景的基础上，以蒙牛第六期自动化立体仓库为研究对象，对其货 品的存储货位进行优化研究。 首先，在分析物流管理的基础上提出货位优化的概念。结合货位优化的存储策略 与货位分配的原则，建立了一种以提高货物周转效率为目标，同时又能满足货架稳 定性要求的货位优化模型；其次，通过对现有的货位优化处理方法进行分析，提出 采用多目标遗传算法来解决该优化问题，并尝试应用妥协方法对优化模型进行求解。 再次，应用m a t l a b 遗传算法工具箱对优化模型进行仿真试验，并针对试验结果进行 分析讨论；最后，在文章结尾对课题的研究工作进行总结，并对后期的研究提出目 标和方向。 关键词：自动化立体仓库；货位优化；多目标遗传算法：妥协方法；m a t l a b 遗传算 法工具箱 a b s t r a c t t h et r a d i t i o n a lw a r e h o u s em a n a g e m e n tu s u a l l yp l a c e sg o o d s a tt h e n e a r e s ta v a i l a b l ea r e aw h e nt h eg o o d sa r r i v e i t c o m e sf r o mt h ep a s t e x p e r i e n c eo n l yc o n s i d e rl e s sd y n a m i cc h a n g e si nc o m m o d i t yd e m a n da n d c h a n g e s i nc u s t o m e rd e m a n dp a t t e m s t r a d i t i o n a lg o o d sl a y o u t c a u s e s c o m p l e xi n e f f i c i e n tp r o c e s s e sa n dl a c ko fs p a c eu t i l i z a t i o n t h e r e f o r e ，t h e s l o t t i n go p t i m i z a t i o nh a sb e e np r o d u c e d t h e s l o t t i n go p t i m i z a t i o nm a n a g e m e n t d e t e r m i n e sa na p p r o p r i a t e l o c a t i o nr o u t i n gb yg o o d sa t t r i b u t e b a s e do i ll o c a t i o nr o u t i n gs t r a t e g y , d e p o t m a n a g e m e n to f f e r sb e t t e rs w i f t e ra n dc o n s i d e r a t es e r v i c et h o u g ht h es a m e l a b o ro rc o s t b a s e do nt h er e s e a r c ha b o u tt h em e n g n i ua s r s ，t h i st h e s i sc a r r i e s o u tam e t h o dt op u tt h eg o o d si nt h ea s r si n t ot h eo p t i m a ls l o t s f i r s to fa 1 1 o nt h eb a s i so fa n a l y z i n gl o g i s t i c sm a n a g e m e n t ，t h i st h e s i s p u t s f o r w a r dt h es l o t t i n go p t i m i z a t i o nc o n c e p t c o m b i n i n gt h es t o r a g e s t r a t e g yw i t ht h es l o t t i n ga s s i g np r i n c i p l e ，c o n f i g u r i n ga s l o t t i n go p t i m i z a t i o n m o d e lt oe n h a n c et h ew a r e h o u s eg o o d st u r n o v e rr a t ea n di m p r o v et h ew h o l e s t a b i l i t y s e c o n d l y ，e s t a b l i s hm u l t i o b j e c t i v eg e n e t i ca l g o r i t h mt or e a l i z e o p t i m i z a t i o nb ya n a l y z i n gt h ee x i s t i n gs l o t t i n go p t i m i z a t i o nm e t h o d s i tt r i e s t om a k eu s eo fc o m p r o m i s ea p p r o a c ht os o l v et h eo p t i m i z a t i o nm o d e l f i n a l l y , r e s e a r c ht h ea r t i f i c i a lr e s u l t so fo p t i m i z i n gm o d e lb ym a t l a bg e n e t i c a l g o r i t h mt o o l b o xa n da n a l y z et h es i m u l a t i o nr e s u l t s k e y w o r d s ： m u l t i o b je c t i v e g a t 0 0 l s a u t o m a t e dw a r e h o u s e ；t h es l o t t i n go p t i m i z a t i o n ； g e n e t i ca l g o r i t h m ；c o m p r o m i s e a p p r o a c h ；m a t l a b 声明尸明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的 法律责任由本人承担。 作者签名：壅垄缒丞日期：丝竺2 靠= 目竺目 关于学位论文使用权的说明 本人完全了解太原科技大学有关保管、使用学位论文的规定，其 中包括：学校有权保管、并向有关部门送交学位论文的原件、复印 件与电子版；学校可以采用影印、缩印或其它复制手段复制并保存 学位论文；学校可允许学位论文被查阅或借阅；学校可以学术交 流为目的，复制赠送和交换学位论文；学校可以公布学位论文的全 部或部分内容( 保密学位论文在解密后遵守此规定) 。 作者签名：轻盈云 日期：垄兰巨姐垒超 导师签名：j 兹翌复垃，一日期：- 坐雩j 上上l 第一章绪论 第一章绪论 1 1 课题研究背景 随着计算机自动识别技术的发展，仓库管理也在逐渐完成信息化。更多传统的 手工管理方式被自动化的管理方式所取代。自动化立体仓库是现代物流技术、仓储 技术、自动化技术与计算机技术高度集成化的产物。它具有存储容量大、占地面积 小、作业快速准确、节约人力等优点，已成为工厂物流、计算机集成制造系统和商 业流通领域的重要组成部分。 对于自动化立体仓库来说，固定货架是最为广泛的存储设备。同一货架的不同 货位上的物品质量可能悬殊很大，为使货架保持稳定，需要尽可能使质量较大的物 品处于货架的底层，即货架的重心应尽可能低。同时，不同货位物品的存取频率也 有较大差别，而对不同货位上的物品进行存取所花费的时间是不同的，因而货位需 要动态发生变化。当货架上货物的质量和存取频率发生较大变化时，需要对货位重 新进行分配，以保证货架稳定和提高存取效率。由此可见，自动化立体仓库中货位 的分配及优化就成为一个值得研究的课题。更优化的货位分配算法将是仓库管理系 统的核心竞争力，它可以降低仓库中货物搬运的成本、提高出入库的效率、为仓库 的管理带来方便，故货位优化研究可以有效的提高仓库的利用率。 ， 本课题以内蒙古蒙牛乳液集团的立体仓库为研究对象，对其仓库内的货位优化 进行研究，提出适合蒙牛集团的货位优化算法，增强其物流环节的核心竞争力，并 为蒙牛集团的货位优化提出可行性建议。 1 2 自动化立体仓库简介 自动化立体仓库是机械、电气与信息技术相结合的产品。它主要由货物储存系 统、货物存取和传送系统、控制和管理等三大系统组成，还有与之配套的供电系统、 空调系统、消防报警系统、称重系统、信息系统等。本节将对自动化立体仓库的构 成与分类进行简单介绍。 1 2 1 自动化立体仓库的构成 一个比较完善的自动化立体仓库主要由货物储存系统、货物存取和传送系统、 控制和管理等三大系统组成：( 1 ) 货物储存系统，用于货物存放和周转的货物储存 的系统，如高层货架及托盘、货箱；( 2 ) 货物存取和传送系统，用于出入库作业的 货物存取和传送，如堆垛机、输送带、装卸机；( 3 ) 入出库分配系统，进行货物的 出入库分配，如辊式、链式输送机、分配车、升降机等。除此之外，一个自动化立 基于遗传算法的自动化立体仓库的货位优化研究 体仓库需有与之配套的辅助系统：( 1 ) 自控系统，由计算机控制的入出库设备、分 配系统以及各种检测、保险机构的全部电控装置组成；( 2 ) 计算机管理系统，用来 管理仓库的信息管理、数据分析、合理管理货位、设备运行、库存情况等；( 3 ) 入 出库频率不高的立体仓库几个巷道可共用一台堆垛机，此时应配备堆垛机转轨设备， 如转轨车。 1 2 2 自动化立体仓库的分类 自动化立体仓库是一个复杂的综合自动化系统，作为一种特定的仓库形式，一 般有以下几种分类形式。 1 按建筑形式分类 按建筑形式可以分为整体式和分离式。整体式指货架除了储存货物外，还可以 作为建筑物的支撑结构，构成建筑物的一个部分，即库房货架形成一体化结构。分 离式是指储存货物的货架独立存在，建在建筑物内部，它可以将现有的建筑物改造 为自动化仓库，也可以将货架拆除，使建筑物用于其他目的。 2 按货物存取形式分类 按货物存取形式分为单元货架式、拣选货架式。单元货架式是一种常见的结构。 货物放在标准容器中或托盘上存储，出入库都以整个单元进行。所用的物料搬运机 械式适用于整个单元搬运的，例如带伸缩货叉的巷道堆垛机、高架叉车等。 3 按货架构造形式分类 按货架构造形式分类可分为单元货格式、贯通式、阁楼式、屏挂式、移动式、 旋转式、驶入式和悬臂式货架仓库。单元货格式仓库是使用最广、适用性较强的一 种仓库形式。其特点是货架沿仓库的宽度方向分成若干排，每两排货架为一组，期 间有一条巷道供堆垛机或其他起重机作业，每排货架沿着仓库纵长方向分为数列， 沿垂直方向又分为若干层，从而形成大量货格，用以存储货物。 4 按在生产和流通中的作用分类 按在生产和流通中的作用可以分为生产性仓库和流通性仓库。生产性仓库是指 工厂内部为了协调工序和工序、车间和车间、外购件和自制件间物流的不平衡而建 立的仓库，它能保证各生产工序间进行有节奏的生产；流通性仓库是一种服务性仓 库，它是企业为了调节生产厂家和用户间的供需平衡而建立的仓库。 本文研究的蒙牛立体仓库采用的是单元货格式仓库。蒙牛乳业集团成立于1 9 9 9 年，总部设在内蒙古呼和浩特市和林格尔县盛乐经济园区，企业总资产达7 6 亿，乳 制品年生产能力5 0 0 万吨。随着生产规模的不断扩大，自2 0 0 2 年起，蒙牛乳业集团 2 第一章绪论 开始采用自动化立体仓库，提高仓储容量与物流管理水平。在全国范围内共拥有2 0 多座立体仓库，其中，2 0 0 7 年投入使用的六期工厂的物流系统项目，以规模巨大和 高度自动化受到业界的广泛关注。 2 0 0 6 年，蒙牛乳业集团做出了在总部投资建设六期生产项目的决定，并提出了 “八化”即国际化、智能化、规模化、立体化、展示化、个性化、差异化、系统化 的要求，准备采用先进的设计理念和技术设备，建成国内规模最大，科技含量最高， 集生产、科研、培训于一体的大型现代化液体奶生产厂。蒙牛六期的建成标志着我 国乳制品加工业技术水平迈进了国际先进行列，缩小了中国乳业与世界的差距。 与蒙牛六期项目相配套的物流系统，继承了自动仓库系统a s r s 、空中悬挂输送 系统、码垛机器人、环形穿梭车、直线穿梭车、自动导引运输车a g v 、自动整形机、 自动薄膜缠绕机、液压升降台、货架穿梭板、连续提升机以及多种类型的输送机等 自动化物流设备，是迄今国内乳业自动化程度最高、最先进的物流系统。 1 3 国内外货位优化的研究现状 第二次世界大战以后随着生产和技术水平的发展，普通的仓储管理模式已经不 能适应发展的要求。由此自动化立体仓库出现，并迅速的发展起来。立体仓库的雏 形出现在2 0 世纪5 0 年代初，美国出现了采用桥式堆垛起重机的仓库，这时的自动 化立体仓库严格的来说只能算是立体仓库，并没有实现自动化管理。到5 0 年代末6 0 年代初出现了由司机操作的巷道式堆垛机，1 9 6 3 年美国首先在仓库业务中采用计算 机控制，建立了第一座计算机控制的立体仓库。而后1 9 6 5 年日本也从欧美引入自动 化立体仓库。随后在英国、法国也相继出现了类似的立体仓库。自动化立体仓库真 正成为高效率的自动化设备，还是在7 0 年代以后的事情。 8 0 年代中期，我国先后在无锡、湖北和大连等地出现多座利用计算机控制巷道 堆垛机的自动化仓库。之后自动化立体仓库在我国迅速发展起来。据不完全统计， 截止到2 0 0 6 年底，全国自动化立体库的保有量已超过5 0 0 座。2 0 0 6 年建设的自动化 立体库在8 0 座以上，主要集中在机械制造、汽车、烟草、食品加工、服装生产、医 药生产及流通等行业。 近年来，无论是国内还是国外，自动化立体仓库的货位分配优化都是一个热点。 新加坡南洋技术大学的s g l e e ，r d e s o u z a ，e k o n g 等通过导引小车服务的自动化 立体仓库( a s r s ) 的一个巷道的模拟仿真，意大利的n a d i ab a l d a s s i n o ，c l a u d i o b e r n u z z i 研究了钢存储托盘货架的分析和变形，c l a u d i ob e r n u z z i 和c a r l o 3 基于遗传算法的自动化立体仓库的货位优化研究 a c a s t i g l i o n i 研究了钢结构托盘货架横梁和立柱连结的周期变形的实验分析。内 盖夫的n a v ap l i s k i n 和m o s h ee b e n - c h a i m e 研究了复杂机械自动化系统的操作管 理。国内山东大学的宁春林研究了基于蚁群算法立体仓库拣选路径的优化问题，窦 金凤对立体仓库物流管理优化模型及其物理实现进行了探讨，江汉石油学院的李诗 珍从出入库周期角度研究了货位分区管理，上海理工大学王恒山介绍了一种基于适 时控制的立体仓库出入库算法。此外西南交通大学的周奇才和上海同济大学的赵炯 也对自动化立体仓库存取方式进行了研究，他们以状态图的方法详细分析了现有的 各种存取操作方式，通过合理的扩展，取得了包罗所有情况的出入库存取操作的货 位状态转移图，从而得出具有实用价值的8 种出入库操作方式。山东工业大学自动 化系的常发亮，刘长有研究了输送系统调度的优化仿真和自动化立体仓库拣选出库 总体调度策略的优化，也提出了立体仓库存储分配最优化目标模型，给出货位管理 的优化原则和具体优化算法，并提供了一种便于仓库管理的数据结构模型。2 0 0 7 年 山东师范大学的陈东、刘希玉采用遗传算法对自动化仓储管理系统中的货位分配进 行了优化，首先建立了货位分配算法的数学模型，然后提出了采用遗传算法解决这 个模型的优化问题，并最终通过应用验证了算法的适应性。大连理工大学的李梅娟 提出了采用p a r e t o 遗传算法解决多目标组合优化问题，通过仿真实验验证了将 p a r e t o 遗传算法应用在实际货位配置优化问题中，取得了较好的结果。 1 4 课题研究意义 在物流中心的作业中，讲求的是省时、有效率。而人员在存取搬运商品时，在 照顾员工的条件下，讲求的是省力。因此要达成存取效率高、省时、省力，则要求 货品定位方面要合理化，从而提高物流中心作业效率和空间利用率，增强从事物流 业务的企业的竞争力。 1 5 本章小结 本章简单介绍了货位优化的概念以及进行货位优化的必要性，并分析了货位优 化的研究现状，进而根据蒙牛实例提出了本论文的主要研究内容、研究目的和意义。 4 第n 二童自动化立体仓库货位优化管理 第二章自动化立体仓库货位优化管理 为了适应当今客户快速和频繁的配送要求，物流中心的拣选作业必须比以前更 快而且更有效率，理想的拣选作业的解决方案，是将恰当的设备和种拣选方法相 结合。但是，为了更加有效地拣选，我们同时也一定要把存放单元放入正确的地方 即货位优化。将货品位置最优化，可以减少货物搬运的成本，降低货物在存储 过程及搬运过程中的损耗，从而降低物流业务本身的成本，提高收益。随着现代物 流技术的发展，一种与所谓的“仓库关键业绩指标( w a r e h o u s ek e yp e r f o r m a n c e i n d i c a t o r ) ，即生产率、运送精度、库存周转、入库时间、订单履行时间和存储密度 紧密关联的货位优化( s l o t t i n go p t i m i z a t i o n ) 已经被提出。货位优化追求不同设备和 货架类型特征、货品分组、货位规划、人工成本等因素以实现最佳的货位布局，能 有效掌握商品变化，将成本节约最大化。货位优化管理为正在营运的仓库挖掘效率 和成本，并为一个建设中的配送中心或仓库提供营运前的关键管理做准备。由于很 少的仓库管理系统( w m s ) 和计算机系统能够支持储位优化管理，因此当前大约8 0 的 配送中心或仓库不能够进行正确的货位优化。 2 1 货位优化概述 货位优化( s l o t t i n go p t i m i z a t i o n ) ，就是在货品当前位置的基础上基于s k u s 和预 想不到的变化因素而动态地再配置仓库中货物的货位，以保证货位分布处于较合理 的状态，达到提高拣选效率和降低仓库操作成本的目的。 s k u s 因素货位优化的内因。即根据货架和货品本身特性的需要而进行货位 调整。例如，由于频繁对某些货物进行存取，这些货箱的重量可能发生较大变化。 如果货架出现诸如“上重下轻 等严重的不均衡现象，则可能导致货架变形甚至倾 覆。因此应遵循“重物在下 的原则，保证货架的稳定性。 预想不到的变化因素货位优化的外因。即根据货物的流动性进行货位调整。 在不同时期，货物的需求品种、需求数量和需求频率肯能会有较大变化，而取存不 同货位上的货物所花路径和时间的代价是不同的，因而货物的货位不应是一成不变 的，根据外界条件的变换，定期对若干货位进行交换。 2 2 货位优化管理 对自动化立体仓库的货位进行管理，是要合理地分配和使用货位。既要考虑如 何提高货位的利用率，又要保证出库效率。货位管理包括：货位分配、货位整理和货 位优化等三个部分，如图2 1 所示。 5 基于遗传算法的自动化立体仓库的货位优化研究 图2 1 自动化立体仓库内的货位管理模型 f i 9 2 1t h es om o d e lo f t h ea u t o m a t e dw a r e h o u s e 由图2 1 可以看出，货位管理主要包括货位分配、货位整理以及货位优化三部 分内容。首先要为需要入库的货物分配货位，当立体仓库运作一段时间以后就可能 出现货物存储比较零散的状况，这就需要进行货位调整；货位调整以后，会有一些 货物仍然处于不合理的货位，进行及时的货位优化就成了必要的操作。本文研究的 重点就是货位优化这一部分内容。 2 2 1 自动化立体仓库的布局 自动化立体仓库的出现是物流技术的一个划时代的革新。它不仅彻底改变了仓 储行业劳动密集、效率低下的落后面貌，而且大大拓展了仓库功能，使之从单纯的 保管型向综合的流通型方向发展。 自动化立体仓库具有普通仓库无法比拟的优越性。首先是节约空间、节约劳动 力。据国际仓库自动化会议资料：以库存1 1 0 0 0 托盘、月吞吐1 0 0 0 0 托盘的冷库为 例，自动化立体仓库与普通仓库比较情况为：用地面积为1 3 、工作人员为2 1 9 、 吞吐成本为5 5 7 ；立体仓库的单位面积存储量为普通仓库的4 到7 倍；其次是提高 仓库管理水平，减少货损，优化、降低库存，缩短周转期，节约资金。 1 自动化立体仓库分类简介 ( 1 ) 按货格内的货位数进行分类。以这种分类方式，自动化立体仓库可以分为 6 第二章自动化立体仓霄货伊优化管理 单货位式货架和多货位式货架两种。单货位式货架对货物单元的外形结构要求较低， 单面和双面托盘均适用，有的货物也可以直接放入货格；多货位式货架不适用于双 面托盘，而且要求托盘叉孔高度能满足堆垛机的升降要求，这种货架对货格利用较 好，能比单货位式货架存储更多的货位。 ( 2 ) 按货架高度分类。按这种分类原则，自动化立体仓库可以分为高层立体货 架( 1 2 米) 、中层立体货架( 5 1 2 米) 、底层立体货架( 太 遗传算法( g e n e t i ca l g o r i t h m ) 是模拟达尔文生物进化论的自然选择和遗传学 机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法， 它是由美国m i c h i g a n 大学的j h o l l a n d 教授于1 9 7 5 年首先提出的，他在该年发表 了著名专著自然系统和人工系统的适配该书系统阐述了遗传算法基本理论方法。 并提出了著名的模式理论。同年，d e j o n g 发表了遗传自适应系统的行为分析，他 在该论文中的研究工作可以看作是遗传算法的里程碑，他在该论文中将模式理论与 计算试验结合起来，进一步完善和系统化了选择、交叉以及变异操作，并提出了诸 如代沟等新技术。进过二十余年的发展，遗传算法的研究取得了丰硕的成果，特别 是近年来世界范围形成的进化计算热潮，计算智能已作为人工智能研究的一个重要 方向，以及后来人工生命研究兴起，使遗传算法受到广泛的关注。本文将对遗传算 法做一个简单的介绍。 3 1 遗传算法简介 遗传算法是从代表问题可能潜在的解集的一个种群( p o p u l a t i o n ) 开始的，而 一个种群则由经过基因( g e n e ) 编码的一定数目的个体( i n d i v i d u a l ) 组成。每个个 体实际上是染色体( c h r o m o s o m e ) 带有特征的实体。染色体作为遗传物质的主要载体， 即多个基因的集合，其内部表现( 即基因型) 是某种基因组合，它决定了个体的形 状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。 因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码 的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者 生存和优胜劣汰的原理，逐代( g e n e r a t i o n ) 演化产生出越来越好的近似解，在每 一代，根据问题域中个体的适应度( f i t n e s s ) 大小选择( s e l e c t i o n ) 个体，并借 助于自然遗传学的遗传算子( g e n e t i co p e r a t o r s ) 进行组合交叉( c r o s s o v e r ) 和 变异( m u t a t i o n ) ，产生出代表新的解集的种群。这个过程将导致种群像自然进化一 样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码 ( d e c o d i n g ) ，可以作为问题近似最优解。 遗传算法研究的历史比较短。它的发展起于7 0 年代，兴起于8 0 年代末9 0 年代 初，是模拟达尔文提出的遗传选择和自然淘汰的生物进化过程的计算模型。 3 1 1 遗传算法的基本原理 遗传算法( g e n e t i ca l g o r i t h m ，简称g a ) 是基于自然选择的遗传机制，在计算 基于遗传算法的自动化立体仓库的货位优化研究 机上模拟生物进化机制的搜索寻优算法。在自然界的演化过程中，生物体通过遗传、 变异来适应外界环境，一代一代地优胜劣汰、繁衍进化。遗传算法中根据每个个体 的适应度进行选择、交叉、变异，剔除适应度低( 性能不佳) 的染色体，留下适应 度高( 性能优良) 的染色体，从而得到新的群体。由于新群体的成员是上一代群体 的优胜者，继承了上一代的优良性能，因而明显优于上代。遗传算法就通过这样 反复地操作，向着更优解的方向进化，直到满足优化收敛的条件为止。g a 是一个重 复的搜索过程，但这一过程并不简单地重复搜索，而是个带着“记忆”的搜索， 算法本身使搜索不会向一个低的区域进化。g a 就是靠着自身的这种“导向”，不断 地产生新的个体，不断的淘汰劣的个体，从而进化到较高阶段或者说趋于收敛。 3 1 2 遗传算法的基本术语 由于遗传算法是自然遗传学和计算机科学相互结合渗透而成的新的计算方法， 因此遗传算法中经常使用自然进化中有关的一些基本用语。了解这些用语对于讨论 和应用遗传算法是十分必要的。 生物遗传物质的主要载体是染色体，d n a 是其中最主要的遗传物质，而基因又 是控制生物性状的遗传物质的功能单位和结合单位。复数个基因组成染色体，染色 体中基因的位置称为基因座，而基因所取的值叫做等位基因。在遗传算法中，染色 体对应的是数据或数组，在标准的遗传算法中，通常是由一维的串结构数据表现。 串上各个位置对应上述的基因座，而各位置上所取的值对应上述的等位基因。遗传 算法处理的是染色体，或者叫基因个体。一定数量的个体组成了群体，也叫集团。 群体中个体的数目为群体的大小，也叫群体规模。而各个体对环境的适应程度叫适 应度。 执行遗传算法时包含两个必要的数据转换操作，一个是表现型到基因型的转换， 它把搜索空间中的参数或解转换成遗传空间中的染色体或个体，此过程称为编码操 作；另一个是基因型到表现型的转换，它是前者的一个相反操作，称为解码操作。 编码与解码的相互关系，如图3 1 所示。 图3 1g a 算法原理图 f i 9 3 。1t h ef i g u r eo fg ap r i n c i p l e 1 2 第二幸遗传算法 人工遗传算法是由自然遗传算法演变而来，故人工遗传算法中所使用的基本术 语与自然遗传算法中所使用的基本术语存在对应关系，如表3 1 所示。 表3 - 1 遗传学和遗传算法中基本用语对照表 t a b e l 3 - 1t h er e f e r e n c et a b l eo fg e n e t i c sa n dg a 自然遗传算法人工遗传算法 染色体( c h r o m o s o m e )解的编码( 教据、数组、位串) 基因( g e n e )解中每一分量的特征 基因座 串中位置 个体解 适者生存算法停止时，最优目标值的解被留住的可能性最大 适应性( f i t n e s s )适应度函数值 群体( p o p u l a t i o n ) 选定的一组解( 其中解的个数为群体的规模) 复制( r e p r o d u c t i o n )根据适应函数值选取的一组解 交配( c r o ss o v e r ) 通过交配原则产生一组新解的过程 变异( m u t a t i o n )编码的某一个分量发生变化的过程 3 1 3 遗传算法的基本操作 虽然遗传算法是一个反复的搜索过程，但这一过程并非简单的重复，而是一个 带着“记忆”的搜索，它是根据适应度函数来进行搜索的，遗传算法通过这样的操 作来改良种群，进而实现寻优。遗传算法具体的操作步骤如下： 步骤一：初始化，设置进化代数计数器t = 0 ；设置最大进化代数t ；随机生产m 个个体作为初始群体p ( 0 ) 。 步骤二：个体评价，计算群体p ( t ) 中各个个体的适应度。 步骤三：选择运算，将选择运算算子作用于群体。 步骤四：交叉运算，将交叉运算作用于群体。 步骤五：变异运算，将变异运算作用于群体。 步骤六：终止条件判断t t ，转到步骤二，否则，以进化过程中所得的适应度最 大的个体作为最优解输出，终止运算。如图3 2 所示。 1 3 基丁遗传算法的自动化立体仓库的货位优化研究 图3 2 标准通传算法框图 f i 9 3 2t h ed i a g r a mo fg a 3 2 遗传算法特点 遗传算法是一种借鉴生物界自然选择和自然遗传机制的随机搜索算法。与传统 算法不同的是，大多数遗传算法是以某个单一度量函数的梯度进行统计，以产生一 个确定性的试验解序列。遗传算法不依赖梯度信息，而是通过模拟自然进化过程来 搜索最优解，它采用某种编码技术，将每种可能出现的解编码为系列的数字串( 称 1 4 第三章遗传算法 为染色体) ，然后模拟由这些串组成的群体的进化过程。遗传算法通过有组织的、随 机的信息交换来重新组合那些适应性好的串，生产新的群体。与传统算法相比，遗 传算法具有以下特点。 1 以决策变量的编码为运算对象 遗传算法将决策变量按照一定的原则进行编码，这种编码组成的运算对象对应 于自然界中的基因和染色体。采用编码的方法可以方便的进行遗传操作运算。从这 里可以看出遗传算法与传统的优化方法的不同，传统的方法一般是直接以决策变量 来进行优化运算。 2 直接以目标函数值同时使用多个搜索点作为搜索信息 遗传算法一般仅需要有一个目标函数就可以确定搜索方向和搜索范围，无需其 他目标函数信息。而传统的优化算法不仅需要利用目标函数值，还需要如导数值等 其他一些辅助信息才能确定搜索方向。 3 使用多个搜索点的搜索信息 这是由于遗传算法本身所具有的隐含并行性的特点。就是说一个个编码中隐含 了多种不用的模式，处理了一个个体，实际上也就并行处理了多种模式。 4 使用概率搜索技术 遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具 体领域，对问题的种类有很强的鲁棒性。近十年来，遗传算法得到了迅速的发展， 广泛应用于许多学科与领域。遗传算法的主要应用领域及问题举例，如表3 - 2 所示。 表3 - 2 遗传算法的主要应用领域 t a b e l 3 2t h ea p p l i c a t i o n so fg a 应用领域举例 规划 生产规划，并行机任务分配 设计 v l s i 布局，通信网络设计，喷气发动机设计 组合优化t s p 问题，背包问题，图划分问题 图像处理模式识别，特征提取，图像恢复 信号处理滤波器设计，目标识别，运动目标分割 机器人路径规划 人工生命 生命的遗传进化 1 5 基于遗传算法的自动化立体仓库的货位优化研究 3 3 本章小结 在本章中，首先介绍了遗传算法的基本概念、基本原理、特点以及多目标遗传算法 原理，然后根据研究课题的性质确定该课题为多目标优化问题，通过比较最终决定 采用多目标遗传算法来解决该问题。 1 6 第四章自动匕立体仓库的货传优化研究 第四章自动化立体仓库的货位优化研究 本章，我们将按照前两章所提出的货位分配优化理论以及遗传理论基础，对蒙 牛自动化立体仓库的货位优化研究加以详细的阐述。 4 1 基础数据收集 进行自动化立体仓库货位分配优化的基础是数据，故第一步就是收集所需要的 基础信息。所谓基础信息就是：仓库内货位特性资料、货品需求资料和产品文件。 通常，这些相关数据可以从w m s ( w a r e h o u s em a n a g e m e n ts y s t e m ) 或e r p ( e n t e r p r i s e r e s o u r c ep l a n n i n g ) 中获取，分析货品需求的季节性变化规律、淘汰变化等物流特性 资料。 通过前期的调查，我们得到蒙牛六期立体仓库的基础数据信息。蒙牛六期立体 仓库物料系统项目由太原刚玉物流工程有限公司负责整体规划、实施。蒙牛六期物 流系统主要服务于常温液态奶的生产、储存、发货，按照功能设计分为生产区、入 库区、储存区和出库区等，由计算机统一对整个物流流程实行自动化管理。六期项 目共设置2 2 条生产线，包括1 0 条利乐2 2 型机和1 2 条康美机、生产能力为1 8 0 0 吨 p o 小时，出库量为5 0 0 0 吨2 2 小时。按照规定，每天来自灌装车间的产品入库量 约为1 1 0 托盘d , 时；出库需分拆的量为3 0 托盘d , 时。在物流系统规划过程中，蒙 牛集团不仅对处理提出了很高的要求，更重要的是要求实现从牛奶生产到成品最后 出库装车发货全过程的无人作业，同时整个系统还要符合经济性、灵活性、安全性 与易维护性的要求。 通过研究分析仓库中货品的活动情况，有助于我们分析货品的历史数据、需求、 周转率等参数，从而为合理分配货位提供参考。 4 2 位优化的目标和约束 所谓货位优化就是根据一定的存储策略和几个货位分配原则对仓库中的初始货 位进行调整使之处于最合理的状态( 最合理状态指通过货位优化，使得货位达到提 高拣选效率和降低仓库操作成本的目的) 。货位优化的目标和约束在实施优化过程中 是必不可少的。目标决定了优化的方向，而约束则规定了优化的方式。 4 2 1 货位优化的原则 影响自动化立体仓库货位优化的因素有很多，如周转率、货品季节特性、移动 距离。自动化立体仓库是为物流系统服务的，所以立体库货位优化的目的应该是在 考虑上述因素的基础上满足物流系统的s p e e d ( 速度) 、s a f e t y ( 安全) 、s u r e l y ( 可靠) 、 1 7 基于遗传算法的自动化立体仓库的货位优化研究 l o w ( 低费用) 的3 s 1 l 原则。 4 2 2 货位优化的目的 货位优化是用来确定每一货品的恰当储存方式，在恰当的储存方式下的空间储 位分配。货位优化追求不同设备和货架类型特征、货品分组、货位规划、人工成本 内置等因素以实现最佳的货位布局，能有效掌握商品变化，将成本节约最大化。因 此，货位优化的最终目标就是通过提高生产力和将无用的运动减少到最少来降低成 本从而获取最大的效益。对货位优化模型而言，如何判定它的优劣呢? 我们采用仓 库关键业绩指标来判定，所谓仓库关键业绩指标指的是生产率、运送精度、库存周 转、入库时间、订单履行时间、存储密度和自动化程度等七个指标。通过平衡操作 者的工作量，提高拣货效率、减少补货工作量、缩短拣货距离等作业效率改善指标 来评定所建立的优化模型的效果。 4 2 3 货位优化的约束 货位优化并不是随心所欲的优化，必须满足一定的客观约束条件。如：货品重 量、货位大小、拣货准确率要求等。一般来说，货位优化的约束条件有如下几条。 1 、考虑到承载能力，在存放货品的时候应遵循“货架承重均匀，上轻下重 原 则，即重物放置在货架靠近地面的层位上。 2 、根据货物的尺寸规格选择相应的货位：大容量使用大货位，小容量使用小货 位；高货物使用高货位的层面储存，低货物使用低货位的层面储存。 3 、根据不同的拣货方式选择货品的储存区域：对于人工操作方式应该将易混淆 的货品储放于不同的区域；对自动化操作方式则不必要强调易混淆物品的储存区域。 综上所述，货位优化的约束条件在一定程度上对自动化立体仓库的作业效率有 影响，我们在研究立体仓库货位优化时，需要兼顾提高作业效率和满足限制条件两 方面的因素。 4 3a s r s 货位优化建模分析 所谓数学建模就是对现实世界的实际研究对象和目的建立模型的过程，也就是 对于现实世界的一个特定对象( 原始参照物) ，为了某种特定的目的，根据该对象特 有的内在规律，做出一些必要的简化假设，运用适当的数学工具得到一个数学结构。 本文研究的重点就是将立体仓库的货架结构、货品信息等经过抽象建立一个合理的 数学模型，并为之求解。 4 3 1 物流系统建模的意义与方法 模型是依据一定的假设对客观事物的一种抽象，由于模型忽略了实物的非本质 18 第四章自动化立体仓庠的货位优化研究 东西，故它比原始实物更容易控制。故通过对实际研究对象进行抽象，建立一种可 操作的模型，对求解问题有很大的帮助。本小节主要介绍建模的意义与方法。 1 物流系统建模的意义 模型在系统分析中得到了广泛的应用，模型是对系统的特征要素、有关信息和 变化规律的一种抽象表述，它反映了系统某些本质属性，描述了系统各要素间的相 互关系，系统和环境之间的相互作用。 物流系统优化的目的在于降低其供应链运营总成本，将物流系统的本质属性、 各要素间的相互关系等抽象成模型，这样对物流系统的优化研究有非常大的帮助。 从模型的特征可以看出模型是对现实系统的抽象，它能反映客观实际又高于实际。 一般来说，建造一个模型比建造一个完整的系统要经济得多，有利于减少复杂性， 便于理解。同时，可视化的建模，使得模型容易对具体世界进行仿真，以方便与他 人进行交流。 总而言之，系统分析中模型被广泛应用的意义主要体现在三方面：( 1 ) 客观实 体系统难做试验或者根本不能做试验，通过建模可以实现对实体系统的模拟仿真； ( 2 ) 对象问题虽然可以做试验，但是利用模型更便于理解；( 3 ) 模型易于操作，通 过模型的参数变化来了解现实问题的本质与规律更加经济方便。 2 物流系统建模的方法 物流系统的研究已经有较长的历史，其建模与分析设计的方法有很多，简单来 说主要有以下几种：( 1 ) 决策系统分析与建模法。该方法以概念参考模型为基础， 将系统分解为物理、信息和决策三部分，采用自上而下的分析方法清楚地表明决策 系统内部间的决策职能以及在决策和信息上的相互联系。该方法适合于决策功能层 的优化，但仿真实现比较困难；( 2 ) 功能模型。该模型结构化地描述了所研究系统 的活动和处理进程；( 3 ) 信息模型。该模型表达了制造系统环境的信息结构和语义； ( 4 ) 仿真模型设计。该模型表述了环境或系统时常变化的行为特征，常用于系统模 拟，建立动态模型；( 5 ) 面向对象问题分解法。面向对象设计方法的基本思想就是 寻找并处理问题域中的对象以及各对象间的关系，采用分解问题的方法将建模问题 分解为“三要素”：初始态、目标态和过程。 自动化立体仓库作为物流系统中的重要组成部分，对其进行研究时同样可以采 用以上的物流系统建模方法。在本文主要采用面向对象问题分解法来进行建模，对 仓库中的货位进行优化研究。 在解决问题的过程中，首先要对问题有一个全面的了解，只有对问题全貌有一 1 9 基丁遗传算法的自动化立体仓库的货位优化研究 个清晰的认识才能更好的研究问题。首先简单介绍分解问题法。其本质是将问题分 解为初始态、目标态、过程等“三要素”。初始态，表示当前看到的状态也就是目前 的已知条件与数据等；目标态，最终希望的目标即我们希望达到的或者说想要得到 的状态：过程，在初始态与目标态间作用的行为即我们通过什么样的方式使得问题 从初始态转向目标态。 “初始态”通过“过程”作用达到“目标态”，系统模型运行一段时间后由于多 种因素的影响，“目标态 可能已经达不到我们的要求，这时它就会转变为“初始态 。 这“三要素”间的转换关系，如图4 1 所示。 图4 1 状态转换图 f i 9 4 1t h ef i g u r eo fs t a t ec o n v e r s i o n 接下来应用该方法对自动化立体仓库货位优化问题进行分解。货位优化的实际 本质是将仓库中货品的当前货位进行调整使之处于最合理的位置，从而使得仓库中 货物的周转效率最高。应用问题分解法对货位优化问题进行分解：初始态，自动化立 体仓库中当前货品所处的货位布局情况：目标态，自动化立体仓库中希望所处的合理 货位布局情况；过程，对初始货位布局进行优化调整。 对问题进行分解以后，我们已经对货位优化问题有一个清楚的认识，明白货位 优化实际需要做的工作是什么、需要达到的目标是什么。那么如何实现初始货位布 局到合理货位布局的转化呢，这是本章的重点。 蒙牛六期立体仓库中主要存放的是成品纯鲜奶与成品瓶酸奶，根据产品存储温 度的不同要求，该库划分为常温与低温两个区域。常温区保存鲜奶成品，低温区配 置制冷设备存储瓶酸奶。根据本文第二章中提到的货位存储策略以及仓库特征，我 们决定采用分类随机存放的存储策略对货位进行优化。优化的过程需要在满足限制 条件的原则下提高作业效率。由此可见，货位优化问题实际上是一个多目标决策问 题，从经济学角度分析，既要满足限制条件实现货位布局最佳又要降低物流成本， 2 0 第匹章自动化立体仓库的货位优化研究 这本身就是一个“效益背反”问题。同时，货位优化的目标也不是唯一的，各优化 目标间存在相互矛盾、相互制约、相互竞争。例如，为了实现“常用易取”的目标， 我们系统将物流动性高的货物放置在靠近出入口的货位上；同时，为了保证货架的 稳定性采用的“重物应在下”的目标，则要求重量大的货物应放在靠近地面的位置 上。这样两个互不相关的属性就存在竞争，满足“常用易取”的目标势必会在一定 程度上削弱货架的稳定性。同理，满足了“重物应在下”的目标势必会在一定程度 上降低“常用易取”的实现。实际的工程优化问题大多数是多目标优化问题，目标 之间一般都是相互冲突的。多目标优化问题总是以牺牲一