（系统工程专业论文）基于离散粒子群与模拟退火融合算法的自动小车存取系统货位优化.pdf

摘要摘要随着现代工业的快速发展，自动化立体仓库得到越来越多的应用。面对成千上万的货格，立体仓库的货位存储优化已成为提高存取效率、降低成本的关键。自动小车存取系统( v s r s ) 是自动化立体仓库未来的主要发展方向，是柔性制造系统不可或缺的重要组成部分。因此，研究自动小车存取系统( a v s r s )的货位优化，提高系统的工作效率就具有了积极的现实意义。本文以a v s r s 为研究对象，研究了货位优化系统的目标以及实现货位优化系统目标的手段，分析了货位优化方法以及采用离散粒子群与模拟退火融合算法进行货位优化的原因。根据a v s r s 的物理结构和逻辑特征，建立了系统的简易三维数学模型，再结合自动化立体仓库货位优化的一般原则，建立了 v s r s的货位优化数学模型，并对其进行了数学描述。综合考虑了货物的质量和存取频率对自动小车存取系统进行了货位预分区，并进行了优化，最后再在指定分区内对货位进行优化，利用m a t l a bi 具对其进行了仿真，表明了本文提出的货位优化手段是有效的。关键词：自动小车存取系统；离散粒子群与模拟退火融合算法；货位优化a b s t r a c tw i t ht h ed e v e l o p m e n to fm o d e r ni n d u s t r ya n dl o g i s t i c st e c h n o l o g y ，t h ea u t o m a t i cw a r e h o u s ei sb e i n gw i d e l yu s e di nm o d e r nl o g i s t i c si n d u s t r y t h eu s i n go fa u t o m a t i cw a r e h o u s ec a ne c o n o m i z et h eu s eo fs p a c ea n di m p r o v et h ee f f i c i e n c yo fm a t e r i a l ss t o r a g ea n dr e t r i e v a l t h ea u t o n o m o u sv e h i c l es t o r a g ea n dr e t r i e v a ls y s t e m s ( a v s r s ) w i l lb et h ed e v e l o p m e n td i r e c t i o nf o ra u t o m a t e dw a r e h o u s e i tw i l lb ea ne s s e n t i a lc o m p o n e n to ft h ef l e x i b l em a n u f a c t u r i n gs y s t e mi nf u t u r e i ti sm e a n i n g f u lt oi m p r o v et h ee f f i c i e n c yo fg o o d sl o c a t i o na s s i g n m e n ti na u t o n o m o u sv e h i c l es t o r a g ea n dr e t r i e v a ls y s t e m b a s e do nt h ea v s r s ，t h ep a p e rs t u d i e st h eg o a l so fg o o d sl o c a t i o na s s i g n m e n ts y s t e ma n dh o wt oa c h i e v et h eg o a l s ，a n a l y s i st h er e a s o n sw h yt h eo p t i m i z a t i o nm e t h o du s e sd i s c r e t ep a r t i c l es w a l l i lo p t i m i z a t i o nw i t ht h es i m u l a t e da n n e a l i n ga l g o r i t h mt oo p t i m i z eg o o d sl o c a t i o na s s i g n m e n ts y s t e ma c c o r d i n gt ot h ep h y s i c a ls t r u c t u r ea n dl o g i c a lc h a r a c t e r i s t i co ft h ea v s r s ，t h em a t h e m a t i cm o d e lo fg o o d sl 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 ni se s t a b l i s h e db a s e do nt h em o d e l ，t h es t r a t e g yo fs e c t i o na s s i g n m e n ti sp r o p o s e da n dt h es a p s oi sa d o p t e dt om i n i m i z et h em a k e s p a nu n d e rt h ed e a d l o c k - f l e es c h e d u l i n g f i n a l l y , ac a s 0s t u d yi sg i v e nt ov a l i d a t et h ea l g o r i t h m k e y w o r d s ：t h ea u t o n o m o u sv e h i c l es t o r a g ea n dr e t r i e v a ls y s t e m s ，s a d p s oa l g o r i t h m ，g o o d sl 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 n厦门大学学位论文原创性声明本人呈交的学位论文是本人在导师指导下，独立完成的研究成果本人在论文写作中参考其他个人或集体已经发表的研究成果，均在文中以适当方式明确标明，并符合法律规范和厦门大学研究生学术活动规范( 试行) 。另外，该学位论文为() 课题( 组)的研究成果，获得() 课题( 组) 经费或实验室的资助，在() 实验室完成。( 请在以上括号内填写课题或课题组负责人或实验室名称，未有此项声明内容的，可以不作特别声明。)声明人，孙群净杜月 聃厦门大学学位论文著作权使用声明本人同意厦门大学根据 中华人民共和国学位条例暂行实施办法等规定保留和使用此学位论文，并向主管部门或其指定机构送交学位论文( 包括纸质版和电子版) ，允许学位论文进入厦门大学图书馆及其数据库被查阅、借阅。本人同意厦门大学将学位论文加入全国博士、硕士学位论文共建单位数据库进行检索，将学位论文的标题和摘要汇编出版，采用影印、缩印或者其它方式合理复制学位论文。本学位论文属于：。() 1 经厦门大学保密委员会审查核定的保密学位论文，于年月日解密，解密后适用上述授权。() 2 不保密，适用上述授权。( 请在以上相应括号内打“一或填上相应内容。保密学位论文应是已经厦门大学保密委员会审定过的学位论文，未经厦门大学保密委员会审定的学位论文均为公开学位论文。此声明栏不填写的，默认为公开学位论文，均适用上述授权。)声明人( 签名) ：窍撤狰棍第一章绪论第一章绪论1 1 本课题研究背景及意义1 1 1 课题的背景随着科学技术和工业生产的飞速发展，现代物流技术领域内出现了一种新型仓储方式一自动化立体仓库( a u t o m a t e ds t o r a g e r e t r i e v a ls y s t e m ，a s r s ) 。它是以高层货架为主体，以成套搬运设备为基础，以计算机控制技术为手段的高效率物流、大容量存储的机电一体化高科技集成系统。它集机械、电子、计算机、通信、网络、传感器和自动控制等多种技术于一体，以搬运机械化、控制自动化、管理微机化、信息网络化为特征，成为现代化物流设计中产品生产与存储的枢纽。立体仓库系统主要有两大应用领域：其一是各种自动化生产线中的在线立体仓库系统( 如c i m s 中的在线立体仓库系统) ：其二是各种物资配送中心( 如超市配货中心等) 。1 9 5 9 年世界上第一座自动化立体仓库在美国阿尔巴马州建成。之后，美国于1 9 6 3 年建成了世界上第一座计算机控制的自动化立体仓库。现在，以自动化功能齐全的立体仓库取代传统的普通房式仓库己成为世界仓储建设发展的潮流，其中，应用最多、发展速度最快的国家是日本。近年来每年约有上千个各种类型的自动化物流系统投入使用。我国在2 0 世纪7 0 年代开始进行自动化立体仓库的开发研究工作，已有几十家企业、科研院校和高等学府从事自动化物流系统的开发研究和工程应用。北京起重运输机械研究所于1 9 6 3 年就研制了我国第一台桥式堆垛起重机，1 9 7 3 年开始研制由计算机控制的自动化立体仓库，并于1 9 8 0 年投入使用。同时，由北京机械工业自动化研究所等单位研制建成的我国第一座自动化立体仓库在北京汽车制造厂投产。我国的自动化仓库技术已实现了与其它信息决策系统的集成，正在做智能控制和模糊控制的研究工作。到目前北京机械工业自动化研究所已为国内企业建立和完善了3 0 多座自动化立体仓库，如济南第一机床厂、仪征化纤工业公司、成都飞机制造公司、株洲南方摩托集团有限公司、重庆长安汽车有限公司等。据不完全统计，到2 0 0 5 年为止我国已建成的立体仓库已达5 0 0 余座，其中高度在1 5 米以上的大型立体仓库1 0 0 多座。2 0 0 5 年建成的有5 0 个左右 9 1 。现在我国更有多家单位研制和生产l基于离散粒子群与模拟退火融合算法的自动小车存取系统货位优化自动化立体仓库，如西安迪普物流机械有限公司生产的托盘式立体仓库、料箱式立体仓库、重力自动立体仓库，还有太原双塔刚玉股份有限公司、西安斯达机电有限责任公司等多家公司【。现在，自动化物流技术和成套设备的开发研制己经发展成为一个庞大的产业。目前，物料搬运产业年产值超过2 0 0 亿美元，其中立体仓库和自动导引车a g v 等直接组成自动化物流的产品，1 9 9 7 年达到了2 7 亿美元，其研究及应用也己经达到标准化、系列化、流水线生产的程度，并具有相当高的自动化水平。在德国，自1 9 9 2 年以来，自动化物流系统的产品己经发展成为机械制造业中最大的专业分支，1 9 9 6 年产值为1 7 5 亿马克。今天，现代物流的理论已进入世界各国经济生活的各个领域，自动化的物流系统己成为现代化工厂不可缺少的重要部分。可以说，物流是经济发展的命脉，像人体的血液一样，时刻支撑着人体的各种循环，维持着生命。在物流学众多的研究领域中，工业企业物流一直是被关注的焦点，这不仅由于物流组织的好坏直接决定着企业生产过程是否能够顺利进行，决定着企业产品的价值和使用价值是否能够顺利实现，而且企业的物流费用己成为生产成本和流通成本的重要组成部分。1 9 7 9 年英国的第一次调查表明，在从原材料获取到把产品送到用户的整个生产流通过程中，只有7 2 的费用是生产成本，其他( 剩余的2 8 ) 的6 3 都消耗在运输和仓储过程中。在第五次国际物流会议上，美国产业界人士明确指出，当前美国全部生产过程中只有5 的时间用于加工制造，9 5 的时间则用于搬运、储存等物流过程。在我国，1 9 9 9 年全社会物流费用支出约占g d p 的2 0 【l l 】。在这种情况下，企业将主要力量花在降低生产成本上是“不得要领 的，明智而有效的方法是改善物流。因此，以降低物流成本、减少资金占用、缩短生产周期为主要目标的物流合理化( r a t i o n a l i z a t i o n ) 被称为企业的“第三利润源泉 、“最重要的竞争领域一，它被放到企业发展的战略高度来加以研究和实施。而自动化仓库作为物流系统的一个枢纽和核心，是物流系统实现物流合理化的关键所在，在国民经济中有着举足轻重的地位因此，随着国民经济的发展，无论是在流通领域还是在生产制造领域，建立自动化立体仓库的系统模型，构建系统的模型框架，优化提高系统的整体性能，已成为产学界研究的热点。2第一章绪论1 1 2 课题的意义自动化仓库系统是现代物流系统的一个重要组成部分，广泛地运用于各行各业中。随着现代工业的发展，柔性制造系统( f m s - - 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 ) 和工厂自动化( f 卜_ f a c t o r ya u t o m a t i o n )对自动化仓库系统提出了更多的要求【1 2 l 。自动化仓库系统的功能已经不再仅是储存原料和保管成品，更重要的是对内支持灵活变化的实时性生产需要，对外能够准确便捷出库，快速响应销售市场的需求。目前很多工厂的自动化仓库已经和生产系统联为一体，成为生产线上毛坯或半成品的供应者。原料出库的快速、实时和准确将极大地影响生产线的加工效率，而原料经过加工组装为成品后，成品回库的速度也将影响装卸工作站的下批工作，实时性要求也较高。仓储管理本身成为一种具有服务性质的生产，作为工厂生产线的始端和终端，必须面临提高效率，加速周转的要求。因此，实现仓库系统的实时性，柔性化，采用灵活的传输设备和物流线路是实现物流和仓储自动化的趋势。仓库物流控制系统的设计、实现、运行是非常复杂的，如何发现和预测物流中的瓶颈和关键路径，控制和优化物流设备运行，挖掘设备资源的潜力，降低库存水平和能耗，以实现多路径的物料输送平衡、资源的平衡、时间的平衡，是仓库物流系统控制和监控调度的主要问题。由于堆垛机能同时进行水平和垂直运动，存取效率较高，所以传统的自动化仓库系统一般采用堆垛机存取货物( 一般称为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 s ：a s r s ) 。然而，堆垛机只能服务单一的巷道，若发生故障，那么该巷道则无法进行出入库操作，进而使整个仓库运行效率大大受到影响。以某厂的自动化立体仓库系统为例，该厂有原料库、辅料库和成品库三个小型立库，是整个生产过程的调节中心。每个自动化仓库有六排货架、8 层货位、6 4 列货格，共计3 0 7 2 个货位。其中每台堆垛机服务两排二维货架。堆垛机可以在二维空间运行，以提高存取效率。然而采用堆垛机存取方式，当堆垛机发生故障时，该巷道随即处于瘫痪状态，其影响有两方面，一方面，系统控制策略失效，如货物巷道均分、先进先出原则；另一方面，降低了出入库效率，特别是出库效率( 约为原来的2 3 ) ，给企业生产计划和物质流通带来很大的影响。由于堆垛机存取方式上的不足，查阅国外资料发现，一种新型的自动化仓基于离散粒子群与模拟退火融合算法的自动小车存取系统货位优化库系统一自动小车存取系统( a u t o n o m o u sv e h i c l es t o r a g ea n dr e t r i e v a ls y s t e m s ，a v s r s ) 2 0 0 1 年后开始受到关注。a v s r s 利用轨道导引小车( r a i l g u i d e dv e h i c l e s ，r g v ) 在立体仓库货位间的轨道上作水平运动实现货物的出入库操作，其垂直运动依靠安置在仓库边缘的升降机系统完成。即r g v 小车在立体仓库中作三维运动实现货物的存取操作。与a s r s 相比，虽然a v s r s 运行效率相对较低，但是其价格低且柔性化更高，每台r g v 可以服务任意货位，不会因为某辆小车故障而影响整个仓库的出入库操作，另外用户还可以根据业务量调整小车运行的数量，因此，a v s r s 被认为是a s r s 的替代系统【1 3 】。a v s r s 融合了a g v 系统的柔性和原有高架库系统的优势，未来将成为柔性制造系统不可或缺的部分。相比a v r s 系统，a v s r s 系统的控制明显复杂的多，特别是对r g v 自动小车系统的控制。另外，自动小车存取系统与a s r s 系统又有所区别，因为前者小车需要在三维空间运行，后者则是在平面运行，而且它们的运行模式也有所不同。所以有必要对a v s 瓜s 这种新型自动化仓库系统进行深入研究。1 2 国内外研究现状以自动化功能齐全的立体仓库取代传统的房式仓库己成为世界仓储建设发展的潮流。据不完全统计，美国拥有各种类型的自动化立体仓库2 0 0 0 0 多座，日本有3 8 0 0 0 多座，德国有1 0 0 0 0 多座，英国有4 0 0 0 多座，前苏联有1 5 0 0 多座。我国进人9 0 年代以来，一些交通运输部门，物资储存部门以及现代化大中型企业对老式仓库进行了技术改造，开始采用自动化立体仓库。据不完全统计，目前我国拥有立体仓库5 0 0 余座，其中高度在1 5 米以上的大型立体仓库1 0 0 多座。在欧美及日本等发达国家，立体仓库的自动化程度已相当高，整个仓库的运作也实现完全自动化。而国内，自动化仓库还处于起步阶段，自动化程度还比较落后。自动化仓库在设计和使用中还存在许多问题，如立体仓库利用率低，效果不明显，规模不确定，优势不突出等，造成许多库场资源闲置。特别是一些产量较小、品种单一的生产型企业，自动化立体仓库库场设备资源闲置与重复配置矛盾突出，问题严重【1 4 1 。由于目前自动化立体仓库的安装和使用具有很高的成本，自动化设备价格昂贵。所以在建设物流系统及自动化仓库的过程中，4第一章绪论追求先进技术的同时，还应该更加注重实用性和安全性。合理的自动化立体仓库的设计，对立体仓库进行优化管理、调度，可以在不增加设备投资的基础上，减少作业时间，从而大大提高仓库的运行效率。分析总结国内外对自动化立体仓库的研究的主要理论和成果，可归结为以下几个方面：1 、自动化立体仓库总体的规划设计。这一领域的研究主要是从自动化立体仓库设计阶段入手，结合企业的需求，综合考虑成本、效率等因素，从整体上设计出适用的自动化存储系统。自动化立体仓库的设计包括很多方面，如构造设计、堆垛机的选用、电气控制的设计、货架的设计、仓库管理信息系统的设计、输送系统的设计等【l 见。这方面理论主要是从宏观上对自动化立体仓库进行整体规划设计，研究也大多集中在自动化立体仓库规划设计的初期设计阶段。2 、存取设备的改进。即对于自动化立体仓库使用设备进行改进，包括堆垛机，输送系统和周边设施等的改进。大多数研究主要集中在堆垛机的改进，比较典型的理论有：双货叉存取方式，即在原来的基础增加了一个货又，这种新颖设计的堆垛机拥有两个货叉，它在运作中可以缩短在货架到返回点之间的运行时间，而且可以在一个工作流程中就完成存货和取货的操作；堆垛机性能构造的改进设计，即对堆垛机结构和机械设计的力学分析和研究，得出适合应用的特殊结构堆垛机的优化设计方法【嘲。3 出入库任务作业的调度的优化即从优化调度自动化立体仓库出入库任务角度出发，把自动化立体仓库的出入库任务问题或订单下发分配问题抽象成为自动化立体仓库中的旅行商问题t s p ( t r a v e ls a l e s m a np r o b l e m ) 【1 7 1 ，目前关于这方面理论研究有很多，对于这类问题的解决方法也有很多，比较有代表性的有：a s y m m e t r i ct s p s 问题的研列1 舯，采用蚁群算法的研究【l9 】，遗传算法 2 0 l ，组合算法等。4 、控制系统优化。即对自动化立体仓库控制系统及p l c 编程问题的研究，主要典型的理论有：将双模模糊控制器应用与堆垛机的快速、准确的定位控制的研究：针对传统程序设计方法难以对具有并发、协调、竞争等复杂事件的p l c 控制系统编程的问题，探讨一种基于p e t r i 网模型的p l c 程序设计方法，利用p e t r i网的图形性质和对并发事件建模的能力，可简便、直观地构建p l c 控制系统程序【2 0 】的研究。5 、仓库管理信息系统的集成。即采用集成化技术对w m s 系统进行优化设计5基于离散粒子群与模拟退火融合算法的自动小车存取系统货位优化从而实现从上位端对自动化立体仓库的最优控制和操作。主要的研究理论有：基于实时控制的出入库算法，即采用出入库管理、通讯控制、和滚道控制、堆垛机控制四个部分算法通过可编程控制器有机集成，将各种出入库复杂情况和出入库过程中的设备情况有机的集合在一起，从而统一调度处理的模式【2 1 】；基于u m l 的仓库管理系统设计技术，在u m l 建模机制的基础上，讨论了数据库应用系统的面向对象的设计方法瞄1 ：结合现代科技的发展，特别是计算机技术、通信技术以及信息技术等应用，着重研究自动化立体仓库系统的控制及管理技术【2 3 】o综上所述，对于自动化立体仓库各个领域的研究已经取得了非常显著的成绩，但是对于立体仓库调度策略和应用的研究还显得比较滞后，特别是对于出入库流程设计和货位分配的优化调度方面还没有形成比较标准化的设计方法。大型的自动化立体仓库具有成千甚至上万货格，对于每一次入库操作来说，有许多可供选择的空货位作为入库位；同样对于每一次出库来说，也存在许多满足出库条件的出库货。如果每一次出库或入库操作中，选择自动存取小车运行时间或距离最短的货位进行出入库操作，可以减少每次出入库作业时间。对于每天繁忙的多出入库任务，如果每一次出入库都可以节省一定时间，则自动化立仓库的总体工作效率会得到很大的提高。选择最优的货位进行出入，在使用有限设备的基础上，可以提高设备使用效率，节省调度时间、作业时间，加速物品存储周转率以及加快物品流通，从而充分体现出自动化立体仓库的优势。本文就是通过提出一种基于选择货位存储优化度的算法，以实现最优出入库货位为目标，即在每一次入库和出库过中总是选择最优的出入库货位进行操作，从而提高整个自动化立体仓的作业效率：同时通过进一步合理规范自动化立体仓库出入库流程，其出入库作业更加合理化、实用化和标准化。1 3 本文的研究内容及主要创新点1 3 1 本文的主要研究内容在本文中，主要进行了如下两个方面的研究：l 、a v s r s 货位优化数学模型根据自动小车存取系统( a v s r s ) 的物理结构和逻辑特征，建立了仓库的三6第一章绪论维模型，给出了自动小车存取系统货位优化分配的数学模型描述。2 、a v s r s 货位的优化配置自动小车存取系统( a v s r s ) 是一个动态的有机的整体，要想使整个系统运行效率达到最优，必须合理安排好各个环节，做到统筹兼顾、前后照应。货位的安排作为仓库调度问题的第一个环节，在仓库的管理中具有重要的地位，如果货位的安排合理可以做到减少自动存取小车的工作量、减少盘库作业，并能使得货架的受力情况良好，从而加快了货物周转，提高了效率，提高了可靠性。本文提出了先对立体仓库进行预分区，再对货物进行在所指派库区进行货位优化的货物存放方案，给出了仓库进行预分区的数学模型和货位优化配置的数学模型。提出了用粒子群模拟退火融合算法解决此类问题的步骤。并以某一仓库为原型利用上述方法进行了仿真实验，表明了本文货位优化方法的有效性。1 3 2 本文的主要创新点本文的主要创新点：1 、对新型的自动化立体仓库a v s r s 建立了三维模型，并对其三维模型进行了数学描述。2 、建立了a v s r s 货位预分区的数学模型，并对仓库按需要进行货位分区。3 、建立了a v s r s 货位优化分配系统的数学模型并对其进行了数学描述，利用离散粒子群与模拟退火融合算法对a v s r s 进行了货位优化。7基于离散粒子群与模拟退火融合算法的自动小车存取系统货位优化第二章自动化立体仓库系统及相关货位优化方法2 1 自动化立体仓库2 1 1 自动化立体仓库简介在现代物流系统中，自动化立体仓库是一个重要的组成部分，它是一种新型的仓储技术，自动化立体仓库又称为自动存储检索系统( a u t o m a t e ds t o r a g e r e t r i e v a ls y s t e m ，即a s r s ) ，它是物料搬运和仓储科学中的一门综合科学技术工程。它以高层货架为主要标志，以成套先进搬运设备为基础，以先进的计算机控制技术为主要手段，由此形成高效率的物流、大容量的科学存储，以适应现代物流系统的需求。自动化立体仓库是现代物流技术的核心之一，是当代物流技术、仓储技术、自动化技术高度集成化的产物，它集存储、输送、分发、管理等功能于一体：由于采用高层立体结构，具有存储容量大、占地面积小的优点，它是工厂物流和计算机集成制造系统( 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 ) 中的重要环节。同样也在商业流通和城市交通等领域有着广泛的应用。自动化仓储技术的发展历史和现实己经表明，使用自动化立体仓库能够带来巨大的社会效益和经济效益。自动化立体仓库具有传统仓库的基本功能外，还具有分拣、理货的功能，以及在不直接进行人工处理的情况下，自动存储和取出物料的功能。现代自动化立体仓库，是在生产力和科学技术不断发展的情况下出现的一种崭新的物流技术，也是一种处于不断发展中的技术【2 4 】。美国学者j a v c h i t c 将自动化技术在仓储领域的发展分为以下五个阶段【2 5 】：第一阶段是人工仓储技术阶段。在这一阶段当中，物资的输送、存储、管理和控制主要靠人工实现，其实时性和直观性有较明显的优点。人工仓储技术在初期设备投资的经济指标也具有优越性。第二阶段是机械化仓储技术阶段。物料可以通过各种各样的传送带，工业输送车、机械手、吊车、堆垛机和升降机来移动和搬运，用货架、托盘和可移动式货架存储物料，通过人工操作机械存取设备，用限位开关，螺旋机械制动和机械监视器等控制设备的运行。机械化满足了人们对速度、精度、高度、重第二章自动化立体仓库系统及相关货位优化方法量、重复存取和搬运等方面的要求。第三阶段是自动化仓储技术阶段。自动化技术对仓储技术的发展起了重要的促进作用。2 0 世纪5 0 年代末和6 0 年代初，相继研制和采用了自动导引小车( a g v ) 、自动货架、自动存取机器人、自动识别和自动分拣等系统。2 0 世纪7 0 年代和8 0 年代，旋转式立体货架、移动式货架、巷道式堆垛机和其他搬运设备都加入了自动控制的行列，但这时只是各个设备的局部自动化各自独立应用，被称为。自动化孤岛一。随着计算机技术的发展，自动化仓库研究的工作重点逐渐转向物资的控制和管理的实时、协调和一体化，信息自动化技术逐渐成为仓储自动化技术的核心。计算机之间、数据采集点之间、机械设备的控制器之间以及它们与主计算机之间的通信可以及时高效地汇总信息，仓库计算机及时地记录订货和到货时间，显示库存量，计划人员可以方便地做出供货决策，他们知道目前工厂正在生产什么、需要订什么货物、什么时间发什么品种、规格的货物，管理人员随时掌握货源及客户的需求。在这一阶段信息技术的应用己成为仓储技术的重要支柱。第四阶段是集成自动化仓储技术阶段。在2 0 世纪7 0 年代末和8 0 年代，自动化技术被越来越多地用到生产和分配领域，显然，“自动化孤岛”需要集成化，于是便形成了“集成系统 的概念。在集成化系统中，整个系统的有机协作，使总体效益和生产的应变能力大大超过各部分独立效益的总和。集成化仓库技术作为计算机集成制造系统中物资存储的中心受到人们的重视。在集成化系统里包括了人、设备和控制系统，而前面所叙述的三个阶段是它的基础。第五阶段是智能自动化仓储技术阶段。人工智能技术的发展使自动化技术向更高级的阶段智能自动化方向发展。现在，智能自动化仓储技术还处于发展阶段，但已引起国际上有关设计研究人员的极大关注，它将是仓库自动化技术的主要发展方向。随着自动化技术和信息技术在自动化立体仓库中广泛运用，自动化立体仓库的发展将呈现以下趋势：l 、仓储作业管理自动化水平将会逐步提高。2 、智能技术将会获得应用。3 、仓库作业调度向智能化发展。9基于离散粒子群与模拟退火融合算法的自动小车存取系统货位优化2 1 2 自动化立体仓库优点由于自动化立体仓库具有节约劳动力，作业迅速准确，提高保管效率，减低物流费用等优越性，因此受到了广泛的重视。它是工厂物流、柔性制造系统和计算机集成制造系统中不可或缺的重要组成部分，它在提高生产效率、实现仓储自动化方面起到了越来越大的作用，其智能化管理在提高企业竞争力和满足客户服务等方面已经越来越成为一个重要的因素。其优点主要体现在以下几个方面汹1 ：1 、提高空间利用率及货物管理质量。由于使用高层货架存储货物，存储区可以大幅度地向高空发展，充分利用仓库地面和空间，因此，节省了库存占地面积，提高了空间利用率。采用高层立体货架储存，不同的货物在不同的货架空间内，彼此之间不互相挤压，存取时互不干扰。而且由于采用机械化作业，所以货物在运输过程中的完好性比较好，不容易发生破坏。另外，结合了计算机管理，可以容易地实现先入先出，防止货物的自然老化、变质、生锈或发霉矗盘守o2 、提高劳动生产率，降低劳动强度。自动化立体仓库使用机械和自动化设备，运行和处理速度快，大大提高了劳动生产率，减轻了仓库管理人员的工作强度和工作环境，确保安全、文明生产。同时，机械化使立体仓库的存取过程完全融入到企业的物流系统当中，使物流系统的运行更加流畅和有效。采用自动化技术后，还能较好地适应黑暗、低温、污染、有毒和易爆等特殊场合的物品存储需要。3 、科学储备，提高物料调节水平，加快储备资金周转。由于自动化仓库采用计算机控制，计算机能准确的对仓库中的各种信息进行存储和管理，调控仓库中的堆垛机和智能运货车合理、高效率的运行，使仓库的运行更加流畅，能减少货物处理过程中的差错，而利用人工管理不能做到这一点。同时借助于计算机管理还能有效地利用仓库储存能力和库存信息进行有效的评估，便于清点和盘库，合理减少库存，加快储备资金周转，节约流动资金，从而提高仓库的管理水平。另外，在自动化系统的管理和控制下，能对物料进行科学的管理使物料在存储过程中合理利用各种资源，提高处理效率，适应多种存储要求。4 、有效衔接生产与库存，加快物资周转，降低成本。作为生产过程的中间1 0第二章自动化立体仓库系统及相关货位优化方；去环节，具有原材料、在制品和成品的缓冲存储功能，在自动化和机械化设各处理下，自动化程度提高各种物料库存周期缩短，从而降低了总成本。对不同运输方式、不同装运方式、不同状态的物料衔接，改变运输方式，改变装运方式和采用有效的技术，都会带来费用的降低。5 、为企业的生产指挥和决策提供有效的依据。自动化立体仓库的信息系统可以与企业的生产信息系统集成，实现企业信息管理的自动化。由于仓储信息及时准确，便于企业决策人员及时掌握库存情况，根据生产以及市场情况及时对企业规划做出调整，提高了生产的应变能力和决策能力。因此，使用自动化仓库，促进企业的科学管理，减少了浪费，保证均衡生产。国内外的实践经验表明，阻自动化仓库为中心的物流管理自动化，在实现物料的自动化管理，加速资金周转，提高劳动生产率，降低劳动强度，节约库存的占地面积，提高厂房空间的利用率，保证生产均衡等诸方面能带来巨大的效益。213 传统自动化立体仓库的组成自动化立体仓库是机械和电气、强电控制和弱电控制相结合的产物。传统的巷道堆垛机式自动化立体仓库如图2 - i 所示。图2l 巷道堆垛机式立体仓库自动化立体仓库主要由货物存储系统、货物存取和传送系统、控制和管理三太系统组成，还有与之配套的供电系统、空调系统、消防报警系统、称重计基于离散粒子群与模拟退火融合算法的自动小车存取系统货位优化量系统、信息流通系统等【2 7 ，2 8 矧。l 、货物存储系统：由立体货架的货格( 托盘或货箱) 组成，用于存放货物，货物放在托盘上，出入库时连同托盘一起出入库。其高度分为高层货架( 1 2 米以上) 、中层货架( 5 米至1 2 米) 、底层货架( 5 米以下) ，按货架形式分为单元货架、重力货架、活动货架和拣选货架等。2 、货物存取和传送系统：该系统承担货物存取、出入仓库的功能，通常由巷道堆垛机、出入库输送机、装卸机械等组成。巷道堆垛机是在高层货架的窄巷道内作业的起重机，可实现沿轨道行进、垂直起降和货叉伸缩三种功能，用于从两侧货架的任何货位上自动存入或取出货物。每两个高层货架之间有一台巷道堆垛机。出入库输送机可根据货物的特点采用传送带输送机、机动辊道、链传动输送机等，主要将货物送到堆垛机上下料位置和货物出入库位置。装卸机械承担货物出入库装车或卸车的工作，一般由行车、吊车、叉车等机械组成。3 、控制和管理系统：由管理计算机、中央控制计算机和堆垛机、出入库输送等直接控制的可编程控制机械组成控制系统，控制调度整个立体仓库的出入库作业的正常运行。计算机管理系统主要完成对整个仓库系统信息管理和作业管理，并负责与上级系统的通讯以及企业信息管理系统的部分任务。2 1 4 自动小车存取系统由于堆垛机只能服务单一的巷道，若发生故障，该巷道随即处于瘫痪状态，无法进行出入库操作，进而使整个仓库运行效率受到影响。不仅降低了出入库效率，而且还可导致控制策略失效。因此，为了弥补传统立体仓库系统的不足，一种新型的自动化仓库系统一自动小车存取系统( a u t o n o m o u sv e h i c l es t o r a g ea n dr e t r i e v a ls y s t e m s ，a v s r s ) 应运而生。自动小车存取系统( a v s r s ) 利用轨道导引小车( r a i l g u i d e dv e h i c l e s ，r g v ) 在立体仓库货位间的轨道上作水平运动实现货物的出入库操作，其垂直运动依靠安置在仓库边缘的升降机系统完成。即r g v 小车在立体仓库中作三维运动实现货物的存取操作。a v s r s 系统主要包括轨道导引小车系统( r g v ) 、升降机系统和货架以及货物缓存区，其立体简图如图2 2 【3 0 1 所示与a s r s 相比，虽然a v s r s 运行效率相对较低，但是其价格低且柔性化更高，每台r g v 可以服务任意货位，不会因为某辆小车故障而影响整个仓库的出入库操作，另外用户还可以根据业务量调整小车运行1 2第二章自动化立体仓库系统及相关货位优化方法的数量，因此，a v s r s 被认为是a s r s 的替代系统。a v s r s 从2 0 0 0 年后逐渐在欧洲开始受到关注并且已经有若干实际应用。图2 - 2a v s r s 的立体简图图23a v s r s 的平面框架示意图圈2 - 3 是a v s r s 系统的平面框架示意固。从图23 可以看出，a v s r s 系统与传统的巷道堆垛机式立体仓库不同。入库时，先由升降机运送r g v 小车和托盘到指定的层数，再由r g v 小车将货物运送至指定的货位。出库时刚好相反。22 货位优化系统目标及实现手段的分析22 1 货位优化系统目标分析现代物流尤其是在供应链管理模式下的新目标足：用同样的劳动力或成本基于离散粒子群与模拟退火融合算法的自动小车存取系统货位优化来做更多的工作，减少订单履行时间，提供更快捷，更周到的服务。这个目标可以用两个字来进行描述，即“效率 。以效率为目标的货位优化系统，能够在更短的时间内完成货物的入库、出库操作。这个目标总的来说，就是要提高工作效率，而货位优化系统的目标正好符合现代物流提高工作效率的要求，能为现代物流事业的发展起到积极的作用【3 舶。在仓储业迅猛发展的今天，许多智能化仓储设备都已经开始应用。我国加入w t o 以后，很多国外的大物流公司纷纷在我国进行投资，为引进国外先进技术创造了一个良好的环境，因此，提高仓储工作效率是完全“可乞求 的，把提高工作效率作为货位优化的目标，具有“积极的 ，“可乞求的 作用。基于以上分析，本文选择了提高工作效率作为本文研究的仓储货位优化系统的目标。2 2 2 货位优化系统目标的实现手段分析货位优化管理是用来确定每一货品的恰当储存方式，在恰当的储存方式下的空间储位分配。货位优化时，为了提高工作效率，一般要遵循以下四种规则，即实现提高工作效率这个目标，有四种手段：( 1 ) 以周转率为基础的手段周转率即存取频率，对不同货位上物品进行存取时，所需要的时间是不同的【3 4 1 。以周转率为基础的手段，即将货品按周转率由大到小排序，再将此序分为若干段( 通常分为三至五段) ，同属于一段中的货品列为同一级，依照定位或分类存储法的原则，指定存储区域给每一级货品，周转率越高应离出入口越近 3 5 10( 2 ) 产品同一性手段所谓同一性的原则，指把同一物品储放于同一保管位置的原则。这样作业人员对于货品保管位置能简单熟知，并且对同一物品的存取花费最少搬运时间时提高物流中心作业生产力的基本原则之一。否则当同一货品散布于仓库内多个位置时，物品在存放取出等作业时不方便，就是在盘点以及作业人员对货架物品掌握程度都可能造成困难。( 3 ) 产品尺寸手段在仓库布置时，应该同时考虑货物单位大小以及由于相同的一群物品所造成的整批形状，以便能供应适当的空间满足某一特定要求。所以在存储物品时，1 4第二章自动化立体仓库系统及相关货位优化方法必须要有不同大小位置的变化，用以容纳不同大小的物品和不同的容积。此法则可以使物品存储数量和位置适当，使得拨发迅速，搬运工作及时间都能减少。一旦未考虑存储物品单位大小，将可能造成存储空间太大而浪费空间，或存储空间太小而无法存放；未考虑存储物品整批形状亦可能造成整批形状太大无法同处存放。( 4 ) 以重量为基础的手段所谓以重量为基础的手段，是指按照物品重量不同来决定储放物品于货位的高低位置，主要是为了满足货架的稳定性，也可以减少人工搬运的困难。一般而言，重物应保管于地面上或货架的下层位置，而重量轻的物品则保管于货架的上层位置：若是以人手进行搬运作业时，人腰部以下的高度用于保管重物或大型物品，而腰部以上的高度则用来保管重量轻的物品或小型物品。对于手段( 2 ) ，( 3 ) 现有仓库都已经实现，本文不进行再次考虑。而手段( 4 )的制定，主要是为了满足货架的稳定性，是货位优化必须满足的前提条件，是货位优化的约束条件。本文将手段( 1 ) 作为实现目标的手段，因此实现提高工作效率这一目标的手段为：存货周转率高的货物放在离出货区近的地方。根据上述分析，画出货位优化问题的目标一手段图，如图2 4 所示。目手图2 - 4 货位优化一目标手段系统图存货周转率高的货物放在离出货区近的地方可以通过货位分区的手段来实现，因此，在指定分区内，最大限度的缩短小车的总行走时间就成了我们系统货位优化的目标之一。综合考虑货架的稳定性和小车的总行走时间，本系统的货位优化问题是一多目标的货位优化问题，本文采用加权法对这一问题进行优1 5基于离散粒子群与模拟退火融合算法的自动小车存取系统货位优化化，详细介绍在5 - 6 试验仿真部分。2 3 货位优化方法的选择货位优化问题属于组合优化问题，组合优化问题的特点是可行解的数量有限。由于可行解数量有限，在理论上，这类问题可以通过简单的枚举法找到最优解，然而在实际情况中通常无法实现。特别是当实际问题的规模很大，可行解的数量非常多的时候更是如此。解决这种问题的主要方法是启发式算法【3 6 1 。启发式算法比较接近于人类的思维方式，易于理解，用这类算法求解组合优化问题在得到最优解的同时也可以得到一些次优解，便于优化人员研究比较。此类算法有：遗传算法、粒子群算法、模拟退火算法等。( 1 ) 遗传算法。遗传算法鲁棒性强，是解决组合优化问题的强有力的工具。遗传算法的显著优点是可以同时搜索空间中的许多点，而不是一个点，因而能够作到全局优化；但是用遗传算法解决组合优化问题时，需要用到选择、交叉和变异等算子，其操作相对较为繁杂。( 2 ) 粒子群算法。粒子群算法是一种基于多点随机搜索的启发式算法，采用多点并行搜索方式，通过粒子间的信息交互，能够快速收敛于解空间中的某一点，粒子群算法的优势在于算法的简洁性，易于实现，没有很多参数需要调整，且不需要梯度信息。粒子群算法是非线性连续优化问题、组合优化问题和混合整数非线性优化问题的有效优化工具。( 3 ) 模拟退火算法。模拟退火算法是一种基于概率的随机搜索优化算法，它是一种有效的全局优化算法，与以往的近似算法相比，模拟退火算法具有描述简单、使用灵活、运用广泛、运行效率高和较少受初始条件限制等特点。由于遗传算法在解决组合优化问题时的操作较为复杂，因此本文不采用其来进行优化。虽然粒子群算法和模拟退火算法操作都比较简单，但是它们都有各自的缺点，粒子群算法容易因为收敛过快而容易陷入局部最优，而模拟退火算法则收敛速度较慢，且优化时间会随着系统规模的扩大和复杂而急剧增加。为了克服粒子群算法与模拟退火算法各自的缺点，本文决定采用粒子群与模拟1 6第二章自动化立体仓库系统及相关货位优化方法退火算法融合算法来进行对货位的优化。2 4 本章小结自动化立体仓库具有节约劳动力，作业迅速准确，提高保管效率，减低物流费用等优越性，因此受到了广泛的重视。它是工厂物流、柔性制造系统和计算机集成制造系统中不可或缺的重要组成部分。本章主要介绍了自动化立体仓库的发展史及它的优点，介绍了传统自动化立体仓库和新型的自动化立体仓库一自动小车存取系统，以及自动化立体仓库货位优化目标的分析和货位优化方法的选择。1 7基于离散粒子群与模拟退火融合算法的自动小车存取系统货位优化3 1 基本粒子群算法第三章粒子群算法3 1 1 算法原理粒子群优化算法p s o 是基于群体的演化算法，其思想来源于人工生命和演化计算理论。k e n n e d y 和e b e r h a r t m 3 对鸟飞行的研究发现，鸟仅仅是追踪它有限数量的邻居，最终的整体结果是整个鸟群好像在一个中心的控制之下，即复杂的全局行为是由简单规则的相互作用引起的。p s o 源于对鸟群捕食行为的研究，一群鸟在随机搜寻食物，如果这个区域里只有一块食物，那么找到食物的最简单有效的策略就是搜寻目前离食物最近的鸟的周围区域。p s o 算法就是从这种模型中得到启示而产生的，并用于解决优化问题。另外，人们通常是以他们自己及他人的经验来作为决策的依据，这就构成了p s o 的一个基本概念。p s o 求解优化问题时，问题的解对应于搜索空间中一只鸟的位置，称这些鸟为“粒子 ( p a r t i c l e ) 。每个粒子都有自己的位置和速度( 决定飞行的方向和距离) ，还有一个被优化函数决定的适应值。各个粒子记忆、追随当前的最优粒子，在解空间中搜索。每次迭代的过程不是完全随机的，如果找到较好解，将