（计算机应用技术专业论文）基于蚁群算法的自动化立体仓库作业调度研究.pdf

摘要 自动化立体仓库( a u t o m a t e ds t o r a g e r e t r ie v a ls y s t e m ，即a s r s ) 是现代物流系 统的重要组成部分。对自动化立体仓库的调度进行优化，可以在不增加设备投资的情况 下减少作业时间，提高仓库的运行效率，是物流领域研究的热点问题。自动化立体仓库 调度优化问题涉及实际的现场问题，没有统一的方法可以解决所有问题。当前国内外所 用的方法大致分为两类，一类着眼于理论的研究和探讨，预先设计了理想的前提，试图 对调度优化给予理论的指导，这类方法的缺点是前提较为理想，不利于实际应用；另一 类是结合工厂的实际，利用仿真方法进行研究，针对实际问题提出优化方案，再升华到 理论层面，这类优化方案的弱点就是应用的适应面较窄。 本文对自动化立体仓库的研究背景、研究现状进行分析后，针对现存研究方法的不 足和自动化立体仓库的实际情况，进行了基于蚁群算法的自动化立体仓库作业调度的研 究，分别对自动化立体仓库中堆垛机拣选作业和输送系统的调度问题进行了研究。 通过对堆垛机拣选作业特点、流程等进行的分析，针对任务数量的不可预测性、货 箱的体积和堆垛机的额定载荷均有限制等实际情况，提出了一个新型自动化立体仓库堆 垛机拣选作业调度优化模型( a r s c o p ) 。在分析了蚁群算法解决自动化立体仓库作业调度 问题的优势后，针对基本蚁群算法( a c a ) 收敛速度慢，容易陷入局部最优发生停滞等缺 点和a r s c o p 模型的特点，提出了基于非定长小窗的自适应蚁群遗传混合算法 ( n f l w s a c g ) 来解决a r s c o p 问题。实验证明，n f l w s a c g 算法解决a r s c o p 问题的性能如收 敛性、解的质量和稳定性均优于a c a 算法。其解的质量稳定，不受任务数量的影响，适 合各种规模的自动化立体仓库使用。 对输送系统调度的优化研究，首先分析了输送系统作业调度的特点和当前研究所存 在的问题，针对输送系统调度的瓶颈堆垛机与输送系统的排序调度问题，提出了堆 垛机与输送系统排序调度优先级因子，进而提出了输送系统调度优化模型( t s o p ) 。将堆 垛机与输送系统的排序调度优先级因子引入到蚁群算法的转移概率公式中，结合粒子群 算法的思想和t s o p 模型的特点，提出了有粒子群特性的动态参数蚁群算法( d p a p a ) 来解 决t s o p 问题。实验证明，d p a p a 算法解决t s o p 问题的综合性能指标优于a c a 算法，具 有良好的收敛性，并且更适合于大规模的自动化立体仓库所使用。 本文由七章组成，第一章介绍了自动化立体仓库调度问题的研究背景、国内外研究 现状，对堆垛机拣选作业、输送系统调度问题进行了概述；第二章提出了堆垛机拣选作 业调度优化模型( a r s c o p ) ；第三章介绍了基本蚁群算法解决a r s c o p 问题的思路；第四 章提出了基于非定长小窗的自适应蚁群遗传混合算法来解决a r s c o p 问题；第五章 提出了堆垛机与输送系统排序调度优先级因子，进而提出了输送系统调度优化模型 ( t s o p ) ；第六章提出了有粒子群特性的动态参数蚁群算法来解决t s o p 问题；第七章是 总结及展望。 关键词：自动化立体仓库蚁群算法堆垛机拣选作业a g v a b s t r a c t 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 ) i sa l li m p o r t a n tc o n s t i t u e n to fm o d e m l o g i s t i c ss y s t e m w i t ht h eo p t i m i z i n go ft a s ks c h e d u l i n gi na s r s ，t a s kt i m ec o u l db e d e c r e a s e da n dt h es y s t e me f f i c i e n c yc o u l db ei m p r o v e dw i t h o u ta d d i n gi n v e s t m e n to f e q u i p m e n t s ot h eo p t i m i z i n go ft a s ks c h e d u l i n gi na s r si sar e s e a r c hf o c u s t h eo p t i m i z i n g o ft a s ks c h e d u l i n gi na s r sr e f e r ss o m ep r a c t i c a lp r o b l e m s ，s ot h e r ei sn ot m i f o r ms o l u t i o nt o s o l v ea l lp r o b l e m s c u r r e n t l y , t h es o l u t i o no ft h eo p t i m i z i n go ft a s ks c h e d u l i n gi na s r s c o u l db ec l a s s i f i e di n t ot w oc a t e g o r i e s ：o n ek i n do fs o l u t i o nf o c u s e so nt h et h e o r e t i c a l r e s e a r c h i tp r e - d e s i g n si d e a lp r e m i s ea n da t t e m p t st oi n s t r u c tt h eo p t i m i z i n go fs c h e d u l i n g 1 1 1 es h o r t c o m i n go ft h i sk i n do fs o l u t i o ni st h ep r e - d e s i g n e dp r e m i s ei st o oi d e a lt ou s ei nt h e p r a c t i c a la p p l i c a t i o n a n o t h e rk i n do fs o l u t i o np u t sf o r w a r do p t i m i z i n gs c h e m ef o rp r a c t i c a l p r o b l e m so ff a c t o r i e s i tc o n d u c t sr e s e a r c hb ys i m u l a t i o nm e t h o d a n dt h e nt h es i m u l a t i o n m e t h o dw i l lu p g r a d et ot h e o r y l i m i t e da p p l i c a t i o nd o m a i ni st h ef l a wo ft h i sl 【i n do fs o l u t i o n i nt h ee s s a y , b a c k g r o u n da n dc u r r e n tr e s e a r c hs t a t u so fa s r si sa n a l y z e df i r s t l y a n d t h e n , r e s e a r c ho nt h et a s ks c h e d u l i n gi na 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 mb a s e do n a n tc o l o n ya l g o r i t h ma c c o r d i n gt od i s a d v a n t a g e so fc u r r e n tr e s e a r c ha n dt h ea c t u a ls i t u a t i o n o fa s r s t h er e s e a r c hi sc o n s i s t e do ft h eo p t i m i z i n go fs t a c k i n gc r a n eo r d e rp i c k i n ga n dt h e o p t i m i z i n go ft h et r a n s p o r t a t i o ns y s t e m a f t e rt h ea n a l y s i so ft h ef l o wa n dc h a r a c t e r i s t i c so fs t a c k i n gc r a n eo r d e rp i c k i n g ， a c c o r d i n g t ot h eu n p r e d i c t a b i l i t yo ft h en u m b e ro ft a s k s ，t h ec o n s t r a i no fc o n t a i n e rc u b a g ea n d t h ec o n s t r a i no fs t a c k i n gc r a n er a t e dl o a d ，an o v e lo p t i m i z i n gs c h e d u l i n gp r o b l e mm o d e lo f 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 ms t a c k i n gc r a n eo r d e rp i c k i n g ( a r s c o p ) i sp u t f o r w a r d t h e n ，a d v a n t a g e so fs o l v i n gt h eo p t i m i z i n go ft a s ks c h e d u l i n gi na s r sb ya n t c o l o n ya l g o r i t h m ( a c a ) a r ee x p l a i n e d t oi m p r o v et h ec o n v e r g e n c et i m eo fa c a ，a v o i d f a l l i n gi nl o c a lb e s ta n de n h a n c et h eq u a l i t yo fs o l u t i o n , an e wn o n - f i x e dl e n g t hl i t t l e w i n d o wb a s e d s e l f - a d a p t i v ea n tc o l o n y - g e n e t i ch y b r i da l g o r i t h m ( n f l w s a c g ) i s p r o p o s e dt os o l v ea r s c o p i nt e r m so fc h a r a c t e r i s t i c so fa r s c o ec o m p a r i n gw i t ha c a ， t h es i m u l a t i o nr e s u l to na r s c o ps h o w st h a tn f l w s a c gh a sb e t t e rp e r f o r m a n c e ，s u c ha s t h ec o n v e r g e n c ep e r f o r m a n c e ，t h eq u a l i t yo fr e s u l t sa n dt h es t a b i l i t y r e g a r d l e s st h en u m b e r o ft a s k s ，r e s u l t so fn f l w s a c gi ss t e a d y a n di tp r o v e st h a tn f l w s a c gc a l lb eu s e di n v a r i o u ss c a l ea s r s i nt h er e s e a r c ha b o u tt h eo p t i m i z i n go ft h et r a n s p o r t a t i o ns y s t e m ，d i s a d v a n t a g e so f c u r r e n tr e s e a r c hs t a t u sa n dt r a i t so fs c h e d u l i n gp r o b l e ma r ee x p l a i n e df i r s t l y a n dt h e nt h e o r d e r i n gs c h e d u l i n gp r i o r i t yf a c t o ro fs t a c k i n gc r a n ea n dt r a n s p o r t a t i o ns y s t e mi sb r o u g h t f o r w a r dt or e s o l v et h eb o t t l e n e c kp r o b l e mt h a tt h eo r d e r i n gs c h e d u l i n gp r o b l e mo fs t a c k i n g c r a n ea n dt r a n s p o r t a t i o ns y s t e m f u r t h e r , an e wo p t i m i z i n gs c h e d u l i n gp r o b l e mm o d e lo f t r a n s p o r t a t i o ns y s t e m ( t s o p ) i sp r o p o s e d 。功eo r d e r i n gs c h e d u l i n gp r i o r i t yf a c t o ro fs t a c k i n g g r a n ea n dt r a n s p o r t a t i o ns y s t e mi su s e di nt h et r a n s i t i o np r o b a b i l i t yf o r m u l ao fa c a c o n s i d e r i n gt r a i t so ft s o pa n dl e a r n i n gc h a r a c t e r i s t i c so fp a r t i c l es w a r mo p t i m i z a t i o n a l g o r i t h m ，a no r i g i n a ld y n a m i cp a r a m e t e r sa n tc o l o n ya l g o r i t h mw i t hp a r t i c l es w a r m c h a r a c t e r i s t i c ( d p a p a ) i sp r e s e n t e dt os e t t l et s o et h es i m u l a t i o nr e s u l ts h o w st h a tt h e c o m p r e h e n s i v ep e r f o r m a n c ei n d i c a t o ro fd p a p ai sb e t t e rt h a na c ai nt s o p a n dt h e d p a p ah a sg o o dc o n v e r g e n c ep e r f o r m a n c e t h er e s u l ta l s op r o v e st h a td p a p ai sm o r e s u i t a b l et ob et l s e di nt h el a r g e s c a l ea s r s t h ee s s a yi sc o n s i s t e do fs e v e nc h a p t e r s i nt h ef i r s tc h a p t e r , t h eb a c k g r o u n da n dc u r r e n t r e s e a r c hs t a t u so fa 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 mi si n t r o d u c , e d a n dt h e nt h e o p t i m i z i n gs c h e d u l i n gp r o b l e mo fs t a c k i n gc r a n eo r d e rp i c k i n ga n dt r a n s p o r t a t i o ns y s t e mi s s u m m a r i z e d 1 1 1 eo p t i m i z i n gs c h e d u l i n gp r o b l e mm o d e lo fa u t o m a t e ds t o r a g ea n dr e t r i e v a l s y s t e ms t a c k i n gc r a n eo r d e rp i c k i n gi sp r o p o s e di nt h es e c o n dc h a p t e r t h ei d e at h a ts o l v e s a r s c o pb ya c ai se x p l a i n e di nt h et h i r dc h a p t e r i nt h ef o u r t hc h a p t e r , n o n - f i x e dl e n g t h l i t t l ew i n d o wb a s e ds e l f - a d a p t i v ea n tc o l o n y - g e n e t i ch y b r i da l g o r i t h mi sp r e s e n t e dt o s o l v ea r s c o ei nt h ef i f t hc h a p t e r , t h eo p t i m i z i n gs c h e d u l i n gp r o b l e mm o d e lo ft h e t r a n s p o r t a t i o ns y s t e m ( t s o p ) i sb r o u g h tf o r w a r d t h e n , d y n a m i cp a r a m e t e r sa n tc o l o n y a l g o r i t h mw i t hp a r t i c l es w a r mc h a r a c t e r i s t i c ( d p a p a ) i sp u tf o r w a r dt os o l v et s o pi nt h e s i x t hc h a p t e r n es u m m a r ya n d e x p e c t a t i o ni ss h o w e di nt h es e v e n t hc h a p t e r k e yw o r d s ：a s r s ，a c a ，s t a c k i n gc r a n e ，o r d e rp i c k i n g ，a g v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取 得的研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得 天津理工大学 或 其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研 究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 学位论文作者签名：办板姆签字日期：如o p 年协月乡f 日 学位论文版权使用授权书 本学位论文作者完全了解 叁盗堡墨盘堂有关保留、使用学位论文 的规定。特授权墨盗堡墨盘堂 可以将学位论文的全部或部分内容编入 有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇编， 以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复本和电子 文件。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：磊妊妁 导师签名： 孑；寥盔 签字日期：知咿年协月；1 日签字日期：知妒年，j 月引日 第一章绪论 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 ) 作为物流系 统的一个核心和枢纽，是物流系统实现物流合理化的关键所在n 1 。自动化立体仓库是在 不直接进行人工处理的情况下能自动存储和取出物料的系统，采用高层货架储存货物， 用起重、装卸、运输机械设备进行货物出库和入库作业的仓库。物流系统的多样性，决 定了自动化立体仓库的多样性，它由4 个主要部分组成：储存结构，也称为料架系统，是 自动化仓库的基础；货物存取机，也称堆垛机，是自动化立体仓库的基本组成部分；输 送设备，是指除货物存取机外，用来运送货物进出库的设备；控制装置，能把仓库的所 有设备有机地组合在一起，形成一个系统，不仅包括设备的控制，而且也包括信息的控 制。图i - i 为某自动化立体仓库的总体构成图乜】： 润 定 赞 攘 区 如瘁 口 口 口 口 口 口 口口 口 口旋 口转 广1 赞 量篓 口 口口 口口攘选台 口口 觯台 图卜1 自动化立体仓库总体构成图 货架区由多排立体货架组成。堆垛机负责货架上货物的存取，在巷道口处各有一出 库台和一入库台，堆垛机把取出的货箱放到出库台，同时又可从入库台上取得货箱放置 相应的货物。分拣系统负责把取出的货物按相应品种和数量分发给在各分拣口等待的相 第一章绪论 应客户，它包括若干个分拣台，每一分拣台又各有一个上包台和一个下包台。输送系统 包括导轨和若干自动导向车( a g v ) ，自动导向车可以从出库台上取得货箱并把它送至分 拣台的上包台，又可以从下包台上取得货箱并把它送回某一入库台，从而完成货物的出 ( 入) 库过程。上述就是自动化立体仓库的基本工作流程。 在第五次国际物流会议上，美国产业界人士明确提出，当前美国全部生产只有5 的 时间用于加工制造，9 5 9 6 的时间则用于搬运、存储、调度等物流过程。企业在降低成本 的压力下，采用自动化立体仓库技术可以最大限度的利用土地资源，加快出入库的速度， 节省物流环节的费用。在我国经济迅速发展的背景下，越来越多的企业意识到自动化立 体仓库技术的重要性，开始大量采用自动化立体仓库。对自动化立体仓库的调度进行优 化，可以在不增加设备投资的前提下，减少作业时间，提高仓库的运行效率，同时它也 是自动化立体仓库技术发展的重要方面，在实际应用中具有十分重大的意义。 自动化立体仓库中，立体货架和堆垛机是重要的组成部分，拣选作业是指堆垛机从 巷道口出发，一次存取若干个货位，然后返回巷道口，并将货箱送到出货台。物资出入 库的效率取决于堆垛机的工作效率，除堆垛机本身的性能参数外，堆垛机的调度是影响 其工作效率的主要因素。在实践中，物流成本占商品最终售价的3 0 ，其中包括配送、 搬运和存储等成本。一般拣选成本约是其他堆叠、装卸和运输等成本总和的9 倍，占物 流搬运成本的绝大部分嘲。因此要降低物流搬运成本，首先应从拣选作业着手改进才能 有事半功倍的效果。按照我国现在的国情，目前大多数的仓储中心仍然属于劳动力密集 型产业，其中与拣选作业直接相关的人力占5 0 以上，而且拣选作业的时间投入也占整 个仓储中心的3 0 9 6 4 0 口1 。因此合理规划拣选作业对于仓储中心运作效率的提高具有决定 性影响，而提高拣选作业效率的关键就是在一定条件下优化拣选路径。因此研究堆垛 机的作业调度问题，对提高自动化立体仓库的效率、降低成本具有非常重要的意义嘲。 在自动化立体仓库中输送系统是连接存储区和分拣系统的纽带，除了特大( 重) 型货 箱由叉车直接进出( 入) 库操作外，其余中小型货物都要通过输送系统运送至分拣台分拣 出库。由于分拣系统的分拣速度和存货区的取货速度比较快，输送系统成了整个仓库 的“瓶颈 。此时多个货箱的出库过程并发进行，其运输顺序对整个仓库的运行效率影 响极大。因此需要对输送系统进行合理调度。 综上所述，对自动化立体仓库进行优化调度，可以在不增加设备投资的前提下，减 少作业时间，提高仓库的运行效率，因此对堆垛机拣选作业以及输送系统的调度进行优 化，将极大的提高自动化立体仓库的作业效率，同时它也是自动化立体仓库技术发展的 重要方面。提高自动化仓库的作业效率，就可以用更小的成本，取得更大的经济效益， 减少人力物力消耗，减低企业成本，加快货物的流动，在实际应用中具有重要的意义。 1 2 自动化立体仓库作业调度问题概述 所谓作业调度，主要是指调配资源、合理安排作业顺序，在满足现有条件的情况下， 使运行成本最小。调度的质量可用不同的目标函数( 如考虑时间、效率、费用等目标) 来 度量。寻找合理的调度方案的过程就是对任务的作业顺序进行组合优化的过程，所以调 第一章绪论 度问题也称为排序问题。自动化立体仓库的调度是针对一项可分解的工作( 如仓库状 态) ，探讨在尽可能满足约束条件( 如最小延迟、最大前提、协调作业、资源情况) 的前 提下，通过控制货物出入库流程和调整堆垛机和运输系统的工作顺序，以获得运行的最 小时间或成本的最优化。实现调度的最优化有利于提高自动化立体仓库的利用率，最大 限度提高企业的生产效率，减低成本。自动化立体仓库中堆垛机拣选作业的调度、输送 系统的调度、倒库作业的调度等都属于调度问题。其中，堆垛机拣选作业的调度和输送 系统的调度是自动化立体仓库作业调度的核心问题，是提高自动化立体仓库工作效率的 关键，也是本文研究的主要内容。 1 2 1 堆垛机拣选作业调度优化 堆垛机拣选作业是指堆垛机从巷道口出发，一次存取若干个货位，然后返回巷道口， 将货箱送到出货台。拣选作业的调度问题实际上就是堆垛机拣选作业的路径优化问题。 堆垛机的调度是影响自动化立体仓库工作效率的主要因素，因此优化堆垛机拣选作业将 极大的提高自动化立体仓库的作业效率。另外，堆垛机在进行拣选取货或者送货的时候， 有多种拣选路径可以选择，这是一个典型的n p 难题，不存在有效的多项式解法盯1 ，是具 有典型性的组合优化问题，因此对该问题的研究不仅具有重大的实际意义而且具有很高 的理论价值。 堆垛机拣选作业调度优化主要包含以下两方面的问题： ( 1 ) 如何快速的寻找到一条最短的拣选路径。在堆垛机各项参数的限制下，快速的 找到一条最短或者较短的拣选路径是提高堆垛机工作效率的关键问题。 ( 2 ) 在拣选的货物的重量和体积不超过堆垛机的承载能力和拣选货箱的体积时，在 保证路径较短的情况下，如何尽量减少堆垛机的工作次数。减少堆垛机的工作次数，就 可以减少堆垛机的停、开机次数，从而减少能源的损耗。 1 2 2 输送系统调度优化 在自动化立体仓库中输送系统是连接存储区和分拣系统的纽带，除了特大( 重) 型货 箱由叉车直接进出( 入) 库操作外，其余中小型货物都要通过输送系统运送至分拣台分拣 出库。输送系统一般包括水平导轨和若干辆在导轨上前后运行的自动导向小车( a g v ) ， a g v 在导轨上前后运行，可到达每一个巷道口的出( 入) 货台取货或卸货。堆垛机按照出 库指令从不同的货位陆续运出货箱到本巷道的出库台，输送系统检测各出库台的状态信 号，若有货箱则a g v 小车运行至该出库台处，取过货箱并将其送至某个分拣上包台，同 时原出库台恢复原位；待输送系统检测到分拣完毕信号后，a g v d x 车运行至缓存器的货 箱出口，取过货箱并把其送回原巷道的入库台，完成该货箱的一个出库周期。 输送系统的调度问题一般有以下几个问题： ( 1 ) 怎样解决各个巷道出( 入) 货台的货物取( 送) 的优先级排序问题，即堆垛机 输送系统的排序调度问题。由于分拣系统的分拣速度和存货区的取货速度比较快，多个 货箱的出库过程并发进行，输送系统就成了整个仓库的“瓶颈”，若调度不合理，巷道 会发生堵塞，造成效率下降和资源浪费。 第一章绪论 ( 2 ) 怎样才能选择一个最优路径，使得所有a g v j 、车走得总路程最短、时间最少、 能耗最小。对输送系统进行优化研究，为a g v 选择最佳的任务集，具有重要的现实意义。 1 3 国内外研究现状与分析 1 3 1 国内外研究现状 自动化立体仓库作为现代物流的关键部分，很大程度上反映了企业的发展状况，国 内外研究机构对自动化立体仓库的调度问题做了大量的研究，取得了不少研究成果。 自动化仓库系统的调度是针对一项可分解的工作，探讨在尽可能满足约束条件的前 提下，通过控制出入库货物流程和调整堆垛机、a g v j 、车的工作顺序，以获得运行的最 小时间或成本的最优化。在理论研究中，自动化仓库的调度问题实际上就是排序问题或 者资源分配问题。实际的调度问题有复杂性、动态随机性、多目标等特点，随着目标的 增加，己证明调度问题是一个完全n p 难题。国内外的学者针对自动化立体仓库的调度 问题进行了大量的研究。山东大学以及上海交通大学等许多国内研究者对自动化立体仓 库的调度问题进行了深入的研究陋。1 钔。田国会等提出了影响仓库运行效率的若干调度优 化问题，分别采用p e t r i 网、时态逻辑、模拟退火、遗传算法、神经网络等方法，并结 合计算机仿真技术进行了研究，他们还针对自动化立体仓库中拣选作业要求速度快、效 率高的特点，分析和研究了一种新型改进l i nk e r n i n g h a n ( l k ) 算法，并将其应用于固定 货架的拣选优化问题中h 5 1 7 1 ；周奇才提出立体仓库运行控制的优化准则，分析确定自动 化立体仓库系统控制的优化控制数学模型，并运用有关原理，提出堆垛机及出入库系统 货箱运行的优化控制程序等n 蝴1 。国外学者对于自动化立体仓库调度所进行的研究非常 广泛，从多个方面对自动化立体仓库的调度问题进行了研究。美国学者l i n n r 在研究 自动化立体仓库的过程中，提出将专家系统的思想应用到自动化立体仓库的控制中，引 起了人们的极大关注口。w h i t l e y 等人对应用于自动化立体仓库调度的启发式方法和遗 传算法进行了比较晗幻；n o r b e r ta s c h e u e 等针对在线的非对称t s p 问题，即自动化立体仓 库中的作业调度问题提出采用简单的启发式规则优化的软件包，以堆垛机的空载时间最 短为目标，以s n i 公司的六条自动化仓库的实测数据为基础，对自动化立体仓库作业调 度进行了仿真，得到了显著的效果，可以用于在线的实时控制乜引；b o y e r 等人对自动化 仓库的运行时间模型进行了分析心制；b y u n g - k i m 等针对一个实际的工厂自动化仓库提出 了基于模型的智能a g e n t 技术，考虑在两种极端的分等级和不分等级情况下的情况，实 体( 货物和零件) 和资源( 存储面积和拣选顺序) 作为具有合作特点功能的智能体，以便 于实现个体和系统整体的目标，这些智能体所采取的一种动态实时的作业调度和别的决 策基于制定这些决策时的环境乜引；e a e l s a y e d 在每个调度命令进行执行时间控制的情 况下，对命令的执行过程进行了研究口们。 自动化立体仓库调度优化问题由于涉及实际的现场问题，非常复杂，没有统一的方 法可以解决所有的问题，但是对于现有的方法进行分析，大致分为两类，一类是着眼于 理论的研究和探讨，试图对调度优化给予理论的指导，预先设计了比较理想的前提，例 第一章绪论 如上面所提到的b y u n g k i m 等提出的基于模型的智能a g e n t 技术；另一类是结合工厂的 实际f 矾驯，如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 ) 系统，利用仿真方法或者别的理论 进行研究，针对实际问题提出优化方案，然后升华到理论的层面。第一类方法存在的问 题是预先设计的前提较为理想，模型过于抽象，采用的算法多为单一算法，从理论到实 际应用还有一定的距离。第二类方法的弱点是优化结果的适应面较窄。 1 3 2 研究现状分析 目前，国内外针对堆垛机拣选作业的研究大多是将拣选作业抽象转化为t s p 问题 艄羽，然后采用各种算法求解。这些方法在一定程度上提高了堆垛机拣选作业的效率， 但是，该类数学模型忽略了堆垛机的额定载荷问题、周转货箱的容量限制等实际问题， 将堆垛机假设成可携带无限多的货物进出巷道，因此该数学模型只能应用于部分系统。 目前我国不断投入使用的自动化立体仓库仅依赖硬件来提高运行效率，拣选作业没能采 用合适的优化算法，也成为制约堆垛机效率提高的主要因素。 同样，针对输送系统的调度研究通常将a g v 小车的路径优化问题转化为v r p 问题( 车 辆路径问题) ，忽略了a g v 小车的载重量和运送货箱总体积安全值等实际问题。对堆垛 机与输送系统的排序问题研究不足，容易造成巷道堵塞，导致自动化立体仓库的效率下 降和资源的浪费。 随着各种新的相关学科与优化技术的建立与发展，在调度领域也出现了许多新的优 化方法1 ，比如神经网络、模拟退火算法、遗传算法、禁忌搜索法、蚁群算法、弹性网 算法、路径代数算法、动态规划、分支定界法等，使得调度问题的研究向多元化方向发 展。但任何一种算法都有其自身的缺陷。神经网络算法能求得问题的局部最优解，用于 求解小规模问题时，优于启发式算法；当问题规模较大时，解的质量不如采用启发式算 法求得的解：弹性网算法作为一种求解旅行商问题的递推算法，可用于求解各种规模的 问题，但当问题的规模较大时，所需的计算时间较长1 。路径代数算法对同一问题，计 算时间较其它几种启发式算法明显增长，用于求解小规模问题时，一般可得到较好的解， 当问题的规模较大时，解的质量有明显下降。遗传算法往往出现早熟和收敛性能差等缺 点，仅依赖解的适应度值来实现对解空间的搜索，对所求解的约束条件的描述能力也比 较差，在实际中，要找到一个合适的交叉算子也是很困难的。模拟退火算法对系统中的 反馈信息利用不够，当求解到一定范围时往往做大量无为的冗余迭代。如果将两种或更 多种不同的算法结合起来，取长补短，相信会取得更好的效果。 通过上述对国内外研究现状的分析，可以看出当前对自动化立体仓库作业调度问题 的研究有以下问题： ( 1 ) 把堆垛机拣选作业问题简单转换为t s p 问题，将堆垛机假设成可携带无限多的 货物进出巷道，忽略了任务数量的不确定性、堆垛机的额定载荷、周转货箱的容量限制 等实际问题。 ( 2 ) 同样，对a g v 小车的研究也忽略了其载重量等实际问题，对堆垛机与输送系统 的排序问题研究不足，影响自动化立体仓库的工作效率。 ( 3 ) 我国不断投入使用的自动化仓库仅依赖硬件来提高运行效率，作业调度没能采 第一章绪论 用合适的优化算法，成为制约自动化立体仓库效率提高的主要问题。 本文将针对上述问题逐一进行研究。 1 4 本文主要研究工作、创新点 本文对自动化立体仓库的研究背景、研究现状进行分析后，针对现存研究方法的不 足和自动化立体仓库的实际情况，进行了基于蚁群算法的自动化立体仓库作业调度的研 究。本课题的研究主要分两部分： ( 1 ) 对堆垛机拣选作业的优化，提高拣选作业的工作效率。根据堆垛机拣选作业的 特点结合任务数量的不确定性、拣选货箱的容积限制、堆垛机的额定载荷等实际情况， 提出了一种新型自动化立体仓库堆垛机拣选作业调度优化模型( a r s c o p ) ，解决堆垛机拣 选作业的路径优化问题。针对自动化立体仓库拣选作业要求速度快、效率高的特点，采 用基于非定长小窗的自适应蚁群遗传混合算法( n f l w s a c g ) 求解a r s c o p 问题，在提 高求解质量的同时加快了算法的求解速度。 ( 2 ) 对输送系统进行优化。综合“最小积压”、“先来先服务”和“用户需求 这3 方面的因素，提出了堆垛机与输送系统的排序调度优先级因子的概念，来解决堆垛机与 输送系统的排序调度问题，尽量避免巷道堵塞的发生。对输送系统运行流程、特点进行 分析，建立输送系统调度优化模型( t s o p ) 。采用有粒子群特性的动态参数蚁群算法 ( d p a p a ) 对a g v 小车的运行路径进行优化，使小车走的路程最短、时间最少、能耗最小。 本课题的创新点： ( 1 ) 通过对堆垛机拣选作业流程、特点的分析，提出了一个新型的自动化立体仓库 堆垛机拣选作业调度优化模型( a r s c o p ) ，该模型充分考虑了实际情况中任务数量的不确 定性、堆垛机的额定载荷和拣选货箱的容积问题，以求出一条最短的拣选路径为目标， 从而减少了堆垛机工作的总时间和能源的消耗。 ( 2 ) 通过对基本蚁群算法不足的分析，针对a r s c o p 模型的特点，结合遗传算法思 想提出了基于非定长小窗的自适应蚁群遗传混合算法( n f l w s a c g ) 来解决a r s c o p 问 题，快速、高效的对堆垛机的拣选作业进行调度，从而提高拣选作业的工作效率。 ( 3 ) 经过对堆垛机与输送系统的排序调度问题的分析，综合“最小积压 、“先来先 服务”和“用户需求这3 方面的因素，提出堆垛机与输送系统的排序调度优先级因子 的概念，来解决堆垛机与输送系统的排序调度问题，避免巷道发生堵塞。 ( 4 ) 通过对输送系统运行流程和特点的分析，在考虑了运送货箱总体积安全值、a g v 载重量等实际情况的基础上，提出了输送系统调度优化模型( t s o p ) ，在不违反运送货箱 总体积安全值和a g v 载重量的前提下，使a g v 行驶路线的总距离最小，从而加快输送系 统整体的工作效率。 ( 5 ) 将堆垛机与输送系统的排序调度优先级因子引入蚁群算法转移概率公式中，结 合粒子群算法多信息指导的思想和t s o p 模型的特点，提出了一种新型的有粒子群特性 的动态参数蚁群算法( d p a p a ) 来解决t s o p 问题，对输送系统的a g v 小车进行合理调度， 从而提高自动化立体仓库的整体工作效率。 第一章绪论 1 5 本文的结构 本文由七章组成，在对自动化立体仓库作业调度问题的概述与分析的基础之上，对 堆垛机拣选作业和输送系统的作业调度进行了研究，分别建立了相应的数学模型，采用 改进后的蚁群算法进行求解。本文的结构如下： 第一章：对课题的背景、内容、研究意义、国内外研究现状进行了阐述和分析。 第二章：通过对堆垛机拣选作业研究现状的分析，发现了其中的不足和存在的问题， 根据堆垛机拣选作业的流程和特点，提出了堆垛机拣选作业调度优化模型( a r s c o p ) 。 第三章：通过分析蚁群算法的特点，阐明了蚁群算法解决自动化立体仓库作业调度 问题的优势，应用基本蚁群算法对堆垛机拣选作业调度问题进行优化。 第四章：针对堆垛机拣选作业的特点，分析了基本蚁群算法解决堆垛机拣选作业调 度优化问题的不足，提出了基于非定长小窗的自适应蚁群遗传混合算法来解决 a r s c o p 问题。通过实验，对基本蚁群算法和基于非定长小窗的自适应蚁群遗传混合 算法解决a r s c o p 问题的性能进行了对比。 第五章：对输送系统的特点和存在问题进行了分析，针对输送系统调度的瓶颈问题 堆垛机与输送系统的排序调度问题，提出了堆垛机与输送系统排序调度优先级因 子，进而建立了输送系统调度优化模型( t s o p ) 。 第六章：基于输送系统调度优化模型( t s o p ) 的特点，借鉴了粒子群算法的思想，提 出了有粒子群特性的动态参数蚁群算法解决t s o p 问题。通过实验，对基本蚁群算法和 有粒子群特性的动态参数蚁群算法解决输送系统调度优化问题的性能进行了对比。 第七章：总结了本文的主要工作和所得结论，分析了其中有待进一步研究的问题， 明确了今后的研究方向。 第二章堆垛机拣选作业调度优化模型 第二章堆垛机拣选作业调度优化模型 2 1 堆垛机拣选作业特点和存在问题分析 2 1 1 堆垛机拣选作业概述 自动化立体仓库中，货架并排排列，每两组货架的中间设有一条巷道，供巷道堆垛 机行驶作业。每排货架分为若干纵列和横排，构成货格存放货物。巷道口有出库台和入 库台。堆垛机可同时在水平方向和垂直方向独立运动。堆垛机拣选作业的操作流程通常 是由仓库管理控制系统根据需求下达拣选作业任务表单，然后堆垛机从入库台提取空的 拣选货箱，从巷道口出发，按照任务表单上的拣选任务，依次从一个已完成的货位点到 下一个将要进行拣选的货位点。当任务表单上的所有任务全部完成或拣选货箱已放满或 货物的重量已达到堆垛机的额定载荷时，堆垛机就回到巷道口的出库台处，将货物卸下 测。作业流程如图2 - 1 所示： 图2 1 堆垛机拣选作业流程 第一章堆垛机拣选作业润应优化模型 堆垛机的运行轨迹如图2 - 2 、2 - 3 所示 i 圈圈圈圈蜀习圈i 固固囹丑珏目目、 l 臻帆2 贷位点， 轨薯t 图2 - 2 堆垛机运行俯视圉 ：田田跚= 口 l 豳自珥独 2 1 2 堆垛机拣选作业特点分析 圈23 堆垛机运行侧视图 经过对堆