（计算机应用技术专业论文）立体仓库固定货架拣选路径优化的蚁群算法研究.pdf

摘要 摘要 随着企业生产规模的不断扩大，自动化立体仓库由于其物资存储效率高， 占用空间少等特点越来越被广泛应用。立体仓库主要使用固定货架来存放货物， 对固定货架货物拣选路径的优化是提高立体仓库使用率的一个非常有效的方 法。由于立体仓库规模较大，对其进行仿真试验和研究，可以预防实际操作中 容易出现的问题，减少不必要的损失。本文将固定货架拣选路径问题归结为典 型t s p 问题，并深入研究蚁群算法对该问题进行优化。 本文首先深入分析了三个典型的蚁群算法系统：蚂蚁系统，蚁群系统和最 大最小蚂蚁系统；在详细描述了他们的数学模型后，对他们分别使用m a t l a b 7 0 编程并进行仿真试验，对数学模型中提出的参数进行分析，找出参数最合适的 取值范围；同时分析各个算法的特点，结合立体仓库固定货架拣选路径问题的 实际情况，选出适合固定货架拣选的数学模型。 其次，在已成熟的蚁群算法的基础上，提出了新的算法优化策略，其中包 括根据迭代次数自适应调整q 0 参数，对每次迭代的局部最优路径采用2 一o p t 策略 优化更新和使用精英策略对信息素更新方式进行优化，通过仿真试验对以上优 化算法进行分析，选取有较好优化效果的算法。 最后，综合以上分析，选取出适应固定货架拣选路径优化的数学模型，在 此基础之上提出新的蚁群算法，结合仿真试验分析，确定新的蚁群算法可以以 较快的速度找到较优的路径，极大地提高了立体仓库的使用效率。 关键字：蚁群算法旅行商问题路径优化固定货架物流仿真 a b s t r a c t a b s t r a c t w i t ht h es o c i a l p r o d u c t i v i t yo fc o n t i n u o u s l yd e v e l o p m e n t ，t h e a u t o m a t i c w a r e h o u s e ，r a t h e rt h a nn o r m a lo n e ，i sb e n e f i t i n gi nh i g h e rs t o r a g ee f f i c i e n c ya n d l e s s e rs p a c eu s a g e s o ，m o s to ft i m e ，i tw a ss e l e c t e dt o s t o r a g em a t e r i a la sl a g e r a p p l i c a t i o n sw i t hf i x e ds h e l f t h ef o l l o w i n gr e s e a r c ho nt 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 nf o rf i x e ds h e l fw o u l ds i g n i f i c a n t l yi n c r e a s ee f f i c i e n c yo fa u t o m a t e d w a r e h o u s e w i t ht h ep a t ho p t i m i z a t i o na n dv e r i f i e db ys i m u l a t i o n ，m i s h a n d l i n gi s s u e i nt h ea c t u a lo p e r m i o nc a nb er e m a r k a b l yp r e v e n t e d ，t h u si td or e d u c eu n n e c e s s a r y l o s s e s t h i sa r t i c l ew i l la t t r i b u t et h es h e l fp a t hs e l e c t i o np r o b l e mt ot h et r a v e l i n g s a l e s m a np r o b l e m ，a n dd i v ed e e p l yt oa n tc o l o n ya l g o r i t h mc a r r i e sa st h eb a s e l i n e f o r t h ep a t ho p t i m i z a t i o n t h ea r t i c l eh a sa n a l y z e dt h r e et y p i c a la n tc o l o n ya l g o r i t h m i cs y s t e m s ：1 a n t s y s t e m ，2 a n tc o l o n ys y s t e m ，3 m a x m i na n ts y s t e m m a t l a b 7 0h a sb e e nu s e dt o e s t a b l i s ht h o s e3m a t h e m a t i c a lm o d e l s ，t oc o m p i l ep r o g r a ma n dp e r f o r ms i m u l a t i o n o nt h o s e3m o d e l so n eb yo n e t oa n a l y z e dp a r a m e t e r si nt h em o d e l ，a n df i n dt h e o p t i m i z e dp a r a m e t e rr a n g e c o m p a r i s o nf o rt h em o s ta p p r o p r i a t ev a l u es c o p ea n d t h e na n a l y z e st h ec h a r a c t e r i s t i co fe a c ha l g o r i t h m t h ea u t o m a t e dw a r e h o u s eo r d e r p i c k i n gr o u t eo p t i m i z a t i o no ft h ef i x e ds h e l fa c t u a ls i t u a t i o n ，a n df i n do u tt h em o s t s u i t a b l em a t h e m a t i c a lm o d e lf o rt h ef i x e ds h e l fs e l e c t i o nc a s e b a s eo na n tc o l o n ya l g o r i t h m ，i th a sb e e np r o p o s e ds o m en e wo p t i m i z e d m e t h o di nm ya r t i c l e ，i n c l u d i n gr e a l t i m e a d j u s t i n gs e l f - a d a p t e dp a r a m e t e rq o a c c o r d i n gt ot i m e so fi t e r a t i v e ，u s et h e2 - o p to p t i m i z a t i o ni ne a c ht i m ei t e r a t i v et of i n e t u n el o c a lo p t i m i z a t i o ns e a r c h i n gs t r a t e g ya n du s e st h eo u t s t a n d i n gs t r a t e g yt o o p t i m i s tl o c a li n f o r m a t i o nu p d a t em e t h o d a f t e ra n a l y z eo nt h es i m u l a t i o nr e s u l tb a s e o nt h e s ea l g o r i t h m so p t i m i z a t i o n ，s e l e c tt h eo p t i m i z e dm e t h o d f i n a l l yw i t ht h eo p t i m i z e dm a t h e m a t i c a lm o d e lb a s eo nn e wa n tc o l o n y a l g o r i t h mw em e n t i o n e db e f o r e ，c o n f i r mt h en e wa n ta l g o r i t h mw i l ls u p p o r to n f a s t f i n d i n go fo p t i m i z e dp a t h ，i tc a nb ec l e a r l yo b s e r v e dt h a tw a r e h o u s e se f f i c i e n c y i i a b s t r a c t w a ss i g n i f i c a n t l yi n c r e a s e d k e yw o r d s ： a n tc o l o n y a l g o r i t h m ，t r a v e l i n g s a l e s m a np r o b l e m ，p a t h o p t i m i z a t i o n ，f i x e ds h e l f , l o g i s t i c ss i m u l a t i o n i i i 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名： 年月日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年月 日 各密级的最长保密年限及书写格式规定如下： 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、己公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名： 年月 日 第一章引言 1 1 1 物流系统简介 第一章引言 第一节物流系统 物流是指物资实体的物理流动过程，即物资场所的转移和流动过程中时间 的占用。它是由第二次世界大战期间军事后勤工程的概念演变而来的，现在己 经扩大到流通领域、生产领域以及其他社会经济生活当中。 物流的基本任务是完成物资的储存和运输。围绕这一基本任务，物流还应 包括物资的计划、管理、检验、包装、装卸等，最终要根据物资的种类、数量、 和质量，在最合适的时刻，以最低的成本，将其输送到正确的地点，及时完成 物资信息的传输和修改，以及运输工具的使用和回收这一全过程。 物流按照其活动的规模和范围可以分为社会宏观物流、企业物流和第三方 物流【1 1 。社会宏观物流贯穿生产领域、流通领域和消费领域，包含了由原材料到 成品，由产品到商品，再经过流通环节，送到消费者手中的整个过程，即物资 运输、储存、搬运、包装、顾客服务、订单处理、信息沟通等过程。企业物流 则是企业内部各工序间、各车间内、仓库内、厂内以及它们之间的物流过程， 它主要由供应物流、生产物流、销售物流和回收物流组成。第三方物流是指企 业作为一个单独的经营方来对物流进行管理，它既不涉及生产又不涉及销售， 只是通过第三方的身份来经营管理物料的输送及储存。 回顾物流技术的发展历史，大致可以分为五个阶段【2 j ： 第一代物流是人工物流。人类自有文明以来，物流一直是人类世界的一个 重要组成部分。初始的物流是从人们的举、拉、推和记数等人工操作开始的， 虽然人工物流是第一代物流，但在今天，人工物流仍存在于所有的系统当中。 第二代物流是机械物流。由于机械设备和管理机构的引入，人类的能力和 活动范围都扩大了。现代化设备能让人们举起、移动和放下更重的物体，速度 也更快，机器延伸了人们的活动范围。从1 9 世纪中叶到2 0 世纪中叶的一个世 纪里，这种机械物流一直起主导作用，同时它在今天的许多物流系统中也仍然 第一章引言 是一个主要的组成部分。 第三代物流是自动化物流。自动存储系统( a s r s ) 、自动导引车( a g o ) 、 电子扫描器和条形码是自动化系统的主要组成部分。同时，自动化物流也普遍 采用机器人堆垛物料和包装、监视物流过程及执行某些操作。自动输送机系统 提供物料和工具的搬运，加快了运输的速度，使物流的效率大大提高了。 第四代物流是集成物流。它强调在中央控制下各个自动化物流设备的协同 性，中央控制通常由主计算机实现。这种物流系统是在自动化物流的基础上进 一步将物流系统的信息集成起来，使得从物流计划、物流调度直到将物料运输 到达生产的各个过程的信息，通过计算机网络相互沟通。它不仅使物流系统各 单元间达到协调，而且使生产与物流之间达到协调。 第五代物流是智能型物流。在生产计划做出后，自动生成物料和人力需求； 查看存货单和购货单，规划并完成物流。这种物流系统将人工智能集成到了物 流系统中。 1 1 2 现代物流技术的发展 现代物流是人类进入信息经济时代后适应全球经济一体化的产物，可以说 现代物流是现代社会经济正常运行的主动脉。物流管理最初发源于美国，早在 第一次世界大战后的2 0 世纪2 0 年代美国的理论界就开始使用“p h y s i c a l d i s t r i b u t i o n 作为企业经营活动中一个重要的要素来加以考察和研究；到了第二 次世界大战，大规模的后勤供给活动促使人们开始运用运筹学、系统论的观点， 以保障物资运输链条的高效运转，并以最少的周转环节，最短的时间保证物资 运输及时到达目的地p j 。 二战后，物流的理论与管理方法得到企业及政府管理部门的普遍认可和赞 同，并被广泛应用于社会实践和生产管理中去，其理论在实践中得到了进一步 的发展和深化；特别是上世纪8 0 年代以后，m r p 、m r pi i 、m i 冲i 、d r p 、 d r pi i 、e r p 等大型先进管理系统软件的开发和应用，极大推动了现代物流和 供应链管理理论在生产流通全过程的广泛应用，并形成了综合物流的概念和供 应链管理过程一体化的概念。 目前，世界上一些经济发达的国家，为了充分发挥货物运输的效率，在其 中心城市、交通枢纽周围都设有货物流通中心，而且已联结成网络。 2 第一章引言 信息技术的快速发展，特别是电子商务技术、网络技术、数据库技术和 g p s g i s 技术的应用与发展，促进了电子信息技术与物流实际应用的结合。在现 代物流管理过程中，信息化、网络化的特征愈来愈明显，人们甚至开始使用 e l o g i s t i c s ( 电子物流) 来指现代物流活动，现代物流愈发体现出专业化、国际 化、一体化的特点。在全球化浪潮的推动下，如何利用现代物流的理念，结合 电子技术、信息技术、网络技术、数据库技术、数据挖掘技术推动物流产业的 升级与整合，开拓出一条跨越式的发展道路来，是当代物流产业必须面对并应 解决的问题。 第二节物流仿真 1 2 1系统仿真技术简介 系统仿真是建立在系统理论、控制理论、相似理论、数理统计、信息技术 和计算机技术等理论基础之上的，以计算机和其他专用设备为工具，利用系统 模型对真实或假象的系统进行试验，并借助于专家经验知识、统计数据和系统 资料对试验结果进行分析研究，做出决策的- - f - j 综合性和实验性的学科【4 】。 使用系统仿真作为研究方法主要是由于直接使用实习系统进行研究存在着 很多现实性的问题，主要有： 1 ) 安全性：在研究重要的、有人身安全或者设备安全威胁的系统时，不允 许在实际系统上进行试验。 2 ) 不可逆性：很多系统是不可逆的，比如系统可能导致无法挽救的灾害。 3 ) 投资风险过大：一些重大的工程项目、重大设备系统很复杂，投资巨大， 不允许在实际系统上进行实验。 4 ) 研究时间过长：多数情况下，在实际系统上研究问题往往需要经历较长 的时间。 5 ) 真实系统尚未建立。 基于以上原理，利用仿真技术来研究系统是非常必要的。 系统仿真技术是( 物理的、数学的或非数学的) 模型的建立、验证和试验 运行技术。现代仿真技术的特点可归纳为： 1 ) 系统仿真技术是一门通用的支撑性技术。 第一章引言 2 ) 系统仿真技术学科的发展具有相对的独立性，同时又与光、机、电、声， 特别是信息等众多专业技术领域的发展互为促进。 3 ) 系统仿真技术的发展与应用紧密相关。 4 ) 系统发展技术应用正朝着“全系统”、“系统全生命周期 、“系统全方位 管理”的方向发展。 1 2 2 现代物流与系统仿真 随着现代物流的日益发展，物流作为一个多因素、多目标的复杂系统，追 求其整体的优化已成为一个复杂的系统分析问题。现代物流越来越多的强调物 流的系统化和综合化，这样就更需要使用系统分析的方法对其进行分析和研究。 系统仿真技术通过模型建立、验证和试验运行的过程，成为了一门通用的 支撑性技术。在决策者们面对一些重大的，棘手的问题时，能以其他方法无法 替代的特殊功能，为其提供关键性的见解和创新的观点。而系统仿真技术正是 适应了物流系统的复杂化，物流目标多样化的发展需要。 系统仿真方法研究物流系统可以分为以下几类： 1 ) 物流过程仿真研究 物流过程是指运输、仓储、装卸、包装等物流的功能过程。研究目的归结 为回答诸如：在时间的进程中，这些过程是如何推进的? 推进过程中发生了哪 些事件? 这些事件引起系统状态发生了哪些状态变化，等问题。用仿真工具研 究这些问题，我们归结为物流过程的仿真研究。 2 ) 物流管理仿真研究 物流管理的仿真研究是为物流管理决策分析服务的。例如，交通运输网络 的布局规划、自动化物流系统的策略运用、物流园区规划、供应链库存控制策 略等。 3 ) 物流成本仿真研究 物流成本的计算是一件细致复杂的事情。在物流管理中，有物流成本管理 法，即以降低物流成本为评价指标，不断改进物流流程，改进物流管理方法。 准确的物流成本计算对于改进物流作业与管理十分重要。 本文主要研究的立体仓库的仿真就属于物流过程仿真研究的范畴。 4 第一章引言 第三节立体仓库固定货架拣选路径问题 1 3 1问题背景 企业现代化生产规模的不断扩大和深化，使得仓库成为生产物流系统中的 一个重要且不可缺少的环节。立体仓库正以它最小的占地面积和最佳的空间利 用率，逐步代替了面积大利用率低且陈旧落后的平面仓库，这种代替促使仓储 物流业的水平提高。 自动化仓库自从五十年代首次出现以来，由于它在实践应用方面所具有的 无比优越性，得到了迅速的推广、应用与发展。现在自动化立体仓库已经成为 现代物资存取技术与自动化技术相结合的高新技术产物，是物流自动化的显著 标志之一，是现代化大生产的必然产物，自动化技术和计算机技术的迅速发展 为仓库的自动化提供了有力的条件。 自动化立体仓库有如下优剧5 j ： 1 ) 存储量大，占地面积小。由于自动化仓库向高层、立体化方向发展，同 时堆垛机的作业通道宽度大幅度减少，因此大大的提高了自动化仓库的面积和 空间的利用率； 2 ) 可迅速方便的进行货物的入、出库作业。由于库存分别放在货架的独立 货位内，彼此互不堆压，因此在存取时互不干扰； 3 ) 便于实现仓库的机械化、自动化，从而可以节约劳动力、减轻劳动强度， 提高入、出库的作业效率和仓库周转能力； 4 ) 提高了库存管理的准确性和快速性，从而相对减少库存量，减少了库存 占有资金； 5 ) 缩短交货时间，增加了操作的安全性，减少了货物损坏率，提高了服务 质量； 6 ) 提高了整个工厂企业的管理和生产效率。 目前美国、日本、德国和英国是世界上拥有自动化仓库最多的国家6 ，7 ，8 ，9 1 。 我国自动化仓库起步较晚，于七十年代后期开始建立自动化仓库，但在当时的 发展却相当缓慢。自八十年代我国进行改革开放发展社会主义市场经济以来， 国民经济迅速增长，科学技术也取得了突飞猛进的发展。与工业增长相应的自 动化仓库的应用也取得了长足的发展，但在数量和技术上同发达国家相比仍然 5 第一章引言 姗刚托 三二二三习口 口 - i 雠台 图1 1 立体仓库总体构成图 固定货架部分一般由若干仓库巷道组成，每一巷道由一台或多台堆垛机进 行服务。巷道两侧有许多存放货物的货箱，使用堆垛机可对某一货位的货物进 行存取操作，为了便于存取，在货箱朝向巷道的一侧设有一个开口，由此开口 将货物取出或存入货箱。每一巷道一般有一出库台和一入库台，货物由此出库 或入库。 旋转货架一般由多层可分别独立旋转的货架构成，每一层货架上有若干个 货格，并有一个或多个伺服机，当某一货格旋转至伺服机位置时，可进行存取 6 第一章引言 操作，它适用于存放体积小、重量轻的货物。 输送系统是连接存储区的出、入库台和分拣区的一套自动输送设备。它一 般由导轨和输送小车组成，小车在导轨上运行可到达任意一个巷道的出、入库 台和分拣台。货物出库时，它可以将出库台上的货箱运送到分拣系统分拣出库， 或将要入库的货物运送到指定的入库台。 自动分拣系统可对即将出库的货物进行识别、分类、分配、入箱。 计算机管理和监控系统一般采用分级集成系统，中央处理机提供管理信息， 分处理机用以控制仓库的特定部分，以便对全部作业进行管理和控制。 为了便于进行倒库作业，有些仓库还设置倒库台，以便在需要的时候将货 箱旋转1 8 0 。 1 3 2 现状研究 目前，立体仓库中有固定货架和旋转货架两大部分来存放货物，其中固定 货架占了相当大的比重，大多数货物存放在固定货架区。 从当前自动化立体仓库的技术结构来看，自动化立体仓库硬件设备的技术 和自动控制及通讯技术已经十分完善，而自动化仓库的优化管理、调度和作业 优化尚未引起人们的高度重视，是一个未完全成熟的方面，因而未能使自动化 立体仓库的作用得到充分发挥。对自动化立体仓库进行优化管理、调度，可以 在不增加设备投资的情况下，减少作业时间，大大提高仓库的运行效率，所以 对固定货架拣选作业问题进行优化，将极大的提高立体仓库的作业效率，同时 它也是自动化仓库技术发展的重要方面，在实际应用中具有十分重大的意义【1 1 | 。 另外，固定货架拣选作业问题与实际中许多其它的组合优化问题具有一定的代 表性，是具有典型性的组合优化问题，因此对该问题的研究不仅具有重大的实 际工程意义而且具有很高的理论价值【l 引。 对于固定货架拣选作业问题的优化算法有启发式算法、神经网络算法、弹 性网算法和路径代数算法等，其中启发式算法又分为邻近启发式、最邻近插入 启发式、几何启发式等三种算法，它们规则简单、易于理解，所需计算时间较 少，所得解在多数情况下尚能满足一定要求，但有时解的质较差，这些方法适 用于对计算时间要求较高同时求解规模较大的问题。神经网络算法能求得问题 的局部最优解，用于求解小规模问题时，优于启发式算法；当问题规模较大时， 7 第一章引言 解的质量不如采用启发式算法求得的解。弹性网算法作为一种求解旅行商问题 的递推算法，可用于求解各种规模的问题，一般说来，解的性能优于启发式算 法；但当问题的规模较大时，所需的计算时间较长。路径代数算法和几种启发 式算法相比，对同一问题，计算时间较后者明显增长，同时前者求解小规模问 题时，一般可以得到较好的解，当问题的规模较大时，解的质量明显下降【l 引。 近年来，随着计算技术的发展，一些新的智能算法，如遗传算法【l4 1 、模拟 退火算法【l5 1 、禁忌搜索算法等得到了迅速发展和广泛应用。本文介绍的蚁群算 法就是一种新型的模拟进化算法。该算法是由意大利学者m d o r i g o 等人首先提 出，并应用该算法求解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 ) 问题、分配问题、 j o b s h o p 调度问题均取得了较好的结果。受其影响，蚁群系统模型逐渐引起了 其他研究者的注意，并用该算法来解决一些实际问题。 蚁群算法是一个增强型学习系统，具有分布式的计算特性，具有很强的顽 健性，易于与其他优化算法融合。但基本蚁群算法在解决大型优化问题时，存 在搜索空间和时间性能上的矛盾，容易出现搜素时间长，收敛速度慢和易陷入 局部最优解的缺点。 针对蚁群算法的这些问题，本文做了大量的仿真试验将蚁群算法进行分析， 并对蚁群算法中的参数进行优化，结果得到了较好的结论，其改进方法对于立 体仓库固定货架拣选所遇到的实际问题有着很大的实用价值。 第四节 m a tia b 简介 m a 廿a b 作为美国m a t h w o r k s 公司开发的用于概念设计，算法开发，建模仿真， 实时实现的理想的集成环境。是目前最好的科学计算类软件【l6 1 。 作为和m a t h e m a t i c a 、m a p l e 并列的三大数学软件。其强项就是其强大的矩 阵计算以及仿真能力。m a t l a b 的名称源自m a t r i xl a b o r a t o r y ，它是一种科学计算 软件，专门以矩阵的形式处理数据。 每次m a t h w o r k s 发布m a t l a b 的同时也会发布仿真工具s i m u l i n k 。在欧美很 多大公司在将产品投入实际使用之前都会进行仿真试验，他们所主要使用的仿 真软件就是s i m u l i n k 。 。m a t l a b 提供了自己的编译器：全面兼容c 以及f o r t r a n 两大语言。所以m a t l a b 是工程师、科研工作者手上最好的语言，最好的工具和环境。 第一章引言 m a t l a b 将高性能的数值计算和可视化集成在一起，并提供了大量的内置函 数，从而被广泛地应用於科学计算、控制系统、信息处理等领域的分析、仿真 和设计工作，而且利用m a t l a b 产品的开放式结构，可以非常容易地对m a t l a b 的 功能进行扩充，从而在不断深化对问题认识的同时，不断完善m a t l a b 产品以提 高产品自身的竞争能力【1 7 1 。 目前m a t l a b 产品族可以用来进行： 数值分析 数值和符号计算 工程与科学绘图 控制系统的设计与方针 数字图像处理 数字信号处理 通讯系统设计与仿真 财务与金融工程 m a t l a b 是m a t l a b 产品家族的基础，它提供了基本的数学算法，例如矩阵运 算、数值分析算法，m a t l a b 集成了2 d 和3 d 图形功能，以完成相应数值可视化 的工作，并且提供了一种交互式的高级编程语言m 语言，利用m 语言可以 通过编写脚本或者函数文件实现用户自己的算法。 m a t l a bc o m p i l e r 是一种编译工具，它能够将那些利用m a t l a b 提供的编程 语言m 语言编写的函数文件编译生成为函数库、可执行文件c o m 组件等 等。这样就可以扩展m a t l a b 功能，使m a t l a b 能够同其他高级编程语言例如 c c + + 语言进行混合应用，取长补短，以提高程序的运行效率，丰富程序开发 的手段。 利用m 语言还开发了相应的m a t l a b 专业工具箱函数供用户直接使用。这些 工具箱应用的算法是开放的可扩展的，用户不仅可以查看其中的算法，还可以 针对一些算法进行修改，甚至允许开发自己的算法扩充工具箱的功能。 目前m a t l a b 产品的工具箱有四十多个，分别涵盖了数据获取、科学计算、 控制系统设计与分析、数字信号处理、数字图像处理、金融财务分析以及生物 遗传工程等专业领域。 9 第一章引言 第五节论文主要工作及论文结构安排 本文主要工作是使用蚁群算法解决立体仓库固定货架拣选路径优化的问 题。需要对蚁群算法的各类系统进行分析，对其中的参数进行优化，选取适合 固定货架拣选的算法。 。 论文结构安排如下： 第二章说明了固定货架的组成、工作过程和工作原理，将固定货架拣选路 径问题归结为t s p 问题，并对t s p 问题进行描述，介绍其各种解决方案。 第三章详细介绍蚁群算法，介绍蚁群算法发展过程中的各个系统，并将各 个系统通过m a t l a b 7 0 实际编写程序进行仿真试验，对比其中的优缺点，选出适 合固定货架拣选的参数和算法模块。根据蚁群算法的特点对算法进行优化，其 中根据迭代次数不同，优化q o 参数；对每次迭代的最优路径通过2 - o p t 策略优 化；对信息素局部更新时选取不同的信息素增量。所有优化策略均通过m a t l a b 7 0 仿真试验得到确定数据，可得证其中一些策略可以使结果朝着更优的方向前进。 第四章综合第三章中分析的结论将蚁群算法更新，给出新蚁群算法的数学 模型、算法详细描述和算法流程图，结合固定货架拣选点众多的特点选取较多 拣选点进行仿真试验，通过m a t l a b 7 0 编程得证新蚁群算法优于其他蚁群算法的 结论。 1 0 第二章固定货架拣选工作原理及t s p 问题 第二章固定货架拣选工作原理及t s p 问题 第一节固定货架拣选问题 2 1 1固定货架组成 图2 1 为某立体仓库固定货架。 弓illllil l 卜一l lliiii l 卜卜一iil lll ll l 3 、 r - 1 ，) 、。i 一弓i lill 4 一 j lillllii 口 i 卜卜一l li l l 卜 一liiill 口 弓lllll 8 - - - 一一9 、1 u ，0 上 i 酉弋6 息入口 图2 1 固定货架结构图 如图2 1 所示，1 是货架，2 是有轨巷道堆垛机，3 是链条输送机，4 是升降 机，5 是监控计算机，6 是管理计算机，7 是输送系统手动操作台，8 是轨道输 送机，9 是中央控制室。固定货架一般由若干仓库巷道组成，每一巷道由一台或 多台堆垛机进行服务。巷道两侧有许多存放货物的货箱，使用堆垛机可对某一 货位的货物进行存取操作，为了便于存取，在货箱朝向巷道的一侧设有一个开 口，由此开口将货物取出或存入货箱。每一巷道一般有一个出库台和一个入库 第二章固定货架拣选工作原理及t s p 问题 台，货物由此出库或入库。 2 1 2 货物拣选的工作过程 固定货架拣选的工作过程是这样的：管理计算机根据操作员发送的命令得 知需要取货，然后查询数据库里面的存货信息，获取货物所在的地址。由于堆 垛机一次需要取出很多货物，因此堆垛机要依次到达货物单元所在的位置，确 定要进行拣选作业的货位，然后巷道堆垛机携带一空箱从巷道口出发，依次到 达要进行拣选作业的货位进行拣选作业，拣选完后堆垛机到达巷道口，并将货 箱送到出库台。相应货架的出库台处将需要出货的货物放在输送小车上面，然 后输送小车将货物送往分拣台对货物进行分拣。 2 1 3 货物拣选的工作原理 固定货架拣选的工作原理是在拣选的过程中合理确定拣选路径，使整个拣 选过程所用的时间最短。这样对于有n 个要拣选出库的货位，堆垛机从原点出 发，依次到达要拣选出库的货位，最后回到原点，就是一个典型的旅行商问题 ( 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 ) 问题。求得拣选的最短路径就能保证拣选 作业所用的总时间代价最小。 2 2 1t s p 问题简介 第二节t s p 问题* 巡回旅行商问题( t s p ) ，也称为货郎担问题 1 8 】，是一个较古老的问题。最 早可以追溯到1 7 5 9 年e u l e r 提出的骑士旅行问题。1 9 4 8 年，由美国兰德公司推 动，t s p 成为近代组合优化领域的一个典型难题。应该说，t s p 是一个具有广泛 的应用背景和重要理论价值的组合优化问题，它已经被证明属于n p 难题。 2 2 2t s p 问题描述 旅行商问题( t s p ) 描述为：给定1 1 个城市，有一个旅行商从某一个城市出 1 2 第二章固定货架拣选工作原理及t s p 问题 发，访问每个城市各一次之后再回到原来出发的城市，要求找出最短的巡回路 径。 t s p 不存在有效的多项式解法。t s p 搜索空间随着城市数n 的增大而变大， 所用的旅程路线组合数为( n 1 ) 1 1 2 。5 个城市的情形对应1 2 0 1 0 = - 1 2 条路线， 1 0 个城市的情形对应3 6 2 8 8 0 0 2 0 = 1 8 1 4 4 0 条路线，1 0 0 个城市的情形则对应有 4 6 6 6 3 1 0 1 5 5 条路线。在如此庞大的搜索空间中寻求最优解，对于常规方法和现 有的计算工具而言，存在着诸多的计算困难。 2 2 3t s p 问题解决方案 几十年来，出现了很多近似优化算法用于解决t s p 问题【19 1 ，如临近法( n e a r e s t n e i g h b o r ) 、贪心算法( g r e e d ya l g o r i t h m ) 、最近插入法( n e a r e s ti n s e r t i o n ) 、最远 插入法( f a r t h e s ti n s e r t i o n ) 、双极小生成树法( d o u b l em i n i m u ms p a n n i n gt r e e ) 等 世 彳子0 近年来，又有很多解决该问题的较为有效的算法不断被推出，例如h o p f i e l d 神经网络方法、模拟退火方法以及遗传算法。 蚁群算法也是近年来异军突起的一种算法，其仿照蚂蚁群觅食原理解决t s p 问题在很多行业取得了较好的成绩 2 0 , 2 1 , 2 2 1 。 1 3 第三章蚁群算法解决固定货架拣选问题 第三章蚁群算法解决固定货架拣选问题 第一节蚁群算法简介 蚁群算法( a c a ，a n tc o l o n ya l g o r i t h m ) 来源于对自然界蚂蚁寻找从蚁巢 到食物的最短路径并找到回巢路径方法的研究，是一种自2 0 世纪5 0 年代中期 创立了仿生学以来，人们从生物进化的机理中受到启发提出了许多用以解决复 杂优化问题的方法之一，是一种新型的随机优化算法。 蚁群算法充分利用了蚁群搜索食物的过程与旅行商问题( t s p ) 之间的相似 性，通过人工模拟蚂蚁搜索食物的过程一即通过个体之间的信息交流与相互协作 最终找到从蚁穴到食物源的最短路径来求解t s p 。 蚁群算法的主要特点是【2 3 】： 采用分布式控制，不存在中心控制； 每个个体只能感知局部信息，不能直接感知全局信息； 个体可以改变环境并进行间接通讯； 个体的交互过程表现为群体的复杂行为； 采用改良型的全局搜索方法求解全局最优解； 求解过程不依赖于问题的严格数学性质； 各主体通过相互协作更好的适应环境； 具有潜在的并行性，搜索时从多个点进行。 第二节蚁群算法原理 蚁群算法的原理是参照自然界中的蚂蚁在寻找食物或遇到障碍物时，总能 找到一条从食物到蚁巢或绕过障碍物的最优路径。其原因在于，蚂蚁运动时会 在所经过的路径上释放出一种叫信息素( p h e r o m o n e ) 的物质，蚂蚁在运动过程 中能够感知这种物质的存在及其强度，并以此指导自己的运动方向，蚂蚁倾向 于朝着该物质强度高的方向移动。因此，一由大量蚂蚁组成的集体行为便表现出 一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概 1 4 第三章蚁群算法解决固定货架拣选问题 率就越大，由于在一定的时间内，越短的路径会被越来越多的蚂蚁访问，因而 积累的信息素也就越多，在下一个时间内，被其他的蚂蚁选中的可能性也就越 大，这个过程一直持续到所有的蚂蚁都走最短的那一条路径为止，蚂蚁个体之 间就是通过这种信息交流达到搜索食物的目的。这样构成了一个学习信息的正 反馈过程，可以逐渐逼近最优解。 蚁群算法吸收了如下蚂蚁群体行为的典型特征： 能察觉小范围区域内状况，并判断出是否有食物或其他同类的信息素轨 迹： 能释放自己的信息素； 所遗留的信息素数量会随时间而逐步减少。 3 3 1数学模型 第三节蚂蚁系统算法 蚁群算法首先由意大利学者m d o r i g o 等人于1 9 9 1 年提出来，当时他们称之 为蚂蚁系统( a s ，a n ts y s t e m ) 2 4 】。以求解平面上n 个城市的t s pi 口- j 题为例来 说明。 假设有n 个节点代表n 个城市，d i j 代表第i 和第j 个城市的距离，其中i j n 。m 是蚁群中蚂蚁的数量，b i ( t ) 表示t 时刻位于节点i 的蚂蚁的个数， m = b i ( t ) ( 3 1 ) i = 1 ti i ( t ) 表示t 时刻在城市i j 间的路径上残留的信息量。初始时刻，各条路径 上的信息量相等，设ti j ( 0 ) = c ( c 为常数) 。蚂蚁k ( k _ 1 ，2 m ) 在运动过程中， 根据各条路径上的信息量决定转移方向。p ：( f ) 表示在t 时刻蚂蚁k 由节点i 转 移到节点j 的概率： 承妒 一 1 5 j a l l o w e d k o t h e r w i s e ( 3 2 ) 第三章蚁群算法解决固定货架拣选问题 上式中：a l l o w e d i = v - t a b u t ，表示蚂蚁k 下一步允许选择的节点，v = 0 ，1 ，2 n 为所有节点的集合，t a b u 。为禁忌表，用来记录蚂蚁k 目前已经走过的节点。 口为信息启发式因子，表示轨迹的相对重要性，反映了蚂蚁在运动过程中 所积累的信息在蚂蚁运动时所起的作用。其值越大，则该蚂蚁越倾向于选择其 它蚂蚁已经走过的路径，蚂蚁之间协作性越强。 为期望启发式因子，表示能见度的相对重要性，反映了启发信息在蚂蚁 选择路径中受重视的程度。其值越大，则蚂蚁在某个局部点上选择局部最短路 径的可能性越大。 r l ，( f ) 为启发函数，该启发函数表示蚂蚁从节点i 转移到节点j 的期望程度， 其值为节点i 与节点j 之间距离的倒数。 ( f ) 。1 d 扩 ( 3 3 ) ( 3 2 ) 式表明信息量越多的路径和距离越短的路径被选中的概率越大。经 过一段时间，路径上的信息素逐渐消失，p 用来表示信息素消失程度，0 p 1 ， 1 p 就表示信息素的残留程度，在所有蚂蚁完成了一次循环之后，每条路径上的 信息量按下列公式更新： 乃o + 1 ) = ( 1 一p ) 。乃o ) + 乃( f ) ( 3 4 ) 其中： a r 驴( f ) = a r ； ( 3 5 ) f ；表示第k 只蚂蚁在本次循环中留在路径i j 上的信息素，a r 盯表示本次循 环中路径i j 上的信息素增量。 根据信息素浓度更新策略的不同，有三种不同的算法模型： 1 ) a n t q u a n t i t y ( 蚁量) 模型 公务j 号蚂蚁k 经瑚 【0 其他 ( 3 6 ) ( 3 6 ) 式中，q 是常量，信息素的增量与i j 之间的距离有关。 2 ) a n t d e n s i t y ( 蚁密) 模型 1 6 第三章蚁群算法解决固定货架拣选问题 叫2 骺蚂鬣出 7 ， ( 3 7 ) 式中，q 是常量，信息素只增加一个固定值，与i j 之间的距离无关。 3 ) a n t c y c l e ( 蚁周) 模型 f ；：j 罢蚂蚁k 经过i j 【0 其他 ( 3 8 ) ( 3 8 ) 式中，q 是常量，厶表示第k 只蚂蚁的循环路线，即如果蚂蚁经过 i j ，则信息素增量为一个常量除以蚂蚁k 的循环路线长。这时，信息素增量只与 蚂蚁的循环路线有关，而和具体的d ；，无关。 a n t q u a n t i t y 和a n t - d e n s i t y 利用的是局部信息，蚂蚁在走完一步后更新所有 路径上的信息素，而a n t c y c l e 利用的是整体信息，蚂蚁在一个循环以后，更新 所有路径上的信息素。在a n t d e n s i t y 和a n t c y c l e 模型中，蚂蚁释放的信息素的 浓度与边长以无关；而在a n t - q u a n t i t y 模型中，这两者就建立了相关性，也就是 说蚂蚁下一步倾向于选择比较短的路段。所以a n t q u a n t i t y 模型最适用于最短路 径问题，蚂蚁系统算法选用的是a n t q u a n t i t y 模型。 。 2 3 2 算法描述 ， 根据蚂蚁系统蚁群算法的数学模型，结合立体仓库固定货架拣选操作，这 里给出算法描述： 假设需要取1 1 1 个货柜的货物，堆垛机从起始点开始出发，需要经过这n 。1 个节点取出货物，最后回到起始点。这样把起始点考虑在内共有n 个地址需要 堆垛机走过。首先定义n 个节点的坐标n i ( x i ，y i ) ，其中i = 0 ，1 ，2 n - 1 。x i 表示 固定货架的列地址，y i 表示固定货架的层地址。其中x o = o ，y o = 0 。 运算的步骤如下： s t e p l ，设有r n 个蚂蚁，将这r n 个蚂蚁放在n 个节点( 也就是货柜处) 上作 为各自的起始位置。 s t e p 2 ，根据n 个拣选点得到各拣选点之间的距离d 盯，计算r u ( t ) = l d 盯。设 定a r f ，( o ) = 0 ，ti j ( 0 ) = c ( i ，j = 0 ，1 ，2 n - 1 ) 。 s t e