仓库管理_自动化仓储系统agv调度研究与实现论文

分类号：T P 3 9 1 密级：学号：2 0 1 0 1 2 7 7 9 硕士学位论文 蝴目： 自动化仓储系统A G V 调度研究与实现 S t u d ya n d R e a l i z a t i o no f A G VS c h e d u l i n gi nA u t o m a t i c S t o r a g e R e t r i e v a lS y s t e m 学院名 专业名 指导教 合作导 称理盐物速巫塞生! 坠 称物流工程 师昱耀堡 师 2 0 1 3 年0 4 月侣日 原创性声明 2 3 3 1 9 9 7IY 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何 其他个人或集体己经发表或撰写过的科研成果。对本文的研究作出重要贡 献的个人和集体，均己在文中以明确方式标明。本声明的法律责任由本人 承担。 论文作者签名：鲻 日期：翌! ! ：堇：婴 关于学位论文使用授权的声明 本人同意学校保留或向国家有关部门或机构送交论文的印刷件和电子 版，允许论文被查阅和借阅；本人授权山东大学可以将本学位论文的全部 或部分内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手 段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：篓盘! 因导师签名 山东大学硕士学位论文 目录 摘要I A B S T R A C T I I I 第1 章绪论1 1 1 课题背景及意义1 1 2 自动化仓储系统A G V 调度文献综述3 1 3 研究内容和结构安排4 第2 章算法相关理论7 2 1 粒子群优化算法7 2 2 离散粒子群优化算法8 2 3 本章小结9 第3 章A G V 调度系统功能分析与设计1 l 3 1A G V 控制系统简介l l 3 2A G V 调度系统功能设计与调度逻辑1 4 3 3 数据交互与功能模块逻辑图18 3 3 1 数据交互一l8 3 3 2 功能模块逻辑图2 0 3 4A G V 系统工作方式2 2 3 5 本章小结一2 4 第4 章A G V 调度问题建模与分析2 5 4 1 单A G V 调度问题建模与分析2 5 4 1 1 问题描述与假设2 5 4 1 2 单A G V 调度问题建模2 7 4 2 多A G V 调度问题建模与分析2 8 4 2 1 问题描述与假设2 8 4 2 2 多A G V 调度问题建模2 9 4 3 本章小结3 0 第5 章A G V 调度问题求解算法与仿真3 1 5 1 求解A G V 调度问题的粒子群算法3 1 山东大学硕士学位论文 5 1 1 单A G V 调度算法基本步骤3 l 5 1 2 多A G V 调度算法基本步骤一3 2 5 2 实例仿真3 3 5 2 1 单A G V 调度仿真3 7 5 2 2 多A G V 调度仿真3 8 5 3 多A G V 的避障问题研究3 9 5 4 本章小结4 1 第6 章总结与展望一4 3 附录多A G V 调度粒子群算法实现4 5 参考文献5 7 致谢6 1 山东大学硕士学位论文 C o N T E N T S A B S T R A C T I E N G L I S HA B S T R A C T I I I C h a p t e r1 I n t r o d u c t i o n 1 1 1R e s e a r c hB a c k g r o u n d 1 1 2R e s e a r c hS t a t u sa tH o m ea n dA b r o a d 3 1 3C o n t r i b u t i o no f t h eR e s e a r c ha n dF r a m e w o r k 4 C h a p t e r2B a c k g r o u n dT h e o r y 7 2 1P a r t i c l es w a r l no p t i m i z a t i o n 7 2 2D i s c r e t ep a r t i c l es w a r mo p t i m i z a t i o n 8 2 3C h a p t e rS u m m a r y 9 C h a p t e r3A n a l y s i sa n dd e s i g no f A G Vs c h e d u l i n gs y s t e m 1 1 3 1B r i e fi n t r o d u c t i o nt oA G Vc o n t r o ls y s t e m 11 3 2F u n c t i o nd e s i g na n ds c h e d u l i n gl o g i co f A G Vs c h e d u l i n gs y s t e m 1 4 3 3D a t ae x c h a n g ea n dl o g i cd i a g r a mo ff u n c t i o nm o d u l e 18 3 3 1D a t ae x c h a n g e 1 8 3 3 2L o g i cd i a g r a mo ff u n c t i o nm o d u l e 2 0 3 4O p e r a t i o nm o d eo f A G V s y s t e m 2 2 3 5C h a p t e rS u m m a r y 2 4 C h a p t e r4M o d e l i n ga n da n a l y s i so f A G Vs c h e d u l i n gp r o b l e m 2 5 4 1M o d e l i n ga n da n a l y s i so fs i n g l eA G V s c h e d u l i n gp r o b l e m 2 5 4 1 1P r o b l e md e s c r i p t i o na n dh y p o t h e s i s 2 5 4 1 2M o d e l i n go fs i n g l eA G Vs c h e d u l i n gp r o b l e m 2 7 4 2M o d e l i n ga n da n a l y s i so fm u l t i A G Vs c h e d u l i n gp r o b l e m 2 8 4 2 1P r o b l e md e s c r i p t i o na n dh y p o t h e s i s 2 8 4 2 2M o d e l i n go fm u l t i A G Vs c h e d u l i n gp r o b l e m 2 9 4 3C h a p t e rS u m m a r y 3 0 C h a t e r 5A l g o r i t h ma n dS i m u l a t i o no f A G Vs c h e d u l i n gp r o b l e m 31 5 1P a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h mf o rA G Vs c h e d u l i n gp r o b l e m 31 I I I 山东大学硕士学位论文 5 11B a s i cs t e p so f s i n g l eA G Vs c h e d u l i n ga l g o r i t h m 一31 5 1 2B a s i cs t e p so fm u l t i - A G Vs c h e d u l i n ga l g o r i t h m 3 2 5 2S i m u l a t i o n e x a m p l e s 一3 3 5 2 1 S c h e d u l i n gs i m u l a t i o no fs i n g l eA G V 3 7 5 2 2S c h e d u l i n gs i m u l a t i o no f m u l t i A G V 3 8 5 3S t u d yo na v o i d a n c eo b s t a c l eA G V 3 9 5 4C h a p t e rS u m m a r y 4 1 C h a p t e r6C o n c l u t i o na n dF u t u r eW o r k 4 3 A p p e n d i x 4 5 R e f e r e n c e s 5 7 A c k n o w l e d g e m e n t s 6 1 山东大学硕十学位论文 摘要 当前国内对A G V 的需求呈井喷之势，除了传统A G V 使用量最多的汽车、烟 草等行业，在其他行业中的应用也明显增加。由于行业的特殊性，某些企业需要 采用A G V 来实现搬运相关的作业，在实际应用过程中，由于考虑到成本因素，现 阶段国内中小企业大多选用的A G V 自主控制能力较写蜀，需要通过集中控制，实现 其有效地作业。在这一过程中易出现调度不当以及车辆碰撞等一系列的问题，因 此如何实现A G V 的有效调度便成为一个亟待解决的问题。 目前对于仅使用A G V 执行搬运作业的自动化仓储系统中A G V 的调度问题研 究较少。因此本文针对这一现状，提出了“规划前置，提前调整”的离线解决办 法。即在整批任务执行前，提前规划好A G V 的行驶路线及任务分派。首先把每项 任务( 从装载到卸载) 当作一个占用时间的任务点，对于使用单A G V 进行调度的 情况，将问题归结为T S P 问题求解，进而求解出任务的执行顺序，也同时求出了 任务执行的最短路径。对于多A G V 的调度问题，借助于解决占用式多车辆路径问 题和短板效应的思想，在一批任务下达后，完成全部任务的时间长短取决于耗时 最长的那一辆，因此以最短时间完成全部任务为目标时，通过对任务分派的优化， 使得所有A G V 中耗时最长的A G V 用时尽量少，于是完成全部任务的时间也就相 应减少。这样便实现了在系统内A G V 数量一定的情况下，在最短时间内完成整批 任务的目标，进而实现了对多A G V 行驶路径的规划。由于考虑调度的时效性，采 用收敛速度相对较快的粒子群算法，并通过采用适当的离散策略，使其适用于本 文问题的求解。然后，针对求解方案中多A G V 路径规划时可能出现的冲突问题， 提出了借助类似于甘特图的逻辑思想，解决了路段冲突和路段交叉问题。最后， 将最终调度方案以路径列表的形式存储到交通管理模块，实现了任务的预调度。 在预调度之后，开始指派A G V 根据任务列表及路径列表执行任务。由于前置规划 耗时少，能够很好地满足企业的实际需求。 为验证方法的有效性，本文进行相应的仿真实验。实验主要分成两个部分： 对于实际问题中的任务分别在单A G V 和多A G V 的情况下进行测试，测试结果表 明在单A G V 的情况下，运用本文的方法可以实现在路径代价尽量小的情况下任务 执行路径的优化和任务的排序。对于多A G V 的测试结果表明，本文所采用的研究 方法能够有效地实现在最短时间内完成全部任务的目标，并实现多A G V 系统的任 山东大学硕士学位论文 务均衡分配。 最后，本文对于解决A G V 调度问题的方法进行了总结与展望，并给出了进一 步的研究方向。 H 关键词：A G V 调度；离散粒子群算法；T S P 问题；最短时间；优化 山东大学硕士学位论文 A B S T R A C T C u r r e n t l yd o m e s t i cd e m a n d sf o rA G Va r eb o o m i n g ，i na d d i t i o nt ot h et r a d i t i o n a l A G Vu s a g ei nt o b a c c oa n do t h e ri n d u s t r i e s ，t h eu s a g ei no t h e ri n d u s t r i e si sa l s o i n c r e a s i n g B e c a u s eo f t h ep a r t i c u l a r i t yo fs o m ei n d u s t r i e s ，s e v e r a le n t e r p r i s e sn e e dt o a d o p tA G V f o rw o r k sr e l a t e dt oc a r r y , i nt h ea c t u a la p p l i c a t i o np r o c e s s ，c o n s i d e r i n gt h e f a c t o ro fc o s t , s m a l la n dm e d i u m - s i z e dd o m e s t i ce n t e r p r i s e sm o s t l yu s et h i sl ( i n do f A G V , w h i c hh a sl o wi n d e p e n d e n tc o n t r o la b i l i t ya n dd e p e n do nc e n t r a l i z e dc o n t r o l s y s t e m I nt h i sp r o c e s sas e r i e so fp r o b l e m sh a p p e n e db e c a u s eo fi m p r o p e rs c h e d u l i n g a n dv e h i c l ec o l l i s i o n , S Oh o wt or e a l i z ee f f i c i e n ts c h e d u l i n go ft h eA G Vh a sb e c o m ea n u r g e n tp r o b l e m A tp r e s e n t ，t h e r ei sr a r er e s e a r c ho nd i s p a t c ho fA G Vi nt h ea u t o m a t e ds t o r a g ea n d r e t r i e v a ls y s t e mw h i c ho n l yu s eA G Vf o rw o r k sr e l a t e dt oc a r r y I nv i e wo ft h i s s i t u a t i o n , t h i sa r t i c l ep u t sf o r w a r dt h eo f f - l i n es o l u t i o no fe xa n t ef o r e c a s t i n ga n d a d j u s t i n gb e f o r eh a p p e n i n g F i r s t ，e a c ht a s k ( f r o ml o a d i n gt ou n l o a d i n g ) i sc o n s i d e r e d a sat a s k W h e nt h e r ei so n l yo n eA G V , t h ep r o b l e mc o m e sd o w nt oT S P p r o b l e m ，t h e n w ec a l c u l a t et h ee x e c u t i o no r d e ro ft a s k s ，a n da tt h es a m et i m et h es h o r t e s tp a t hi s c a l c u l a t e d F o rt h es c h e d u l i n gp r o b l e mo fm u l t i p l eA G V s ，w eu s et h em e a n so fs o l v i n g o c c u p i e dm u l t i p l e - v e h i c l er o u t i n gp r o b l e ma n dt h es h o r tb o a r de f f e c tt h o u g h t W h e na n u m b e ro ft a s k sa r eg i v e n , t h et i m eo fc o m p l e t i n ga l lt a s k sd e p e n d so nt h eA G Vw h i c h t a k e st h el o n g e s tt i m e ，t h e r e f o r et h es h o r t e s tt i m et oc o m p l e t ea l lt a s k sa st h eg o a l ， t h r o u g ht h eo p t i m i z a t i o no ft h et a s ka s s i g n m e n t , b ym a k i n gt h el o n g e s tt i m ew h i c h A G Vc o s ta sl i t t l ea sp o s s i b l e ，t h ew h o l et i m ec o m p l e t i n ga l lt a s k si sr e d u c e d a c c o r d i n g l y F i n a l l yt h eg o a lo fc o m p l e t i n ga l lb a t c h e so ft a s k si nt h es h o r t e s tt i m ea n d t h em u l t i p l e - A G Vr o u t ep l a n n i n ga r ea c h i e v e di nt h ec a s eo fc e r t a i nA G V si nt h e A S R S C o n s i d e r i n gt h et i m e l i n e s so fs c h e d u l i n g ，w ec h o o s et h ep a r t i c l es w a r m a l g o r i t h m ，w h i c hc o n v e r g e sr e l a t i v e l yf a s t , t h e nu s et h ed i s c r e t es t r a t e g i e sa p p r o p r i a t e l y t om a k ei ts u i t a b l ef o rt h es o l u t i o no fO u rp r o b l e m s S e c o n d l y , t or e s o l v et h ec o n f l i c t s a p p e a r e do nt h em u l t i - A G Vp a t hi nt h es c h e m ew eh a v eg o t , w ep u tf o r w a r dt h el o g i c a l t h i n k i n gw h i c hi ss i m i l a rt ot h eG a n t tc h a r t ，a i m i n ga ts o l v i n gt h ep r o b l e mo fc o n f l i c t s a n dr o a d - C R O S Ss e c t i o n F i n a l l y , w ep u tt h ef i n a ls c h e d u l i n gs c h e m et ot h et r a f n c m a n a g e m e n tm o d u l eb ym e a n so ft h ep a t hl i s tf o rs t o r a g e ，a n dr e a l i z et h et a s ko f p r e d i c t i o n A f t e rp r i o rf o r e c a s t i n g ，w e s t a r t a p p o i n t i n gA G Vt op e r f o r mat a s k I l l 山东大学硕十学位论文 a c c o r d i n gt ot h et a s kl i s ta n dt h el i s to fp a t h s P r e d i c t i o nc o s t sal i t t l et i m e ，w h i c hc a n w e l lm e e tt h ea c t u a ln e e d so fe n t e r p r i s e s T ov e n f yt h e v a l i d i t y o ft h em e t h o d , t h i sp a p e rm a k e ss o m es i m u l a t i o n e x p e r i m e n t s W bt e s to u rs o l u t i o ni nt h e s ee x p e r i m e n t sw h i l eu s i n gs i n g l eA G V a n d m u l t i p l eA G V s ，a n dt h er e s u l t ss h o wt h a ti ns i n g l e - A G Vc a s e ，t h i sm e t h o dc a l la c h i e v e t h eo p t i m i z a t i o no ft a s ke x e c u t i o np a t ha n dt h et a s ko r d e rs o r t i n go nc o n d i t i o no ft h e p a t hc o s ta ss m a l la sp o s s i b l e F o rm u l t i - A G Vt e s t , t h er e s u l ts h o w st h a tt h em e t h o d u s e di nt h i sp a p e rc a ne f f e c t i v e l ya c h i e v et h ec o m p l e t i o nt a r g e to fa l lt h et a s k si nt h e s h o r t e s tt i m ea n dt h et a s kd i s t r i b u t i o nf o rA G V s y s t e mm o r e b a l a n c e d F i n a l l y , t h i sp a p e rd i s c u s s e dt h em e t h o dt os o l v et h eA G Vs c h e d u l i n gp r o b l e m ， a n dg i v e st h ed i r e c t i o nf o rf u r t h e rs t u d y K e y w o r d s ：A G Vs c h e d u l i n g ；d i s c r e t ep a r t i c l es w a r mo p t i m i z a t i o n ；T S Pp r o b l e m ； o p t i m i z a t i o n I V 山东大学硕士学位论文 第1 章绪论 1 1 课题背景及意义 自动化仓储系统中A G V 的应用日渐显示出其优越性，主要是由于其适应性 好、可靠性高、柔性好、能实现生产和搬运功能的自动化和集成化，在各国各行 业都得到广泛地应用。 近两年来，国内对A G V 的需求量正在以井喷的势头增长，除了传统的A G V 使用量最多的汽车和烟草行业，A G V 在其他行业中的应用也在逐渐增加，如家电 业、食品饮料业等。然而，与发达国家相比，国内的A G V 技术水平还处于初级阶 段，仅相当于欧美国家上世纪8 0 年代初的水准。 随着计算机集成制造系统技术的逐步发展和工厂运作自动化的趋势，自动化 立体仓库和柔性制造系统的广泛应用，A G V 作为调节和联系离散型物流系统，使 其作业连续化的必要的自动化装卸搬运手段，其应用范围和技术水平得到迅猛发 展I l 】o 据相关资料显示，在产品生产的整个过程中，用于加工制造的环节仅占5 的 时间，其余9 5 都用于储存、装卸、等待加工和输送等环节。在美国，劳动成本 在生产总成本中所占比例不足1 0 ，而且这一比例还在呈现不断下降的趋势，储 存、运输等环节的费用却占生产总成本的4 0 ，因此目前各工业强国的企业将改 造物流结构、降低物流成本作为在竞争中取胜的重要措施【2 1 。为适应现代生产的 需要，物流正在向现代化的方向发展。自动导引小车( A G V ) 因其在可靠性、柔 性、适应性等方面的优势，能够实现搬运和生产功能的自动化和集成化，逐渐得 到广泛应用【3 J 。 当然，这与不同国家的具体情况有关。目前中国的大多数企业属于劳动密集 型，也就是主要靠人力来生产制造，虽说很多企业抱怨招工难的问题，但实际上 劳动力还是比较充足的。加上中国劳动力的廉价，因此企业对于自动化的要求相 比于很多欧美国家来说就显得没那么高。例如，一台激光导引后叉式A G V = 1 0 W 欧元，一个叉车工人一年的工资= 3 W 欧元，也就是说一台A G V = 3 个工人1 年工 资，而且没包括福利，保险，加薪等等各种人力消耗。在这种情况下，欧美国家 对A G V 全自动化的依赖才会这么大，才会促进A G V 往更先进的方向发展。到现 山东大学硕士学位论文 在为止，有数据表明，欧美A G V 小车的覆盖面广：各种驱动模式，各种导引方式， 各种移载机构应有尽有，系列产品的载重量可从5 0 k g 到6 0 0 0 0 k g ( 6 0 吨) 。目前 承载已经达到了1 5 0 吨，运用了1 6 个驱动轮；用于自动化集装箱码头的A G V 速 度已经达到了5 m s ( 1 8 k m h ) ，还在发展第3 代，时速将达到5 0 k m h 以上。而国 内一些中小型企业考虑的首要因素是如何尽快收回成本。 目前国内应用A G V 的领域主要包括柔性制造系统，在柔性制造系统中，怎样 实现A G V 的有效调度成为生产领域的难题，原因是在生产制造过程中，仅有5 的时间用于生产，而9 5 的时间里都是在进行原料、半成品以及成品的搬运装卸 等环节，因此对于这方面的研究也是很多的。其次，随着中国汽车工业的蓬勃发 展，为了提高自动化水平，已经有很多汽车制造企业将A G V 用于生产线或发动机 生产线上，能在很大程度上提高生产过程中的自动化水平，降低工人的劳动强度， 并且降低劳动过程中带来的危险，并适应可能发生的装配场地的变动等。在国外， 这类应用早已屡见不鲜，而在国内汽车行业中，如上海通用、一汽大众以及上海 大众等合资企业，采用先进的现代化生产技术，运用A G V 进行现场的流水线操作， 凸显了A G V 的灵活机动、高效运作，配合生产计划，高效完成生产任务的能力。 最后，不得不指出的是，A G V 在烟草行业的应用，烟草行业具有柔性化程度高、 运送环节多、信息系统研究严格以及物料流量大等特点，A G V 作为现代化的物流 仓储手段，具备了满足上述研究的条件，此外烟草行业具有较好的整体效益，也 是促进烟草行业对A G V 的需求。卷烟原料配料库中，A G V 同样发挥了不可替代 的作用，对于自动化立体库的供应原料，以及在发生突发情况时，机动灵活的处 理生产任务等。此外，在国内很多行业领域中，也开始大量出现了A G V 的身影， 当然大部分还是处于示范性引进的阶段，距离大规模的A G V 应用还是存在着一定 的差距的，但是示范性的引进技术，对于国内自动化程度的提高以及适应将来大 规模引进时带来的技术问题等，都起到了提前练兵的效果。应用A G V 的意义总结 起来包括灵活性、先进性、兼容性、可靠性、示范性以及安全性。 但随着劳动力成本的不断攀升，国内企业明显出现了招工难的问题。而对于 成本较低、技术含量低的A G V 需求明显提升，由于不需要自己开发，因此这种 A G V 受到了企业的青睐，当然这只是我国从机械化向自动化迈进的进程中，不得 己却必不可少的一步，而这种A G V 与价格昂贵的A G V 相比，明显具有智能性不 高、信息交互能力差等弱点。因此需要集中控制来实现其调度，但目前大部分的 2 山东大学硕士学位论文 研究集中在先进的A G V 的研发方面，忽略了这些技术上相对落后的A G V 的调度 的研究，致使很多企业在这类A G V 的引进过程中，调度不当引发一系列问题。于 是，如何实现这一类A G V 有效、合理地调度，便成了现阶段国内应用A G V 的企 业面临的重要问题。 1 2 自动化仓储系统A G V 调度文献综述 国外学者【4 】【5 】【6 】【7 】对自动化仓储系统中调度方面的研究取得了很多成果，这些 成果为提高自动化仓储系统中设备资源的利用率和企业的效益发挥了重大的作 用，同时也为动态自动化仓储系统调度的研究奠定了坚实的基础。L i m ，J o o n M o o k L 【8 】应用遗传算法和计算机模拟方法对在线调度系统进行研究，包括存储设计策 略、出入库机器调度规则、库计划控制等优化；K O O 等【9 】在A G V 调度规则下建 立了A G V 的运行时间模型，并用传统的启发式算法解决问题；美国的C h o w 教授 【1 0 】等提出了应用排队和仿真模型来区分关键性能参数并比较不同调度规则的方 法；G i n m e r 掣1 1 】提出了固定部分变量的启发式方法解决大规模的多种公共汽车调 度问题以减少运输成本。 国内学者对A G V 调度方面的研究主要有邮政自动化仓库、中烟工业原料立体 库、柔性制造系统( F M S ) 等方面的A G V 调度问题。 剡昌锋等1 2 】【1 3 1 通过分析邮包自动化仓库，提出一种改进的遗传算法求解在线 调度问题，并用计算机模拟仿真评判调度方法的优劣，该方法与基于规则的启发 式方法进行比较，大幅度地缩短A G V 的空载时间。李志宏【1 4 】在智能邮政分布式 及混合建模研究中，对邮政运输调度系统进行了深入研究，研究了A g e n t 之间的 协调调度规则和学习机制。 赵长友【l5 J 在烟叶原料配方立体库的优化研究中，对有固定轨道的A G V 的作 业调度进行优化，并分析了单A G V 与多A G V 作业调度优化的异同。金芳等【l 6 】 运用排队论方法解决了某烟厂烟叶自动化立体仓库的A G V 调度问题，主要研究的 是直线导轨型A G V 的调度问题。顾红【1 7 】在卷烟企业物流系统柔性管理研究中， 对环型A G V 的调度规则及调度问题建模，并用遗传算法加以实现。 任小龙等【l 副研究了考虑实际交通状况下的F M S 中A G V 与工件的同步调度问 题，实现了A G V 系统的P e t r i 网建模以及路径优化调度。姚君遗等【l9 】对F M S 中 A G V 调度进行了分析，建立数学模型，并提出了相应的算法，研究了任务序列对 3 山东大学硕士学位论文 系统运行效率的影响。王佳溶【2 0 】基于F M S 中多A G V 系统的调度优化问题提出了 两阶段控制策略和带约束的多目标遗传算法的控制策略。边培莹【2 l J 从粒子群算法 原理入手，以提高F M S 的整体销量为目标，分析粒子群算法在F M S 中的A G V 调 度实现方法。雷定道等口2 1 从F M S 中多机多请求出发，以最小化车辆数、最大化满 意度、最小化总运行距离为目标，提出了多台A G V 多请求处理的数学模型，并采 用混合遗传算法，确定请求与A G V 对应。 国内其他学者【2 3 1 也用不同的方法进行自动化仓储系统调度问题的研究。汪达 开1 2 4 建立了一种简化的仓库模型，针对该模型将出入库作业解析为由任务号相关 联的出入小车、堆垛机的出入任务，然后提出根据设备任务执行算法完成出入 库任务；陈方建【2 5 1 用面向对象着色P e t r i 网模型和时态逻辑方法对输送系统调度问 题进行了研究，解决死锁问题，给出系统行为的时态逻辑规范和避免死锁的最大 允许反馈控制策略：徐香玲等2 6 】对自动化立体仓库输送系统建立仿真P e t r i 网模型， 给出启发式调度规则和优化算法；田国会2 7 1 通过对货位分配原则和自动化仓储系 统中作业调度归纳总结，建立专家系统知识库，论证专家系统在自动化仓储系统 调度中应用的可行性。 通过对自动化仓储系统中输送系统调度方面的研究发现，目前大多数研究成 果都是基于对巷道堆垛机调度的研究，而对A G V 调度方面的研究很少；在线调度 研究方法还不够成熟，还尚未形成一个能被普遍接受的方法【2 3 】：对只应用A G V 作为搬运工具的自动化仓储系统的调度问题研究更是少之又少。 1 3 研究内容和结构安排 本文主要研究自动化仓储系统中A G V 调度的研究与实现，着重解决以下两个 问题： ( 1 ) A G V 调度功能分析与调度逻辑； ( 2 ) A G V 调度的具体算法实现以及针对具体问题提出相应的解决方案。 论文的研究内容结构安排如下： 第一章：绪论。本章主要阐述论文提出的课题背景和研究意义，总结A G V 在 国内外的应用与A G V 调度方面的国内外研究现状，提出论文研究的思路，结合国 内现阶段A G V 的发展情况，简要地概括本文的解决思路。 第二章：粒子群算法相关理论综述。概述粒子群算法的数学描述和离散粒子 山东大学硕士学位论文 群算法的三种离散化策略。 第三章：A G V 调度功能分析与设计。首先，介绍本文采用的A G V 控制系统， 针对集中式控制系统，提出了其优缺点。其次，分析与设计了A G V 调度系统实现 的四个功能，对各功能实现以及实现过程中的数据交互等内容加以分析。最后， 介绍了实现基于以上四个功能的A G V 系统的工作方式。 第四章：调度建模与分析。本章对于单A G V 和多A G V 的调度问题进行分析， 并且建立相应的数学模型，运用求解T S P 问题的思想，建立单A G V 的模型，以 期达到在路径代价最小的情况下，实现对单A G V 任务的排序，从而实现单A G V 路径优化。对于多A G V 问题，本文采用多车辆路径规划问题的思想进行求解。 第五章：求解算法与仿真。首先阐述采用的粒子群算法求解调度问题的基本 步骤。对于A G V 的调度仿真分别从单A G V 和多A G V 入手，简单分析其异同点， 并通过算法求解出A G V 的优化调度方案。对于多A G V 路径规划时可能发生的碰 撞问题，本章提出了解决的具体逻辑及流程。 第六章：总结与展望。对全文进行总结，提出论文研究的不足及可改进之处， 展望下一步研究的重点，为A G V 调度研究提供思路和方法。 本文的重点在于第四章和第五章，论文的研究框架如图1 1 所示。 图1 1 论文框架结构图 5 I JJ 东大学硕士学位论文 6 山东大学硕士学位论文 第2 章算法相关理论 2 1 粒子群优化算法 1 9 9 5 年，受自然界中鸟群模型的启发，K e n n e d y 博士和E l b e r h a r t 博士，提出 粒子群算法。该算法把鸟群栖息地作为求解问题空间，之后通过鸟群中个体的信 息交互，使得较好解出现的可能性大大增加，当较好解出现时，个体之间的信息 指引群体中所有粒子朝可能解位置聚集。具有更强的全局优化能力和实现简单是 P S O 算法相对于其他进化算法的优势。算法一经提出，引起了广泛的关注，短短 时间里涌现了大量的研究成果，成为研究热点。这些研究成果表明，G A 所能解 决的各类优化问题都能由P S O 算法解决【2 9 】【3 0 】【3 1 1 。 粒子群算法同样存在一般生物算法早熟、局部最优的缺点，针对这些问题粒 子群的改进方法尚处于探索阶段。粒子群算法中，相关参数均属于连续实数域， 因此，粒子群算法主要适用于求解连续空间域的数值优化问题【3 2 1 。近年应用粒子 群算法解决离散问题的研究越来越多，其优越性也使得其成为这方面的研究热点 p 3 】1 3 4 】 o P S O 算法连续空间中的算法的数学描述如下： 设粒子群的种群规模为M ，决策空间刀维，其中粒子f 在时刻t 的坐标位置可 以表示为Z 刊。岛，兄) ，i = 1 ，2 ，彤，粒子f 的速度定义为每次迭代中粒子移动 的距离，用嘲，V ! ；2 ，吒) 表示，则粒子f