（机械电子工程专业论文）基于蚁群算法的自动化仓库作业调度研究.pdf

哈尔滨工业大学工学硕士学位论文 摘要 物流是社会经济发展的命脉之一，由于世界各国企业问的竞争日趋激烈， 依靠生产领域技术的发展来获取更高利润的速度趋于稳定，所以物流领域技术 的进步成为获取更高利润新的源泉。自动化仓库是物流领域的一个关键设备， 一般由固定货架和旋转货架两大部分来存放货物。所以在自动化仓库中对固定 货架、旋转货架拣选路径优化问题的研究将极大地提高自动化仓库的作业效 率。在自动化仓库中，输送系统是自动化仓库的重要组成部分，承担着货物运 输的任务，由于固定货架和旋转货架的作业速度很快，输送系统可能成为整个 系统的速度“瓶颈”。因此，对自动化仓库的输送系统的调度作业进行优化， 可以避免或者减轻“瓶颈效应”，提高自动化仓库的整体运行效率。 蚁群算法( a c a ：a n tc o l o n ya l g o r i t h m ) 是一种新型的随机优化算法，是意 大利学者在2 0 世纪9 0 年代初首先提出来的，在解决经典组合优化问题中取得 了较好的结果，引起了国内外学者的广泛关注。本文使用蚁群算法和最大最小 蚁群算法( m m a s a ：m a x m i na n ts y s t e ma l g o r i t h m ) 研究了固定货架、旋转货 架拣选路径优化及输送系统的调度优化问题。仿真结果表明，蚁群算法可取得 较好结果。此外还分析了单拣选台水平旋转货架系统的工作过程，利用蚁群算 法，取得了满意的结果。并对相对比较复杂的输送系统提出了一个简单的输送 系统模型，利用蚁群算法，对其优化调度问题进行了初步探讨。 关键词自动化仓库；固定货架；旋转货架；蚁群算法；调度优化 哈尔滨丁业大学t 学硕+ 学位论文 a b s t r a c t l o g i s t i c s l so n eo ft h el i f el i n e so fe c o n o m i cd e v e l o p m e n t b e c a u s et h e c o m p e t i t i o ni sm o r ed r a s t i ca m o n g t h ee n t e r p r i s e so fm a n yc o u n t r i e si nt h ew o r l d ，t h e s p e e do fo b t a i n i n gm o r ep r o f i t st h a td e p e n d e d o nt h ed e v e l o p m e n to ft h et e c h n o l o g y i nt h ep r o d u c et e n d st ob es t a b l e s ot h el o g i s t i ct e c h n o l o g yi sb e c o m i n gt h en e w s o u r c eo fo b t a i n i n gh i g h e rp r o f i ta u t o m a t e dw a r e h o u s et h a ti st h ek e ye q u i p m e n ti n t h el o g i s t i c s ，t h ef i x e d - s h e l fa n dc a r o u s e la r eu s e dt os t o r et h em a t e r i a li na a u t o m a t e dw a r e h o u s e t h er e s e a r c ho nt h eo r d e rp i c k i n gr o u t eo p t i m i z a t i o no f f i x e d s h e l fa n dc a r o u s e lc a l l g r e a t l y i n c r e a s et h ee f f i c i e n c yo ft h ea u t o m a t e d w a r e h o u s e t h et r a n s p o r t a t i o ns y s t e mi st h ei m p o r t a n tp a r to faa u t o m a t e dw a r e h o u s e ， a n di su s e dt ot r a n s p o r tt h eg o o d s b e c a u s et h ef i x e d s h e l fa n dc a r o u s e lw o r kq u i c k l y , t h et r a n s p o r t a t i o ns y s t e mi sp o s s i b l et ob e c o m et h es p e e db o t t l e n e c ko ft h et o t a l s y s t e m h e n c e ，i fw eo p t i m i z et h es c h e d u l i n gi nt h et r a n s p o r t a t i o n ，t h eb o t t l e n e c k e f f e c tc a nb ee l i m i n a t e do rl i g h t e n ，t h u sw ec a ni m p r o v et h et o t a lr u n n i n ge f f i c i e n c y o faa u t o m a t e dw a r e h o u s e a n tc o l o n ya l g o r i t h mi san o v e lr a n d o mo p t i m i z a t i o na l g o r i t h mt h a ti sp u t f o r w a r db yt h es c h o l a ro fi t a l yi nt h ef i r s tp l a c ea t1 9 9 1 i th a sg a i nt h eb e t t e rr e s u l t i nt h es o l v i n gt h ec l a s s i cc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m s ，a n dh a s r e c e i v e d m u c ha t t e n t i o no fm a n yd o m e s t i ca n do v e r s e a ss c h o l a r s a n tc o l o n ya l g o r i t h ma n d m a x - m i na n ts y s t e ma l g o r i t h ma r eu s e dt os t u d yt h eo r d e rp i c k i n gr o u t e o p t i m i z a t i o ni nf i x e d - s h e l fa n dc a r o u s e l ，a n da l s oa r eu s e dt os t u d yt h es c h e d u l i n g o p t i m i z a t i o ni nt h et r a n s p o r t a t i o ns y s t e mi nt h i sa r t i c l e t h es i m u l a t i o nr e s u l t ss h o w t h a ta n tc o l o n ya l g o r i t h mc a na c q u i r et h eb e t t e rr e s u l t w ea l s oa n a l y s i st h ew o r k p r o c e s si nt h es i n g l e p i c k e r - h o r i z o n t a l c a r o u s e l ，a n do b t a i nab e t t e rr e s u l tb a s e do n t h ea n tc o l o n ya l g o r i t h m w eg i v eas i m p l em o d e lo f t h et r a n s p o r t a t i o nf o rt h em o r e c o m p l i c a t e dt r a n s p o r t a t i o ns y s t e ma n ds t u d yt h ev e h i c l es c h e d u l i n gw i t ht h e a n t c o l o n ya l g o r i t h me l e m e n t a r i l y k e y w o r d s a u t o m a t e dw a r e h o u s e ，f i x e d s h e l f , c a r o u s e l ，a n tc o l o n ya l g o r i t h m s c h e d u l i n go p t i m i z a t i o n 1 1 引言 第1 章绪论 在物流学众多的研究领域中，工业企业物流一直是被关注的焦点，这不仅 由于物流组织的好坏直接决定着企业生产过程是否能够顺利进行，决定着企业 产品的价值和使用价值是否能够顺利实现，而且企业的物流费用已经成为生产 成本和流通成本的重要组成部分。在这种情况下，企业将主要精力花在降低生 产成本上是“不得要领”的，明智而有效的方法是改善物流。因此，以降低物 流成本、减少资金占有、缩短生产周期为主要目标的物流合理化 ( r a t i o n a l i z a t i o n ) 被称为企业的“第三方利润源泉”，被放到企业发展的战略高 度来加以研究和实施。而自动化立体仓库作为物流系统的一个枢纽和核心，是 物流系统实现物流合理化的关键所在。通常，一种产品要从原材料做成成 品，再把成品作为商品，送到消费者手中，需经过两个基本物流环节：前者是 物流生产过程( 如：加工流水线、自动生产线) ，后者是把商品送到消费者手中 的物流流通过程。基于上述两个基本物流环节，目前自动化立体仓库主要有两 大应用领域：其一是各种自动化生产线中的在线立体仓库系统( 如 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 ) 中的在线立库系统) ：其二二是各 种物资配送中心( 如超市配货中心等) 。 虽然自有生产以来就有物流，但是物流作为一项专门的学问引起人们重 视，作为一个专门的学科被研究，却远远滞后于生产制造。生产物流是现代生 产的重要组成部分，随着生产力水平的日益提高，生产物流系统中所蕴含的巨 大潜力越来越引起人们的注意。因此在提高加工制造设备本身能力与效益的同 时，挖掘物流的潜力，提高生产系统的总体效益已经成为生产现代化的重要标 志之一。随着国内制造业的迅猛发展，竞争目趋激烈，降低成本的压力逐渐增 大，而物流作为有效降低产品成本的有效措施，被越来越多的企业和政府重 视，作为物流业重要设施的自动化仓库也得到了高度重视。 哈尔滨t 业大学t 学颂士学位论文 1 2 自动化仓库概述 1 2 1 自动化仓库的定义 自动化仓库( a u t o m a t e dw a r e h o u s e ) 是指在不直接进行人工处理的情况下， 能自动地存储和取出物料的系统，它由多层货架、能在巷道内的任何货位存储 和取出货物的搬运车以及计算机控制和通信系统组成。它的特点在于以高层立 体货架为主要标志，以成套的先进搬运设备为基础，以先进的计算机控制技术 为主要手段，高效地利用空间、时间和人力进行出入库处理。由于它具有节约 劳动力，作业迅速准确，可以提高保管效率，降低物流费用等优越性，日益受 到人们越来越多的重视。从广义上来讲，对自动化仓库的总体要求是：在要求 的时间内，在准确的位置，按准确的顺序与方位，为准确的用户提供准确品种 和准确数量的物资j 。 1 2 2 自动化仓库的构成 一个完整的自动化立体仓库系统，是一个可对集装单元货物实现自动化保 管和计算机管理的智能仓库。物流系统的多样性决定了自动化仓库的多样性， 但是自动化仓库基本组成部分是一致的。其主要组成部分如下： ( 1 ) 储存结构存放货物的主要设备，是自动化仓库的基础，一般与托 盘、存储货箱配合适应，借助于巷道堆垛机进行物资存放。高层货架的制造一 般有两种形式：整体式一货架与建筑物合而为一；分离式一货架与建筑物分 丌，相互独立。货架上货物的存放形式多采用同一规格的集装单元。 ( 2 ) 货物存取机也称堆垛起重机，是自动化仓库的基本组成部分，来回 运行在货架巷道内，自动存取货物，并把货物放到出入库的机械设备。通常一 条巷道配置一台堆垛机，进出货物不太频繁的仓库也可几条巷道共用一台堆垛 机。 ( 3 ) 出入库输送系统是指除堆垛起重机外，用来运送货物进出库的设备 或者是结构更为复杂的，能把堆垛起藿机和其他设备的操作连接起来成为一种 更为完善的输送设备系统。 ( 4 ) 管理控制系统这是高层货架仓库实现自动化作业的核心，具有管 理、监控和控制三个功能。能对自动化仓库里面的设备及信息进行控制，并做 出合适的决策。管理功能由控制中心的主计算机管理系统承担：监控功能由高 晴尔滨工业大学工学硕士学位论文 层仓库和托运系统的监控系统承担：控制功能由堆垛机及搬运系统的控制系统 承担刚】。 1 2 3 自动化仓库的分类 自动化仓库的分类方式有以下几种： ( 1 ) 按建筑形式分为整体式和分离式两种。 ( 2 ) 按货物存取形式分为单元货架式，移动货架式和拣选货架式。 ( 3 ) 按货架构造形式分为单元货格式、贯通式、循环式仓库三种。 ( 4 ) 按自动化仓库在实际当中所起的作用分为生产性仓库和流通性仓库两 种。 ( 5 ) 按自动化仓库与生产联接的紧密程度分为独立型、半紧密型和紧密型 仓库三种。 当然，自动化仓库还有其它分类方式，可见文献【4 。 1 2 4 自动化仓库的发展历史及现状 1 9 5 0 年美国e i d u p o u t d en e m o u r s 公司制成手动控制堆垛机进行仓库内堆 垛作业。1 9 5 9 年美国国际纸张公司，在阿拉巴马州仓库中采用了司机操纵巷道 式堆垛起重机，克服了桥式起重机缺点。19 6 2 年西德将电子计算机技术应用于 这种仓库，建成了世界上第一座自动化仓库。它一出现，即成为众人注目的新 技术。 日本在自动化仓库技术发展中具有重要位置。6 0 年代中期，日本经济持续 发展，物流量进一步增大，要保证工业生产持续上升和物流畅通，客观上要求 扩大仓库、海湾、公路等物流设备。当时在r 本物流费用占商品价格的1 5 左 右，节约这笔开支的潜力很大，在这种情况下，日本于1 9 6 5 年建成国内第一 座自动化仓库，1 9 6 9 年开始进行大规模建设，并向欧洲、美国派出了许多考察 团，对自动化仓库进行了深入的研究，逐步明确认识到：自动化仓库对于国土 狭窄的日本来讲是发展物流事业的必由之路。于是1 9 7 4 年前后出现了建设自 动化仓库的热潮，一年期间竟建起了三四百座。目前，日本已成为自动化数量 最多的国家之一。 8 0 年代自动化仓库向着合理化、系统化、综合化和社会化方向发展。在国 际上，特别最近l o 年，自动化仓库技术进步非常显著，无论在生产、流通、 交通运输和物流企业都谋求在更广泛的范围内，各方配合、共同协作，以达到 整体的物流合理化。比如：实行叉车托盘化，包装标准集装箱化和海陆联合直 达运输，点到点的配送业务等。由于高度机械化、自动化和高服务标准的物流 管理作业，降低了物流成本，增加了企业利润。这样，除同本、美国、德国以 外，瑞士、意大利、英国、法国、瑞典、波兰等国在自动化仓库行业也有长足 的发展 3 1 。 我国的自动化仓库的发展是从2 0 世纪7 0 年代开始的【2 j 。自从1 9 8 0 年由 北京机械工业自动化研究所等单位研制成功的我国第一座自动化立体仓库在北 京汽车制造厂投产后，自动化仓库的研究和应用在我国得到了迅速的发展。掘 不完全统计，目前我国己建成的自动化仓库近三百座。其中全自动化的立体仓 库有3 0 多个。目前，我国有能力承接建造自动化仓库的单位就有十几家。随 着我国的经济和贸易与世界的联系日益密切，自动化仓库系统的发展也日益趋 向国际化方向靠拢。 通过引进外国著名公司的先进技术，消化和吸收，开发研制出具有自主知 识产权的自动化仓库系统，并且在许多方面都取得了很大的进步。例如，苏州 富士达仓储成套设备有限公司，它原来是苏州起重机械厂的一个事业部，1 9 8 6 年通过引进德国西马克( s i e m a g ) 自动化立体仓库技术，通过消化和吸收，承 接了上海宝钢二期工程自动化仓库的设计、建设、制造、安装和调试任务， 1 9 9 1 年荣获国家重大技术装备成果一等奖，在1 9 9 2 年开发研制成功了岔道式 转轨有轨巷道堆垛机。之后，又在自动化立体仓库中成功地采用了远红外通 讯、扩频通讯、电力载波通讯、条形码识别、实时显示等技术。在1 9 9 9 年中 科院合肥智能研究所和安徽叉车集团共同开发研制成功了国内首台集信息交 互、智能控制、传感器技术、网络技术等多项现代化高新技术于一体的机电液 一体化大型自动搬运车辆。 国内许多科研院所都在立体仓库计算机控制系统的集成化技术方面进行了 大量的研究，并取得了一定的成果。自动化仓库的计算机控制系统涉及两部分 主要功能，库存信息管理和货箱运输控制。采用计算机网络、数据库、多种语 言编程，数据通讯和人机接口等技术，实现了出入库平台同时进行出入操作， 能跟踪显示堆垛机及滚道上货箱传送的实际情况，具有避免故障发生和人一机 交互处理故障的能力，将出入库控制和库存管理有机地结合起来，成为一个完 整的管理控制系统。我国的自动化仓库技术己实现了与其他信息决策系统的集 成，正在做智能控制和模糊控制的研究工作。 尽管己经取得了这些非常显著的成绩，但是和国外的自动化仓库相比较， 还有相当大的差距，主要表现在以下几个方面： 哈尔滨t 业大学丁学硕十学位论文 ( 1 ) 发展速度慢。目前我们国家自动化仓库的数量和生产能力还不能满足今 后我国经济发展的需要。 但) 设备品种和规格较少。 f 3 ) 应用先进控制技术和驱动技术的还不多。 独立自主开发研究和创新的能力还不够。 ( 5 ) 在调度策略研究和应用方而显得比较滞后。 1 2 5 自动化仓库的发展阶段 美国学者j a w h i t e 根据自动化技术在仓储领域( 包括立体仓库) 中的应 用，把自动化仓库的发展分为五个阶段：即人工仓储阶段、机械化仓储阶段、 自动化仓储阶段、集成化仓储阶段和智能自动化仓储阶段。在2 0 世纪9 0 年代 后期以及2 1 世纪的若干年内，智能自动化仓储将是自动化仓库技术的主要发 展方向和目标。以下对五个阶段作简单的阐述。 第一阶段，人工仓储阶段。在这一阶段当中，物资的输送、存储、管理和 控制主要靠人工实现，实时性和直观性是较明显的优点。人工仓储技术在初期 设备投资的经济指标也具有优越性。 第二阶段，机械化仓储阶段。物料可以通过各式各样的输送带、工业输送 车、机械手、吊车、堆垛机和升降机来移动和搬运，用货架、托盘和移动式货 架存储物料，通过人工操作机械存取设备，用限位开关，螺旋机械制动和机械 监视器等控制设备的运行，机械化满足了人们对速度、精度、高度、重量、重 复存取和搬运方面的要求。 第三阶段，自动化仓储技术阶段。自动化技术对仓储技术的发展起到了重 要的促进作用。2 0 世纪5 0 年代末6 0 年代初，相继研制和采用了自动导引小车 f a g v - a u t o m a t i cg u i d ev e h i c l e ) 、自动货架、自动存取机器人、自动识别和自动 分拣等系统。2 0 世纪7 0 年代和8 0 年代，旋转式立体货架、移动式货架、巷道 式堆垛机和其它搬运设备都加入了自动化控制的行列，但这时只是各个设备的 局部自动化并各自独立应用，被称为“自动化孤岛”。随着计算机技术的发 展，自动化仓库研究的工作重点逐渐转向物资的控制和管理的实时、协调和一 体化，信息自动化技术逐渐成为仓储自动化技术的核心。计算机之间、数据采 集点之间、机械设备的控制器之间以及它们与主计算机之间的通信可以及时高 效地汇总信息，仓库计算机及时地记录订货和到货时间，显示库存量，计划人 员可以方便地做出供货决策，他们知道目前工厂正在生产什么、需要订什么货 哈尔滨丁业大学工学硕士学位论文 物、什么时间发出什么品种、规格的货物、管理人员随时掌握货源及客户的需 求。在这一阶段信息技术的应用已成为仓储技术的重要支柱。 第四阶段，集成自动化仓储技术阶段。在2 0 世纪7 0 年代末和8 0 年代， 自动化技术被越来越多地用到生产和分配领域，显然，“自动化孤岛”需要集 成化，于是便形成了“集成系统”的概念。在集成化系统中，整个系统的有机 协作，使总体效益和生产的应变能力大大超过各部分独立效益的总和。 集成化仓库技术作为计算机集成制造系统( c i m s c o m p u t e ri n t e g r a t e d m a n u f a c t u r i n gs y s t e m ) d o 物资存储的中心受到人们的重视。虽然人们在8 0 年代 已经注意到系统集成化，但至今在我国已建成的集成化仓储系统还不多。在集 成化系统里包括了人、设备和控制系统，而前面所叙述的三个阶段是它的基 础。7 0 年代初期，我国开始研究采用巷道式堆垛机的立体仓库。 第五阶段，智能自动化仓储技术。人工智能技术的发展使自动化技术向更 高级的阶段一智能自动化方向发展。现在，智能自动化仓储技术还处在初级发 展阶段，到将来仓储技术的智能化将具有更加广阔的应用前景【5 j 。 目前对于自动化仓库国内外的叫法不一致。有人称“立体仓库”、“高层货 架仓库”、“高位仓库”、“货架系统”、“自动化仓库”、“自动化立体仓库”。这 些名称的出现与人们对于仓库的认识及自动化发展过程相关，本文中统称为 “自动化仓库”。 1 34 自动化仓库拣选路径优化问题及研究现状 1 3 1 自动化仓库拣选路径优化问题 所谓调度( s c h e d u l i n g ) ，主要是指用于调配资源、合理安排作业顺序，在 满足现有条件下，使运行成本最小。调度的质量可用不同的目标函数( 如考虑 时间、效率、费用等目标) 来度量。寻找合理的调度方案的过程就是对任务的 作业顺序进行组合优化的过程。所以调度问题也称为排序( s e q u e n c i n g ) 问题。 调度问题实际上是一个优化问题，自动化立体仓库中固定货架的拣选作业、输 送小车和堆垛机调度、倒库作业的调度以及旋转货架中的拣选作业都属于调度 问题。实现最优的调度有利于提高自动化仓库的利用率，最大限度地提高企业 的生产率。自动化仓库的调度通常可以借鉴流水车间调度、作业车间调度、机 器调度和运输问题的调度 2 1 。 哈尔滨工业大学丁学硕士学位论文 1 3 2 自动化仓库拣选路径优化问题研究现状 许多学者对调度问题做了大量的研究，取得了不少的研究成果。自动化仓 库系统的调度是针对一项可分解的工作( 如仓库状态) ，探讨在尽可能满足约束 条件( 如搬运量、最小延迟、最大前提、协调作业、资源情况) 的前提下，通过 控制出入库物流程和调整堆垛机和运输车顺序，以获得运行的最小时间或成本 的最优化( 即最小延迟l a t e n e s s 或最小花费c o s t ) 。在理论研究中，自动化仓库 的调度问题实际上就是排序问题或者资源分配问题。实际的调度问题有复杂 性、动态随机性、多目标等特点，随着目标的增加，已经证明调度将变成一个 完全的n p ( n o n d e t e n n i n i s t i cp o l y n o m i a l ) 难题。山东大学以及上海交通大学等 许多国内研究者对自动化仓库的调度问题进行了深入的研究【6 0 2 1 。 一般的调度问题都是对于具体生产环境中复杂的、动态的、多目标的调度 问题的一种抽象和简化，因而一个调度算法可以通过其如何表述这些复杂性进 行分类。由于实际生产环境是千差万别的，那么一个调度算法就应该根据其是 否能适合对应的生产环境的重要特征进行评估。在对调度问题进行研究的方法 上，最初是集中在整数规划、仿真和简单的规则上，这些方法不是调度结果不 理想就是难以解决复杂的问题。随着各种新的相关学科与优化技术的建立与发 展，在调度领域也出现了许多新的优化方法【l 孤，比如神经网络、模拟退火法、 遗传算法、禁忌搜索法、蚁群算法等，使得调度问题的研究向多元化方向发 展。国外学者对于自动化仓库调度所进行的研究非常广泛，从多个方面对自动 化仓库调度问题进行了研究。w h i t l e y 等人对应用于自动化仓库调度的启发式 方法和遗传算法进行了比较1 1 4 1 ，n o r b e na s c h e u e r 等针对在线的非对称t s p 问 题即自动化仓库中的作业调度问题提出采用简单的启发式规则所优化软件包， 以堆垛机的空载时间最短为目标，以s n i 公司的六条自动化仓库的实测数据为 基础，进行了对自动化仓库作业调度的仿真，得到了显著的效果，可以用于在 线的实时控制旧，b o y e r 等人对自动化仓库的运行时问模型进行了分析l i ， b y u n g k i m 等针对一个实际的工厂自动化仓库提出了使用基于模型的智能 a g e n t 技术，考虑在两种极端的分等级和不分等级情况下的情况，实体( 货物和 零件) 和资源( 存储面积和拣选顺序) 作为具有合作特点功能的智能体，以便于 实现个体和系统整体的目标。这些智能体所采取的一种动态实时的作业调度和 别的决策基于制定这些决策时的环境【j 7 】。b a e t s a y e d 在每个调度命令进行执 行时间控制的情况下，对命令的执行过程进行了研究”。 目前，自动化立体仓库利用固定货架和旋转货架来存放货位，其中立体固 喻尔滨t 业大学工学硕士学位论文 定货架占了相当大的比重，旋转货架是自动化立体仓库的最新发展，特别适合 小件及微小件物品的存放i l 。 固定货架和旋转货架拣选作业问题与实际中许多其它的组合优化问题具有 一定的代表性，是具有典型性的组合优化问题，因此对该问题的研究不仅具有 重大的实际工程意义而且具有很高的理论价值。固定货架和旋转货架拣选作业 问题非常复杂，它们与旅行商问题( t s p , t r a v e l i n gs a l e s m a np r o b l e m ) - - 样，属 于n p 难题，不存在有效的多项式解法。 对于固定货架拣选作业问题的优化算法有启发式算法、神经网络算法、弹 性网算法和路径代数算法等等，其中启发式算法又分为邻近启发式、最邻近插 入启发式、几何启发式等三种算法，它们规则简单、易于理解，所需计算时间 较少，所得解在多数情况下尚能满足一定要求，但有时候的质量较差，这些方 法适用于对计算时间要求较高同时求解规模较大的问题。神经网络算法能求得 问题的局部最优解，用于求解小规模问题，当问题规模较大时，解的质量不如 采用启发式算法求得的解。弹性网算法作为一种求解旅行商问题的递推算法， 可用于求解各种规模的问题，一般来说，解的性能优于启发式算法；但当问题 的规模较大时，所需的计算时问较长。路径代数算法和几种启发式算法相比， 对同一问题，计算时间较后者明显增长，同时前者求解小规模问题时，一般可 以得到较好的解，当问题的规模较大时，解的质量明显下降。 针对自动化仓库固定货架系统中拣选优化作业的特点，田国会等设计了一 种新型高效混合遗传算法，显著改善了原有遗传算法能力，在利用 h o p f i e l d t a n k 神经网络的快速局部搜索能力的同时，又利用了遗传算法的全局 寻优特性，有效地获得全局优化的拣选路径，仿真结果表明算法能够满足待拣 选货位点数目在较大范围内变动的要求【2 。针对自动化仓库中固定货架拣选作 业要求速度快、效率高的特点，田伟分析和研究了一种新型改进l i n k e m i g h a n ( l k ) 算法，并将其应用于固定货架拣选优化问题。仿真实验结果表 明，该算法能够大大降低时间和空间的计算复杂度，快速、稳定地找出最优 解，满足了多次作业时待拣选货物数目在较大范围内变动的要求，尤其是满足 了中大规模作业的要求1 2 lj 。 对于旋转货架拣选作业问题的优化算法有动态规划、启发式算法、模拟退 火算法和遗传算法等等，其中动态规划分支定界法和分支定界法只用来解决单 层水平旋转货架，并且两种算法都以问题的复杂性为代价，原因在于指数计算 时间和问题规模的约束，它们用来解决小规模问题是可行的，而对于大规模问 题则需要浪费大量的计算时间。要得到有效的启发式算法，必须对要解决的问 哈尔滨工业大学工学硕士学位论文 题领域的知识具有深入的了解，同时启发式算法的针对性较强，只能解决具体 的问题，缺乏通用性。模拟退火是一种随机优化方法，为了保证能收敛到全局 最优解。降温过程必须非常缓慢。张攀等对单伺服机水平分层旋转货架进行分 析，建立了数学模型，给出了解决单伺服机分层旋转货架拣选作业优化的一种 混合遗传算法【2 2 ，2 ”。林家恒对双伺服机旋转货架拣选问题提出虚拟点方法，将 其化为单伺服机拣选问题进行建模1 2 。n l i t v a k 等人对旋转货架系统进行了研 究，提出了一种新的启发式算法，来减少拣选时间【2 ”】，h a r kh w a n g 等人对 有两个伺服机的旋转货架系统进行了研究1 2 ”。 田国会，常发亮等还对自动化仓库中输送系统的调度问题运用p e t r i 网对 输送系统进行建模、仿真【2 8 _ 3 0 】。 总的看来，自动化仓库调度优化的问题由于涉及实际的现场问题，非常复 杂，没有统一的方法可以解决所有的问题，但是对于所有的方法进行分析，大 致分为两类，一类是着眼于理论的研究和探讨，试图对调度优化给予理论的指 导，预先设计了比较理想的前提，如将固定货架的拣选问题简化为平面的t s p 问题；另一类是结合工厂的实际 3 1 , 3 2 1 ，如f m s 伍l e x i b l em a n u f a c t u r i n gs y s t e m ) 系统，利用仿真方法或者别的理论进行研究，针对实际问题提出优化方案，然 后升华到理论的层面，当然这些优化的结果适应面较窄。 1 4 课题研究的目的、意义和内容 1 4 1 课题研究的目的 随着自动化技术、信息技术等新技术在自动化仓库上的推广应用，自动化 仓库已经发生了深刻的变化，各种新的设备层出不穷，极大地提高了自动化仓 库的功能，拓展了自动化仓库的应用范围。相对于自动化仓库在硬件方面的突 飞猛进，自动化仓库在软件方面的发展就比较逊色，尤其是能够应用于实时控 制的、高效的调度算法一直是研究的重点。本课题基于近年来兴起的仿生算 法一蚁群算法，对自动化仓库的作业调度进行理论上的研究和探讨，力图得 到有效的优化调度方法。 1 4 2 课题研究的意义 由于人口密集，土地资源有限，竞争日趋激烈，在降低成本的压力下，采 哈尔滨工业大学t 学硕士学位论文 用自动化仓库技术可以最大限度的利用土地资源，加快出入库的速度，节省物 流环节的费用。在我国经济迅速发展的背景下，越来越多的企业意识到自动化 仓库技术的重要性，开始大量采用自动化仓库。对自动化立体仓库进行优化调 度，可以在不增加设备投资的情况下，减少作业时间，大大提高仓库的运行效 率，因此对固定货架和旋转货架拣选作业问题以及输送系统的作业调度进行优 化，将极大的提高自动化仓库的作业效率，同时它是自动化仓库技术发展的重 要方面，在实际应用中具有十分重大的意义。另外和自动化仓库良好效果形成 对比的是它的巨大的投资，提高自动化仓库的作业效率，就可以用更小的成 本，取得更大的经济效益。 1 4 3 课题研究的内容 本论文从自动化仓库的作业调度研究现状出发，以自动化仓库中的三类作 业调度问题进行研究，将蚁群算法应用在自动化仓库的作业调度，为自动化仓 库的作业调度提供了一种新思路，并利用m a t l a b 的强大运算功能和图像功 能，编写m a t l a b 的算法程序，验证蚁群算法的优化效果。 本课题研究的内容可归结为： ( 1 ) 固定货架拣选路径优化问题的分析； ( 2 ) 旋转货架拣选路径优化问题的分析； ( 3 ) 建立一个输送系统的简化模型，利用蚁群算法对固定货架、旋转货架 和输送系统的作业调度问题进行研究。 ( 4 ) 编写m a t l a b 程序，验证算法的效果。 哈尔滨工业大学工学硕士学位论文 2 1 蚁群算法简介 2 1 1 引言 第2 章蚁群算法 研究群居性昆虫行为的科学家发现，昆虫在群落一级上的合作基本上是自 组织的，在许多场合中尽管这些合作可能很简单，但它们却可以解决许多复杂 的问题。蚁群算法就是利用群体智能解决组合优化问题的典型例子。蚁群算法 ( a n tc o l o n ya l g o r i t h m ，a c a ) 是由意大利学者m d o r i g o ，v m a n i e z z o ， a c o l o m i 等人在2 0 世纪9 0 年代初首先提出来的。它是继模拟退火、遗传算 法、禁忌搜索算法、人工神经网络算法等启发式搜索算法以后的又一种应用于 组合优化问题的启发式搜索算法。关于蚁群算法的研究虽然刚刚起步，但是这 些研究己显示蚁群算法在求解复杂的优化问题( 特别是离散优化问题) 方面的一 些优越性，证明它是一种很有发展前景的方法。蚁群算法通过候选解组成的群 体的进化过程来寻求最优解，该过程包含两个基本阶段：适应阶段和协同工作 阶段。在适应阶段，各候选解根据积累的信息不断调整自身结构；在协同工作 阶段，候选解之间通过信息交流，以期产生性能更好的解1 3 ”j 。 如图2 1 ，为g o s s 在1 9 8 9 年m j ，d e n e u b o r g 于1 9 9 0 年使用阿根廷蚂蚁所 进行的实验，观察蚂蚁从蚁穴到食物源，然后返回的过程。 图2 - 1g o s s 使用阿根廷蚂蚁进行试验 f i 9 2 1g o s sd i dt h ee x p e r i m e n tw i t ht h ea r g e n t i n ea n t 哈尔滨工业大学工学硕士学位论文 g o s s 在研究过程中发现： ( 1 ) 蚂蚁倾向于选择从蚁穴到食物源间最短的路径： ( 2 ) 蚂蚁释放信息素( p h e r o m o n e ) ，并会沿着有更高信息素的路径前进，进 行间接通信： ( 3 ) 信息素在最短的路径上积聚： 基于上面的实验，意大利学者m d o r i g o ，v m a n i e z z o ，a c o l o m i 等人在上世 纪9 0 年代初提出了蚁群算法( a c a ) 1 3 6 4 1 】。蚁群算法不仅能够智能搜索、全局 优化，丽且具有稳健性( 鲁棒性) 、f 反馈、分布式计算、易于其它算法相结合 等特点。利用正反馈原理，可以加快进化过程；分布式计算使孩算法易于并行 实现，个体之间不断进行信息交流和传递，有利于找到较好的解，不容易陷入 局部最优；该算法易与多种启发式算法结合，可改善算法的性能，由于鲁棒性 强，故在基本蚊群算法模型基础上进行修改，便可用于其它问题。因此，蚁群 算法的问世为诸多领域解决复杂优化问题提供了有力的工具。 m d o r i g o 等人将蚁群算法先后应用于旅行商问题，资源二次分配问题等经 典优化问题，得到了较好的效果。蚁群算法在动态环境下也表现出高度的灵活 性和健壮性，如其在电信路由控制方面的应用被认为是目前较好的算法之一。 此外，蚁群任务分工、打扫蚁巢，分类蚁卵等行为也启发了相应的协作和聚类 算法。 2 。1 。2 蚁群算法的基本原理 蚁群系统本来是生物学家为更好揭示昆虫的交互作用而提出的一种昆虫自 组织模式。尽管建立这种模式的初衷是为了帮助人们去理解这类昆虫的复杂行 为，但是数学及计算机方面的专家把这种超越生物本事的模型转化成了一项有 用的优化和控制算法蚁群算法，也称蚁群系统( a n t c o l o n ) , s y s t e m ，a c s ) 口”。 其原理可大致描述如下：蚂蚁属于群居昆虫，个体行为极其简单，而群体 行为却非常复杂。相互协作的蚁群蚂蚁很容易找到从蚁巢到食物源的最短路 径，而单个蚂蚁则不能。 此外，蚂蚁还能够适应环境的变化，例如在蚁群的运动路线上突然出现障 碍物时，它们能够很快地重新找到最优路径。人们通过大量的研究发现，蚂蚁 个体之间是通过在其所经过的路上留下一种可称之为“信息素”( p h e r o m o n e ) 的 物质来进行信息传递的。随后的蚂蚁遇到信息素时，不仅能检测出该物质的存 在以及量的多少，而且可根据信息素的浓度来指导自己对前进方向的选择。同 时，该物质随着时间的推移会逐渐挥发掉，于是路径的长短及该路径上通过蚂 哈尔滨工业大学工学硕士学位论文 蚁的多少就对残余信息素的强度产生影响，反过来信息素的强弱又指导着其他 蚂蚁的行动方向。因此，某一路径上走过的蚂蚁越多，则后来者选择该路径的 概率就越大。这就构成了蚂蚁群体行为表现出一种信息正反馈的现象。蚂蚁个 体之间就是通过这种信息交流达到快捷搜索到食物源的目的。 下面以图2 2 来表示蚁群算法的基本原理。 e 1 0 d 2 l d = 0 5 h c 局s b l a 曲 回卜 1 芗。 。，涎8 磊。 h 岫 固卜 1 碧饕地 ，。逮髟蛐 。 图2 - 2 蚁群算法的基本原理 f i g2 - 2t h eb a s i cp r i n c i p l eo f a n tc o l o n ya l g o r i t h m m d o r i g o 等人提出蚁群算法时，针对不同的信息素更新方式，提出了三种 算法，即a n t - d e n s i t y ，a n t - q u a n t i t y ，a n t - c y c l e ，经过对这三种算法的研究 和比较，发现a n t - c y c l e 算法可以得到更好的解。因此以后的蚁群算法均指 a n t - c y c l e 算法。 2 1 3 基本蚁群算法的算法模型 为了便于理解，通过蚁群算法来求解平面上n 个城市的t s p l ，n l 表示城市序号) ，以此来说明蚁群算法的具体实现步骤。 问题，可以对此模型稍作修改便可应用 4 2 】。 给定一个有n 个城市的t s p 问题，人工蚂蚁数量为m ， m = 缸( f ) 忙t 式中m 是蚂蚁的总数量 问题( o ， 对于其他 ( 2 1 ) 哈尔滨工业大学工学硕士学位论文 包u ) 表示在第i 个城市的蚂蚁数量 吐，= 【( t x ，) 2 + ( y i y j ) 2 2 ( 2 - 2 ) z ，表示在平面的两点i 和j 之间的最短距离，即两点之间的直线距离； 0 0 + 1 ) = p r u ( t ) + a r 。( r ，f + 1 ) ( 2 - 3 ) 式中 z 0 0 + 1 ) 表示在t + 1 时刻路径d 上信息素强度； p 是信息素的挥发系数； a r f ( t ，f + 1 ) = 苟o ，f + 1 ) 是所有蚂蚁在时刻t 和什1 之l 1 3 z 空i j 上 释放的信息素强度； rn 露( f ) ： 芳 如果第k 个蚂蚁经过路径j ( 2 _ 4 ) 【0 否则 蹦归粤塑丛巫 ( 2 _ 5 ) 【勺( f ) 】“【( f ) r 式中，p 分别表示蚂蚁在运动过程中所积累的信息素及启发因子在蚂蚁旋 转路径中所起的作用； = 1 一，表示可见度，即局部启发值，一般在t s p 问题中表示为两点 之间距离的倒数； p f ，表示从城市i 转移到城市j 的概率； 则算法可表示如下： 1 初始化，设t = o ；设路径q 上的信息素初始值r u ( t ) ，在每个城市i 放置6 ( f ) 只蚂蚁；对任意城市i ，j ，设a r 口( t ，+ ”) = 0 ； 2 重复直至禁忌表t a b u l i s t 满为止 ( 1 ) f o r i = lt o n d o f o r k = lt o 鱼( f ) d o 依据公式( 2 5 ) 选择下一步要转移的城市k ，然后把k 插入到禁忌表t a b u l i s t 中； ( 2 ) 根据公式( 2 4 ) 计算露( ，f + h ) ； ( 3 ) 计算勺( f ，f + n ) = 呓( f ，f + n ) ； ( 4 ) 根据公式( 2 3 ) 和( 2 5 ) 计算勺o + n ) 和岛( f ) 的新值 哈尔滨工业大学t 学硕士学位论文 3 储存发现的最短路径，然后清空禁忌表t a b u l i s t ； 4 如果不满足中止条件 设t - - t + n ，对每个城市设f ( t ，t + ”) = 0 ，返回步骤2 否则打印最短路径，中止算法【3 6 1 。 上面所说的中止条件是满足固定的循环次数或者是所求解进化的趋势不明 显。 2 2 蚁群算法的发展 自从1 9 9 1 年m d o r i g o 等人首先提出蚁群算法以来，吸引了许多研究人员 对该算法进行研究，并成功地运用于解决组合优化问题，如：t s p ， q a p ( q u a d r a t i c a s s i g n m e n tp r o b l e m ) 问题。蚁群算法可以用于解决许多组合优化 问题，只要能做到用一个图表来阐述将要解决的问题，能定义一种正反馈过程 ( 如t s p 问题中的残留信息) ，问题结构本身能提供解题用的启发式信息( 如t s p 问题中城市问的距离) ，约束机制的建立( 如t s p 问题中己访问城市的列表) 。几 年前，a c o ( a